Allocation mémoire rapide - Page 1

Bonjour,


Il y a quelques années, j'avais parlé ici d'un projet d'allocateur mémoire rapide pour TI. J'en ai eu besoin plus tard et l'ai donc achevé. Il compile et fonctionne sur Linux, mais il marche sans problème sur d'autres plateformes, tant que le compilateur est GCC (ou un équivalent fortement compatible tel que GCC4TI ou GTC).

Son utilité est discutable sur Linux, car le malloc de Linux est excellent. Sur Windows, je n'en sais rien... à tester par d'évenutelles personnes qui auraient besoin d'un allocateur rapide.
Sur TI, le gain est énorme.
D'une manière générale, s'il arrive à quelqu'un de programmer sur une plateforme qui ne dispose pas d'un gestionnaire de mémoire performant, voire d'aucun gestionnaire, peut-être ce travail lui rendra service.

- sur un Core2Duo à 3 GHz accompagné de DDR II à 800 MHz, il réalise par exemple 2.1 millions d'allocations/libérations par seconde (contre 2.5 pour le malloc de Linux).
- sur une TI à 12 MHz, il réalise par exemple 2000 allocations/libérations par seconde (contre moins de 100 pour le malloc du TIOS).

Ces performances varient avec le logarithme du nombre de zones libres, car les zones sont accédées par un arbre de tri auto équilibré (AVL pour les intimes). Il y a une heuristique sensée diminuer la fragmentation. Elle utilise des flottants (ralentissant à peine les opérations sur PC, mais très lents sur TI). Elle n'est pas présente dans la version destinée aux TI.


Voici ce qu'il faut savoir pour l'utiliser :

Décompresser l'archive et inclure tous les fichiers .c et .h dans votre projet.
Ecrire #include "fast_heap.h" en préambule des fichiers sources de votre programme où vous avez besoin de l'allocateur.

Son utilisation est très simple :

FastHeap *open_fast_heap (FHSize capacity)Fonction à appeler lors de l'initialisation de votre programme (ou à tout autre endroit, selon vos besoins).
Le paramètre capacity est la quantité de mémoire maximale que vous pourrez allouer, en octets. Soyez réaliste et juste, car cette quantité vous est réservée et devient indisponible pour le reste du système.
Il est possible de créer plusieurs allocateurs simultanés avec cette fonction.

void close_fast_heap (FastHeap *fast_heap)Détruit l'allocateur fast_heap créé avec la fonction précédente.

void *fast_alloc (FastHeap *fast_heap, FHSize size)Equivalent de malloc.
Le paramètre fast_heap est l'allocateur créé par la première fonction décrite ci-dessus. Le paramètre size est la taille du bloc que vous souhaitez allouer.
Renvoie NULL si la mémoire disponible n'est pas suffisante pour satisfaire votre demande.

void fast_free (FastHeap *fast_heap, void *user_address)Equivalent de free.
Le paramètre fast_heap est l'allocateur créé par la première fonction décrite ci-dessus. Le paramètre user_address est l'adresse du bloc à libérer.

L'allocateur : fast_heap.zip

Si quelqu'un a des suggestions (pour corriger des erreurs, pour réduire la fragmentation), c'est bienvenu. L'utilisation est libre de droits.

Intéressant.

Vous avez comparé les perfs de votre algo avec les allocateurs spécialisés existant déjà ?

On a eu 2 semaines pour réaliser la totalité du projet. Ca explique les imprécisions qui trainent dans le rapport et la superficialité des tests que tu as relevée. On l'a effectivement comparé, mais uniquement avec le malloc de Linux. Sur les séries testées, malloc prenait en moyenne 129 ms. Mon allocateur est donc un peu plus lent, comme précisé dans le post #0.

Il faudrait tester sur d'autres systèmes. Je pense en particulier aux TI, là je suis confiant Tu connais d'autres allocateurs ?

Oh, dans ce cas c'est pas mal du tout, 2 semaines c'est peu pour un projet de ce genre !
Je pensais que c'était un projet beaucoup plus long, où l'usage est de comparer avec les algos existants, d'où la question.

J'y connais pas grand-chose en algorithmie, mais il me semble que les allocateurs ont été pas mal étudiés, donc je pense qu'il doit bien en avoir un optimisé pour la rapidité. WP en parle ici mais j'ai pas le courage de lire à cette heure-ci (et comme d'hab, Knuth a apparemment écrit sur le sujet).

