Lock-free pool allocators

Marsh Posté le 29-12-2014 à 22:42:11

Hello :hello:

Je commence à regarder la programmation concurrentiel en lock-free, et j'avoue que ça me séduit très fortement
Histoire de m'échauffer un peu, j'ai voulu commencer par implémenter un pool allocator en lock-free.
(Pour des raisons d'apprentissage / cas ultra foireux de la mort caca, dans un vrai code j'essaierai plutôt d'avoir une architecture qui minimise au maximum le partage d'objets..)

J'ai une version non thread-safe déjà implémentée qui marche comme ça en gros :

Chaque chunk est une zone mémoire de N bytes (où N >= sizeof(void*)).
Dans la mesure où un chunk est "libre", l'adresse vers le prochain chunk free est stockée en début, ça correspond globalement à ça :

Code :

struct pool_chunk
{
pool_chunk* next_chunk;
// padding mémoire ici -pas en dur, biensûr-
};

Et globalement, l'alloc/dealloc donne ça (sans les check de "apu chunks"/alignment demandé/taille demandée/constructeur/.... ) :

Code :

class pool_allocator
{
private:
pool_chunk* m_next_free_chunk;
public:
void* allocate( ... )
{
pool_chunk* free_chunk = m_next_free_chunk;
m_next_free_chunk = free_chunk->next_chunk;
return reinterpret_cast<void*>(free_chunk);
}
void deallocate( void* address )
{
pool_chunk* new_free_chunk = reinterpret_cast<pool_chunk*>(address);
new_free_chunk->next_chunk = m_next_free_chunk;
m_next_free_chunk = new_free_chunk;
}
};

Jusqu'ici tout va bien (O(1) en alloc/dealloc, c'est du propre )

Comme le processus est assez simple, j'ai pensé qu'une version lock-free devrait être pas trop chiante à implémenter.

Ma première idée (que je vais pas tellement détailler) consistait à avoir un tableau de pool_chunk* comme racine.
Chaque entrée de tableau était associé à un compteur atomic.
L'allocation se faisait avec le même process en gros, sauf qu'au lieu de bosser direct sur un pointeur, il y avait une boucle active qui incrémentait chaque entrée une-à-une en récupérant la valeur précédente.
Si elle était à 0, ça veut dire que la racine correspondante n'était pas utilisée, et donc le thread pouvait tranquillement faire son affaire, et finir par relâcher l'entrée en décrémentant le compteur.
Si c'était pas à 0, il décrémentait direct le compteur et passait au suivant (en gros).

Bon sauf que c'est carrément un spinlock moins "hard", et que toute l'optim se base sur un principe que globalement le bordel est équilibré (ce qui est pas forcément juste , peut-être en parcourant linéairement avec un offset calculé selon l'ID du thread...)

Bref, du coups je viens de partir sur une autre idée un peu plus "fancy" qui a l'air de faire le café (testé en release avec 40 threads + 4096 allocs, aucune collisions, ~10x plus rapide qu'un mutex sachant que la version d'avant était de 2 à 6x plus rapide qu'un mutex).

Le principe, c'est de coller un flag pour chaque chunk qui dit si oui ou non il est en train d'être manipulé par un autre thread (copie locale).
Pour ce flag, je part du principe que l'alignment minimal est de 2 (assert), du coups le dernier bit de l'adresse sera toujours 0.
Je me sert de ce flag pour ne pas manipuler plusieurs fois le même chunk et avoir aucune collisions, voilà l'implém (en gros) :

Code :

class atomic_pool_chunk
{
std::atomic<intptr_t> next_chunk;
};

Code :

class atomic_pool_allocator
{
protected:
std::atomic<intptr_t> m_root;
public:
void* allocate(...)
{
const intptr_t kmask0 = ~intptr_t(1); // Masque logique à 111...0
const intptr_t kmask1 = intptr_t(1); // Masque logique à 000...1
intptr_t i_next_chunk = 0;
intptr_t i_chunk = m_root.load();
atomic_pool_chunk p_chunk = nullptr;
for(;;)
{
p_chunk = reinterpret_cast<atomic_pool_chunk*>( i_chunk & kmask0 ); // On récupère le chunk courant, en forcant le dernier bit à 0 si le précédent est flagé
i_next_chunk = p_chunk->next_chunk.fetch_or( kmask1 ); // On essaie de flagger ce chunk comme "utilisé" et on récupère la valeur précédente.
if ( ( i_chunk & kmask1 ) == 0 ) // youpi, le chunk était pas flagé donc on a le pouvoir suprême sur celui-ci
break;
i_chunk = i_next_chunk;
}
// On a récupéré un chunk valide (le cas de "apu chunk" est pas encore traité ceci-dit..)
// Vu que le i_chunk était bien flaggé, forcément p_chunk pointe sur la bonne adresse)
root.store( p_chunk->next_chunk.load() ); // Cette ligne me semble un peu douteuse, je part du principe que le load correspond forcément au dernier store sur le next_chunk, et je restock ça sur la racine.
return reinterpret_cast<void*>(p_chunk);
}
};

Voilà le code pour l'allocation( sans les check ni le cas où il n'y a plus de chunks dispo, mais c'est trivial), j'imaginais un système équivalent pour la deallocation qui permettrait d'assigner au suivant un pointeur pas manipulé par un thread (et de relâcher le bit lors du store), histoire de jamais brancher un nouveau noeud sur un noeud qui va peut-être partir..

Avant de m'aventurer plus loin, j'aimerai savoir si ce code est bien data-race-free :??:

A priori ça me paraît OK, sachant que toutes les transactions mémoires par défaut sont en sequentially-consistent donc il ne devrait pas y avoir de soucis de réorganisation mémoire foireuse dans ce cas.. ?
Je peux pas tellement partir du postulat que "après x essais sur mon CPU avec 40threads et 4096 allocs c'est OK !".
J'imagine aussi que le code peut être amélioré en utilisant des barrières mémoires adéquat ?
J'avoue qu'après avoir vu les deux speechs de Herb Sutter, ça fait un peu peur tout ça

Désolé pour le pavé et merci pour votre aide ! [:mad_overclocker]

---------------
Perhaps you don't deserve to breathe

Marsh Posté le 29-12-2014 à 22:42:11

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed

Name *

Email *

URL

Message *