[zeromq-dev] scalability of zeromq in terms fof queues and topics

Martin Sustrik sustrik at 250bpm.com
Sat Apr 10 07:19:31 CEST 2010


Bhavin,

> Thanks for the links. We checked the code and I am kicking myself for not
> realizing that a basic trie would be all that's needed :). We also noticed
> the nice lil optimization to the trie data structure implementation to
> reduce storage space requirements :)

It's trading functionality (no sexy regular expressions) for performance...

There's still one possibility for optimisation though: If, at any 
particular place of the tree there's a single-branch node (currently the 
memory footprint optimisation you've noticed), the associated structure 
could possibly hold up to say 8 subsequent characters. The idea is that 
single-branch nodes tend to appear in strings. Consider following 
example. Plus signs correspond to real branchings while minus signs 
denote strings of single-branch nodes:

animals.dogs
--------+++-

animals.donkeys
--------+++----

animals.ducks
--------++---

animals.cats
--------+---

The whole point is to significantly lower memory footprint which in turn 
should have severe impact on performance. Specifically with large search 
trees it may happen that some parts of the tree are eliminted from the 
CPU cache. In such case, access to physical memory can slow down the 
algorithm by an order of magnitude. Thus keeping the data structure as 
compact as possible will make it much faster, even for sparsely used topics.

Thoughts?
Martin



More information about the zeromq-dev mailing list