3
\$\begingroup\$

I have write a normal programm "Transpose the matrix" in go. Suppose input are always correct. I also read the article An Efficient Matrix Transpose in CUDA C/C++. So I keen to know how I can use Go-routines or another efficient way to problem in go way

package main

import (
    "fmt"
)


func main() {
    a := [][]int{{1, 1, 1, 1}, {2, 2, 2, 2}, {3, 3, 3, 3}, {4, 4, 4, 4}}
    r := transpose(a)   
    fmt.Println(r)
}

func transpose(a [][]int) [][]int {
    newArr := make([][]int, len(a))
    for i := 0; i < len(a); i++ {
        for j := 0; j < len(a[0]); j++ {
            newArr[j] = append(newArr[j], a[i][j])
        }
    }

    return newArr
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I have revised my answer to include goroutines. \$\endgroup\$ – peterSO Jan 17 at 1:01
3
\$\begingroup\$

In Go, measure performance. Run benchmarks using the Go testing package.

For example,

$ go test transpose_test.go -bench=. -benchmem
BenchmarkTranspose-4       2471407    473 ns/op    320 B/op    13 allocs/op
BenchmarkTransposeOpt-4    9023720    136 ns/op    224 B/op     2 allocs/op
$

As you can see, minimizing allocations is important. Efficient memory cache usage probably helps too.

transpose_test.go:

package main

import "testing"

func transpose(a [][]int) [][]int {
    newArr := make([][]int, len(a))
    for i := 0; i < len(a); i++ {
        for j := 0; j < len(a[0]); j++ {
            newArr[j] = append(newArr[j], a[i][j])
        }
    }
    return newArr
}

func BenchmarkTranspose(b *testing.B) {
    a := [][]int{{1, 1, 1, 1}, {2, 2, 2, 2}, {3, 3, 3, 3}, {4, 4, 4, 4}}
    b.ResetTimer()
    for N := 0; N < b.N; N++ {
        _ = transpose(a)
    }
}

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

func transposeOpt(a [][]int) [][]int {
    b := NewMatrix(len(a[0]), len(a))
    for i := 0; i < len(b); i++ {
        c := b[i]
        for j := 0; j < len(c); j++ {
            c[j] = a[j][i]
        }
    }
    return b
}

func BenchmarkTransposeOpt(b *testing.B) {
    a := [][]int{{1, 1, 1, 1}, {2, 2, 2, 2}, {3, 3, 3, 3}, {4, 4, 4, 4}}
    b.ResetTimer()
    for N := 0; N < b.N; N++ {
        _ = transposeOpt(a)
    }
}

Goroutines have overhead. For a small task (4 x 4 matrix), the overhead may outweigh any gains.

Let's look at a 1920 x 1080 matrix (the size of an FHD display).

For this type of problem, we examine the optimized transpose function (transposeOpt) and see if it can be subdivided into smaller, concurrent pieces. For example, by row (transposeRow), or the number of available CPUs (transposeCPU).

$ go test goroutine_test.go -bench=. -benchmem
BenchmarkTranspose-4       37   31848320 ns/op   63354443 B/op   15121 allocs/op
BenchmarkTransposeOpt-4   202    5921065 ns/op   16616065 B/op       2 allocs/op
BenchmarkTransposeRow-4   229    5307156 ns/op   16616159 B/op       3 allocs/op
BenchmarkTransposeCPU-4   360    3347992 ns/op   16616083 B/op       3 allocs/op
$

A row is still a small task. Twice the number of CPUs amortizes the goroutine overhead over a number of rows. By any measure -- CPU, memory, allocations -- transposeCPU is considerably more efficient than the original transpose for a 1920 x 1080 matrix.

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

var numCPU = runtime.NumCPU()

func transposeCPU(a [][]int) [][]int {
    b := NewMatrix(len(a[0]), len(a))
    var wg sync.WaitGroup
    n := 2 * numCPU
    stride := (len(b) + n - 1) / n
    for lo := 0; lo < len(b); lo += stride {
        hi := lo + stride
        if hi > len(b) {
            hi = len(b)
        }
        wg.Add(1)
        go func(b [][]int) {
            defer wg.Done()
            for i := 0; i < len(b); i++ {
                c := b[i]
                for j := 0; j < len(c); j++ {
                    c[j] = a[j][i]
                }
            }
        }(b[lo:hi])
    }
    wg.Wait()
    return b
}

However, for a amall, 4 x 4 matrix, the goroutine overhead outweighs any gains.

BenchmarkTranspose-4      2570755    463 ns/op   320 B/op   13 allocs/op
BenchmarkTransposeOpt-4   8241715    145 ns/op   224 B/op    2 allocs/op
BenchmarkTransposeRow-4    908217   1318 ns/op   240 B/op    3 allocs/op
BenchmarkTransposeCPU-4    881936   1330 ns/op   240 B/op    3 allocs/op

As always, when we are exploiting concurrency, we use the Go race detector to check for data races. The overhead to check for data races is considerable. Therefore, we discard any benchmark results.

$ go test goroutine_test.go -bench=. -benchmem -race

By design, there are no data races.

goroutine_test.go:

package main

import (
    "runtime"
    "sync"
    "testing"
)

func transpose(a [][]int) [][]int {
    newArr := make([][]int, len(a))
    for i := 0; i < len(a); i++ {
        for j := 0; j < len(a[0]); j++ {
            newArr[j] = append(newArr[j], a[i][j])
        }
    }
    return newArr
}

func BenchmarkTranspose(b *testing.B) {
    for N := 0; N < b.N; N++ {
        _ = transpose(a)
    }
}

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

func transposeOpt(a [][]int) [][]int {
    b := NewMatrix(len(a[0]), len(a))
    for i := 0; i < len(b); i++ {
        c := b[i]
        for j := 0; j < len(c); j++ {
            c[j] = a[j][i]
        }
    }
    return b
}

func BenchmarkTransposeOpt(b *testing.B) {
    for N := 0; N < b.N; N++ {
        _ = transposeOpt(a)
    }
}

func transposeRow(a [][]int) [][]int {
    b := NewMatrix(len(a[0]), len(a))
    var wg sync.WaitGroup
    for i := 0; i < len(b); i++ {
        wg.Add(1)
        c := b[i]
        go func(c []int, i int) {
            defer wg.Done()
            for j := 0; j < len(c); j++ {
                c[j] = a[j][i]
            }
        }(c, i)
    }
    wg.Wait()
    return b
}

func BenchmarkTransposeRow(b *testing.B) {
    for N := 0; N < b.N; N++ {
        _ = transposeRow(a)
    }
}

var numCPU = runtime.NumCPU()

func transposeCPU(a [][]int) [][]int {
    b := NewMatrix(len(a[0]), len(a))
    var wg sync.WaitGroup
    n := 2 * numCPU
    stride := (len(b) + n - 1) / n
    for lo := 0; lo < len(b); lo += stride {
        hi := lo + stride
        if hi > len(b) {
            hi = len(b)
        }
        wg.Add(1)
        go func(b [][]int) {
            defer wg.Done()
            for i := 0; i < len(b); i++ {
                c := b[i]
                for j := 0; j < len(c); j++ {
                    c[j] = a[j][i]
                }
            }
        }(b[lo:hi])
    }
    wg.Wait()
    return b
}

func BenchmarkTransposeCPU(b *testing.B) {
    b.ResetTimer()
    for N := 0; N < b.N; N++ {
        _ = transposeCPU(a)
    }
}

var a = func() [][]int {
    b := NewMatrix(1920, 1080)
    for i := range b {
        for j := range b[0] {
            b[i][j] = i<<16 + j
        }
    }
    return b
}()

You might want to look at gonum, the Go numeric module. It's open source.

For matrices:

package mat

import "gonum.org/v1/gonum/mat"

Package mat provides implementations of float64 and complex128 matrix structures and linear algebra operations on them.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.