Heap Performance

Mr. N

@Gregor: Und du darfst versuchen, mein Progrämmchen (ohne die spezifischen Sachen, nur den Grund Benchmark) auf Java zu portieren :P. Den (deinen) Java Code zu verstehen bräucht ich schoma n halbes Stündchen.

Mr. N

Entschuldigung, aber den Code find ich _leicht_ merkwürdig:

for (i = 0; i < size; ++i)
      {
         array[i] = new int[i % 10];
         for (j = 0; j < array[i].length; ++j)
            array[i][j] = j;
      }

(stilistisch angepasst :D)

new int[0]? unlogisch.

[ Dieser Beitrag wurde am 02.12.2002 um 20:42 Uhr von Mr. N editiert. ]

Gregor

Original erstellt von Mr. N:
**
new int[0]? unlogisch.**

Warum? Ein Array ist in Java ein Objekt. Insofern ist es kein Problem, sich ein Array mit 0 Elementen zu erstellen. ...du kannst ja statt nem Array nen Vektor nehmen! ...der kann ja auch mal leer sein.

...nachher werde ich mir mal deinen Code genauer ansehen und gucken, ob ich das nach Java portieren kann. Ich sehe da auch schon einige Probleme!

[ Dieser Beitrag wurde am 02.12.2002 um 20:42 Uhr von Gregor editiert. ]

Mr. N

@Gregor: Ich tu mal das java-irrelevante aus dem Code raus.

Mr. N

So. Das sollte halbwegs portierbar sein: (die Tricks sind eben nich eingebaut)

#include <iostream>
#include <ctime>

using namespace std;

int main()
{
    int sum = 0; int *p = NULL; int i;
    clock_t a = clock();
    for (i = 0; i < 10000000; i++) {
        sum = *(p = new int(sum + 1));
        delete(p);
    }
    clock_t b = clock();
    cout << sum << " : " << b - a << endl;
    sum = 0;
    p = 0;
    a = clock();
    for (i = 0; i < 10000; i++) {
        int *array[1000] = {0};
        for (int j = 0; j < 1000; j++)       
            sum = *(array[j] = new int(sum + 1));
        for (j = 0; j < 1000; j++)
            delete(array[j]);
    }
    b = clock();
    cout << sum << " : " << b - a << endl;
    return 0;
}

Gregor

Original erstellt von Mr. N:
@Gregor: Ich tu mal das java-irrelevante aus dem Code raus.

Mir ist schon klar, was ich alles portieren muss und was nich! Das Problem ist nur, dass man in Java keine primitiven Datentypen auf den Heap werfen kann. Ich glaube, du machst das irgendwo. Da muss ich also entweder nem Wrapper nehmen, der viel Größer ist, oder ich muss mir was einfallen lassen. ...wahrscheinlich werde ich das mit nem Array lösen.

Mr. N

Keine primitiven Typen auf den Heap? So ne Scheiße. Nix Array. Zur Not schreibst du ne class à la:
[java]
class T {
private int i;
// Konstruktor, etc.
}
[/code]

Mr. N

Soweit so gut. Beim Portieren ist mir folgendes unbekanntes aufgefallen (bja würde sagen: Syntax Error :D):
[java]
System.arraycopy (array,0,array,i*10,10);
[/code]

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

straight-forward

das heisst?

Mr. N

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

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

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