[squid-dev] RFC: making TrieNode less memory-hungry

[Amos Jeffries]

On 20/06/20 9:13 am, Francesco Chemolli wrote:
> Hi all,
>   I'm looking at the TrieNode code, and while it's super fast, it's
> quite memory-hungry: each node uses 2kb of RAM for the children index
> and any moderately-sized Trie has plenty of nodes. On the upside, it's
> blazing fast.
> 
> How about changing it so that each node only havs as many children as
> the [min_char, max_char] range, using a std::vector and a min_char
> offset? Lookups would still be O(length of key), insertions may require
> shifting the vector if the char being inserted is lower than the current
> min_char, but the memory savings sound promising.
> 
> What do you think?
> 

Before doing anything, please look at how trie is implemented for
rbldnsd. It is both super fast and memory efficient. A lot of the
optimization analysis and work has already been done by some super smart
people we can probably leverage.

Also, keep in mind that trie is only used by ESI. So it is not exactly a
high-usage feature.


Amos