9 ms·

Your friend might be wasting a lot of effort (apart from his personal learning experience), as Phil Bagwell is working on Scala's collection library.

arohner 16y ago
For context to "outsiders": Bagwell wrote the papers that the Clojure datastructures are based on.
KirinDave 16y ago
“A lot of effort?” Wrapping the PersistentMaps took like less than 200 lines of code: http://github.com/codahale/yoink http://github.com/codahale/yoink
- Artemidoros 16y ago
  Yes, 'a lot' is quite relative. :-) From my point of view 200 LoC giving me something I already have is a lot. From the point of view of your friend 200 LoC might be a very small price to pay for a good learning experience.
  - KirinDave 16y ago
    The back of your hand is going to get sore with all those compliments.
    - Artemidoros 16y ago
      I did not have the intention of backhanding you or your friend. If my post had the appearance of doing so, I apologize. I just wanted to point out the (for me at least) non obvious fact that the mind behind the theory of Clojure's persistent datastructures is working on Scala's collection library and that Scala's hash maps are already backed by hash tries - http://www.scala-lang.org/archives/downloads/distrib/files/nightly/docs/library/scala/collection/immutable/HashMap.html http://www.scala-lang.org/archives/downloads/distrib/files/n...
      - KirinDave 16y ago
        Good for Scala. When it's ready, people can use that. Until then, there are interim solutions. And it's pretty neat to see a scala proponent call a scala project a "waste of time." Way to represent for your community, bro.
  - codahale 16y ago
    I invite you to benchmark the two. I'm also slightly confused as to why you think reusing stable, proven, and reviewed data structure implementations is a "good learning experience" as opposed to being SOP.
    - Artemidoros 16y ago
      scala.collection.immutable is/will not be stable, proven and reviewed?
      - codahale 16y ago
        The hash array mapped trie was committed to trunk 3 months ago and was first released in 2.8.0.RC1 (which no one uses due to various bugs) and is now available in 2.8.0.RC2 (which very few people are using due to binary incompatibility). In contrast, Clojure's PersistentHashMap dates back to 2007 and was in both the 1.0 and 1.1.0 releases.
        Artemidoros 16y ago
        Is it unreasonable to expect that Scala's persistent collections will work comparably to Closure's when 2.8 final is released?
        codahale 16y ago
        That doesn't sound unreasonable, no -- at some point in the future, Scala's hash array mapped trie will be robust and highly optimized. If your plan is to wait until then, you might be able to speed things up by helping them out yourself. In the meantime, I benchmarked Yoink's PeristentHashMap against 2.8.0.RC2's immutable.HashMap by a) creating a map of 100,000 sequential keys and then removing them all, and b) creating a map of 100,000 random keys and then removing 100,000 random keys. In the first case, Yoink was 20.7041% (±1.83693%) faster. In the second case, Yoink was 24.7834% (±4.17055%) faster. (Student's t distribution, 95% confidence interval, source is in src/test on the GitHub project and I used ministat for the statistical analysis [a cross-platform port of which is also available on my GitHub page].) So to summarize, I have a provably faster hash array mapped trie at almost zero cost right now because I spent a few hours with a "good learning experience."

arohner 16y ago

For context to "outsiders": Bagwell wrote the papers that the Clojure datastructures are based on.

KirinDave 16y ago

“A lot of effort?” Wrapping the PersistentMaps took like less than 200 lines of code: http://github.com/codahale/yoink http://github.com/codahale/yoink

Artemidoros 16y ago
Yes, 'a lot' is quite relative. :-) From my point of view 200 LoC giving me something I already have is a lot. From the point of view of your friend 200 LoC might be a very small price to pay for a good learning experience.
- KirinDave 16y ago
  The back of your hand is going to get sore with all those compliments.
  - Artemidoros 16y ago
    I did not have the intention of backhanding you or your friend. If my post had the appearance of doing so, I apologize. I just wanted to point out the (for me at least) non obvious fact that the mind behind the theory of Clojure's persistent datastructures is working on Scala's collection library and that Scala's hash maps are already backed by hash tries - http://www.scala-lang.org/archives/downloads/distrib/files/nightly/docs/library/scala/collection/immutable/HashMap.html http://www.scala-lang.org/archives/downloads/distrib/files/n...
    - KirinDave 16y ago
      Good for Scala. When it's ready, people can use that. Until then, there are interim solutions. And it's pretty neat to see a scala proponent call a scala project a "waste of time." Way to represent for your community, bro.
- codahale 16y ago
  I invite you to benchmark the two. I'm also slightly confused as to why you think reusing stable, proven, and reviewed data structure implementations is a "good learning experience" as opposed to being SOP.
  - Artemidoros 16y ago
    scala.collection.immutable is/will not be stable, proven and reviewed?
    - codahale 16y ago
      The hash array mapped trie was committed to trunk 3 months ago and was first released in 2.8.0.RC1 (which no one uses due to various bugs) and is now available in 2.8.0.RC2 (which very few people are using due to binary incompatibility). In contrast, Clojure's PersistentHashMap dates back to 2007 and was in both the 1.0 and 1.1.0 releases.
      - Artemidoros 16y ago
        Is it unreasonable to expect that Scala's persistent collections will work comparably to Closure's when 2.8 final is released?
        codahale 16y ago
        That doesn't sound unreasonable, no -- at some point in the future, Scala's hash array mapped trie will be robust and highly optimized. If your plan is to wait until then, you might be able to speed things up by helping them out yourself. In the meantime, I benchmarked Yoink's PeristentHashMap against 2.8.0.RC2's immutable.HashMap by a) creating a map of 100,000 sequential keys and then removing them all, and b) creating a map of 100,000 random keys and then removing 100,000 random keys. In the first case, Yoink was 20.7041% (±1.83693%) faster. In the second case, Yoink was 24.7834% (±4.17055%) faster. (Student's t distribution, 95% confidence interval, source is in src/test on the GitHub project and I used ministat for the statistical analysis [a cross-platform port of which is also available on my GitHub page].) So to summarize, I have a provably faster hash array mapped trie at almost zero cost right now because I spent a few hours with a "good learning experience."