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

strings/bytes: LastIndexByte is significantly slower than IndexByte #36891

Open
kirillx opened this issue Jan 30, 2020 · 5 comments
Open

strings/bytes: LastIndexByte is significantly slower than IndexByte #36891

kirillx opened this issue Jan 30, 2020 · 5 comments
Assignees
Milestone

Comments

@kirillx
Copy link
Contributor

@kirillx kirillx commented Jan 30, 2020

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

$ go version
go version go1.13.1 darwin/amd64

Does this issue reproduce with the latest release?

yes.

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

Both Linux/MacOS

What did you do?

I was using multipart.NewReader() to process multi-part responses from Cloud REST API.
It turned out that ~1/3 of profile is spent in mime/multipart/multipart.go :: scanUntilBoundary() -> bytes.LastIndexByte().

After looking into it, it is no wonder as bytes.LastIndexByte() is not using any optimisations and compiled into simple loop iterating over bytes, no REP SCASB instruction is used on Intel (nor SSE).

What did you expect to see?

bytes.LastIndexByte() to use SSE or at least REP SCASB optimised code.

What did you see instead?

simple byte to byte loop in asm code.

@ALTree
Copy link
Member

@ALTree ALTree commented Jan 30, 2020

Thanks for reporting this.

IndexByte has been optimized significantly more than LastIndexByte, and it appears to be ~7x faster in comparable benchmarks (i.e. IndexByte(aaaa...ax) vs IndexLastByte(xa...aaaa), when looking for x).

I guess we could port the same implementation to LastIndex .

@ALTree ALTree added the Performance label Jan 30, 2020
@ALTree ALTree added this to the Unplanned milestone Jan 30, 2020
@ALTree ALTree changed the title bytes.LastIndexByte is not optimised and signification in profiles bytes: LastIndexByte is significantly slower than IndexByte Jan 30, 2020
@ALTree ALTree added the NeedsDecision label Feb 1, 2020
@martisch martisch changed the title bytes: LastIndexByte is significantly slower than IndexByte strings/bytes: LastIndexByte is significantly slower than IndexByte Jun 18, 2020
@martisch
Copy link
Contributor

@martisch martisch commented Jun 18, 2020

I was just about to create a new Issue for this but notice this one exists already. I came across this as profiling data shows LastIndexByte is used alot nowdays (e.g. in proto code) to account for a good chunk of overall CPU time profiled.

I agree we should optimize strings/bytes.LastIndexByte similar to IndexByte:
https://github.com/golang/go/blob/master/src/internal/bytealg/index_amd64.s

@networkimprov
Copy link

@networkimprov networkimprov commented Jun 18, 2020

Maybe status = NeedsFix?

@martisch martisch added the NeedsFix label Jun 23, 2020
@martisch martisch self-assigned this Jun 26, 2020
@martisch
Copy link
Contributor

@martisch martisch commented Jun 26, 2020

Assigned myself earlier because I already have prototype that passes ./all.bash but needs benchmarking on a quiet machine and double checking of page boundary handling before sending for review.

@gopherbot
Copy link

@gopherbot gopherbot commented Oct 30, 2020

Change https://golang.org/cl/266538 mentions this issue: strings, bytes: use SIMD for LastIndexByte on amd64

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants
You can’t perform that action at this time.