Summe schneller machen?

Gibt es irgendeine Möglichkeit, Summen der Form

int sum=0;
int array[10] = {...}; //größe variabel
int n = 10; //ist natürlich variabel
for(int i=0;i<n;++i)
{
   sum += array[i];
}

Schneller zu implementieren als es hier gemacht wird?

Cpp_Junky

-Die Schleife kannst du per Pointer-Arithmetik implementieren
-Wenn du die Anzahl der Elemente kennst, kannst du in Blöcken aufsummieren
-Probier mit verschiedenen Datentypen rum falls das geht
-Machs in Assembler ^^

Tachyon

SIMD-Instuktionen benutzen.

Ethon

Falls der Compiler das nicht bereits macht, mehrere Additionen pro Schleifendurch lauf. zb:

int accumulate(int* arr, int n)
{
    int r = 0;
    for(; n > 4; n -= 5, arr += 5)
    {
        r += arr[0];
        r += arr[1];
        r += arr[2];
        r += arr[3];
        r += arr[4];
    }

    // Rest
    for(int i = 0; i != n; ++i)
    {
        r += arr[i];
    }

    return r;
}

Cpp_Junky

Wir hatten hier mal einen Programmierwettbewerb bei dem sowas Ähnliches die Aufgabe war. Ich glaub der Sieger hatte es einfach so gemacht, das er schlicht per #define mehrere Additionen zusammengepackt hat, so dass das Programm diese tatsächlich der Reihe nach (ohne Schleife) ausführte. Das geht natürlich gut, wenn man vorher weiss wie viele Elemente das werden, andernfalls muss man irgendwie rumtricksen.

knivil

Du kannst SSE benutzen oder eine Bibliothek wie http://software.intel.com/sites/products/documentation/doclib/ipp_sa/71/ipp_manual/index.htm , die das schon macht.

SeppJ

knivil schrieb:

Du kannst SSE benutzen oder eine Bibliothek wie http://software.intel.com/sites/products/documentation/doclib/ipp_sa/71/ipp_manual/index.htm , die das schon macht.

Man kann sogar noch einen Schritt weitergehen, und das Problem blockweise parallel berechnen, dann die Ergebnisse zusammenzählen.

P.S.: Das lohnt sich natürlich nur für sehr große N.

rapso

Cpp_Junky schrieb:

Wir hatten hier mal einen Programmierwettbewerb bei dem sowas Ähnliches die Aufgabe war. Ich glaub der Sieger hatte es einfach so gemacht, das er schlicht per #define mehrere Additionen zusammengepackt hat, so dass das Programm diese tatsächlich der Reihe nach (ohne Schleife) ausführte. Das geht natürlich gut, wenn man vorher weiss wie viele Elemente das werden, andernfalls muss man irgendwie rumtricksen.

das rumtricksen ist indem man eine jump table an die stelle macht wo soviele durchlaeufe uebrigbleiben wie man elemente im array hat.

jedoch wuerde ich an sich erwarten dass man einfach nur speicher limitiert ist bei sowas trivialem und wenn man das komplett unrollt, duerfte man die situation verschlechtern, weil dann noch der speichertransfer fuer den code dazu kommt.

ich glaube fast, so wie der code da oben steht, wuerde er auf allerneusten intel cpus schon perfekt laufen. branching kostet nichts in dem fall, die dependancy von i++ und array[i] koennen die cpus auch aufloesen, dabei 3 add jedes cycle verarbeiten (hier stehen bei +=array[a++] nur zwei an).

in assembler koennte man das als

rep add eax,[ecx]

loesen, aber ich glaube es duerfte nichts an der performance aendern.

nevermore

Wenn du nur einen Akkumulator verwendest könnte das schlecht für das Pipelining der CPU sein. Ethon's Ansatz mit mehreren Akkumulatoren (also r+=... s+=... t+=... und return r+s+t statt nur auf r zu addieren) könnte noch was bringen (zusätzlich zu SSE & Co).

cooky451

std::valarray :xmas1:

Ethon

nevermore schrieb:

Wenn du nur einen Akkumulator verwendest könnte das schlecht für das Pipelining der CPU sein. Ethon's Ansatz mit mehreren Akkumulatoren (also r+=... s+=... t+=... und return r+s+t statt nur auf r zu addieren) könnte noch was bringen (zusätzlich zu SSE & Co).

Müsste man dabei aber nicht aufpassen nicht mehr Akkumulatoren zu verwenden als freie Register zur Verfügung stehen? Ich denke da ist jeder Compiler zu schlau, aber angenommen ein Akkumulator lebt als Stackvariable dann wäre das fatal.

x86 hat doch so viele freie Register, dass man da schon was besonderes machen müsste, dass es nicht passt!
</sarcasm>

nevermore

Ethon schrieb:

