senderista

The Big OOPs: Anatomy of a 35-Year Mistake

Speaker: Casey Muratori Event: The inaugural Better Software Conference Format: Conference talk (~2 hours), followed by a Q&A with Ryan Fleury

Cleaned-up transcript. Timestamps and filler removed; sentences lightly punctuated and grouped into paragraphs; spoken wording kept close to the original. Proper names and technical terms that the auto-transcriber garbled have been corrected — e.g. Bjarne Stroustrup, Kristen Nygaard, Ole-Johan Dahl, Tony Hoare, Alan Kay, Douglas T. Ross, Ivan Sutherland, Simula, ALGOL, COBOL, Sketchpad, metaballs, Ultima Underworld, and Marc LeBlanc.

---

senderista

There are two basic algorithms I've found for building mutexes from futexes: I'll call them  "tristate" and "waiter count" based on the state they maintain in the futex word.

The "tristate" algorithm allows the futex word to be in exactly 3 states: UNLOCKED, LOCKED, LOCKED_WITH_POSSIBLE_WAITERS. It is introduced in Ulrich Drepper's 2004 paper "Futexes Are Tricky" as "mutex3":
https://dept-info.labri.fr/~denis/Enseignement/2008-IR/Articles/01-futex.pdf#page=7
The same algorithm is used for pthreads mutexes in glibc as the "low-level lock" (LLL):
https://codebrowser.dev/glibc/glibc/sysdeps/nptl/lowlevellock.h.html
https://codebrowser.dev/glibc/glibc/nptl/lowlevellock.c.html
Other languages have implemented the same algorithm for mutexes on Linux, such as Go:
https://golang.bg/src/runtime/lock_futex_tristate.go
Here is a version that adds adaptive spinning and uses byte-width atomics, storing the "locked" and "maybe_waiters" bits in separate bytes (and uses all 4 possible states instead of just 3):

senderista

// Peterson's algorithm in C++11 atomics
//
// Adapted from Dmitry Vyukov's example in the comments to https://bartoszmilewski.com/2008/12/01/c-atomics-and-memory-ordering/.
// For a correctness argument, see https://www.justsoftwaresolutions.co.uk/threading/petersons_lock_with_C++0x_atomics.html.

#include <atomic>
#include <immintrin.h>

constexpr size_t CACHE_LINE_SIZE = 64;
struct alignas(CACHE_LINE_SIZE)

senderista

#!/usr/bin/env python3

import numpy


class BinHasher64EntriesTwoChoices:

    def __init__(self, size_exp: int) -> None:
        # each bin is represented by a word-size bitvector
        self.size_exp: int = size_exp

senderista

#!/usr/bin/env python3

import numpy


class BinHasher64EntriesOneChoice:

    def __init__(self, size_exp: int) -> None:
        # each bin is represented by a word-size bitvector
        self.size_exp: int = size_exp

senderista

#!/usr/bin/env python3

import numpy


class BinHasher32EntriesTwoChoices:

    def __init__(self, size_exp: int) -> None:
        # each bin is represented by a word-size bitvector
        self.size_exp: int = size_exp

senderista

#!/usr/bin/env python3

import numpy


class BinHasher32EntriesOneChoice:

    def __init__(self, size_exp: int) -> None:
        # each bin is represented by a word-size bitvector
        self.size_exp: int = size_exp

senderista

#!/usr/bin/env python3

import numpy


class BinHasher16EntriesTwoChoices:

    def __init__(self, size_exp: int) -> None:
        # each bin is represented by a word-size bitvector
        self.size_exp: int = size_exp

senderista

#!/usr/bin/env python3

import numpy


class BinHasher16EntriesOneChoice:

    def __init__(self, size_exp: int) -> None:
        # each bin is represented by a word-size bitvector
        self.size_exp: int = size_exp

senderista

#!/usr/bin/env python3

import numpy


class BinHasher8EntriesTwoChoices:

    def __init__(self, size_exp: int) -> None:
        # each bin is represented by a byte-size bitvector
        self.size_exp: int = size_exp