Allocation mémoire rapide - Page 2

Très intéressant tout ce que vous dites. Puisque "fast_heap" stocke la taille des blocs deux fois, au début et à la fin, y'a un moyen de détecter les corruptions.

Sinon squalyl tes 16 octets perdus en moyenne me donnent une idée pour diminuer la perte moyenne, peut être de 24 à... 4 octets.

où est ce que j'ai perdu 16 octets en moyenne? parce que j'ai fait des blocs de 32 octets? :-)

j'ai fait explicitement un truc ultra-simple et sans prétention, ou 1 bloc = 1 bit et trouver des places de libre revient a chercher des séquences de zéros parmi des bits

donc ouais y'a forcément moyen d'optimiser ça

pour l'embarqué je trouve l'idée de TI pas mal avec des blocs relogeables et des handles à déréférencer.: Au moins la fragmentation est niquée à la source, un HeapCompress() et hop!

Oui, sauf mauvaise compréhension des choses de ma part, un alignement de la taille des blocs à x octets fait perdre en moyenne x/2 octets par bloc alloué. Ta solution est moins rapide c'est vrai, mais elle induit une perte moyenne inférieure à la mienne. Mais en complexifiant légèrement le code je dois pouvoir la réduire (les blocs auraient une taille minimale de 48 octets et seraient alignés sur un multiple de 8).

Il me semble que, dans un topic de la section, quelqu'un avait donné une idée pour accélérer l'allocation dans un système à bitmap comme le tien. Tu as une stratégie spéciale de recherche ?

C'est vrai que les handles de TI sont ingénieux. Bon, il y a au moins deux inconvénients. Ca interdit le multitache, et il faut penser à mettre à jour tous les pointeurs du programme après une allocation. Cela dit, on peut aussi bloquer ceux dont on a besoin à l'entrée d'une fonction, et les débloquer à la sortie. Ceux qui ne sont pas bloqués sont déplacables, ce qui est déjà pas mal.
C'est peut être surtout pour les fichiers qu'ils ont fait ça ? Tous sont libres, sauf celui en cours d'utilisation. Du coup, les fichiers ne fragmentent pas la mémoire.

squalyl (./32) :
pour l'embarqué je trouve l'idée de TI pas mal avec des blocs relogeables et des handles à déréférencer.: Au moins la fragmentation est niquée à la source, un HeapCompress() et hop!

In-before-Godzil : Apple faisait déjà ça depuis les premiers Mac

Zerosquare (./30) :
Il n'y a que les mauvais codeurs qui font des buffer overflow, tu n'as pas besoin de ça voyons

s/codeurs/languages/

Bof, oui et non.

Un bon codeur en C ne fait pas de buffer overflow.

Un mauvais codeur en Java ou C# ne peut pas faire de buffer overflow (à supposer qu'il n'utilise pas de code unsafe et que la VM n'ait pas de bugs), mais il peut toujours leaker de la mémoire, ce qui est à peine mieux.

Zerosquare (./36) :
Un bon codeur en C ne fait pas de buffer overflow.

ne fait presque pas. Et c'est bien là le problème.

Un mauvais codeur en Java ou C# ne peut pas faire de buffer overflow (à supposer qu'il n'utilise pas de code unsafe et que la VM n'ait pas de bugs), mais il peut toujours leaker de la mémoire, ce qui est à peine mieux.

Un langage qui ne permet pas les buffer overflows n'est pas forcément un langage managé, il s'agit juste de proposer une sémantique qui permet au compilateur de vérifier le code, ce que font plusieurs dialects du C par exemple (safe c, cyclone, etc.).

Thibaut: faut locker pour utiliser la heap+handles en multitaches.

sinon, je crois que j'utilisais un first fit.

malloc taille
bits = taille / taille bloc
chercher une chaine d'au moins bits zéros consécutifs en partant du début
-> done ou fail.

Oui, du coup ça perd son intérêt : le tas de chaque processus est entièrement locké Sauf pour les fichiers lorsqu'ils qui sont en RAM (chose courante dans l'embarqué peut être ?)

OK pour ta méthode. J'avais pas très bien compris. Donc tu perds 16 + n/(32x8) octets par bloc de n octets. Ça parait très bon. Au niveau de la vitesse et de la fragmentation, c'est correct ? Bien sur, ça doit dépendre des besoins, de l'utilisation.

j'avoue que j'avais pas fait de tests poussés si ça t'intéresse je peux te passer la source pour que tu la testes

pour le locking, le bidule était fait pour aller dans un noyau expérimental accessible par une paire de syscalls, donc toujours en exclusion mutuelle.

par contre je sais plus comment j'avais implémenté free() ptet avec un bit de séparation? je crois pas. bon, j'sais plus en fait

Pas de problème pour lui faire passer le bench Faut juste qu'il soit utilisable facilement (inclusion de headers et de .c dans un projet).

Ensuite, dans quel contexte : système très limité (TI) donc peu de blocs et peu de fragments ? Système plus large (PC) avec des centaines de milliers de blocs et des milliers de fragments ?

