unicode/utf8: make DecodeRune and DecodeLastRune inlineable

[dsnet]

Code like the following is unfortunately very common:

r, n := rune(b[0]), 1
if r >= utf8.RuneSelf {
    r, n = utf8.DecodeRune(b)
}

and we have several examples in the standard library itself:

• fmt/format.go:347
• fmt/print.go:1101
• regexp/regexp.go:418
• regexp/regexp.go:465
• bytes/bytes.go:482
• bytes/bytes.go:560
• bytes/bytes.go:781
• bytes/bytes.go:836
• bufio/bufio.go:295
• strings/strings.go:741
• strconv/quote.go:43
• strconv/quote.go:266

All of these cases ultimate come down to the caller manually performing inlined logic for the ASCII case. We should make it such that DecodeRune and DecodeLastRune are inlineable for the ASCII case. Unfortunately my attempts to do so exceed the inline budget by ever so much:

// cannot inline DecodeRune: function too complex: cost 87 exceeds budget 80
func DecodeRune(p []byte) (r rune, size int) {
	if len(p) > 0 && p[0] < RuneSelf {
		return rune(p[0]), 1
	}
	return decodeRune(p)
}

// cannot inline DecodeLastRune: function too complex: cost 93 exceeds budget 80
func DecodeLastRune(p []byte) (r rune, size int) {
	if len(p) > 0 && p[len(p)-1] < UTFMax {
		return rune(p[len(p)-1]), 1
	}
	return decodeLastRune(p)
}

We should find a way to make these inlinable whether by special casing them, clever tricks to make the cost lower, by increasing the inline budget, etc.

\cc @CAFxX @josharian @mdempsky @martisch

[CAFxX]

FWIW, I gave it a shot before: https://go-review.googlesource.com/c/go/+/332770

Unfortunately yes, I really can not see a way to make it work without messing with the inliner (either by changing the heuristics, or by adding special cases) or otherwise adding some kind of annotation.

[renthraysk]

Seem to remember commenting on a similar issue, that couldn't do the same with binary.Uvarint().

#31666

But now with for loop inlining since added to go, Uvarint() can be made to (replace range use) inline as whole without needing a separate func.

[zigo101]

The inline cost of the following implementation is 83:

func DecodeRune(p []byte) (r rune, size int) {
	if len(p) > 0 && p[0] < RuneSelf {
		r, size = rune(p[0]), 1
	} else {
		r, size = decodeRune(p)
	}
	return
}

[zigo101]

And this one is 81:

func DecodeRune(p []byte) (r rune, size int) {
	if len(p) > 0 && p[0] < RuneSelf {
		return rune(p[0]), 1
	}
	r, size = decodeRune(p)
	return
}

[zigo101]

Maybe the inline cost calculation should consider whether or not bound checks are eliminated.
Here, the bound checks for p[0] are eliminated, so its cost should be some lower.

BTW, why the inline costs of function calls are so large?

[mengzhuo]

The ExtraCall budget is 57 plus two arguments we had at least 64 budget, maybe we can force inline by asm code.
However I've tried modified the ExtraCall budget and it appears only improve ASCII related DecodeRune and regression on slow path.

https://perf.golang.org/search?q=upload:20210922.6

name                               old time/op  new time/op  delta
RuneCountTenASCIIChars             9.27ns ± 1%  9.27ns ± 1%     ~     (p=0.151 n=9+9)
RuneCountTenJapaneseChars          37.8ns ± 2%  38.2ns ± 1%   +1.09%  (p=0.022 n=10+8)
RuneCountInStringTenASCIIChars     9.26ns ± 0%  9.26ns ± 0%     ~     (p=0.333 n=10+10)
RuneCountInStringTenJapaneseChars  39.3ns ± 1%  38.1ns ± 2%   -3.07%  (p=0.000 n=10+10)
EncodeASCIIRune                    1.71ns ± 0%  1.71ns ± 0%     ~     (all equal)
EncodeJapaneseRune                 2.86ns ± 0%  2.83ns ± 0%   -1.12%  (p=0.000 n=10+9)
AppendASCIIRune                    0.26ns ± 0%  0.26ns ± 0%   -2.44%  (p=0.000 n=7+10)
AppendJapaneseRune                 3.09ns ± 0%  3.08ns ± 0%   -0.02%  (p=0.029 n=9+9)
DecodeASCIIRune                    2.06ns ± 0%  0.26ns ± 0%  -87.53%  (p=0.000 n=8+8)
DecodeJapaneseRune                 3.60ns ± 0%  3.73ns ± 0%   +3.52%  (p=0.000 n=10+8)
FullRune/ASCII                     1.03ns ± 0%  1.18ns ± 3%  +14.28%  (p=0.000 n=10+10)
FullRune/Incomplete                2.18ns ± 2%  2.14ns ± 1%   -2.00%  (p=0.000 n=10+10)
FullRune/Japanese                  1.03ns ± 0%  1.18ns ± 3%  +15.03%  (p=0.000 n=9+10)

[dsnet]

However I've tried modified the ExtraCall budget and it appears only improve ASCII related DecodeRune and regression on slow path.

Isn't that expected? With inlining, we generally want to get the common case to be inlined (i.e., ASCII), and perform the function call for the less common case (i.e., multibyte Unicode).

[gopherbot]

Change https://golang.org/cl/354769 mentions this issue: cmd/compile: zero cost of byte to rune conversion

[gopherbot]

Change https://golang.org/cl/354770 mentions this issue: unicode/utf8: make DecodeRune inlined

[gopherbot]

Change https://golang.org/cl/356769 mentions this issue: unicode/utf8: default ascii fast path for DecodeRune