Array exceeded erkennen

@Shade of Mine

Schau mal da:http://www.c-plusplus.net/forum/viewtopic.php?t=39460

Dann siehst du was ich meine.

japro

noproblem schrieb:

Es geht dabei vor allem um das einfügen und löschen, was extrem viel Zeit verbraten tut.Beim lesen und schreiben habe ich bisher noch keinen Unterschied gemessen, müsste man mal testen.

öhm? hö? wie kann man etwas schneller in ein array einfügen oder löschen als in einem vector? für ein array muss man das alles aufwendig selber coden. und auch dann ist der vector nur dann wesentlich langsamer wenn die grösse angepasst werden muss. und das kann man bei einem statischen array bekanntlich garnicht.

Shade Of Mine

was willst du mir damit sagen?

japro

Shade Of Mine schrieb:

noproblem schrieb:

Mal abgesehen von den Speicherlöchern die beim resize entstehen...

wtf?

so wie ich das verstehe meint er damit, dass bei einem verkleindernden resize bei einem vector der speicher nicht unbedingt wieder freigegeben wird sondern der vector diesen aus performance gründen behält... glaub ich

@Shade of Mine

Ach nur das es den Anschein hatte, das du eine andere Meinung hattest.

@japro

Natürlich ist es aufwendiger, aber dafür auch schneller.Und von statischem Array war keine rede.

otze

doch, davon war die rede.
und zwar ging es darum, ob es besser ist einen Vector zu benutzen, wenn man weis wieviele einträge er haben wird, oder ob es besser ist, ein array zu benutzen.

Vom ursprünglichen Thema her gesehen natürlich schon.
Da es aber mehr eine Streiterei über Performance vom vector ging ist da speziell keine rede von statischen Arrays gewesen.

Christoph

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.

Warum sollte das logisch sein?

Du hast festgestellt, dass bei deinem Compiler in einer bestimmten Version und bestimmten Compilereinstellungen bei einer bestimmten STL-Implementation der Zugriff auf einen vector langsamer ist als auf ein Array. Das sagt nicht allzuviel aus.
IMHO sind heutige Compiler durchaus in der Lage, bei geeigneten STL-Implementierungen den Vector-Zugriff über [] in genau denselben Maschinencode umzuwandeln, wie wenn das Objekt ein C-Array wäre.

Beweis ???

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

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

Christoph

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.

@cd9000

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

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

Artchi

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.

Christoph

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.

japro

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

otze

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

japro

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.

otze

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