5 ms·
On a related note, cache alignment is one of the reasons Clojure's vectors (log32 insertion, access, and deletion) and linked lists (o(index) insertion, access,
by aphyr 13y ago
On a related note, cache alignment is one of the reasons Clojure's vectors (log32 insertion, access, and deletion) and linked lists (o(index) insertion, access, and deletion) have unintuitive performance characteristics. For instance, constructing lists of either type takes roughly the same amount of time for big lists:
user=> (with-progress-reporting (bench (into '() (range 100000))))
Execution time mean : 9.293932 ms
Execution time std-deviation : 269.771284 µs
user=> (with-progress-reporting (bench (into [] (range 100000))))
Execution time mean : 9.882163 ms
Execution time std-deviation : 359.744662 µs
And with smaller lists, building vectors is ~30-50% slower.
user=> (with-progress-reporting (bench (into '() (range 24))))
Execution time mean : 2.483705 µs
Execution time std-deviation : 71.302962 ns
user=> (with-progress-reporting (bench (into [] (range 24))))
Execution time mean : 3.349080 µs
Execution time std-deviation : 114.007930 ns
However, traversal is significantly faster for vectors, because you can pack 32 references into a cache line at a time. Here's a decent-sized list:
user=> (let [x (apply list (range 100000))] (bench (reduce + x)))
Execution time mean : 8.586510 ms
Execution time std-deviation : 80.923357 µs
Vs a comparable vector:
user=> (let [x (vec (range 100000))] (bench (reduce + x)))
Execution time mean : 4.564553 ms
Execution time std-deviation : 135.795328 µs
Traversing small lists:
user=> (let [x (apply list (range 24))] (bench (reduce + x)))
Execution time mean : 2.041794 µs
Execution time std-deviation : 18.752533 ns
Vs small vectors:
user=> (let [x (vec (range 24))] (bench (reduce + x)))
Execution time mean : 1.051182 µs
Execution time std-deviation : 10.413211 ns
http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/ http://blog.higher-order.net/2009/02/01/understanding-clojur...
- gtani 13y agoBenchmarking on the JVM is tricky, beyond pure algorithmic efficiency (assuming all memory accesses are equal), there's cache effects, JVM heap and GC effects and the usual warmup/inlining concerns of benchmarking. On page 551 of the excellent scala staircase book (2nd edition[1]) there's a collection efficiency table w.r.t. head/tail/indexing/insert, but that's a jumping off point (sorry, I can't find an online version of the table). [1] http://www.artima.com/shop/programming_in_scala_2ed http://www.artima.com/shop/programming_in_scala_2ed
- happy_dino 13y agohttp://docs.scala-lang.org/overviews/collections/performance-characteristics.html http://docs.scala-lang.org/overviews/collections/performance...
- aphyr 13y agoThese benchmarks were taken with Criterium, which performs JIT warming, GC purge, final GC, retains results for each run, isolates outliers, etc.