strings: optimize ToLower and ToUpper

[dsnet]

According to a profiling data from a large number of servers at Google, strings.ToLower and strings.ToUpper is within the top 300 functions by CPU time. I believe there can be a significant speed-up by specifically handling ASCII characters first before falling back to the unicode.ToLower and unicode.ToUpper functions.

[martisch]

Working on this. Documentation and better benchmarks (e.g. for runes and mixes) needed.

As a baseline i first wanted to see what we can get out of the existing generic Map function before we start considering the tradeoff of specialized ToLower and ToUpper functions.

benchmark                   old ns/op     new ns/op     delta
BenchmarkByteByteMap-4      2060          985           -52.18%
BenchmarkMapNoChanges-4     180           119           -33.89%

To be benchmarked:

If we make a specialized Map Function (mapReplace) that does not have to deal with the possibilities of drops (negative return value in map function) or stateful functions (e.g. Title)
we might get a bit faster and have more compact code.

As @dsnet said specialized ToLower and ToUpper functions could handle the ASCII case inline and only call unicode functions for non-ASCII characters.

[gopherbot]

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

[bradfitz]

Punting to Go 1.10. But @martisch, curious if there are still big wins here.

[agnivade]

@martisch , @bradfitz -

I did pt 3 as mentioned above and certainly got some improvements for the ascii case. Non-ascii case remained the same.

Test case set is the same as the ToUpper.

func BenchmarkToUpper(b *testing.B) {
	for _, tc := range upperTests {
		b.Run(tc.in, func(b *testing.B) {
			for i := 0; i < b.N; i++ {
				actual := ToUpper(tc.in)
				if actual != tc.out {
					b.Errorf("ToUpper(%q) = %q; want %q", tc.in, actual, tc.out)
				}
			}
		})
	}
}

name             old time/op    new time/op    delta
ToUpper/#00        13.5ns ± 5%     8.1ns ±10%  -39.57%  (p=0.008 n=5+5)
ToUpper/abc        96.4ns ±20%    66.2ns ±13%  -31.32%  (p=0.008 n=5+5)
ToUpper/AbC123      109ns ±14%      79ns ± 9%  -27.18%  (p=0.008 n=5+5)
ToUpper/azAZ09_     123ns ±16%      80ns ±14%  -34.59%  (p=0.008 n=5+5)
ToUpper/ɐɐɐɐɐ       426ns ±24%     413ns ±14%     ~     (p=0.841 n=5+5)

name             old alloc/op   new alloc/op   delta
ToUpper/#00         0.00B          0.00B          ~     (all equal)
ToUpper/abc         16.0B ± 0%      6.0B ± 0%  -62.50%  (p=0.008 n=5+5)
ToUpper/AbC123      16.0B ± 0%     16.0B ± 0%     ~     (all equal)
ToUpper/azAZ09_     24.0B ± 0%     16.0B ± 0%  -33.33%  (p=0.008 n=5+5)
ToUpper/ɐɐɐɐɐ       64.0B ± 0%     64.0B ± 0%     ~     (all equal)

Let me know what you guys think on this.

[stemar94]

Let me know what you guys think on this.

Can you send a CL for that change you did?

[agnivade]

I did -

func ToUpper(s string) string {
	if s == "" { // quick return for empty strings
		return s
	}
	if isASCII(s) { // optimize for ascii condition
		b := make([]byte, len(s))
		for i, c := range s {
			if c >= 'a' && c <= 'z' {
				c -= 'a' - 'A'
			}
			b[i] = byte(c)
		}
		return string(b)
	}
	return Map(unicode.ToUpper, s)
}

I will wait for @martisch / @bradfitz 's thoughts before sending a CL just to confirm whether there is no other work planned on this. Or whether this is indeed the correct approach.

[martisch]

Non-ascii case remained the same.

I do not understand how the above code can keep the performance of the non-ascii path the same. Shouldn't the isASCII call always add some non negative overhead?

14% and 24% is a lot of variance for benchmark runs. If not already the benchmarks should to be run on a very quiet system (no other apps e.g. browser open) and ideally even offline to get a low variance.

Should also be tested with much longer strings.

[agnivade]

I do not understand how the above code can keep the performance of the non-ascii path the same. Shouldn't the isASCII call always add some non negative overhead?

The isASCII call returns on seeing the first non-ascii character. So in this case of a completely non-ascii string, the overhead is just one compare.

func isASCII(s string) bool {
	for i := 0; i < len(s); i++ {
		if s[i] >= utf8.RuneSelf {
			return false
		}
	}
	return true
}

The code is taken verbatim from the net/http/http.go file.

If not already the benchmarks should to be run on a very quiet system (no other apps e.g. browser open)

I usually do that, but I might have kept one tab open 😝 Will re-run with longer strings also. And maybe some cases with mix of ascii and non-ascii.

[agnivade]

@martisch - Re-ran the tests with a proper setup and bigger strings.

The results are much more in line with what is expected. Slight perf hit for a non-ascii case, and good benefits for ascii case.

name                                     old time/op    new time/op    delta
ToUpper/#00                                12.9ns ± 1%     7.5ns ± 0%  -41.31%  (p=0.008 n=5+5)
ToUpper/abc                                79.8ns ± 1%    62.6ns ± 2%  -21.52%  (p=0.008 n=5+5)
ToUpper/AbC123                             92.6ns ± 1%    74.0ns ± 0%  -20.10%  (p=0.008 n=5+5)
ToUpper/azAZ09_                             106ns ± 0%      76ns ± 1%  -28.53%  (p=0.016 n=4+5)
ToUpper/longStrinGwitHmixofsmaLLandcAps     255ns ± 2%     146ns ± 1%  -42.66%  (p=0.008 n=5+5)
ToUpper/longɐstringɐwithɐnonasciiⱯchars     447ns ± 1%     453ns ± 1%   +1.39%  (p=0.008 n=5+5)
ToUpper/ɐɐɐɐɐ                               368ns ± 0%     375ns ± 0%   +1.90%  (p=0.008 n=5+5)

name                                     old alloc/op   new alloc/op   delta
ToUpper/#00                                 0.00B          0.00B          ~     (all equal)
ToUpper/abc                                 16.0B ± 0%      6.0B ± 0%  -62.50%  (p=0.008 n=5+5)
ToUpper/AbC123                              16.0B ± 0%     16.0B ± 0%     ~     (all equal)
ToUpper/azAZ09_                             24.0B ± 0%     16.0B ± 0%  -33.33%  (p=0.008 n=5+5)
ToUpper/longStrinGwitHmixofsmaLLandcAps     80.0B ± 0%     64.0B ± 0%  -20.00%  (p=0.008 n=5+5)
ToUpper/longɐstringɐwithɐnonasciiⱯchars     96.0B ± 0%     96.0B ± 0%     ~     (all equal)
ToUpper/ɐɐɐɐɐ                               64.0B ± 0%     64.0B ± 0%     ~     (all equal)

Up to you guys whether you think this is worth doing or not.

[stemar94]

Why didn't you put out that CL already, then we all could see for ourselves. There is no harm in uploading ;-)