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