Les listes de diffusion sont un moyen courant d'accélérer l'allocation en réutilisant la mémoire existante déjà allouée. Existe-t-il un moyen d'utiliser des listes libres dans un allocateur concurrent, sans encourir la surcharge d'un verrou pour chaque allocation (ce qui neutraliserait le gain de performance prévu de la liste de diffusion)?Listes avec allocateurs simultanés
Utilisez un lock-free linked list.
Vous pouvez avoir des blocs de liste libre spécifiques au thread.
Fondamentalement, il existe un système qui remplit les listes libres (par exemple un garbage collector). Chaque thread pourrait alors avoir son propre bloc de liste libre, contenant un petit nombre d'entrées. Le verrouillage serait utilisé pour allouer un nouveau segment. Avec des blocs de 30 entrées, vous ne verrouillez qu'une fois toutes les 30 allocations. Inversement, avec des blocs spécifiques à un thread, vous devrez peut-être exécuter le GC plus tôt, car la liste partagée pourrait devenir vide même si certaines parties spécifiques à un thread ont encore des entrées libres.
Est-ce que c'est vraiment une victoire de performance sur un verrou, je crois comprendre que les structures de données sans verrou ont toujours approximativement la même vitesse qu'une variante verrouillée (mais perd le potentiel pour des blocages, etc.)? –
S'il y a peu de conflit, une implémentation sans verrouillage devrait surpasser l'utilisation d'un verrou (lecture-modification-écriture au lieu d'un verrou-lecture-modification-écriture-déverrouillage), surtout si l'utilisation du verrou. En cas de conflit important, l'implémentation sans verrou peut avoir des performances moins bonnes (en raison de devoir reculer et réessayer à plusieurs reprises) mais dans ce genre de situation, vous ne gagnez rien en ayant plusieurs threads avec une implémentation verrouillée La liste de liens est la majorité de votre travail, la majorité de votre travail serait sérialisé de toute façon. – moonshadow