Les tableaux non contigus sont-ils performants?

En C #, lorsqu'un utilisateur crée un List<byte>et y ajoute des octets, il y a une chance qu'il manque d'espace et ait besoin d'allouer plus d'espace. Il alloue le double (ou un autre multiplicateur) de la taille du tableau précédent, copie les octets et rejette la référence à l'ancien tableau. Je sais que la liste augmente de façon exponentielle car chaque allocation est coûteuse et cela la limite aux O(log n)allocations, où le simple fait d'ajouter 10des éléments supplémentaires à chaque fois entraînerait des O(n)allocations.

Cependant, pour les grandes tailles de baie, il peut y avoir beaucoup d'espace perdu, peut-être près de la moitié de la baie. Pour réduire la mémoire que j'ai écrit une classe similaire NonContiguousArrayListqui utilise List<byte>comme un magasin de support s'il y avait moins de 4 Mo dans la liste, il attribuerait des tableaux d'octets de 4 Mo supplémentaires NonContiguousArrayListont augmenté en taille.

Contrairement à List<byte>ces tableaux qui ne sont pas contigus, il n'y a donc pas de copie de données autour, juste une allocation supplémentaire de 4M. Lorsqu'un élément est recherché, l'index est divisé par 4M pour obtenir l'index du tableau contenant l'élément, puis modulo 4M pour obtenir l'index dans le tableau.

Pouvez-vous signaler des problèmes avec cette approche? Voici ma liste:

• Les tableaux non contigus n'ont pas de localité de cache, ce qui entraîne de mauvaises performances. Cependant, à une taille de bloc de 4M, il semble qu'il y aurait suffisamment de localité pour une bonne mise en cache.
• Accéder à un élément n'est pas aussi simple, il y a un niveau supplémentaire d'indirection. Serait-ce optimisé loin? Cela causerait-il des problèmes de cache?
• Puisqu'il y a une croissance linéaire après que la limite de 4M est atteinte, vous pourriez avoir beaucoup plus d'allocations que vous ne le feriez normalement (disons, 250 allocations maximum pour 1 Go de mémoire). Aucune mémoire supplémentaire n'est copiée après 4 Mo, mais je ne sais pas si les allocations supplémentaires sont plus chères que la copie de gros morceaux de mémoire.

Aux échelles que vous avez mentionnées, les préoccupations sont totalement différentes de celles que vous avez mentionnées.

Localité de cache

• Il existe deux concepts liés:
  1. Localité, la réutilisation de données sur la même ligne de cache (localité spatiale) qui a été visitée récemment (localité temporelle)
  2. Prélecture automatique du cache (streaming).
• Aux échelles que vous avez mentionnées (cent Mo à gigaoctets, en blocs de 4 Mo), les deux facteurs ont plus à voir avec votre modèle d'accès aux éléments de données qu'avec la disposition de la mémoire.
• Ma prédiction (désemparée) est que statistiquement il pourrait ne pas y avoir beaucoup de différence de performances qu'une allocation de mémoire contiguë géante. Aucun gain, aucune perte.

Modèle d'accès aux éléments de données

