pruefen, ob alle werte 'wert' haben

[volkard]

camper schrieb:

jedenfalls dürftest du dich in beiden fällen irren.

cool. das höre ich sonst nur bei java-diskussionen.

der umliegende code braucht selbst höchtens zwei oder drei register,

ich kenne den umliegenden code nicht. und du auch nicht. steckt der uns gezeigte ausschnitt nicht in wirklichkeit in ner schleife? wir wissen es nicht.

also bleibt leicht noch etwas frei, und falls es doch eine speicher variable ist... nun das ist irrelevant - eine vorzögerung ensteht nicht, solange nur geschrieben wird.

also für mich sieht schreiben in eine variable so aus: var=wert; und lesen so: tuwas(var);
aber var&=wert sieht für mich verdammt stark nach lesen und schreiben aus. geht dir das ähnlich?

es war auch nicht unbedingt nach einer funktion gefragt, wenn es keine sein soll, wirst du nicht um eine hilfsvariable drumherum kommen

klar geht das. man kommt nur nicht elegant umhin. der klassiker ist wohl, bei fund mit goto tuwas() zu überhüpfen.

[smasher1985]

Das mit der Performance in diesem Fall hat mich jetzt doch mal interessiert. Ich zeig euch einfach mal, wie ich gemessen hab, sagt mir falls da methodisch was faul ist - ich hab sowas noch nicht so oft gemacht...

Die Ergebnisse jedenfalls sind
Camper's Methode mit zusätzlicher Variable: 18.57s
Camper's Methode ohne zusätzliche Variable: 2.46s
Volkard's Methode: 2.90s

Kommt mir ja ein bisschen zu krass vor, vor allem der Unterschied zwischen den zwei ersten Methoden. Ich kann aber keinen Fehler sehen also klärt mich auf *g*

@Volkard: deine Methode ist nicht 1 zu 1 übernommen. Aber mit double als Typ des ersten Parameters kann das ja nicht kompilieren oder täusch ich mich??

Achja, und noch eine Frage by the way: gibts eine standard-konforme version von QueryPerfomanceCounter bzw. einen entpsrechenden Header?

#include <iostream>
#include <windows.h>
#include <mmsystem.h>

using namespace std;

#define NUM 10000000

// hier hab ich den ersten Parameter angepasst...
inline bool areAllTrue(bool* array,int arrayend){ 
   for(int i=0;i<arrayend;++i) 
      if(!array[i])//wenn einer mit false gefunden wird 
         return false;//dann sind nicht alle true 
   return true;//wenn keine false in der schleife gefunden wurde, sind's true 
} 

void foo() {
	int j;
	j=1;
}

int main()
{
	LONGLONG frequency, currentTime, lastTime;
	double timeElapsed, timeScale;

	QueryPerformanceFrequency((LARGE_INTEGER*)&frequency);
	timeScale = 1.0 / frequency;

	bool array[100];
	for (int j=0; j<100; ++j)
		array[j] = true;

	/// CAMPERS METHODE 1

	QueryPerformanceCounter((LARGE_INTEGER*)&lastTime);

	{
		for (int j=0; j < NUM; ++j) {
			bool allTrue; 
			for( int i = 0; ( allTrue = bool( array[ i ] ) ) && ++i < 100; ); 
			if (allTrue) foo(); 
		}

	}

	QueryPerformanceCounter((LARGE_INTEGER*)&currentTime);
	timeElapsed = (currentTime - lastTime) * timeScale;
	cout << timeElapsed << endl;

	/// CAMPERS METHODE 2

	QueryPerformanceCounter((LARGE_INTEGER*)&lastTime);

	{
		for (int j=0; j < NUM; ++j) {
			for (int i = 0; bool( array[ i ] ) && ++i < 100; );
			if (i >= 100) {
				foo();
			}
		}
	}

	QueryPerformanceCounter((LARGE_INTEGER*)&currentTime);
	timeElapsed = (currentTime - lastTime) * timeScale;
	cout << timeElapsed << endl;

	/// VOLKARDS METHODE (leicht verändert)

	QueryPerformanceCounter((LARGE_INTEGER*)&lastTime);

	{
		for (int j=0; j < NUM; ++j) {
			if(areAllTrue(array,100)) {	
				foo();
			}
		}

	}

	QueryPerformanceCounter((LARGE_INTEGER*)&currentTime);
	timeElapsed = (currentTime - lastTime) * timeScale;
	cout << timeElapsed << endl;  
}

