buddy allocator workshop
1.0.0
Ce référentiel contient quelques petits exemples d'implémentations d'allocateurs Buddy. Ils sont conçus pour allouer la mémoire physique, bien qu'ils puissent être utilisés pour d'autres types d'allocation, tels que le tas. Finalement, le plus performant sera fusionné en fleur.
Tout d'abord, clonez le repo. Ensuite, cd dedans et faites cargo +nightly run pour exécuter tous les allocateurs de démonstration. Par défaut, la taille du bloc est 4KIB et la quantité de blocs est de 100 000, ce qui peut prendre un certain temps pour l'exemple des listes liées. Ne vous inquiétez pas, cela n'allouera rien - seulement des blocs de mémoire simulés. Passer -h ou --help pour obtenir de l'aide et voir l'utilisation. Vous pouvez modifier le code source pour modifier les tailles de blocs min / max, etc. Pour exécuter les tests unitaires, exécuter cargo test . Malheureusement, il n'y a pas encore de références de fret, mais je l'ai comparée de manière assez peu scientifique sur ma machine Windows.
J'ai testé les algorithmes en chronométrant diverses implémentations en utilisant le rapport intégré, allouant un gibibyte en blocs 4Kib (avec imprimerie) sur ma machine Windows. Si vous avez d'autres repères à ajouter, veuillez consulter la contribution.
(MSI CX61-2QF)
| Mise en œuvre | Temps | Déborder |
|---|---|---|
| Listes - vecteurs | 2 min | ~ 8.33E-3 gib / s |
| Listes - listes doublement liées | 25 minutes | ~ 6.66e-4 gib / s |
| RB arbres - vecteurs | ~ 0,3S | ~ 3,33 gib / s |
| RB Trees - Listes liées individuellement | ~ 0,5 s | ~ 2 gib / s |
| Bitmap | ~ 0,07s | ~ 14,28 gib / s |
Remarque: Le débit est extrapolé à partir du temps qu'il a fallu pour allouer 1 GIB dans les blocs 4Kib. Pour les implémentations qui ont une complexité> o (log n) (comme l'implémentation basée sur la liste naïve), cela ne sera pas précis - le débit ralentira à mesure que davantage de blocs seront alloués. Cela devrait être précis pour ceux qui ont une complexité de O (log n) ou moins cependant.
Cette implémentation conserve une liste par ordre du bloc. Il est générique sur le type de listes utilisées. J'ai décidé d'utiliser deux types de listes: les vecteurs ( Vec à partir de std ) et les listes doublement liées ( LinkedList , également à partir de std ). Les listes liées sont souvent appréciées pour leur temps de poussée prévisible (aucune réallocation nécessaire pour pousser), tandis que les vecteurs ont une meilleure localité de cache car les éléments sont alloués dans un bloc de mémoire contigu. J'ai utilisé des listes doublement liées car elles sont plus rapides pour l'indexation que les listes liées individuellement, car elles peuvent itérer de l'arrière ou du front selon que l'index est plus proche du début ou de la fin de la liste. J'ai décidé de tester les deux pour voir ce qui fonctionnerait mieux dans l'ensemble.
L'implémentation est récursive. Pour allouer un bloc gratuit de l'ordre K , il recherche d'abord les blocs gratuits dans la liste des blocs d'ordre k . Il ne garde pas de liste gratuite. Si aucune n'est trouvée, elle se reproduit en essayant d'allorer un bloc d'ordre K + 1. Enfin, si aucun bloc, il n'y a trouvé des blocs gratuits, il abandonne et panique. Dès que l'on est le divise de moitié, en supprimant le bloc d'origine de sa liste de commandes et en poussant les moitiés à la liste des commandes plus bas. Il renvoie ensuite la commande et l'index du premier bloc dans sa liste de commandes. Vous pouvez trouver cet algorithme dans find_or_split .
Une référence rapide et non scientifique sur ma machine Windows dit qu'il a fallu environ deux minutes pour allouer un gibibyte complet (1024 ^ 3 octets). J'ai remarqué de temps en temps une deuxième pause pour réaffecter le vecteur entier pour pousser un élément.
stdUne référence similaire indique qu'il a fallu vingt-cinq minutes pour allouer un gibibyte complet. Cela est plus de douze fois plus lent que la même implémentation avec les vecteurs. Cependant, cette implémentation n'a pas été optimisée pour les listes liées, elle est donc légèrement injuste. Contrairement à la mise en œuvre avec des vecteurs, je n'ai remarqué aucune pause, mais l'allocation est progressivement devenue plus lente.
Nous pouvons conclure que bien que les listes doublement liées en théorie soient plus rapides à pousser que les vecteurs, ils étaient encore 12 fois plus lents que les vecteurs. Cela pourrait être dû au fait que la mise en œuvre était légèrement en faveur des vecteurs (beaucoup d'indexation), ou parce que les vecteurs avaient une localité de cache plus élevée et ont donc connu moins de manquements de cache, tandis que les listes liées éprouvent des manquements de cache élevés car ils ont des éléments alloués individuellement à tas.
Cette implémentation conserve un arbre rouge-noir (de intrusive_collections ) pour tous les blocs et une liste gratuite pour chaque commande. Les listes gratuites ont été implémentées pour STD Vec de STD et intrusive_collections SinglyLinkedList . J'ai choisi une liste individuelle car il n'y aurait eu aucun avantage réel à double liaison - la seule méthode qui aurait profité (négligeable) est FreeList::remove , mais cela est toujours appelé au plus sur le deuxième élément de cette liste gratuite, il n'y a donc pas de véritable point dans l'optimisation de cela. L'arbre rouge-noir est individuellement alloué à chaque nœud, ce qui aggrave l'efficacité du cache, mais contrairement à BTreeSet / BTreeMap de std , sa recherche est O(log n) , tandis que std utilise une recherche linéaire, qui n'est pas O(log n) (vous pouvez lire à ce sujet ici). Cependant, les arbres de std n'allocation pas individuellement les nœuds, donc la localité du cache est meilleure. J'ai décidé que même si c'était vrai, car un allocateur de copain devait faire face à un nombre incroyablement grand de blocs, il était plus important d'avoir un algorithme de recherche plus efficace.
L'implémentation est récursive. Pour allouer un bloc gratuit de l'ordre K , il recherche d'abord les blocs gratuits dans la liste gratuite de la liste des blocs de commande k . Si aucune n'est trouvée, elle se reproduit en essayant d'allorer un bloc d'ordre K + 1. Enfin, si aucun bloc, il n'y a trouvé des blocs gratuits, il abandonne et panique. Dès que l'on est le divise de moitié, en supprimant le bloc d'origine de l'arbre et en insérant les moitiés, poussant leurs adresses à la liste gratuite pertinente. Il renvoie ensuite un curseur pointant vers le premier bloc. Vous pouvez trouver cet algorithme dans find_or_split . À la couche de récursivité la plus externe (la fonction qui appelle réellement la fonction Recursive find_or_split ), le bloc retourné est marqué comme utilisé et supprimé de la liste gratuite.
L'utilisation des vecteurs comme listes gratuites a pris ~ 0,3 s pour allouer un gib complet. C'est ~ 0,2 s plus rapide que les listes liées en tant que version de listes gratuites. Cela est probablement dû au fait que les vecteurs ont une meilleure localité de cache.
L'utilisation des listes liées car les listes gratuites ont pris ~ 0,5 s pour allouer un GIB complet. Voir les vecteurs comme la section listes gratuites ci-dessus.
Cette implémentation était 400x plus rapidement que l'implémentation basée sur la liste naïve (au mieux, en utilisant les vecteurs comme listes gratuites). Cela est probablement dû au fait que les arbres rouge-noir ont des opérations O(log n) à tous les niveaux, plus rapidement que les recherches, les inserts et les supprimer des vecteurs ou des listes liées.
Cette implémentation n'est pas strictement un bitmap en soi, mais est une modification d'un système bitmap. Essentiellement, chaque bloc de l'arbre stocke le plus grand ordre (entièrement fusionné) quelque part en dessous. Par exemple, un arbre qui est gratuit avec 4 commandes ressemble à ceci:
3
2 2
1 1 1 1
0 0 0 0 0 0 0 0
Si nous allouons un bloc de commande 0, il ressemble à ceci (t est t aken):
2
1 2
0 1 1 1
T 0 0 0 0 0 0 0
Il est mis en œuvre comme un tableau aplati, où pour un arbre comme
1
2 3
La représentation est 1; 2; 3 Cela a la propriété agréable que si nous utilisons des indices commençant à 1 (c'est-à-dire des indices et non des décalages), alors l'index de l'enfant gauche d'un index donné est 2 * index , et l'enfant droit est simplement 2 * index + 1 . Le parent est floor(index / 2) . Étant donné que toutes ces opérations fonctionnent avec 2s, nous pouvons utiliser un décalage de binds efficace pour les exécuter ( index << 1 , (index << 1) | 1 , et index >> 1 ).
Nous pouvons faire une recherche binaire pour trouver le bloc qui est exempt de l'ordre souhaité. Tout d'abord, nous vérifions s'il y a des blocs de l'ordre souhaité gratuitement en vérifiant le bloc racine. S'il y en a, nous vérifions si l'enfant gauche en a assez libre. Si c'est le cas, nous vérifions à nouveau son enfant gauche, etc. Si l'enfant gauche d'un bloc n'a pas assez de blocs libres, nous utilisons simplement son enfant droit. Nous savons que le bon enfant doit alors avoir assez libre, ou que le bloc racine n'est pas valide.
Cette implémentation a été très rapide. Sur mon ordinateur, il n'a fallu que ~ 0,07 s pour allouer 1Gib. Je l'ai cependant vu fonctionner jusqu'à 0,04 sur mon ordinateur - les performances fluctuent un peu. Je suppose que cela concerne la charge du processeur.
Cette implémentation n'a pas de très bonne localité de cache, car les niveaux sont stockés loin de l'autre, donc un bloc parent peut être très loin de son enfant. Cependant, tout le reste est encore très rapide, il est donc compensé. C'est aussi O (log n), mais pratiquement c'est si rapide que cela n'a pas vraiment d'importance. Pour référence: l'allocation de 8gib a pris 0,6 s, mais je l'ai vu fonctionner beaucoup mieux à> 150 ms sur l'ordinateur portable de @ gegy1000.
Si vous avez quelque chose à ajouter (comme une modification à la lecture ou à une autre implémentation ou une référence), n'hésitez pas à soumettre une demande de traction! Vous pouvez également créer un problème. Si vous voulez simplement discuter, n'hésitez pas à me faire cingler sur la Discord de la rouille (Restioson # 8323).
