6 ms·

The biggest performance issue Clojure has, which isn't mentioned in the article and is fundamentally unsolvable, is that it misses the CPU cache - a lot. The d

The biggest performance issue Clojure has, which isn't mentioned in the article and is fundamentally unsolvable, is that it misses the CPU cache - a lot. The data structure that drives the immutable variables, the Hash-Array Mapped Trie, is efficient in terms of time- and space- complexity, but it's incredibly CPU cache-unfriendly because by nature it's fragmented - it's not contiguous in RAM. Any operation on a HAMT will be steeped in cache misses, which slows you down by a factor of hundreds to thousands. The longer the trie has been around, the more fragmented it is likely to become. Looping over a HAMT is slower than looping over an array by two or three orders of magnitude. I don't think there is really a solution to that. It's inherent. Clojure will always be slow, because it's not cache friendly. The architecture of your computer means you physically can't speed it up without sacrificing immutability.

fulafel 5y ago
A traditional hash table can also be pretty cache unfriendly. I wonder if there are any published measurements that compare these.
jeofken 5y ago
I’m familiar with the implementation of HAMTs - if anyone wants to study one in C I recommend https://github.com/Jamesbarford/hash-array-mapped-trie https://github.com/Jamesbarford/hash-array-mapped-trie or my polymorphic fork of it https://github.com/fromheten/hash-array-mapped-trie-poly https://github.com/fromheten/hash-array-mapped-trie-poly. Are there any other key/value data structures where insertion and retrieval are less than O(n) in complexity, but where the memory layout is better ordered for cache hits during searches? Maybe good old red-black trees?
- _bsless 5y ago
  I don't think there's an immediately available answer here. The wide branch factor in Clojure's implementation is very iteration-friendly, less so for updates. Worth checking out are BTrees and Hitchhiker trees, but I think a definitive answer will be implementation dependent even in those cases, i.e. one might win out over the other for a specific branch factor or other tune-able parameters
dan-robertson 5y ago
This is entirely hypothesising but I don’t see how these wide trees are awful for the cache. In particular I don’t think they would be much worse than a flat array of objects—the problem is, I think, that objects are references and iterating the things in an array of pointers usually sucks. For a HAMT, With depth (eg) 2, you should be able to prefetch the next node in your iteration while you iterate the current node of 64 elements. Actually iterating through the objects is going to suck but hopefully you can prefetch enough of them too. (Or maybe hotspot could online things enough to improve memory access patterns a bit to take advantage of ILP). There’s still the problem that you can’t read main memory sequentially except that often all the objects in a HAMT were allocated sequentially so you can read main memory sequentially (as allocation is typically just bumping a pointer, allocation-time-locality tends to correspond to address-locality)
dgb23 5y ago
I wonder if the wide branching factor of them gives you some cache friendliness. However, not every use case can benefit from cache optimization and you can use other data structures. It’s not super useful to make generalizations about performance that way.
- j-pb 5y ago
  Yes-ish: https://db.in.tum.de/~leis/papers/ART.pdf https://db.in.tum.de/~leis/papers/ART.pdf