• Cet article illustre visuellement comment les modèles d'accès à la mémoire affecteront les performances.
• En bref, gardez à l'esprit que si votre algorithme est déjà goulot d'étranglement par la bande passante mémoire, la seule façon d'améliorer les performances est de faire un travail plus utile avec les données déjà chargées dans le cache.
• En d'autres termes, même si YourList[k]et YourList[k+1]ont une forte probabilité d'être consécutifs (une chance sur quatre millions de ne pas l'être), ce fait n'aidera pas les performances si vous accédez à votre liste de manière complètement aléatoire, ou à grands pas imprévisibles, par exemplewhile { index += random.Next(1024); DoStuff(YourList[index]); }

Interaction avec le système GC

• À mon avis, c'est là que vous devriez vous concentrer le plus.
• Au minimum, comprenez comment votre conception interagira avec:
  • Collecte des ordures générationnelle ,
  • Tas d'objets volumineux
• Je ne connais pas bien ces sujets, je laisse donc d'autres personnes apporter leur contribution.

Frais généraux des calculs de décalage d'adresse

• Le code C # typique fait déjà beaucoup de calculs de décalage d'adresse, de sorte que la surcharge supplémentaire de votre schéma ne serait pas pire que le code C # typique travaillant sur un seul tableau.
  • N'oubliez pas que le code C # effectue également la vérification des plages de tableaux; et ce fait n'empêche pas C # d'atteindre des performances de traitement de tableau comparables avec du code C ++.
  • La raison en est que les performances sont principalement gênées par la bande passante mémoire.
  • L'astuce pour maximiser l'utilité de la bande passante mémoire est d'utiliser les instructions SIMD pour les opérations de lecture / écriture de la mémoire. Ni C # ni C ++ typiques ne font cela; vous devez recourir à des bibliothèques ou à des modules complémentaires linguistiques.

Pour illustrer pourquoi:

• Faire le calcul d'adresse
• (Dans le cas de l'OP, chargez l'adresse de base du bloc (qui est déjà dans le cache), puis faites plus de calcul d'adresse)
• Lire / écrire à l'adresse de l'élément

La dernière étape prend toujours la part du lion.

Suggestion personnelle

• Vous pouvez fournir une CopyRangefonction, qui se comporterait comme une Array.Copyfonction mais fonctionnerait entre deux instances de votre NonContiguousByteArray, ou entre une instance et une autre normale byte[]. ces fonctions peuvent utiliser le code SIMD (C ++ ou C #) pour maximiser l'utilisation de la bande passante mémoire, puis votre code C # peut fonctionner sur la plage copiée sans surcharge de déréférencement multiple ou de calcul d'adresse.

Problèmes d'utilisation et d'interopérabilité

• Apparemment, vous ne pouvez pas l'utiliser NonContiguousByteArrayavec des bibliothèques C #, C ++ ou en langue étrangère qui attendent des tableaux d'octets contigus ou des tableaux d'octets qui peuvent être épinglés.
• Cependant, si vous écrivez votre propre bibliothèque d'accélération C ++ (avec P / Invoke ou C ++ / CLI), vous pouvez passer une liste d'adresses de base de plusieurs blocs de 4 Mo dans le code sous-jacent.
  • Par exemple, si vous devez donner accès à des éléments commençant par (3 * 1024 * 1024)et se terminant par (5 * 1024 * 1024 - 1), cela signifie que l'accès s'étendra sur chunk[0]et chunk[1]. Vous pouvez ensuite construire un tableau (taille 2) de tableaux d'octets (taille 4M), épingler ces adresses de blocs et les transmettre au code sous-jacent.
• Un autre problème de convivialité est que vous ne serez pas en mesure de mettre en œuvre l' IList<byte>interface de manière efficace: Insertet Removecela prendra trop de temps à traiter car cela prendra du O(N)temps.
  • En fait, il semble que vous ne pouvez pas implémenter autre chose que IEnumerable<byte>, c'est-à-dire qu'il peut être analysé séquentiellement et c'est tout.

Il convient de noter que C ++ a déjà une structure équivalente par Standard, std::deque. Actuellement, il est recommandé comme choix par défaut pour avoir besoin d'une séquence d'accès aléatoire.

La réalité est que la mémoire contiguë est presque complètement inutile une fois que les données dépassent une certaine taille - une ligne de cache ne fait que 64 octets et une taille de page n'est que de 4 à 8 Ko (valeurs typiques actuellement). Une fois que vous commencez à parler de quelques Mo, cela devient vraiment une préoccupation. Il en va de même pour le coût d'allocation. Le prix du traitement de toutes ces données - même juste en les lisant - éclipse de toute façon le prix des allocations.

La seule autre raison de s'en inquiéter est l'interfaçage avec les API C. Mais vous ne pouvez pas obtenir un pointeur vers le tampon d'une liste de toute façon, il n'y a donc aucune préoccupation ici.

Lorsque des blocs de mémoire sont alloués à différents moments, comme dans les sous-matrices de votre structure de données, ils peuvent être situés loin les uns des autres en mémoire. Que ce soit un problème ou non dépend du CPU et est très difficile à prévoir plus longtemps. Vous devez le tester.

C'est une excellente idée, et c'est celle que j'ai utilisée dans le passé. Bien sûr, vous ne devez utiliser que des puissances de deux pour vos tailles de sous-réseau et le décalage de bits pour la division (cela peut se produire dans le cadre de l'optimisation). J'ai trouvé ce type de structure légèrement plus lent, dans la mesure où les compilateurs peuvent optimiser plus facilement une seule indirection de tableau. Vous devez tester, car ces types d'optimisations changent tout le temps.

Le principal avantage est que vous pouvez vous rapprocher de la limite supérieure de mémoire de votre système, tant que vous utilisez ces types de structures de manière cohérente. Tant que vous agrandissez vos structures de données et ne produisez pas de déchets, vous évitez les collectes de déchets supplémentaires qui se produiraient pour une liste ordinaire. Pour une liste géante, cela pourrait faire une énorme différence: la différence entre continuer à courir et manquer de mémoire.

Les allocations supplémentaires sont un problème uniquement si vos morceaux de sous-tableau sont petits, car il y a une surcharge de mémoire dans chaque allocation de tableau.

J'ai créé des structures similaires pour les dictionnaires (tables de hachage). Le dictionnaire fourni par le framework .net a le même problème que List. Les dictionnaires sont plus difficiles dans la mesure où vous devez également éviter de les ressasser.

Avec une taille de bloc de 4M, même un seul bloc n'est pas garanti contigu dans la mémoire physique; il est plus grand qu'une taille de page VM standard. Localité non significative à cette échelle.

Vous devrez vous soucier de la fragmentation du tas: si les allocations se produisent de telle sorte que vos blocs sont en grande partie non contigus dans le tas, alors lorsqu'ils sont récupérés par le GC, vous vous retrouverez avec un tas qui peut être trop fragmenté pour s'adapter à un attribution ultérieure. C'est généralement une situation pire car des échecs se produiront dans des endroits indépendants et forceront éventuellement un redémarrage de l'application.

Je tourne certaines des parties les plus centrales de ma base de code (un moteur ECS) autour du type de structure de données que vous avez décrit, bien qu'il utilise des blocs contigus plus petits (plus comme 4 kilo-octets au lieu de 4 mégaoctets).

Il utilise une double liste gratuite pour réaliser des insertions et des suppressions à temps constant avec une liste gratuite pour les blocs libres qui sont prêts à être insérés dans (blocs qui ne sont pas pleins) et une liste sous-libre à l'intérieur du bloc pour les indices dans ce bloc prêt à être récupéré lors de l'insertion.

Je couvrirai les avantages et les inconvénients de cette structure. Commençons par quelques inconvénients car il y en a plusieurs:

Les inconvénients

1. Il faut environ 4 fois plus de temps pour insérer quelques centaines de millions d'éléments dans cette structure std::vector(une structure purement contiguë). Et je suis assez décent pour les micro-optimisations, mais il y a juste plus de travail conceptuellement à faire car le cas commun doit d'abord inspecter le bloc libre en haut de la liste des blocs libres, puis accéder au bloc et faire apparaître un index gratuit à partir du bloc. liste libre, écrivez l'élément à la position libre, puis vérifiez si le bloc est plein et faites-le sortir de la liste des blocs libres si c'est le cas. C'est toujours une opération à temps constant, mais avec une constante beaucoup plus grande que de repousser std::vector.
2. Cela prend environ deux fois plus de temps lors de l'accès aux éléments à l'aide d'un modèle d'accès aléatoire étant donné l'arithmétique supplémentaire pour l'indexation et la couche supplémentaire d'indirection.
3. L'accès séquentiel ne correspond pas efficacement à une conception d'itérateur car l'itérateur doit effectuer une ramification supplémentaire chaque fois qu'il est incrémenté.
4. Il a un peu de surcharge de mémoire, généralement autour de 1 bit par élément. 1 bit par élément peut ne pas sembler beaucoup, mais si vous l'utilisez pour stocker un million d'entiers 16 bits, cela représente 6,25% de mémoire en plus qu'un tableau parfaitement compact. Cependant, dans la pratique, cela a tendance à utiliser moins de mémoire qu'à std::vectormoins que vous ne compactiez le vectorpour éliminer la capacité excédentaire qu'il réserve. De plus, je ne l'utilise généralement pas pour stocker de tels éléments minuscules.

Avantages

1. L'accès séquentiel à l'aide d'une for_eachfonction qui prend en charge un traitement de rappel des plages d'éléments dans un bloc rivalise presque avec la vitesse d'accès séquentiel avec std::vector(seulement comme un diff de 10%), il n'est donc pas beaucoup moins efficace dans les cas d'utilisation les plus critiques pour moi ( la plupart du temps passé dans un moteur ECS est en accès séquentiel).
2. Il permet des suppressions à temps constant du milieu avec la structure désallouant les blocs lorsqu'ils deviennent complètement vides. En conséquence, il est généralement assez décent de s'assurer que la structure de données n'utilise jamais beaucoup plus de mémoire que nécessaire.
3. Il n'invalide pas les index des éléments qui ne sont pas directement supprimés du conteneur, car il laisse simplement des trous derrière en utilisant une approche de liste libre pour récupérer ces trous lors de l'insertion ultérieure.
4. Vous n'avez pas à vous soucier autant de manquer de mémoire même si cette structure contient un nombre épique d'éléments, car elle ne demande que de petits blocs contigus qui ne posent pas de défi au système d'exploitation pour trouver un grand nombre de contigus inutilisés pages.
5. Il se prête bien à la concurrence et à la sécurité des threads sans verrouiller toute la structure, car les opérations sont généralement localisées sur des blocs individuels.

Maintenant, l'un des plus grands avantages pour moi était qu'il devient trivial de créer une version immuable de cette structure de données, comme ceci:

Depuis lors, cela a ouvert toutes sortes de portes pour écrire plus de fonctions dépourvues d'effets secondaires, ce qui a rendu beaucoup plus facile la sécurité d'exception, la sécurité des threads, etc. cette structure de données avec le recul et par accident, mais sans doute l'un des plus beaux avantages qu'elle a fini par avoir car elle a facilité la maintenance de la base de code.

Les tableaux non contigus n'ont pas de localité de cache, ce qui entraîne de mauvaises performances. Cependant, à une taille de bloc de 4M, il semble qu'il y aurait suffisamment de localité pour une bonne mise en cache.

La localité de référence n'est pas quelque chose qui vous préoccupe avec des blocs de cette taille, encore moins des blocs de 4 kilo-octets. Une ligne de cache ne fait généralement que 64 octets. Si vous souhaitez réduire les erreurs de cache, concentrez-vous simplement sur l'alignement correct de ces blocs et privilégiez des modèles d'accès séquentiels lorsque cela est possible.

Un moyen très rapide de transformer un modèle de mémoire à accès aléatoire en modèle séquentiel consiste à utiliser un jeu de bits. Disons que vous avez une cargaison d'indices et qu'ils sont dans un ordre aléatoire. Vous pouvez simplement les parcourir et marquer des bits dans le jeu de bits. Ensuite, vous pouvez parcourir votre ensemble de bits et vérifier quels octets sont différents de zéro, en vérifiant, disons, 64 bits à la fois. Une fois que vous rencontrez un ensemble de 64 bits dont au moins un bit est défini, vous pouvez utiliser les instructions FFS pour déterminer rapidement quels bits sont définis. Les bits vous indiquent les indices auxquels vous devez accéder, sauf que vous obtenez maintenant les indices triés dans un ordre séquentiel.

Cela a des frais généraux mais peut être un échange utile dans certains cas, surtout si vous allez parcourir ces indices plusieurs fois.

Accéder à un élément n'est pas aussi simple, il y a un niveau supplémentaire d'indirection. Serait-ce optimisé loin? Cela causerait-il des problèmes de cache?

Non, il ne peut pas être optimisé. L'accès aléatoire, au moins, coûtera toujours plus cher avec cette structure. Souvent, cela n'augmentera pas beaucoup vos erreurs de cache, car vous aurez tendance à obtenir une localité temporelle élevée avec le tableau de pointeurs vers les blocs, surtout si vos chemins d'exécution de cas courants utilisent des modèles d'accès séquentiels.

Puisqu'il y a une croissance linéaire après que la limite de 4M est atteinte, vous pourriez avoir beaucoup plus d'allocations que vous ne le feriez normalement (disons, 250 allocations maximum pour 1 Go de mémoire). Aucune mémoire supplémentaire n'est copiée après 4 Mo, mais je ne sais pas si les allocations supplémentaires sont plus chères que la copie de gros morceaux de mémoire.

Dans la pratique, la copie est souvent plus rapide car il s'agit d'un cas rare, ne se produisant que comme le log(N)/log(2)total des temps tout en simplifiant simultanément le cas courant bon marché où vous pouvez simplement écrire un élément dans le tableau plusieurs fois avant qu'il ne soit plein et doit être réaffecté à nouveau. Donc, généralement, vous n'obtiendrez pas des insertions plus rapides avec ce type de structure, car le travail de cas commun est plus cher, même s'il n'a pas à faire face à ce cas rare coûteux de réallocation d'énormes tableaux.

Le principal attrait de cette structure pour moi malgré tous les inconvénients est une utilisation réduite de la mémoire, ne pas avoir à se soucier du MOO, être capable de stocker des index et des pointeurs qui ne sont pas invalidés, la concurrence et l'immuabilité. C'est agréable d'avoir une structure de données où vous pouvez insérer et supprimer des choses en temps constant pendant qu'il se nettoie pour vous et n'invalide pas les pointeurs et les index dans la structure.