RFC: making TrieNode less memory-hungry
Francesco Chemolli <[email protected]>
| Newsgroups | gmane.comp.web.squid.devel |
|---|---|
| Message-ID | <CA+Y8hcNpFipqkYBkMyALo9Mw8mPjT6X=e1fLidK+VnWouaWXZg@mail.gmail.com> |
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?
--
Francesco
_______________________________________________
squid-dev mailing list
[email protected]
http://lists.squid-cache.org/listinfo/squid-dev