Heap Performance
-
@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.
-
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; }
-
Ausgabe:
13671 ms (or usec) 444560896und das mit Winamp im Hintergrund :D.
OK, nich genau das gleiche. Aber momentan stört mich das nich.
-
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!
-
Pack ichs halt auf den Heap. Die 1 ms.
-
Auf den Heap gepackt. 2 Sekunden langsamer. Kann der Compiler weniger optimieren. War übrigens nie auf dem Stack. Das nur angemerkt. Ab wieder weg vom Heap.
Edit: Wahrscheinlich weniger als 2s. Bei nem neuen Test kam nur 1s raus.
[ Dieser Beitrag wurde am 03.12.2002 um 20:34 Uhr von Mr. N editiert. ]
-
Vergiß das mit den Referenzen nicht. Das ist doch einer der Hauptvorteile von nem GC. Da muss man dann in C++ halt ein bischen Aufwand betreiben.
-
Frage: Bei Veränderung wird die Referenz entkoppelt?
-
Original erstellt von Mr. N:
Frage: Bei Veränderung wird die Referenz entkoppelt?Was meinst du damit? Wenn es mehrere Referenzen auf ein Objekt gibt, dann gibt es nur ein Objekt. Wenn du daran etwas veränderst, dann ist es halt verändert. Egal, von welcher Referenz aus gesehen. Jede Referenz verweist dann auf das selbe veränderte Objekt.
-
System.arraycopy. Das meine ich. Wie ist es definiert? Zeig doch mal nen Ausschnitt aus der Referenz.
-
Original erstellt von Mr. N:
System.arraycopy. Das meine ich. Wie ist es definiert? Zeig doch mal nen Ausschnitt aus der Referenz.??? OK ???!!! :
arraycopy public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) Copies an array from the specified source array, beginning at the specified position, to the specified position of the destination array. A subsequence of array components are copied from the source array referenced by src to the destination array referenced by dest. The number of components copied is equal to the length argument. The components at positions srcPos through srcPos+length-1 in the source array are copied into positions destPos through destPos+length-1, respectively, of the destination array. If the src and dest arguments refer to the same array object, then the copying is performed as if the components at positions srcPos through srcPos+length-1 were first copied to a temporary array with length components and then the contents of the temporary array were copied into positions destPos through destPos+length-1 of the destination array. If dest is null, then a NullPointerException is thrown. If src is null, then a NullPointerException is thrown and the destination array is not modified. Otherwise, if any of the following is true, an ArrayStoreException is thrown and the destination is not modified: The src argument refers to an object that is not an array. The dest argument refers to an object that is not an array. The src argument and dest argument refer to arrays whose component types are different primitive types. The src argument refers to an array with a primitive component type and the dest argument refers to an array with a reference component type. The src argument refers to an array with a reference component type and the dest argument refers to an array with a primitive component type. Otherwise, if any of the following is true, an IndexOutOfBoundsException is thrown and the destination is not modified: The srcPos argument is negative. The destPos argument is negative. The length argument is negative. srcPos+length is greater than src.length, the length of the source array. destPos+length is greater than dest.length, the length of the destination array. Otherwise, if any actual component of the source array from position srcPos through srcPos+length-1 cannot be converted to the component type of the destination array by assignment conversion, an ArrayStoreException is thrown. In this case, let k be the smallest nonnegative integer less than length such that src[srcPos+k] cannot be converted to the component type of the destination array; when the exception is thrown, source array components from positions srcPos through srcPos+k-1 will already have been copied to destination array positions destPos through destPos+k-1 and no other positions of the destination array will have been modified. (Because of the restrictions already itemized, this paragraph effectively applies only to the situation where both arrays have component types that are reference types.) Parameters: src - the source array. srcPos - starting position in the source array. dest - the destination array. destPos - starting position in the destination data. length - the number of array elements to be copied. Throws: IndexOutOfBoundsException - if copying would cause access of data outside array bounds. ArrayStoreException - if an element in the src array could not be stored into the dest array because of a type mismatch. NullPointerException - if either src or dest is null.[ Dieser Beitrag wurde am 04.12.2002 um 22:31 Uhr von Gregor editiert. ]
-
@Gregor: ich hoffe natürlich, du testest die C++ programme auf höchster optimierungsstufe
-
Original erstellt von Mr. N:
@Gregor: ich hoffe natürlich, du testest die C++ programme auf höchster optimierungsstufe...immer mit -O3 beim g++!
...ich glaube aber, dass du auch generell nen besseren PC hast, als ich. Bei die ist ja alles schneller![ Dieser Beitrag wurde am 04.12.2002 um 22:32 Uhr von Gregor editiert. ]
-
@Gregor: :). Ehrlich gesagt erkenne ich nicht, wo Reference-Counting in deinem Programm zum Einsatz kommt.
-
Original erstellt von Mr. N:
@Gregor: :). Ehrlich gesagt erkenne ich nicht, wo Reference-Counting in deinem Programm zum Einsatz kommt.Vielleicht fällt es dir auf, wenn du dir dieses Programm mal anguckst:
[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;
}
}
System.out.println(sum);
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;
}
}
}
System.out.println(sum);
for (i = 1 ; i < 100 ; ++i)
{
System.arraycopy (array,0,array,i*10,10);
}
System.out.println(sum);
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][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]
Hier kommt nämlich etwas anderes raus als beim alten Programm. Beim alten Programm kommt 444560896 heraus, hier kommt 445031146 heraus.
-
peinlich, peinlich ;):
sum += array[element][k]; ++array[element][k];meinen tust du natürlich:
sum += array[element][k]++;
-
> 1 GB Speicherverbrauch ist nicht normal für deine Variante, oder?
-
Original erstellt von Mr. N:
> 1 GB Speicherverbrauch ist nicht normal für deine Variante, oder?Ich denke nicht! Java kann in denGrundeinstellungen nur 64 MB Speicher verbrauchen. Alles, was darüber liegt, ist prinzipiell nicht normal!
-
Das mit dem 1 GB ist jetzt behoben, jetzt kommt nur noch ne Access-Violation.
-
@Gregor: Hätte dir deine dumme Idee nicht früher einfallen können? Guck mal:
#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 }; inline 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; } inline 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] > 8192) { int i = 0; while (*x) { p = x; x = * (int **) x; delete [] p; cout << i << ": " << p << endl; i++; } Xu[size] = 0; } Xfree[size] = x; } int main() { const int size = 1000; 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; } int *ref[size]; int _ref[size] = { 0 }; for (i = 0; i < 10; ++i) { ref[i] = &_ref[i]; ++*ref[i]; } for (i = 10; i < size; ++i) { //Xdel(array[i], length[i]); array[i] = array[i % 10]; length[i] = length[i % 10]; ref[i] = ref[i % 10]; ++*ref[i]; } 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]++; if (--*ref[element] <= 0) { Xdel(array[element], length[element]); } array[element] = Xnew( length[element] = sizes[i % 7] ); ref[element] = &_ref[element]; _ref[element] = 1; for (k = 0; k < length[element]; ++k) array[element][k] = k; } cout << clock() - time << " ms (or usec)" << endl; cout << sum << endl; return 0; }Wird ein unglültiges Dingsie gefreed.