Nehmt mal bitte Stellung

Mfg, smasher1985

Edit: Achja, das ganze ist mit MSVC6.0 kompiliert

[camper]

es gibt keinen guten grund diese diskussion weiterzuführen. der code, so wie er ist, funktioniert und verletzt keine standards. und die tatsache, dass keiner von uns weiss, was der umliegende code tut, kann wohl kaum als argument dagegen verwendet werden. &&= bzw. &= kommt in meinem code gar nicht vor; und bzgl. der hilfsvariable habe ich micht auch bereits selbst widerlegt - kein grund das noch einmal anzuführen.

die stl variante ist sicherlich eine gute möglichkeit, die man in den meisten fällen vorziehen wird. aber auf irgendeine magische weise schneller oder weniger resourcenintensiv ist sicherlich nicht.

mein code ist und war nur als optimierung der vorangegangenen beispiele gedacht - und er ist schneller und prägnanter als diese. ich begreife nicht, wieso das soviel widerspruch hervorruft.

[camper]

mit vc++7.1 bekomme ich diese werte:
1.94414
1.82313
1.84317

möglich das vc6 erst den zugewiesenen ausdruck auf true prüft - in dem falle wäre es nat. eine schreib-lese-vorgang, der zeit kostet - auf jeden fall eine schwäche des compilers.

[camper]

ich habe diesen 'benchmark' noch einmal untersucht und kleine änderungen vorgenommen:

#include <iostream>
#include <windows.h>
#include <mmsystem.h>

using namespace std;

#define NUM 100000000

// hier hab ich den ersten Parameter angepasst...
inline bool areAllTrue(bool* array,int arrayend){
   for(int i=0;i<arrayend;++i)
      if(!array[i])//wenn einer mit false gefunden wird
         return false;//dann sind nicht alle true
   return true;//wenn keine false in der schleife gefunden wurde, sind's true
}

