Prestazioni degli allocatori personalizzati

Question

Sto costruendo una classe di albero AVL che avrà un numero massimo fisso di elementi. Così ho pensato, invece di allocare ciascun elemento da solo, assegnerei l'intero blocco in una sola volta e userei una bitmap per assegnare nuova memoria quando necessario.

Il mio codice di allocazione/deallocazione:

avltree::avltree(UINT64 numitems) 
{ 
    root = NULL; 

    if (!numitems) 
    buffer = NULL; 
    else { 
    UINT64 memsize = sizeof(avlnode) * numitems + bitlist::storagesize(numitems); 
    buffer = (avlnode *) malloc(memsize); 
    memmap.init(numitems, buffer + numitems); 
    memmap.clear_all(); 
    freeaddr = 0; 
    } 
} 

avlnode *avltree::newnode(keytype key) 
{ 
    if (!buffer) 
    return new avlnode(key); 
    else 
    { 
    UINT64 pos; 
    if (freeaddr < memmap.size_bits) 
     pos = freeaddr++; 
    else 
     pos = memmap.get_first_unset(); 
    memmap.set_bit(pos); 
    return new (&buffer[pos]) avlnode(key); 
    } 
} 

void avltree::deletenode(avlnode *node) 
{ 
    if (!buffer) 
    delete node; 
    else 
    memmap.clear_bit(node - buffer); 
} 

Per poter utilizzare nuovo standard/delete, devo costruire l'albero con numItems == 0. Per poter usare il mio allocatore, mi basta passare il numero di articoli. Tutte le funzioni sono in linea per le massime prestazioni.

Questo è tutto a posto, ma il mio allocatore è il 20% più lento del nuovo/cancella. Ora, so quanto siano complessi gli allocatori di memoria, non c'è modo che il codice possa essere eseguito più velocemente di una ricerca di array + un bit set, ma questo è esattamente il caso qui. Cosa c'è di peggio: il mio deallocator è più lento anche se rimuovo tutto il codice da esso?!?

Quando controllo l'output dell'assieme, il percorso del codice del mio allocatore è guidato con istruzioni PTR di QWORD che trattano con bitmap, avltree o avlnode. Non sembra essere molto diverso per il nuovo/percorso di cancellazione.

Per esempio, la produzione di assemblaggio di avltree :: newnode:

;avltree::newnode, COMDAT 
mov  QWORD PTR [rsp+8], rbx 
push rdi 
sub  rsp, 32 

;if (!buffer) 
cmp  QWORD PTR [rcx+8], 0 
mov  edi, edx 
mov  rbx, rcx 
jne  SHORT $LN4@newnode 

; return new avlnode(key); 
mov  ecx, 24 
call ??2@YAPEAX_K@Z   ; operator new 
jmp  SHORT $LN27@newnode 

;$LN4@newnode: 
;else { 
; UINT64 pos; 
; if (freeaddr < memmap.size_bits) 
mov  r9, QWORD PTR [rcx+40] 
cmp  r9, QWORD PTR [rcx+32] 
jae  SHORT $LN2@newnode 

; pos = freeaddr++; 
lea  rax, QWORD PTR [r9+1] 
mov  QWORD PTR [rcx+40], rax 

; else 
jmp  SHORT $LN1@newnode 
$LN2@newnode: 

; pos = memmap.get_first_unset(); 
add  rcx, 16 
call ?get_first_unset@bitlist@@QEAA_KXZ ; bitlist::get_first_unset 
mov  r9, rax 

$LN1@newnode: 
; memmap.set_bit(pos); 
mov  rcx, QWORD PTR [rbx+16]     ;data[bindex(pos)] |= bmask(pos); 
mov  rdx, r9         ;return pos/(sizeof(BITINT) * 8); 
shr  rdx, 6 
lea  r8, QWORD PTR [rcx+rdx*8]     ;data[bindex(pos)] |= bmask(pos); 
movzx ecx, r9b         ;return 1ull << (pos % (sizeof(BITINT) * 8)); 
mov  edx, 1 
and  cl, 63 
shl  rdx, cl 

; return new (&buffer[pos]) avlnode(key); 
lea  rcx, QWORD PTR [r9+r9*2] 
; File c:\projects\vvd\vvd\util\bitlist.h 
or  QWORD PTR [r8], rdx      ;data[bindex(pos)] |= bmask(pos) 

; 195 :  return new (&buffer[pos]) avlnode(key); 
mov  rax, QWORD PTR [rbx+8] 
lea  rax, QWORD PTR [rax+rcx*8] 
; $LN27@newnode: 
test rax, rax 
je  SHORT $LN9@newnode 

; avlnode constructor; 
mov  BYTE PTR [rax+4], 1 
mov  QWORD PTR [rax+8], 0 
mov  QWORD PTR [rax+16], 0 
mov  DWORD PTR [rax], edi 

; 196 : } 
; 197 : } 
; $LN9@newnode: 
mov  rbx, QWORD PTR [rsp+48] 
add  rsp, 32      ; 00000020H 
pop  rdi 
ret  0 
?newnode@avltree@@QEAAPEAUavlnode@@H@Z ENDP    ; avltree::newnode 
_TEXT ENDS 

