Migrate trie implementation to patricia trie to increase possible subscription count on a single box

[jabberfest]

In:
https://github.com/zeromq/libzmq/blob/master/src/trie.cpp
https://github.com/zeromq/libzmq/blob/master/src/mtrie.cpp

a trie is used. When subscriptions for the pub/sub protocol near several million the memory footprint on a single box becomes fairly large. The instance of ZeroMQ can become memory bound if you have a large amount of subscriptions, and not IO bound. I'm open to discussion and thoughts! nanomsg appears to have this done already.

See for additional reasoning:
http://250bpm.com/blog:19

[hintjens]

Feel free to provide a pull request, and a test case if possible.

On Sun, May 17, 2015 at 1:13 AM, jabberfest notifications@github.com
wrote:

In:
https://github.com/zeromq/libzmq/blob/master/src/trie.cpp
https://github.com/zeromq/libzmq/blob/master/src/mtrie.cpp

a trie is used. When subscriptions for the pub/sub protocol near several
million the memory footprint on a single box becomes fairly large. The
instance of ZeroMQ can become memory bound if you have a large amount of
subscriptions, and not IO bound. I'm open to discussion and thoughts!
nanomsg appears to have this done already.

See for additional reasoning:
http://250bpm.com/blog:19

—
Reply to this email directly or view it on GitHub
#1400.

[farias-r7]

My c++ is rusty, but I'll take a stab at in a couple of weeks.

@sustrik am I right in thinking that just writing a radix tree (patricia trie) implementation and swapping out the calls to trie and mtrie over to the patricia trie implementation is all I need to do? I know you no longer are involved with the project but I figured I'd ask you since you wrote the original implementation.

[ssbl]

I've written a radix tree implementation with the same API as that in trie.hpp; it's fairly well-tested and seems to work. It could potentially be a more efficient alternative to the trie libzmq currently uses.

The repository is here; just wanted to confirm before proposing a somewhat big change. It won't be the exact same code, I'll adapt it to libzmq's guidelines.

[bluca]

Have you done some performance measurement to see if there are improvements, and in which conditions? Also it needs to be C++ 98 as there are users on very old compilers

[ssbl]

I don't have any measurements yet, I'll collect some and see if there's actually an improvement in performance. Porting it to C++98 shouldn't be a problem, I think.

[ssbl]

I've added the radix tree and a simple benchmarking script to my fork of libzmq (link to commit). The script initializes both data structures with the same data, and runs a common set of queries on each. Here are the timings for running 100K queries on a data set of 10K randomly-generated keys of size 20 bytes each (times are in ms):

~/code/radix-tree/bench/libzmq/build $ bin/unittest_trie
[trie]
Starting warmup...
Collecting samples...
34.00
32.00
32.00
32.00
32.00
32.00
32.00
32.00
32.00
32.00
[radix_tree]
Starting warmup...
Collecting samples...
12.00
11.00
11.00
11.00
11.00
11.00
11.00
11.00
11.00
11.00

I couldn't figure out how to make a standalone benchmarking script, so I added it as a unit test to libzmq. Assuming that there aren't any problems with doing it this way, I've tried to make sure that the script creates a valid benchmark:

• The build passed all 107 tests run by CTest.
• Another benchmarking script using google benchmark produced similar results. Running both benchmarks (one for each data structure) together produced incorrect results for some reason; running each benchmark separately, however, produced results similar to those from the above script (12-15ms for the radix tree and 35-40ms for the trie). EDIT: It seems I was using google benchmark's PauseTiming and ResumeTiming functions incorrectly. I've fixed this and the script produces similar results: 31ms for the trie and 11ms for the radix tree.

I've also tried to measure memory usage when running the above script. Going by the output of heaptrack, the radix tree uses 1/10th of the memory used by the trie (~433KB vs ~4.3MB). Here is the full output from heaptrack: heaptrack-analyze.txt

All of the above results are from a fresh release build of my libzmq fork, so I hope the results are reproducible.

[jamesdillonharvey]

