Repository: cilium/ebpf
Pull request #1210 (2023-11-07 11:26:51)

btf: Optimize string table for globally increasing offsets
After doing some observations while parsing VMLinux, it seems that the lookup access pattern for strings is mostly globally increasing with with some patches of seemingly unpridicable offsets.

This is a sample of the access pattern, numbers are the index into the string table, not the offset:
```
1112
1113
1114
348
78
1115
1116
372
1117
1118
1119
```

This commit adds logic to track this globally increasing offset and checks if the if the offset at the next expected index matches the offset we are looking for. If it does, we can skip the binary search. In VMLinux this fast path is taken about 50% of the time, resulting in about a 7% speedup.

```
goos: linux
goarch: amd64
pkg: github.com/cilium/ebpf/btf
cpu: 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
                │ before.txt  │          after.txt          │
                │   sec/op    │   sec/op     vs base        │
ParseVmlinux-16   48.52m ± 1%   44.79m ± 1%  -7.69% (n=100)

                │  before.txt  │            after.txt            │
                │     B/op     │     B/op      vs base           │
ParseVmlinux-16   31.45Mi ± 0%   31.45Mi ± 0%  ~ (p=0.127 n=100)

                │ before.txt  │           after.txt            │
                │  allocs/op  │  allocs/op   vs base           │
ParseVmlinux-16   534.1k ± 0%   534.1k ± 0%  ~ (p=0.130 n=100)
```

lmb: I get this on my machine:

```
$ benchstat base.txt opt.txt 
goos: linux
goarch: amd64
pkg: github.com/cilium/ebpf/btf
cpu: 12th Gen Intel(R) Core(TM) i7-1260P
                │  base.txt   │              opt.txt              │
                │   sec/op    │   sec/op     vs base              │
ParseVmlinux-16   42.76m ± 3%   40.35m ± 2%  -5.66% (p=0.002 n=6)

                │   base.txt   │            opt.txt            │
                │     B/op     │     B/op      vs base         │
ParseVmlinux-16   31.45Mi ± 0%   31.45Mi ± 0%  ~ (p=0.132 n=6)

                │  base.txt   │           opt.txt            │
                │  allocs/op  │  allocs/op   vs base         │
ParseVmlinux-16   534.1k ± 0%   534.1k ± 0%  ~ (p=0.165 n=6)
```

The laptop is plugged in and I ran `sudo cpupower frequency-set -g performance`.

Patch:
diff --git a/btf/strings.go b/btf/strings.go
index f8ae08c..114d250 100644
--- a/btf/strings.go
+++ b/btf/strings.go
@@ -15,6 +15,7 @@ import (
 type stringTable struct {
 	base    *stringTable
 	offsets []uint32
+	prevIdx int
 	strings []string
 }
 
@@ -61,7 +62,7 @@ func readStringTable(r sizedReader, base *stringTable) (*stringTable, error) {
 		return nil, errors.New("first item in string table is non-empty")
 	}
 
-	return &stringTable{base, offsets, strings}, nil
+	return &stringTable{base, offsets, 0, strings}, nil
 }
 
 func splitNull(data []byte, atEOF bool) (advance int, token []byte, err error) {
@@ -84,15 +85,28 @@ func (st *stringTable) Lookup(offset uint32) (string, error) {
 }
 
 func (st *stringTable) lookup(offset uint32) (string, error) {
+	// Fast path: zero offset is the empty string, looked up frequently.
 	if offset == 0 && st.base == nil {
 		return "", nil
 	}
 
+	// Accesses tend to be globally increasing, so check if the next string is
+	// the one we want. This skips the binary search in about 50% of cases.
+	if st.prevIdx+1 < len(st.offsets) && st.offsets[st.prevIdx+1] == offset {
+		st.prevIdx++
+		return st.strings[st.prevIdx], nil
+	}
+
 	i, found := slices.BinarySearch(st.offsets, offset)
 	if !found {
 		return "", fmt.Errorf("offset %d isn't start of a string", offset)
 	}
 
+	// Set the new increment index, but only if its greater than the current.
+	if i > st.prevIdx+1 {
+		st.prevIdx = i
+	}
+
 	return st.strings[i], nil
 }
 


Test patch:
diff --git a/btf/strings_test.go b/btf/strings_test.go
index d34726d..e97c626 100644
--- a/btf/strings_test.go
+++ b/btf/strings_test.go
@@ -112,5 +112,5 @@ func newStringTable(strings ...string) *stringTable {
 		offset += uint32(len(str)) + 1 // account for NUL
 	}
 
-	return &stringTable{nil, offsets, strings}
+	return &stringTable{nil, offsets, 0, strings}
 }