Intéressant, en effet.

Parmi les autres allocateurs, je connais http://goog-perftools.sourceforge.net/doc/tcmalloc.html , plus rapide que l'allocateur de glibc en single-threaded, et bien meilleur en multi-threaded. Mais il est hors de portée des TI-68k:

In particular, at startup TCMalloc allocates approximately 6 MB of memory. It would be easy to roll a specialized version that trades a little bit of speed for more space efficiency.

Zerosquare (./4) :
Je pensais que c'était un projet beaucoup plus long, où l'usage est de comparer avec les algos existants, d'où la question.

Pour être précis, ça devait se faire en 3 mois. Pour des raisons propres à l'équipe (hors sujet ici), il a fallut faire 90% du boulot en 2 semaines. Des tests plus détaillés ont été présentés oralement par la suite, mais ça ne concernait pas l'allocateur, qui n'est qu'un détail.

J'y connais pas grand-chose en algorithmie, mais il me semble que les allocateurs ont été pas mal étudiés, donc je pense qu'il doit bien en avoir un optimisé pour la rapidité.

Tout à fait C'est un allocateur efficace, parmi d'autres, qui n'est pas le meilleur. Mais il est simple (peu de code, peu d'overhead).

WP en parle ici

L'état de l'art donné à la fin semble aussi intéressant que complet Il y a eu quelques progrès depuis, mais c'est une excellente base, voire un cours assez pointu.

Lionel Debroux (./5) :
Parmi les autres allocateurs, je connais http://goog-perftools.sourceforge.net/doc/tcmalloc.html , plus rapide que l'allocateur de glibc en single-threaded, et bien meilleur en multi-threaded. Mais il est hors de portée des TI-68k

Il me fait penser à l'allocateur de Linux. En fait, l'utilisation de tables pointant vers des listes chaînées (pour avoir un accès direct à une zone libre de n'importe quelle taille) semble commune à tous les allocateurs efficaces. J'avais laissé de côté cette voie là, car je ne voyait pas comment faire lorsqu'une liste est vide (pas de zone de la taille demandée).

Fallait-il parcourir la table à la recherche de la première liste de zones libres de taille supérieure ? Ca aurait été très long.
L'auteur de ton article, si j'ai bien compris, utilise un tas général, dans lequel il va piocher des zones au besoin. Mon système d'arbre de tri auto équilibré constituerait le tas général, serait la première couche du système, dans laquelle un allocateur en O(1) (pas vraiment, mais un truc logarithmique avec une constante multiplicative proche de zéro) viendrait tailler des gros blocs au besoin, pour créer ses petites zones libres chainées.

J'ai porté l'allocateur sur TI 89/92+/V200. Il est donc directement utilisable avec TIGCC et GCC4TI. GTC n'a pas été testé.

Des tests de performance ont été faits. Sur des séries d'environ 1750 allocations de tailles aléatoires entrecoupées d'environ 950 libérations de blocs choisis aléatoirement :

- mon allocateur réalise l'ensemble des opérations en 1.3 s en moyenne.
- le malloc du TIOS réalise l'ensemble des opérations en 27 s en moyenne, lorsque la machine vient d'être réinitialisée. Si l'on fait le test après une utilisation normale (où de nombreux fichiers et handles ont été créés et détruits), le temps monte à plus de 60 s.

Comme on s'y attendait, le gain est énorme : l'allocation et la libération d'un bloc est de 21 à plus de 50 fois plus rapide. Avec fast_heap, on réalise plus de 2000 opérations par seconde, contre moins de 100 op/s avec le malloc du TIOS.


L'archive du post #0 est mise à jour. Elle contient la version adaptée pour les TI, et une version standard pour les ordinateurs plus modernes (entre autres, l'heuristique de réduction de la fragmentation y est activée).

Joli boulot Thibaut.

Thibaut (./7) :
Si l'on fait le test après une utilisation normale (où de nombreux fichiers et handles ont été créés et détruits), le temps monte à plus de 60 s.

A noter qu'un programme TI qui sait qu'il va violemment taper dans le heap devrait faire un HeapCompress au démarrage. Mais je ne sais pas si beaucoup de programme le font.

