Table de hachage limitée en mémoire

Bonjour,

Je cherche à savoir comment créer une table de hachage de manière à ne pas dépasser un certain seuil en mémoire. En utilisant unordered_set il est difficile de savoir la consommation mémoire à un instant T de manière précise (ou alors je ne sais pas comment faire).
La performance en recherche est aussi importante.

Par exemple, je veux créer une table de hachage limitée à 1024 Mo sachant que je n'ajouterais que des pointeurs dans la table.

La précision doit être de l'ordre de 10Mo.

Est ce possible ?

Merci :)

Je ne pense pas qu'il soit possible de maintenir de telles contraintes avec les conteneurs de base, a fortiori de manière portable.

Tu vas probablement devoir recourir à une implémentation alternative, ou bien la développer toi-même.

Peut-être avec un allocateur spécialisé qui lance std::bad_alloc quand la table demande trop de mémoire ? Après, je ne suis pas certain que ce soit idéal, car dans l'absolu, la table pourrait peut-être continuer à tourner avec de moins bonnes perfs... Mais en fait, il y a une question de base : Que veux-tu qu'il se passe si la table atteint cette limite ?

Je suis prêt à recoder une table de hachage maison. Ce n'est pas un problème. Je n'arrive juste pas à savoir comment connaître la mémoire totale de la table de manière précise ?

Je serais parti sur un vector (pour les buckets) et dans chaque case du vector une forward_list pour gérer les collisions. Mais est ce la bonne approche ?

Si la table est pleine au niveau mémoire, juste refuser l'insertion et éventuellement lever une exception.

Ps : je connais sparsecpp sur github mais cela ne correspond pas à mes besoins. Je suis prêt à perdre un peu en performance pour assurer le maintien de la contrainte mémoire.

Merci

Tu n'expliques toujours pas ce qui doit se passer si tu dépasses la mémoire que tu t'es allouée. Acceptes-tu d'avoir des perfs déplorables si tu commences à être juste en mémoire ? Jusqu'à quel point ? Et si malgré tes efforts, tu dépasses quand-même, tu fais quoi ?

Sinon, la taille occupée par un unordered_set<T> u, c'est grosso-modo u.bucket_count() * sizeof(void*) + u.size() * ( sizeof T + sizeof(T*))

La seule façon de connaître l'occupation mémoire de la structure est de maintenir le total en surchargeant l'allocateur comme l'a suggéré JolyLoic, puis d'y ajouter le sizeof de l'objet.

L'avantage de sparsepp ici n'est pas tant la performance que l'assurance d'avoir une implémentation identique sur toutes les plateformes. Si tu parviens à partir de là à déterminer une limite haute par élément, il te serait beaucoup plus simple d'encapsuler la map et de gérer la contrainte sur le nombre d'éléments.

Citation:

---

Envoyé par JolyLoic

Tu n'expliques toujours pas ce qui doit se passer si tu dépasses la mémoire que tu t'es allouée.

---

Citation:

---

Envoyé par Aspic

Si la table est pleine au niveau mémoire, juste refuser l'insertion et éventuellement lever une exception.

---

Citation:

---

Acceptes-tu d'avoir des perfs déplorables si tu commences à être juste en mémoire ? Jusqu'à quel point ? Et si malgré tes efforts, tu dépasses quand-même, tu fais quoi ?

---

Oui quand la table est presque pleine, on peut dégrader les perfs mais quand c'est full, on n'autorise plus aucun insert.
Cette table de hachage est utilisée dans un algorithme en IA donc en fait, l'idée est d'arrêter l'algo quand la table de hachage est pleine.

Je vais faire un test avec un unordered_set mais à mon avis, l'estimation sera mauvaise.

Citation:

---

La seule façon de connaître l'occupation mémoire de la structure est de maintenir le total en surchargeant l'allocateur comme l'a suggéré JolyLoic, puis d'y ajouter le sizeof de l'objet.

---

Jamais testé une surcharge d'allocateur mémoire, je vais voir dans cette direction

EDIT: Si on surcharge l'allocateur, pourra t-on connaitre la vraie taille en octet de l'allocation car je sais qu'il y a du padding (alignement mémoire) à chaque fois qu'on fait un new et il me semble qu'il n'est pas possible de récupérer la vraie taille allouée en octet...

Salut,

Citation:

---

Envoyé par Aspic

