How to fast transpose byte matrix [][]byte in Golang assembly

[Wei Shen]

Hi all,

Matrix transpose in pure golang is slow in HPC cases, and using package gonum needs structure transformation which costs extra time. So a assembly version may be a better solution.

Sizes of the matrix vary ([][]byte) or can be fixed for example ([64][512]byte), and the element type may be int32 or int64 for general scenarios.

Below is a golang version:

m := 64
n := 512

// orignial matrix
M := make([][]byte, m)
for i := 0; i < m; i++ {
    M[i] = make([]byte, n)
}

func transpose(M [][]byte) [][]byte {
    m := len(M)
    n := len(M[0])

    // transposed matrix
    T := make([][]byte, n)
    for i := 0; i < n; i++ {
        T[i] = make([]byte, m)
    }

    var row []byte // a row in T
    for i := 0; i < n; i++ {
        row = T[i]
        for j = 0; j < m; j++ {
            row[j] = M[j][i]
        }
    }

    return T
}

​

[jake...@gmail.com]

Not a direct answer, but one simple improvement you could do is to allocate all the rows together, then break them up by slicing. So instead of your:

    T := make([][]byte, n)
    for i := 0; i < n; i++ {
        T[i] = make([]byte, m)
    }

Do something like:

    T := make([][]byte, n)

    Q := make([]byte, m*n)

    for i := 0; i < n; i++ {

        T[i] = Q[i*m : (i+1)*m]
    }

In my benchmarks, with your matrix size, this gives a 20-30 percent speedup. In part because it avoids many allocations, but also (I suspect) because the data is contiguous. 

[peterGo]

jake,

I do the same thing but I like to have the correct length and capacity.

func NewMatrix(r, c int) [][]int {
    a := make([]int, r*c)
    m := make([][]int, r)
    lo, hi := 0, c
    for i := range m {
        m[i] = a[lo:hi:hi]
        lo, hi = hi, hi+c
    }
    return m
}

https://play.golang.org/p/ifWtRaiVSQ3

Peter