nevermore schrieb:

Wenn du nur einen Akkumulator verwendest könnte das schlecht für das Pipelining der CPU sein. Ethon's Ansatz mit mehreren Akkumulatoren (also r+=... s+=... t+=... und return r+s+t statt nur auf r zu addieren) könnte noch was bringen (zusätzlich zu SSE & Co).

Müsste man dabei aber nicht aufpassen nicht mehr Akkumulatoren zu verwenden als freie Register zur Verfügung stehen? Ich denke da ist jeder Compiler zu schlau, aber angenommen ein Akkumulator lebt als Stackvariable dann wäre das fatal.

Moderne CPUs haben mehr Register als über den Befehlssatz benutzt werden können, die Technik nennt sich "Register Renaming".

DocShoe

Loop Unrolling per TMP?

Hallo an alle.

Was bringt einem hier SSE? Gibt es einen SSE Befehl der auf eine einzige Summenvariable den Inhalt mehrerer Felder addiert?

SSE müsste das intern doch auch einfach seriell machen, oder?

knivil

1.) Stichwort: horizontal add (SSE3 oder SSE4)
2.) 4 Summen "gleichzeitig" bei SSE2

Gibt es einen SSE Befehl der auf eine einzige Summenvariable den Inhalt mehrerer Felder addiert?

Wurde schon angesprochen, du kannst die Summe auf mehrere Variablen aufteilen und diese am Ende einzeln aufaddieren.

krümelkacker

schnellsummer schrieb:

Was bringt einem hier SSE? Gibt es einen SSE Befehl der auf eine einzige Summenvariable den Inhalt mehrerer Felder addiert?
SSE müsste das intern doch auch einfach seriell machen, oder?

Du berechnest mehrere Summen vektoriell und addierst ganz zum Schluss die einzelnen Komponenten des Ergebnisvektors. Also im Prinzip so:

s0 = a0 + a4 + a8  + a12 + ...
s1 = a1 + a5 + a9  + a13 + ...
s2 = a2 + a6 + a10 + a14 + ...
s3 = a3 + a7 + a11 + a15 + ...

        ^    ^     ^     ^
       parallele Additionen

sum = s0 + s1 + s2 + s3;

Allerdings wird das nichts bringen, wenn die Daten nicht schon im Cache liegen; denn dann ist der Speicherzugriff sehr wahrscheinlich der Flaschenhals.

rapso

nevermore schrieb:

Ethon schrieb:

nevermore schrieb:

Wenn du nur einen Akkumulator verwendest könnte das schlecht für das Pipelining der CPU sein. Ethon's Ansatz mit mehreren Akkumulatoren (also r+=... s+=... t+=... und return r+s+t statt nur auf r zu addieren) könnte noch was bringen (zusätzlich zu SSE & Co).

Müsste man dabei aber nicht aufpassen nicht mehr Akkumulatoren zu verwenden als freie Register zur Verfügung stehen? Ich denke da ist jeder Compiler zu schlau, aber angenommen ein Akkumulator lebt als Stackvariable dann wäre das fatal.

Moderne CPUs haben mehr Register als über den Befehlssatz benutzt werden können, die Technik nennt sich "Register Renaming".

diese werden aber fuer die OOO ausfuehrung benutzt, nicht dafuer um register spilling abzufangen. wenn du also mehr variablen nutzt als register frei sind, wird deine cpu diese in den speicher schreiben, weil...

der compiler der cpu nicht mitteilen kann, dass diese memory writes nur auslagerungen sind
die cpu nicht annehmen darf dass irgend ein write unterlassen werden koennte vor einem read (der ja zwangslaeufig folgen wird wenn zuviele temporaries fuer das register set da sind).

@nevermore
ja das koennte schlecht sein, aber an sich sollte das bei einem add kein problem sein.

hier mal kurz einen benchmark zusammengehauen

#include <stdint.h>
#include <malloc.h>
#include <time.h>
#include <stdio.h>
#include <emmintrin.h>

const size_t	LOOPS	=	16;
const size_t	SIZE	=	128*1024*1024;

template<size_t Index>
struct TAdd
{
	static uint32_t Eval(const uint32_t* pBuffer) 
	{
		return pBuffer[SIZE-Index]+TAdd<Index-1u>::Eval(pBuffer);
	}
};

template<>
struct TAdd<0>
{
	static uint32_t Eval(const uint32_t* pBuffer){return 0;}
};

