Springen naar inhoud

Increment vs. decrement


  • Log in om te kunnen reageren

#1

Vladimir Lenin

    Vladimir Lenin


  • >250 berichten
  • 829 berichten
  • Ervaren gebruiker

Geplaatst op 15 mei 2009 - 21:58

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
"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 16 mei 2009 - 10:39

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.

#3

Revelation

    Revelation


  • >1k berichten
  • 2364 berichten
  • Technicus

Geplaatst op 16 mei 2009 - 14:30

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.
ďQuotation is a serviceable substitute for wit.Ē - Oscar Wilde

#4

Vladimir Lenin

    Vladimir Lenin


  • >250 berichten
  • 829 berichten
  • Ervaren gebruiker

Geplaatst op 16 mei 2009 - 18:37

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
for(int i = 0; i < n; i++) {
   ...
}
- Decrement
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
"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)

#5

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 17 mei 2009 - 09:30

Stel:
- Increment

for(int i = 0; i < n; i++) {
   ...
}
- Decrement
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:

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

#6

Schwartz

    Schwartz


  • >250 berichten
  • 691 berichten
  • Verbannen

Geplaatst op 17 mei 2009 - 19:45

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.
Een computertaal is voor mensen, niet voor de computer.

#7

virtlink

    virtlink


  • >100 berichten
  • 158 berichten
  • Ervaren gebruiker

Geplaatst op 25 juni 2009 - 19:18

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:
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):
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.
"Niet gehinderd door enige kennis van zaken..."

#8

Aries

    Aries


  • >25 berichten
  • 83 berichten
  • Ervaren gebruiker

Geplaatst op 12 augustus 2009 - 08:05

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 :P

#9

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 12 augustus 2009 - 10:29

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

#10

virtlink

    virtlink


  • >100 berichten
  • 158 berichten
  • Ervaren gebruiker

Geplaatst op 12 augustus 2009 - 11:35

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#
"Niet gehinderd door enige kennis van zaken..."

#11

Vladimir Lenin

    Vladimir Lenin


  • >250 berichten
  • 829 berichten
  • Ervaren gebruiker

Geplaatst op 12 augustus 2009 - 15:21

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#:
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
"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures