To Trie or not to Trie

Have you ever thought about what exactly happens when you subscribe for a topic using SUB socket? The messages have to be checked and those not matching the subscription(s) have to be dropped.

Currently, matching is done using an N-ary search tree, a structure known as trie.

Searching a trie is very fast. The search time is independent of overall number of topics or number of subscriptions. It's linearly dependent only on the length of the topic string in the message being matched. However, with large number of subscriptions the trie can consume more memory than alternative search structures such as hash table. Larger memory usage means that memory cache misses happen more often and slow the algorithm down.

Bhavin Turakhia did a research on trie optimisation and blogged about it.

Read more....