Schnellwettbwerb: Absolute Zahl

Beitrag von **cloidnerux** » Fr Mär 02, 2012 7:08 pm

Ergebnisse:
Der Code:

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

LARGE_INTEGER start, end, frequency;

int AbsoluteXin( int i )
{
	if( *reinterpret_cast< unsigned int * >( &i ) & 0x80 ) return ~i+1;

	return i;
}

int AbsoluteCloidnerux(int a)
{
	return ((a < 0)?(~(a-1)):(a));
}

const int HALFRANGE = 0x80000000;

int AbsoluteFatLobyte(int x)
{
    int submask = x >> 31;

    x += HALFRANGE;
    x += HALFRANGE - ((x & submask) << 1);
    
    return x;
}

int AbsoluteFatLobyte2(int x)
{
    int submask = x >> 31;

    x -= ((x & submask) << 1);
    
    return x;
}

void TestFunction(int (*TestFunction)(int))
{
	for(int i = -100000; i < 100000; i++)
	{
		if(TestFunction(i) != ((i < 0)?(i*-1):(i)))
		{
			std::cout << TestFunction(i) << " " << i << "  failed!" << std::endl;
			return;
		}
	}
	QueryPerformanceCounter(&start);
	for(int i = -10000000; i < 10000000; i++)
	{
		TestFunction(i);
	}
	QueryPerformanceCounter(&end);
	double elapsed = (double)(end.QuadPart  - start.QuadPart) / (double)(frequency.QuadPart);
	std::cout << "Time: " << elapsed << std::endl;
}

int main()
{
	if(!QueryPerformanceFrequency(&frequency))
	{
		std::cout << "Performance counter not supported!" << std::endl;
		return 0;
	}
	for(int i = 0; i < 10; i++)
	{
		std::cout << "Durchgang: " << i << std::endl;
		std::cout << "cloidnerux:  ";
		TestFunction(AbsoluteCloidnerux);
		std::cout << "Xin:         ";
		TestFunction(AbsoluteXin);
		std::cout << "Fat-Lobyte:  ";
		TestFunction(AbsoluteFatLobyte);
		std::cout << "Fat-Lobyte2: ";
		TestFunction(AbsoluteFatLobyte);
	}
	return 0;
}

Die Ergebnisse, Normal ohne Optimierungen:

Code: Alles auswählen

Durchgang: 0
cloidnerux:  Time: 1.02007
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.974177
Fat-Lobyte2: Time: 0.981317
Durchgang: 1
cloidnerux:  Time: 0.953523
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.990207
Fat-Lobyte2: Time: 0.972756
Durchgang: 2
cloidnerux:  Time: 0.952685
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.997275
Fat-Lobyte2: Time: 1.03233
Durchgang: 3
cloidnerux:  Time: 0.983867
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 1.07335
Fat-Lobyte2: Time: 1.08516
Durchgang: 4
cloidnerux:  Time: 0.938563
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 1.00118
Fat-Lobyte2: Time: 0.987632
Durchgang: 5
cloidnerux:  Time: 0.946707
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.979446
Fat-Lobyte2: Time: 1.10497
Durchgang: 6
cloidnerux:  Time: 1.01846
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 1.30061
Fat-Lobyte2: Time: 1.14477
Durchgang: 7
cloidnerux:  Time: 0.961695
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 1.0205
Fat-Lobyte2: Time: 1.1046
Durchgang: 8
cloidnerux:  Time: 0.941668
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 1.04531
Fat-Lobyte2: Time: 1.03076
Durchgang: 9
cloidnerux:  Time: 0.936019
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.973315
Fat-Lobyte2: Time: 1.0083

Mit O2(Geschwindigkeit):

Code: Alles auswählen

Durchgang: 0
cloidnerux:  Time: 0.118843
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.116535
Fat-Lobyte2: Time: 0.117512
Durchgang: 1
cloidnerux:  Time: 0.116734
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.117401
Fat-Lobyte2: Time: 0.119287
Durchgang: 2
cloidnerux:  Time: 0.11475
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.115192
Fat-Lobyte2: Time: 0.115893
Durchgang: 3
cloidnerux:  Time: 0.118736
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.119174
Fat-Lobyte2: Time: 0.118722
Durchgang: 4
cloidnerux:  Time: 0.118791
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.123701
Fat-Lobyte2: Time: 0.123066
Durchgang: 5
cloidnerux:  Time: 0.11262
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.112666
Fat-Lobyte2: Time: 0.1144
Durchgang: 6
cloidnerux:  Time: 0.117093
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.111267
Fat-Lobyte2: Time: 0.11453
Durchgang: 7
cloidnerux:  Time: 0.112701
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.112284
Fat-Lobyte2: Time: 0.112488
Durchgang: 8
cloidnerux:  Time: 0.112713
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.115529
Fat-Lobyte2: Time: 0.114998
Durchgang: 9
cloidnerux:  Time: 0.111399
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.111935
Fat-Lobyte2: Time: 0.113689