void foo() {
    int j;
    j=1;
}
/*
__declspec( naked ) bool __fastcall areAllTrue(bool* array,int arrayend)
{
	__asm
	{
		psubb	mm0, mm0
		push	edx
		movq	mm1, mm0
		xor		eax, eax
		and		edx, 0xfffffff0
		movq	mm2, mm0
		jz		_xx
		lea		ecx, [ ecx + edx ]
		neg		edx
_loop:	pcmpeqb	mm0, [ ecx + edx ]
		por		mm2, mm0
		pcmpeqb	mm1, [ ecx + edx + 8 ]
		add		edx, 16
		por		mm2, mm1
		jnz		_loop
		psubb	mm0, mm0
		pcmpeqb	mm0, mm2
		pmovmskb eax, mm0
		test	eax, eax
		jnz		_false
_xx:	emms
		pop		edx
		and		edx, 0xf
		jz		_true
		add		ecx, edx
		neg		edx
_loop2:	cmp		byte ptr [ ecx + edx ], 1
		inc		edx
		jc		_false2
		jnz		_loop2
_true:	inc		eax
		ret
_false:	pop		edx
_false2:emms
		xor		eax, eax
		ret
	}
}
*/
int main()
{
    LONGLONG frequency, currentTime, lastTime;
    double timeElapsed, timeScale;

    QueryPerformanceFrequency((LARGE_INTEGER*)&frequency);
    timeScale = 1.0 / frequency;

    bool array[100];
    for (int j=0; j<100; ++j)
        array[j] = true;

    /// CAMPERS METHODE 1

	QueryPerformanceCounter((LARGE_INTEGER*)&lastTime);

    {
        for (int j=0; j < NUM; ++j) {
            bool allTrue;
            for( int i = 0; ( allTrue = bool( array[ i ] ) ) && ++i < 100; );
            if (allTrue) foo();
        }

    }

    QueryPerformanceCounter((LARGE_INTEGER*)&currentTime);
	QueryPerformanceCounter((LARGE_INTEGER*)&lastTime);

    {
        for (int j=0; j < NUM; ++j) {
            bool allTrue;
            for( int i = 0; ( allTrue = bool( array[ i ] ) ) && ++i < 100; );
            if (allTrue) foo();
        }

    }

    QueryPerformanceCounter((LARGE_INTEGER*)&currentTime);
    timeElapsed = (currentTime - lastTime) * timeScale;
    cout << timeElapsed << endl;

    /// CAMPERS METHODE 2

    QueryPerformanceCounter((LARGE_INTEGER*)&lastTime);

    {
        for (int j=0; j < NUM; ++j) {
            for (int i = 0; bool( array[ i ] ) && ++i < 100; );
            if (i >= 100) {
                foo();
            }
        }
    }

    QueryPerformanceCounter((LARGE_INTEGER*)&currentTime);
    timeElapsed = (currentTime - lastTime) * timeScale;
    cout << timeElapsed << endl;

    /// VOLKARDS METHODE (leicht verändert)

    QueryPerformanceCounter((LARGE_INTEGER*)&lastTime);

    {
        for (int j=0; j < NUM; ++j) {
            if(areAllTrue(array,100)) {   
                foo();
            }
        }

    }

    QueryPerformanceCounter((LARGE_INTEGER*)&currentTime);
    timeElapsed = (currentTime - lastTime) * timeScale;
    cout << timeElapsed << endl;  
	QueryPerformanceCounter((LARGE_INTEGER*)&lastTime);

    {
        for (int j=0; j < NUM; ++j) {
            bool allTrue;
            for( int i = 0; ( allTrue = bool( array[ i ] ) ) && ++i < 100; );
            if (allTrue) foo();
        }

    }

    QueryPerformanceCounter((LARGE_INTEGER*)&currentTime);
    timeElapsed = (currentTime - lastTime) * timeScale;
    cout << timeElapsed << endl;

    /// CAMPERS METHODE 2

    QueryPerformanceCounter((LARGE_INTEGER*)&lastTime);

    {
        for (int j=0; j < NUM; ++j) {
            for (int i = 0; bool( array[ i ] ) && ++i < 100; );
            if (i >= 100) {
                foo();
            }
        }
    }

    QueryPerformanceCounter((LARGE_INTEGER*)&currentTime);
    timeElapsed = (currentTime - lastTime) * timeScale;
    cout << timeElapsed << endl;

    /// VOLKARDS METHODE (leicht verändert)

    QueryPerformanceCounter((LARGE_INTEGER*)&lastTime);

    {
        for (int j=0; j < NUM; ++j) {
            if(areAllTrue(array,100)) {   
                foo();
            }
        }

    }

    QueryPerformanceCounter((LARGE_INTEGER*)&currentTime);
    timeElapsed = (currentTime - lastTime) * timeScale;
    cout << timeElapsed << endl;  
}

und erhalte nun z.b. diese zeiten:
11.5908
11.4006
11.6515
11.4341
11.3817
11.9264
ich stelle fest, dass die erste gemesene zeit nun kürzer als zuvor ist. offenbar profitiert dieser benchmark nun auch von gewissen prozessorinternen optimierungen (wie anwesenheit der daten im L1 cache etc.), zuvor war dieser unangemessen benachteiligt. man kann wohl sagen, dass es keinen signifikanten unterschied zwischen variante 1 und 2 gibt; und auch die dritte variante düfte im rahmen der messgenauigkeit als gleichschnell angesehen werden. wer will, kann ja noch die assembler variante ausprobieren - ist nur eine studie

[0xdeadbeef]

Einfachste Möglichkeit wohl

#include <valarray>

// ...

if(std::valarray<bool>(array, &array[arraylen]) == true) {
  // alles true
}

Ist grad ungetestet, aber ich denke, dass es so gehen müsste. Die Performance hängt dabei natürlich von der Qualität der valarray-Implementierung ab, und liegt im Zweifel wegen des Kopierens im Konstruktor unter der des Vergleichens des Arrays von Hand, aber wenns dir um die Notation geht...

Ne andere Möglichkeit wäre

#include <set>

// ...

std::set<bool> tmp_set(array, &array[arraylen]);
if(tmp_set.find(false) == tmp_set.end()) {
  // alles true
}

performancetechnisch gilt da aber das gleiche wie für valarray.

[volkard]

smasher1985 schrieb:

Nehmt mal bitte Stellung

ok. ich hab mit MinGW compiliert.

