On Fri, Jan 14, 2011 at 6:04 AM, Ross Paterson
On Fri, Jan 14, 2011 at 11:58:18AM +0100, Johan Tibell wrote:
...[Ross couldn't speed things up easily.]
I think the problem is that you get almost 2x allocation. O(log n) allocation to create the Path and O(log n) allocation to rebuild the tree. Perhaps one could use continuations to create the whole instead of reifying the stack as a Path? We might lose the ability to get the smaller/larger elements but at least we might be able to update the "hole" efficiently?
That's essentially apfelmus's original suggestion. I believe I tried that but creating the closures seems even slower.
Er, yes, the proposed data structure defunctionalizes these continuations (which in principle also lets us manipulate them more flexibly). Remember that a closure (especially a complex continuation) is *also* a data structure, folks! -Jan