- Restructure calculateChecksumNoASM() to consistently handle misaligned
inputs: special-case inputs less than 8 bytes in size, otherwise align the
buffer address to 8 bytes before checksumming in bulk. This avoids
significant performance degradation on misaligned inputs due to fallback to
unrolledCalculateChecksum().
- Sum up to 64 bytes per loop iteration in calculateChecksumNoASM(), as in
unrolledCalculateChecksum(). This significantly improves performance for
large inputs.
- Don't plumb carry between blocks in calculateChecksumNoASM(). On x86, this is
significantly faster because many instructions clobber the carry flag, so
saving it requires extra overhead; on arm64, this has minimal effect on the
generated code (the compiler inserts an extra useless copy from the zero
register to a temporary).
- Replace the folding of uint64 accumulator to uint16 checksum with a
branchless equivalent, which is ~2ns/checksum faster on average due to
avoiding an unpredictable loop.
- Fix calculateChecksumNoASM() on big-endian architectures.
- Delete unrolledCalculateChecksum(), which is now unused.
Before these changes, calculateChecksumAMD64() is approximately twice as fast
as calculateChecksumNoASM(). After these changes, calculateChecksumNoASM() is
faster than calculateChecksumAMD64():
```
goos: linux
goarch: amd64
pkg: pkg/tcpip/checksum/checksum
cpu: Intel(R) Xeon(R) CPU @ 2.80GHz
│ checksum_baseline │ checksum_experiment │
│ sec/op │ sec/op vs base │
Checksum/checksum_64-48 10.50n ± 0% 10.10n ± 0% -3.86% (p=0.000 n=10)
Checksum/checksum_128-48 13.72n ± 0% 12.16n ± 0% -11.37% (p=0.000 n=10)
Checksum/checksum_256-48 22.80n ± 0% 16.31n ± 0% -28.48% (p=0.000 n=10)
Checksum/checksum_512-48 39.92n ± 0% 24.96n ± 0% -37.47% (p=0.000 n=10)
Checksum/checksum_1024-48 81.34n ± 0% 44.26n ± 2% -45.58% (p=0.000 n=10)
Checksum/checksum_1500-48 119.70n ± 1% 65.05n ± 2% -45.65% (p=0.000 n=10)
Checksum/checksum_2048-48 157.30n ± 0% 86.65n ± 0% -44.91% (p=0.000 n=10)
Checksum/checksum_4096-48 309.5n ± 0% 172.4n ± 3% -44.30% (p=0.000 n=10)
Checksum/checksum_8192-48 615.0n ± 0% 348.0n ± 0% -43.42% (p=0.000 n=10)
Checksum/checksum_16384-48 1222.5n ± 0% 690.8n ± 0% -43.49% (p=0.000 n=10)
Checksum/checksum_32767-48 2.447µ ± 0% 1.381µ ± 0% -43.55% (p=0.000 n=10)
Checksum/checksum_32768-48 2.442µ ± 0% 1.381µ ± 0% -43.48% (p=0.000 n=10)
Checksum/checksum_65535-48 4.883µ ± 0% 2.933µ ± 0% -39.94% (p=0.000 n=10)
Checksum/checksum_65536-48 4.877µ ± 0% 2.935µ ± 0% -39.82% (p=0.000 n=10)
geomean 260.6n 161.9n -37.88%
```
Thus, use calculateChecksumNoASM() on all architectures and rename it to
calculateChecksum().
---
Note: As of this writing, calculateChecksumNoASM() is still ~7% slower than an
equivalently-optimized x86 assembly implementation, for three main reasons:
1. The Go compiler emits separate MOV memory-to-register and ADD/ADC
instructions rather than using memory operands for the latter.
2. For statements of the form `buf = buf[1:]`, updating the slice data pointer
takes ~5 instructions instead of 1, because the compiler avoids incrementing
the pointer if the resulting slice length is 0 (such that the pointer would
point outside of the underlying array). This overhead can be avoided by
using uintptr and runtime.KeepAlive(), but doing so worsens problem (1):
replacing `*(*uint64(unsafe.Pointer(&buf[8])))` with
`*(*uint64(unsafe.Pointer(addr+8)))` causes the compiler to split each MOV
into LEA + MOV.
3. The faster form of reduce() described in that function is implementable in
assembly.
Thus, we can add the optimized x86 assembly implementation back if desired.
---
`GOOS=linux GOARCH=mips64 go test -exec qemu-mips64 ./...` fails before this
CL, since the "bitslib" implementation, i.e. calculateChecksumNoASM(), is
broken on big-endian architectures. After this CL:
```
ok gvisor.dev/gvisor/pkg/tcpip/checksum 125.970s
```
PiperOrigin-RevId: 574264329
- When buffers aren't 64 bit aligned, use the slower unrolled checksum
that's safe across different architectures.
- Remove the copied checksum implementation in checksum_test so we don't
have to update both.
- Play with build tags such that checksum_test tests all checksum
implementations, not just the preferred one on that architecture.
Fixes#9499.
This is a roll-forward of cl/540620826. The differences are:
- Added Tony's test that showed breakage on ARM64
- Fixed the 64-bit non-AMD64 checksum implementation
- Handles odd buffers correctly
- Doesn't call the unrolled checksum impl anymore
- Re-ordered calculateChecksum to reduce indentation
Otherwise this is the same CL. The only changes are in checksum_test.go and
checksum_noasm_unsafe.go.
PiperOrigin-RevId: 547890206
tcp_benchmark shows we spend significant time checksumming -- after Syscall,
checksumming is the most time-consuming function.
AMD64 gets a 77% faster checksum via assmebly implementation.
Other 64bit machines get a new checksum function, which runs 38% faster than
current checksumming on my machine and 34% faster on an ARM test machine.
tcp_benchmark is pretty noisy here, but generally shows a 2-5% decrease in CPU
usage or a small boost to throughput:
```
│ /tmp/old.log │ /tmp/new.log │
│ Mb/s │ Mb/s vs base │
TCP/role=server/host-gso=false/host-gro=false 142.0 ± 28% 154.5 ± 24% ~ (p=0.459 n=40)
TCP/role=client/host-gso=false/host-gro=false 1.794k ± 1% 1.840k ± 1% +2.59% (p=0.000 n=40)
geomean 504.7 533.2 +5.65%
│ /tmp/old.log │ /tmp/new.log │
│ cpu-time │ cpu-time vs base │
TCP/role=server/host-gso=false/host-gro=false 244.0m ± 25% 256.3m ± 21% ~ (p=0.529 n=40)
TCP/role=client/host-gso=false/host-gro=false 2.251 ± 1% 2.242 ± 1% ~ (p=0.079 n=40)
geomean 741.1m 758.1m +2.30%
```
So it seems checksumming is not the bottleneck in tcp_benchmark. This may be
different in other environments, especially those where we cannot rely on host
receive checksum offload.
PiperOrigin-RevId: 540620826
Checksum capabilities are logically separate from tcpip header definitions
and operations. It makes sense to extract this logic into its own package.
This is also necessary to avoid circular dependencies with bufferv2.
PiperOrigin-RevId: 473096480
Jing Chen
Jamie LiuandgVisor bot
Kevin Krakauer
Adin ScannellandgVisor bot
Lucas ManningandgVisor bot