Une carte et de jeu qui utilise de la mémoire contiguë et dispose d'une réserve de fonction

- Je utiliser plusieurs cartes et des ensembles. Le manque de mémoire contiguë, et le nombre élevé de (de)les allocations, est un goulot d'étranglement des performances. J'ai besoin d'un principalement STL-compatbile de la carte et de l'ensemble de la classe qui peut utiliser un bloc contigu de mémoire pour les objets internes (ou plusieurs blocs). Il doit également avoir un reserve fonction de sorte que je peux préallouer pour les tailles attendues.

Avant d'écrire mon propre je voudrais vérifier ce qui est disponible en premier. Est-il quelque chose de Boost qui fait cela? Est-ce que qqn sait de la mise en œuvre ailleurs?

Intrusive types de collection ne sont pas utilisables ici que les mêmes objets doivent exister dans plusieurs collections. Autant que je sache, STL pools de mémoire, par type, pas par exemple (sorte de, sorte de non, de nombreuses mises en garde). Ces piscines ne sont pas efficaces à l'égard de la mémoire de la localité multi-cpu/core de traitement.

Objet piscines ne fonctionnent pas comme les types seront partagés entre l'instance, mais leur piscine ne devrait pas.

Dans de nombreux cas, une carte de hachage peut être une option.

  • Pouvez-vous utiliser la STL map et set conteneurs avec un noeud personnalisé allocateur? (Par exemple, Visual C++ Standard Library fourni avec un ensemble de coutume allocateurs avec différentes caractéristiques de performance (je suis sûr qu'il ya d'autres allocateurs disponibles qui sont plus portable; ceux là sont les premiers qui viennent à l'esprit).)
  • c'est ce que je voulais dire avec l'objet de piscines. STL ne supporte pas par exemple allocateurs, par type d'allocateurs.
  • Objet de la piscine est le rightest façon de gérer la mémoire liés à des problèmes de performances. Je changerais les autres conditions pour faire l'objet d'bassins pourrait être utilisé. Par ailleurs, vous pouvez stocker des objets réels dans un vecteur ou deque et l'utilisation de la carte/jeu seulement pour la référence/pointeur.
  • Normal STL carte/jeu de est généralement soutenu par équilibrée structure de l'arbre. Donc, si l'on rend la mémoire contiguë de la carte/set, beaucoup de possibilités sont là, il sera la mémoire inefficace mise en œuvre. D'autre part, si vous pouvez déterminer ensemble de données de taille de la clé ou de la diversité, vous peut utiliser hachage de la carte/set. De hachage basée sur les conteneurs sont plus susceptibles d'être la mémoire contiguë.
  • les pools de mémoire doit être par exemple dans le but de profiter de per-core la mémoire de la localité. Par le partage d'une piscine, je vais partager trop de segments de mémoire à travers les cœurs. Je suis déjà à l'aide de pointeurs. Je vais envisager de hachage cartes comme une possibilité.
  • hein? C'est peu probable de faire une différence mesurable. Sonne comme l'optimisation prématurée.

InformationsquelleAutor edA-qa mort-ora-y | 2011-01-01
  1. 14

    Ont un coup d'oeil à ceci: Google Éparses De Hachage Carte. Il a été mon préféré de la bibliothèque C++ depuis que je suis tombé sur ça il y a quelques années.

    Sa performance est incroyable, a à la fois une carte et un ensemble de classe, et a demandé-pour la réserve de fonctions. J'ai basculé d'innombrables projets à partir de divers autres carte-comme des structures de données de google sparsehash avec des résultats incroyables. La syntaxe est drop-in compatible avec le C++0x unordered_map (terrible, terrible nom!), mais il a plus de fonctions supplémentaires et de fonctionnalités ainsi.

    En interne, il est mis en œuvre avec une table de hachage à l'aide de la sparsehashing technique.

    MODIFIER (13 Mai 2015)

    Comme cela est devenu un populaire réponse, je voulais juste souligner deux autres carte des structures de type I ont été à l'aide de ces dernières années. Le Miscellaneous Container Templates (MCT) bibliothèque fournit drop-in compatible haute performance unorderd_map implémentations dans quelques variétés:

    Il dispose de six à usage général de la table de hachage des conteneurs de
    closed_hash_set, closed_hash_map, linked_hash_set, linked_hash_map,
    forward_hash_set et forward_hash_map. Les deux premiers sont très similaires
    pour TR1 unordered_set et unordered_map. Liés assurent
    des fonctionnalités supplémentaires, tandis que l'attaquant des tables de hachage sont plus efficaces
    que d'être lié, mais ont limité l'interface. Dans certains cas, la performance
    de la closed_hash_* les conteneurs peuvent encore être améliorées avec
    en option le degré d'intrusion de soutien.

    Et la folie par facebook a quelques très grandes structures. Ils n'ont pas de drop-in unordered_map remplacement proprement dit, mais il y a un lock-free/thread-safe de la mise en œuvre de unordered_map et construire des choses autour de fbvector peut entraîner d'énormes gains de performance grâce à une meilleure utilisation de la mémoire et de la présentation.

    Dans mes tests, single-threaded code de Google dense_hash_map est encore mon option préférée pour des performances maximales.

    • Merci, je vais vérifier. unordered_map est en fait un bon nom -- il suit la convention de nommage de l'abstrait collection plutôt que de la sauvegarde de la structure.
    • Eh bien, ce n'est pas une baisse de 100% de remplacement, vous avez besoin d'un set_empty_key() appeler au moins.
    • Je pense que si vous prenez le google dense_map, il ne peut pas être d'abandon en raison de l'itérateur d'invalidation sur le réchauffé. c'est exactement à cause de cette raison que le C++ std implémentations de unordered ne peut pas faire aussi bien. Il est dans la norme des spec que les itérateurs n'invalident pas sur insérer/effacer de sans rapport avec les touches. Ce qui signifie std à base de trucs est obligé d'utiliser fermée adresse hashin dans la pratique. google stuff est ouverte à l'adresse et ne respectent pas la norme. donc pas de baisse.
    InformationsquelleAutor Mahmoud Al-Qudsi
  2. 6

    Vous pouvez simplement utiliser un vecteur binaire de recherche pour contiguë de stockage et de réserve() ainsi que le maintien de O(logn). L'insertion serait plus cher, cependant.

    • Pour l'ensemble des cas cela pourrait probablement fonctionner dans certaines situations, en particulier ceux qui ne tous les inserts avant tout des recherches. Dommage que std::binary_search ne retourne un itérateur, qui aurait été plus pratique.
    • Utilisation lower_bound
    • Oui, que vais le faire. Merci.
    InformationsquelleAutor Puppy
  3. 6

    Coup de pouce.Interprocessus et Boost.Récipient plat définir et plats de la carte qui peut vous aider à améliorer les performances de votre application.

    Voir https://svn.boost.org/svn/boost/sandbox/move/libs/container/doc/html/boost_container_reference.html#header.boost.container.flat_set_hpp

    • Oui! Qui ressemble à ce que je veux. Je vais vérifier les caractéristiques de performance d'elle.
    • Désolé, j'ai du décocher la case "réponse" élément ici. Tout cet ensemble/carte sont utiles, ils auront certainement une mauvaise insertion de la performance (comme ils fonctionnent comme un vecteur trié).
    InformationsquelleAutor Vicente Botet Escriba
  4. 6

    Une récente post sur la relance de la liste de diffusion discuté quelque chose de semblable.

    Howard Hinnant a créé un allocateur qui peut utiliser la pile au lieu du tas.

    http://howardhinnant.github.io/stack_alloc.html

    • Merci. Alors que peut-être pas une solution générale, je pense que je peux l'utiliser dans quelques endroits. Or, cela rend l'utilisation de la quasi-fonctionnelle par exemple allocateurs dans la STL (je pense 0x nettoie cette place pour travailler mieux)
    • vous avez raison, c'est la garantie de travailler avec C++0x, mais pas avec le C++03, même si je semble me rappeler qu'il ne fonctionne pas avec gcc / VC.
    • Je peux confirmer qu'il fonctionne avec gcc 4.4 en ce moment.
    InformationsquelleAutor dalle
  5. 1

    Vous voudrez peut-être jeter un coup d'oeil à Google TCMalloc. C'est une baisse-dans le remplacement pour le malloc, ce qui pourrait accélérer la vitesse de votre programme. TCMalloc est spécifiquement conçu pour de multiples threads.

    • Je n'ai pas encore vérifier si tcmalloc fonctionnera mieux que de glibc ptmalloc. En général, mon but est d'éviter les allocations complètement comme ils ne devraient pas être nécessaires.
    InformationsquelleAutor Jørgen Fogh