Messen ist sauschwer. Aber ich dachte mir schon, daß da was nicht stimmen kann.
Ich messe dies:

#include <iostream> 

typedef unsigned long long u64;

#ifdef __MSCVER__
#pragma warning(default:4035)
inline u64 rdtsc(){
	__asm	rdtsc
}
#pragma warning(disable:4035)//warning C4035: no return value
#else
inline u64 rdtsc() {
  u64 tmp;
  __asm volatile("rdtsc" : "=A" (tmp));
  return tmp;
}
#endif

using namespace std; 

// hier hab ich den ersten Parameter angepasst... 
inline bool areAllTrue(bool* array,int arrayend){ 
   for(int i=0;i<arrayend;++i) 
      if(!array[i])//wenn einer mit false gefunden wird 
         return false;//dann sind nicht alle true 
   return true;//wenn keine false in der schleife gefunden wurde, sind's true 
} 

int g;
void foo(){
	++g;//garantier, daß nix wegoptimiert wird
}

int main() 
{ 
	int const NUM=1000000;
    bool array[100];
    for (int j=0; j<100; ++j) 
        array[j] = (rdtsc()!=0); //garantier, daß der compiler nachher nix wegoptimiert
	u64 time;

    /// CAMPERS METHODE 1 
    time=-rdtsc();
    { 
        for (int j=0; j < NUM; ++j) { 
            bool allTrue; 
            for( int i = 0; ( allTrue = bool( array[ i ] ) ) && ++i < 100; ); 
            if (allTrue) foo(); 
        } 

    } 
    time+=rdtsc();
    cout <<"Camper1 "<<time<< endl; 

    /// CAMPERS METHODE 2 
    time=-rdtsc();
    { 
        for (int j=0; j < NUM; ++j) { 
			int i = 0;//musste i aus der schlefe nehmen, sonst compiliert's nicht
            for (; bool( array[ i ] ) && ++i < 100; ); 
            if (i >= 100) { 
                foo(); 
            } 
        }
    } 
    time+=rdtsc();
    cout <<"Camper2 "<<time<< endl; 

    /// VOLKARDS METHODE (leicht verändert) 
    time=-rdtsc();
    { 
        for (int j=0; j < NUM; ++j) { 
            if(areAllTrue(array,100)) {    
                foo(); 
            } 
        } 
    } 
    time+=rdtsc();
    cout <<"Volkard "<<time<< endl; 

	cout<<'('<<g<<')'<<endl;
}

ausgabe:
Camper1 461972848
Camper2 646757321
Volkard 494893179
(3000000)

jo, so sind deine messungen.
jetzt lege ich meinen code mal an den anfang, wo unser prozess noch
hohe priorität hat und nicht als langrechner abgestuft wurde.

#include <iostream> 

typedef unsigned long long u64;

#ifdef __MSCVER__
#pragma warning(default:4035)
inline u64 rdtsc(){
	__asm	rdtsc
}
#pragma warning(disable:4035)//warning C4035: no return value
#else
inline u64 rdtsc() {
  u64 tmp;
  __asm volatile("rdtsc" : "=A" (tmp));
  return tmp;
}
#endif

using namespace std; 

// hier hab ich den ersten Parameter angepasst... 
inline bool areAllTrue(bool* array,int arrayend){ 
   for(int i=0;i<arrayend;++i) 
      if(!array[i])//wenn einer mit false gefunden wird 
         return false;//dann sind nicht alle true 
   return true;//wenn keine false in der schleife gefunden wurde, sind's true 
} 

int g;
void foo(){
	++g;
}

int main() 
{ 
	int const NUM=1000000;
    bool array[100];
    for (int j=0; j<100; ++j) 
        array[j] = (rdtsc()!=0); 
	u64 time;

    /// VOLKARDS METHODE (leicht verändert) 
    time=-rdtsc();
    { 
        for (int j=0; j < NUM; ++j) { 
            if(areAllTrue(array,100)) {    
                foo(); 
            } 
        } 
    } 
    time+=rdtsc();
    cout <<"Volkard "<<time<< endl; 

    /// CAMPERS METHODE 1 
    time=-rdtsc();
    { 
        for (int j=0; j < NUM; ++j) { 
            bool allTrue; 
            for( int i = 0; ( allTrue = bool( array[ i ] ) ) && ++i < 100; ); 
            if (allTrue) foo(); 
        } 

    } 
    time+=rdtsc();
    cout <<"Camper1 "<<time<< endl; 

    /// CAMPERS METHODE 2 
    time=-rdtsc();
    { 
        for (int j=0; j < NUM; ++j) { 
			int i = 0;//musste i aus der schlefe nehmen, sonst compiliert's nicht
            for (; bool( array[ i ] ) && ++i < 100; ); 
            if (i >= 100) { 
                foo(); 
            } 
        }
    } 
    time+=rdtsc();
    cout <<"Camper2 "<<time<< endl; 

	cout<<'('<<g<<')'<<endl;
}

ausgabe:
Volkard 397708167
Camper1 423422744
Camper2 549747252
(3000000)

merke: nur durch erhöhen der anzahl der mesungen erreicht man nicht unbeding eine steigerung
der genauigkeit.

am genauesten wird generell gemessen, wenn man von sehr vielen messungen den kleinsten messwert nimmt. denn schneller als ohne störenden fremden einfluss gehts nicht. aber störende einflüsse können auf modernen maschinen so mannigfaltig viele sein, daß man sie beim messen einfach immer mal drin hat.

das führt direkt zu diesem code (bin auf dieses messverfahren sehr stolz):

#include <iostream> 

typedef unsigned long long u64;

#ifdef __MSCVER__
#pragma warning(default:4035)
inline u64 rdtsc(){
	__asm	rdtsc
}
#pragma warning(disable:4035)//warning C4035: no return value
#else
inline u64 rdtsc() {
  u64 tmp;
  __asm volatile("rdtsc" : "=A" (tmp));
  return tmp;
}
#endif

using namespace std; 

// hier hab ich den ersten Parameter angepasst... 
inline bool areAllTrue(bool* array,int arrayend){ 
   for(int i=0;i<arrayend;++i) 
      if(!array[i])//wenn einer mit false gefunden wird 
         return false;//dann sind nicht alle true 
   return true;//wenn keine false in der schleife gefunden wurde, sind's true 
} 

int g;
void foo(){
	++g;
}

void volkard(bool array[10000]){
	if(areAllTrue(array,10000))
		foo();
}

void camper1(bool array[10000]){
	bool allTrue; 
	for( int i = 0; ( allTrue = bool( array[ i ] ) ) && ++i < 10000; ); 
	if (allTrue) foo(); 
}

void camper2(bool array[10000]){
	int i = 0;//musste i aus der schlefe nehmen, sonst compiliert's nicht
	for (; bool( array[ i ] ) && ++i < 10000; ); 
	if (i >= 10000) { 
		foo(); 
	} 
}

u64 measure(void(*f)(bool[10000])){
    bool array[10000];
    for (int j=0; j<10000; ++j) 
        array[j] = (rdtsc()!=0); 

	u64 minTime=u64(-1);
	int left=10000;
	while(left--){
		u64 time=-rdtsc();
		(*f)(array);
		time+=rdtsc();
		if(time<minTime){
			minTime=time;
			left=10000;
		}
    } 
	return minTime;
}

int main() 
{ 
    cout <<"Volkard "<<measure(&volkard)<< endl; 
    cout <<"camper1 "<<measure(&camper1)<< endl; 
    cout <<"camper2 "<<measure(&camper2)<< endl; 
	cout<<'('<<g<<')'<<endl;
}

ausgabe:
Volkard 26404
camper1 26404
camper2 26404
(30008)

dann bin ich ins netz gegangen und hab noch ein paarmal gemessen:
Volkard 26389
camper1 26394
camper2 26394
(39654)

Volkard 26394
camper1 26394
camper2 26389
(48521)

Volkard 26389
camper1 26394
camper2 26389
(63805)

wir stellen fest: ich kann sachen mit so grossen laufzeiten nicht auf den takt genau messen. aber den fehler und 1% riegt man schon.
und im rahmen der messgenauigkeit sind alle drei lösungen identisch.

[camper]

interessante lösung - wenns recht ist, benutz ich die in zukunft auch
das ganze nochmal mit vc++7.1 (mal zusätzlich mit der assemblervariante - die ist allerdings nicht ganz optimal)
Volkard 30112
VolkardAsm 6636
camper1 30112
camper2 30112
(30006)

