Heap Performance

Mr. N

Hehe. Versehentlich j++ statt j += i;

Mr. N

Das guut Code sei:

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cassert>

using namespace std;

int main()
{
    const int size = 1000;
    static int *array[size];
    const int sizes[] = { 2, 3, 5, 7, 11, 13, 17 };
    int length[size] = {0};
    unsigned long sum = 0;
    clock_t time = clock();
    int i;
    for (i = 0; i < size; ++i) {
        int s = i % 10;
        array[i] = new int[s];
        length[i] = s;
        for (int j = 0; j < s; ++j)
            array[i][j] = j;
    }
    for (i = 1; i < 100000; ++i)
        for (int j = 0; j < 5000000; j += i) {
            int element = j % size;
            int k;
            for (k = 0; k < length[element]; ++k) 
                sum += array[element][k];
            delete [] array[element];
            array[element] = new int[ length[element] = sizes[i % 7] ];
            for (k = 0; k < length[element]; ++k) 
                array[element][k] = k;
        }
    for (i = 10; i < size; ++i) {
        delete [] array[i];
        array[i] = new int[ length[i] = length[i % 10] ];
        memcpy(array[i], array[i % 10], length[i]);
    }
    for (i = 100000; i > 0; --i)
        for (int j = 0; j < 5000000; j += i) {
            int element = j % size, k;
            for (k = 0; k < length[element]; ++k)
                sum += array[element][k];
            delete [] array[element];
            array[element] = new int[ length[element] = sizes[i % 7] ];
            for (k = 0; k < length[element]; ++k)
                array[element][k] = k;
        }
    cout << clock() - time << " ms (or usec)" << endl;
    cout << sum << endl;
    return 0;
}

Mr. N

Output:

26906 ms (or usec)
3963054733

27 Sekunden. Unhandoptimiert

Gregor

...und bei mir kommt mit "j += i" folgendes heraus :

144 Sekunden, 1054756072

Weder dein Ergebnis, noch dieses hier stimmt mit dem der Vorgabe überein! ...scheint also doch nicht so ganz straight-Forward zu sein, gell?

Wie wir gerade im C++ Forum erfahren haben soll clock ja garnicht sinnvoll sein!

Mr. N

Original erstellt von <clock clock>:
Wie wir gerade im C++ Forum erfahren haben soll clock ja garnicht sinnvoll sein!

???

Gregor

Original erstellt von <clock clock>:
Wie wir gerade im C++ Forum erfahren haben soll clock ja garnicht sinnvoll sein!

Warum? Zu ungenau? Hier interessieren doch eh nicht die Millisekunden.

funktion, die die laufzeit des programms wiedergibt

Da steht was davon, das auch minütliche Unterschiede entstehen können

Mr. N

Nicht bei unseren Programmen.

MrN--;

Mr. N

Original erstellt von < >:
MrN--;

Öhm. Meine Antwort ist doch nicht gelogen, oder irgendwie falsch? Wie soll ich das verstehen? Als persönlichen, ungerechtfertigten Angriff?

Als unoptimierte! Abwertung.

Mr. N

@Gregor: auf was ist sum nach jedem Beenden einer for (i...) schleife gesetzt?
/me kriegt für das hier

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cassert>

using namespace std;

int main()
{
    const int size = 1000;
    static int *array[size];
    const int sizes[] = { 2, 3, 5, 7, 11, 13, 17 };
    int i, j, k, element;
    int length[size] = {0};
    unsigned long sum = 0;
    clock_t time = clock();
    for (i = 0; i < size; ++i) {
        int s = i % 10;
        array[i] = new int[s];
        length[i] = s;
        for (j = 0; j < s; ++j)
            array[i][j] = j;
    }
    cout << sum << endl;
    for (i = 1; i < 100000; ++i)
        for (j = 0; j < 5000000; j += i) {
            element = j % size;
            for (k = 0; k < length[element]; ++k) 
                sum += array[element][k];
            delete [] array[element];
            array[element] = new int[ length[element] = sizes[i % 7] ];
            for (k = 0; k < length[element]; ++k) 
                array[element][k] = k;
        }
    cout << sum << endl;
    for (i = 10; i < size; ++i) {
        delete [] array[i];
        array[i] = new int[ length[i] = length[i % 10] ];
        memcpy(array[i], array[i % 10], length[i]);
    }
    cout << sum << endl;
    for (i = 100000; i > 0; --i)
        for (j = 0; j < 5000000; j += i) {
            element = j % size, k;
            for (k = 0; k < length[element]; ++k)
                sum += array[element][k];
            delete [] array[element];
            array[element] = new int[ length[element] = sizes[i % 7] ];
            for (k = 0; k < length[element]; ++k)
                array[element][k] = k;
        }
    cout << sum << endl;
    cout << clock() - time << " ms (or usec)" << endl;
    cout << sum << endl;
    return 0;
}

