Increment vs. decrement

Vladimir Lenin

In een ver verleden meende ik ooit eens gehoord te hebben dat een for-loop sneller met decrement gaat dan met increment. Nu had ik het er een paar weken geleden eens over met een paar medestudenten van mij en die waren niet meteen overtuigd. We hebben de test gedaan in een paar talen en op een aantal systemen met volgende resultaten:

Java

- Unix: increment werkt 36% sneller

- Microsoft Windows: idem maar allebei doen ze er bijna dubbel zo lang over dan bij Unix

(Microsoft Windows werkte wel op een 32-bit machine terwijl Unix op een 64-bit machine werkte)

C++

- Unix: gelijke tijd (af en toe een percentje meer of minder)

Ti-Basic

- Ti-89 Titanium (Heeft een 80x86-CPU-familie processor): Decrement werkt zo'n 16% sneller

hoe komt men die verschillen uit, hoe komt het dat een for-loop low-level sneller in decrement werkt, en in high-level niet. En wat maakt dat Windows er zo lang over doet of komt dit enkel door de machine

Cycloon

En wat maakt dat Windows er zo lang over doet of komt dit enkel door de machine

Dat is moeilijk te zeggen natuurlijk, het kan zowel aan de JVM liggen, als aan de manier waarop windows de hardware aanspreekt. Voor de rest hangt alles natuurlijk af van hoe de hardware is opgebouwd. Ik zou best kunnen geloven dat je verschillende resultaten krijgt wanneer je dezelfde test draait op verschillende computers met hetzelfde OS.

Revelation

Heb je ook bekeken wat in ASM het snelst werkt? Als je aftelt naar 0 kan je JZ gebruiken, die sneller werkt dan de andere compares. Verder moet je de telrichting misschien veranderen, maar dat is maar 1 commando. Het verschil lijkt minimaal, heel erg low-level. Misschien kan C gewoon beter optimaliseren bij aftellen.

Vladimir Lenin

Nou Ti-Basic lijkt me al behoorlijk low-level. Ik dacht dat decrement beter werkte omdat je dan ik je vergelijking een constante schrijft, waardoor dat 1 geheugenoproep uitspaart.

Stel:

- Increment

Code: Selecteer alles

for(int i = 0; i < n; i++) {

   ...

}

- Decrement

Code: Selecteer alles

for(int i = n-1; i >= 0; i--) {

   ...

}

Iedere keer wanneer de processor de for-loop passeert komt hij bij het vergelijkingsgedeelte aan. Bij een increment moet hij dan de waarde van n uit het geheugen opvragen wat tijd kost, terwijl de decrement zijn waarde al in het bevel zelf heeft staan, je spaart dus per keer dat je de for doorloopt een geheugenoproep uit. Het probleem is dat ik dat niet zie in de resultaten.

Ik beheers ASM nie, al ken ik wel iemand die dat wel doet, ik heb het hem al eens gevraagd, maar zijn antwoord was dat een groter dan of gelijk aan operator 4 cycli nodig had terwijl een kleiner dan 1 cycli nodig heeft, maar dan kan ik mij moeilijk indenken, zeker omdat bijde operatoren in code zeer vaak gebruikt worden, en dus wel geoptimaliseerd moeten zijn. Punt is hoe verklaar je de verschillen in increment en decrement

Cycloon

Vladimir Lenin schreef:Stel:

- Increment
Code: Selecteer alles
for(int i = 0; i < n; i++) {

   ...

}
- Decrement
Code: Selecteer alles
for(int i = n-1; i >= 0; i--) {

   ...

}
Iedere keer wanneer de processor de for-loop passeert komt hij bij het vergelijkingsgedeelte aan. Bij een increment moet hij dan de waarde van n uit het geheugen opvragen wat tijd kost, terwijl de decrement zijn waarde al in het bevel zelf heeft staan, je spaart dus per keer dat je de for doorloopt een geheugenoproep uit. Het probleem is dat ik dat niet zie in de resultaten.

Wat had je gedacht van:

Code: Selecteer alles

for(int i = -n; i < 0; i++) {

   ...

}

Schwartz

Even een test doorgedraaid...

In pascal werkt de normale net zo snel als de downto.

In pascal kan men bij for alleen met +1 of -1 tellen.

Hij telt dan wel in 27 seconden 50.000.000.000 keer...

De processor werkt op 3 gigahertz....

En de for die loopt dan op 1.85 gigahertz.

En 10.000.000.000 met een inc(a) werkt die af in ongeveer 8 seconden.

Dat is nog zo'n 1.25 gigahertz ongeveer...

De 10.000.000.000 stappen met een WHILE lus met een inc(a) werkt die af in ongeveer 11 seconden.

En als men de inc(x) verander in x:=x+1 dan verandert er weining.

Als men inc(x,2) doet en de while test is dubbel zo groot (we hebben dan net zo veel stappen) dan hebben we ongeveer 3 seconden tijdswinst....

vreemd eigenlijk...

Naar aanleiding van deze testen denk ik dat het probleem van verschil in de inc en dec toe te wijzen is aan de compileerinstellingen die men heeft...

Hierdoor worden er extra testen ingevoegd of niet die de compileersnelheid drastisch kunnen veranderen.

Hoe minder testen hoe beter de software door de processor kan gaan.

virtlink

Waarom decrement in een loop vaak sneller werkt dan increment

Op de x86 processoren is er (onder andere) een instructie LOOP die controleert of de waarde in het ECX register 0 is. Is dit niet het geval, wordt de loop herhaald. Het kost dus voor een decrement-loop maar twee loop instructies: Voorbeeld:

