1. #1
    Expert confirmé
    Avatar de Aspic
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2005
    Messages
    3 897
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : août 2005
    Messages : 3 897
    Points : 4 317
    Points
    4 317

    Par défaut 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
    Qui ne tente rien n'a rien !
    Ce qui ne nous tue pas nous rends plus fort !!
    Mon projet ZELDA en C++/Allegro
    http://www.tutoworld.com - Le Forum -
    Mes ressources Dotnet (cours, sources, tutos)
    --------------------------------------------
    + + =

    Ne pas oublier le Tag !

  2. #2
    Membre expert
    Inscrit en
    mars 2005
    Messages
    1 087
    Détails du profil
    Informations forums :
    Inscription : mars 2005
    Messages : 1 087
    Points : 3 176
    Points
    3 176

    Par défaut

    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.

  3. #3
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    août 2004
    Messages
    5 372
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2004
    Messages : 5 372
    Points : 15 051
    Points
    15 051

    Par défaut

    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 ?
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  4. #4
    Expert confirmé
    Avatar de Aspic
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2005
    Messages
    3 897
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : août 2005
    Messages : 3 897
    Points : 4 317
    Points
    4 317

    Par défaut

    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
    Qui ne tente rien n'a rien !
    Ce qui ne nous tue pas nous rends plus fort !!
    Mon projet ZELDA en C++/Allegro
    http://www.tutoworld.com - Le Forum -
    Mes ressources Dotnet (cours, sources, tutos)
    --------------------------------------------
    + + =

    Ne pas oublier le Tag !

  5. #5
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    août 2004
    Messages
    5 372
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2004
    Messages : 5 372
    Points : 15 051
    Points
    15 051

    Par défaut

    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*))
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  6. #6
    Membre expert
    Inscrit en
    mars 2005
    Messages
    1 087
    Détails du profil
    Informations forums :
    Inscription : mars 2005
    Messages : 1 087
    Points : 3 176
    Points
    3 176

    Par défaut

    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.

  7. #7
    Expert confirmé
    Avatar de Aspic
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2005
    Messages
    3 897
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : août 2005
    Messages : 3 897
    Points : 4 317
    Points
    4 317

    Par défaut

    Citation Envoyé par JolyLoic Voir le message
    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.
    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...
    Qui ne tente rien n'a rien !
    Ce qui ne nous tue pas nous rends plus fort !!
    Mon projet ZELDA en C++/Allegro
    http://www.tutoworld.com - Le Forum -
    Mes ressources Dotnet (cours, sources, tutos)
    --------------------------------------------
    + + =

    Ne pas oublier le Tag !

  8. #8
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    Consultant informatique
    Inscrit en
    octobre 2004
    Messages
    10 576
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Belgique

    Informations professionnelles :
    Activité : Consultant informatique

    Informations forums :
    Inscription : octobre 2004
    Messages : 10 576
    Points : 23 425
    Points
    23 425

    Par défaut

    Salut,
    Citation Envoyé par Aspic Voir le message
    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

    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  9. #9
    Membre chevronné
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    juin 2011
    Messages
    486
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : juin 2011
    Messages : 486
    Points : 2 095
    Points
    2 095

    Par défaut

    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.

  10. #10
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    Consultant informatique
    Inscrit en
    octobre 2004
    Messages
    10 576
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Belgique

    Informations professionnelles :
    Activité : Consultant informatique

    Informations forums :
    Inscription : octobre 2004
    Messages : 10 576
    Points : 23 425
    Points
    23 425

    Par défaut

    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
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  11. #11
    Expert confirmé
    Avatar de Aspic
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2005
    Messages
    3 897
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : août 2005
    Messages : 3 897
    Points : 4 317
    Points
    4 317

    Par défaut

    Citation Envoyé par koala01 Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.
    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
    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 :
    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
    Qui ne tente rien n'a rien !
    Ce qui ne nous tue pas nous rends plus fort !!
    Mon projet ZELDA en C++/Allegro
    http://www.tutoworld.com - Le Forum -
    Mes ressources Dotnet (cours, sources, tutos)
    --------------------------------------------
    + + =

    Ne pas oublier le Tag !

  12. #12
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    août 2004
    Messages
    5 372
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2004
    Messages : 5 372
    Points : 15 051
    Points
    15 051

    Par défaut

    Citation Envoyé par Aspic Voir le message
    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.
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  13. #13
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    Consultant informatique
    Inscrit en
    octobre 2004
    Messages
    10 576
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Belgique

    Informations professionnelles :
    Activité : Consultant informatique

    Informations forums :
    Inscription : octobre 2004
    Messages : 10 576
    Points : 23 425
    Points
    23 425

    Par défaut

    Citation Envoyé par Aspic Voir le message
    Je n'ai pas très bien compris le concept...
    Je veux dire que, au lieu d'avoir un test proche de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  14. #14
    Expert confirmé
    Avatar de Aspic
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2005
    Messages
    3 897
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : août 2005
    Messages : 3 897
    Points : 4 317
    Points
    4 317

    Par défaut

    Citation Envoyé par JolyLoic Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.
    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
    Qui ne tente rien n'a rien !
    Ce qui ne nous tue pas nous rends plus fort !!
    Mon projet ZELDA en C++/Allegro
    http://www.tutoworld.com - Le Forum -
    Mes ressources Dotnet (cours, sources, tutos)
    --------------------------------------------
    + + =

    Ne pas oublier le Tag !

  15. #15
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    août 2004
    Messages
    5 372
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2004
    Messages : 5 372
    Points : 15 051
    Points
    15 051

    Par défaut

    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).
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  16. #16
    Expert confirmé
    Avatar de Aspic
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2005
    Messages
    3 897
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : août 2005
    Messages : 3 897
    Points : 4 317
    Points
    4 317

    Par défaut

    Citation Envoyé par JolyLoic Voir le message
    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

    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    Qui ne tente rien n'a rien !
    Ce qui ne nous tue pas nous rends plus fort !!
    Mon projet ZELDA en C++/Allegro
    http://www.tutoworld.com - Le Forum -
    Mes ressources Dotnet (cours, sources, tutos)
    --------------------------------------------
    + + =

    Ne pas oublier le Tag !

  17. #17
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    août 2004
    Messages
    5 372
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2004
    Messages : 5 372
    Points : 15 051
    Points
    15 051

    Par défaut

    Citation Envoyé par Aspic Voir le message
    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.
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  18. #18
    Expert confirmé
    Avatar de Aspic
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2005
    Messages
    3 897
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : août 2005
    Messages : 3 897
    Points : 4 317
    Points
    4 317

    Par défaut

    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.
    Qui ne tente rien n'a rien !
    Ce qui ne nous tue pas nous rends plus fort !!
    Mon projet ZELDA en C++/Allegro
    http://www.tutoworld.com - Le Forum -
    Mes ressources Dotnet (cours, sources, tutos)
    --------------------------------------------
    + + =

    Ne pas oublier le Tag !

  19. #19
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    Consultant informatique
    Inscrit en
    octobre 2004
    Messages
    10 576
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Belgique

    Informations professionnelles :
    Activité : Consultant informatique

    Informations forums :
    Inscription : octobre 2004
    Messages : 10 576
    Points : 23 425
    Points
    23 425

    Par défaut

    Citation Envoyé par JolyLoic Voir le message
    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

    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 )

    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 )
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. table de hachage
    Par mrtatou dans le forum Langage
    Réponses: 4
    Dernier message: 18/01/2006, 10h41
  2. Table de hachage
    Par Gryzzly dans le forum Général Algorithmique
    Réponses: 1
    Dernier message: 25/12/2005, 18h31
  3. Limite Allocation Mémoire d'un tableau d'entier
    Par l9ft b9hind dans le forum C++
    Réponses: 5
    Dernier message: 27/10/2005, 20h29
  4. [Conception] Table de hachage et doublons de clés
    Par mammou dans le forum java.util
    Réponses: 2
    Dernier message: 13/05/2004, 20h16
  5. Réponses: 2
    Dernier message: 05/02/2004, 13h54

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo