mirror of
https://github.com/hanzoai/visor.git
synced 2026-09-24 17:04:14 +00:00
Jamie LiuandgVisor bot
40a662086b
- 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
69 lines
1.9 KiB
Go
69 lines
1.9 KiB
Go
// Copyright 2018 The gVisor Authors.
|
|
//
|
|
// Licensed under the Apache License, Version 2.0 (the "License");
|
|
// you may not use this file except in compliance with the License.
|
|
// You may obtain a copy of the License at
|
|
//
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
//
|
|
// Unless required by applicable law or agreed to in writing, software
|
|
// distributed under the License is distributed on an "AS IS" BASIS,
|
|
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
// See the License for the specific language governing permissions and
|
|
// limitations under the License.
|
|
|
|
// Package checksum provides the implementation of the encoding and decoding of
|
|
// network protocol headers.
|
|
package checksum
|
|
|
|
import (
|
|
"encoding/binary"
|
|
)
|
|
|
|
// Size is the size of a checksum.
|
|
//
|
|
// The checksum is held in a uint16 which is 2 bytes.
|
|
const Size = 2
|
|
|
|
// Put puts the checksum in the provided byte slice.
|
|
func Put(b []byte, xsum uint16) {
|
|
binary.BigEndian.PutUint16(b, xsum)
|
|
}
|
|
|
|
// Checksum calculates the checksum (as defined in RFC 1071) of the bytes in the
|
|
// given byte array. This function uses an optimized version of the checksum
|
|
// algorithm.
|
|
//
|
|
// The initial checksum must have been computed on an even number of bytes.
|
|
func Checksum(buf []byte, initial uint16) uint16 {
|
|
s, _ := calculateChecksum(buf, false, initial)
|
|
return s
|
|
}
|
|
|
|
// Checksumer calculates checksum defined in RFC 1071.
|
|
type Checksumer struct {
|
|
sum uint16
|
|
odd bool
|
|
}
|
|
|
|
// Add adds b to checksum.
|
|
func (c *Checksumer) Add(b []byte) {
|
|
if len(b) > 0 {
|
|
c.sum, c.odd = calculateChecksum(b, c.odd, c.sum)
|
|
}
|
|
}
|
|
|
|
// Checksum returns the latest checksum value.
|
|
func (c *Checksumer) Checksum() uint16 {
|
|
return c.sum
|
|
}
|
|
|
|
// Combine combines the two uint16 to form their checksum. This is done
|
|
// by adding them and the carry.
|
|
//
|
|
// Note that checksum a must have been computed on an even number of bytes.
|
|
func Combine(a, b uint16) uint16 {
|
|
v := uint32(a) + uint32(b)
|
|
return uint16(v + v>>16)
|
|
}
|