From 1 µs to 45 ns: Rewriting a Go Cloud IP Lookup on net/netip

go-cloudip answers one question: does this IP address belong to AWS, GCP, Azure, Cloudflare, DigitalOcean or Oracle, and if so, the provider plus whatever region and service metadata it has. You hand it an address from a log line or a connection, it looks the address up in about 131,000 published ranges and tells you aws, eu-central-1, EC2. A typical use is enrichment: tagging flow records or access logs in bulk against a snapshot that’s rebuilt daily.

The README promised “sub-microsecond lookup times”, and a benchmark that looks up one address agrees: 234 ns on my machine. Benchmarked with 65,536 sampled addresses instead of one, an IPv4 lookup that hits takes 1,069 ns and the benchmark reports 5 allocs/op. I rewrote the lookup. Version v0.0.20 replaces the cidranger trie with a flat, sorted index built on net/netip, and the same benchmark now takes 45 ns with zero allocations. Startup went from 741 ms to 49 ms.

Every number below comes from cloudip-bench, a separate repo that runs the same benchmark file against both releases on the same pinned data (cloudip-db v2026-10-26, 131,624 records, 83,206 distinct prefixes), compares the new index with bart and cidranger under the same result contract, and checks the answers against a slow oracle. Everything ran on one Apple M1 Max with Go 1.26.8, so treat the absolute numbers as one machine’s numbers. You need Go 1.26 or newer to run it.

One address, one path through the trie

The old benchmark looked up 52.94.76.1 in a loop. One address walks one path through the trie and matches the same few networks every time, so the benchmark measured that one case. Other addresses go deeper or match more networks: v0.0.19 reported 3 allocs/op on that single address and 5 on hitting samples.

cloudip-bench replays 65,536 seeded samples, wrapping around with a mask. There are four sets, and every run sees the same addresses: v4hit picks a random record from the snapshot and a random address inside it (so every lookup hits, and prefixes listed in several records get picked more often), v4random is uniform random IPv4 (mostly misses), v4mix shuffles the two 50/50, and v6hit does the same as v4hit for IPv6 records. The same set keeps the old one-address benchmark around for comparison. The samples are drawn with replacement, so v4hit has 56,842 distinct addresses and v6hit 62,824. They’re synthetic and may not look like real traffic. They still reach far more of the index than one address does.

The release comparison is one file in release/ that only uses go-cloudip’s public API. scripts/bench.sh copies it into a scratch module, pins go-cloudip to v0.0.19 and then v0.0.20, runs each ten times, and hands both outputs to benchstat:

The same row lands inside the README’s 200–250 ns range: 234 ns. On hitting samples the same code takes 1,069 ns. The new version shows the same gap at a smaller scale, 19 ns for one address and a 45 ns median over ten runs on the samples, where benchstat reports ±15% uncertainty. Measured with only one address, the speedup reads 12x instead of 24x, and the 4.6x gap, with hitting lookups over a microsecond, doesn’t show at all.

Startup shows up in that table too: NewDetector went from 15 million allocations to 4,250.

Where the old version spent its time

The v0.0.19 lookup turned the netip.Addr back into a net.IP, asked cidranger for every network containing it, and kept the longest:

func (s *detectorState) lookup(ip net.IP) *rangeEntry {
	if s == nil || s.ranger == nil {
		return nil
	}

	entries, err := s.ranger.ContainingNetworks(ip)
	if err != nil || len(entries) == 0 {
		return nil
	}

	// Return the most specific (smallest) matching network
	// cidranger returns entries in order, but we want the most specific
	var best *rangeEntry
	var bestSize int = -1

	for _, e := range entries {
		entry, ok := e.(*rangeEntry)
		if !ok {
			continue
		}

		// Calculate network size (smaller = more specific)
		ones, _ := entry.network.Mask.Size()
		if bestSize < 0 || ones > bestSize {
			best = entry
			bestSize = ones
		}
	}

	return best
}

