5 ms·

Compressing Radix Trees Without Too Many Tears (2017)

58 points by noch 9y ago

vbernat 9y ago
Radix trees are often used in routing tables. On Linux, for IPv4, there is an additional level of compression to avoid the cost of many intermediate nodes. I've described the algorithm used on Linux here: https://vincent.bernat.im/en/blog/2017-ipv4-route-lookup-linux#route-lookup-in-a-trie https://vincent.bernat.im/en/blog/2017-ipv4-route-lookup-lin...
fanf2 9y ago
See also djb’s crit-bit trees, which are a tighter and simpler version of PATRICIA trees - https://cr.yp.to/critbit.html https://cr.yp.to/critbit.html - and agl‘s nice literate code explanation of how they work - https://github.com/agl/critbit/ https://github.com/agl/critbit/ And my qp tries, which are smaller and faster than crit-bit trees https://dotat.at/prog/qp/ https://dotat.at/prog/qp/
- PeCaN 9y ago
  Oh hey, I've used qp-tries in an interpreter for a Forth-like language. They're really elegant IMO. Thanks for publicizing and implementing your discovery!
  - fanf2 9y ago
    Always a pleasure to hear about people making good use of them!
- tonyg 9y ago
  Both critbit and qp tries are wonderful. I have pure-functional implementations of the central critbit algorithms in OCaml (https://github.com/tonyg/ml-critbit/blob/master/critbit.ml https://github.com/tonyg/ml-critbit/blob/master/critbit.ml) and Typed Racket (https://github.com/tonyg/racket-critbit/blob/master/critbit.rkt https://github.com/tonyg/racket-critbit/blob/master/critbit....). I was surprised to find the OCaml implementation is competitive speedwise with the built-in Set implementation over strings.
danbruc 9y ago
An obvious way to save space that is not mentioned is of course not to have alphabet sized pointer arrays in each node and if the alphabet is big, for example Unicode characters, it is not really an option to begin with. In that case you would use some kind of dictionary to store the pointers to child nodes. You can also dynamically switch between different node implementations depending on the number of child nodes.
- deleted 9y ago
  [deleted]
faragon 9y ago
Compressing tree data is not trivial. E.g. using per-node heap allocation could take many times the space of the actual data (memory used by the allocator, metainformation, alignment padding, etc.). Using a custom allocator can reduce the memory usage dramatically.

58 points by noch 9y ago

Radix trees are often used in routing tables. On Linux, for IPv4, there is an additional level of compression to avoid the cost of many intermediate nodes. I've described the algorithm used on Linux here: https://vincent.bernat.im/en/blog/2017-ipv4-route-lookup-linux#route-lookup-in-a-trie https://vincent.bernat.im/en/blog/2017-ipv4-route-lookup-lin...

fanf2 9y ago

See also djb’s crit-bit trees, which are a tighter and simpler version of PATRICIA trees - https://cr.yp.to/critbit.html https://cr.yp.to/critbit.html - and agl‘s nice literate code explanation of how they work - https://github.com/agl/critbit/ https://github.com/agl/critbit/ And my qp tries, which are smaller and faster than crit-bit trees https://dotat.at/prog/qp/ https://dotat.at/prog/qp/

PeCaN 9y ago
Oh hey, I've used qp-tries in an interpreter for a Forth-like language. They're really elegant IMO. Thanks for publicizing and implementing your discovery!
- fanf2 9y ago
  Always a pleasure to hear about people making good use of them!
tonyg 9y ago
Both critbit and qp tries are wonderful. I have pure-functional implementations of the central critbit algorithms in OCaml (https://github.com/tonyg/ml-critbit/blob/master/critbit.ml https://github.com/tonyg/ml-critbit/blob/master/critbit.ml) and Typed Racket (https://github.com/tonyg/racket-critbit/blob/master/critbit.rkt https://github.com/tonyg/racket-critbit/blob/master/critbit....). I was surprised to find the OCaml implementation is competitive speedwise with the built-in Set implementation over strings.

danbruc 9y ago

An obvious way to save space that is not mentioned is of course not to have alphabet sized pointer arrays in each node and if the alphabet is big, for example Unicode characters, it is not really an option to begin with. In that case you would use some kind of dictionary to store the pointers to child nodes. You can also dynamically switch between different node implementations depending on the number of child nodes.

deleted 9y ago
[deleted]

faragon 9y ago

Compressing tree data is not trivial. E.g. using per-node heap allocation could take many times the space of the actual data (memory used by the allocator, metainformation, alignment padding, etc.). Using a custom allocator can reduce the memory usage dramatically.