hash table

Matt Kulukundis explains how Google designed SwissTable, a fast, cache-friendly hash table, step by step from std::unordered_map. The talk covers open addressing, SIMD probing and the tradeoffs of changing a fundamental data structure.

Malte Skarupke's C++Now 2018 talk on hash table performance, explaining why std::unordered_map is slow and memory hungry and presenting faster designs, including his bytell hash map.

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.

Matt Kulukundis reviews two years of Abseil's Swiss table hashtable, covering post-release optimizations, lessons from rolling it out across Google, design choices, and what global monitoring revealed.

Lee Byron of Facebook explains how persistent immutable data structures work and how to use them in React apps with Immutable.js. He covers memoization benefits and avoiding coupling through shared mutable state.

Juan Pedro Bolivar Puente explains immutable and persistent data structures in C++ and how they support value semantics. He presents the Immer library, rrb-trees, and a prototype text editor that opens a huge file instantly.

Python core developer Raymond Hettinger explains how Python's dictionary implementation evolved into the compact, ordered dict in Python 3.6. He uses pictures and small bits of pure Python, and covers key-sharing, compaction and versioning.

Tom7 explains how he built a SIGBOVIK 2017 paper made only of printable ASCII bytes that is also a valid DOS executable. He writes a C compiler targeting printable x86 without self-modifying code and solves the puzzles the constraint creates.

Nina Teicholz, author of The Big Fat Surprise, speaks at Low Carb Gold Coast 2017 about the history and health implications of vegetable and seed oils. She covers the political and institutional forces behind dietary fat advice.

Shashi Tharoor's Oxford Union speech arguing that Britain owes reparations to its former colonies, focused on the effects of British rule in India. It lists economic and political damage done by colonialism.

Justine Tunney presents Redbean, a web server distributed as a single actually portable executable that runs on multiple operating systems. It embeds Lua, SQLite and MbedTLS in a fork-based server.

Aaron Hsu shows how to manipulate and transform tree data in APL using arrays and inverted tables instead of pointers. He claims much smaller code, better performance and easier parallelisation.

Chandler Carruth's CppCon 2014 talk on writing fast C++, explaining why data structure choice and memory layout matter more than clever algorithms. It covers why standard containers like unordered_map perform poorly on modern CPUs.

A JuliaCon 2016 talk by Shashi Gowda showing an APL implementation in Julia. APL code is translated to Julia and JIT compiled to machine code.

Richard Feldman's elm-conf talk on designing models so that bugs from impossible application states cannot occur, using Elm's compiler and types. It demonstrates techniques for making invalid states unrepresentable.

Rich Hickey's JaxConf 2012 keynote examines what values are and why immutable values matter as information systems grow more complex and data gets bigger. It contrasts places with values and builds the case for immutability.

Martin Kleppmann argues that databases are global shared mutable state and proposes treating them as an ever-growing log of immutable facts. Derived data such as caches, indexes and views is then built by stream processors like Apache Samza. The talk draws on Kafka and LinkedIn's experience with commit logs.

Paul Chiusano's Strange Loop 2019 talk introduces Unison, an open-source functional language for distributed, elastic systems. It covers content-addressed code identified by hashes of the syntax tree, a codebase manager, and algebraic effects called abilities.

Cardiologist James O'Keefe argues in a TEDx talk that moderate running confers the best longevity benefits, while extreme endurance training can damage the heart. He draws on data and his own experience as a lifelong runner.

David Nolen presents Om Next, the redesign of the ClojureScript Om library, drawing on Relay, Netflix's JSONGraph and Datomic. He covers the tradeoffs in handling the client-server boundary over immutable data.

Bobby Powers presents Mesh, a drop-in malloc replacement that eliminates memory fragmentation in unmodified C/C++ programs by compacting memory. The talk covers how it works despite C's fixed object addresses, and its benefits for programs like Redis.

Mobileye co-founder and CTO Amnon Shashua explains what goes into sensing for autonomous driving and whether end-to-end deep learning can work for it. He argues for decomposing the problem.

David Nolen reviews the first five years of ClojureScript, documenting its landmarks and looking ahead to the next five. It is a history-and-roadmap talk from the Clojure community.

Andrei Alexandrescu's CppCon 2019 talk revisits sorting, showing how branchless tricks, hybrid strategies and a cost metric can speed up std::sort-style algorithms on modern hardware.

James Long's dotJS 2019 talk on how CRDTs enable local-first apps and how simple they can be to implement. He shows how to use them to build robust offline-capable frontends.

Guy Steele presents a small geometric problem and compares four computational approaches: a classic sequential solution and three parallel-friendly ones. Each is illustrated pictorially and with working code, weighing total work against time to solution.

Martin Kleppmann's QCon London 2018 talk on keeping data consistent in distributed systems without a central leader. It surveys CRDT algorithms for syncing devices and collaborative editing over peer-to-peer networks.

A JSConf 2014 talk visually breaking down algorithms behind everyday UI patterns, such as dropdown menus that vanish when the mouse drifts and picking the nearest target to the cursor. It shows how these are implemented in JavaScript.

Sean Parent's CppCon 2015 talk on better use of standard containers and the goal of having no incidental data structures. It argues that proper containers can greatly simplify code.

Redis Labs and Tim Davis present RedisGraph, which uses GraphBLAS to treat graph queries in Cypher as sparse linear algebra for lower latency.

Stephan T. Lavavej's CppCon 2019 talk on implementing floating-point to_chars and from_chars in Microsoft's C++ STL. It covers the history of float-string conversion and the algorithms that make it much faster.

Elasticsearch engineer and Lucene committer Adrien Grand explains the design decisions inside a Lucene index and what problems it can and cannot solve. The talk goes into how Lucene stores data for fast search and analytics.

Martin Kleppmann surveys current research on CRDTs, the algorithms for merging concurrent edits across offline replicas. He covers the hard parts such as rich text, moves and merge results that are technically correct but poor.

Bryan Cantrill presents the ARC (Adaptive Replacement Cache) paper by Megiddo and Modha at Papers We Love. He opens with a survey of caching strategies before digging into the self-tuning LRU/MFU design.

Neil Fraser of Google presents Differential Synchronization, the algorithm behind MobWrite, for keeping multiple copies of a document in sync in real time. The talk argues the approach is robust, convergent and efficient.

Daniel Lemire's QCon talk on how simdjson parses gigabytes of JSON per second. It covers SIMD vectorization, branch prediction and the lessons learned building a fast parser.

Jon Bentley walks through three implementations of Hoare's Quicksort, from a dozen-line C function to a series of systematic code transformations that make the program ever simpler and more powerful. It is a Google Tech Talk on code elegance and program derivation.

A Microsoft Research talk on BetrFS, a file system built on B-epsilon trees, a write-optimized data structure. It covers WODS such as LSM-trees, how to design a file system around them, and benchmark wins over ext4 and xfs.

Andrei Alexandrescu's ACCU 2016 talk previews material from his book on writing fast code, with a focus on optimization techniques such as sentinels and faster search.

Edward Kmett's 2013 talk at Prezi in Budapest on succinct data structures, which store data in close to the information-theoretic minimum space while supporting fast queries. It ties together the research and walks through his Haskell succinct library.