CHAMP an improvement on HAMT?

[Alexander Hudek]

I figured this would end up here eventually, so may as well cross post from HN:

https://michael.steindorfer.name/publications/phd-thesis-efficient-immutable-collections.pdf

It directly compares to and improves on Clojure's HAMT based data structures. 

[Didier]

I think that paper is from 2015. Curious to hear what are people's thoughts as to why it didn't replace Clojure's HAMT. I wouldn't mind a free 3x performance boost and a reduced memory footprint. Is it just a matter of didn't have someone doing the work, or did it turn out that there was issues with CHAMP that would prevent Clojure's default core data structures from being migrated to it?

[Timothy Baldridge]

It came up today in the Clojurian's Slack mailing list, and it sounds like the gist is that the papers did a bit of a apples-to-oranges comparison by using a different hashing algorithm when comparing CHAMP to Clojure's hashmaps. Once this difference is rectified the performance improvements are much smaller, if they exist at all. Apparently CHAMP uses less memory, and that might be a reason to switch, but I think the efforts to integrate CHAMP mostly died when the fixed benchmarks failed to show significant performance gains. 

On Mon, Aug 14, 2017 at 3:00 AM, Didier <did...@gmail.com> wrote:

I think that paper is from 2015. Curious to hear what are people's thoughts as to why it didn't replace Clojure's HAMT. I wouldn't mind a free 3x performance boost and a reduced memory footprint. Is it just a matter of didn't have someone doing the work, or did it turn out that there was issues with CHAMP that would prevent Clojure's default core data structures from being migrated to it?

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+unsubscribe@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

“One of the main causes of the fall of the Roman Empire was that–lacking zero–they had no way to indicate successful termination of their C programs.”
(Robert Firth)

[Colin Fleming]

Previous discussion from Zach Tellman about his CHAMP implementation (bifurcan): https://groups.google.com/d/topic/clojure/1m_I7IrDGb0/discussion

It seems that Clojure's hashing and in particular equality semantics are relatively expensive, and this accounts for most of the performance difference. Zach's implementation does offer some advantages (faster iteration, lower memory usage and some improved operations specific to each data structure) but if you're stuck with Clojure's hashing and equality the gains are not as significant.