Hi Bhavin, > * If developing something like a chat server or a pub-sub server where > topics are domain names (us...@domain.com, us...@domain.com) this > optimization may help if the string were to be reversed (moc.nia...@1resu) > possibly and interestingly increasing the number of single-branch nodes at > the top of the tree as opposed to only at the bottom :). Infact in general > topic strings could be created in a manner so as to utilize this > optimization
Good point. > * I obviously haven't thought through this structure as much as you have - > but why the "limit" in terms of the number of characters stored at that node > (say 8). Why not store as many characters as represent no branching. The > moment another topic comes in that needs to branch out at a particular > place, then the split could be made at that time. This could increase > insertion complexity, but insertion is a one time activity. I might be > missing something obvious. You are not missing anything. The only rationale I have is that variable length string would require a dynamic allocation which by itself uses some memory (chunk header, say 24 bytes). By limiting the number of character to something like 8 we can store it directly in the node structure with no additional allocation required. Ultimately it's a trade-off: We'll have to allocate a new node for each 8 characters in the topic, however, we'll spare 24 bytes per node. 8 character limit algorithm would thus have best if the unbranched sequences of characters are mostly up to 8 characters long. I believe that's the case in most scenarios. > * I can share my experience here. We had done a ton of tests concerning > optimization of a similar data structure w.r.t DNS caches. In all our tests > the difference in performance was of the order of double-digits when the > memory structure could be stored in the CPU Cache vs RAM. Thanks for proving my point! :) Martin _______________________________________________ zeromq-dev mailing list zeromq-dev@lists.zeromq.org http://lists.zeromq.org/mailman/listinfo/zeromq-dev
