News for hackers. Stuff that matters.
Re:Efficient Immutable Collections [pdf] by devrandomguy on Sunday August 13, 2017 @10:07PM (#15006209)
Clojure devs: 3.5 is the figure you are looking for, and it does look very good, at first glance.
Re:Efficient Immutable Collections [pdf] by emsimot on Monday August 14, 2017 @02:08AM (#15006831)
Did 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!

Re:Efficient Immutable Collections [pdf] by amelius on Monday August 14, 2017 @02:33AM (#15006918)
Nice results, but in the old days, algorithms improved on other algorithms in the big-O sense.
Re:Efficient Immutable Collections [pdf] by Johnny_Brahms on Monday August 14, 2017 @06:54AM (#15007774)
If asymptotic performance was everything, we would all be using Fibonacci heaps.

In reality other things matter.

Re:Efficient Immutable Collections [pdf] by kristianp on Monday August 14, 2017 @03:20AM (#15007072)
A lot more low-hanging fruit in the old days.
Re:Efficient Immutable Collections [pdf] by anarazel on Monday August 14, 2017 @04:03AM (#15007203)
Right, which is why nobody ever used qsort. Or, wait. It's been widely used for a long time...
Re:Efficient Immutable Collections [pdf] by amelius on Monday August 14, 2017 @04:14AM (#15007232)
Well, 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.

Re:Efficient Immutable Collections [pdf] by kcorbitt on Monday August 14, 2017 @12:36PM (#15010015)
Actually, big-O complexity by definition is determined based on the worst case. https://stackoverflow.com/questions/3230122/big-oh-vs-big-th...
Re:Efficient Immutable Collections [pdf] by anarazel on Monday August 14, 2017 @02:34PM (#15011214)
Sure, 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.
Re:Efficient Immutable Collections [pdf] by prospero on Monday August 14, 2017 @03:38AM (#15007137)
The 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/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.

Re:Efficient Immutable Collections [pdf] by spektom on Monday August 14, 2017 @03:21AM (#15007078)
This paper was published back in 2015: https://michael.steindorfer.name/publications/oopsla15.pdf

I wonder why the improvement wasn't adopted yet by the Clojure and Scala communities.

Re:Efficient Immutable Collections [pdf] by loopingoptimism on Monday August 14, 2017 @08:41AM (#15008203)
Adoption (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), 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).

Re:Efficient Immutable Collections [pdf] by jabl on Tuesday August 15, 2017 @04:09AM (#15016358)
Any 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.
Re:Efficient Immutable Collections [pdf] by loopingoptimism on Wednesday August 16, 2017 @09:15AM (#15027168)
I 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_i...