Repository navigation
bytes, strings: optimize Trim for ASCII cutsets #46446
Description
I analyzed usages of strings.Trim (and related functions in both strings and bytes) in all source code known by the module proxy:
- 76.6% have a cutset of len=1, and
- 13.4% have a cutset of len=2.
Given that a vast majority of usages only have a cutset of len=1, I argue we should more heavily optimize for that situation. Currently, there is some optimization for cutsets of len=1, but it’s within the internal makeCutsetFunc function. This is sub-optimal as it incurs an allocation in the internal makeCutsetFunc for the closure over that single byte. I believe we should place special handling of cutsets with len=1 directly in Trim, TrimRight, and TrimLeft.
Example benchmark for strings.TrimRight("hello==", "="):
BenchmarkStd 18299240 69.16 ns/op 24 B/op 1 allocs/op
BenchmarkOpt 226575349 5.330 ns/op 0 B/op 0 allocs/op
The suggested optimization results in a >10x speedup for this common case.
P.S. There is currently an optimization for cutsets that are all ASCII. This optimization is still justified to keep as 99.3% of all cutsets are pure ASCII.
Activity
ianlancetaylor commentedon May 29, 2021
Out of curiosity, is there any particular byte that predominantly appears in the set of single-byte cutsets?
dsnet commentedon May 30, 2021
The top-ten single-byte cutsets are:
'/'at 30.2%'\n'at 15.7%' 'at 10.1%'.'at 7.0%'\x00'at 5.7%'0'at 5.0%','at 3.5%'='at 3.4%'-'at 2.6%'|'at 2.5%dsnet commentedon May 30, 2021
https://go-review.googlesource.com/c/go/+/323315 is an example of speedup in application code if
bytes.Trimwere to be optimized.gopherbot commentedon May 30, 2021
Change https://golang.org/cl/323318 mentions this issue:
bytes, strings: optimize Trim for single byte cutsetsnightlyone commentedon May 30, 2021
Maybe is is useful to do the same optimization as LastIndexAny and IndexAny where the cutover to use a cutset is 8 bytes.
dsnet commentedon May 30, 2021
@nightlyone, can you elaborate more what you have in mind?
Currently, the logic for
LastIndexAnyis already fairly complex. Any optimizations ofLastIndexAnyshould be driven by how Go code at scale uses it, which is an analysis I haven't performed yet.I should note that the we could conceivably delete the optimization in
LastIndexAnyfor a cutset with len=1, which was added in golang.org/cl/156998. I don't find that specific optimization particularly compelling since:LastIndexBytealready exists, andjosharian commentedon Jun 1, 2021
I recently cobbled together https://go-review.googlesource.com/c/go/+/271669 to work around that allocation. As I noted there, "another alternative is to duplicate a bunch of the trimming code to work directly on asciiSets", which might be a viable option to consider.
@bradfitz also had some thoughts about this. I've forgotten what they were, but perhaps he remembers. :)
dsnet commentedon Jun 1, 2021
Interesting idea caching the cutset functions. I think inlining the single-byte handling is still preferred since a quick check against a single byte is dramatically faster than always calling a
func(rune) bool.That said, if it provides any insights, the top most common cutsets with len>1 are:
"\r\n"at 4.6%" \t"at 2.3%"\n\r"at 0.8%"//"at 0.7%", "at 0.5%" \t\r\n"at 0.5%"\t\n\f\r "at 0.4%" \t\n\f\r"at 0.4%"./"at 0.3%"01234567"at 0.3%Observations of the above:
"//"is an identical cutset to"/").gopherbot commentedon Jun 5, 2021
Change https://golang.org/cl/325251 mentions this issue:
strings,bytes: optimize the Trim/TrimLeft/TrimRight fast pathsstrings,bytes: optimize the Trim/TrimLeft/TrimRight fast paths
strings,bytes: optimize the Trim/TrimLeft/TrimRight fast paths
gopherbot commentedon Jul 4, 2021
Change https://golang.org/cl/332771 mentions this issue:
strings,bytes: optimize the Trim/TrimLeft/TrimRight fast pathsCAFxX commentedon Jul 5, 2021
https://golang.org/cl/332771 removes the allocation in all cases, and in general speeds up Trim/TrimLeft/TrimRight 2x~10x depending on the cutset, with the biggest speedups for the case of a cutset composed of a single ASCII character.
2 remaining items
[-]bytes, strings: optimize Trim for 1-byte cutsets[/-][+]bytes, strings: optimize Trim for multi-byte cutsets[/+]dsnet commentedon Aug 25, 2021
Re-opening since there's some interest in optimizing for multi-byte ASCII cutsets. The evidence for supporting single-byte cutsets is very strong given that they are >75% of all usages. For the remaining 25% where the cutset is not a single byte, 97% of them are all ASCII.
cespare commentedon Aug 25, 2021
@dsnet what do you think about opening a new issues and reverting the title of this one? I think it's confusing that this was originally about 1-byte cutsets, and then that was implemented, and now the issue is reopened and is about something new.
At minimum, it should be retitled to be about both optimizations.
[-]bytes, strings: optimize Trim for multi-byte cutsets[/-][+]bytes, strings: optimize Trim for ASCII cutsets[/+]dsnet commentedon Aug 25, 2021
I renamed the issue to be about ASCII cutsets, which I think accurately captured both optimizations being discussed.
CAFxX commentedon Sep 4, 2021
I just rebased and re-ran the benchmarks in https://golang.org/cl/332771. Would be ideal if someone could take a look at it. It completely eliminates all memory allocations and significantly speeds up both the ASCII fast path and the slow path.
bytes, strings: optimize Trim for single byte cutsets