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 [email protected] _______________________________________________ zeromq-dev mailing list [email protected] http://lists.zeromq.org/mailman/listinfo/zeromq-dev
