Heap Performance

[Gregor]

Das macht folgendes (das ist das fieseste am ganzen Code) :):

Es wird etwas von array zu array kopiert. Und zwar von Position 0 zu position i*10. ...und zwar werden 10 Elemente kopiert. Da in dem Array Referenzen sind, werden also Referenzen kopiert und somit vervielfältigt. Allerdings nur die Referenzen. Nicht die Objekte (Arrays), die an den Referenzen dranhängen.

EDIT : Wenn i = 1 ist, dann werden also die Elemente 0-9 nach 10-19 kopiert. Wenn i = 2 ist, dann werden die Elemente 0-9 nach 20-29 kopiert.

[ Dieser Beitrag wurde am 02.12.2002 um 21:12 Uhr von Gregor editiert. ]

[Mr. N]

Das heißt, das ganze Array wird mit array[0..9] gefüllt?
Gilt dann: array[i] = array[i % 10]?

[Gregor]

Jo!

[Mr. N]

So ausgedrückt: Direkt portiert ist der Code nicht direkt schnell. Wie sieht deine Zeit uas?

[Gregor]

ungefähr eine Minute.

Zeig mal Code! ...mich interessiert, wie man das mit den multiplen Referenzen macht. Man weiß ja nicht, wann ein Objekt gelöscht werden kann.

[ Dieser Beitrag wurde am 02.12.2002 um 22:13 Uhr von Gregor editiert. ]

[Mr. N]

Der is extrem straight-forward:

#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};
    int 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) {
            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;
}

[vollkorn]

straight-forward

das heisst?

[Mr. N]

straight-forward: hier: eine ziemlich "direkte" umsetzung

[vollkorn]

Geil danke! Dann können wir es Gregor endlich zeigen.
Aber könnt ihr nicht mal Kommantare in den Code einfügen?

[Gregor]

Irre ich mich, oder ist "array" nicht auf dem Heap?

...außerdem scheinst du keine Referenzen zu kopieren, sondern die ganzen Arrays.

[ Dieser Beitrag wurde am 02.12.2002 um 22:26 Uhr von Gregor editiert. ]

[Irren ist menschlich]

Du hast dich bis jetzt immer geirrt. Warum nicht auch jetzt?

[Gregor]

Original erstellt von <vollkorn>:
**Geil danke! Dann können wir es Gregor endlich zeigen.
**

Ich habe das jetzt mal gestartet und ahne schon, dass das mit dem Zeigen wohl erstmal nichts wird! :p

[Gregor]

So! Das C++-Programm arbeitet jetzt schon 2 Stunden. Ich breche das jetzt ab. So, wie das C++-Programm momentan ist, braucht es zumindest sehr viel länger als das Java Programm. Es benötigt zumindest weit mehr als die 100fache Zeit. Aber ich denke mal, aus dem C++-Programm kann man noch ne Menge rausholen.

Volkard wollte da ja noch was programmieren, was so ein Programm sehr deutlich beschleunigt. ...im neuen Jahr. Da bin ich mal gespannt.

[Gregor]

Hier der Java-Code für das, was du geschrieben hast. ...also das, was du ganz am Schluss geschrieben hast.
[java]
public class TestHeap
{

/** Creates a new instance of TestHeap */
public TestHeap ()
{
}

/**
* @param args the command line arguments
*/
public static void main (String[] args)
{
MyInt sum = new MyInt(0);
int i,j;
long time = System.currentTimeMillis ();
for (i = 0; i < 10000000; ++i)
{
sum = new MyInt (sum.i +1);
}
System.out.print (sum.i);
System.out.print (" : ");
System.out.println (System.currentTimeMillis () - time);
sum = new MyInt(0);
time = System.currentTimeMillis ();
MyInt [] array;
for (i = 0; i < 10000; ++i)
{
array = new MyInt[1000];
for (j = 0; j < 1000; ++j)
{
sum = array[j] = new MyInt(sum.i + 1);
}
}
System.out.print (sum.i);
System.out.print (" : ");
System.out.println (System.currentTimeMillis () - time);
}

private static final class MyInt
{
public int i;
MyInt(int i)
{
this.i = i;
}
}
}[/code]

Ergebnis :

10000000 : 351
10000000 : 561

...und das C++-Programm (Variante von Noesis) :

220
8762
14652
370

[ Dieser Beitrag wurde am 03.12.2002 um 01:03 Uhr von Gregor editiert. ]

[Mr. N]

Wie man sieht, ist Java geringfügig lagsamer als der hier handoptimierte Code :). Ich setz mich jetz nochmal an den Gregor-Code und schau, warum der so lahm is. Vielleicht ja auch ne Endlosschleife.

[Mr. N]

Ich sehe gerade, Gregor hat keine straight-forward java Version gepostet. Die möchte ich auch sehen.

[Gregor]

Original erstellt von Mr. N:
Ich sehe gerade, Gregor hat keine straight-forward java Version gepostet. Die möchte ich auch sehen.

Was meinst du?

[Mr. N]

Original erstellt von Gregor:
Was meinst du?

Nix
Das mit dem Array auf den Heap find ich nur gewöhnungsbedürftig.

Hmm. Dieser Code:

for (i = 100000; i > 0; --i)
    for (int j = 0; j < 5000000; ++j)
        sum = (sum + sum % 4) % 6;

Rechnet ziemlich lange. Mal sehen, ob die Zahlen in Gregors Progrämmchen stimmen.

[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;
}