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 _______________________________________________ squid-dev mailing list squid-dev@lists.squid-cache.org http://lists.squid-cache.org/listinfo/squid-dev
