Using Integers as Arrays of Bitfields a.k.a. SWAR Techniques
summary
A C++11 library implements SWAR (treating 64-bit words as arrays of bitfields) to brute-force Texas Hold’em equities and it actually classifies ~2 billion opponent/community combos in ~18 seconds — about 114 million classifications/sec or ~26 cycles per hand. Techniques: masks, shifts, element-wise subtraction to get booleans, recursive bitwise population-count logic (competes with popcnt via compiler auto-vectorization), and a next subset routine (213 ops). Design avoids huge lookup tables and proves practical, high-throughput speed.
AI-written summary · about
chapters (14)
- 0:00Introduction to techniques
- 1:30SIMD and architecture
- 2:44SWAR techniques explained
- 6:00Benefits of SWAR
- 10:13Poker simulation case study
- 15:18C++ and SWAR integration
- 19:10Detecting three of a kind
- 23:21Bit manipulation strategies
- 26:41Vertical vs horizontal ops
- 30:16Implementing hand logic
- 34:29Population count techniques
- 38:22Compiler optimization analysis
- 44:23Advanced algorithms
- 46:57Conclusion and Q&A
related talks
01h 21mCPU optimized data structures - more fun with assembler
01h 08mFrom Numerical Cosmology to Efficient Bit Abstractions for the Standard Library
57mAdventures in SIMD-Thinking (part 1 of 2)
01h 01mWhat’s In A Bit – Designing, Using And Reverse-engineering Binary File Formats
01h 01mAdventures in SIMD-Thinking (part 2 of 2)
01h 03mCompute More in Less Time Using C++ Simd Wrapper Libraries
53mFun with Flags - C++ Type-safe Bitwise Operations
30m“Esoteric Data Structures and Where to Find Them”