Je travaille sur un algorithme de tri externe qui utilise std::queue
et doit contraindre soigneusement son utilisation de la mémoire. J'ai remarqué que pendant la phase de fusion (qui utilise plusieurs std::queue
s de longueur fixe), mon utilisation de la mémoire augmente à environ 2.5X ce que j'attendais. Puisque std::queue
utilise par défaut std::deque
comme conteneur sous-jacent, j'ai effectué quelques tests sur std::deque
pour déterminer son temps de mémoire. Voici les résultats, fonctionnant sur VC++ 9, en mode release, avec un processus 64 bits:Que se passe-t-il avec la surcharge de mémoire de std :: deque?
Lors de l'ajout de 100 000 000 char
à un std::deque
, l'utilisation de la mémoire passe à 252 216K. Notez que 100M char
s (1 octet) devrait occuper 97,656K, donc c'est un overhead de 154,560K.
J'ai répété le test avec double
s (8 octets) et la mémoire de scie est passée à 1 976 676K, tandis que 100M double
devrait occuper 781 250K, pour un surcoût de 1 195 426K !!
Maintenant, je comprends que std::deque
est normalement implémenté comme une liste chaînée de "morceaux". Si cela est vrai, alors pourquoi le surcoût est-il proportionnel à la taille de l'élément (parce que la taille du pointeur devrait être fixée à 8 octets)? Et pourquoi est-ce si énorme?
Quelqu'un peut-il nous éclairer sur les raisons pour lesquelles std::deque
utilise autant de mémoire barrée? Je pense que je devrais passer mes std::queue
conteneurs sous-jacents à std::vector
car il n'y a pas de frais généraux (étant donné que la taille appropriée est reserve
ed). Je pense que les avantages de std::deque
sont largement annulés par le fait qu'il a un énorme surcharge (résultant en des échecs de cache, des défauts de page, etc.), et que le coût de la copie des éléments std::vector
peut être moindre, étant donné que l'ensemble l'utilisation de la mémoire est tellement inférieure. Est-ce juste une mauvaise implémentation de std::deque
par Microsoft?
Première question. Comment avez-vous déterminé l'utilisation de la mémoire? Comme certaines méthodes ne sont pas aussi précises que d'autres. –
@Martin, je suis juste en train d'observer la valeur "Peak Working Set" pour le processus dans Task Manager. – Tabber33
Si vous écrivez un programme pour allouer 2M de données (en morceaux) puis relâchez le tout, attendez que l'utilisateur entre avant de quitter le comportement. c'est-à-dire que la mémoire monte en puissance puis se stabilise mais ne redescend pas. PS> Je ne peux pas trouver "Peak Working Set" –