O2 und Inlinefunktionen:

Code: Alles auswählen

Durchgang: 0
cloidnerux:  Time: 0.128479
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.112748
Fat-Lobyte2: Time: 0.117027
Durchgang: 1
cloidnerux:  Time: 0.115995
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.11165
Fat-Lobyte2: Time: 0.111743
Durchgang: 2
cloidnerux:  Time: 0.113584
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.114818
Fat-Lobyte2: Time: 0.114798
Durchgang: 3
cloidnerux:  Time: 0.110545
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.108895
Fat-Lobyte2: Time: 0.108947
Durchgang: 4
cloidnerux:  Time: 0.10894
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.114672
Fat-Lobyte2: Time: 0.109757
Durchgang: 5
cloidnerux:  Time: 0.109177
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.109285
Fat-Lobyte2: Time: 0.109069
Durchgang: 6
cloidnerux:  Time: 0.109543
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.117185
Fat-Lobyte2: Time: 0.110174
Durchgang: 7
cloidnerux:  Time: 0.109838
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.109862
Fat-Lobyte2: Time: 0.117252
Durchgang: 8
cloidnerux:  Time: 0.115763
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.116145
Fat-Lobyte2: Time: 0.135786
Durchgang: 9
cloidnerux:  Time: 0.125808
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.125284
Fat-Lobyte2: Time: 0.115544

Volle Optimierung: O2, Inlinefunktionen, Schnellere Code, Volle Optimierung:

Code: Alles auswählen

Durchgang: 0
cloidnerux:  Time: 0.0849635
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.0956691
Fat-Lobyte2: Time: 0.0926058
Durchgang: 1
cloidnerux:  Time: 0.0778466
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.0893933
Fat-Lobyte2: Time: 0.087585
Durchgang: 2
cloidnerux:  Time: 0.0768679
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.0877169
Fat-Lobyte2: Time: 0.0892249
Durchgang: 3
cloidnerux:  Time: 0.0767437
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.0905347
Fat-Lobyte2: Time: 0.0893481
Durchgang: 4
cloidnerux:  Time: 0.0764694
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.0880393
Fat-Lobyte2: Time: 0.0879141
Durchgang: 5
cloidnerux:  Time: 0.0776811
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.0883155
Fat-Lobyte2: Time: 0.0871818
Durchgang: 6
cloidnerux:  Time: 0.0767918
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.0874031
Fat-Lobyte2: Time: 0.0886975
Durchgang: 7
cloidnerux:  Time: 0.0786858
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.087149
Fat-Lobyte2: Time: 0.0885176
Durchgang: 8
cloidnerux:  Time: 0.0774453
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.0883684
Fat-Lobyte2: Time: 0.0882981
Durchgang: 9
cloidnerux:  Time: 0.0777648
Xin:         -100000 -100000  failed!
Fat-Lobyte:  Time: 0.0880373
Fat-Lobyte2: Time: 0.0881971

Xins code schlägt fehl, er hat mir aber bisher noch keinen neune geschickt.

fat-lobyte · Beitrag von **fat-lobyte** » Fr Mär 02, 2012 7:25 pm

Ein bisschen Kritik:

1) Das schwank leider ziemlich :-/
Vor allem wenns so knapp wie zwischen dir und mir ist, ist das nicht unbedeutend.
Keine Ahnung, was man da machen kann.

2) Du verhinderst durch den Funktionszeiger inlining. Wie soll das Funktionieren?? Bitte verwende ein Template:

Code: Alles auswählen

template<int TestedFunction(int)>
void TestFunction()
{
   for(int i = -100000; i < 100000; i++)
   {
      if(TestedFunction(i) != ((i < 0)?(i*-1):(i)))
      {
         std::cout << TestedFunction(i) << " " << i << "  failed!" << std::endl;
         return;
      }
   }
   QueryPerformanceCounter(&start);
   for(int i = -10000000; i < 10000000; i++)
   {
      TestedFunction(i);
   }
   QueryPerformanceCounter(&end);
   double elapsed = (double)(end.QuadPart  - start.QuadPart) / (double)(frequency.QuadPart);
   std::cout << "Time: " << elapsed << std::endl;
}

3) Weil ich so ein schlechter Verlierer bin, werde ich jetzt sagen dass das unfair ist und verlange, dass ich meine Version auch auf eine Zeile zusammenkürzen darf:

Code: Alles auswählen

int myabs(int x)
{
    return x - ((x & (x>>31)) << 1);
}

(bitte

)

Beitrag von **Xin** » Fr Mär 02, 2012 7:45 pm

