Divisions entières rapides

Je me suis attaqué à un morceau plutôt amusant : en effet, j'ai eu besoin d'écrire ma propre queue circulaire à accès concurrent, avec un producteur et un consommateur - Typiquement le genre de problème que l'on désire résoudre avec un algo "lock-free". Ce n'est pas très compliqué : un atomic pour l'écriture, un atomic pour la lecture, et basta. Là où ça devient intéressant, c'est dans les différentes optimisations sur lesquelles on peut travailler.

Tout d'abord, bien penser à séparer ses atomiques, afin d'éviter le "false sharing", c'est à dire le transfer entre les caches CPUs de données qui sont indépendantes, mais proches. On utilise pour cela alignas(std::hardware_destructive_interference_size) devant nos attributs afin de bien les séparer.

Ensuite, on se rend compte que l'on a besoin à chaque lecture ou à chaque écriture de vérifier si l'on a atteint la fin du tampon circulaire pour repartir à zéro. Cela peut se faire soit avec un test, soit avec un modulo. Les deux sont plutôt chers... Heureusement, si l'on est pas trop regardant sur la taille exacte de son tampon, on peut l'arrondir à la puissance de 2 suivante, ce qui simplifie énormément les calculs : en effet, le modulo n'est alors qu'un masque...

Voici la partie intéressante du code, qui utilise std::bit_ceil pour trouver la prochaine puissance de 2, calcule le masque, et effectue l'incrément et la division modulaire

class Buffer
{
public:
    Buffer(size_t length):
        _size(std::bit_ceil(length)),
        _mask(_size - 1),
        _reader(0),
        _writer(0)
    {
    }

    void nextRead()
    {
        _reader = (_reader + 1) | _mask;
    }

    const size_t _size;
    const size_t _mask;
    alignas(std::hardware_destructive_interference_size)
    std::atomic _reader;
    alignas(std::hardware_destructive_interference_size)
    std::atomic _writer;
};

Mais la plus grande optimisation que l'on peut faire est de correctement effectuer l'ordonnancement de la mémoire, en sélectionnant memory_order_relaxed, memory_order_acquire ou memory_order_release lors des appels à store et load. La différence est très impressionnante - Un facteur 10 ou 20 dans certains benchmarks ! Je vous passe la logique exacte (en très gros, on load en memory_order_acquire, on store en memory_order_release, et pour des cas indépendants comme chercher la taille du tampon, on peut utiliser memory_order_relaxed), mais en permettant la réécriture des opérations de manière plus flexible que l'accès strict par défaut, le compilo est capable d'effectuer de très bonnes micro-optimisations, et cela se voit !