tu verras le source, je l'avais fait tourner sur un système à 68k.

en fait j'utilise deux tables de bits : la 2e contient un "1" a chaque "bloc de début" pour savoir ce qu'il faut libérer #tricouic#

Je doute que quelqu'un soit intéressé, mais, à tout hasard, une nouvelle version est en cours. L'overhead est toujours le meme (de 8 à 16 octets par bloc) mais l'espace moyen perdu a été sensiblement reduit. Les résultats aux benchs sont très nets, tant sur le nombre de fragments après des centaines de milliers d'opérations que sur la mémoire disponible.

Je ne publie rien tant que l'heuristique ne sera pas mise à jour. Je mets au point un filtre quasi-gaussien pour réaliser les statistiques glissantes. Les files de valeurs (ancienneté et taille des blocs mémoire) qui permettaient le calcul de moyennes et d'écarts types seront remplacées par une équation de récurrence. Il y a 4 avantages à ce système : Plus besoin de 1 à 2 ko de mémoire pour les files, Réponse fréquentielle sans phénomène oscillatoire, Produit déphasage*période quasi nul (pas de retard dans la prise en compte des nouvelles valeurs), Pas de phénomène d'horizon (toutes les données sont prises en compte, mais sont pondérées avec un poids décroissant).

OK, il suffirait de prendre les équations toutes faites de la théorie des filtres numériques, mais c'est pas drôle J'avais pensé à utiliser une moyenne glissante exponentielle (cf wikipedia), qui a une équation de récurrence plus légère que celle d'un filtre gaussien. Mais je trouve qu'elle donne trop de poids aux valeurs récentes. En plus, le produit déphasage*période de ce type de filtre (passe bas du premier ordre) est très mauvais, je trouve.

Pour accompagner cette amélioration de la qualité des données, le calcul naïf des probabilités de libération des blocs va être remplacé par de l'inférence bayesienne (de base, rien de compliqué).

Tu as oublié de m'envoyer ton allocateur squalyl ? Je suis toujours intéressé, si tu as le temps.

je voudrais d'abord ton adresse email en fait

C'est moi qui l'ai recu en fait (mon p'énom c'est Thibault aussi)

L'archive donnée dans le tout premier message du topic est mise à jour.

L'overhead moyen par bloc alloué a sensiblement diminué, et la vitesse globale a un peu augmenté. Pour une séquence d'allocations/désallocations donnée, plus de mémoire est disponible par rapport à avant.

L'heuristique de réduction de la fragmentation est à revoir en profondeur, ses degrés de liberté sont trop restreints pour qu'elle soit efficace. Mais bon, l'allocateur fragmente moins grâce à la diminution du multiple dont doit être toute taille de bloc (de 4 à 8 octets contre de 32 à 64 avant). Merci pour les pistes que vous avez données

