bytes: Equal more expensive than string equality

[seebs]

What version of Go are you using (go version)?

1.12ish, but seems common

Does this issue reproduce with the latest release?

Yup.

What operating system and processor architecture are you using (go env)?

Mostly amd64, but hardly relevant.

What did you do?

Hang out in #performance on gopher slack, notice someone commenting about string comparison being faster than bytes.Equal. Got curious.

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

Perhaps more informative:
https://godbolt.org/z/59xE8E

What did you expect to see?

Not a factor of two performance penalty for using bytes.Equal

What did you see instead?

Reported timing of 7ns vs 17ns for an op that relied heavily on equality tests of small byte slices.

Observations: string comparison can inline the test for equal length, which resolves a large number of tests without actually doing the comparisons. Calling bytes.Equal requires passing two slice headers, and has to do all the function call setup and overhead unconditionally even in the trivial cases.

Not sure this is actually fixable, or possibly even worth fixing, but I was thinking about writing up a thing on how you should do this, and then thinking about what happens if a lot of programmers get in the habit of always converting []byte to string to work on it, and all the pitfalls that could ensue, and I thought "hmm maybe this is worth a look".

[josharian]

Hmm. Any reason not to simply change the implementation of bytes.Equal to be:

func Equal(a, b []byte) bool {
	return string(a) == string(b)
}

If there is a reason not to do that, we could do:

func Equal(a, b []byte) bool {
	return len(a) == len(b) && bytealg.Equal(a, b)
}

And the len check would get inlined. It'd still be a bit slower than the string version, because of the stack setup (three words for slices instead of two for strings), and because bytealg.Equal will compare lengths again. We could fix the latter issue by pushing the length check to all callers of bytealg.Equal.

Aside: if we go the simpler route, I wonder whether it'd be worth teaching the compiler to optimize string([]byte("constant string")) to just "constant string". Then string(b) == "abc" would generate the same code as bytes.Equal(b, []byte("abc")).

cc @bradfitz @ianlancetaylor for package bytes and @randall77 for package bytealg

[bradfitz]

@cherrymui, does gccgo handle return string(a) == string(b) now? You've been doing a lot of work on brining gc optimizations to gccgo lately.

[josharian]

And if we go the “just convert to strings” route then we can convert the other users of bytealg.Equal to bytes.Equal and then delete all the bytealg equality assembly.

[cherrymui]

@cherrymui, does gccgo handle return string(a) == string(b) now? You've been doing a lot of work on brining gc optimizations to gccgo lately.

CL https://go-review.googlesource.com/c/gofrontend/+/170894 elides the copy in string([]byte) conversion. It doesn't do inlined len and pointer comparisons yet, which should be simple to add.

[gopherbot]

Change https://golang.org/cl/173323 mentions this issue: bytes, internal/bytealg: simplify Equal

[josharian]

It doesn't do inlined len and pointer comparisons yet, which should be simple to add.

cmd/compile doesn't have an inlined pointer comparison. Do you have any data about whether it is worth adding?

[seebs]

I was going to say the pointer comparison would be useless, but i'm not actually sure about that, depending on whether the compiler would in some cases be able to prove it true or false.

[cherrymui]

cmd/compile doesn't have an inlined pointer comparison. Do you have any data about whether it is worth adding?

No. I just thought it does (and I'm wrong). I could do some measurement when I work on inlined len comparison.

[seebs]

just for the record, this was actually found by @stuartcarnie in gophers slack, i just thought "hey that should probably get reported".

[josharian]

Thanks for finding it, @stuartcarnie. And thanks for filing it, @seebs. There’s a world of talented gophers out there that it is great to hear from—I encourage everyone I meet to file issues.

@cherrymui I look forward to hearing about what you learn about inlined pointer comparisons.

[stuartcarnie]

No problem and thanks to @seebs for filing the issue 🎉