Advanced Topics in Programming Languages: A Lock-Free Hash Table
Channel:GoogleTalksArchive · Length:58:35 · Published:2012-08-22 · Views:29135
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
- A JVM Does That? · Google TechTalks · 52:37
- Dtrace Review · GoogleTalksArchive · 1:18:02
- John Carmack Keynote - Quakecon 2013 · IGN · 2:49:18
- Java on a 1000 Cores - Tales of Hardware / Software CoDesign · Google TechTalks · 1:12:01
- AWS re:Invent 2016: Tuesday Night Live with James Hamilton · Amazon Web Services · 1:33:27
- Tracy Young Speaks at Female Founders Conference 2015 · Y Combinator · 26:51
- AWS re:Invent 2018: How AWS Minimizes the Blast Radius of Failures (ARC338) · Amazon Web Services · 55:43
- Zebras All the Way Down - Bryan Cantrill, Uptime 2017 · Code & Supply · 46:36
- Jeff Bezos 1997 Interview · Chuck Severance · 5:39
- Simulating an epidemic · 3Blue1Brown · 23:12
- Paxos lecture (Raft user study) · Diego Ongaro · 1:06:33
- Bret Victor - Inventing on Principle · Rui Oliveira · 54:20
- DNA animation (2002-2014) by Drew Berry and Etsuko Uno wehi.tv #ScienceArt · WEHImovies · 7:19
- Hey Underscore, You're Doing It Wrong! · InfoQ · 36:30
- Keynote - JSON Graph: Reactive REST at Netflix · Association for Computing Machinery (ACM) · 54:57
- AWS re:Invent 2015 | (NET403) Another Day, Another Billion Packets · Amazon Web Services · 42:25
- A Philosophy of Software Design | John Ousterhout | Talks at Google · Talks at Google · 1:01:40
- Replace Your Exploit-Ridden Firmware with Linux - Ronald Minnich, Google · The Linux Foundation · 38:02
- Bryan Cantrill on Jails and Solaris Zones · PapersWeLove · 1:45:46
- CppCon 2017: Carl Cook “When a Microsecond Is an Eternity: High Performance Trading Systems in C++” · CppCon · 1:00:07