2010-11-03 11 views
15

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?

+0

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. –

+0

@Martin, je suis juste en train d'observer la valeur "Peak Working Set" pour le processus dans Task Manager. – Tabber33

+0

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" –

Répondre

14

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).

+11

Vous devez aimer sizeof (T) <= 1 ... –

+0

@Dialecticus, très intéressant! Mais pourquoi la proportion de frais généraux est-elle la même pour les caractères de 1 octet que pour les doubles de 8 octets? – Tabber33

+0

Chaque bloc a un surcoût constant (le plus probable). Dans les deux cas, la taille du bloc est également constante (16 octets), de sorte que la surcharge en octets est constante. – Dialecticus

3

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).

+0

Non ce n'est pas possible. Je construis mon application de test en mode release (avec l'optimisation/O2) et je crée une liaison avec la bibliothèque d'exécution de release.En mode débogage, l'utilisation de la mémoire est beaucoup plus élevée: 4.327.684K pour le cas de 100M double – Tabber33

+0

@ Tabber33 - voir edit, exécutez vos mesures en dehors de l'IDE pour éviter les options de tas inefficaces –

+0

Couru en dehors de l'IDE - l'utilisation de la mémoire est identique. – Tabber33

-2

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.

+5

'queue' est un adaptateur pour' deque', par défaut. 'deque' ne fonctionne pas comme ça - il alloue de la mémoire en morceaux et en conserve une chaîne pour représenter le conteneur global. 'vecteur' est plus susceptible de faire ce que vous avez décrit ici. –

+1

Ce que vous décrivez est quelque peu précis pour 'std :: vector' quand' reserve' n'est pas appelé, mais pas du tout pour 'std :: deque'. – Tabber33

+1

Plus d'information ici fyi - http://www.gotw.ca/publications/mill14.htm –