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

[Staffan Gimåker]

On Mon, Jan 30, 2012 at 1:24 PM, Martin Sustrik <sustrik at 250bpm.com> wrote:
>
> 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
>

I did consider Patricia tries, among others. For our setup I didn't think
they were the best candidate in terms of memory usage and implementation
complexity, so I didn't explore that option further.

Out of the stuff I experimented with (bucketing, using bitsets to determine
which nodes are non-null, ...) I never really got anything that matched the
matching performance of the current solution. Due to that and that exact
matching seemed like the better option for us I decided to abandon that
work for now. I would be very interested in seeing how a Patricia and
something Burst trie-like compare to the current solution, though.

/S
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.zeromq.org/pipermail/zeromq-dev/attachments/20120130/592c4974/attachment.htm