array vs vector

[David_pb]

Shade Of Mine schrieb:

Und wer hat dir den quark erzählt?

Steht in diversen Papers von AMD.

Shade Of Mine schrieb:

a[b] == *(a+b) == *(b+a) == b[a]

fuer alle diese Ausdrücke wird jeder intelligente Compiler exakt den selben Code generieren.

Jaja, Theorie und Praxis liegen z.T. schon weit auseinander...

[Gast]

Ich glaube du verwechselst da was.

[David_pb]

Tim schrieb:

Ich glaube du verwechselst da was.

Ja? Dann klär mich mal auf.

[Shade Of Mine]

David_pb schrieb:

Tim schrieb:

Ich glaube du verwechselst da was.

Ja? Dann klär mich mal auf.

zeig uns was in den AMD Papieren steht und wir erklären dir was du falsch verstanden hast.

Was ich gepostet habe ist Prozessor unabhaengig.

ein compiler kann manchmal mit laufenden zeigern besser optimieren als mit index zugriffen oder umgekehrt, aber das liegt daran wie gut er den code versteht. und manchmal versteht er den code mit der einen syntax besser.

aber wenn ich auf p[5] zugreifen will, dann mach ich in asm ein

mov ecx, p
add ecx, 5
mov eax, [ecx]

die cpu sieht nie ob ich *(p+5) oder p[5] geschrieben habe. selbes bei laufenden zeigern versus index...

[Gast]

@ David_pb:

Na ich weiss nicht, vorhin hast du von Zeiger-Aliasing und gleichzeitig von der unterschiedlichen Syntax beim dereferenzieren geredet. Zwei Dinge die eigentlich wenig miteinander zu tun haben. Vielleicht erklärst du das nochmal genauer?

[David_pb]

Shade Of Mine schrieb:

ein compiler kann manchmal mit laufenden zeigern besser optimieren als mit index zugriffen oder umgekehrt, aber das liegt daran wie gut er den code versteht. und manchmal versteht er den code mit der einen syntax besser.

Hab ich das nicht geschrieben?

ohne aufwendige Analyse

So, hab nochmal die Quelle rausgekramt:

The use of pointers in C makes work difficult for the optimizers
in C compilers. Without detailed and aggressive pointer
analysis, the compiler has to assume that writes through a
pointer can write to any place in memory. This includes storage
allocated to other variables, creating the issue of aliasing, i.e.,
the same block of memory is accessible in more than one way.
To help the C compiler optimizer in its analysis, avoid the use of
pointers where possible. One example where this is trivially
possible is in the access of data organized as arrays. C allows the
use of either the array operator [] or pointers to access the
array. Using array-style code makes the task of the optimizer
easier by reducing possible aliasing.
For example, x[0] and x[2] cannot possibly refer to the same
memory location, while *p and *q could. It is highly
recommended to use the array style, as significant performance
advantages can be achieved with most compilers.

[Gast]

David_pb schrieb:

Shade Of Mine schrieb:

ein compiler kann manchmal mit laufenden zeigern besser optimieren als mit index zugriffen oder umgekehrt, aber das liegt daran wie gut er den code versteht. und manchmal versteht er den code mit der einen syntax besser.

Hab ich das nicht geschrieben?

Du hast nichts von laufenden Zeigern gesagt. Aber jetzt ist es klar.

[Shade Of Mine]

David_pb schrieb:

Hab ich das nicht geschrieben?

Nein.

Mal abgesehen dass diese Info mit laufenden Zeigern versus index schon jahre veraltet ist, ist je nach Situation das eine oder andere schneller wenn der compiler dumm ist. die zitierte quelle ist übrigens auch fehlerhaft. denn *p und *q kann das selbe sein, aber x[1] und x[2] hat mit dem p/q beispiel nix zu tun. und x[1] und y[2] können sehr wohl das selbe sein.

früher war es so, dass je nach situation das eine oder andere schneller war, je nachdem wie gut der compiler das konstrukt verstanden hat.

es gibt gerade bei optimierungen viele halbwahrheiten - meistens aus der zeit als c++ compiler stroh dumm waren. schau dir den generierten asm code heute einfach mal an. die compiler sind soviel klueger geworden und erkennen code konstrukte ziemlich gut.

wenn also eine der beiden varianten schneller ist, dann ist es ein fehler im optimierer des compilers.