int main(int argc,char* argv[])
{
	uint32_t* pBuffer	=	reinterpret_cast<uint32_t*>(_mm_malloc(SIZE*sizeof(*pBuffer),16));

	for(size_t a=0;a<SIZE;a++)
		pBuffer[a]=a*17+13;

	uint32_t Sum0=0;
	uint32_t Sum1=0;
	uint32_t Sum2=0;
	uint32_t Sum3=0;
	const float T0	=	static_cast<float>(clock())/CLOCKS_PER_SEC;
	for(size_t b=0;b<LOOPS;b++)
	for(size_t a=0;a<SIZE;a++)
		Sum0+=pBuffer[a];
	const float T1	=	static_cast<float>(clock())/CLOCKS_PER_SEC;
	uint32_t SumA=0,SumB=0,SumC=0,SumD=0;
	for(size_t b=0;b<LOOPS;b++)
	for(size_t a=0;a<SIZE;a+=4)
	{
		SumA+=pBuffer[a];
		SumB+=pBuffer[a+1];
		SumC+=pBuffer[a+2];
		SumD+=pBuffer[a+3];
	}
	Sum1=SumA+SumB+SumC+SumD;
	const float T2	=	static_cast<float>(clock())/CLOCKS_PER_SEC;
	__m128i SumA4	=	_mm_set1_epi32(0);
	__m128i SumB4	=	_mm_set1_epi32(0);
	__m128i SumC4	=	_mm_set1_epi32(0);
	__m128i SumD4	=	_mm_set1_epi32(0);
	for(size_t b=0;b<LOOPS;b++)
	for(size_t a=0;a<SIZE;a+=16)
	{
		SumA4=_mm_add_epi32(SumA4,*reinterpret_cast<__m128i*>(pBuffer+a));
		SumB4=_mm_add_epi32(SumB4,*reinterpret_cast<__m128i*>(pBuffer+a+4));
		SumC4=_mm_add_epi32(SumC4,*reinterpret_cast<__m128i*>(pBuffer+a+8));
		SumD4=_mm_add_epi32(SumD4,*reinterpret_cast<__m128i*>(pBuffer+a+12));
	}
	SumA4	=	_mm_add_epi32(_mm_add_epi32(SumA4,SumB4),_mm_add_epi32(SumC4,SumD4));
	Sum2	=	SumA4.m128i_i32[0]+SumA4.m128i_i32[1]+SumA4.m128i_i32[2]+SumA4.m128i_i32[3];//wird auf dem gcc nicht bauen, da muesst ihr halt eine union {uint32 t[4];__m128i T;}... basteln
	const float T3	=	static_cast<float>(clock())/CLOCKS_PER_SEC;
	for(size_t b=0;b<LOOPS;b++)
		Sum3+=0;//TAdd<SIZE>::Eval(pBuffer);
	const float T4	=	static_cast<float>(clock())/CLOCKS_PER_SEC;

	printf("%8d %2.3fs %2.3fMIntop/s %2.3fMB/s\n",Sum0,T1-T0,LOOPS/1000000.f*SIZE/(T1-T0),LOOPS/1000000.f*SIZE*sizeof(*pBuffer)/(T1-T0));
	printf("%8d %2.3fs %2.3fMIntop/s %2.3fMB/s\n",Sum1,T2-T1,LOOPS/1000000.f*SIZE/(T2-T1),LOOPS/1000000.f*SIZE*sizeof(*pBuffer)/(T2-T1));
	printf("%8d %2.3fs %2.3fMIntop/s %2.3fMB/s\n",Sum2,T3-T2,LOOPS/1000000.f*SIZE/(T3-T2),LOOPS/1000000.f*SIZE*sizeof(*pBuffer)/(T3-T2));
	printf("%8d %2.3fs %2.3fMIntop/s %2.3fMB/s\n",Sum3,T4-T3,LOOPS/1000000.f*SIZE/(T4-T3),LOOPS/1000000.f*SIZE*sizeof(*pBuffer)/(T4-T3));
	return 0;
}

1 ist das vom op
2 ist 4x unrolled
3 ist 4x unrolled sse
4 ist template (falls jemand die zeit hat es durchbauen zu lassen :D), oder hab ich da was unsmart gemacht?

SeppJ

Kannst du auch noch eine kurze Version mit mehreren Threads bauen? Ich bin nicht so gut mit den C-Threads, kann nur C++ . Aber die CPU-Hersteller hätten so gerne, dass man alle Kerne voll ausnutzt, sollen sie mal zeigen was besser ist: SSE oder mehr Kerne? :xmas1:

Ethon

SeppJ schrieb:

Kannst du auch noch eine kurze Version mit mehreren Threads bauen? Ich bin nicht so gut mit den C-Threads, kann nur C++ . Aber die CPU-Hersteller hätten so gerne, dass man alle Kerne voll ausnutzt, sollen sie mal zeigen was besser ist: SSE oder mehr Kerne? :xmas1:

Summe mit mehreren Kernen? Da ist doch sowieso der Speicher der Flaschenhals, ein Kern allein kann doch schon die komplette Speicherbandbreite ausnutzen.