Oui quand la table est presque pleine, on peut dégrader les perfs mais quand c'est full, on n'autorise plus aucun insert.
Cette table de hachage est utilisée dans un algorithme en IA donc en fait, l'idée est d'arrêter l'algo quand la table de hachage est pleine.

---

ca, c'est purement et simplement aberrant d'un point de vue conceptuel car cela jetterait tous les principes SOLID aux orties (ou au minimum le SRP) : la responsabilité de ta map est.. de maintenir "un certain nombre d'éléments" en mémoire, point barre. Elle ne doit absolument pas être responsable de quoi que ce soit en termes d'algorithme.

Si "quelque chose" doit dégrader les performances ou arrêter un algorithme en fonction du nombre d'éléments (ou de la taille qu'ils représentent en mémoire) qui se trouvent dans un conteneur (le fait que ce soit une hashmap est anecdotique) , c'est ton algorithme, ce n'est surement pas ton conteneur ;)

Citation:

---

EDIT: Si on surcharge l'allocateur, pourra t-on connaitre la vraie taille en octet de l'allocation car je sais qu'il y a du padding (alignement mémoire) à chaque fois qu'on fait un new et il me semble qu'il n'est pas possible de récupérer la vraie taille allouée en octet...

---

La taille nécessaire pour représenter "un élément" en mémoire est toujours égale à la taille de tous les éléments qui le composent + "ce qu'il faut pour assurer l'alignement correct des données en mémoire" ("padding").

Si tu as bel et bien un padding sur une structure proche de

Code:

---

1 2 3 4

struct A{ char c[3]; int i; };

---

tu n'en as a priori rien à foutre, car le nombre de bytes nécessaire à la représentation de n'importe quel élément de type A correspond forcément a la taille renvoyée par sizeof qui... prend ce padding en compte: tu te foutras pas mal de savoir qu'il ne faut "que 7 bytes" pour pouvoir représenter les trois caractères et l'entier, ou (dit d'une autre manière) que tu perds un byte à cause du padding. Tout ce que tu as vraiment besoin de savoir, c'est... qu'il te faut bel et bien 8 bytes pour représenter cet élément en mémoire ;)

Note au passage que, si tu veux calculer correctement la quantité de mémoire utilisée, tu dois également prendre en compte la mémoire allouée de manière dynamique, à laquelle on accède au travers d'un pointeur ;)

Concernant les données allouées par l'allocateur, si elles sont d'une taille prédéfinie, autant ne pas les allouer dynamiquement, mais via un tableau statique sur pile refiler à l'allocateur qui va le tronçonner en petit bout à chaque allocation. Ou à la place d'un tableau sur pile, une grosse allocation qui englobe l'ensemble des éléments allouables.

Quand plus de place: std::bad_alloc. Et le container ne ferra rien.

Pour la taille allouée réellement par new, cela dépend beaucoup trop de l’implémentation pour être prédictible. Je suis même certain qu'on ne peut pas connaître la taille allouer par une allocation sans devoir faire cette allocation.

Hum...

A choisir, je préférerais que l'allocateur parte sur une assertion proche de taille_allouee + taille_nouvel_objet <= taille_maximale_admise plutôt que sur le lancement d'une exception :

A mon sens, si le développeur décide de restreindre la quantité de mémoire susceptible d'être allouée à son conteneur (quelque soit la manière dont il s'y prend) et qu'il en vient à dépasser, c'est que, d'une manière ou d'une autre, son algorithme n'est pas correct et qu'il doit donc être corrigé avant d'essayer de faire quoi que ce soit d'autre (je pense principalement au fait de faire passer sa version en production).

Et, une fois que le développeur aura corrigé son algorithme pour prendre cette restriction en compte, il ne devrait plus se trouver dans une situation dans laquelle ses besoins dépasseraient la quantité de mémoire maximale autorisée; ce qui devrait permettre de désactiver la vérification au niveau de l'allocateur ;)

Citation:

---

Envoyé par koala01

La taille nécessaire pour représenter "un élément" en mémoire est toujours égale à la taille de tous les éléments qui le composent + "ce qu'il faut pour assurer l'alignement correct des données en mémoire" ("padding").

Si tu as bel et bien un padding sur une structure proche de

Code:

---

1 2 3 4

struct A{ char c[3]; int i; };

---