These results look really good, especially the memory usage. I have a market data system (ZMQ_PUB/SUB) where 100k subscriptions on a single publisher are not uncommon so the memory saving would be useful. My biggest issue though is on large batches of unsubscribes. Unsubscribing large numbers of subjects/topics causes the publisher to hit 100% cpu for many seconds. How is the performance of your radix tree for inserts and erases vs the trie ? Thanks

…

On Tue, Oct 23, 2018 at 3:26 PM Shubham Lagwankar ***@***.***> wrote: I've added the radix tree and a simple benchmarking script to my fork of libzmq (link to commit <ssbl@1f1cd56>). The script initializes both data structures with the same data, and runs a common set of queries on each. Here are the timings for running 100K queries on a data set of 10K randomly-generated keys of size 20 bytes each (times are in ms): ~/code/radix-tree/bench/libzmq/build $ bin/unittest_trie [trie] Starting warmup... Collecting samples... 34.00 32.00 32.00 32.00 32.00 32.00 32.00 32.00 32.00 32.00 [radix_tree] Starting warmup... Collecting samples... 12.00 11.00 11.00 11.00 11.00 11.00 11.00 11.00 11.00 11.00 I couldn't figure out how to make a standalone benchmarking script, so I added it as a unit test to libzmq. Assuming that there aren't any problems with doing it this way, I've tried to make sure that the script creates a valid benchmark: - The build passed all 107 tests run by CTest. - Another benchmarking script <https://gist.github.com/ssbl/9b4947a221518c9b8919fbd9117a000f> using google benchmark produced similar results. Running both benchmarks together produced incorrect results for some reason; running each benchmark separately, however, produced results similar to those from the above script (12-15ms for the radix tree and 35-40ms for the trie). I've also tried to measure memory usage when running the above script. Going by the output of heaptrack, the radix tree uses 1/10th of the memory used by the trie (~433KB vs ~4.3MB). Here is the full output from heaptrack: heaptrack-analyze.txt <https://github.com/zeromq/libzmq/files/2506350/heaptrack-analyze.txt> All of the above results are from a fresh release build of my libzmq fork, so I hope the results are reproducible. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1400 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ALNYGpztL9cwP_i2_7vQOnK_4tUTkx7wks5unyb5gaJpZM4EdLQt> .

[ssbl]

I've added a new benchmark to the google benchmark script which deletes 100K randomly-generated keys from the data structure. There's a greater speedup here: 114ms for the trie vs 29ms for the radix tree, although I'm not sure how closely this random dataset resembles real-world inputs.

It seems that the radix tree's lookup performance degrades slightly faster than the trie's as more keys are inserted. Here are the full results of the script with 100K keys instead of 10K:

-----------------------------------------------------------------
Benchmark                          Time           CPU Iterations
-----------------------------------------------------------------
BM_TrieLookup                     58 ms         58 ms         12
BM_RadixTreeLookup                33 ms         33 ms         21
BM_Erase<zmq::trie_t>            114 ms        114 ms          7
BM_Erase<zmq::radix_tree>         29 ms         29 ms         22

[jamesdillonharvey]

So far the radix tree has no down sides :) What about adding a test for insert performance? What happens when you reach 1M keys?

…

On Wed, Oct 24, 2018 at 2:01 PM Shubham Lagwankar ***@***.***> wrote: I've added a new benchmark to the google benchmark script <https://gist.github.com/ssbl/9b4947a221518c9b8919fbd9117a000f/d06087d33aea6af1f70aa7d6af688863f4600d92> which deletes 100K randomly-generated keys from the data structure. There's a greater speedup here: 114ms for the trie vs 29ms for the radix tree, although I'm not sure how closely this random dataset resembles real-world inputs. It seems that the radix tree's lookup performance degrades slightly faster than the trie's as more keys are inserted. Here are the full results of the script with 100K keys instead of 10K: ----------------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------------- BM_TrieLookup 58 ms 58 ms 12 BM_RadixTreeLookup 33 ms 33 ms 21 BM_Erase<zmq::trie_t> 114 ms 114 ms 7 BM_Erase<zmq::radix_tree> 29 ms 29 ms 22 — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#1400 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ALNYGmMqCWa7_b_qqZu-oKrZC6EHPWHnks5uoGS0gaJpZM4EdLQt> .