Sinon, PpHd a écrit genalib, une librairie écrite pour TI, pour les allocations/libérations intensives, tu pourrait regarder, voire comparer de ce côté aussi.

Ouai tu m'en avais parlé. Est-ce qu'il y a un document qui explique son fonctionnement interne ?
Pour les perfs, je vais me faire exploser

Pour le fonctionnement, il y a la source : http://www.ticalc.org/pub/89/asm/libs/kernel/genalib89.zip

Je ne sais pas pour les perfs. Voici les benches du ridmi :

V. Bench

	Here are the results of the program tstalloc.c.
	This program allocs N blocks, and free them in a random
	number.

		Tios		GenAlib
N=1500		4042=45s	132=1.5s
N=1000		1856=20.6s	68=0.75s
N=500		548=6.10s	22=0.25s

Tu semblerais plus rapide ?

Ca dépend des cas

Genalib est très simple à utiliser, donc je lui ai fait passer mon bench. Elle est 2 fois plus rapide : là où je mets 1.3 s pour faire 1750 allocations / 950 libérations aléatoires, PpHd met 0.6 s.

Pour celui qui programme en kernel, Genalib est excellente ! C'est dommage que PpHd ne détaille pas le fonctionnement.

Thibaut (./11) :
Pour celui qui programme en kernel, Genalib est excellente ! C'est dommage que PpHd ne détaille pas le fonctionnement.

Tu as les sources ( t3/?id=2&d=archives/Librairies/Genalib/ )
C'est juste une liste doublement chainée sur les blocs libres, bien implantée en assembleur. Rien de plus.
Elle n'a pas été conçue pour être un allocateur générique, mais un particulier sur un type de donnée.

(D'ailleurs je voulais la sortir en LGPL et je l'ai jamais fait).

"juste" ? Tu tries les maillons, ou tu les classes par taille non ?

Pas de trie. La liste est dans l'ordre des blocs dans la mémoire. De telle sorte qu'un free est O(1) et un alloc un O(n).

D'accord. Merci pour tes précisions.

C'est surprenant du O(n) venant de ta part Mais, finalement, sur ce bench, tu es meilleur. Asymptotiquement, mon allocateur est meilleur. En pratique, le bench génère trop peu de fragments pour que mon O(log n) soit meilleur que ton O(n), du fait des constantes multiplicatives inhérentes à l'entretien d'un arbre.

Si tu gères bien la fragmentation, tu peux même être meilleur en moyenne sur la plupart des cas pratiques sur TI, et ce serait très intéressant d'en discuter (sur PC, l'avantage dû a ta faible constante multiplicative disparaîtrait sans doute). Quelle est ta stratégie (best fit, first fit, autre subtilité digne de PpHd) ?

J'ai une liste des blocs libres. Je parcours la liste jusqu'à trouver le premier qui peut faire l'affaire.
Il n'est pas conçu pour être fait avec des blocs extrêmement variés. Le O(n) n'arrive que si tu as une liste chainée de bloc de plus en plus grand, et seul le dernier peut faire l'affaire. En pratique, le premier fait le plus souvent l'affaire.
La boucle de recherche est:

\loop		move.l	NextFreePtr(a0),a0
		cmp.w	Size(a0),d0
		bhi.s	\loop