tu n'en as a priori rien à foutre, car le nombre de bytes nécessaire à la représentation de n'importe quel élément de type A correspond forcément a la taille renvoyée par sizeof qui... prend ce padding en compte: tu te foutras pas mal de savoir qu'il ne faut "que 7 bytes" pour pouvoir représenter les trois caractères et l'entier, ou (dit d'une autre manière) que tu perds un byte à cause du padding. Tout ce que tu as vraiment besoin de savoir, c'est... qu'il te faut bel et bien 8 bytes pour représenter cet élément en mémoire ;)

---

Oui je sais que le sizeof prend en compte le padding mais je rejoins pluto jo_link_noir qui dit qu'il est quasiment impossible de savoir la vraie quantité d'octets allouées lors d'un new voire même d'un malloc.

Citation:

---

Pour la taille allouée réellement par new, cela dépend beaucoup trop de l’implémentation pour être prédictible. Je suis même certain qu'on ne peut pas connaître la taille allouer par une allocation sans devoir faire cette allocation.

---

Je veux bien créer un allocateur custom et le passer en 4ème paramètre de unordered_set mais si je ne peux pas pister de manière fiable la taille des allocations, ca ne sert pas à grand chose ;)

Citation:

---

A choisir, je préférerais que l'allocateur parte sur une assertion proche de taille_allouee + taille_nouvel_objet <= taille_maximale_admise plutôt que sur le lancement d'une exception :

---

Je n'ai pas très bien compris le concept...

Dans mon cas, je ne stocke que des pointeurs donc ca simplifie niveau mémoire ca ne prend que 4 octets (je tourne en 32 bits). Mais je viens de tester, avec un unordered_set, la formule :

Citation:

---

u.bucket_count() * sizeof(void*) + u.size() * ( sizeof T + sizeof(T*))

---

n'est pas fiable. A noter que dans mon cas, je n'ai pas besoin du "sizeof T" car j'ai déjà alloué ailleurs les pointeurs.

Y'a t-il un moyen en créer un nouvel allocateur de pister de manière fiable la taille des allocations ?

J'avais trouvé sous Linux une fonction qui renvoit la vraie taille pour un malloc : malloc_usable_size mais je suis sous Windows (je crois qu'il existait _msize mais d'après mes souvenirs ca ne fonctionnait pas sous GCC...)

Merci

Citation:

---

Envoyé par Aspic

Je veux bien créer un allocateur custom et le passer en 4ème paramètre de unordered_set mais si je ne peux pas pister de manière fiable la taille des allocations, ca ne sert pas à grand chose ;)

---

Je ne comprends pas ton raisonnement... Si tu écris un allocateur custom, tu as le devoir de gérer les allocations de mémoire. Et ceux qui vont t'appeler ne vont pas te mentir, sinon ils accèderaient à de la mémoire qui ne leur appartient pas => BOOM! Si de plus de ton côté, tu ne fais qu'une seule allocation de mémoire de 10Mo, puis que tu pioches là dedans, même si cette allocation initiale a quelques octets de plus, ce qui va être négligeable, par la suite, c'est toi et toi seul qui saura le taux d'efficacité de ton allocation (et oui, il te faudra probablement perdre un peu de mémoire si tu veux être efficace), mais tu auras une vision précise de la mémoire utilisée.

Citation:

---

Envoyé par Aspic

Je n'ai pas très bien compris le concept...

---

Je veux dire que, au lieu d'avoir un test proche de

Code:

---

1 2 3 4 5 6 7

/* soit totalSize = espaceMeMoireDejaAlloue + espaceMemoireRequisPourNouvelElement  * et maxSize l'espace de mémoire maximal autorisé pour la collection envisagée  */ if(totalSize >= maxSize) throw std::bad_alloc(); }

---

tu devrais faire en sorte que la vérification ne soit effectuée qu'en mode debug, car, si ton algorithme en arrive à nécessiter plus de mémoire que la quantité que le développeur est d'accord pour lui accorder, c'est que l'on est face à une erreur de programmation . C'est toute la différence entre la programmation défensive, représentée par ce premier code et la programmation par contrat qui serait obtenue sous une forme proche de

Code:

---

1 2 3 4 5

/* soit totalSize = espaceMeMoireDejaAlloue + espaceMemoireRequisPourNouvelElement  * et maxSize l'espace de mémoire maximal autorisé pour la collection envisagée  */ assert(totalSize <=masSize && "too many memory needed");

---

En effet, comme je l'ai dit plus haut, c'est à l'algorithme, à la logique qui s'occupe de remplir ta collection que revient la responsabilité de veiller à ce que la quantité de mémoire nécessaire à la représentation des élément que contient ta collection ne dépasse pas un certain seuil.

