performance de la déclaration d'objets

Jan 03 2021

J'étais en train de coder dans une sorte de conquête universitaire et j'ai remarqué quelque chose, quand je déclare une carte dans une boucle comme ci-dessous:

for (int i = 0; i < n; i++)
{
    map<int, bool> hashMap;
    //...
}

cela prend plus de temps que:

map<int, bool> hashMap;
for (int i = 0; i < n; i++)
{
    hashMap.clear();
    //...
}

alors je me demandais pourquoi la déclaration d'un objet dans une boucle a de pires performances que la simple réinitialisation?

Réponses

2 dxiv Jan 04 2021 at 10:59

Dans la première version du code, le constructeur et le destructeur de hashMapsont appelés nfois, tandis que dans la deuxième version, ils ne sont appelés qu'une seule fois.

La question naturelle est de savoir pourquoi la destruction et la construction d'un nouvel mapobjet seraient sensiblement différentes de la suppression et de la réutilisation d'un seul et même objet. Cela ne peut être résolu définitivement qu'en inspectant le mapcode réel de l'implémentation utilisée, donc ce qui suit n'est qu'une supposition plausible.

std::mapest généralement implémenté en utilisant des arbres rouge-noir , et il est courant pour les implémentations d'arbre rouge-noir d'utiliser un nœud sentinelle pour les feuilles NIL, voir par exemple Bénéfice d'un nœud sentinelle dans un arbre rouge noir? . Cette sentinelle doit être allouée à chaque fois qu'un arbre est construit, puis relâchée lors de la destruction. En revanche, clear'ing a map, à la place, vide l'arborescence mais réutilise les objets internes associés.

Pour un exemple réel d'une telle implémentation, le _Treeconstructeur de Microsoft appelle le bien nommé _Alloc_sentinel_and_proxy();. Puisque leur mapdérive de _Tree, cela est appelé à chaque fois qu'un mapobjet est construit.