[bdr]

This is cool. remove() was a bottleneck for my app, but a constant-fraction speedup won't be enough to fix it. I'll have to dig in and see if it actually works differently now.

[jeresig]

Constant fraction? It's a 4x speedup - that seems like more than enough to help you out!

[bdr]

Well it was taking like 20 seconds to do my cleanup. Five seconds still sucks for users. IIRC, remove has to recurse to every child to check for stored data, so I'm just removing the nodes manually and eating the tiny data memory leak.

edit: and yes, 4x is a constant fraction, as opposed to an asymptotic improvement. :)

[jeresig]

Actually, we did reduce the complexity to a constant: Went from n^2 to just n: http://ejohn.org/blog/function-call-profiling/

The 4x number was wall-clock time for the particular tests - so obviously your mileage may vary. In fact, the more complicated your case the better your eventual gains will be.

[bdr]

Great link, thanks. Looking at the patch I can now why it's n^2 -- I didn't realize it was that bad when I looked at the code before.

[seasoup]

That's a constant fractions... 16/4. :)