This event has ended. View the official site or create your own event → Check it out
This event has ended. Create your own
View analytic
Friday, May 19 • 4:30pm - 6:00pm
The Holy Grail - A Hash Array Mapped Trie for C++

Log in to save this to your schedule and see who's attending!

Feedback form is now closed.
C++ has a handful of associative containers. We started with set and map, both based on node-based red-black trees. These are fine but are not the most efficient and, in particular, suffer from more cache misses than we’d like. If we want to build persistent versions of them it’s achievable but aggravates the problems even more and adds considerable extra complexity (I know - I’ve done it!)

C++11 brought the hash-map based unordered_set and unordered_map, which are generally much faster, with better cache locality - but can be less memory efficient and also don’t translate so easily into persistent versions.

But there exists another general purpose data structure that combines many of the characteristics of trees and hash tables into something that in many important ways is superior to both, and with minimal downside (they are close but not quite as fast as pure hash tables). Hash Array Mapped Tries are more memory efficient than hash tables and, as a bonus, are trivially made persistent - with big implications for concurrency, functional programming, and other applications that benefit from being able to treat them immutably (as well as share large amounts of common state in memory at once).

This talk will describe how this data structure works from the ground up and look at a reference implementation I am writing with the intention of proposing as a boost library - and possibly later for standardisation. We’ll also look at how it can be used in practice, and some of the performance characteristics.

avatar for Phil Nash

Phil Nash

Developer Advocate, JetBrains
I'm the author of the test framework, Catch, and also have feet in the Swift and F# worlds. | As Developer Advocate at JetBrains I'm involved with CLion, AppCode and ReSharper C++.

Friday May 19, 2017 4:30pm - 6:00pm
Hudson Commons

Attendees (36)