(Il y a une sentinelle de taille max qui permet de s'assurer que cela finit).

La structure d'un bloc est:

; Define a block.
Size		equ	0                                    ; Taille du bloc divisé par 4
Sizep		equ	2                                    ; Taille du bloc précédent divisé par 4 + $8000 si alloué
NextFreePtr	equ	4                            ; Prochain bloc libre
PrevFreePtr	equ	8                                    ; Précédent bloc libre
EntrySize	equ	12

OK, c'est du first fit. Si je passe en first fit (3 lignes de code à changer), les allocateurs pourraient être à égalité. Il paraît que c'est mauvais pour la fragmentation en général, mais c'est bon pour toi car tu supposes que la plupart des blocs auront une même taille.

Tout dépend des besoins quoi. Voilà peut-être ce qu'on peut dire pour ta question Folco (./8)

Thibaut, quel est l'overhead de ton algo : de combien de mémoire supplémentaire a t il besoin pour sa gestion?

Est il résistant aux buffer overflows? ie si mon programme jardine, est ce que je pète toute la heap?

comment tu conçois qu'un allocateur puisse résister aux buffer overflows ?

au moins partiellement, évidemment

j'avais fait un allocateur à base de bitmaps (1 bit pour 32 octets - fallait bien choisir un truc pour le projet) et les descripteurs étaient tous regroupés dans une table au début de la mémoire, avant tous les blocs alloués. Du coup il fallait jardiner bien au début de la mémoire pour tout péter.

maintenant si tu fais un allocateur qui fout des listes chainées au milieu des blocs libres/alloués, évidemment, tu peux niquer plus facilement la structure de contrôle dès qu'un octet "dépasse"

vala, je voyais rien de plus

d'où ma question sur l'overhead aussi, vu qu'un bloc de 32 octets avait besoin d'un bit supplémentaire dans mon système.

./19 : il y a la technique des canaris, entre autres : http://en.wikipedia.org/wiki/Buffer_overflow_protection

Dans la version de base, l'overhead est de 16 octets par bloc. Si l'on désactive la possibilité de travailler dans un espace global de plus de 2 Go, (et c'est le cas dans la version TI), il tombe à 8 octets. Je crois que ce sont des valeurs à peu près classiques.
En plus de ça, lorsqu'on active l'heuristique, il y a 512 octets pour la table d'exponentielles précalulées, ainsi que moins de 1 ko pour les files qui servent à réaliser les statistiques.

L'autre facteur de perte de place qu'il faut prendre en compte dans tout système d'allocation (dis moi si je me trompe), c'est l'alignement. Actuellement, mes blocs ont une taille réelle multiple de 64 octets sur un système 64 bits, et 32 octets sur un système 32 bits. Je suis en train de réduire ça, pour tomber à 24 octets sur un système 32 bits et 48 octets sur un système 64 bits.

Actuellement, la place perdue en moyenne par bloc est donc de 8+32/2 = 24 octets sur un système 32 bits, et 16+64/2 = 48 octets sur un système 64 bits où on a autorisé la gestion de plus de 2 Go. On passera à 20 - 40 avec la prochaine version.
Sur ton système, si j'ai bien compris, elle est de 1/8+32/2 = 16.125 octets par bloc.

Pour répondre à ta dernière question, on peut effectivement perdre des branches de l'arbre en cas d'overflows. Je suis tenté de te répondre de manière statistique. Prenons un système 64 bits. Il y aura en moyenne 24 octets inutiles par bloc à cause de l'alignement. La probabilité de péter l'allocateur par un dépassement de q octets serait donc de q/24. Par exemple, un dépassement de 4 octets aura une probabilité de faire planter le système de 1/6. Bon le calcul est très grossier, c'est plus compliqué que ça.

Concernant l'efficacité de l'heuristique, ça serait pas mal de faire un peu d'inférence bayésienne. La fragmentation pourrait se réduire plus qu'actuellement. J'y réfléchis.

./21 : je ne connaissais pas, mais ça ne rend pas l'allocateur plus résistant aux buffers overflows, ça propose "juste" un moyen de détecter les éventuelles corruptions ? (c'est déjà pas mal, mais c'est vraiment la notion de "résister" qui m'intriguait, au sens où ça pourrait les contrecarrer ^^)

bah dans un RTOS tu peux hypothétiquement mettre la table des descripteurs de blocs alloués dans des pages interdites d'accès à l'userspace #usineagaz#

RTOS ou pas, c'est une question de présence de MMU ou non, non ?

Bah oui, d'où mon interrogation dans un sujet qui parle d'allocateur mémoire (mais bon ça devient un peu HS pour le coup, désolé )

Oui, sans MMU, tout ce que tu peux faire c'est détecter après coup qu'il y a eu corruption.

Avec une MMU, tu peux théoriquement empêcher les buffer overflow en encadrant le buffer par des pages à accès interdit. Mais il faut tenir compte de la granularité des pages (quelques Ko en général) : si tu t'amuses à faire ça pour tous les buffers, tu gaspilles énormément de mémoire.

Zerosquare, toi qui a rien à foutre, soude-nous une MMU qui te me surveille les overflows à l'octet près (pas de s'il te plait, complètement inutile)

Il n'y a que les mauvais codeurs qui font des buffer overflow, tu n'as pas besoin de ça voyons