Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

runtime: improve performance of == on arrays. #14302

Closed
pborman opened this issue Feb 12, 2016 · 2 comments
Closed

runtime: improve performance of == on arrays. #14302

pborman opened this issue Feb 12, 2016 · 2 comments

Comments

@pborman
Copy link
Contributor

pborman commented Feb 12, 2016

What version of Go are you using (go version)? go1.5.3
What operating system and processor architecture are you using? Linux, amd64
What did you do? benchmarked == vs bytes.Equal for array types
What did you expect to see? == be as fast as or faster than bytes.Equal
What did you see instead? == is slower than bytes.Equal

Given:

type A [16]byte
var a1, a2 A

a1== a2 is slower than bytes.Equal(a1[:], a2[:]) with the regular gc compiler.

On my machine, the two benchmarks:

type A [16]byte
func BenchmarkEqual(b *testing.B) {
        a1 := A{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}
        a2 := A{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}
        b.ResetTimer()
        for i := 0; i < b.N; i++ {
                if a1 != a2 {
                        b.Fatal("not equal")
                }
        }
}

func BenchmarkBytesEqual(b *testing.B) {
        a1 := A{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}
        a2 := A{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}
        b.ResetTimer()
        for i := 0; i < b.N; i++ {
                if !bytes.Equal(a1[:], a2[:]) {
                        b.Fatal("not equal")
                }
        }
}

result in times of:

BenchmarkEqual-12           200000000            6.02 ns/op
BenchmarkBytesEqual-12      300000000            4.90 ns/op

It seems the same optimizations that have been applied to bytes.Equal could be applied to the code generated by the compiler (or the compiler could simply call the equivalent of the bytes.Equal function).

I also ran the test with 8, 128, and 1024 byte arrays (as well as 16 bytes). The source code is
a_test.go.txt.

The results:

BenchmarkEqual8-12          200000000            5.78 ns/op
BenchmarkBytesEqual8-12     300000000            4.89 ns/op
BenchmarkEqual16-12         200000000            6.77 ns/op
BenchmarkBytesEqual16-12    300000000            5.93 ns/op
BenchmarkEqual128-12        200000000            8.48 ns/op
BenchmarkBytesEqual128-12   200000000            7.57 ns/op
BenchmarkEqual1024-12       50000000            30.1 ns/op
BenchmarkBytesEqual1024-12  50000000            30.4 ns/op

As a side note, with gccgo the results are the opposite, == is faster than bytes.Equal. bytes.Equal with gccgo is also slower than bytes.Equal with the regular gc compiler.

@randall77
Copy link
Contributor

I get similar results, although the delta is not as big:

BenchmarkEqual-8        200000000            7.05 ns/op
BenchmarkBytesEqual-8   200000000            6.73 ns/op

Both use the same underlying algorithm and code.

I think the difference is just call overhead. bytes.Equal directly calls into memeqbody. == calls memequal, which calls memeq, which calls memeqbody. (Both memequal and bytes.Equal have the shortcut check if the slices are aliased.)

We could short-circuit one of those trampolines, sure.

@randall77 randall77 self-assigned this Feb 12, 2016
@randall77 randall77 added this to the Go1.7 milestone Feb 12, 2016
@rakyll rakyll changed the title Improve performance of == on arrays. runtime: improve performance of == on arrays. Feb 13, 2016
@gopherbot
Copy link

CL https://golang.org/cl/19843 mentions this issue.

ceseo pushed a commit to powertechpreview/go that referenced this issue May 3, 2016
They do the same thing, except memequal also has the short-circuit
check if the two pointers are equal.

A) We might as well always do the short-circuit check, it is only 2 instructions.
B) The extra function call (memequal->memeq) is expensive.

benchmark                 old ns/op     new ns/op     delta
BenchmarkArrayEqual-8     8.56          5.31          -37.97%

No noticeable affect on the former memeq user (maps).

Fixes golang#14302

Change-Id: I85d1ada59ed11e64dd6c54667f79d32cc5f81948
Reviewed-on: https://go-review.googlesource.com/19843
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@golang golang locked and limited conversation to collaborators Feb 28, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

3 participants