ClojureScript

ArrayVector for small vectors

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
  • Environment:
    master cljs, chrome

Description

Just like we have an ArrayMap for small maps, I propose to have an ArrayVector for small vectors.

Use cases:

  • pair of values, e.g. coordinates, triples and other tuple values
  • returning multiple values from a function and subsequent destructuring in a caller fn

ArrayVector has 100x faster vector creation compared to PersistentVector.
With an ^ArrayVector hint, it offers more than 10x faster destructuring. Without it, it is still about 40% faster.

Example of such destructuring:

(defn foo [a b] 
  [(+ a b) (- a b) (* a b)])

(defn bar []
  (let [[plus minus times] ^ArrayVector (foo 1 2)]
    (str "bla bla" plus "blaah" minus)))

I've attached a patch with complete implementation of such vector, supporting all basic functionalities as well as transients. This patch also replaces default vector implementation with ArrayVector, falling back to PersistentVector for large vectors.

ArrayVector implementation can also be found at array-vec branch at https://github.com/wagjo/clojurescript/tree/array-vec

Activity

Hide
David Nolen added a comment -

Thanks! This interesting, it would be helpful to see a more comprehensive set of benchmarks on jsperf.com.

Show
David Nolen added a comment - Thanks! This interesting, it would be helpful to see a more comprehensive set of benchmarks on jsperf.com.
Hide
Jozef Wagner added a comment - - edited

I have prepared benchmarks for ArrayVector. One is at http://jsperf.com/cljs-arrayvector/2 and the other one is at http://wagjo.github.io/benchmark-cljs/ . Note that both benchmarks use same code, at https://github.com/wagjo/benchmark-cljs and use advanced compilation and bleeding edge ClojureScript.

Results on my linux machine in chrome are following:

Results for benchmark small-vector/create for 10000 iterations, median from 300 runs
000.031ms - baseline
000.128ms - array
000.396ms - array vector
000.878ms - persistent vector

Results for benchmark small-vector/access for 10000 iterations, median from 50 runs
000.044ms - baseline
000.244ms - array
000.930ms - array vector
001.110ms - persistent vector
000.254ms - destructure array vector
001.224ms - destructure persistent vector

Results for benchmark small-vector/conj for 10000 iterations, median from 100 runs
000.035ms - baseline
001.193ms - array
001.794ms - array vector
002.119ms - persistent vector

Edit: Table is updated with more precise data.

Show
Jozef Wagner added a comment - - edited I have prepared benchmarks for ArrayVector. One is at http://jsperf.com/cljs-arrayvector/2 and the other one is at http://wagjo.github.io/benchmark-cljs/ . Note that both benchmarks use same code, at https://github.com/wagjo/benchmark-cljs and use advanced compilation and bleeding edge ClojureScript. Results on my linux machine in chrome are following:
Results for benchmark small-vector/create for 10000 iterations, median from 300 runs 000.031ms - baseline 000.128ms - array 000.396ms - array vector 000.878ms - persistent vector Results for benchmark small-vector/access for 10000 iterations, median from 50 runs 000.044ms - baseline 000.244ms - array 000.930ms - array vector 001.110ms - persistent vector 000.254ms - destructure array vector 001.224ms - destructure persistent vector Results for benchmark small-vector/conj for 10000 iterations, median from 100 runs 000.035ms - baseline 001.193ms - array 001.794ms - array vector 002.119ms - persistent vector
Edit: Table is updated with more precise data.
Hide
David Nolen added a comment -

These are interesting results, will look into this some more. I will say that type hinting like that is not officially supported, ^not-native is experimental but more likely to be something we allow.

Show
David Nolen added a comment - These are interesting results, will look into this some more. I will say that type hinting like that is not officially supported, ^not-native is experimental but more likely to be something we allow.
Hide
Michał Marczyk added a comment -

If I understand correctly, the benefit in destructuring ArrayVector}}s comes from directly accessing the underlying array. We could do the same with short PVs if this "shortness" information could be conveyed through a type hint. Not saying that we necessarily should, though there might be an upside with hinting {{^shortvec rather than ^ArrayVector from a semantic POV (hinting a property vs. hinting implementation).

In any case, I suppose there would be very nearly no cost to introducing a separate AV type (conj beyond 32 elements would simply do exactly what it does right now; conj! needs to allocate a new TV, but the cost should be acceptable), so, if it speeds things up...

I'll run some experiments and get back to this ticket with further comments.

Show
Michał Marczyk added a comment - If I understand correctly, the benefit in destructuring ArrayVector}}s comes from directly accessing the underlying array. We could do the same with short PVs if this "shortness" information could be conveyed through a type hint. Not saying that we necessarily should, though there might be an upside with hinting {{^shortvec rather than ^ArrayVector from a semantic POV (hinting a property vs. hinting implementation). In any case, I suppose there would be very nearly no cost to introducing a separate AV type (conj beyond 32 elements would simply do exactly what it does right now; conj! needs to allocate a new TV, but the cost should be acceptable), so, if it speeds things up... I'll run some experiments and get back to this ticket with further comments.
Hide
David Nolen added a comment -

I'm not excited about more type hints I've landed a performance improvement for conj, PVs run circles around AVs now. PV construction time can be made competitive with AV construction time trivially by making the compiler inline instantiation.

This leaves lookup time, I wonder if we could close the gap? It would be nice to rerun the benchmarks after we land some more PV enhancements.

Show
David Nolen added a comment - I'm not excited about more type hints I've landed a performance improvement for conj, PVs run circles around AVs now. PV construction time can be made competitive with AV construction time trivially by making the compiler inline instantiation. This leaves lookup time, I wonder if we could close the gap? It would be nice to rerun the benchmarks after we land some more PV enhancements.
Hide
David Nolen added a comment -

PersistentVector creation time is now nearly as fast as ArrayVector in master. -nth is still a bit slower under V8, but surprisingly under WebKit Nightly PVs appear to outperform AVs here.

Show
David Nolen added a comment - PersistentVector creation time is now nearly as fast as ArrayVector in master. -nth is still a bit slower under V8, but surprisingly under WebKit Nightly PVs appear to outperform AVs here.
Hide
Jozef Wagner added a comment -

Thank you. I've updated the benchmarks which confirm that PV are now on par with AV in terms of creation and conjoining. The lookup time optimization boils down to this core, which can be changed to support PVs too.

Show
Jozef Wagner added a comment - Thank you. I've updated the benchmarks which confirm that PV are now on par with AV in terms of creation and conjoining. The lookup time optimization boils down to this core, which can be changed to support PVs too.
Hide
David Nolen added a comment -

We're not going to add special cases like that. It's in the works to add more inference to the compiler so that protocol backed fns will inline more simply with less hinting.

Show
David Nolen added a comment - We're not going to add special cases like that. It's in the works to add more inference to the compiler so that protocol backed fns will inline more simply with less hinting.

People

Vote (0)
Watch (4)

Dates

  • Created:
    Updated: