net/url: optimize unescape and escape

[dsnet]

According to a profiling data from a large number of servers at Google, URL related functions are among the top 150 functions by CPU time. The simplest optimizations I see are around using LUTs in shouldEscape, isHex, and unHex.

[LMMilewski]

Based on the profiling data that you mention, it looks like the unescape time is split evenly between runtime.makeslice and runtime.slicebytetostring.
The net/url.shouldEscape function is responsible only for ~7% of the CPU time. LUTs might not help as much as we would like.

[bradfitz]

Regarding the allocations and slicebytetostring, see compiler feature request #6714.

/cc @randall77 @cherrymui @josharian @dr2chase

[bradfitz]

See also: #18990

[ccbrown]

I'm not sure it's the kind of optimization you want, but I find that if I do some "hand optimization", just eliminating branches, I get pretty significant speed increases:

const ESCAPE_ME = "net/url: optimize unescape and escape"

var s string

func BenchmarkPathEscape(b *testing.B) {
	for i := 0; i < b.N; i++ {
		s = url.PathEscape(ESCAPE_ME)
	}
}

func shouldPathEscape(c byte) bool {
	if 'A' <= c && c <= 'Z' || 'a' <= c && c <= 'z' || '0' <= c && c <= '9' {
		return false
	}
	switch c {
	case '-', '_', '.', '~', ':', '@', '&', '=', '+', '$':
		return false
	}
	return true
}

func MyPathEscape(s string) string {
	hexCount := 0
	for i := 0; i < len(s); i++ {
		if shouldPathEscape(s[i]) {
			hexCount++
		}
	}
	if hexCount == 0 {
		return s
	}
	t := make([]byte, len(s)+2*hexCount)
	j := 0
	for i := 0; i < len(s); i++ {
		c := s[i]
		if shouldPathEscape(c) {
			t[j] = '%'
			t[j+1] = "0123456789ABCDEF"[c>>4]
			t[j+2] = "0123456789ABCDEF"[c&15]
			j += 3
		} else {
			t[j] = c
			j++
		}
	}
	return string(t)
}

func BenchmarkMyPathEscape(b *testing.B) {
	for i := 0; i < b.N; i++ {
		s = MyPathEscape(ESCAPE_ME)
	}
}

goos: darwin
goarch: amd64
BenchmarkPathEscape-8     	 3000000	       438 ns/op
BenchmarkMyPathEscape-8   	10000000	       147 ns/op

It seems to me like calls to functions like escape should probably be inlined when a parameter on which many branches depend is given a const argument:

func PathEscape(s string) string {
    return escape(s, encodePathSegment) // not inlined, but probably should be
}

[martisch]

I also experimented with some optimizations (mostly unescpae) but have not cleaned them up in a CL yet. So i am interested what we can improve too. Maybe i still get around to finish them for 1.10.

I was thinking of creating a table [256]uint8 where byte contains some flags. e.g. shouldPathEscape (if we need more flags this can become uint32)
so we can use the same lookup table in multiple functions to quickly look up properties of ASCII characters while at the same time not wasting ram for a lookup table each time. This could be even stored in a separate package so multiple std lib packages (e.g unicode.IsSpace or strings.Fields) can use the same table.

For unhex i prefer using 9*(c>>6)` + (c&15) vs a LUT. I will have to benchmark this again but will send as a small separate improvement for the std lib occurrences if it still checks out to be faster than the current branch based version.

@ccbrown
Some comments while briefly looking at the code from the above comment:

• t[j+2] could maybe avoid some bounds check here by checking _ = t[j+2] earlier in the block.
• we could remember the first position where a to be escaped symbol is and skip ahead to that in the second loop after making a copy of the start up to that symbol. But that would make performance worse when to position is very near the start of the string.

if shouldPathEscape(s[i]) {
 hexCount++
}

if this is not already recognized by the compiler to become a setCC instruction with an add on AMD6 4 instead of a branch we should have a look at optimizing that. (maybe there is even an add that just takes the flag without setCC)

Does your new version pass all the tests?

[ccbrown]

Tried a few more things.

Using a boolean LUT does make things faster:

func MyBoolLUTEscape(s string, shouldEscapeLUT [256]bool) string {
	hexCount := 0
	for i := 0; i < len(s); i++ {
		if shouldEscapeLUT[s[i]] {
			hexCount++
		}
	}
	if hexCount == 0 {
		return s
	}
	t := make([]byte, len(s)+2*hexCount)
	j := 0
	for i := 0; i < len(s); i++ {
		c := s[i]
		if shouldEscapeLUT[c] {
			t[j] = '%'
			t[j+1] = "0123456789ABCDEF"[c>>4]
			t[j+2] = "0123456789ABCDEF"[c&15]
			j += 3
		} else {
			t[j] = c
			j++
		}
	}
	return string(t)
}

BenchmarkPathEscape-8              	 3000000	       438 ns/op
BenchmarkMyPathEscape-8            	10000000	       144 ns/op
BenchmarkMyBoolLUTPathEscape-8     	10000000	       128 ns/op

Compacting all of the different encodings into a single [256]byte LUT is slower, but still reasonably fast (and would potentially save 6*256 bytes in memory):

func MyLUTEscape(s string, mode encoding) string {
	hexCount := 0
	mask := byte(1 << byte(mode))
	for i := 0; i < len(s); i++ {
		if shouldEscapeLUT[s[i]]&mask != 0 {
			hexCount++
		}
	}
	if hexCount == 0 {
		return s
	}
	t := make([]byte, len(s)+2*hexCount)
	j := 0
	for i := 0; i < len(s); i++ {
		c := s[i]
		if shouldEscapeLUT[s[i]]&mask != 0 {
			t[j] = '%'
			t[j+1] = "0123456789ABCDEF"[c>>4]
			t[j+2] = "0123456789ABCDEF"[c&15]
			j += 3
		} else {
			t[j] = c
			j++
		}
	}
	return string(t)
}

BenchmarkMyLUTEscape-8             	10000000	       151 ns/op

Note while these functions can be re-used by all of the encodings, I'm still excluding the c == ' ' && mode == encodeQueryComponent case for now. If needed, query component encoding can get its own function implementation.

@martisch

t[j+2] could maybe avoid some bounds check here by checking _ = t[j+2] earlier in the block.

we could remember the first position where a to be escaped symbol is and skip ahead to that in the second loop after making a copy of the start up to that symbol. But that would make performance worse when to position is very near the start of the string.

Tried both. Neither really made a measurable difference for me.

if this is not already recognized by the compiler to become a setCC instruction with an add on AMD64 instead of a branch we should have a look at optimizing that.

That function actually got inlined for me. So it didn't use any conditional instructions like that there.

But in the LUT version, maybe that sort of thing could work here:

perf_test.go:207	0x10f004d		4084f8			TESTL DI, AL
perf_test.go:207	0x10f0050		74e3			JE 0x10f0035
perf_test.go:208	0x10f0052		48ffc6			INCQ SI
perf_test.go:207	0x10f0055		ebde			JMP 0x10f0035

I'm not really gonna try to optimize this at such a low level yet though.