March 2, 2009
5:37 a.m.
Jim Jewett wrote:
how often will there be long chains,
My suspicion is not very often. The timing tests I did suggest that the biggest benefit will be from simply removing most of the delegation overhead from a single level of delegation, and you don't need any fancy algorithm for that. My experiments with traversing binary trees suggest that the delegation overhead isn't all that great a problem until the tree is about 20 levels deep, or 1e6 nodes. Even then it doesn't exactly kill you, but even so, my naive implementation shows a clear improvement. -- Greg