Keith, you rock. I love Beanstalk for many reasons, certainly its simplicity and ease-of-use. That being said, I would love some introspection abilities. I have read your earlier posts about how introspection and speed can be mutually exclusive, so I am aware of the trade-offs. But still, having better introspection abilities would be a great missing feature.
Thus, if you do this test implementation and your benchmarks show it comparable to the existing hashtable approach then I welcome my new radix tree overlords. Keep up the great work! Thanks /Cody On Tue, May 4, 2010 at 3:40 PM, Keith Rarick <[email protected]> wrote: > 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. > > -- 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.