nichts besonders ... ganz im gegensatz zu icl 8.1
Volkard 30108
VolkardAsm 6632
camper1 20088
camper2 16788
(37531)
soweit ich das erkennen kann, liegt das daran, dass die volkard version nicht vektorisiert werden kann - das ist eben bei if statements schwierig.

edit: es muss übrigens #ifdef _MSC_VER heissen

[groovemaster]

volkard schrieb:

alleTrue &&= array[i];

Sollte das ein Gag sein?

[volkard]

camper schrieb:

nichts besonders ... ganz im gegensatz zu icl 8.1
Volkard 30108
VolkardAsm 6632
camper1 20088
camper2 16788
(37531)
soweit ich das erkennen kann, liegt das daran, dass die volkard version nicht vektorisiert werden kann - das ist eben bei if statements schwierig.

ka. mag dem argument aber nicht folgen. warum sollten schleifenabbrüche was anderes als if sein? bringt umsortieren wieder was? dann wär's fiesmal schlechtes function alignment.

den faktor 5 für die asm-lösung hab ich mit c++ auch.

inline bool areAllTrueOpt(bool* array,int arrayend){
	while(arrayend%8)
		if(array[--arrayend]) return false;
	while(reinterpret_cast<size_t>(array)&3)
		if(!*array++) return false;
	for(int i=0;i<arrayend/8;++i){
		if(((long long*)array)[i++]!=0x0101010101010101ULL) return false;
	}
	return true;
}

be mir bringen dir 8-er-schritte aber keinen hauch mehr als 4-er-schritte. hab mal 8-er genommen, falls du nen 64-bittigen prozessor hast.

[camper]

volkard schrieb:

camper schrieb:

nichts besonders ... ganz im gegensatz zu icl 8.1
Volkard 30108
VolkardAsm 6632
camper1 20088
camper2 16788
(37531)
soweit ich das erkennen kann, liegt das daran, dass die volkard version nicht vektorisiert werden kann - das ist eben bei if statements schwierig.

ka. mag dem argument aber nicht folgen. warum sollten schleifenabbrüche was anderes als if sein? bringt umsortieren wieder was? dann wär's fiesmal schlechtes function alignment.

den faktor 5 für die asm-lösung hab ich mit c++ auch.

inline bool areAllTrueOpt(bool* array,int arrayend){
	while(arrayend%8)
		if(array[--arrayend]) return false;
	while(reinterpret_cast<size_t>(array)&3)
		if(!*array++) return false;
	for(int i=0;i<arrayend/8;++i){
		if(((long long*)array)[i++]!=0x0101010101010101ULL) return false;
	}
	return true;
}

be mir bringen dir 8-er-schritte aber keinen hauch mehr als 4-er-schritte. hab mal 8-er genommen, falls du nen 64-bittigen prozessor hast.

so gehts nat. auch. die 8er schritte waren den mmx befehlen geschuldet, die ja gleich 8byte mit einem mal aufnehmen. sonst sind 4er schritte im allgemeinen eusreichend. die sache mit der vektorisierung - ich hab nat. zuerst den assemblertext angeschaut, bevor ich das behauptet habe. sicherlich ist das if dem schleifenabbruch in der schleifenbedingung im grunde equivalent. allerdings für den compiler anhand von formalen kriteren kaum zu erkennen. möglich das sich das in späteren versionen ändert.

[Shade Of Mine]

Das schöne ist: nur volkards Version lässt sich so optimieren, da es eben eine Funktion ist Bei campers Variante müsste man die Stellen im Code suchen und dort Copy&Pasten...

[0xdeadbeef]

Je nach Compiler könnte das hier ne portablere Variante von Volkards MEthode sein:

#include <cstring>

using namespace std;

bool all_are_true(bool *arr, int arraylen) {
  static bool true_arr[8] = { true, true, true, true,
                                       true, true, true, true };

  if(memcmp(arr, true_arr, arraylen % 8))
    return false;
  arr += arraylen % 8;
  for(int i = 0; i < arraylen / 8; ++i) {
    if(memcmp(arr, true_arr, 8))
      return false;
    arr += 8;
  }
  return true;
}

Der gcc zum Beispiel implementiert die Funktion intrinsic, als dürfte da kein Geschwindigkeitsverlust entstehen. Glaube ich...