OR sudden slowdown depending on array size

Question

I wrote a simple program that ORs all the values contained in a huge go slice. When I use a 10 times bigger slice, I would expect a 10x performance drop. However when executing the provided test, there is a huge performance gap. The program output is the following :

oadam@oadam-Latitude-E6510:~/$ go test -bench .
testing: warning: no tests to run
PASS
BenchmarkLittle 2000000000           0.11 ns/op
BenchmarkBig           1    2417869962 ns/op
ok      _/home/oadam/   5.048s

And the code

package main

import (
    "math/rand"
    "testing"
)

const (
    little = 5000000
    big    = 50000000
)

var a = make([]uint32, big)

func benchOR(b *testing.B, l int) {
    for i := 0; i < l; i++ {
        a[i] = rand.Uint32()
    }

    var result uint32
    for i := 0; i < l; i++ {
        result |= a[i]
    }
}

func BenchmarkLittle(b *testing.B) {
    benchOR(b, little)
}

func BenchmarkBig(b *testing.B) {
    benchOR(b, big)
}

EDIT: must be a bug in go test -bench. Using a manual timing I don't reproduce

package main

import (
    "log"
    "math/rand"
    "time"
)

const (
    little = 5000000
    big    = 50000000
)

var a = make([]uint32, big)

func initA(l int) {
    for i := 0; i < l; i++ {
        a[i] = rand.Uint32()
    }
}

func test(l int) uint32 {
    var result uint32
    for i := 0; i < l; i++ {
        result |= a[i]
    }
    return result
}

func main() {
    initA(little)
    var before = time.Now()
    test(little)
    log.Println(time.Since(before))

    initA(big)
    var before2 = time.Now()
    test(big)
    log.Println(time.Since(before2))

}

Answer 1

The problem is that you are not using b.N, which tells you how many times to run the benchmark. Also, if you only want to benchmark the ORing, you should probably just initialize the array once, or at least call b.ResetTimer() so the initialization is not counted.

Here's what I ended up with, which gives the expected results:

package main

import (
    "math/rand"
    "testing"
)

const (
    little = 5000000
    big    = 50000000
)

var a = make([]uint32, big)

func init() {
    for i := 0; i < big; i++ {
        a[i] = rand.Uint32()
    }
}

func benchOR(b *testing.B, l int) {
    var result uint32
    for _, u := range a[:l] {
        result |= u
    }
}

func BenchmarkLittle(b *testing.B) {
    for i := 0; i < b.N; i++ {
        benchOR(b, little)
    }
}

func BenchmarkBig(b *testing.B) {
    for i := 0; i < b.N; i++ {
        benchOR(b, big)
    }
}

My results:

BenchmarkLittle      500       3222064 ns/op
BenchmarkBig          50      32268023 ns/op

Answer 2

I don't think it's a bug. I modified your code a bit, and that's what I got:

% go test -bench=.
testing: warning: no tests to run
PASS
BenchmarkLittle 2000000000           0.00 ns/op
BenchmarkBig  2000000000           0.02 ns/op
ok    _/Users/kavu/TMP/becnh_or 12.659s

Code:

    package main

    import (
        "math/rand"
        "testing"
    )

    const (
        little = 5000000
        big    = 50000000
    )

    func benchOR(a []uint32, l int) (result uint32) {
        for i := 0; i < l; i++ {
            result |= a[i]
        }
        return result
    }

    func BenchmarkLittle(b *testing.B) {
        var a = make([]uint32, big)

        for i := 0; i < little; i++ {
            a[i] = rand.Uint32()
        }

        b.ResetTimer()
        benchOR(a, little)
    }

    func BenchmarkBig(b *testing.B) {
        var a = make([]uint32, big)

        for i := 0; i < big; i++ {
            a[i] = rand.Uint32()
        }

        b.ResetTimer()
        benchOR(a, big)
    }

You can comment out b.ResetTimer() and benchOR(a, big) things and see what happens. Also you can experiment with big constant. Somewhere 10000000 it's fast enough, even without reseting the timer. So, generating a big slice with rand.Uint32 slows everything.