Loading…
CppCon 2019 has ended
Thursday, September 19 • 15:15 - 16:15
How C++ Beats All Other Languages at Card Games: Using Integers as Arrays of Bitfields a.k.a. SWAR Techniques

Log in to save this to your schedule and see who's attending!

Many applications, including card games, may achieve large speedups by treating 64-bit integers as arrays of bitfields and processing all of their elements with simple processor instructions. This is called "SWAR", which stands for "SIMD Within A Register", or using bit-wise and integer instructions for multiple bitfields within a processor register.

SWAR techniques are described mostly in the HAKMEM memos and the "Hacker's Delight" book. However, in the absence of real, illustrative applications, it is difficult to learn how to use them and capitalize on their potential for large speedups. For example, normal 52-card deck games have 13 ranks, representing each group of four cards of a rank as a bitfield element in a SWAR vector we can achieve, compared to the serial equivalent, 13x speedups for things such as detecting four-of-a-kind. Here we will show many practical uses of SWAR techniques that were organized as a SIMD (Single Instruction Multiple Data) library to help make an artificial intelligence engine for card games.

We will talk about:
1. known and potentially original SWAR techniques,
2. how we packaged them in a library used to calculate "equities" of hands of cards in the game of Poker,
3. the benchmarks that prove this library performs better than other popular solutions

And we will focus throughout on how C++ 11 and more modern help: Instead of having to do lots of very error-prone busy work as in other languages, C++ has zero-performance-cost Generic Programming abstractions that allow us to get clean and easy to reason about code while keeping top performance; also, there are many techniques that accomplish the same things, but have different cost profiles that can be evaluated with benchmarking and the powers of Generic Programming also make it very easy to reconfigure the choices to incorporate benchmark knowledge.

Speakers
avatar for Eduardo Madrid

Eduardo Madrid

Software Engineer Lead, Snapchat
Eduardo has been working for many years on financial technologies, automated trading in particular, and other areas where performance challenges can be solved in C++. He contributes to open source projects and teaches advanced courses on Software Engineering with emphasis in Generic... Read More →


Thursday September 19, 2019 15:15 - 16:15
Summit 4/5

Attendees (146)




Twitter Feed