Mais l'utilisateur est un imbécile distrait, et, s'il fait une erreur au niveau de cette logique, il faut impérativement:

1. que l'erreur soit repérée le plus tôt possible (et de préférence avant que l'application n'entre en phase de production)
2. que l'erreur 'si elle existe) soit corrigée avant que l'application n'entre en phase de production

Or la conséquence du (2) est que... une fois l'erreur de logique corrigée, ton application n'aura plus jamais à s'inquiéter d'un éventuel dépassement, vu que la logique se sera déjà assurée qu'il ne surviendra plus.

Du coup, lorsque ton application entrera en phase de production (que tu la compilera en mode "release"), la vérification n'aura purement et simplement plus "aucune raison d'être" et pourrait carrément être "supprimée". La macro assert agit exactement sous cette forme, alors que le premier code (à base d'un test et du lancement d'une exception) restera quoi qu'il arrive dans la version release, ce qui serait dommage.

Citation:

---

Envoyé par JolyLoic

Je ne comprends pas ton raisonnement... Si tu écris un allocateur custom, tu as le devoir de gérer les allocations de mémoire. Et ceux qui vont t'appeler ne vont pas te mentir, sinon ils accèderaient à de la mémoire qui ne leur appartient pas => BOOM! Si de plus de ton côté, tu ne fais qu'une seule allocation de mémoire de 10Mo, puis que tu pioches là dedans, même si cette allocation initiale a quelques octets de plus, ce qui va être négligeable, par la suite, c'est toi et toi seul qui saura le taux d'efficacité de ton allocation (et oui, il te faudra probablement perdre un peu de mémoire si tu veux être efficace), mais tu auras une vision précise de la mémoire utilisée.

---

Possible que je m'exprime mal car je ne connais pas les surcharges d'allocateur. Je n'utilisais jusqu'à présent que l'allocateur par défaut de la STD.

Oui je comprends bien le concept de faire une grosse allocation et de piocher dedans et donc de bien contrôler la mémoire (c'est d'ailleurs ce que je fais dans mon programme avec une pool mémoire d'objets pré-alloués et justement ce sont ces objets là que je veux stocker dans une table de hachage (en fait un pointeur sur l'objet)).

Par contre, je ne comprends pas en quoi, je peux appliquer ce concept pour unordered_set même en passant l'allocateur en 4ème paramètre.

Exemple:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

// Creation d'une pool d'entiers. On contrôle donc la consommation mémoire sans problème // nbElem = 20000000 std::vector<int> pool_int; for (int i=0; i<nbElem; ++i) { pool_int.push_back(i); }   // Maintenant, on les stocke dans la table de hachage sous forme de pointeurs // Comment contrôler la charge mémoire de la table de hachage même avec un allocateur custom ? std::unordered_set<int*, std::hash<int*>, std::equal_to<int*>> hashtable; for (int i=0; i<nbElem; ++i) { hashtable.insert(&pool_int[i]); } std::cout << "Nb elem in hashtable = " << hashtable.size() << std::endl;

---

Ma question est donc de savoir comment limiter la taille de la table de hachage dans ce cas précis où l'on stock que des pointeurs sur des éléments.

Citation:

---

En effet, comme je l'ai dit plus haut, c'est à l'algorithme, à la logique qui s'occupe de remplir ta collection que revient la responsabilité de veiller à ce que la quantité de mémoire nécessaire à la représentation des élément que contient ta collection ne dépasse pas un certain seuil.

Mais l'utilisateur est un imbécile distrait, et, s'il fait une erreur au niveau de cette logique, il faut impérativement:

que l'erreur soit repérée le plus tôt possible (et de préférence avant que l'application n'entre en phase de production)
que l'erreur 'si elle existe) soit corrigée avant que l'application n'entre en phase de production

Or la conséquence du (2) est que... une fois l'erreur de logique corrigée, ton application n'aura plus jamais à s'inquiéter d'un éventuel dépassement, vu que la logique se sera déjà assurée qu'il ne surviendra plus.

---

Ok merci j'ai bien compris la différence :)

Je ne suis pas certain de comprendre ce que tu ne comprends pas...
À partir du moment où tu définiras un allocateur custom, toutes les allocations mémoire associée à cet undordered_map passeront obligatoirement par cet allocateur. C'est lui qui devra faire le boulot, mais qui en contrepartie a le contrôle. Donc rien ne t’empêche de compter combien tu as alloué, combien tu as désalloué, et à un moment, lors d'une allocation, de dire stop, je n'alloue plus rien, limite dépassée.