und wie gesagt, diese laufende zeiger versus index diskussion ist seit jahren begraben... es sei denn man programmiert im embedded bereich, aber dann muss man sich sowieso an die bugs der compiler anpassen...

[David_pb]

Hm, danke für die Info!

[Shade Of Mine]

um es zu belegen:

ich habe den code aus dem AMD64 OPtimierungsguide genommen:
http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF

test.c und test2.c sind die beiden Dateien:
mit "gcc -O2 -S -c test.c"

der code der generiert wird ist leicht unterschiedlich. ein diff liefert daher viele unterschiede (alles mov*, add*, mul*) aber:

TS-MacBook-Pro:perftest ts$ cat test2.s | grep mov | wc -l
      25
TS-MacBook-Pro:perftest ts$ cat test2.s | grep add | wc -l
      15
TS-MacBook-Pro:perftest ts$ cat test2.s | grep mul | wc -l
      16
TS-MacBook-Pro:perftest ts$ cat test.s | grep mov | wc -l
      25
TS-MacBook-Pro:perftest ts$ cat test.s | grep add | wc -l
      15
TS-MacBook-Pro:perftest ts$ cat test.s | grep mul | wc -l
      16

und natürlich:

TS-MacBook-Pro:perftest ts$ cat test.s | wc -l
      77
TS-MacBook-Pro:perftest ts$ cat test2.s | wc -l
      77

also wenn es einen unterschied gibt an dem code, dann kann er nicht messbar sein...

[hustbaer]

Einen Unterschied kann es geben wenn der Compiler einmal die Grösse des Arrays kennt, und ein anderes mal nicht.
Mit einem Zeiger wo beim Übersetzen der entsprechenden Codestelle nicht bekannt ist wie gross der dahinterliegende Speicher ist muss der Compiler unter umständen anders umgehen als mit einem Zeiger von dem der Compiler sehr genau weiss worauf er zeigt. Genauso macht es einen Unterschied ob Aliasing ausgeschlossen werden kann oder nicht.

Auch könnte es sein dass der Optimizer je nach verwendeter Syntax unterschiedlichen Code erstellt.

Allgemein kann man aber denke ich keine Aussage machen dies oder jenes sei schneller. Für eine bestimmte Version eines bestimmten Compilers vielleicht, aber allgemein wohl nicht. Und natürlich kann es sein dass der Code der auch CPU X schneller läuft auf CPU Y langsamer läuft.

Alles in allem ist die Diskussion IMO ziemlich überflüssig.

[asmcode]

Shade Of Mine schrieb:

asmcode schrieb:

Shade Of Mine schrieb:

Skym0sh0 schrieb:

ein normales c array ist schneller

wieso sollte das so sein?

beim zugriff mit [] wars glaub ich eine Operation mehr im Assemblercode

Begruendung?

Hier gabs mal dieses Beispiel. Da kannst du die Begründung selber suchen.

void foo()
{
    LONGLONG g_Frequency, g_CurentCount, g_LastCount;

    //Frequenz holen
    if (!QueryPerformanceFrequency((LARGE_INTEGER*)&g_Frequency))
        std::cout << "Performance Counter nicht vorhanden" << std::endl;

    //1. Messung
    QueryPerformanceCounter((LARGE_INTEGER*)&g_CurentCount);

	int max=50000;
	std::vector<int> a(max);
	for (int i=0; i<=max-2; i++)
	{
		int x,Min = i;
		for (int j=i+1; j<=max-1; j++)
			if (a[j]<a[Min]) Min = j;
		x = a[i]; a[i] = a[Min]; a[Min] = x;
	}

    //2. Messung
    QueryPerformanceCounter((LARGE_INTEGER*)&g_LastCount);

    double dTimeDiff = (((double)(g_LastCount-g_CurentCount))/((double)g_Frequency)); 
	std::cout << "Zeit: " << dTimeDiff << std::endl; 
}

