bart
"BAlanced Routing Table", a path-compressed radix trie optimized for fast IP address and prefix lookup with minimal memory footprint.
Based on the Go implementation of the same name.
Examples
use ;
use ;
Performance
You can run the benchmarks with:
Current performance figures put us in the same ballpark as go-bart.
Memory utilization
Amortized memory utilization for a large route table is about 24 bytes/route for IPv4 routes and 40 bytes/route for IPv6 routes -- this is just the prefix storage, the actual memory size will vary with the stored value type. This is slightly worse than go-bart, which on my machine reports 20 bytes/rt for combined IPv4/IPv6, 37 bytes/rt for IPv6, and confusingly 101 bytes/rt for IPv4-only.
If using the table as a RIB (IpAddr table values), this comes out to ~48 bytes/rt for IPv4 and ~75
bytes/rt for IPv6.
Implementation status
The current implementation should be usable as a routing table, though it hasn't been tested in anger yet. Some of the more involved functionality provided by bart is lacking, however:
- Table inspection (sorted prefix walk primarily, we do provide a DFS node iterator)
- Table merging and intersection
- Optional persistent data structure functionality (shallow clone on mutate)
- Subnet/supernet queries