Benchmarks

Some Trie Operation Benchmarks

Specs: go 1.19.2 on a MacBook Pro MacOS Ventura 13.5.1 with the Apple M1 Max processor and 32 GB of RAM goos: darwin goarch: arm64

Of course, the benchmark numbers depend on the subnets in the trie and the address used to search. In general they show that operations are on the order of hundreds of nanoseconds. In particular, subnet containment operations are very fast.

Benchmark code

Subnet Containment Check, Shortest Prefix Match, Longest Prefix Match, and All Containing Subnets (Contained in Subnet in Trie)

BenchmarkIPv4ElementContains
BenchmarkIPv4ElementContains-10        	 3653710	       323.0 ns/op
BenchmarkIPv6ElementContains
BenchmarkIPv6ElementContains-10        	11027071	       109.0 ns/op
BenchmarkIPv4ElementNotContains
BenchmarkIPv4ElementNotContains-10     	15974688	        75.23 ns/op
BenchmarkIPv6ElementNotContains
BenchmarkIPv6ElementNotContains-10     	14500480	        81.52 ns/op
BenchmarkIPv4LongestPrefixMatch
BenchmarkIPv4LongestPrefixMatch-10       	 3558340	       335.5 ns/op
BenchmarkIPv6LongestPrefixMatch
BenchmarkIPv6LongestPrefixMatch-10       	 8051430	       147.3 ns/op
BenchmarkIPv4LongestPrefixNoMatch
BenchmarkIPv4LongestPrefixNoMatch-10     	15106396	        79.53 ns/op
BenchmarkIPv6LongestPrefixNoMatch
BenchmarkIPv6LongestPrefixNoMatch-10     	13835463	        87.33 ns/op
BenchmarkIPv4ShortestPrefixMatch
BenchmarkIPv4ShortestPrefixMatch-10      	 3606108	       335.3 ns/op
BenchmarkIPv6ShortestPrefixMatch
BenchmarkIPv6ShortestPrefixMatch-10      	10479979	       115.6 ns/op
BenchmarkIPv4ShortestPrefixNoMatch
BenchmarkIPv4ShortestPrefixNoMatch-10    	14696163	        79.18 ns/op
BenchmarkIPv6ShortestPrefixNoMatch
BenchmarkIPv6ShortestPrefixNoMatch-10    	12683972	        90.83 ns/op
BenchmarkIPv4ElementsContaining
BenchmarkIPv4ElementsContaining-10       	 2627948	       458.8 ns/op
BenchmarkIPv6ElementsContaining
BenchmarkIPv6ElementsContaining-10       	 4225256	       308.0 ns/op
BenchmarkIPv4ElementsContainedBy
BenchmarkIPv4ElementsContainedBy-10      	 3952704	       304.5 ns/op
BenchmarkIPv6ElementsContainedBy
BenchmarkIPv6ElementsContainedBy-10      	 8279932	       142.2 ns/op

Equality (Contained in Trie)

BenchmarkIPv4Contains
BenchmarkIPv4Contains-10                 	 3852819	       313.6 ns/op
BenchmarkIPv6Contains
BenchmarkIPv6Contains-10                 	 7827152	       153.6 ns/op
BenchmarkIPv4NotContains
BenchmarkIPv4NotContains-10              	 4351102	       276.6 ns/op
BenchmarkIPv6NotContains
BenchmarkIPv6NotContains-10              	 8383827	       143.9 ns/op

Add and Remove

BenchmarkIPv4AddAndRemove
BenchmarkIPv4AddAndRemove-10             	  779631	      1604 ns/op
BenchmarkIPv6AddAndRemove
BenchmarkIPv6AddAndRemove-10             	 1337410	       897.6 ns/op

Operations to Find the "Closest" Addresses or Subnets (Closest Subnet or Address in Trie)

BenchmarkIPv4Floor
BenchmarkIPv4Floor-10                    	 1260399	       958.7 ns/op
BenchmarkIPv6Floor
BenchmarkIPv6Floor-10                    	 1962202	       581.4 ns/op
BenchmarkIPv4Ceiling
BenchmarkIPv4Ceiling-10                  	 1287793	       935.0 ns/op
BenchmarkIPv6Ceiling
BenchmarkIPv6Ceiling-10                  	 2050754	       592.8 ns/op