reitzensteinm 5y ago
While I do agree, with pointer chasing down a persistent data structure being basically the worst case use of a CPU, the ease of threading Clojure programs means you can often claw a lot of that penalty back.
- MillenialMan 5y ago
  Threading doesn't compensate for that degree of slowdown, and itself has overhead. You'll get something back, but not much.
  - reitzensteinm 5y ago
    In my experience you can usually achieve near linear speed up. My machine can run 24 threads.
    - gnuvince 5y ago
      Could you share an example program that does that?
    - MillenialMan 5y ago
      Fair enough on scaling. But 24 is still a lot less than two to three orders of magnitude.
      - reitzensteinm 5y ago
        Yes, it is. I'd probably ballpark Clojure at 100x slower than the kinds of low level C# I usually write (gamedev). But threading C#, especially low level imperative C#, is so awful I often don't bother unless it's very important or there's an embarrassingly parallel element (genetic algorithms and simulating sound waves on a 2D grid are two cases I've pulled the trigger where both were true). This leaves Clojure as 1/4 the overall speed, which seems about right. However that's based on a hugely unscientific gut feeling, because generally I don't touch Clojure if performance matters and I don't touch C# if it doesn't. By the way, I've implemented persistent data structures on disk for a problem they were particularly useful for. If stalling for a cache miss feels bad, try waiting for an SSD :)
lukashrb 5y ago
If I understand you correctly, this i a general problem of functional data structures? > Clojure will always be slow, because it's not cache friendly. You always have the option to use the java data structures, for the cases this kind of optimization is needed.
- MillenialMan 5y ago
  Yes, this is a general problem with functional data structures. They have to be fragmented in order to share data. There's also the more nebulous issue that they encourage nesting to leverage the architectural benefits of immutability, which is a complete disaster for cache friendliness. Replacing the critical path is an option, but that only works for numpy-style situations where you can cleanly isolate the computational work and detach it from the plumbing. If your app is slow because the inefficiencies have added up across the entire codebase (more common, I would argue), that's not an easy option.
  - didibus 5y ago
    > If your app is slow because the inefficiencies have added up across the entire codebase (more common, I would argue), that's not an easy option. This is where I would have to disagree, in my experience, that is less common. Generally there are specific places that are hot spots, and you can just optimize those. Could be it depends what application you are writing, I tend to write backend services and web apps, for those I've not really seen the "inefficiencies have added up", generally if you profile you'll find a few places that are your offenders. "Slow" is also very relative. (cr/quick-bench (reduce (constantly nil) times-vector)) Execution time mean : 3.985765 ms (cr/quick-bench (dotimes [i (.size times-arraylist)] (.get times-arraylist i))) Execution time mean : 775.562574 µs (cr/quick-bench (dotimes [i (alength times-array)] (aget times-array i))) Execution time mean : 590.941280 µs Yes iterating over a persistent vector of Integers is slower compared to ArrayList and Array, about 5 to 8 times slower. But for a vector of size 1000000 it only takes 4ms to do so. In Python: > python3 -m timeit "for i in range(1000000): None" 20 loops, best of 5: 12.1 msec per loop It take 12ms for example. So I would say for most uses, persistent vectors serve as a great default mix of speed and correctness.
sesm 5y ago
It is mentioned in the article, one of the last optimizations done there was switching to array. Also, Clojure’s HAMT was designed with CPU cache in mind and it’s performance characteristics don’t degrade over time. Immutable data structures will be slower than arrays - that’s true, but Clojure standard library works on arrays just fine, as demonstrated in the article.
- MillenialMan 5y ago
  You're right - I missed that, the author does mention arrays having better access characteristics, although he doesn't really explain why HAMTs specifically are slow. How does Clojure's HAMT avoid fragmenting over time? > Clojure standard library works on arrays just fine, as demonstrated in the article. Right, but then you don't have immutability - so you lose all the guarantees that you originally had with immutable-by-default.
  - _bsless 5y ago
    > although he doesn't really explain why HAMTs specifically are slow Hello, author here :) HAMTs are certainly slower, for "churning" operations, i.e., lots of updates, which is where Clojure exposes the transient API, which gives you limited localized mutability (some terms and conditions may apply) Where iteration is concerned, they standard library implementation is pretty good. It relies on chunks of 64 element arrays which store the keys and values contiguously. Thus, APIs which expose direct iteration, Iterator and IReduce(Init) operate on these chunks one at a time. It isn't as fast as primitive arrays, but it's pretty fast.
  - didibus 5y ago
    > but then you don't have immutability - so you lose all the guarantees that you originally had with immutable-by-default Not really, for example take the following solution with execution time mean : 1.678226 ms (defn smt-8''' [^ints times-arr] (loop [res (transient []) pointer-1 (int 0) pointer-2 (int 7)] (if (< pointer-2 (alength times-arr)) (let [start-element (aget times-arr pointer-1) end-element (aget times-arr pointer-2) time-diff (- end-element start-element)] (recur (if (< time-diff 1000) (conj! res [(mapv #(aget times-arr (+ pointer-1 (int %))) (range 8)) time-diff]) res) (inc pointer-1) (inc pointer-2))) (persistent! res)))) It only requires the input being an array, but it will return an immutable persistent vector of vectors. So it is very easy to selectively go down to an array in the performance critical sections while being immutable and idiomatic in most places. > he doesn't really explain why HAMTs specifically are slow Take this solution using HAMT vectors with execution time mean : 23.567174 ms (defn smt-8' [times-vec] (loop [res (transient []) pointer-1 (int 0) pointer-2 (int 7)] (if-let [end-element (get times-vec pointer-2)] (let [end-element (int end-element) start-element (int (get times-vec pointer-1)) time-diff (- end-element start-element)] (recur (if (< time-diff 1000) (conj! res [(subvec times-vec pointer-1 (inc pointer-2)) time-diff]) res) (inc pointer-1) (inc pointer-2))) (persistent! res)))) Now it is 14 times slower than my prior one which iterates over an array, but it is still pretty fast, so that's OP's point, things are often sufficiently fast, and when they are not you can selectively optimize those parts, and easily too, see how similar my two solutions are from one another. Edit: These assume you've `(set! unchecked-math true)` prior to compiling the functions.
gpderetta 5y ago
Partially unrolled node based data structures could help. Does clojure use them?

fulafel 5y ago

A traditional hash table can also be pretty cache unfriendly. I wonder if there are any published measurements that compare these.

jeofken 5y ago

I’m familiar with the implementation of HAMTs - if anyone wants to study one in C I recommend https://github.com/Jamesbarford/hash-array-mapped-trie https://github.com/Jamesbarford/hash-array-mapped-trie or my polymorphic fork of it https://github.com/fromheten/hash-array-mapped-trie-poly https://github.com/fromheten/hash-array-mapped-trie-poly. Are there any other key/value data structures where insertion and retrieval are less than O(n) in complexity, but where the memory layout is better ordered for cache hits during searches? Maybe good old red-black trees?

_bsless 5y ago
I don't think there's an immediately available answer here. The wide branch factor in Clojure's implementation is very iteration-friendly, less so for updates. Worth checking out are BTrees and Hitchhiker trees, but I think a definitive answer will be implementation dependent even in those cases, i.e. one might win out over the other for a specific branch factor or other tune-able parameters

dan-robertson 5y ago

This is entirely hypothesising but I don’t see how these wide trees are awful for the cache. In particular I don’t think they would be much worse than a flat array of objects—the problem is, I think, that objects are references and iterating the things in an array of pointers usually sucks. For a HAMT, With depth (eg) 2, you should be able to prefetch the next node in your iteration while you iterate the current node of 64 elements. Actually iterating through the objects is going to suck but hopefully you can prefetch enough of them too. (Or maybe hotspot could online things enough to improve memory access patterns a bit to take advantage of ILP). There’s still the problem that you can’t read main memory sequentially except that often all the objects in a HAMT were allocated sequentially so you can read main memory sequentially (as allocation is typically just bumping a pointer, allocation-time-locality tends to correspond to address-locality)

dgb23 5y ago

I wonder if the wide branching factor of them gives you some cache friendliness. However, not every use case can benefit from cache optimization and you can use other data structures. It’s not super useful to make generalizations about performance that way.

j-pb 5y ago
Yes-ish: https://db.in.tum.de/~leis/papers/ART.pdf https://db.in.tum.de/~leis/papers/ART.pdf

reitzensteinm 5y ago

While I do agree, with pointer chasing down a persistent data structure being basically the worst case use of a CPU, the ease of threading Clojure programs means you can often claw a lot of that penalty back.

MillenialMan 5y ago
Threading doesn't compensate for that degree of slowdown, and itself has overhead. You'll get something back, but not much.
- reitzensteinm 5y ago
  In my experience you can usually achieve near linear speed up. My machine can run 24 threads.
  - gnuvince 5y ago
    Could you share an example program that does that?
  - MillenialMan 5y ago
    Fair enough on scaling. But 24 is still a lot less than two to three orders of magnitude.
    - reitzensteinm 5y ago
      Yes, it is. I'd probably ballpark Clojure at 100x slower than the kinds of low level C# I usually write (gamedev). But threading C#, especially low level imperative C#, is so awful I often don't bother unless it's very important or there's an embarrassingly parallel element (genetic algorithms and simulating sound waves on a 2D grid are two cases I've pulled the trigger where both were true). This leaves Clojure as 1/4 the overall speed, which seems about right. However that's based on a hugely unscientific gut feeling, because generally I don't touch Clojure if performance matters and I don't touch C# if it doesn't. By the way, I've implemented persistent data structures on disk for a problem they were particularly useful for. If stalling for a cache miss feels bad, try waiting for an SSD :)

lukashrb 5y ago

If I understand you correctly, this i a general problem of functional data structures? > Clojure will always be slow, because it's not cache friendly. You always have the option to use the java data structures, for the cases this kind of optimization is needed.

MillenialMan 5y ago
Yes, this is a general problem with functional data structures. They have to be fragmented in order to share data. There's also the more nebulous issue that they encourage nesting to leverage the architectural benefits of immutability, which is a complete disaster for cache friendliness. Replacing the critical path is an option, but that only works for numpy-style situations where you can cleanly isolate the computational work and detach it from the plumbing. If your app is slow because the inefficiencies have added up across the entire codebase (more common, I would argue), that's not an easy option.
- didibus 5y ago
  > If your app is slow because the inefficiencies have added up across the entire codebase (more common, I would argue), that's not an easy option. This is where I would have to disagree, in my experience, that is less common. Generally there are specific places that are hot spots, and you can just optimize those. Could be it depends what application you are writing, I tend to write backend services and web apps, for those I've not really seen the "inefficiencies have added up", generally if you profile you'll find a few places that are your offenders. "Slow" is also very relative. (cr/quick-bench (reduce (constantly nil) times-vector)) Execution time mean : 3.985765 ms (cr/quick-bench (dotimes [i (.size times-arraylist)] (.get times-arraylist i))) Execution time mean : 775.562574 µs (cr/quick-bench (dotimes [i (alength times-array)] (aget times-array i))) Execution time mean : 590.941280 µs Yes iterating over a persistent vector of Integers is slower compared to ArrayList and Array, about 5 to 8 times slower. But for a vector of size 1000000 it only takes 4ms to do so. In Python: > python3 -m timeit "for i in range(1000000): None" 20 loops, best of 5: 12.1 msec per loop It take 12ms for example. So I would say for most uses, persistent vectors serve as a great default mix of speed and correctness.

sesm 5y ago

It is mentioned in the article, one of the last optimizations done there was switching to array. Also, Clojure’s HAMT was designed with CPU cache in mind and it’s performance characteristics don’t degrade over time. Immutable data structures will be slower than arrays - that’s true, but Clojure standard library works on arrays just fine, as demonstrated in the article.

MillenialMan 5y ago
You're right - I missed that, the author does mention arrays having better access characteristics, although he doesn't really explain why HAMTs specifically are slow. How does Clojure's HAMT avoid fragmenting over time? > Clojure standard library works on arrays just fine, as demonstrated in the article. Right, but then you don't have immutability - so you lose all the guarantees that you originally had with immutable-by-default.
- _bsless 5y ago
  > although he doesn't really explain why HAMTs specifically are slow Hello, author here :) HAMTs are certainly slower, for "churning" operations, i.e., lots of updates, which is where Clojure exposes the transient API, which gives you limited localized mutability (some terms and conditions may apply) Where iteration is concerned, they standard library implementation is pretty good. It relies on chunks of 64 element arrays which store the keys and values contiguously. Thus, APIs which expose direct iteration, Iterator and IReduce(Init) operate on these chunks one at a time. It isn't as fast as primitive arrays, but it's pretty fast.
- didibus 5y ago
  > but then you don't have immutability - so you lose all the guarantees that you originally had with immutable-by-default Not really, for example take the following solution with execution time mean : 1.678226 ms (defn smt-8''' [^ints times-arr] (loop [res (transient []) pointer-1 (int 0) pointer-2 (int 7)] (if (< pointer-2 (alength times-arr)) (let [start-element (aget times-arr pointer-1) end-element (aget times-arr pointer-2) time-diff (- end-element start-element)] (recur (if (< time-diff 1000) (conj! res [(mapv #(aget times-arr (+ pointer-1 (int %))) (range 8)) time-diff]) res) (inc pointer-1) (inc pointer-2))) (persistent! res)))) It only requires the input being an array, but it will return an immutable persistent vector of vectors. So it is very easy to selectively go down to an array in the performance critical sections while being immutable and idiomatic in most places. > he doesn't really explain why HAMTs specifically are slow Take this solution using HAMT vectors with execution time mean : 23.567174 ms (defn smt-8' [times-vec] (loop [res (transient []) pointer-1 (int 0) pointer-2 (int 7)] (if-let [end-element (get times-vec pointer-2)] (let [end-element (int end-element) start-element (int (get times-vec pointer-1)) time-diff (- end-element start-element)] (recur (if (< time-diff 1000) (conj! res [(subvec times-vec pointer-1 (inc pointer-2)) time-diff]) res) (inc pointer-1) (inc pointer-2))) (persistent! res)))) Now it is 14 times slower than my prior one which iterates over an array, but it is still pretty fast, so that's OP's point, things are often sufficiently fast, and when they are not you can selectively optimize those parts, and easily too, see how similar my two solutions are from one another. Edit: These assume you've `(set! unchecked-math true)` prior to compiling the functions.

gpderetta 5y ago

Partially unrolled node based data structures could help. Does clojure use them?