Code: Selecteer alles

loopstart:

; Doe iets

dec ecx

; Decrement ECX

loop loopstart	 ; LOOP als ECX != 0

Voor increment bestaat zoiets niet, omdat je kan stoppen bij elk willekeurig getal. De machinecode hiervoor (minstens drie instructies voor de increment-loop) zou als volgt zijn (als je tot 10 telt bijvoorbeeld):

Code: Selecteer alles

loopstart:

; Doe iets

inc ecx

; Increment ECX

cmp ecx, 10		; CoMPare ECX met 10

jl loopstart	   ; Jump if Lower (dan 10)

Nu denk je misschien: één instructie meer, dat maakt toch niet zo'n groot verschil? Maar de LOOP instructie is zwaar geoptimaliseerd, en werkt daarom alleen met ECX en de waarde 0. De compare (CMP) instructie is minder efficiënt, en kost dus wat meer processortijd. Maar die kan je dan ook gebruiken met elk register en elke waarde.

Waarom higher level languages verschillen in wat sneller is

De compilers van die talen proberen zo efficiënt mogelijke code te genereren. Voor talen die direct naar machine code compileren kan het zijn dat bijvoorbeeld een increment in een for-loop als decrement wordt uitgevoerd (mits deze optimalisatie mogelijk is) of worden er andere trucjes toegepast.

Voor talen die eerst naar een tussentaal compileren (C# en Java) zouden dit soort optimalisaties bij het uitvoeren op het laatste moment moeten worden gedaan. Omdat dit het programma vertraagt wordt deze code minder geoptimaliseerd.

Aries

Een kleine kanttekening...

In tegenstelling tot java waarvan de tussencode geinterpreteerd wordt (is dus eigenlijk een soort basic

)

Wordt de bytecode (gecompileerd programma in tussencode) van C# voor de eerste run op DIE machine gecompileert en geoptimaliseerd voor die ene machine. C# is dus veel effectiever dan java.

C++ rules uiteraard

Cycloon

Java wordt niet volledig geïnterpreteerd, veel zaken worden intussen ook "gecompileerd" at runtime.

virtlink

Aries schreef:Een kleine kanttekening...

In tegenstelling tot java waarvan de tussencode geinterpreteerd wordt (is dus eigenlijk een soort basic )

Wordt de bytecode (gecompileerd programma in tussencode) van C# voor de eerste run op DIE machine gecompileert en geoptimaliseerd voor die ene machine. C# is dus veel effectiever dan java.

Niet juist:

Machinecode vs. Byte code: C# en Java worden beide naar byte-code gecompileerd voor een 'Virtuele Machine' (VM), die ook wel de runtime wordt genoemd, en die eenmalig moet worden opgestart; deze machine zal met JIT (Just-in-time-compilatie) de bytecode eenmalig naar machinecode compileren en laten uitvoeren, en is ook verantwoordelijk voor voorzieningen zoals garbage collection. [...] Het gebruik van de virtuele machine heeft als nadeel de overhead van het opstarten en het (eenmalig) compileren; anderzijds maakt het bepaalde optimalisaties in het compileren mogelijk die bij compilatie vooraf onmogelijk zijn.

Bron: Wikipedia: Vergelijking met Java en C#

Vladimir Lenin

Maar in C# kun je wel unmanaged code en assembler aanspreken al waren ze in een soort van virtuele dll ondergebracht. Het is dus mogelijk om al te compileren naar een soort van C programma bij C# al weet ik niet hoe dat zit met Java. Het punt is dat de twee talen een tussentaal gebruiken en een virtuele machine nodig hebben, alleen zijn er bij de twee talen andere prioriteiten gesteld wat betreft snelheid, zo doet C# er vijf keer langer over om een exception te handlen, dat komt omdat ze bijvoorbeeld niet aangekondigd moet worden, voordeel is echter wel dat programmeurs niet beperkt zijn in de exceptionlist van de programmeur van de bovenliggende klasse. Hier een codevoorbeeld van unmanaged code in C#:

Code: Selecteer alles

extern "C" __declspec(dllexport) char* __stdcall getCPUType() {

	static char pszCPUType[13];

	memset(pszCPUType, 0, 13);

	_asm {

		mov eax, 0

		cpuid

		mov pszCPUType[0], bl

		mov pszCPUType[1], bh

		ror  ebx, 16

		mov pszCPUType[2], bl

		mov pszCPUType[3], bh

		mov pszCPUType[4], dl

		mov pszCPUType[5], dh

		ror  edx, 16

		mov pszCPUType[6], dl

		mov pszCPUType[7], dh

		mov pszCPUType[8], cl

		mov pszCPUType[9], ch

		ror  ecx, 16

		mov pszCPUType[10], cl

		mov pszCPUType[11], ch

	}

	pszCPUType[12] = '\0';

	return pszCPUType;

}

Voor meer info over performantie van talen:

http://boykin.acis.ufl.edu/?p=79

Wetenschapsforum

Laatste berichten

Nieuwsberichten

Increment vs. decrement

Increment vs. decrement

Re: Increment vs. decrement

Re: Increment vs. decrement

Re: Increment vs. decrement

Re: Increment vs. decrement

Re: Increment vs. decrement

Re: Increment vs. decrement

Re: Increment vs. decrement

Re: Increment vs. decrement

Re: Increment vs. decrement

Re: Increment vs. decrement