Forsida
Temaer
Sjangere
Raskeste måte å bytte to tall
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.
Testprogram
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;
}
Gransking av assembly
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
Optimalisering av assembly
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
Testprosedyre
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.
Resultater
| 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 |
Diskusjon
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.
Ring gratis med mobilen
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.
Linux Virtual Server på 1-2-3
Tema: Programvare; sjanger: Artikler
Skrevet av Stig Magnus Halvorsen den 16. mai 2009 kl 19:06:44; Kommentarer: 2
På jobben satt jeg opp en lokal server for noen uker siden. Nylig ble jeg nødt til å konfigurere den for virtuelle servere (flere apachesider på en tjener), da snakka jeg med noen av linuxekspertene på jobben. Og ut i fra det kom jeg opp med denne guiden. Dette har jeg testet på CentOS (lokal jobbserver) og Mandriva (nerdvar). Ser ingen grunn til at det ikke skal virke på andre linuxdistribusjoner, dog muligens andre mappebaner.
Først må du logge inn som root, enten via et grafisk miljø eller shell. Deretter må du navigere deg til mappen /etc/httpd/conf.d. Her må vi lage en ny tekstfil. Denne kun av sikkerhetsårsaker, og siden apache lister de virtuelle tjenerene alfabetisk MÅ denne være først. Derfor lagrer vi denne som 01.conf. Den må inneholde:
# Set up empty virtual host so that original content doesn't change NameVirtualHost *:80 <VirtualHost *:80> </VirtualHost>
Som sagt er sikkerhet grunnen til denne filen må eksistere. Hvis ikke vil alle filene i root-mappa bli lista om en forsøker å koble til en virtuell server som ikke eksisterer på tjeneren. Navnet 01 er viktig for at den skal leses først av de virtuelle tjenerne. Apache fungerer slik at den velger den første tilgjengelige virtuelle tjeneren om man prøver å koble til en ikke-eksisterende virtuell server. Det denne filen gjør er istede å vise webroot (/var/www/html).
Så kan vi sette opp våre virtuelle servere som individuelle .conf-filer i samme mappe. Slik kan feks. example.com.conf se ut:
LogFormat "%h %v %u %t \"%r\" %>s %b \"%{Referer}i\" \"%{User-Agent}i\" \"%{Cookie}i\""
<VirtualHost *:80>
ServerName www.example.com
ServerAlias example.com vvv.example.com
DocumentRoot /home/user/html
ErrorLog logs/examplecom-error_log
CustomLog logs/examplecom-access_log
<Directory /home/user/html>
Options FollowSymLinks -Indexes
AllowOverride None
Order allow,deny
Allow from all
</Directory>
</VirtualHost>
DocumentRoot og Directory må selvfølgelig være den samme mappen. Det første den gjør er å definere den virtuelle tjeneren for å så sette konfigruasjonen. Dette blir mappen det virtuelle domenet linker til (webrootmappen). Linje 1, 8 og 9 er for at feilmeldingen skal logges i en individuel fil for den virtuelle tjeneren. Disse kan tas bort om en ønsker at feilmeldingene skal logges i den vanlige errorloggen.
Etter de forskjellige .conf-filene er lagret må vi restarte apache. For å sjekke at det ikke er noen feil i conf-filene kan en kjøre /etc/init.d/httpd configtest først. Deretter er det bare å kjøpe domenet example.com og linke det til din servers ip-adresse. Det er viktig at domenet er det samme som i conf-fila. En kan også teste det fra en maskin ved å endre hosts-fila. I Windows XP finner du den her: C:/WINDOWS/system32/drivers/etc. La den se ca. slik ut:
127.0.0.1 localhost <serverip> example.com www.example.com
Lagre fila, omstart nettleseren og skriv inn example.com i adressefeltet. Og that's it! Denne hostsfila kan være morsom å bruke for å feks. lure venner til å tro at sider som feks. Facebook er blitt hacka ved å sette IPen til feks. Nerdvar ;).
Lykke til!
Herschel & Planck i bane
Tema: Vitenskap; sjanger: Artikler
Skrevet av Andreas Nordal den 14. mai 2009 kl 16:06:50; Kommentarer: 0
De to romteleskopene tok av i en Ariane-5-rakett fra Fransk Guyana ved 15:30-tiden i dag og har nettopp skilt lag i rommet som planlagt. Begge vil bli plassert i bane rundt lagrangepunkt 2, som er i skyggen av jorda i en avstand på ca 1,5·109 m. De vil være framme om 2 måneder, Herschel først.
Les mer på esa.eu
Hvordan laste ned fra NRK nett-TV
Tema: Internett; sjanger: Artikler
Skrevet av Andreas Nordal den 13. januar 2009 kl 00:25:32; Kommentarer: 5
- Søk etter "var WM_url" i kildekoden til den aktuelle siden. OPPDATERING: Søk heller etter "mplayer2".
- Den etterfølgende lange URL-en leder til en XML-fil. Last ned denne.
- De to like URL-ene som starter på "mms://" og slutter på ".wmv" leder til filmen. Last den ned med et program som støtter mms-protokollen, for eksempel msdl eller VLC.
Trykk på bildet for å se en film som viser prosedyren (12,6 MB Ogg Theora uten lyd). Opptaket er gjort med recordmydesktop.
Bønn til NRK: Så enkelt kan det gjøres
Med denne videoen vil jeg samtidig demonstrere hvordan video på nett kan gjøres enklere og mer brukervennlig enn NRK har gjort. Slik er videoen satt inn:
<a href="NRKnettTVhvordan.ogv"><img src="NRKnettTVhvordan_500.jpg" width="500" height="371"/></a>
Ett klikk er det som skal til for Konqueror (min favorittnettleser) å spille av filmen ved bruk av HTML-koden ovenfor. Nettlesere som ikke vet hva de skal gjøre med filmen vil normalt spørre hvilket program den skal åpnes med. Bruk av <embed> er kanskje mer naturlig, men den endelige løsningen er HTML 5. Dessverre er dette ønsketenkning før nettleserne begynner å støtte det:
<div style="width:500px; height:371px;">
<video>
<source src="NRKnettTVhvordan.ogv" type="video/ogg; codecs="theora, vorbis""/>
</video>
</div>
Heldigvis begynner NRK å merke at Windows Media Video var et dårlig valg av videoformat. Var det ikke det vi visste? Jeg håper NRK gjør som meg, følger regjeringen og legger ut video i Ogg Theora. Det som derimot filmen min viser, er at måten den settes inn på nettsiden kan være vel så viktig for brukeropplevelsen.