Heap Performance

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

[TRAURIG]

seid ihr echt nicht fähig mal ein vergleichbares programm hinzubekommen in c++ und java?

[Mr. N]

Original erstellt von <TRAURIG>:
seid ihr echt nicht fähig mal ein vergleichbares programm hinzubekommen in c++ und java?

ist doch vergleichbar. oder wie?

[Gregor]

Kommt jetzt das Richtige raus? ...es stört mich, dass du die Probleme, die ich dir gestellt habe, einfach umgangen hast. Da muss ich mir wohl was besseres einfallen lassen.

[Mr. N]

@Gregor: Ich hätte auch cout << "0 ms\nresultat" << endl; machen können (resultat: das gewünschte ergebnis). Das mit den Referenzen ist ne andere Sache. Man könnte da so einiges machen.

[Gregor]

Original erstellt von Mr. N:
ist doch vergleichbar. oder wie?

Nein! Du machst viele Dinge anders! :p Wie schon gesagt : Ein Array isz in Java ein Objekt. Schreib dir doch mal ne Array-Klasse, die auch ein Element "length" enthält.

EDIT : Außerdem ist dein äußeres Array nichtmal auf dem Heap.

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

[WÜTEND]

ist doch vergleichbar. oder wie?

Nein, es wird da überhaupt nicht klar wie langsam Java ist.

[Gregor]

Original erstellt von <WÜTEND>:
Nein, es wird da überhaupt nicht klar wie langsam Java ist.

Nur, dass das klar ist. Hier soll eigentlich nicht Java mit C++ verglichen werden. Es geht um die Performance on C++ auf dem Heap. Ich hatte mal behauptet, dass man da mit nem Garbage Collector schneller ist. Im ursprünglichen Thread ging es um D und nicht um Java. Java wird hier nur genutzt, weil es nen Garbage Collector hat.

[Mr. N]

@Gregor: Wieso sollte ich so blöd sein und das äußere Array auf den Heap tun? Und selbst wenn, die Milliskeunde ändert da auch nix. Ich überleg gerade heftig Strategien zum Optimieren. KA Y, aber ich werde woll (unvernünftigerweise) keine Klasse nehmen.

[Mr. N]

Schon relativ gut:

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

using namespace std;

/* Analysis:
Occurences of 'new's:
0: 100
1: 100
2: 14506287
3: 24201675
4: 100
5: 18946842
6: 100
7: 17061342
8: 100
9: 100
11: 16037221
13: 15367557
17: 14882188
*/

int *Xfree[18] = { 0 };
int Xu[18] = { 0 };

int *Xnew(size_t size) {
    if (size < 1 || size > 17 || !Xfree[size]) return new int[size];
    int *result = Xfree[size];
    Xfree[size] = * (int **) Xfree[size];
    --Xu[size];
    return result;
}

void Xdel(int *p, size_t size) {
    if (size < 1 || size > 17) { delete [] p; return; }
    int *x = Xfree[size];
    *(int **)p = x;
    x = p;
    if (++Xu[size] > 819200) {
        while (*x) {
            p = x;
            x = * (int **) x;
            delete [] p;
        }
        Xu[size] = 0;
    }
    Xfree[size] = x;
}

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;
    size_t length[size] = {0};
    long sum = 0;
    clock_t time = clock();
    for (i = 0; i < size; ++i) {
        int s = i % 10;
        array[i] = Xnew(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];
            Xdel(array[element], length[element]);
            array[element] = Xnew( length[element] = sizes[i % 7] );
            for (k = 0; k < length[element]; ++k) 
                array[element][k] = k;
        }
    for (i = 10; i < size; ++i) {
        Xdel(array[i], length[i]);
        array[i] = Xnew( 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];
            Xdel(array[element], length[element]);
            array[element] = Xnew( 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]

Ausgabe:

13671 ms (or usec)
444560896

und das mit Winamp im Hintergrund :D.
OK, nich genau das gleiche. Aber momentan stört mich das nich.

[Gregor]

Bei mir sind es 33 Sekunden. ...und ich werde mir gleich mal was ausdenken, wo du nicht mehr so gut schummeln kannst. ...zumindest wird es noch ein Stück schwerer sein, als hier. Du wolltest Heap-Performance-Testen. Was machst du? Du stellst alles Mögliche auf den Stack!

[Mr. N]

Pack ichs halt auf den Heap. Die 1 ms.