3. Array exceeded erkennen

Array exceeded erkennen

  • ?

    Ich habs mit devc und builder6 pro getestet.
    Beides nahezu identisch.

    0
  • ?

    Also ich möchte mal meine persönliche Lösung vorschlagen:

    boost::array verwenden, das ist _garantiert_ nicht langsamer wie ein normales C-Array (denn es ist nichts anderes als ein normales C-Array) und bietet Methoden wie size() und assign() an. Außerdem hab ich im Index-Operator ein assert (wieder keine Verlangsamung der Laufzeit) eingebaut, dass prüft, ob der Index gültig ist.
    Damit hat man auch immer noch den Unterschied zu at(), weil [] dann nur beim Debug-Build prüft und sonst genauso schnell ist wie ein normaler Array-Zugriff.
    Sollte jetzt irgendjemand nachmessen und feststellen, dass boost::array langsamer ist wie ein normales Array, dann kann er entweder nicht gescheit messen oder hat nen Drecks-Compiler. :p

    0
  • C

    noproblem schrieb:

    Beweis ???

    int main()
	int* atest = new int[1];
	vector<int> vtest(1);
	vtest[0] = 0;
	atest[0] = 0;
}

    Ergibt bei VC++ 6 und STLPort:

    /* vtest[0] = 0; */
:0040105C 8B4DE0                  mov ecx, dword ptr [ebp-20]
:0040105F C70100000000            mov dword ptr [ecx], 00000000
/* atest[0] = 0; */
:00401065 8B45EC                  mov eax, dword ptr [ebp-14]
:00401068 C70000000000            mov dword ptr [eax], 00000000

    Jetzt verrat mir mal, warum die zweite Zeile schneller als die erste sein sollte.

    0
  • ?

    @cd9000

    Dann vermag VC++ diese lobenswerte Optimierung.
    Andere Compiler anscheinend nicht.

    0
  • ?

    @cd: Ich weiss, es klingt seltsam, aber bei mir ist ein std::vector manchmal wirklich langsamer beim Elementzugriff als ein C-Array, auch im Release-Build mit allen Optimierungen und auto-inline.
    Ich hab da nicht weiter nachgeforscht, sondern einfach nur mal vector durch boost::array ersetzt und hatte einen registrierbaren Laufzeitgewinn.

    Kann (und wird) natürlich wirklich am Compiler oder der Implementierung liegen.

    0
  • A

    noproblem schrieb:

    Gerade mal getestet 1000 * 50000 Elemente schreiben (Typ Integer)

    vector: 0,671 s
    int array:0,55 s

    Ist ja wohl auch logisch das der Zugriff auf einen natürlichen Datentypen schneller vonstatten geht.

    Poste doch mal bitte die Listings. Würde mich interessieren, wie du es gecodet hast.

    0
  • C

    noproblem schrieb:

    Dann vermag VC++ diese lobenswerte Optimierung.
    Andere Compiler anscheinend nicht.

    Ich kann das leider gerade nicht testen, aber gcc beherrscht das ziemlich sicher auch. Ist ja eigentlich auch nicht viel mehr als inlining von Funktionen. Der Code für operator[] steht in <vector>, und das sollte nicht viel mehr sein als "return *(_array + index)".
    Ich wage mal zu behaupten, dass die meisten Compiler hier inlining anwenden können.

    0
  • J
     

    #include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
   const int size = 1024*2;
   long long start, end;
   int array[size];
   vector<int> vektor(size); 

   int sum = 0;
   for(int i=0;i<1000;++i)
   {
      for(int j=0;j<size;++j)
      { array[j] = rand(); }

      __asm__ __volatile__ ("rdtsc"
               : "=A" (start)  );

      sort(array, array+size); // dann halt =)

      __asm__ __volatile__ ("rdtsc"
               : "=A" (end) );

      sum += end-start;
   }

   cout << "array:  " << sum/100 << endl;

   sum = 0;
   for(int i=0;i<1000;++i)
   {
      for(int j=0;j<size;++j)
      { vektor[j] = rand(); }

      __asm__ __volatile__ ("rdtsc"
               : "=A" (start)  );

      sort(vektor.begin(), vektor.end());

      __asm__ __volatile__ ("rdtsc"
               : "=A" (end) );

      sum += end-start;
   }

   cout << "vector: " << sum/100 << endl; 
}

    lässt sich im gcc kompilieren:

    ohne optionen kompiliert:
array:  10993013
vector: 14753069

