Tema: Vitenskap; sjanger: Artikler
Skrevet av Andreas Nordal den 12. oktober 2009 kl 03:47:21; Kommentarer: 8
Å bytte om verdiene på to tall er en problemstilling som man ofte kommer over når man programmerer. Det er en viktig del av mange algoritmer, særlig sorteringsalgoritmer, og selvfølgelig en masse andre som man ikke skulle tro hadde noe med bytting av tall å gjøre. Dessuten er det en typisk operasjon som dataprogrammet kanskje gjør veldig mange ganger. Dette er så enkelt og viktig at det fins liten unnskyldning for å gjøre det feil.
Jeg har testet de 4 metodene i C/C++ som jeg syns var mest aktuelle (i håp om å finne den raskeste), samt 3 assembly-modifikasjoner av disse. Til sammen 7 tester nummerert fra 0 til 6. Følgende kildekode i C/C++ vil, som vi straks skal se, kunne kompileres til 4 forskjellige programmer.
/* testbenk.c */
#include <stdio.h>
#include <inttypes.h>
#ifdef __cplusplus
# include <algorithm> //std::swap
#endif
int main(){
#ifdef SWAP
int a=666, b=13;
register int32_t i=0;
do{//Bytt om a og b 2^32 ganger
# if SWAP==0
a ^= b;
b ^= a;
a ^= b;
# elif SWAP==1
# ifndef __cplusplus
# error "Dette er C++"
# endif
std::swap(a, b);
# elif SWAP==2
int temp = a;
a = b;
b = temp;
# elif SWAP==3
register int temp = a;
a = b;
b = temp;
# endif
}while(++i);
printf("%d %d\n", a, b);
#endif //defined SWAP
return 0;
}
Når vi kompilerer, la oss gå veien om assembly, og titte på hva den stakkars prosessoren plages med:
gcc -S -DSWAP=0 testbenk.c -o swap0.s g++ -S -DSWAP=1 testbenk.c -o swap1.s gcc -S -DSWAP=2 testbenk.c -o swap2.s gcc -S -DSWAP=3 testbenk.c -o swap3.s
Her ser vi utdrag av hva kildekoden koker ned til av instruksjoner i hvert av de 4 tilfellene. Merk at assemblykode er forskjellig fra maskin til maskin; disse utdragene er fra den første testen (se resultater). Det som har med tallbytting å gjøre er markert med feit skrift.
Utdrag fra swap0.s:
movl $666, -8(%rbp)
movl $13, -4(%rbp)
movl $0, -20(%rbp)
.L2:
movl -4(%rbp), %eax
xorl %eax, -8(%rbp)
movl -8(%rbp), %eax
xorl %eax, -4(%rbp)
movl -4(%rbp), %eax
xorl %eax, -8(%rbp)
addl $1, -20(%rbp)
cmpl $0, -20(%rbp)
jne .L2
Utdrag fra swap1.s:
_ZSt4swapIiEvRT_S1_:
pushq %rbp
movq %rsp, %rbp
movq %rdi, -24(%rbp)
movq %rsi, -32(%rbp)
movq -24(%rbp), %rax
movl (%rax), %eax
movl %eax, -4(%rbp)
movq -32(%rbp), %rax
movl (%rax), %edx
movq -24(%rbp), %rax
movl %edx, (%rax)
movq -32(%rbp), %rdx
movl -4(%rbp), %eax
movl %eax, (%rdx)
leave
ret
movl $666, -4(%rbp)
movl $13, -8(%rbp)
movl $0, -20(%rbp)
.L4:
leaq -8(%rbp), %rsi
leaq -4(%rbp), %rdi
call _ZSt4swapIiEvRT_S1_
addl $1, -20(%rbp)
cmpl $0, -20(%rbp)
setne %al
testb %al, %al
jne .L4
Utdrag fra swap2.s:
movl $666, -12(%rbp)
movl $13, -8(%rbp)
movl $0, -20(%rbp)
.L2:
movl -12(%rbp), %eax
movl %eax, -4(%rbp)
movl -8(%rbp), %eax
movl %eax, -12(%rbp)
movl -4(%rbp), %eax
movl %eax, -8(%rbp)
addl $1, -20(%rbp)
cmpl $0, -20(%rbp)
jne .L2
Utdrag fra swap3.s:
movl $666, -8(%rbp)
movl $13, -4(%rbp)
movl $0, -20(%rbp)
.L2:
movl -8(%rbp), %edx
movl -4(%rbp), %eax
movl %eax, -8(%rbp)
movl %edx, -4(%rbp)
addl $1, -20(%rbp)
cmpl $0, -20(%rbp)
jne .L2
swap4.s: Når det fornuftstridig viste seg under testene at såkalt registerswap var treigere enn vanlig temp-swap, tydet det på at koden i swap3.s ikke var optimal. Like fullt, det er mulig å se at swap3.s burde ha vært raskere enn swap2.s. Et bevis for dette er at ved å gjøre om "-8(%rbp)" til "-12(%rbp)" og "-4(%rbp)" til "-8(%rbp)" i swap3.s, og å variere bruken av registere litt i swap2.s, oppnår vi at den eneste forskjellen mellom disse 2 filene er 2 linjer ekstra i swap2.s, samtidig som virkemåten til begge programmene er bevart:
; swap2.s (modifisert)
|
; swap3.s (modifisert) aka swap4.s
|
Den modifiserte swap3.s ble lagret som swap4.s.
5: En skulle kanskje tro at xchg (exchange) hørtes ut som en ideell instruksjon for vårt formål. Med utgangspunkt i swap4.s lagde jeg swap5.s:
; swap5.s
movl -12(%rbp), %eax
xchgl -8(%rbp), %eax
movl %eax, -12(%rbp)
6: Ved hjelp av "inc" i stedet for "add" og å bruke registeret eax som tellevariabel, ble swap4.s forbedret til swap6.s:
movl $666, -12(%rbp)
movl $13, -8(%rbp)
movl $0, %eax
.L2:
movl -12(%rbp), %edx
movl -8(%rbp), %ebx
movl %ebx, -12(%rbp)
movl %edx, -8(%rbp)
incl %eax
cmpl $0, %eax
jne .L2
gcc -s swap0.s -o swap0 g++ -s swap1.s -o swap1 gcc -s swap2.s -o swap2 gcc -s swap3.s -o swap3 gcc -s swap4.s -o swap4 gcc -s swap5.s -o swap5 gcc -s swap6.s -o swap6 gcc -s swap7.s -o swap7
Hadde det ikke vært for at vi må bruke g++ i ett tilfelle:
for i in *.s; do gcc -s $i -o ${i%.?}; done
bash$ time ./swap1
666 13 #Uinteressant: Programmet virker.
real 0m27.270s #Uinteressant: Så lang tid det faktisk tok.
user 0m27.226s #Interessant: CPU-tid i user-mode.
sys 0m0.040s #Interessant: CPU-tid i protected-mode.
Kjøretiden ble målt som i eksempelet over. Som antydet, er det summen av CPU-tid som teller, altså user + sys. Når det står flere tall i samme celle i tabellen, er det fordi jeg har testet flere ganger. Tiden er i sekunder.
| Maskin | 0: XOR-swap | 1: std::swap | 2: temp-swap | 3: registerswap (gcc) | 4: registerswap (fiksa) | 5: xchg-swap | 6: Så bra jeg kan i assembly |
|---|---|---|---|---|---|---|---|
| ny laptop: Intel Core 2 Duo T8100 2,1GHz (2 kjerner), GCC 4.3.2, Linux 2.6.27.29 x86_64 | 34,226s 34,066s | 27,266s 27,306s | 11,629s 11,805s | 12,485s 12,565s | 9,737s 9,781s | 72,569s 72,817s | 9,465s 9,397s |
| gammel stasjonær: AMD Athlon XP 2600+ 1,9GHz, GCC 4.3.0, Linux 2.6.27.25 i686 | 39,19s | 47,20s | 14,16s | 16,17s | 12,41s | 49,47s | 8.93s |
| ny server: Intel Xeon 3,2 GHz (4 prosessorer), GCC 4.2.4, Linux 2.6.24-24 i686 | 20,48s 20,35s | 40,77s 40,44s | 10,61s 10,72s | 8,18s 8,26s | 6,92s 7,13s | ||
| gammel server: Intel Pentium III Coppermine 936MHz (2 prosessorer), GCC 4.1.1, Linux 2.6.18 i686 | 87,34s 87,38s | 111,22s 109,07s | 36,85s 36,83s | 23,39s 23,79s | 18,41s 18,40s | ||
| gammel laptop: Intel Pentium 4 2,0GHz, GCC 4.3.2, Linux 2.6.27 i686 | 116,471s 116,219s | 105,799s 100,218s | 40,050s 37,802s | 28,274s 27,650 | 22,333s 21,786s | ||
| server: Intel Xeon 2,83 GHz, GCC 4.2.4, Linux 2.6.24 | 28,12s | 23,88s | 10,16s | 8,74s | 7,71s |
0 (XOR-swap): Så elegant, men akk så treigt. XOR-swap fører til stans i prosessorens samlebånd, fordi hver instruksjon må vente på resultatet av den forrige. Grunnen til at moderne prosessorer kan ha klokkefrekvenser over et par hundre MHz er bruken av samlebånd.
1 (std::swap): Et funksjonskall tar ekstra tid, og indirekte adressering gir lang kode. Programmet swap1 ble forresten 8 byte større enn hver av de andre. Std::swap er rett og slett dømt til å være treig.
2-4 (temp-swap vs registerswap): Jeg kan ikke kåre noen vinner mellom disse 2. Selv om all fornuft sier at det skal være raskere å bruke et register til mellomlagring framfor å bruke RAM, stemte det ikke med mitt program i C. Jeg har vist at dette skyldes GCCs ugunstige plassering av variablene på stakken, og at registerswap faktisk ble raskere enn temp-swap ved å plassere variablene som i temp-swap. Ikke vet jeg om fenomenet skyldes cache-kollisjon eller hva det er. Det ser ut til å være reproduserbart på flere maskiner, men det hele kan jo være en tilfeldighet ved akkurat mitt program.
5 (xchg): Er dette en ubrukelig instruksjon?
6 (Så bra jeg kan i assembly): Dette vil funke i alle fall på i386.
Tema: Programvare; sjanger: Artikler
Skrevet av Stig Magnus Halvorsen den 3. oktober 2009 kl 03:31:48; Kommentarer: 0
Statistikk fra etter lansering av den første iPhone viser at det har vært en liten eksplosjon i bruken av internett på mobiltelefoner. Spesielt nå som de fleste nye telefoner kommer med innebygd WiFi og flere leverandører gir mye eller ubegrenset mobilnett for pengene. Hvorfor ikke da utnytte dette fullt ut? Gjør en det, vil det å ringe og å sende SMS bli nesten eller helt gratis!
Skype er et program som brukes til IP-telefoni og direktemeldinger. Ligner på MSN, men fokuset har ligger på funksjonen om å kunne ringe hverande gratis. Programmet har eksistert for datamaskin siden 2003, men er i senere år også blitt lansert for mobiltelefoner og bærbare håndholdte enheter. Dette i tillegg til å skaffe deg en skypekonto på skype.com er mer eller mindre alt du trenger!
Skype for mobil fungerer på iPhone, telefoner med Windows Mobile, Nokia N800/N810 og PSP. Skype er også til en rekke andre telefoner, sjekk om din telefon kan ha Skype Lite
Det er noen bakdeler med dette. En må installere et ekstra program på mobilen, en må enten ha et internettvennlig abonnement eller være innenfor WiFi-sone og de du vil ringe må også ha skype og være pålogget. Men om dette hadde blitt en standard med tiden, så vil det kun være til gode for almennheten. Det betyr bedre gratis kommunikasjon til folket og at abonnementstilbudene blir betraklige bedre pga konkurranse.