Discussion :

[Aspic]

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

[Matt_Houston]

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.

[JolyLoic]

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 ?

[Aspic]

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

[JolyLoic]

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*))

[Aspic]

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

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

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.

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...

[Matt_Houston]

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.