cloidnerux hat geschrieben:Ergebnisse:
Die Ergebnisse, Normal ohne Optimierungen:
Code: Alles auswählen
Xin:         -100000 -100000  failed!
Xins code schlägt fehl, er hat mir aber bisher noch keinen neune geschickt.

Xin liegt auf der Couch und hat Kopfschmerzen.
Außerdem hasst Xin Little-Endian.

Ansonsten würde ich hier tatsächlich mal return (x<0)? -x : x ins Rennen schicken.

Beitrag von **cloidnerux** » Fr Mär 02, 2012 7:56 pm

3) Weil ich so ein schlechter Verlierer bin, werde ich jetzt sagen dass das unfair ist und verlange, dass ich meine Version auch auf eine Zeile zusammenkürzen darf:

Wir wollen mal nicht so sein, also hab ich mal kurz deine Vorschläge eingebaut:
0. So viel Zeit brauchen wir, außer dein 2ter Code, der braucht manchmal etwas Zeit.
Ich habe gerade mal die Anzahl der Iterationen Quadriert, immer noch 0.

(x<0)? -x : x

Sieht sehr ähnlich mit meinem Code aus^^

Beitrag von **Xin** » Fr Mär 02, 2012 7:59 pm

cloidnerux hat geschrieben:
(x<0)? -x : x
Sieht sehr ähnlich mit meinem Code aus^^

Mir scheint Deiner aufwendiger. Als ich meinen abgeschickt habe mit ~i+1, habe ich mich gefragt, warum ich eigentlich -i vermeide...

fat-lobyte · Beitrag von **fat-lobyte** » Fr Mär 02, 2012 8:06 pm

cloidnerux hat geschrieben:Wir wollen mal nicht so sein, also hab ich mal kurz deine Vorschläge eingebaut:

Juhu, danke

0. So viel Zeit brauchen wir, außer dein 2ter Code, der braucht manchmal etwas Zeit.
Ich habe gerade mal die Anzahl der Iterationen Quadriert, immer noch 0.

Du meinst jetzt mit dem Template statt dem Funktionszeiger?
Sieh dir mal den Assemblercode an, und kuck ob die Funktion überhaupt generiert wird. Könnte mir vorstellen, dass das einfach wegoptimiert wird, da ja nach der Schleife das Ergebnis nicht verwendet wird.
Wie wärs mit nem Ringpuffer, in den geschrieben wird? Beeinflusst die Messung, aber mal kucken...

Dann brauchen wir halt genauere Messungen. Ich kenn mich auf Windows nicht so gut aus, aber auf Linux gibts utime(3), da gehts auf Nanosekunden genau. Ich glaube übrigens da passt was mit QueryPerformanceCounter nicht. Kuck nochmal in der MSDN nach, was genau schiefgelaufen sein könnte, oder kuck dich nach alernativen um.

Beitrag von **cloidnerux** » Fr Mär 02, 2012 8:09 pm

Mir scheint Deiner aufwendiger. Als ich meinen abgeschickt habe mit ~i+1, habe ich mich gefragt, warum ich eigentlich -i vermeide...

Jein, also natürlich ist es umständlicher erst Minus 1 zu rechnen und dann die Inverse zu Bilden, die frage ist aber wie es umgesetzt wird...
Im Prinzip ist es das gleiche^^

Aber im großen und Ganzen, fand ich es einen Durchaus Interessanten Wettbewerb, auch wenn es nicht viele Teilnehmer gab.
Es ging um ein SERH triviales Problem, nur ein Vorzeichen entfernen. Das hätte jeder der ein wenig C/C++ gerlernt hat hinbekommen.
Nun hat man aber Versucht möglichst Effizienten Code zu schreiben, wie es Xin und auch Fat-lobyte versucht haben um dann zu den ernüchternden Ergebnis zu kommen: Mit einer Verzweigung geht es doch schneller.
Fazit: Wir haben hier ein triviales Problem, das mal ganz Trivial gelöst wurde.

P.S: Ich schau nochmal wegen der Zeitmessung, hab den code aus unserem wiki.
Alternativ könnt ihr den Code auch bei euch ausführen, geht ja mehr um den relativen Vergleich.

Beitrag von **Xin** » Fr Mär 02, 2012 8:35 pm

cloidnerux hat geschrieben:
Mir scheint Deiner aufwendiger. Als ich meinen abgeschickt habe mit ~i+1, habe ich mich gefragt, warum ich eigentlich -i vermeide...
Jein, also natürlich ist es umständlicher erst Minus 1 zu rechnen und dann die Inverse zu Bilden, die frage ist aber wie es umgesetzt wird...
Im Prinzip ist es das gleiche^^

Man sollte auf die Anweisungen im Prozessor zurückgreifen und dann möglichst auf die, die wenig Takte brauchen.

