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.

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.
  - capableweb 5y ago
    You seem to be missing the point lukashrb made regarding using Java data structures. Your claim was "It's inherent. Clojure will always be slow" which is demonstrable false as you can use interop with your host language (Java, JavaScript, Erlang) to use data structure that don't suffer from this. Wrap how you're using them in Clojure functions and the usage code for this is idiomatic while also having cache friendly data structures.
    - MillenialMan 5y ago
      I understand the point, I'm not arguing that you can't do that or speed up your code by doing that. Python is also slow, but you can still go fast (in some cases) by calling into C libraries like numpy - but the performance is coming from C, not Python. Python is still slow, it's just not an issue because you're only using it for plumbing. But Clojure is immutable-by-default, that's the point of the language - it gives you various guarantees so you don't have to worry about mutability bubbling up from lower levels. In order to wrap your heavy path you have to go outside the Clojure structure and sacrifice that guarantee. You do lose structural integrity when you do that, even if you attempt to insulate your mutable structure. The system loses some provability.
      - pjmlp 5y ago
        I have learned to embrace polyglot programming instead of trying to use the same language for every possible scenario. Personally I see this language X is better than Y at Z a waste of time, because I would just use X and Y depending on what I have to do.
        MillenialMan 5y ago
        In general I would agree, but a significant part of Clojure's appeal is that it's immutable by default, because that allows you to make certain assumptions about the codebase. Introducing mutable datastructures means you can no longer make those assumptions, so it potentially has much wider ramifications than e.g. calling into C code from Python.
      - 5y ago
  - 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.
gpderetta 5y ago
Partially unrolled node based data structures could help. Does clojure use them?
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.
    - 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 :)
        5y ago
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
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.
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)
fulafel 5y ago
A traditional hash table can also be pretty cache unfriendly. I wonder if there are any published measurements that compare these.

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.
- capableweb 5y ago
  You seem to be missing the point lukashrb made regarding using Java data structures. Your claim was "It's inherent. Clojure will always be slow" which is demonstrable false as you can use interop with your host language (Java, JavaScript, Erlang) to use data structure that don't suffer from this. Wrap how you're using them in Clojure functions and the usage code for this is idiomatic while also having cache friendly data structures.
  - MillenialMan 5y ago
    I understand the point, I'm not arguing that you can't do that or speed up your code by doing that. Python is also slow, but you can still go fast (in some cases) by calling into C libraries like numpy - but the performance is coming from C, not Python. Python is still slow, it's just not an issue because you're only using it for plumbing. But Clojure is immutable-by-default, that's the point of the language - it gives you various guarantees so you don't have to worry about mutability bubbling up from lower levels. In order to wrap your heavy path you have to go outside the Clojure structure and sacrifice that guarantee. You do lose structural integrity when you do that, even if you attempt to insulate your mutable structure. The system loses some provability.
    - pjmlp 5y ago
      I have learned to embrace polyglot programming instead of trying to use the same language for every possible scenario. Personally I see this language X is better than Y at Z a waste of time, because I would just use X and Y depending on what I have to do.
      - MillenialMan 5y ago
        In general I would agree, but a significant part of Clojure's appeal is that it's immutable by default, because that allows you to make certain assumptions about the codebase. Introducing mutable datastructures means you can no longer make those assumptions, so it potentially has much wider ramifications than e.g. calling into C code from Python.
    - 5y ago
- 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.

gpderetta 5y ago

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

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.
  - 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 :)
      - 5y ago

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

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.

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)

fulafel 5y ago

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