[ANN] An exploration of Hash Array Mapped Tries

203 views
Skip to first unread message

Ambrose Bonnaire-Sergeant

unread,
Dec 6, 2016, 4:16:52 PM12/6/16
to clojure
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

unread,
Dec 6, 2016, 4:29:44 PM12/6/16
to clo...@googlegroups.com
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

unread,
Dec 6, 2016, 4:32:29 PM12/6/16
to clojure

Yehonathan Sharvit

unread,
Dec 6, 2016, 10:41:41 PM12/6/16
to Clojure, abonnair...@gmail.com
Looks good stuff.
Would be very nice to port to cljs.
Then you could have a very compelling demo in the browser.

Colin Fleming

unread,
Dec 9, 2016, 4:16:58 PM12/9/16
to clo...@googlegroups.com
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

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.
Reply all
Reply to author
Forward
0 new messages