device: use linked list for per-peer allowed-ip traversal

This makes the IpcGet method much faster.

We also refactor the traversal API to use a callback so that we don't
need to allocate at all. Avoiding allocations we do self-masking on
insertion, which in turn means that split intermediate nodes require a
copy of the bits.

benchmark               old ns/op     new ns/op     delta
BenchmarkUAPIGet-16     3243          2659          -18.01%

benchmark               old allocs     new allocs     delta
BenchmarkUAPIGet-16     35             30             -14.29%

benchmark               old bytes     new bytes     delta
BenchmarkUAPIGet-16     1218          737           -39.49%

This benchmark is good, though it's only for a pair of peers, each with
only one allowedips. As this grows, the delta expands considerably.

Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>

1 files changed, 0 insertions, 1 deletions

diff --git a/device/device.go b/device/device.go
index ebcbd9e..47c4944 100644
--- a/device/device.go
+++ b/device/device.go
@@ -314,7 +314,6 @@ func NewDevice(tunDevice tun.Device, logger *Logger) *Device {
 	device.rate.underLoadUntil.Store(time.Time{})
 
 	device.indexTable.Init()
-	device.allowedips.Reset()
 
 	device.PopulatePools()