Une technique d'optimisation répandue dans certains milieux est la transformation AoS → SoA, ou Array of Structs → Struct of Arrays. L'idée est littéralement de décomposer une séquence d'objets composites en un ensemble de séquences des éléments qui les composent.
Il y a des avantages et des inconvénients à cette technique.
Il est plus facile de comprendre cette technique à partir d'un exemple concret. Dans cet exemple, nous aurons plusieurs monstres (classe Monster), et nous les ferons se déplacer, comparant en vitesse et en taille les versions AoS et SoA du même programme.
Je limite, comme à l'habitude, mes inclusions à des en-têtes standards. |
|
Le calcul du temps se fera à l'aide de la fonction test(), expliquée sur ../AuSecours/Mesurer-le-temps.html |
|
|
Les positions des instances de Monstre seront des instances du type Point présenté à droite. Il est hautement probable que les conditions suivantes s'avèrent sur la plupart des machines : Un Point par défaut sera situé à l'origine. La fonction relocate(pt,dx,dy) retournera un Point tel que pt mais déplacé de dx sur l'axe des et de dy sur l'axe des . |
|
Chaque instance de Monster aura une position, une force, de la vie et... une puanteur. Cette classe n'est qu'esquissée ici; l'important pour notre démonstration est la fonction relocate_monster(), qui modifie la position d'un Monster et retourne le Monster ainsi modifié. Il est hautement probable que les conditions suivantes s'avèrent sur la plupart des machines : Notez l'idée clé ici : si nous déplaçons plusieurs instances de Monster, alors pour chaque instance nous manipulerons un seul attribut du lot à la fois, ce qui nous mènera à un parcours dont la progression en mémoire implique des bonds car les instances de Point accédées ne sont pas contiguës en mémoire. |
|
J'ai écrit deux fonctions advance_troops() de même signature, que je distingue l'une de l'autre par enable_if (des concepts seraient préférables, avec C++ 20) :
Il aurait bien sûr été possible de donner à ces deux fonctions des noms distincts, mais cela aurait manqué un tant soit peu d'élégance... |
|
Le programme de test compare ensuite deux solutions distinctes à un même problème.
Les deux versions réalisent la même tâche. Le code de l'approche SoA est un peu moins élégant, manifestement; la cohésion que l'on obtient en représentant un monstre par un type à part entiere est perdue, et il devient plus compliqué de raisonner sur le programme, son sens étant quelque peu obscurci. En retour, force est d'admettre que l'investissement rapporte :
|
|
À l'exécution, j'obtiens (https://wandbox.org/permlink/FK5S2VwhV5PUxwr7) :
Total size of memory chunk : 240000 bytes
AOS, 100000 advances for 10000 monsters in 1146928 us.
Total size of memory chunks : 220000 bytes
SOA, 100000 advances for 10000 monsters in 828958 us.C'est quand même appréciable.
Pour le code entier :
#include <iostream>
#include <vector>
#include <array>
#include <memory>
#include <cassert>
#include <type_traits>
#include <chrono>
#include <utility>
#include <algorithm>
using namespace std;
using namespace std::chrono;
template <class F, class ... Args>
auto test(F f, Args &&... args) {
auto pre = high_resolution_clock::now();
auto res = f(std::forward<Args>(args)...);
auto post = high_resolution_clock::now();
return pair{ res, post - pre };
}
struct Point {
int x{}, y{};
Point() = default;
constexpr Point(int x, int y) : x{ x }, y{ y }{
}
constexpr bool operator==(const Point &other) const noexcept {
return x == other.x && y == other.y;
}
constexpr bool operator!=(const Point &other) const noexcept {
return !(*this == other);
}
};
constexpr Point relocate(const Point &pt, int dx, int dy) {
return { pt.x + dx, pt.y + dy };
}
class Monster {
Point position;
short strength;
int life;
double smell;
public:
Monster() = default;
Monster(const Point &pos, short strength, int life, double smell)
: position{ pos }, strength{ strength }, life{ life }, smell{ smell } {
}
friend void fight(Monster &a, Monster &b) {
a.life -= b.strength;
b.life -= a.strength;
}
friend Monster relocate_monster(Monster m, int dx, int dy) {
m.position = relocate(m.position, dx, dy);
return m;
}
};
template <class It>
enable_if_t<is_same_v<Monster, decay_t<typename iterator_traits<It>::value_type>>>
advance_troops(It b, It e, int dx, int dy) {
for_each(b, e, [dx, dy](auto & monster) { monster = relocate_monster(monster, dx, dy); });
}
template <class It>
enable_if_t<is_same_v<Point, decay_t<typename iterator_traits<It>::value_type>>>
advance_troops(It b, It e, int dx, int dy) {
for_each(b, e, [dx, dy](auto & pt) { pt = relocate(pt, dx, dy); });
}
int main() {
enum {
NMONSTERS = 10'000, NADVANCES = 100'000
};
array<Monster,NMONSTERS> monsters;
for (int i = 0; i != NMONSTERS; ++i)
monsters[i] = Monster{ Point{ i, 0 }, 100, 1'000, 0.99 };
cout << "Total size of memory chunk : " << sizeof monsters << " bytes" << endl;
auto[r0, dt0] = test([&monsters] {
for(int i = 0; i != NADVANCES; ++i)
advance_troops(begin(monsters), end(monsters), 0, 1);
return 0;
});
cout << "AOS, " << NADVANCES << " advances for " << NMONSTERS << " monsters in "
<< duration_cast<microseconds>(dt0).count() << " us." << endl;
// ...
array<Point, NMONSTERS> positions;
array<short, NMONSTERS> strengths;
array<int, NMONSTERS> lives;
array<double, NMONSTERS> smells;
for (int i = 0; i != NMONSTERS; ++i) {
positions[i] = { i, 0 };
strengths[i] = 100;
lives[i] = 1'000;
smells[i] = 0.99;
}
cout << "Total size of memory chunks : " << (sizeof positions + sizeof strengths +
sizeof lives + sizeof smells) << " bytes" << endl;
auto[r1, dt1] = test([&positions] {
for (int i = 0; i != NADVANCES; ++i)
advance_troops(begin(positions), end(positions), 0, 1);
return 0;
});
cout << "SOA, " << NADVANCES << " advances for " << NMONSTERS << " monsters in "
<< duration_cast<microseconds>(dt1).count() << " us." << endl;
}Quelques liens pour enrichir le propos.
