4 ms·

Does anyone have benchmarks comparing the performance of Clojure's PersistentVectors to standard arrays in Java and/or C? O(1) is pretty useless if the constant

Does anyone have benchmarks comparing the performance of Clojure's PersistentVectors to standard arrays in Java and/or C? O(1) is pretty useless if the constant factor is huge. Anecdotally, I've heard that they are "fast" but it would be interesting to know what that really means.

PeterisP 13y ago
W/o benchmarks, but from theory - it's a rather different data structure. 1) for pure lookup-by-random-int-index, the standard array is much faster - in C you just calculate a memory location and there your data is; this structure requires, say, 4-6 such lookups depending on the array size, and is that many times slower. 2) On the other hand, iteration through large consecutive parts of the array is almost the same as pure arrays; there is some overhead but that's tiny. 3) Insertion is much faster than standard C/Java arrays - you can't really insert in the middle of an array w/o copying almost all of it, but you can do it here. 4) If you need "modification while keeping the old version as well" - then again, arrays need to make a full copy, but this beast can do it cheaply, faster than a raw C array. As for any data structures, there are no "faster data structures" since preferences greatly depend on what you want to do with them, some data structures are faster for X and others are faster for Y. The efficiency of this structure greatly depends if your array/vector is mostly used as random-access-lookup or as a list where you need to process all/many sequential items.
- deliminator 13y ago
  Clojure's standard persistent vectors don't allow insertion in the middle without copying the entire vector, they only allow fast insertion at the end. There is an alternative implementation here [1] which does allow insertion (anywhere) without copying the entire vector. [1] https://github.com/clojure/core.rrb-vector https://github.com/clojure/core.rrb-vector
pron 13y ago
This might be a little hard to compare, because, as others have said, Clojure's vectors have different goals from Java arrays, with persistence being the most important one, and the one at the core of Clojure's entire philosophy. Persistent data structures do have performance costs that are probably significant. First, each "modification" generates garbage; garbage on the JVM has different collection costs – from virtually nonexistent to quite significant – but persistent DS might generate the most expensive kind of garbage: medium-duration-lived objects. The second is caching effects. Mutable data structures reuse cache lines, while persistent DS cause cache faults and pollute the cache. Clojure's transients help with that. Of course, persistence is an essential element of Clojure's beautiful values-and-states philosophy, so you do get something extremely valuable in exchange for some performance cost. There's another issue with persistent DS: they can't be concurrently modified; they allow only one writer at a time. Clojure does support parallel modification using the very elegant reducers, but these only apply in data-parallel situations – not general concurrency.
deleted 13y ago
[deleted]
deleted 13y ago
[deleted]

PeterisP 13y ago

W/o benchmarks, but from theory - it's a rather different data structure. 1) for pure lookup-by-random-int-index, the standard array is much faster - in C you just calculate a memory location and there your data is; this structure requires, say, 4-6 such lookups depending on the array size, and is that many times slower. 2) On the other hand, iteration through large consecutive parts of the array is almost the same as pure arrays; there is some overhead but that's tiny. 3) Insertion is much faster than standard C/Java arrays - you can't really insert in the middle of an array w/o copying almost all of it, but you can do it here. 4) If you need "modification while keeping the old version as well" - then again, arrays need to make a full copy, but this beast can do it cheaply, faster than a raw C array. As for any data structures, there are no "faster data structures" since preferences greatly depend on what you want to do with them, some data structures are faster for X and others are faster for Y. The efficiency of this structure greatly depends if your array/vector is mostly used as random-access-lookup or as a list where you need to process all/many sequential items.

deliminator 13y ago
Clojure's standard persistent vectors don't allow insertion in the middle without copying the entire vector, they only allow fast insertion at the end. There is an alternative implementation here [1] which does allow insertion (anywhere) without copying the entire vector. [1] https://github.com/clojure/core.rrb-vector https://github.com/clojure/core.rrb-vector

pron 13y ago

This might be a little hard to compare, because, as others have said, Clojure's vectors have different goals from Java arrays, with persistence being the most important one, and the one at the core of Clojure's entire philosophy. Persistent data structures do have performance costs that are probably significant. First, each "modification" generates garbage; garbage on the JVM has different collection costs – from virtually nonexistent to quite significant – but persistent DS might generate the most expensive kind of garbage: medium-duration-lived objects. The second is caching effects. Mutable data structures reuse cache lines, while persistent DS cause cache faults and pollute the cache. Clojure's transients help with that. Of course, persistence is an essential element of Clojure's beautiful values-and-states philosophy, so you do get something extremely valuable in exchange for some performance cost. There's another issue with persistent DS: they can't be concurrently modified; they allow only one writer at a time. Clojure does support parallel modification using the very elegant reducers, but these only apply in data-parallel situations – not general concurrency.

deleted 13y ago

[deleted]

deleted 13y ago

[deleted]