L'unité stats.h peut être réutilisée pour d'autres choses (observation en continu de l'évolution des données d'un algo, d'une mesure physique, etc.), elle implémente différents types de moyennes glissantes. La "moyenne glissante gaussienne" (filtre récursif quasi gaussien) a une réponse impulsionnelle pas trop mauvaise (inspirée de la première approximation proposée par Rachid Deriche en 1987), mais on peut faire mieux en se basant sur les sa proposition de 1993. J'ai une descente de gradient qui tourne depuis plus d'un mois pour améliorer les paramètres de sa nouvelle approximation. Je minimise l'intégrale de l'erreur quadratique tandis que Deriche avait obtenu ses paramètres par un échantillonnage de l'erreur quadratique sur 1000 points (méthode de Simpson vs méthode des rectangles, en gros). Je n'aurai pas le temps d'intégrer cette nouvelle approximation dans le calcul de la moyenne mobile gaussienne cette année. Si par hasard quelqu'un qui passe ici est intéressé, je donnerai les meilleurs paramètres obtenus à ce moment.

(juste wow pour toute la théorie que tu mets dans ton algo. O_o C'est un projet d'études?)

vu le boulot que tu y a mis ça m'a l'air d'être "utilisable en vrai", et si le code est pas trop gros, j'envisage de l'utiliser pour mon vaporware long terme de vm java embarquée

Les arbres AVL sont les arbres auto équilibrés les plus simples. C'est sans doute la partie qui a été la plus difficile à implémenter dans cet allocateur. Pour le reste, ce sont des principes plus simples, mais c'est vrai qu'ils ont été cumulés ici. C'était une parenthèse dans un projet qui n'avait rien à voir. Je l'ai un peu améliorée cet été et si ça rend service à d'autres comme toi, c'est parfait

L'heuristique fait de l'inférence bayésienne très basique (théorème de Bayes, au programme de terminale S je crois).

La "moyenne glissante gaussienne", dans le principe, c'est un calcul de moyenne banal : on pondère les valeurs x(t) par une gaussienne g(t) et on additionne le tout (à un facteur près, puisque la somme des coeffs doit valoir 1 dans une moyenne). On fait donc un produit de convolution discret (somme de x(t) x g(T-t) pour tout t pris entre 0 et T).
A chaque instant T, pour éviter d'avoir à multiplier x(t) par g(t-T) pour tous les instants t précédents (ce serait hyper lent), il y a quelqu'un de génial qui a un jour découvert qu'on pouvait exprimer pas mal de produits de convolution discrets par une suite récurrente. L'outil qui permet de trouver la suite associée est la transformée en Z. C'est comme les transformées de Laplace et de Fourier, mais sur les entiers naturels.
Manque de bol, une gaussienne n'admet pas de transformée en Z. On doit se contenter d'approximations. Deriche a été le premier à en proposer une, dont je me suis inspiré : on démontre facilement que (1+alpha.t)^n x exp(-n.alpha.t) équivaut à exp(-t²) lorsque n -> +oo avec alpha = sqrt(2/n). En pratique, on limite n, puisque le nombre de termes dans la suite récurrente est directement lié (il faut que le calcul de la moyenne reste rapide...). On doit donc abandonner l'idée d'un alpha unique. On développe (1+alpha.t)^n x exp(-n.alpha.t) en un polynôme x exp(-n.a.t). On a alors n+1 coefficients à deviner. Pour ça, on peut faire une descente de gradient (on minimise l'écart entre une vraie gaussienne et cette fonction approchée en se promenant sur une hypersurface de dimension n, ça en jette comme ça mais c'est le même algo que pour minimiser une fonction classique à 1 variable, on remplace la dérivée par un gradient et la variable par un vecteur).
Il a proposé quelque chose de beaucoup plus précis en 1993, une somme de cosinus et de sinus pondérés par 2 exponentielles. Mon ordi optimise les coeffs depuis quelques semaines. C'est quasiment fini, ça se joue sur des micropoils de décimales.

Voilà pour la théorie !

Si tu es emmerdé par des bugs, je les corrigerai. On n'en a pas eu dans le projet qui l’utilisait en tout cas Sur TI, le code prend quelques ko. À vérifier.

C'est quoi exactement ton projet ? Ca me dit quelque chose, tu dois avoir un topic quelque part...

nan y'a pas de topic parce que j'ai rien à présenter pour l'instant

merci pour les précisions

Peut-être que le cas ne se produit pas dans un allocateur mémoire, mais je me souviens que le pire cas de certaines opérations des arbres AVL (fortement équilibrés) n'est pas très favorable.
Pour avoir une performance moins bonne en moyenne, mais plus prédictible, les arbres rouge-noir (hauteur garantie inférieure à 2 * hauteur d'un arbre AVL) de Sedgewick et al. sont souvent utilisés à la place des arbres AVL. Et apparemment, la version penchant à gauche (left-leaning Red-Black tree) est un peu meilleure que la version d'origine.

La plus longue branche d'un arbre AVL a une profondeur, au pire, de 1.414 x log2(n). Dans un arbre rouge-noir, c'est 2 x log2(n). Il se peut que les bicolores soient plus équilibrés en pratique ?
Tu as déjà codé ça ? Ca a l'air d'être une prise de tête d'après Wikipedia.

Cela dit, la garantie du temps n'est pas super importante ici, car, quel que soit l'arbre, le délai pour obtenir une allocation/libération est de toute façon dépendant du logarithme du nombre de zones libres.

Non, je n'ai jamais codé ni l'un ni l'autre
Mais je sais que le kernel Linux, entre autres, utilise des rbtrees plutôt que des arbres AVL, et que c'est en effet légèrement pénible de faire le code de rbtrees.

Cela dit, la garantie du temps n'est pas super importante ici, car, quel que soit l'arbre, le délai pour obtenir une allocation/libération est de toute façon dépendant du logarithme du nombre de zones libres.

Tout à fait.

Dans un cas, on a des arbres plus hauts mais des réorganisations plus faciles (nombre garanti très faible de rotations); dans l'autre, on a des arbres de hauteur plus faible dans le pire cas, mais qui peuvent nécessiter une rotation du bas jusqu'en haut.

D'accord

Squalyl : C'est sur TI 68k ton vaporware ?

pas seulement ^^

pour le moment ça marchotte sur PC, mais j'ai surtout pas prévu d'y dédier du temps avant un moment

Tout peut arriver sur yN, GTC a bien fini par sortir ! Tu le sortiras avant Azur, ça c'est sûr.

Aaaaaaaaaaaaaaaaahhh Azur mon Dieu que c'était bon ce truc
topics/3351-as-il-en-est-ou/7#187

Ah ah ah
Quelle blague c'était ce truc ! Merci Martial

Zerosquare (./34) :

squalyl (./32) :
pour l'embarqué je trouve l'idée de TI pas mal avec des blocs relogeables et des handles à déréférencer.: Au moins la fragmentation est niquée à la source, un HeapCompress() et hop!

In-before-Godzil : Apple faisait déjà ça depuis les premiers Mac

Forcement, les premiers mac sont de l'embarqué pour les devs de maintenant!