[ANN] An exploration of Hash Array Mapped Tries

[Ambrose Bonnaire-Sergeant]

Hi,

I've been having a ton of fun this semester learning about

Hash Array Mapped Tries (like PersistentHashMap).

Link

I have written a visual tutorial for HAMT's, as well

as a reference implementation in Clojure that supports

trie visualisations with Rhizome.

There's also a little prototype+writeup of an idea I had about

generating defrecords at runtime based on the frequency

of certain keysets at runtime.

Enjoy!

Ambrose

[Colin Yates]

The "Link" doesn't seem to be working for me (it isn't actually a
link). Is this some sort of gateway tested - if you aren't clever
enough to figure it out you don't deserve to get in? ;-).

On 6 December 2016 at 21:16, Ambrose Bonnaire-Sergeant

> --
> 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+u...@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+u...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Ambrose Bonnaire-Sergeant]

Link: https://github.com/frenchy64/optimized-kw-maps

[Yehonathan Sharvit]

Looks good stuff.

Would be very nice to port to cljs.

Then you could have a very compelling demo in the browser.

[Colin Fleming]

Hi Ambrose,

This looks very interesting, and I look forward to investigating it further when I have a moment.

Once comment on the defrecords generated at runtime based on small keysets - I'd be very careful with this sort of optimisation, and it needs much more than micro-benchmarks to establish whether it's really a win or not. A recent similar change that was proposed for Clojure was Zach Tellman's unrolled small collections (see CLJ-1517, in particular see Rich's comment here). Essentially, the JVM optimises call sites speculatively. Per call site, if you only see a single implementation of the interface you're calling, the site is monomorphic and very highly optimised. If two implementations are seen, the site is bimorphic, and optimised but not as highly. If more than two implementations are seen, the call site is considered megamorphic and is optimised poorly. Additionally, the optimisations that are applied can depend on the order in which the different implementations are seen, which can produce extremely unpredictable performance.

There's a very interesting issue on the Google Guava tracker with tons of really interesting detail by people who know way more about this than I do. It's highly recommended. The tl;dr is that your benchmarks must mix collection types to measure benefit, and that those benchmarks are extremely difficult to relate to real-world use.

Since reading all that, I've often wondered how much Clojure's PersistentArrayMap might affect performance since it will probably cause many call sites to be bimorphic rather than monomorphic. I could imagine it being worthwhile to have a flag which only ever uses PersistentHashMap instead for people who really understand their workload, but I have never had time to investigate it more.

Cheers,

Colin

--

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.