Heap Performance

Mr. N

Siehe D Thread.

#include <iostream>
#include <ctime>

using namespace std;

static int *list = 0;
static int u = 0;

int *_new(int v) {
    if (!list) return new int(v);
    else {
        int *result = list;
        list = *(int **)list;
        *result = v;
        --u;
        return result;
    }
}

void _delete(int *p) {
    if (!p) return;
    *(int **)p = list;
    list = p;
    if (++u > 819200) { 
        while (*list) {
            int *o = list;
            list = *(int **)list;
            delete o;
        }
        u = 0;
    }
}

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

Welche Zahlen kriegt ihr? Ich kriege diesen Output:

10000000 : 62
10000000 : 1375
10000000 : 1938
10000000 : 109

Mr. N

Das hier: Wie heißt der Nachfolger ...

10000000 : 210
10000000 : 2884
10000000 : 2854
10000000 : 210

davie

Ihr habt alle viel bessere Computer als ich ...

380
3900
4560
490

und nochmal der Code für alle, die nicht den M$VC haben

#include <iostream>
#include <ctime>
using namespace std;

static int *list = 0;
static int u = 0;
int *_new(int v) {
    if (!list) return new int(v);
    else {
        int *result = list;
        list = *(int **)list;
        *result = v;
        --u;
        return result;
    }
}
void _delete(int *p) {
    if (!p) return;
    *(int **)p = list;
    list = p;
    if (++u > 819200) { 
        while (*list) {
            int *o = list;
            list = *(int **)list;
            delete o;
        }
        u = 0;
    }
}
int main()
{
    int sum = 0; int *p = NULL;
    clock_t a = clock();
    for (int i = 0; i < 10000000; i++) {
        sum = *(p = _new(sum + 1));
        _delete(p);
    }
    clock_t b = clock();
    cout << sum << " : " << b - a << endl;
    sum = 0;
    p = 0;
    a = clock();
    for (int i = 0; i < 10000000; i++) {
        sum = *(p = new int(sum + 1));
        delete(p);
    }
    b = clock();
    cout << sum << " : " << b - a << endl;
    sum = 0;
    p = 0;
    a = clock();
    for (int i = 0; i < 10000; i++) {
        int *array[1000] = {0};
        for (int j = 0; j < 1000; j++)       
            sum = *(array[j] = new int(sum + 1));
        for (int j = 0; j < 1000; j++)
            delete(array[j]);
    }
    b = clock();
    cout << sum << " : " << b - a << endl;
    sum = 0;
    p = 0;
    a = clock();
    for (int i = 0; i < 10000; i++) {
        int *array[1000] = {0};
        for (int j = 0; j < 1000; j++)       
            sum = *(array[j] = _new(sum + 1));
        for (int j = 0; j < 1000; j++)
            _delete(array[j]);
    }
    b = clock();
    cout << sum << " : " << b - a << endl;
    return 0;
}

Gregor

EDIT : Sieht so aus, als ob du die Testklasse wegoptimiert hast! ...sieht nach Schummeln aus! :p

[ Dieser Beitrag wurde am 02.12.2002 um 04:54 Uhr von Gregor editiert. ]

Gregor

...und damit ihr nicht immer so speziell optimiert kommt hier ein kleines Java-Programm, das gerade meinem kranken Hirn entsprungen ist. Da sollte das Optimieren etwas schwerer sein. Ihr könnt ja mal versuchen, das nach C++ zu portieren. Die int-Arrays sind alle auf dem Heap, sollten also auch in C++ alle auf dem Heap sein.
[java]
public class TestMemory
{

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

public static void main (String [] args)
{
int size = 1000;
int [][] array = new int [size][];
int [] sizes = {2,3,5,7,11,13,17};
int i,j,k,element;
int sum = 0;
long time = System.currentTimeMillis ();
for (i = 0 ; i < size ; ++i)
{
array [i] = new int [i%10];
for (j = 0 ; j < array[i].length ; ++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 < array[element].length ; ++k)
{
sum += array[element][k];
}
array[element] = new int [sizes[i%sizes.length]];
for (k = 0 ; k < array[element].length ; ++k)
{
array[element][k] = k;
}
}
}
for (i = 1 ; i < 100 ; ++i)
{
System.arraycopy (array,0,array,i*10,10);
}
for (i = 100000 ; i > 0 ; --i)
{
for (j = 0 ; j < 5000000 ; j+=i)
{
element = j%size;
for (k = 0 ; k < array[element].length ; ++k)
{
sum += array[element][k];
}
array[element] = new int [sizes[i%sizes.length]];
for (k = 0 ; k < array[element].length ; ++k)
{
array[element][k] = k;
}
}
}
array = null;
System.gc();
System.out.print(System.currentTimeMillis () - time);
System.out.println (" ms");
System.out.println(sum);
}

}[/code]

EDIT : Ein Array ist in Java übrigens ein Objekt. Vielleicht müßt ihr euch auch ne Klasse schreiben, um das vernünftig nachbilden zu können.

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

[ Dieser Beitrag wurde am 02.12.2002 um 05:24 Uhr von Gregor editiert. ]

volkard

Original erstellt von Gregor:
Die int-Arrays sind alle auf dem Heap, sollten also auch in C++ alle auf dem Heap sein.

Ähm.
int [] sizes = {2,3,5,7,11,13,17};
Soll man in C++ auf den Heap legen? Das bringt keiner fertig. Außerdem darf der Java-Optimierer auf den Stack legen, sobald er sieht, daß das Array so winzig ist und seine Größe icht ändert.

Gregor

Original erstellt von volkard:
**
Ähm.
int [] sizes = {2,3,5,7,11,13,17};
Soll man in C++ auf den Heap legen? Das bringt keiner fertig. Außerdem darf der Java-Optimierer auf den Stack legen, sobald er sieht, daß das Array so winzig ist und seine Größe icht ändert.**

OK! Meinetwegen dürft ihr das auf den Stack legen! ...allerdings traue ich es dem Java-Optimierer eigentlich garnicht zu, dass er sowas auf den Stack legt. Kann sein, dass ich da ne Wissenslücke habe.

Aber was ist daran so schwer, sich sowas auf den Heap zu legen. ...sieht doch nur unschön aus :

int * sizes = new int [7];
sizes[0] = 2;
sizes[1] = 3;
...

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

Gregor

...ich bin ja gespannt, wie man da einige Dinge in C++ überhaupt machen kann. Ich könnte das zumindest nicht in C++ schreiben. ...vielleicht lerne ich ja etwas aus dem C++-Programm! ...wenn eins kommt!

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!