3 ms·
Thanks for the excellent write-up. Probably not as cache-friendly, but did you, at any point, evaluate Radix Tree [0] or Patricia Trie / CritBit Tree [1][2] as
by ignoramous 7y ago
Thanks for the excellent write-up.
Probably not as cache-friendly, but did you, at any point, evaluate Radix Tree [0] or Patricia Trie / CritBit Tree [1][2] as an underlying data-structure for the hash-table? These also compact nicely into one of the many succinct data-structures [3][4].
Radix Tree, in particular, seems to work really well for IPs from what I've read [5].
---
[0] https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-linux https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-lin...
[1] https://news.ycombinator.com/item?id=6920862 https://news.ycombinator.com/item?id=6920862
[2] https://news.ycombinator.com/item?id=3015246 https://news.ycombinator.com/item?id=3015246
[3] https://news.ycombinator.com/item?id=2348619 https://news.ycombinator.com/item?id=2348619
[4] https://news.ycombinator.com/item?id=3650657 https://news.ycombinator.com/item?id=3650657
[5] https://news.ycombinator.com/item?id=18921058 https://news.ycombinator.com/item?id=18921058