Ho controllato più volte l'uscita della compilation, quando costruisco la mia avltree con default/allocatore personalizzato e rimane lo stesso in questa particolare regione di codice. Ho provato a rimuovere/sostituire tutte le parti rilevanti senza alcun effetto significativo.

Per essere onesti, mi aspettavo che il compilatore aggiungesse tutto questo in quanto ci sono pochissime variabili. Speravo che tutto, tranne gli oggetti avlnode, venissero inseriti nei registri, ma non sembra essere il caso.

Tuttavia, la differenza di velocità è chiaramente misurabile. Non sto chiamando 3 secondi per 10 milioni di nodi inseriti lentamente, ma mi aspettavo che il mio codice fosse più veloce, non più lento di un allocatore generico (2,5 secondi). Ciò vale soprattutto per il deallocator più lento, che è più lento anche quando tutto il codice viene rimosso da esso.

Perché è più lento?

Modifica: Grazie a tutti per gli eccellenti pensieri su questo. Ma vorrei sottolineare ancora una volta che il problema non è tanto nel mio metodo di allocazione quanto nel modo subottimale di usare le variabili: l'intera classe avltree contiene solo 4 variabili UINT64, solo la bitlist ha 3.

Tuttavia, nonostante ciò, il compilatore non lo ottimizza nei registri. Insiste su istruzioni PW di QWORD che sono ordini di grandezza più lenti. È perché sto usando le lezioni? Dovrei passare a C/variabili semplici? Gratta che. Che stupido. Ho anche tutto il codice del gioco, le cose non possono essere nei registri.

Inoltre, sono a una perdita totale perché il mio deallocator sarebbe ancora più lento, anche se rimuovo TUTTO il codice da esso. Eppure QueryPerformanceCounter mi dice proprio questo. È assurdo pensare che: anche lo stesso deallocator viene chiamato per il nuovo/delete code path e deve cancellare il nodo ... Non deve fare nulla per il mio allocatore personalizzato (quando spoglio il codice).

Edit2: Ora ho rimosso completamente la bitlist e implementato il tracciamento dello spazio libero tramite un elenco collegato singolarmente. La funzione avltree :: newnode ora è molto più compatta (21 istruzioni per il mio percorso di allocazione personalizzato, 7 di queste sono operazioni PW di QWORD che si occupano di avltree e 4 sono usate per il costruttore di avlnode). Il risultato finale (tempo) è diminuito da ~ 3 secondi a ~ 2,95 secondi per 10 milioni di allocazioni.

Edit3: Ho anche riscritto l'intero codice in modo che ora tutto sia gestito dalla lista concatenata. Ora la classe avltree ha solo due membri rilevanti: root e first_free. La differenza di velocità rimane.

Edit4: Riorganizzare il codice e guardando i dati di performance, queste cose sono ciò che ha aiutato di più:

1. Come sottolineato da tutti i contribuenti, avendo una bitmap in c'era semplicemente male. Rimosso a favore dell'elenco di slot gratuiti collegati singolarmente.
2. Località del codice: aggiungendo le funzioni dipendenti (quelle di gestione avl) in una classe locale della funzione anziché averle dichiarate globalmente ha aiutato circa il 15% con la velocità del codice (3 secondi -> 2,5 secondi)
3. dimensione struttura avlnode : solo l'aggiunta di #pragma pack(1) prima dichiarazione struct una diminuzione del tempo di esecuzione di un ulteriore 20% (2,5 sec -> 2 sec)

