ClojureScript

PersistentVector push-tail, do-assoc, pop-tail should not contain recursive calls

Details

  • Type: Enhancement Enhancement
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None

Description

This prevents V8 inlining. Lazlo's earlier experiments seemed to suggest ~30% gain.

Activity

Hide
David Nolen added a comment -

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.

Show
David Nolen added a comment - 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.
Hide
David Nolen added a comment -

So how did the benchmarks turn out for these?

Show
David Nolen added a comment - So how did the benchmarks turn out for these?
Hide
Michał Marczyk added a comment -

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 CLJS-357 (some benchmarks already attached – could use some scrutiny in case they're not exercising what they should be; initial runs indicate a very modest speedup).

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

Show
Michał Marczyk added a comment - 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 CLJS-357 (some benchmarks already attached – could use some scrutiny in case they're not exercising what they should be; initial runs indicate a very modest speedup). 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.)
Hide
David Nolen added a comment -

Awesome! Lets split the patch in two.

Show
David Nolen added a comment - Awesome! Lets split the patch in two.
Hide
Michał Marczyk added a comment -

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

Show
Michał Marczyk added a comment - 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.)

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated: