Que se passe-t-il avec la surcharge de mémoire de std :: deque?

Question

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:

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?

Answer 1

Regardez le code pour _DEQUESIZ (nombre d'éléments par bloc):

#define _DEQUESIZ (sizeof (_Ty) <= 1 ? 16 \ 
    : sizeof (_Ty) <= 2 ? 8 \ 
    : sizeof (_Ty) <= 4 ? 4 \ 
    : sizeof (_Ty) <= 8 ? 2 : 1) /* elements per block (a power of 2) */ 

Il devient plus petit si l'élément est plus grand. Seulement pour les éléments de plus de 8 octets, vous obtiendrez le comportement attendu (diminution proportionnelle du temps système avec augmentation de la taille de l'élément).

Answer 2

Est-il possible que vous exécutiez des binaires de débogage? 252 Mo pour les caractères 100M semble être beaucoup ...

Vous pouvez vérifier l'attribution de ce à umdh à instantané avant et après, puis comparer les deux - pourrait faire la lumière sur pourquoi il est plus grand que prévu.

EDIT: FYI - Lorsque je l'exécute en dehors du débogueur sur VS2010, j'obtiens 181 Mo avec char s.

deque<char> mydequeue; 
for (size_t i = 0; i < 100 * 1024 * 1024; ++i) 
{ 
    mydequeue.push_back(char(i)); 
} 

EDIT: Soutenir l'autre réponse de @Dialecticus, cela me donne la même empreinte que double:

struct twoInt64s 
{ 
public: 
    twoInt64s(__int64 _a, __int64 _b) : a(_a), b(_b) {} 

    __int64 a; 
    __int64 b; 
}; 

EDIT: Avec _DEQUESIZ modifié comme indiqué (128 caractères par bloc), 100M maintenant les caractères prend 113M de mémoire. Ma conclusion est que le surcoût restant que vous avez vu est dû aux structures de gestion pour les blocs deque, qui ont 16 caractères de données, plus les informations de contrôle pour deque plus plus d'informations de contrôle pour le gestionnaire de tas.

#define _DEQUESIZ (sizeof (value_type) <= 1 ? 128 \ 
    : sizeof (value_type) <= 2 ? 8 \ 
    : sizeof (value_type) <= 4 ? 4 \ 
    : sizeof (value_type) <= 8 ? 2 \ 
    : 1) /* elements per block (a power of 2) */ 

Moral - si vous voulez vraiment optimiser ce pour votre but spécial, être prêt à jouer avec <deque>. Son comportement dépend de manière critique de la taille de vos éléments, et au-delà de cela sur le modèle d'utilisation attendu.

EDIT: En fonction de vos connaissances sur les tailles de file d'attente, vous pourrez peut-être ajouter boost::circular_buffer en remplacement du conteneur std :: queue. Je parie que cela fonctionnerait plus comme vous voulez (et attendu).

Answer 3

Sans regarder la mise en œuvre effective de std :: file d'attente que vous utilisez, je suppose que son allocation de mémoire ressemble à ceci:

if (new element won't fit) { 
    double the size of the backing storage 
    realloc the buffer (which will probably copy all elements) 
} 

La raison de doubler plutôt que d'être plus conservateur que vous voulez que l'opération queue.push_pack ait l'heure moyenne O (1). Puisque la réallocation peut copier les éléments existants, une version qui n'a fait que grossir le tableau au besoin (1 élément à la fois) serait O (n^2) lorsque vous poussez initialement toutes vos valeurs dans la file d'attente. Je vais laisser au lecteur le soin de comprendre comment la version doublée donne un temps moyen constant.

Puisque vous citez la taille de l'ensemble du processus, votre estimation d'environ 2 fois plus de temps lorsque vous poussez légèrement plus d'une puissance de 2 (2^26 < 100MM < 2^27) semble raisonnable. Essayez de vous arrêter à 2^(n-1), en mesurant, puis en poussant quelques éléments et en mesurant à nouveau.