CppCon 2016: Christiaan Pretorius “Cache Optimized Hash Tables”

—
—
Hashes and caches, why another hash library ?
Problems,shortcomings and advantages of current open source hash libraries. Includes split between open and closed addressing methods and how these can be combined to give a better solution without much trade off by exploiting the strengths of each.

Benchmarks
Benchmarks of the library with high and medium entropy data, mostly pictures.

Analogies
A short description of the algorithms employed and why they work. This will include a short history of the library and why certain design decisions where made. Use of the birthday problem to model the low memory use evident from the benchmarks.

Practical uses
Demonstrate use cases of the library in treestore MySQL storage engine. Uses include concurrent version control algorithms and a mostly lock free allocation pool. This will include a short session with facebook link bench to illuminate possible advantages.
—
Christiaan Pretorius
Technical Lead, Retro Rabbit
—

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

[origamibulldoser]

Is this what a coffeescript developer looks like?

[TheMmmoser]

i did not quite understand 'rabbit linear probing' and how the 'collided key' is solving clustering with linear hashing (somewhere around 24:00). Did anybody get that?

[TheDuckofDoom.]

The 1.25-1.5x speed tip made the audio reasonable, but the presenter seemed to have super scattered train of thought, I had a hard time following. The subject is not one of my strengths, maybe somebody that is already well versed in the subject could follow well enough to get some useful insights.

[gregorybuckareff]

1.25x is an excellent speed. 1.5x is for those who are really jetting