void bar()
{
    LONGLONG g_Frequency, g_CurentCount, g_LastCount;

    //Frequenz holen
    if (!QueryPerformanceFrequency((LARGE_INTEGER*)&g_Frequency))
        std::cout << "Performance Counter nicht vorhanden" << std::endl;

    //1. Messung
    QueryPerformanceCounter((LARGE_INTEGER*)&g_CurentCount);

	int max=50000;
	int* a = new int[max];
	for (int i=0; i<=max-2; i++)
	{
		int x,Min = i;
		for (int j=i+1; j<=max-1; j++)
			if (a[j]<a[Min]) Min = j;
		x = a[i]; a[i] = a[Min]; a[Min] = x;
	}

    //2. Messung
    QueryPerformanceCounter((LARGE_INTEGER*)&g_LastCount);

    double dTimeDiff = (((double)(g_LastCount-g_CurentCount))/((double)g_Frequency)); 
	std::cout << "Zeit: " << dTimeDiff << std::endl; 
}

int main(int argc, char**argv)
{
	foo();
	bar();
}

Zeit: 3.79928
Zeit: 1.03572

Und ja im Release Mode.

PS: Zusammen kopierter Code, nicht von mir, also keine Kommentare.

[hustbaer]

@asmcode:
Und ja mit dem ollen checked iterators vom MSVC. Dreh die mal ab.

[Gast]

Und ein normales C-Array seh ich in dem Code auch keins.

[OMGgg]

lol 2 sekunden unterschied ich nehm nur noch array und nie wieder vector

[drakon]

OMGgg schrieb:

lol 2 sekunden unterschied ich nehm nur noch array und nie wieder vector

Genau. Und am besten nimmst du auch noch C-Strings und wir sind alle zufrieden.

[Shade Of Mine]

@asmcode:
Ich liebe es wenn Halbwissen verwendet wird. Standardmaessig hat vector beim VC++ einen range check dabei, zB sind auch iteratoren standardmaessig langsamer da jeder iterator einen next zeiger auf einen anderen iterator hat und bei jedem invalidate von iteratoren (bei vector zB einem reallocate) oder auch wenn der container zerstoert wird, gibt es ein notify an alle iteratoren.

das kostet performance und es gibt viel streiterei ob man es im release code drinnen haben will. das muss jeder selbst entscheiden:
#define _SECURE_SCL 0
um es abzudrehen.

und dann sind array und vector auch exakt gleich schnell. natuerlich muss man mehr als einen durchgang testen, aber das sollte klar sein.

ich habe deinen code genommen und foo und bar jeweils dTimeDiff returnen lassen und dann abwechselnd 30 mal foo und bar gecallt:

30 runs.
vec: overall: 36.5086
arr: overall: 36.556

vec: average: 1.21695
arr: average: 1.21853

lustigerweise ist vec in der messung sogar schneller gewesen. aber das ist nichts anderes als ein messfehler, da der generierte code identisch sein muesste.

PS:
es scheint mittlerweile verloren gegangen zu sein. aber frueher war eines der wichtigsten features von c++ das zero cost principle: abstraktion ist gratis.

wenn ich ein normales array nehme und es in eine klasse stecke, dann habe ich dadurch keine runtime kosten. wenn ich jetzt aber zB range checking will, dann kostet das natuerlich schon. aber wenn ich das ohne vector machen wuerde, waere es ja auch nicht gratis.

dieses zero cost principle: ich zahle keine performance kosten fuer abstraktion, scheint irgendwo verloren gegangen zu sein - da ich solche threads wie diesen immer wieder lese. finde ich irgendwie schade.

denn das fasziniert mich an c++ eigentlich so: es gibt keine magie. alles liegt klar und deutlich vor einem...

[asmcode]

Und wie kommt MS auf die dumme Idee bei [] jetzt auch nen range check einzubauen. Ich bin davon ausgegangen, dass der nur bei at() gemacht wird. Steht das nicht im Standard drin, dass das so sein soll?

[asc]

asmcode schrieb:

Und wie kommt MS auf die dumme Idee bei [] jetzt auch nen range check einzubauen. Ich bin davon ausgegangen, dass der nur bei at() gemacht wird. Steht das nicht im Standard drin, dass das so sein soll?

Bei at ist die Prüfung Pflicht, bei [] ist sie erlaubt. Die Lösung über ein Makro halte ich durchaus für akzeptabel, hätte aber besser an einer Stelle stehen sollen wo man sie nicht so leicht übersieht (z.B. ein Schalter in den Projekteinstellungen).

cu André

[asmcode]

Oder einfach defaultmäßig aus. So ist es ja fast schon so wie ein Compiler der im Releasemodus defaultmäßig nicht optimieren würde.