ContainingNetworks collects every containing entry into newly allocated slices when the address hits, and the allocation profile of a million hitting lookups puts 89% of the objects allocated under LookupAddr there. The net.IP conversion (netip.Addr.AsSlice) is another 7%. So most of the garbage came from asking for all matches when only the longest one was needed, and much less from net.IP itself. The CPU profile of the whole benchmark process, setup included, shows the same shape: containingNetworks and everything it calls account for 53% of the samples, and the runtime’s madvise another 16%:

In the second profile, v0.0.20 on the same addresses, neither mallocgc nor madvise shows up in its top entries, and lookup4, the index probe, is the largest one. (pprof has a goroutine profile too; the goroutine visualizer post builds a leak detector on it.)

Startup had its own allocation problem. Creating the detector made 15 million allocations for 131,624 records, and the allocation profile pointed at net.(*IPNet).String. The caller was cidranger’s network comparison:

func (n Network) Equal(n1 Network) bool {
	return n.String() == n1.String()
}

Every equality check during insert formats both networks as strings. Over the profiled runs, 81% of all objects allocated during startup came through that one line:

With net/netip this problem doesn’t exist. netip.Prefix and netip.Addr are small comparable values that hold the address inline, so equality is == and they work as map keys without building strings. v0.0.20 also stopped using msgpack.Unmarshal and decodes the snapshot with a small hand-written decoder that interns region and service strings, so the drop to 4,250 startup allocations comes from both changes. Tailscale’s post on netaddr.IP, the package that became net/netip, explains why the type was designed that way.

Same prefix, three answers

A faster lookup still has to decide what it returns, and the data has duplicates. The 131,624 records cover only 83,206 distinct prefixes. 1.178.10.0/24 appears three times, as AWS AMAZON, S3 and EC2 in eu-central-1. Many Azure prefixes appear once under a global service tag with no region and again under its regional twin.

cidranger’s insert replaces the entry when the network is already there, so v0.0.19 returned whichever record came last in the file. The same address could get a different service depending on how the upstream feed was ordered that day.

v0.0.20 sorts the records before building, so file order no longer matters, and picks one representative record per prefix with a fixed policy. Among the records for the most specific matching prefix, the provider listed first in the snapshot wins, and within that provider a record with a region beats one without, and a specific service beats an umbrella tag:

// rowRank for same-prefix rows, lower wins: has region, then not umbrella
// tag (AMAZON, AzureCloud).
func rowRank(region, service string) int8 {
	var rank int8
	if region == "" {
		rank += 2
	}
	if service == "AMAZON" || service == "AZURECLOUD" || strings.HasPrefix(service, "AZURECLOUD.") {
		rank++
	}
	return rank
}

The same-prefix tie-break key is the provider’s index in the snapshot, then this rank, then service and region name, so every tie has one answer. One more rule is an inference rather than data: while building the index, an empty region is filled from the nearest enclosing prefix whose chosen record has the same provider and a region, and that ancestor’s region may itself be inherited. LookupAddr does no ancestor traversal; it reads the prepared answer. It’s aimed at Azure’s global service tags, which carry no region while the addresses also appear in regional AzureCloud.<region> ranges. LookupResult doesn’t say when a region was inherited.

LookupAll returns every distinct record of every containing prefix with the published service and region, so you can see what the feed says:

Changing the rules changes answers, and I wanted to know how many. Both releases answered 188,220 probe addresses and answerdiff compared them:

43% of these probe answers changed, and every one of them kept the same prefix and the same provider. Only the chosen service or region moved, through the new record policy, the region rule or both. Picking EC2 over S3 makes the answer stable; it doesn’t prove EC2 is what runs on that address, and LookupAll is there for when you need all of them. The change also means the release benchmark compares two versions that don’t return the same answers, so further down there’s a second comparison where every index works under one contract.

Flattening nested ranges into one sorted array

