[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.