3 ms·

> Are you saying this in spite of the existing implementation of decent persistent data structures, at least in some languages? No, s/he's saying that because

by tomp 11y ago

> Are you saying this in spite of the existing implementation of decent persistent data structures, at least in some languages? No, s/he's saying that because of the existing implementations of decent persistent data structures. Practically all of them allocate way more than mutable data structures - e.g. trie-based vectors/arrays, trie-base hashmaps, tree-based ordered maps, etc. Essentially each new addition, modification or removal results in one or more allocations.

sanderjd 11y ago
Also, those allocations imply linked, rather than contiguous, data structures, which (often? always?) imply poor cache interaction, which is a major source of inefficiency. Would love some more perspectives on this, as I've just watched a couple cppcon talks ([0], [1]) and I'm feeling a bit drunk on the kool-aid. [0]: https://www.youtube.com/watch?v=fHNmRkzxHWs https://www.youtube.com/watch?v=fHNmRkzxHWs [1]: https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc
- kqr 11y ago
  There are data structures that are a combination of linked and contiguous, such as the classic rope data structure. For persistent collections, a common backing data structure is the hash array mapped trie, which is basically a quickly-navigated tree of arrays. Somewhere in there is the obvious tradeoff you have to make between access time and copying time, with regards to the array length.
  - sanderjd 11y ago
    Thanks for the info, I didn't realize the connection between hash array mapped tries and persistent collections. Are you aware of any open source (ie. linkable) implementations that work that way?
    - tomp 11y ago
      Clojure [1] - the crucial implementation is really in classes BitmapIndexedNode and ArrayNode. Scala [2] - Scala's source is an incredibly convoluted spaghetti of abstract classes and traits, but it looks like the main bits of implementation is in methods get0 and updated0 of HashTrieMap. There's also a C# implementation somewhere, but it's not a part of a language library, so it's likely less optimized (except for some boxing/reified generics, which make it theoretically more efficient). But all these implementations use the same basic algorithm, so it's irrelevant which one you study. [1] https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java https://github.com/clojure/clojure/blob/master/src/jvm/cloju... [2] https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/immutable/HashMap.scala https://github.com/scala/scala/blob/2.11.x/src/library/scala...
      - sanderjd 11y ago
        Wow, thanks for doing the leg work for me. This is the type of thing that reminds me why the internet is so wonderful :)
    - kqr 11y ago
      Sure, the [unordered-containers](https://github.com/tibbe/unordered-containers https://github.com/tibbe/unordered-containers) library is based on that IIRC, as is the [hash map in Clojure](https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java https://github.com/clojure/clojure/blob/master/src/jvm/cloju...).

by tomp 11y ago

sanderjd 11y ago

Also, those allocations imply linked, rather than contiguous, data structures, which (often? always?) imply poor cache interaction, which is a major source of inefficiency. Would love some more perspectives on this, as I've just watched a couple cppcon talks ([0], [1]) and I'm feeling a bit drunk on the kool-aid. [0]: https://www.youtube.com/watch?v=fHNmRkzxHWs https://www.youtube.com/watch?v=fHNmRkzxHWs [1]: https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc

kqr 11y ago
There are data structures that are a combination of linked and contiguous, such as the classic rope data structure. For persistent collections, a common backing data structure is the hash array mapped trie, which is basically a quickly-navigated tree of arrays. Somewhere in there is the obvious tradeoff you have to make between access time and copying time, with regards to the array length.
- sanderjd 11y ago
  Thanks for the info, I didn't realize the connection between hash array mapped tries and persistent collections. Are you aware of any open source (ie. linkable) implementations that work that way?
  - tomp 11y ago
    Clojure [1] - the crucial implementation is really in classes BitmapIndexedNode and ArrayNode. Scala [2] - Scala's source is an incredibly convoluted spaghetti of abstract classes and traits, but it looks like the main bits of implementation is in methods get0 and updated0 of HashTrieMap. There's also a C# implementation somewhere, but it's not a part of a language library, so it's likely less optimized (except for some boxing/reified generics, which make it theoretically more efficient). But all these implementations use the same basic algorithm, so it's irrelevant which one you study. [1] https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java https://github.com/clojure/clojure/blob/master/src/jvm/cloju... [2] https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/immutable/HashMap.scala https://github.com/scala/scala/blob/2.11.x/src/library/scala...
    - sanderjd 11y ago
      Wow, thanks for doing the leg work for me. This is the type of thing that reminds me why the internet is so wonderful :)
  - kqr 11y ago
    Sure, the [unordered-containers](https://github.com/tibbe/unordered-containers https://github.com/tibbe/unordered-containers) library is based on that IIRC, as is the [hash map in Clojure](https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java https://github.com/clojure/clojure/blob/master/src/jvm/cloju...).