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

Jump to bottom

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

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

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

kirillx opened this issue Jan 30, 2020 · 8 comments
Assignees
@martisch
Labels
help wanted NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone
Unplanned

Comments

@kirillx
Copy link
Contributor

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 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 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 Feedback is required from experts, contributors, and/or the community before a change can be made. 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

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

@martisch martisch added help wanted and removed NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. labels Jun 18, 2020
@andybons andybons added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jun 18, 2020
@networkimprov
Copy link

Maybe status = NeedsFix?

@martisch martisch added the NeedsFix The path to resolution is known, but the work has not been done. label Jun 23, 2020
@gopherbot gopherbot removed the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jun 23, 2020
@martisch martisch self-assigned this Jun 26, 2020
@martisch
Copy link
Contributor

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

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

@quasilyte
Copy link
Contributor

@martisch are you planning on merging that CL at some point?
Do you need any help with testing/review/benchmarking?

@martisch
Copy link
Contributor

martisch commented Dec 3, 2021 •
edited

I can plan to merge it next cycle.

The last thing I was missing is a test that the page boundary at the beginning of the data is honoured. If someone could ammend the existing test (or helpers) to create a test string/byteslice where before (and after) the data the page is protected that would help. Last time I checked it only tested one direction but the the tests have changed recently and I did not check again.

Having beginning and end with protected pages tested to make sure operations using SIMD do not read to much data would also help existing code and can be an independent CL.

@gopherbot
Copy link

Change https://go.dev/cl/522475 mentions this issue: internal/bytealg: add generic LastIndexByte{,String}

gopherbot pushed a commit that referenced this issue Aug 25, 2023
@tklauser @gopherbot
internal/bytealg: add generic LastIndexByte{,String}
890a62b 
To avoid duplicating them in net/netip and os and to allow these
packages automatically benefiting from future performance improvements
when optimized native LastIndexByte{,String} implementations are added.

For #36891

Change-Id: I4905a4742273570c2c36b867df57762c5bfbe1e4
Reviewed-on: https://go-review.googlesource.com/c/go/+/522475
Run-TryBot: Tobias Klauser <tobias.klauser@gmail.com>
Auto-Submit: Tobias Klauser <tobias.klauser@gmail.com>
Reviewed-by: Bryan Mills <bcmills@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@martisch martisch

Labels
help wanted NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
7 participants
@martisch @andybons @networkimprov @ALTree @quasilyte @kirillx @gopherbot