Edit 5:

Dal momento che questo querstion sembra essere stato molto popolare, Ho pubblicato il codice completo finale come risposta sotto. Sono abbastanza soddisfatto delle sue prestazioni.

Answer 1

Il metodo assegna solo la memoria non elaborata in un blocco e quindi deve eseguire un posizionamento nuovo per ciascun elemento. Combinalo con tutto il sovraccarico nella tua bitmap e non sorprende che l'allocazione predefinita new picchi la tua ipotizzando un heap vuoto.

Per ottenere il massimo miglioramento di velocità durante l'allocazione, è possibile allocare l'intero oggetto in un unico array di grandi dimensioni e quindi assegnarlo da lì.Se si guarda a un punto di riferimento molto semplice e artificiosa:

struct test_t { 
    float f; 
    int i; 
    test_t* pNext; 
}; 

const size_t NUM_ALLOCS = 50000000; 

void TestNew (void) 
{ 
    test_t* pPtr = new test_t; 

    for (int i = 0; i < NUM_ALLOCS; ++i) 
    { 
     pPtr->pNext = new test_t; 
     pPtr = pPtr->pNext; 
    } 

} 

void TestBucket (void) 
{ 
    test_t* pBuckets = new test_t[NUM_ALLOCS + 2]; 
    test_t* pPtr = pBuckets++; 

    for (int i = 0; i < NUM_ALLOCS; ++i) 
    { 
     pPtr->pNext = pBuckets++; 
     pPtr = pPtr->pNext; 
    } 

} 

Con questo codice su MSVC++ 2013, con allocazioni 50M TestBucket() sorpassa TestNew() di oltre un fattore di x16 (130 vs 2080 ms). Anche se si aggiunge uno std::bitset<> per tracciare le allocazioni, è ancora x4 più veloce (400 ms).

Una cosa importante da ricordare su new è che il tempo necessario per allocare un oggetto dipende generalmente dallo stato dell'heap. Un heap vuoto sarà in grado di allocare un gruppo di oggetti di dimensioni costanti come questo relativamente veloce, che è probabilmente uno dei motivi per cui il tuo codice sembra più lento di new. Se si dispone di un programma che viene eseguito per un po 'e si assegna un numero elevato di oggetti di dimensioni diverse, l'heap può diventare frammentato e l'allocazione di oggetti può richiedere molto (molto) tempo.

Ad esempio, un programma che ho scritto stava caricando un file da 200 MB con milioni di record ... un sacco di allocazioni di dimensioni diverse. Al primo caricamento ci sono voluti ~ 15 secondi, ma se ho cancellato quel file e ho provato a caricarlo di nuovo, ho impiegato qualcosa come x10-x20 più a lungo. Ciò era interamente dovuto all'allocazione della memoria e il passaggio a un semplice allocatore bucket/arena ha risolto il problema. Quindi, il benchmark elaborato che ho mostrato un aumento di velocità x16 potrebbe effettivamente mostrare una differenza significativamente più grande con un heap frammentato.

Diventa ancora più complicato quando ci si rende conto che sistemi/piattaforme diversi possono utilizzare diversi schemi di allocazione della memoria, in modo che i risultati del benchmark su un sistema possano essere diversi da un altro.

per distillare questo in alcuni punti corti:

1. allocazione di memoria Benchmarking è difficile (performance dipende da un sacco di cose)
2. In alcuni casi si possono ottenere prestazioni migliori con un allocatore personalizzato. In alcuni casi puoi migliorare molto.
3. La creazione di un allocatore personalizzato può essere complicata e richiede tempo per il profilo/benchmark del caso d'uso specifico.

Nota - Benchmark come questo non sono destinate ad essere realistici, ma sono utili per determinare il limite superiore di quanto velocemente qualcosa può essere. Può essere usato insieme al profilo/benchmark del tuo codice reale per determinare cosa dovrebbe/non dovrebbe essere ottimizzato.

