Advanced Topics in Programming Languages: A Lock-Free Hash Table

Channel:GoogleTalksArchive · Length:58:35 · Published:2012-08-22 · Views:29135

Watch on YouTube

Summary

A 2007 Google Tech Talk in which Cliff Click of Azul Systems presents a lock-free concurrent hash table that scales to 768 CPUs. He explains why it is correct by reasoning in a different way than usual happens-before and memory-order arguments.

Why HN recommends it

HN regards it as one of the best technical talks, a deep and clear walkthrough of scalable lock-free hash tables built on compare-and-swap.

I highly recommend this talk by Cliff Click about building highly scalable hash tables via Compare And Swap — HN, 2024

Software performance & optimization · Distributed systems · Algorithms & data structures

Subtitles (excerpt)

welcome to the latest in our series of talks on programming languages um today we have a very special guest star a uh a man who works across the street at Azul on uh computers that have many many processors he uh he formerly worked at Sun where he was one of the chief architects of the hotspot VM um and he is doing some very similar work at UH at aul and uh he's here to talk to us today about his experiences creating a lock free hash table um for Java that scales very well um his name is Cliff click and this is he thanks so um just to show that I'm only sort of not too far behind the time I actually have a Blog now I started a week ago this is how fast I end up moving with with things here so I'm going to talk today about about two things about hash tables and about um a different way of thinking about concurrent algorithms um and and and I'm going to start with the hashtable piece um and I assume everyone here knows what a hashtable is but maybe I can I can throw in a few extra things that maybe you haven't thought about okay so the obvious thing is it's a constant time key value mapping sort of by by definition right um but from a a a key value mapping you can build arbitrary functions out of it and they're extendable they're defined at

On Hacker News

For folks interested in this topic I highly recommend this talk by Cliff Click about building highly scalable hash tables via Compare And Swap: [VIDEO] — benreesman, 2024-09
Probably this one: [VIDEO] Anything from Cliff Click is quite good. This guy has a very deep understanding of compilers, virtual-machines, CPUs, and their interactions. A JVM does that? [LINK] Java on a 1000 Cores [LINK] — qznc, 2013-04
It's worth noting that for a lot of people for a long time, Intel TSO was the memory model in practice (which IIRC makes `std::memory_order_seq_cst` pretty much free on Intel). Many clothes have been torn and many teeth gnashed porting C++ from Intel to more relaxed architectures. Back in the day that usually meant like SPARC, today that usually means ARM. "Acquire" and "Release" are relatively c… — benreesman, 2022-08
I've always admired the wizardry of Cliff Click's concurrent hash: [LINK] [VIDEO] I'm not sure what to make of an "atomic" hash. I don't think OP does as well: "Doesn't this kind of defeat the point of concurrent algorithms? Well, in a sense, it does make it non-atomic, but it isn't really a spin-lock or anything like that, even though it can seem like that:" Concurrent hash seems to be more corr… — eternalban, 2017-05
Dr. Cliff Click's Google talk on Lock-Free Hashtable is here: [VIDEO] Acc to Dr. Click, if you do not have 30+ CPUs in a single machine, ConcurrentHashMap (built-in to the JDK) will do the trick more often than not. The talk is really worth it, if you're curious about the design, esp. Dr. Click also had memorable debate with Rich Hickey over STMs. He works at h2o.ai and wrote about building a Key… — ignoramous, 2016-02

Related videos