You Won’t Believe This One Weird CPU Instruction!
summary
Popcnt counts set bits and ends up as the core primitive across surprising places: compute Hamming weight and Hamming distance with XOR + popcnt to measure errors, design codes with at least a three-bit distance for single-bit correction, accelerate binary convolutional neural nets with XNOR + popcnt for matrix multiplies on phones and routers, represent chess bitboards and molecular fingerprints compactly, and enable succinct rank/select structures. Historical note: CDC 6000 uses 60-bit words and compilers (GCC 9.1, clang 3.7) auto-replace naive implementations.
AI-written summary · about
chapters (19)
- 0:00Intro
- 0:18What is PopCon
- 0:42Is it useful
- 1:02The NSA instruction
- 1:53Why would NSA need this instruction
- 2:27The conspiracy theory
- 2:56Error correction
- 3:25Data comparison
- 3:38Error recovery
- 3:57Binary convolutional
- 4:11Whats convolutional
- 4:23Why convolutional
- 4:56Matrix multiplication
- 5:17Bitboard representation
- 5:34Molecular fingerprinting
- 5:46Hash array map trees
- 6:16Data structures
- 6:44Compiler Explorer
- 7:24Outro
related talks
33mCPU Hardware Counters
01h 04mBranchless Programming in C++
46m.NET Intrinsics in CoreCLR 3.0
24mAdvanced SIMD Algorithms in Pictures
43mUnlock the Power of Parallel Computing With SWAR (SIMD Within A Register)
01h 03mInstruction Level Parallelism and Software Performance
05mBinary in JavaScript
58mOptimization Tips - Mo' Hustle Mo' Problems