Das Problem ist quasi zu klein zum optimieren. Darum habe ich auch an die mehr die Fließkommazahlen gedacht, denn bei ints gibt's eigentlich keine Optimierungmöglichkeit. (denke ich)

cloidnerux hat geschrieben: Aber im großen und Ganzen, fand ich es einen Durchaus Interessanten Wettbewerb, auch wenn es nicht viele Teilnehmer gab.

Habe ich Dir gesagt - Ankündigen, damit die Leute überhaupt wissen, wann sie da zu sein haben.

cloidnerux hat geschrieben:Nun hat man aber Versucht möglichst Effizienten Code zu schreiben, wie es Xin und auch Fat-lobyte versucht haben um dann zu den ernüchternden Ergebnis zu kommen: Mit einer Verzweigung geht es doch schneller.

Mein Code war im Prinzip Unsinn, ich kam von den Fließkommazahlen und habe das einfach bei ints fortgesetzt.
Und das offensichtlich auch noch falsch.

cloidnerux hat geschrieben:P.S: Ich schau nochmal wegen der Zeitmessung, hab den code aus unserem wiki.
Alternativ könnt ihr den Code auch bei euch ausführen, geht ja mehr um den relativen Vergleich.

Wenn Du schon den Wettbewerb ausrufst, dann mach auch den Vergleich B-)

fat-lobyte · Beitrag von **fat-lobyte** » So Mär 04, 2012 9:00 pm

So. Ich hab dann nochmal nachgemessen, und komme zum Schluss: das Problem ist wirklich zu klein.

Da kann man fast nix rausmessen, die Laufzeiten unterscheiden sich nicht signifikant (liegen im Bereich von 1/10-sigma

).

Außerdem hab ichs nicht geschafft die Standardabweichung runterzudrücken, bei manchen Läufen geht sie bis zu 30 % rauf!! Vielleicht hat jemand da Ideen dazu, aber ich glaub da kann man nur auf nem Realtime-System was dagegen machen. Naja, hier ist der Code:

perftest.hpp

abs.cpp

Kompilieren mit

Code: Alles auswählen

g++ -O2 -std=c++0x -Wall -lrt    abs.cpp   -o abs

Hier ein einigermaßen "schönes" Ergebnis:

Code: Alles auswählen

Testing function fat-lobyte 
Experiment with N = 30:
	Timer resolution: 0.001 microseconds
	Average: 134 microseconds.
	Standard deviation: 9.28 microseconds.
	Relat. standard deviation: 6.91%

Testing function Xin 
Experiment with N = 30:
	Timer resolution: 0.001 microseconds
	Average: 134 microseconds.
	Standard deviation: 7.55 microseconds.
	Relat. standard deviation: 5.63%

Testing function cloidnerux 
Experiment with N = 30:
	Timer resolution: 0.001 microseconds
	Average: 134 microseconds.
	Standard deviation: 5.68 microseconds.
	Relat. standard deviation: 4.24%

Sehr unbefriedigend

Beitrag von **cloidnerux** » So Mär 04, 2012 9:25 pm

Da kann man fast nix rausmessen, die Laufzeiten unterscheiden sich nicht signifikant (liegen im Bereich von 1/10-sigma ).

Jop, ist definitiv ein Problem moderner Betriebssysteme: Mit Intelligenter Task-Verwaltung, Resourcen-Management und Multithreading, kann man da meiner Meinung nach nicht auf einen definitiven Wert kommen, deswegen habe ich auch 10 mal das ganze gemessen, um dann ein Mittelwert finden zu können.

Sehr unbefriedigend

Jop, wenn man so einen Schnellwettbewerb wiederholen will, muss das besser geregelt werden.

Vielleicht hat jemand da Ideen dazu, aber ich glaub da kann man nur auf nem Realtime-System was dagegen machen.

Dann sollte man sich überlegen, ein solches System aufzusetzen^^
Ich hab hier sicherlich noch irgendeinen Freien Computer, auf den man ein Realtime-OS installieren kann.

MfG cloidnerux

Community

Einstieg

Sprachen

Bibliotheksfunktionen

Fachthemen

Schnellwettbwerb: Absolute Zahl

Re: Schnellwettbwerb: Absolute Zahl

Re: Schnellwettbwerb: Absolute Zahl

Re: Schnellwettbwerb: Absolute Zahl

Re: Schnellwettbwerb: Absolute Zahl

Re: Schnellwettbwerb: Absolute Zahl

Re: Schnellwettbwerb: Absolute Zahl

Re: Schnellwettbwerb: Absolute Zahl

Re: Schnellwettbwerb: Absolute Zahl

Re: Schnellwettbwerb: Absolute Zahl

Re: Schnellwettbwerb: Absolute Zahl