[zeromq-dev] Radix tree perf?

Francesco francesco.montorsi at gmail.com
Tue Nov 14 10:23:29 CET 2023


Hi Axel,
I'm interested in this topic as well.
I think the radix tree has been proposed as an alternative to mtrie to
allow better memory usage.
See
    https://github.com/zeromq/libzmq/issues/1400
for the details.
In particular in comment
https://github.com/zeromq/libzmq/issues/1400#issuecomment-432774639, there
are benchmarks reporting, for 1M key case, that the radix tree is twice
_FASTER_ than the generic trie. In your test, you seem to find quite the
opposite:

>keys = 1000000, queries = 1000000, key size = 20
>[trie]
>Average lookup time = 17.0 ns
>[radix_tree]
>Average lookup time = 462.3 ns

Can you check how to reproduce the same type of table reported in
https://github.com/zeromq/libzmq/issues/1400#issuecomment-432774639 ?
Maybe that will shed some light on this discrepancy.

Maybe the discrepancy comes from the large refactor of the zeromq generic
mtrie done in this commit

https://github.com/zeromq/libzmq/commit/ab301ebf799b4dbddb1351d77da49b2e6e1cf8ec

and which came AFTER the integration of the radix tree and thus has
probably obsoleted the results reported in
https://github.com/zeromq/libzmq/issues/1400#issuecomment-432774639.

Thanks,
Francesco

PS: my interest on this topic comes from the fact that apparently
integration tests might take a lot of time when the zmq code is
instrumented with Google ASAN, due (apparently) to the large number of
de-allocations happening inside the generic mtrie, after we switched to the
implementation of commit ab301ebf799b4dbddb1351d77da49b2e6e1cf8ec





Il giorno dom 12 nov 2023 alle ore 05:05 Axel R. <axelriet at gmail.com> ha
scritto:

> I'm running the *benchmark_radix_tree* test app and what I see is the
> radix tree is considerably slower than the trie from 1 to at least 10
> million keys.
>
> Is the test representative of real-world use in ZeroMQ? If yes, in which
> circumstance(s) would one want to enable that option?
>
> keys = 1, queries = 1000000, key size = 20
> [trie]
> Average lookup time = 17.0 ns
> [radix_tree]
> Average lookup time = 31.6 ns
>
> keys = 10, queries = 1000000, key size = 20
> [trie]
> Average lookup time = 17.2 ns
> [radix_tree]
> Average lookup time = 41.1 ns
>
> keys = 100, queries = 1000000, key size = 20
> [trie]
> Average lookup time = 17.2 ns
> [radix_tree]
> Average lookup time = 58.0 ns
>
> keys = 1000, queries = 1000000, key size = 20
> [trie]
> Average lookup time = 17.2 ns
> [radix_tree]
> Average lookup time = 74.3 ns
>
> keys = 10000, queries = 1000000, key size = 20
> [trie]
> Average lookup time = 17.3 ns
> [radix_tree]
> Average lookup time = 117.1 ns
>
> keys = 100000, queries = 1000000, key size = 20
> [trie]
> Average lookup time = 17.0 ns
> [radix_tree]
> Average lookup time = 217.4 ns
>
> keys = 1000000, queries = 1000000, key size = 20
> [trie]
> Average lookup time = 17.0 ns
> [radix_tree]
> Average lookup time = 462.3 ns
>
> keys = 10000000, queries = 1000000, key size = 20
> [trie]
> Average lookup time = 17.3 ns
> [radix_tree]
> Average lookup time = 722.6 ns
>
>
> _______________________________________________
> zeromq-dev mailing list
> zeromq-dev at lists.zeromq.org
> https://lists.zeromq.org/mailman/listinfo/zeromq-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.zeromq.org/pipermail/zeromq-dev/attachments/20231114/8ec2fe4e/attachment.htm>


More information about the zeromq-dev mailing list