[CLJS-299] PersistentVector push-tail, do-assoc, pop-tail should not contain recursive calls Created: 04/Jun/12 Updated: 29/Jul/13
|Reporter:||David Nolen||Assignee:||Michał Marczyk|
This prevents V8 inlining. Lazlo's earlier experiments seemed to suggest ~30% gain.
|Comment by Michał Marczyk [ 15/Aug/12 6:17 AM ]|
Here's a patch which eliminates recursion in all the fns mentioned in the ticket name.
I haven't done much in the way of measuring the impact on perf; a naive benchmark of (assoc huge-vector 123 :foo) seems to indicate a modest perf gain (a few percent shaved off the runtime).
Note that whether pop-tail as implemented in this patch is an improvement over the previous version is not that clear, since it needs to precalculate the level at which the main loop should terminate. Careful measurements will be necessary. (I wouldn't be surprised if the difference turned out to be unmeasurable, in which case I guess we needn't bother with the change.)
push-tail and do-assoc have no such problems – all the work being done needs to be done (and is now done in a non-recursive fashion).
Hm... Actually that probably means this patch should be split in two (pop-tail & rest). I'll get around to that soon.
More importantly, some benchmarks for large data structures should be added (assoc / conj of 32 items (at any rate, a large enough number of items for the tail to be pushed in) / repeated pops (again, enough to pop the tail)). ("Large" here means "large enough for the shift of the vector to grow at least to 10", meaning size > 1024 + 32; shift 15 would be better, requiring size > 32768 + 32.)
|Comment by David Nolen [ 17/Aug/12 12:36 AM ]|
Awesome! Lets split the patch in two.
|Comment by Michał Marczyk [ 17/Aug/12 4:23 AM ]|
Ok. Here's a new patch which eliminates recursion in push-tail and do-assoc. I guess the large data structure benchmarks should probably get in first – see
I'll give pop-tail a little more thought and write a new patch for it sometime soon too. (Perhaps worth pointing out is that the zlvl precalculation in the current version of the pop-tail patch doesn't need to traverse any nodes – it's all bit twiddling – so it should be pretty cheap... I guess we'll see what the benchmarks say – I haven't actually ran them on this code yet.)
|Comment by David Nolen [ 29/Aug/12 8:44 PM ]|
So how did the benchmarks turn out for these?
|Comment by David Nolen [ 31/Aug/12 9:04 AM ]|
I applied and ran these benchmarks using the lasted V8. These don't seem to make any difference. Perhaps V8 no longer has issues with the recursive cases? I didn't test beyond running the benchmark script. Might be worth getting something up on JSPerf.