[ssbl]

I added a similar benchmark for inserts. These are the results for 100K keys:

------------------------------------------------------------------
Benchmark                           Time           CPU Iterations
------------------------------------------------------------------
BM_Lookup<zmq::trie_t>             61 ms         60 ms         12
BM_Lookup<zmq::radix_tree>         34 ms         34 ms         21
BM_Insert<zmq::trie_t>             85 ms         85 ms          8
BM_Insert<zmq::radix_tree>         38 ms         38 ms         17
BM_Erase<zmq::trie_t>             122 ms        122 ms          9
BM_Erase<zmq::radix_tree>          32 ms         32 ms         23

With 1M keys:

2018-10-24 10:50:07
Running /home/shubham/src/libzmq/buildgb/bin/unittest_trie
Run on (4 X 3200 MHz CPU s)
CPU Caches:
  L1 Data 32K (x2)
  L1 Instruction 32K (x2)
  L2 Unified 256K (x2)
  L3 Unified 3072K (x1)
------------------------------------------------------------------
Benchmark                           Time           CPU Iterations
------------------------------------------------------------------
BM_Lookup<zmq::trie_t>             90 ms         90 ms          8
BM_Lookup<zmq::radix_tree>         52 ms         52 ms         14
BM_Insert<zmq::trie_t>           1019 ms       1019 ms          1
BM_Insert<zmq::radix_tree>        506 ms        506 ms          2
BM_Erase<zmq::trie_t>            1038 ms       1038 ms          1
BM_Erase<zmq::radix_tree>         453 ms        453 ms          2

I just realized I wasn't including the initial data about the cpu and caches in previous comments; it's essentially the same for every run.

[jamesdillonharvey]

Last test I would want to add would be varying key lengths. As an example of real world data our keys vary from from 10 to 50 chars and are usually [a-Z0-9]. Other than that it looks like a great optimisation.

…

On Wed, Oct 24, 2018 at 4:08 PM Shubham Lagwankar ***@***.***> wrote: I added a similar benchmark <https://gist.github.com/ssbl/9b4947a221518c9b8919fbd9117a000f/507823c27da40b3c32ca8e9b0a6b5d2121664e46> for inserts. These are the results for 100K keys: ------------------------------------------------------------------ Benchmark Time CPU Iterations ------------------------------------------------------------------ BM_Lookup<zmq::trie_t> 61 ms 60 ms 12 BM_Lookup<zmq::radix_tree> 34 ms 34 ms 21 BM_Insert<zmq::trie_t> 85 ms 85 ms 8 BM_Insert<zmq::radix_tree> 38 ms 38 ms 17 BM_Erase<zmq::trie_t> 122 ms 122 ms 9 BM_Erase<zmq::radix_tree> 32 ms 32 ms 23 With 1M keys: 2018-10-24 10:50:07 Running /home/shubham/src/libzmq/buildgb/bin/unittest_trie Run on (4 X 3200 MHz CPU s) CPU Caches: L1 Data 32K (x2) L1 Instruction 32K (x2) L2 Unified 256K (x2) L3 Unified 3072K (x1) ------------------------------------------------------------------ Benchmark Time CPU Iterations ------------------------------------------------------------------ BM_Lookup<zmq::trie_t> 90 ms 90 ms 8 BM_Lookup<zmq::radix_tree> 52 ms 52 ms 14 BM_Insert<zmq::trie_t> 1019 ms 1019 ms 1 BM_Insert<zmq::radix_tree> 506 ms 506 ms 2 BM_Erase<zmq::trie_t> 1038 ms 1038 ms 1 BM_Erase<zmq::radix_tree> 453 ms 453 ms 2 I just realized I wasn't including the initial data about the cpu and caches in previous comments; it's essentially the same for every run. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#1400 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ALNYGuFU8F2n3Y8p-Bb7ZZ1JbhvCCkOAks5uoIJZgaJpZM4EdLQt> .