I've been thinking about the possibility of using radix trees (aka crit bit trees or patricia trees) in two places in beanstalkd.
1. Replace the global job hashtable. This would give us constant-time worst-case insertion, where a hashtable only gives *amortized* constant-time insertion. 2. Replace the binary heaps. This would let us answer range queries on the ready queue, for better introspection. This prospect makes me a little sad, not for any rational reason, but just because the binary heap is such a beautiful structure. The disadvantage of a radix tree would be slightly more complex code, more memory fragmentation, worse memory access locality, and (I think) slightly slower average access times. The allocation overhead could be mitigated somewhat by keeping a free list of tree node structs. Hashtables and binary heaps are extremely simple data structures, but radix trees are only a little more complex. Nowhere near as bad as something like AVL trees or red-black trees. Once I get issue 38 fixed I'm going to do an initial implementation of this and compare the performance. If speed says comparable to what we have now, I'll go ahead and make the switch. In the meantime, if anyone has questions or comments about this, as always, chime in! kr -- You received this message because you are subscribed to the Google Groups "beanstalk-talk" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/beanstalk-talk?hl=en.
