Hacker News Reader

Comment by fiatmoney | Hacker News Reader

I'll give a real tradeoff - persistent datastructures are much less efficient to iterate through, since they usually involve a) returning "mutated" copies at each iteration (not as bad as it sounds due to structural sharing, but much more expensive than incrementing an index) and b) lots of pointer following & manipulation.

Also, the STM has an interesting intersection with garbage collection depending on your access patterns. Returning modified copies & throwing away references to the old one, rather than mutating, can increase pressure on the GC since you end up with more transient objects. Especially if you're "mutating" objects that all end up living in the tenured generation.

View on HN

persistent datastructures are much less efficient to iterate through

As far as Clojure iteration is concerned, Vectors (immutable, persistent) are actually faster than ArrayLists (mutable, unsynchronized). Criterium reports:

  (let [v (vec (range 10000))] (bench (reduce + v)))
  
  Evaluation count : 95340 in 60 samples of 1589 calls.
               Execution time mean : 642.508722 µs
      Execution time std-deviation : 5.452816 µs
     Execution time lower quantile : 636.188082 µs ( 2.5%)
     Execution time upper quantile : 658.023220 µs (97.5%)

  (let [a (java.util.ArrayList. (range 10000))]
    (bench (reduce + a)))

  Evaluation count : 77640 in 60 samples of 1294 calls.
               Execution time mean : 739.523157 µs
      Execution time std-deviation : 6.064187 µs
     Execution time lower quantile : 730.818794 µs ( 2.5%)
     Execution time upper quantile : 751.968107 µs (97.5%)

Amusingly, using iterators directly instead of reduce speeds up ArrayLists (since there's no need to go through seq, I think), and slows down Vectors to the same speed:

  (defn iterator-sum
    [^java.util.Iterator i]
    (loop [sum 0]
      (if (.hasNext i)
        (recur (+ sum (.next i)))
        sum)))
  
  (defn iterable-sum
    [^Iterable i]
    (iterator-sum (.iterator i)))
  
  (let [v (vec (range 10000))]
    (bench (iterable-sum v))))
  Execution time mean : 682.147166 µs

  (let [a (java.util.ArrayList. (range 10000))]
    (bench (iterable-sum a))))
  Execution time mean : 683.351808 µs

After conferring with ztellman, I suspect this is due to Clojure's InternalReduce avoiding extra iterator allocations over vectors, since it can recur f directly over the internal array at each leaf node.

For those of you playing along at home, this is because of Clojure's reducers framework [1]. If we were to extend 'clojure.core.protocols.CollReduce' to ArrayList, we'd get similar performance, but the important point is that efficient iteration across immutable collections is very much possible.

http://clojure.com/blog/2012/05/08/reducers-a-library-and-mo...

EDIT: and my response is just a little redundant now

Are you sure? Reducers framework has its own version of major functions (map, reduce, etc.) and has to be called explicitly by use or require. Last time I checked, in version 1.5, if you just call normal reduce, it does not use reducers framework.

there were changes to the core data structures in order to support reducers, namely the addition of polymorphic reduction by the collection. See: https://github.com/clojure/clojure/commit/5b281880571573c591...

It was a pretty transparent change.

Yes, having to understand the details and implications of clojure's compilation was definitely painful, but the implementing code is accessible. There's always going to be some performance bottlenecks, I guess I'm more concerned with how hard are they to identify and overcome than they might have been having coded stuff up in pure java from the start? Or, once you're committed to a design, say refs and STM, and you hit such a problem, is it difficult to change course?

Why does the iteration have to return copies? Can it not just return the object itself? Or are you talking about return-by-value versus return-by-reference (Java does the latter)?

Immutability means that if you're "modifying" the structure you must actually be "making a new copy with a small change". Structural sharing means that usually only the small change itself gets new allocation, but it's still more pointer-chasing than a continuous memory map.

Lots of algorithms don't work with this kind of copying semantics, but you have all of Purely Functional Data Structures [1] to help.

[1] http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...

Fair enough, but I wasn't talking about modification, I asked about iteration.

Just iterating doesn't make any copies. Replace iterating over with modifying.

Efficient immmutable data structures are easily one of Clojure best features. Easiest trade off ever (though the actual hit to performance isn't that bad) imo.

Not only that, but you can also make a persistent structure locally transient for the duration of the (modifying) iteration, so in lots of cases you do not have to pay the persistence penalty.

Oh, true—I jumped his point

It doesn't. I suspect the parent was thinking of mutation.

I should clarify: "iteration" is a bit of a fuzzy concept in Clojure that encompasses things like "for", "reduce", "some", "map", etc., some of which have differing implementations under the hood. If you're leveraging InternalReduce you're likely to be pretty darn efficient, especially because under the hood it's allowed to multithread with Java fork/join (which you would have to implement much more verbosely if you wanted to use it with an ArrayList). But in a lot of cases, you scan through a collection by taking the first element, then the first of the rest (which is generated by returning a "modified" copy of the original collection), etc.

See for instance, the "some" implementation: https://github.com/clojure/clojure/blob/c6756a8bab137128c811...

> I'll give a real tradeoff - persistent datastructures are much less efficient to iterate through

Pretty sure you mean "mutation", because none of your criticisms makes sense for iteration of persistent datastructures in general (the former one makes no sense at all, the latter one may make sense in tree-based persistent datastructures which will have higher constant factors due to pointer chasing)

If you're constantly returning and saving modified immutable data structures you're doing it wrong. Clojure has mutable data, you use them when you need them, and don't use them when you don't.

Reply on news.ycombinator.com