[zeromq-dev] Feedback on pubsub pull requests (trie/mtrie fixed, etc.)

[john skaller]

On 30/01/2012, at 11:24 PM, Martin Sustrik wrote:

> On 30/01/12 10:49, Staffan Gimåker wrote:
> 
>> 2. https://github.com/zeromq/libzmq/pull/227
>> 
>> Reduce memory usage of mtrie. Instead of keeping a std::set around for
>> only mtrie nodes we only allocate it when needed. Worst case this
>> increase memory usage by sizeof(void*) bytes per node, but typically it
>> will lower it. For example, in our application this cuts memory usage in
>> half. The performance impact should be minimal (I could generate some
>> graphs if someone thinks otherwise).
> 
> Btw, if you are interesting in reducing memory usage even further (along 
> with speading up the algorithm) there's option of having yet another 
> node type which would represent a string of subsequent characters rather 
> than a single character, e.g:
> 
> re---build
>    |
>    +-t---ry
>        |
>        +---weet
> 
> Etc.


If you want minimal memory usage and the fastest possible performance
you would be using a JudySLArray. There's no better data structure.
Its cache tuned, outperforms every other tree structure,  supports
finding ==, < <=, > >= any key, its stable and bug free, and has
a permissive licence.

http://judy.sourceforge.net/

https://github.com/felix-lang/judy

"A C library for creating and accessing dynamic arrays with near O(log-base-256) scalability into the peta-element range"

[BTW: seems RabbitMQ uses Judy ..]


--
john skaller
skaller at users.sourceforge.net