5 ms·
Clojure devs: 3.5 is the figure you are looking for, and it does look very good, at first glance.
by devrandomguy 9y ago
Clojure devs: 3.5 is the figure you are looking for, and it does look very good, at first glance.
- emsimot 9y agoDid you mean "3.6 Benchmarks: CHAMP versus Clojure’s and Scala’s HAMTs"? "Speedups Compared to Clojure’s Maps: In every runtime measurement CHAMP is better than Clojure. CHAMP improves by a median 72 % for Lookup, 24 % for Insert, and 32 % for Delete. At iteration and equality checking, CHAMP significantly outperforms Clojure. Iteration (Key) improves by a median 83 %, and Iteration (Entry) by 73 %. Further, CHAMP improves on Equality (Distinct) by a median 96 %, and scores several magnitudes better at Equality (Derived). Speedups Compared to Clojure’s Sets: The speedups of CHAMP for sets are similar to maps across the board, with exception of insertion and deletion where it scores even better." Interesting indeed!
- amelius 9y agoNice results, but in the old days, algorithms improved on other algorithms in the big-O sense.
- kristianp 9y agoA lot more low-hanging fruit in the old days.
- anarazel 9y agoRight, which is why nobody ever used qsort. Or, wait. It's been widely used for a long time...
- amelius 9y agoWell, I didn't say "worst case". If qsort only provided a constant ratio time improvement over bubble sort in the average case, then it wouldn't have been so popular.
- kcorbitt 9y agoActually, big-O complexity by definition is determined based on the worst case. https://stackoverflow.com/questions/3230122/big-oh-vs-big-theta https://stackoverflow.com/questions/3230122/big-oh-vs-big-th...
- anarazel 9y agoSure, you can point to algorithms that nobody experienced ever uses. But if you e.g. compare qsort usage with heapsort usage, people use qsort because of it's better constant factors, even though the worst case complexity is worse.
- Johnny_Brahms 9y agoIf asymptotic performance was everything, we would all be using Fibonacci heaps. In reality other things matter.
- spektom 9y agoThis paper was published back in 2015: https://michael.steindorfer.name/publications/oopsla15.pdf https://michael.steindorfer.name/publications/oopsla15.pdf I wonder why the improvement wasn't adopted yet by the Clojure and Scala communities.
- loopingoptimism 9y agoAdoption (especially in industry) takes time, but there's definitely interest in the Clojure and Scala communities. The CHAMP data structure was already picked up by the ClojureScript community (https://github.com/bendyworks/lean-map https://github.com/bendyworks/lean-map), but still requires some work to be upstreamed to Clojure I guess. I personally (I'm the author of the thesis linked above) plan to work together with the Scala folks at Lightbend for the collections overhaul that's planned for Scala 2.13 (see https://github.com/scala/collection-strawman https://github.com/scala/collection-strawman).
- jabl 9y agoAny idea about CHAMP and Haskell? IIRC the reception of HAMT was somewhat lukewarm back in the day, and AFAIK to this day the Haskell standard library doesn't use them.
- loopingoptimism 9y agoI do not know well the current state of HAMT data structures in Haskell, but there is a related thread at the Haskell subreddit that you might be interested in: https://www.reddit.com/r/haskell/comments/6tmbju/efficient_immutable_collections_pdf/ https://www.reddit.com/r/haskell/comments/6tmbju/efficient_i...
- prospero 9y agoThe lookup performance gain is largely due to the CHAMP implementation using the default Java equality semantics, while Clojure's maps use Clojure's more expensive equality semantics. See https://github.com/lacuna/bifurcan/blob/master/doc/benchmarks.md#maps https://github.com/lacuna/bifurcan/blob/master/doc/benchmark... for a more in depth illustration of this. However, it is still a meaningful incremental improvement over Clojure's implementation for iteration and equality checks, among others.