Aggiornamento - Non riesco a replicare i risultati nel mio codice sotto MSVC++ 2013. Utilizzando la stessa struttura come la vostra avlnode e cercando un collocamento new produce la stessa velocità come il mio non di posizionamento test secchio allocatore (il posizionamento nuovo era in realtà un po 'più veloce). L'utilizzo di una classe simile a avltree non influisce molto sul benchmark. Con 10 milioni di allocazioni/deallocations ricevo ~ 800 ms per lo new/ e ~ 200ms per l'allocatore personalizzato (con e senza posizionamento new). Mentre non sono preoccupato per la differenza nei tempi assoluti, la differenza di tempo relativa sembra strana.

Suggerirei di dare un'occhiata più da vicino al vostro punto di riferimento e assicurarsi di misurare ciò che pensate di essere. Se il codice esiste in una base di codice più ampia, creare un caso di test minimo per confrontarlo. Assicurati che il tuo ottimizzatore di compilatore non stia facendo qualcosa che invalida il benchmark (succede troppo facilmente in questi giorni).

Si noti che sarebbe molto più semplice rispondere alla domanda se lo si fosse ridotto a un esempio minimo e incluso il codice completo nella domanda, incluso il codice di riferimento. Il benchmarking è una di quelle cose che sembra facile, ma ci sono molti "trucchi" coinvolti in esso.

Aggiornamento 2 - Compreso la classe di allocatore di base e il codice di riferimento che sto utilizzando in modo che altri possano provare a duplicare i miei risultati. Si noti che questo è solo per i test ed è lontano dal codice di lavoro/produzione effettivo. È molto più semplice del tuo codice che potrebbe essere il motivo per cui stiamo ottenendo risultati diversi.

#include <string> 
#include <Windows.h> 

struct test_t 
{ 
    __int64 key; 
    __int64 weight; 
    __int64 left; 
    __int64 right; 
    test_t* pNext;  // Simple linked list 

    test_t() : key(0), weight(0), pNext(NULL), left(0), right(0) { } 
    test_t(const __int64 k) : key(k), weight(0), pNext(NULL), left(0), right(0) { } 
}; 

const size_t NUM_ALLOCS = 10000000; 
test_t* pLast; //To prevent compiler optimizations from being "smart" 

struct CTest 
{ 
    test_t* m_pBuffer; 
    size_t m_MaxSize; 
    size_t m_FreeIndex; 
    test_t* m_pFreeList; 

    CTest(const size_t Size) : 
      m_pBuffer(NULL), 
      m_MaxSize(Size), 
      m_pFreeList(NULL), 
      m_FreeIndex(0) 
    { 
     if (m_MaxSize > 0) m_pBuffer = (test_t *) new char[sizeof(test_t) * (m_MaxSize + 1)]; 
    } 

    test_t* NewNode(__int64 key) 
    { 
     if (!m_pBuffer || m_FreeIndex >= m_MaxSize) return new test_t(key); 

     size_t Pos = m_FreeIndex; 
     ++m_FreeIndex; 
     return new (&m_pBuffer[Pos]) test_t(key); 
    } 

    void DeleteNode(test_t* pNode) 
    { 
     if (!m_pBuffer) { 
      delete pNode; 
     } 
     else 
     { 
      pNode->pNext = m_pFreeList; 
      m_pFreeList = pNode; 
     } 
    } 

}; 


void TestNew(void) 
{ 
    test_t* pPtr = new test_t; 
    test_t* pFirst = pPtr; 

    for (int i = 0; i < NUM_ALLOCS; ++i) 
    { 
     pPtr->pNext = new test_t; 
     pPtr = pPtr->pNext; 
    } 

    pPtr = pFirst; 

    while (pPtr) 
    { 
     test_t* pTemp = pPtr; 
     pPtr = pPtr->pNext; 
     delete pTemp; 
    } 

    pLast = pPtr;  
} 


void TestClass(const size_t BufferSize) 
{ 
    CTest Alloc(BufferSize); 
    test_t* pPtr = Alloc.NewNode(0); 
    test_t* pFirstPtr = pPtr; 

    for (int i = 0; i < NUM_ALLOCS; ++i) 
    { 
     pPtr->pNext = Alloc.NewNode(i); 
     pPtr = pPtr->pNext; 
    } 

    pLast = pPtr; 
    pPtr = pFirstPtr; 

    while (pPtr != NULL) 
    { 
     test_t* pTmp = pPtr->pNext; 
     Alloc.DeleteNode(pPtr); 
     pPtr = pTmp; 
    } 
} 


int main(void) 
{ 
    DWORD StartTick = GetTickCount(); 
    TestClass(0); 
    //TestClass(NUM_ALLOCS + 10); 
    //TestNew(); 
    DWORD EndTick = GetTickCount(); 

    printf("Time = %u ms\n", EndTick - StartTick); 
    printf("Last = %p\n", pLast); 

    return 0; 
} 

Attualmente sto ricevendo ~ 800ms sia per TestNew() e TestClass(0) e sotto 200ms per TestClass(NUM_ALLOCS + 10). L'allocatore personalizzato è piuttosto veloce in quanto opera sulla memoria in modo completamente lineare che consente alla memoria cache di funzionare con la sua magia. Sto anche usando GetTickCount() per semplicità ed è abbastanza preciso finché i tempi sono superiori a ~ 100ms.

Answer 2

È difficile essere certi con un codice così piccolo da studiare, ma sto scommettendo sulla località di riferimento. La tua bitmap con metadati non si trova sulla stessa cachella della memoria allocata stessa. E get_first_unset potrebbe essere una ricerca lineare.

Answer 3

Ora, so quanto sono complessi gli allocatori di memoria, non c'è modo che il codice possa essere eseguito più velocemente di una ricerca di array + un bit set, ma questo è esattamente il caso.

Questo non è nemmeno quasi corretto. Un heap di frammentazione bassa con bucket decente è O (1) con tempo costante molto basso (ed effettivamente zero overhead di spazio aggiuntivo). Ho visto una versione che arrivava a ~ 18 istruzioni asm (con un ramo) prima. Questo è molto meno del tuo codice. Ricorda, gli heap possono essere complessamente complessi, ma il percorso veloce che li attraversa potrebbe essere davvero, molto veloce.

Answer 4

Solo per riferimento, il codice seguente era il più performante per il problema in questione.

È un'implementazione semplice, ma raggiunge 1,7 secondi per 10 milioni di inserimenti e 1,4 secondi per un numero uguale di eliminazioni sul mio 2600K a 4,6 GHz.

#include "stdafx.h" 
#include <iostream> 
#include <crtdbg.h> 
#include <Windows.h> 
#include <malloc.h> 
#include <new> 

#ifndef NULL 
#define NULL 0 
#endif 

typedef int keytype; 
typedef unsigned long long UINT64; 

struct avlnode; 

struct avltree 
{ 
    avlnode *root; 
    avlnode *buffer; 
    avlnode *firstfree; 

    avltree() : avltree(0) {}; 
    avltree(UINT64 numitems); 

    inline avlnode *newnode(keytype key); 
    inline void deletenode(avlnode *node); 

    void insert(keytype key) { root = insert(root, key); } 
    void remove(keytype key) { root = remove(root, key); } 
    int height(); 
    bool hasitems() { return root != NULL; } 
private: 
    avlnode *insert(avlnode *node, keytype k); 
    avlnode *remove(avlnode *node, keytype k); 
}; 

#pragma pack(1) 
struct avlnode 
{ 
    avlnode *left;  //left pointer 
    avlnode *right; //right pointer 
    keytype key;  //node key 
    unsigned char hgt; //height of the node 

    avlnode(int k) 
    { 
    key = k; 
    left = right = NULL; 
    hgt = 1; 
    } 

    avlnode &balance() 
    { 
    struct F 
    { 
     unsigned char height(avlnode &node) 
     { 
     return &node ? node.hgt : 0; 
     } 
     int balance(avlnode &node) 
     { 
     return &node ? height(*node.right) - height(*node.left) : 0; 
     } 
     int fixheight(avlnode &node) 
     { 
     unsigned char hl = height(*node.left); 
     unsigned char hr = height(*node.right); 
     node.hgt = (hl > hr ? hl : hr) + 1; 
     return (&node) ? hr - hl : 0; 
     } 
     avlnode &rotateleft(avlnode &node) 
     { 
     avlnode &p = *node.right; 
     node.right = p.left; 
     p.left = &node; 
     fixheight(node); 
     fixheight(p); 
     return p; 
     } 
     avlnode &rotateright(avlnode &node) 
     { 
     avlnode &q = *node.left; 
     node.left = q.right; 
     q.right = &node; 
     fixheight(node); 
     fixheight(q); 
     return q; 
     } 
     avlnode &b(avlnode &node) 
     { 
     int bal = fixheight(node); 
     if (bal == 2) { 
      if (balance(*node.right) < 0) 
      node.right = &rotateright(*node.right); 
      return rotateleft(node); 
     } 
     if (bal == -2) { 
      if (balance(*node.left) > 0) 
      node.left = &rotateleft(*node.left); 
      return rotateright(node); 
     } 
     return node; // balancing is not required 
     } 
    } f; 
    return f.b(*this); 
    } 
}; 

avltree::avltree(UINT64 numitems) 
{ 
    root = buffer = firstfree = NULL; 
    if (numitems) { 
    buffer = (avlnode *) malloc(sizeof(avlnode) * (numitems + 1)); 
    avlnode *tmp = &buffer[numitems]; 
    while (tmp > buffer) { 
     tmp->right = firstfree; 
     firstfree = tmp--; 
    } 
    } 
} 

avlnode *avltree::newnode(keytype key) 
{ 
    avlnode *node = firstfree; 
    /* 
    If you want to support dynamic allocation, uncomment this. 
    It does present a bit of an overhead for bucket allocation though (8% slower) 
    Also, if a condition is met where bucket is too small, new nodes will be dynamically allocated, but never freed 
    if (!node) 
    return new avlnode(key); 
    */ 
    firstfree = firstfree->right; 
    return new (node) avlnode(key); 
} 

void avltree::deletenode(avlnode *node) 
{ 
    /* 
    If you want to support dynamic allocation, uncomment this. 
    if (!buffer) 
    delete node; 
    else { 
    */ 
    node->right = firstfree; 
    firstfree = node; 
} 

int avltree::height() 
{ 
    return root ? root->hgt : 0; 
} 

avlnode *avltree::insert(avlnode *node, keytype k) 
{ 
    if (!node) 
    return newnode(k); 
    if (k == node->key) 
    return node; 
    else if (k < node->key) 
    node->left = insert(node->left, k); 
    else 
    node->right = insert(node->right, k); 
    return &node->balance(); 
} 

avlnode *avltree::remove(avlnode *node, keytype k) // deleting k key from p tree 
{ 
    if (!node) 
    return NULL; 
    if (k < node->key) 
    node->left = remove(node->left, k); 
    else if (k > node->key) 
    node->right = remove(node->right, k); 
    else // k == p->key 
    { 
    avlnode *l = node->left; 
    avlnode *r = node->right; 
    deletenode(node); 
    if (!r) return l; 

    struct F 
    { 
     //findmin finds the minimum node 
     avlnode &findmin(avlnode *node) 
     { 
     return node->left ? findmin(node->left) : *node; 
     } 
     //removemin removes the minimum node 
     avlnode &removemin(avlnode &node) 
     { 
     if (!node.left) 
      return *node.right; 
     node.left = &removemin(*node.left); 
     return node.balance(); 
     } 
    } f; 

    avlnode &min = f.findmin(r); 
    min.right = &f.removemin(*r); 
    min.left = l; 
    return &min.balance(); 
    } 
    return &node->balance(); 
} 
using namespace std; 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    // 64 bit release performance (for 10.000.000 nodes) 
    // malloc:  insertion: 2,595 deletion 1,865 
    // my allocator: insertion: 2,980 deletion 2,270 
    const int nodescount = 10000000; 

    avltree &tree = avltree(nodescount); 
    cout << "sizeof avlnode " << sizeof(avlnode) << endl; 
    cout << "inserting " << nodescount << " nodes" << endl; 
    LARGE_INTEGER t1, t2, freq; 
    QueryPerformanceFrequency(&freq); 
    QueryPerformanceCounter(&t1); 
    for (int i = 1; i <= nodescount; i++) 
    tree.insert(i); 
    QueryPerformanceCounter(&t2); 
    cout << "Tree height " << (int) tree.height() << endl; 
    cout << "Insertion time: " << ((double) t2.QuadPart - t1.QuadPart)/freq.QuadPart << " s" << endl; 
    QueryPerformanceCounter(&t1); 
    while (tree.hasitems()) 
    tree.remove(tree.root->key); 
    QueryPerformanceCounter(&t2); 
    cout << "Deletion time: " << ((double) t2.QuadPart - t1.QuadPart)/freq.QuadPart << " s" << endl; 

#ifdef _DEBUG 
    _CrtMemState mem; 
    _CrtMemCheckpoint(&mem); 
    cout << "Memory used: " << mem.lTotalCount << " high: " << mem.lHighWaterCount << endl; 
#endif 
    return 0; 
}