CppCon 2017: Phil Nash “The Holy Grail! A Hash Array Mapped Trie for C++”

—
—
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 at some of the performance characteristics.
—
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++.
—

*-----*
*-----*

[JiveDadson]

Sorry, but "try" and "tree" are already taken.

[razzlfraz]

Kind of a let down that he showed worse case insertion performance, instead of better insertion performance by inserting to the non-persistent variation using std::move, like the Postmodern Immutable Data Structures talk did. (Great talk btw.)

[sandeeprajakrishnan]

Please someone help me find this presentation that he is showing, its urgent

[kamalabuhenamostafa]

"VERY FUNNY" ACTUALLY the TEACHING STYLE may termed as " a NASTY TRICK of hiding own competence".