Je te conseille de regarder à en prendre un tout fait, on doit en trouver, par exemple chez bloomberg, qui sont des grands défenseurs du truc, par exemple sur https://github.com/bloomberg/bde/wik...llocator-model BufferedSequentialAllocator a l'air de faire quasiment ce que tu veux (s'il n'a plus de place, il alloue en dehors, mais ça doit pouvoir s'arranger aisément).

Citation:

---

Envoyé par JolyLoic

Je ne suis pas certain de comprendre ce que tu ne comprends pas...
À partir du moment où tu définiras un allocateur custom, toutes les allocations mémoire associée à cet undordered_map passeront obligatoirement par cet allocateur. C'est lui qui devra faire le boulot, mais qui en contrepartie a le contrôle. Donc rien ne t’empêche de compter combien tu as alloué, combien tu as désalloué, et à un moment, lors d'une allocation, de dire stop, je n'alloue plus rien, limite dépassée.

---

Je devais être fatigué hier, effectivement c'est clair :mouarf:

Par contre, comme disait koala01, lever une exception quand il n'y a plus de place n'était pas le mieux. Du coup, dans la fonction allocate de l'allocateur custom, que faire si jamais il n'y a plus de place ? Il parlait de mettre un assert :

Code:

---

1 2 3 4

/* soit totalSize = espaceMeMoireDejaAlloue + espaceMemoireRequisPourNouvelElement  * et maxSize l'espace de mémoire maximal autorisé pour la collection envisagée  */ assert(totalSize <=masSize && "too many memory needed");

---

Mais du coup, cela implique de vérifier la limitation mémoire au niveau de l'algorithme, ce qui n'est pas possible pour moi car l'information de la quantité de mémoire allouée (le fameux totalSize) se trouve dans l'allocateur custom non ?

De mon côté, je vais regarder un exemple d'allocateur comme suggéré par JolyLoic :)

Citation:

---

Envoyé par Aspic

Par contre, comme disait koala01, lever une exception quand il n'y a plus de place n'était pas le mieux.

---

Je pense que nous avons juste une légère divergence d'opinion lui et moi. Si je traduis ce que j'ai compris de lui, il dit qu'à taille de problème connu, si on dépasse la mémoire prise par l'algorithme nécessaire pour le résoudre, c'est qu'on s'est planté dans notre code, et donc qu'une bonne manière de reporter ça est par un assert, pas par une exception. Jusque là, je suis d'accord avec lui. Je pense juste que l'on n'a pas toujours le loisir de connaître la taille des problèmes auquel notre programme sera confronté au cours de sa durée de vie.

Très bien, merci à vous tous !

De mon côté, tout est clair, je n'ai plus qu'à implémenter ma solution :)

Je passe le sujet en résolu.

Citation:

---

Envoyé par JolyLoic

Je pense que nous avons juste une légère divergence d'opinion lui et moi. Si je traduis ce que j'ai compris de lui, il dit qu'à taille de problème connu, si on dépasse la mémoire prise par l'algorithme nécessaire pour le résoudre, c'est qu'on s'est planté dans notre code, et donc qu'une bonne manière de reporter ça est par un assert, pas par une exception. Jusque là, je suis d'accord avec lui. Je pense juste que l'on n'a pas toujours le loisir de connaître la taille des problèmes auquel notre programme sera confronté au cours de sa durée de vie.

---

En fait, nos opinions divergent sans doute bien moins que tu ne le crois :D

Car, oui, tu as bien compris mon opinion sur le sujet : si la limite est connue, tout dépassement indique un problème dans l'algorithme. La seule chose, c'est que, si tu pars sur le fait de limiter la quantité de mémoire utilisable par ta collection (ce qui est l'idée de cette discussion), il faut forcément que le choix de cette quantité soit fait à un moment ou à un autre.

Si l'on n'a pas décidé de la limite, il n'y a aucune raison d'essayer d'en imposer une, vu que nous ne saurions de toutes manières pas quelle limite imposer (lapalisse n'aurait sans doute pas dit mieux, non :question:)

A partir de là, que l'on décide arbitrairement de la limite en fournissant un max1MbAllocator ou que l'on crée une abstraction proche de template <Key, Value, Limit>LimitedHashMap dans laquelle Limit autorise son utilisateur à choisir la limite "qui lui convient", ce n'est que du détail sordide (même si je préférerais la deuxième solution :D ) ;)