mit -O3 kompiliert:
array:  5463807
vector: 4693533

    woher der vector den speedvorteil mit der optimierung nimmt kann ich mir aber echt nicht erklären.

    0
  • O

    ähm hüstel, was bedeuted bei dir das, was hintre __asm__ steht? berechnest du damit die vergangene zeit? wenn ja, wie?

    0
  • J

    otze schrieb:

    ähm hüstel, was bedeuted bei dir das, was hintre __asm__ steht? berechnest du damit die vergangene zeit? wenn ja, wie?

    das ist gcc inline assembler syntax. rdsc gibt irgend so einen hochpräzisen cpu-internen counter zurück. läuft nur auf x86 prozis glaub ich.

    0
  • O

    wärs nich effektiver, wenn man start dann berechnet, bevor der vector gefüllt wird?

    0
  • J

    otze schrieb:

    wärs nich effektiver, wenn man start dann berechnet, bevor der vector gefüllt wird?

    wozu denn? ich will ja nur stoppen, wie schnell er die arrays sortiert. bei der füllschleife dürfte das rand mehr zeit verbrauchen als der arrayzugriff.

    0
  • S

    @japro:
    wenn wir von dem undefinierten verhalten (&array[size]) mal absehen: natürlich kann es am stack schneller sein als am heap - muss aber nicht. Umgekehrt geht es genauso.

    probier das ganze mal mit dynamischen arrays - dann hat sich bei mir die sache sogar umgedreht (liegt aber an dem schwankenden zeiten für memory zugriff)

    std::vector ist natürlich _kein_ ersatz für fixe Arrays - denn dafür gibt es boost::array

    0
  • J

    ist das verhalten echt undefiniert? ich meine da findet ja kein zugriff statt. sind nur adressen die da sind...
    habs mal mit arrays probiert, die mit new allokiert wurden. das resultat ist jedes mal anders und man kann irgendwie nicht mehr ausmachen welche version schneller ist. hättes es aber ehrlichgesagt nicht erwartet, dass per new allokierte arrays schneller als solche auf dem stack sind. jedenfalls beim sortieren.

    array:  4378737
vector: 5325541

array:  4781590
vector: 3654554

array:  5451583
vector: 4000206

array:  4783789
vector: 4918830

array:  5259833
vector: 4658281
    0
  • S

    japro schrieb:

    ist das verhalten echt undefiniert? ich meine da findet ja kein zugriff statt. sind nur adressen die da sind...

    array[size] dereferenziert.
    natürlich wird der compiler ein
    &array[size]
    zu einem
    array+size
    optimieren - aber das ändert nix an dem undefinierten verhalten.

    0
  • O

    @jaspro 1000 mal durchlaufen alssen, und dann den durchschnitt bilden, anders haste da keine chance an nen halbwegs aussagekräftigen wert zu kommen..

    0
  • A

    Ich habe natürlich auch einen Vergleichstest gemacht, und letztendlich ist es egal ob man array oder vector nimmt. Mal ist das eine schneller, mal das andere, und mal sind sogar beide gleich schnell. Das die Zeiten jedesmal unterschiedlich sind, liegt wohl am Multitasking u.a. Einflüssen des Systems.

    #include <Windows.h>
#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char* argv[])
{
	vector<int> vec;
	vec.reserve(500000);

	// ---
	unsigned long startTime = GetTickCount();
	for(int i=0; i<500000; i++)
	{
		vec[i] = 200;
	}
	unsigned long endTime = GetTickCount();
	// ---

	cout << "vector\nstartTime: " << startTime << ", endTime: " << endTime << ", time: " << endTime - startTime << endl;
         return 0;
}

    Und für Arrays:

    #include <Windows.h>
#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char* argv[])
{
         int *array = new int[500000];

	// ---
	unsigned long startTime2 = GetTickCount();
	for(int i=0; i<500000; i++)
	{
		array[i] = 200;
	}
	unsigned long endTime2 = GetTickCount();
	// ---
	cout << "array\nstartTime: " << startTime2 << ", endTime: " << endTime2 << ", time: " << endTime2 - startTime2 << endl;*/

	return 0;
}

    Ergebnisse nach mehreren starts im Kommandofenster unter Win2000pro, compiliert mit VC++6.0 Standard-Edition:

    10 und 20 ms, sowohl Array als auch der Vector haben immer diese Zeiten rausgebracht.

    Habs auch noch mit 5000000 ausprobiert, Ergebnis bei beiden: immer um ca. 140ms.

    Habs auch noch mit 50000000 ausprobiert, Ergebnis bei beiden: immer um ca. 1300ms.

    0
  • J

    otze schrieb:

    @jaspro 1000 mal durchlaufen alssen, und dann den durchschnitt bilden, anders haste da keine chance an nen halbwegs aussagekräftigen wert zu kommen..

    dann schau dir mal mein programm nochmal an 😃

    0
  • ?

    Zeitunterschiede von 10ms sind aber nicht sehr aussagekräftig, insbesondere, weil GetTickCount() manchmal wirklich nur ne Auflösung von mehreren ms hat. Da musst du IMO schon auf ein paar Sekunden kommen, um halbwegs repräsentative Werte zu erreichen.

    0
  • S

    Optimizer schrieb:

    Zeitunterschiede von 10ms sind aber nicht sehr aussagekräftig, insbesondere, weil GetTickCount() manchmal wirklich nur ne Auflösung von mehreren ms hat. Da musst du IMO schon auf ein paar Sekunden kommen, um halbwegs repräsentative Werte zu erreichen.

    GetTickCount hat ne Auflösung von etwa 54ms (IIRC)
    weiters optimiert der VC++ Standard nicht.

    und statt reserver muss man resize verwenden, auch wenn das hier keine rolle spielen sollte.

    0
Anmelden zum Antworten