CIDR blocks have a property that makes the rest of this work: any two are either disjoint or one contains the other. They never partially overlap. So if you sort all prefixes by start address, with the wider one first when two start at the same address, and walk them with a stack, you can cut the address space into non-overlapping segments where each segment knows its most specific prefix:

When the sweep reaches the start of a prefix, it emits a segment boundary owned by that prefix and pushes it. Before handling the next prefix, it pops every prefix that ended earlier, and each pop emits a boundary right after that prefix’s last address, owned by whatever is now on top of the stack, or by “no match” if the stack is empty. That second part is the one that’s easy to get wrong: when 10.1.2.0/24 ends, the addresses after it belong to 10.1.0.0/16 again, not to nothing.

This is the sweep from go-cloudip’s index.go:

	// sweep: ents[lo:hi] of one family -> segs covering family; sets parents
	sweep := func(lo, hi int, maxAddr u128) (starts []u128, refs []uint64) {
		starts = make([]u128, 1, 2*(hi-lo)+1)
		refs = make([]uint64, 1, 2*(hi-lo)+1)
		emit := func(at u128, ref uint64) {
			n := len(starts)
			switch {
			case starts[n-1] == at:
				refs[n-1] = ref
				if n > 1 && refs[n-2] == ref {
					starts, refs = starts[:n-1], refs[:n-1]
				}
			case refs[n-1] != ref:
				starts, refs = append(starts, at), append(refs, ref)
			}
		}
		stack := make([]int, 0, 64)
		pop := func() {
			t := ents[stack[len(stack)-1]]
			stack = stack[:len(stack)-1]
			if t.last == maxAddr {
				return
			}
			var ref uint64
			if len(stack) > 0 {
				ref = ents[stack[len(stack)-1]].ref
			}
			emit(t.last.inc(), ref)
		}
		for e := lo; e < hi; e++ {
			for len(stack) > 0 && ents[stack[len(stack)-1]].last.less(ents[e].first) {
				pop()
			}
			if len(stack) > 0 {
				ix.tree[e].parent = uint32(stack[len(stack)-1])
				ents[e].ref = inheritRegion(ents[e].ref, ix.tree[e].parent)
			}
			emit(ents[e].first, ents[e].ref)
			stack = append(stack, e)
		}
		for len(stack) > 0 {
			pop()
		}

The arrays start with one segment at address zero with ref 0, which means “no match”, so gaps are real segments and a lookup never needs a separate “is this covered?” check. emit overwrites when two boundaries land on the same address and skips a boundary that wouldn’t change the answer, so adjacent pieces with the same owner merge. And the t.last == maxAddr check stops the sweep from computing “last address + 1” for a prefix that ends at 255.255.255.255 or ffff:...:ffff, where it would wrap to zero. The same loop records each prefix’s parent, which is what LookupAll walks later.

The snapshot flattens to 78,374 IPv4 segments and 36,272 IPv6 segments. IPv4 starts are uint32, IPv6 starts are a two-word u128, both packed from the byte arrays that Addr.As4() and Addr.As16() return. A lookup is then “find the last segment start at or below this address”. Plain slices.BinarySearch over all 78,374 starts does that (stepping back one when the address isn’t itself a start) in 81 ns on hitting addresses. I wrote about how Go slices sit in memory a while ago. One flat []uint32 is compact and has no pointer-linked nodes to chase. It’s still too slow: about 17 probes into a 300 KB array, and each next probe depends on the result of the one before.

A directory on the top 16 bits

go-cloudip skips most of that search with a 65,536-entry array indexed by the top 16 bits of the address, one entry per /16 block:

If a whole /16 falls inside one segment, its entry is a leaf that holds the answer, and the lookup is one array read. That’s 63,560 of the 65,536 blocks, which makes sense: most of the IPv4 space belongs to no cloud provider, and big provider blocks cover whole /16s. If a block spans a few segments, the entry stores the range of segments to search, and 824 blocks are like that. If the block spans more than eight segments, it gets its own 256-entry table indexed by the next 8 bits, and each of those entries is again a leaf or a range of segments. Most of those ranges are short, but not all: 1,806 of them span more than eight segments, and the widest spans 140. 1,152 dense blocks get one, which costs 2.4 MB. These counts come from a test that needs go-cloudip’s unexported fields; it’s in cloudip-bench’s extras/ folder with instructions for running it inside a go-cloudip checkout.

The search that’s left runs only over the selected range, and it’s branchless:

func (ix *index) lookup4(x uint32) uint64 {
	d := ix.dir4[x>>16]
	if d&dirSub != 0 {
		d = ix.sub4[uint32(d)|x>>8&0xff]
	}
	if d&dirLeaf != 0 {
		return d &^ dirLeaf
	}
	s := ix.starts4
	base, n := int(d>>32), int(uint32(d))-int(d>>32)+1
	for n > 1 {
		half := n >> 1
		base += half & geMask32(x, s[base+half])
		n -= half
	}
	return ix.refs4[base]
}

// geMask32: -1 if x >= y else 0. Branchless; branches mispredict on random input.
func geMask32(x, y uint32) int {
	return int((uint64(x)-uint64(y))>>63) - 1
}

geMask32 turns the comparison into a mask. For a fixed search span the loop takes a fixed number of iterations, and the comparison picks the next base with arithmetic instead of a branch. The directory dispatch and the loop condition still branch. I measured the bare probe three ways on the same hitting addresses: as shipped, 15.8 ns; the same directory with slices.BinarySearch inside the block, 27.7 ns; no directory at all, 80.8 ns. On random addresses the shipped and the slices.BinarySearch versions are both about 3 ns. With 97% of the /16 blocks being leaves, most random addresses never reach the search.

A 16 ns probe inside a 45 ns lookup

The probe is 15.8 ns and a full LookupAddr hit is 45 ns. I don’t want to split that gap by subtracting one benchmark from another, since they don’t run the same code around the probe. The CPU profile, which also covers the benchmark’s setup (a few percent of the samples), has lookup4 at 38% of the samples, LookupAddr’s own body at 31% (loading the state, the call, moving the 72-byte result) and result at 8%, so the full API costs a lot more than the probe and the profile doesn’t pin down one culprit. result turns the packed reference into a LookupResult: it reads the metadata record and the CIDR string for the matched entry from two more tables.

If you only need to know whether an address belongs to any cloud provider, IsCloudProviderAddr returns a bool without building a result and takes 18.9 ns on the mixed set. The string API pays for parsing. go-cloudip has its own strict IPv4 parser, and on the same address strings it takes 24.1 ns against netip.ParseAddr’s 28.9 ns. That parser returns a uint32 instead of a netip.Addr, so the two don’t do quite the same work, and netip.ParseAddr is already quick.

I also tried to speed up IPv6. The shipped IPv6 probe samples every 16th segment start into a small array, searches that, then counts through one block of 16. A plain branchless bisect over all 36,272 starts measured 47.7 ns against 75.4 ns for the shipped version in the probe benchmark. In the full LookupAddr benchmark it didn’t show a significant improvement. Over five rounds, alternating the two builds with two samples per process, the shipped version stayed between 110 and 116 ns. The bisect version landed near 108 ns in some processes and near 131 ns in others, with medians of 112.4 and 109.6 ns and benchstat reporting p=0.469, and the string version was 7% slower. The isolated probe was faster, the full lookup didn’t establish an improvement, and I kept the shipped code.

bart, and the comparison harness

bart is the routing table I’d reach for first in Go. It supports inserts and deletes, and I compared two of its v0.30.0 variants: bart.Table, the default, and bart.Fast, which spends more memory per node for faster lookups. For a fair comparison, cloudip-bench gives both, and cidranger, go-cloudip’s LookupAddr contract: the same chosen record per prefix, the same inherited regions computed from the published records, and a filled LookupResult on every hit (an empty one on a miss), read from a results table through an int32 payload. The maplen column is the naive approach, one map lookup per prefix length from longest to shortest, which is also the test oracle:

bart.Fast is the fastest on IPv4 hits, 56.9 ns against go-cloudip’s 60.6 ns (p=0.005). The star in the table only marks the lowest median in each row; it isn’t a significance test. On the mixed set benchstat finds no significant difference, on IPv6 hits they’re within about 1% (118.2 vs 119.6 ns), and go-cloudip is ahead on random IPv4, where most lookups end at a directory leaf. Against the default bart.Table, go-cloudip takes 13% less time on IPv4 hits and 34% less on IPv6.

TestMemory measures how much live heap each index adds after the snapshot rows are already decoded. bart and cidranger reuse those rows’ strings in their result tables, while go-cloudip decodes its own copy of the data, so this is an incremental number for this harness rather than a standalone footprint. Measured that way, bart.Fast adds 16.1 MB, bart.Table 10.3 MB and go-cloudip 9.6 MB:

For a table that’s built once and never changed, the flat index gets close to bart.Fast and adds less heap than either bart table, at least in this harness. If your prefixes change between rebuilds, or you need queries like Supernets and Subnets of a prefix, use bart, and bart.Fast if lookups dominate.

The table’s absolute numbers are higher than the release benchmark’s. go-cloudip’s IPv4 hit is 45 ns in the release run and 60.6 ns in the table. I first thought the test binary itself was to blame. BenchmarkHarness measures the same call both ways:

Called directly, the same lookup takes 44.3 ns in the comparison binary, close to the release run’s 45.1 ns. Called through the CloudIP adapter and the Looker interface, it takes 59.9 ns. That measures this call arrangement for go-cloudip as a whole; it doesn’t separate the dispatch, the wrapper and passing the result back. Every implementation in the Lookup rows goes through Looker, though its overhead needn’t be identical for each, so compare within those rows and use the release benchmark for go-cloudip’s own numbers.

Checking a flat table is right

The tests hit prefix boundaries on purpose, to catch off-by-one errors. cloudip-bench picks the record and fills inherited regions from the published records itself, without calling go-cloudip. The oracle, both bart variants and cidranger all answer from that one preparation. When go-cloudip matches the oracle exactly, that checks its record choice and inheritance. When bart and cidranger match it, that checks their lookups only. The checks run on every workload address plus the first and last address of every prefix and the address on each side of them.

cloudip-bench also serves 160 random synthetic tables to go-cloudip through an httptest server (nested, adjacent and duplicated prefixes, mixed providers, 0.0.0.0/0, ::/0 and the last address of each family) and checks every address of a /16 or /112 for each one. It shuffles the real records and checks that all 332,824 probes still get the same answer, and TestInheritance pins the region rule with hand-written cases: nearest parent wins, a parent from another provider is skipped, and a parent’s own inherited region counts.

In the real data that one inference touches a lot of answers: 62,527 of the 660,504 checked answers carry a region taken from an enclosing range. To make sure the tests can fail, TestOracleWithoutInheritanceFails builds the oracle without inheritance and checks that it disagrees with go-cloudip; it does on 43,801 probes.

From a trie to a flat array

The rewrite changed several things at once, so I can’t split the 24x between them. The trie with a result slice became one sorted array with a directory in front of it, built once and only read afterwards. net/netip fits that design: As4 and As16 hand over bytes the index packs into integers, prefixes are comparable values, and the LookupAddr benchmarks report zero allocations per lookup. Next time I’d benchmark with many sampled inputs from day one; one hot address hid a 4.6x gap. And the full lookup still costs about three times the bare probe, so a leaner result type is the next thing I’d try.

Benchmarks, tests, raw results and profiles are on GitHub, and the library is go-cloudip.