<< Back to previous view

[CLJS-453] ArrayVector for small vectors Created: 04/Jan/13  Updated: 02/Dec/14  Resolved: 02/Dec/14

Status: Closed
Project: ClojureScript
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Jozef Wagner Assignee: Unassigned
Resolution: Declined Votes: 0
Labels: None
Environment:

master cljs, chrome


Attachments: Text File 0001-ArrayVector-New-vector-implementation-for-small-vect.patch    

 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



 Comments   
Comment by David Nolen [ 04/Jan/13 4:54 PM ]

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

Comment by Jozef Wagner [ 19/Jul/13 1:09 PM ]

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.

Comment by David Nolen [ 23/Jul/13 1:02 PM ]

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.

Comment by MichaƂ Marczyk [ 23/Jul/13 9:27 PM ]

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.

Comment by David Nolen [ 16/Nov/13 11:38 PM ]

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.

Comment by David Nolen [ 17/Nov/13 12:00 PM ]

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.

Comment by Jozef Wagner [ 19/Nov/13 3:47 AM ]

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.

Comment by David Nolen [ 19/Nov/13 11:03 AM ]

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.

Comment by David Nolen [ 02/Dec/14 6:19 AM ]

I believe Zach Tellman's proposal for tuples will likely land and be the approach we adopt.

Generated at Fri Dec 19 04:14:13 CST 2014 using JIRA 4.4#649-r158309.