folgenden output:

0
2369722731
2369722731
3765571316
26718 ms (or usec)
3765571316

Mr. N

Original erstellt von < >:
Als unoptimierte! Abwertung.

Tut mir leid, da ich nicht verstehe, warum, kann ich _diese_ Erklärung nicht akzeptieren.

Gregor

Es gibt Überläufe, die aber wohl auf bei beiden Programmen gleich sein sollten:

0
-1925244565
-1925244565
56411 ms
444560896

Mr. N

@Gregor: bei dir fehlt da noch eins :). unsigned weg und:

0
-1925244565
-1925244565
-529395980
28296 ms (or usec)
-529395980

wo der fehler (?) liegen müsste, is jetz klarer

Mr. N

Dieser Code, macht der das gleiche wie dein arraycopy? Kannst du das Arraycopy nich auch selber schreiben?

for (i = 10; i < size; ++i) {
        delete [] array[i];
        array[i] = new int[ length[i] = length[i % 10] ];
        memcpy(array[i], array[i % 10], length[i]);
    }

[ €dit: Zu früh geklickt ]

[ Dieser Beitrag wurde am 03.12.2002 um 18:27 Uhr von Mr. N editiert. ]

Gregor

Nein! Er macht nicht das Gleiche. Darauf habe ich schon hingewiesen. Du hast mit diesem Code ein Problem umgangen, das real existiert. Nämlich, dass man nicht so leicht weiß, wann die letzte Referenz auf ein Objekt gelöscht wurde. Du hast halt nicht Referenzen kopiert, sondern die ganzen Arrays.

EDIT : Hast du vielleicht auch noch Source und Destination vertauscht?

[ Dieser Beitrag wurde am 03.12.2002 um 18:33 Uhr von Gregor editiert. ]

Mr. N

Ich meinte eigentlich effektiv das gleiche.

Mr. N

Problem erkannt, Problem gebannt:

#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

int main()
{
    const int size = 1000;
    static int *array[size];
    const int sizes[] = { 2, 3, 5, 7, 11, 13, 17 };
    int i, j, k, element;
    int length[size] = {0};
    long sum = 0;
    clock_t time = clock();
    for (i = 0; i < size; ++i) {
        int s = i % 10;
        array[i] = new int[s];
        length[i] = s;
        for (j = 0; j < s; ++j)
            array[i][j] = j;
    }
    for (i = 1; i < 100000; ++i)
        for (j = 0; j < 5000000; j += i) {
            element = j % size;
            for (k = 0; k < length[element]; ++k) 
                sum += array[element][k];
            delete [] array[element];
            array[element] = new int[ length[element] = sizes[i % 7] ];
            for (k = 0; k < length[element]; ++k) 
                array[element][k] = k;
        }
    for (i = 10; i < size; ++i) {
        delete [] array[i];
        array[i] = new int[ length[i] = length[i % 10] ];
        memcpy(array[i], array[i % 10], length[i] * sizeof(int));
    }
    for (i = 100000; i > 0; --i)
        for (j = 0; j < 5000000; j += i) {
            element = j % size;
            for (k = 0; k < length[element]; ++k)
                sum += array[element][k];
            delete [] array[element];
            array[element] = new int[ length[element] = sizes[i % 7] ];
            for (k = 0; k < length[element]; ++k)
                array[element][k] = k;
        }
    cout << clock() - time << " ms (or usec)" << endl;
    cout << sum << endl;
    return 0;
}

JETZT kann ich optimieren.