Prérequis

Ce tutoriel assume que vous vous y connaissez un minimum en programmation, le data-oriented design malgré son efficacité n'est pas le paradigme le plus facile à prendre en main et c'est pour cela que je recommande fortement d'avoir :

1. Des bases solides en programmation C/C++ (tous les exemples sont en C++)
2. Une connaissance de la programmation orientée objet solide

Introduction

Vous connaissez sans doute la programmation orientée objet, l'un des paradigme de programmation les plus populaires de nos jours, il est très pratique et surtout très logique pour notre cerveau... Malheureusement, ce n'est pas le plus efficace pour le processeur.

Le cache processeur

Le cache processeur est un espace mémoire de taille variable suivant le modèle de CPU qui permet au processeur de stocker des informations temporairement pour y accéder plus tard. Le but principal du cache est de pouvoir accéder rapidement à une information, mais pourquoi existe-t-il ?

(Source: https://gist.github.com/jboner/2841832)

Il faut environ 100 nanosecondes pour accéder à un élément dans la RAM, comparé a seulement 0.5 nanosecondes pour accéder au cache L1 ! C'est pratiquement 200x plus lent !

Voilà la cause : la latence entre le processeur et la RAM est beaucoup trop importante. Le cache a été créé pour pallier cette latence entre processeur et mémoire qui n'a fait qu'être plus perceptible et contraignante à cause de la croissance exponentielle de la puissance des processeurs, contrairement à la mémoire qui n'a pas évolué de la même manière.

Le cache et la POO

Nous avons vu qu'accéder au cache est environ 200x plus rapide qu'accéder à la RAM, mais quel est le rapport avec la programmation orientée objet ? C'est simple, en POO les objets sont éparpillés en mémoire dû à la nature même du paradigme :

class Animal
{
public:
    Animal(const std::string& in_name) : name(in_name) {}

    virtual std::string bruit() = 0;
private:
    std::string name;
};

class Vache : public Animal
{
public:
    Vache() : Animal("vache") {}

    std::string bruit() override
    {
        return "meuuh"
    }
};

class Mouton : public Animal
{
public:
    Vache() : Animal("vache") {}

    std::string bruit() override
    {
        return "bêeee"
    }
};

std::vector<std::unique_ptr<Animal>> animals;
animals.emplace_back(std::make_unique<Vache>());
animals.emplace_back(std::make_unique<Mouton>());
for(const auto& animal : animals)
    std::cout << animal->bruit() << std::endl;

Voici un petit exemple simple, si on lance ceci on devrait avoir dans notre console:

meuuh

bêeee

Très bien!

Analysons cet exemple:

• Premièrement on déclare une classe "Animal" ainsi qu'une fonction virtuelle pure bruit().
• Ensuite nous créons deux classes filles, "Vache" et "Mouton".
• Enfin, une liste de pointeurs unique vers des Animal est créée puis remplie avec une instance de Vache et une instance de Mouton pour ensuite afficher leur bruit().

Lorsque le processeur va itérer notre liste animals, il va devoir faire plusieurs sauts de mémoire pour accéder à nos instances, pourquoi ? Tout simplement car std::unique_ptr est un pointeur unique alloué sur le tas (c'est à dire la RAM) et que notre liste animals est en réalité une simple liste de pointeurs plutôt qu'une liste d'animaux avec leur données stockées de manière contiguë. Et ça se comprend : on ne peut pas faire autrement si on veut pouvoir stocker tous les types dérivés de Animal possibles. C'est ce qu'on appelle un cache miss : le faite de remplir le cache d'informations inutiles et de devoir aller en chercher dans la RAM.

Mais alors que faire ?

Le data-oriented design