|
|
 | Lige og ulige tal
Fra : Chris |
Dato : 24-03-04 20:28 |
|
Hej,
Hvordan finder jeg ud af (i C, ikke C++) om et tal er lige eller
ulige?
Chris
| |
 Husted (24-03-2004)
| Kommentar
Fra : Husted |
Dato : 24-03-04 20:36 |
|
> Hvordan finder jeg ud af (i C, ikke C++) om et tal er lige eller
> ulige?
f.eks. ved at bruge modulo, eksempel:
int x = 10;
if( x % 2 == 0 )
{
/* Lige */
}
else
{
/* ulige */
]
| |
Jesper Toft (24-03-2004)
| Kommentar
Fra : Jesper Toft |
Dato : 24-03-04 20:37 |
|
Chris wrote:
> Hej,
>
> Hvordan finder jeg ud af (i C, ikke C++) om et tal er lige eller
> ulige?
int tal;
if( tal&1 ) {
ulige
} else {
lige
}
--
/Jesper
| |
Michael Banzon (24-03-2004)
| Kommentar
Fra : Michael Banzon |
Dato : 24-03-04 03:52 |
|
"Jesper Toft" <news@bzImage.dk> skrev:
> if( tal&1 ) {
Jeg vel umiddelbart tro at denne mulighed er hurtigst
(hurtigere end tal % 2 == 0) på langt de fleste plat-
forme...
--
Michael Banzon
http://southbound.dk/
http://southbound.dk/blog/
| |
 Igor V. Rafienko (25-03-2004)
| Kommentar
Fra : Igor V. Rafienko |
Dato : 25-03-04 16:37 |
|
[ Michael Banzon ]
[ ... ]
> > if( tal&1 ) {
>
> Jeg vel umiddelbart tro at denne mulighed er hurtigst (hurtigere end
> tal % 2 == 0) på langt de fleste plat- forme...
Jeg vil umiddelbart tro at denne "muligheten" har absolutt ingen
garantier for å virke. Alt gnålet om "hurtigst" er således svært lite
relevant.
Og når man først maser om hastighet: en god kompilator vil kunne
foreta en optimalisering i slike trivielle tilfeller, der det er mulig
(som fx. med 2'er komplement samt visse antagelser om
bitrepresentasjonen til tallene). gcc gjør det tom. uten at man ber
den om det.
Så, hvis noen kunne forklare meg appellen i det bitvise svineriet, vil
jeg være meget takknemlig.
*shrug*
ivr
--
<html><form><input type crash></form></html>
| |
J. Nielsen (25-03-2004)
| Kommentar
Fra : J. Nielsen |
Dato : 25-03-04 21:01 |
|
Hej Igor!
> Jeg vil umiddelbart tro at denne "muligheten" har absolutt ingen
> garantier for å virke. Alt gnålet om "hurtigst" er således svært lite
> relevant.
Det forstår jeg sku ikke ... hvorfor skulle det ikke virke?
> Og når man først maser om hastighet: en god kompilator vil kunne
> foreta en optimalisering i slike trivielle tilfeller, der det er mulig
> (som fx. med 2'er komplement samt visse antagelser om
> bitrepresentasjonen til tallene). gcc gjør det tom. uten at man ber
> den om det.
Det er vel en fordel selv at fortage optimeringerne? Jeg mener, skulle man
nu få behov for at debugge sit kode på baggrund af en disassembling, så er
man jo i problemer, hvis kompileren har optimeret koden?!
| |
Mogens Hansen (25-03-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 25-03-04 23:14 |
|
J. Nielsen wrote:
>>Jeg vil umiddelbart tro at denne "muligheten" har absolutt ingen
>>garantier for å virke. Alt gnålet om "hurtigst" er således svært lite
>>relevant.
>
>
> Det forstår jeg sku ikke ... hvorfor skulle det ikke virke?
Hvorfor skulle det virke ?
Hint:
Hvilke binære repræsentationer af af heltal er tilladt for en C
implementering ?
Specielt, hvilken indflydelse har den anvendte binære repræsentation på
mindst betydende bit egnethed til bestemmelse af hvorvidt tallet er lige
eller ulige ?
Konkret eksempel:
Med toers komplement:
000...00010 = +2
000...00001 = +1
000...00000 = 0
111...11111 = -1
111...11110 = -2
Med en's komplement:
000...00010 = +2
000...00001 = +1
000...00000 = +0
111...11111 = -0
111...11110 = -1
111...11101 = -2
og det er ikke de eneste tilladte repræsentationer.
[8<8<8<]
> Det er vel en fordel selv at fortage optimeringerne?
Man skriver koden til 2 målgrupper:
* computeren der skal eksekvere det
* mennesker der skal læse og vedligeholde koden
Det er en fordel at udtrykke hvad man ønsker programmet skal gøre så
direkte som muligt.
Hvis man ønsker at finde ud af om et tal deleligt med 2 (lige) er det
meget direkte at skrive
if(i % 2 == 0)
i stedet for at gøre antagelser om den underliggende binære
repræsentation (uden at have styr på hvad konsekvensen er).
Hvis man ønsker at finde ud af om mindst betydende bit et 1, er det
meget direkte at skrive
if(i & 1)
> Jeg mener, skulle man
> nu få behov for at debugge sit kode på baggrund af en disassembling, så er
> man jo i problemer, hvis kompileren har optimeret koden?!
At se bort fra gode compileres evne til at foretage optimeringer er dumt.
De færreste programmører kan hamle op med en effektiv optimizer til
moderne (super-scalare, pipeline, multi niveau hukommelse hieraki) CPU'er.
Man debugger typisk sin kode med compiler-options der sikrer at
compileren ikke laver nævneværdig optimering.
Dermed er sammenhængen mellem source kode, program-flow og assembler
instruktioner relativ simpelt.
Man satser derefter på at compilerens optimizer (og CPU'en etc) virker
korrekt, og kører sine test-cases igen på den optimerede kode.
Venlig hilsen
Mogens Hansen
| |
Niels Dybdahl (26-03-2004)
| Kommentar
Fra : Niels Dybdahl |
Dato : 26-03-04 15:59 |
|
> At se bort fra gode compileres evne til at foretage optimeringer er dumt.
Nu er vi nogen som er nødt til at bruge MS Visual Studio. Jeg har prøvet at
compilere begge eksempler med følgende resultat:
if (j % 2):
00402986 and ecx,80000001h
0040298C jns testthis+13h (00402993)
0040298E dec ecx
0040298F or ecx,0FEh
00402992 inc ecx
00402993 je testthis+22h (004029a2)
if (j & 1)
004029A2 test al,1
004029A4 je testthis+27h (004029a7)
Optimeringen er sat til max speed.
Så jo moderne compilere kan stadig optimere så håbløst at man kan gøre det
bedre selv.
Niels Dybdahl
| |
Mogens Hansen (26-03-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 26-03-04 20:05 |
|
"Niels Dybdahl" <ndy@removethisesko-graphics.com> wrote in message
news:4064453d$0$165$edfadb0f@dtext02.news.tele.dk...
> > At se bort fra gode compileres evne til at foretage optimeringer er
dumt.
>
> Nu er vi nogen som er nødt til at bruge MS Visual Studio. Jeg har prøvet
at
> compilere begge eksempler med følgende resultat:
Jeps - det havde jeg set inden jeg postede mit indlæg.
Jeg ville stadig ikke bytte
* klarhed i koden
* kodens korrekthed
for en formodentlig lille performance forskel.
Husk at de 2 udtryk generelt ikke er ækvivalente.
[8<8<8<]
> Så jo moderne compilere kan stadig optimere så håbløst at man kan gøre det
> bedre selv.
Spiller dette tilfælge nogen _reel_ rolle ?
Jesper Louis Andersen har beskrevet de relevante overvejelser.
Intel C++ V8 for MS-Windows giver iøvrigt:
;;; if((i % 2) == 0)
mov eax, ebx ;18.6
and eax, 1 ;18.6
$LN6:
test eax, eax ;18.2
jne .B1.5 ; Prob 50% ;18.2
og
mov eax, DWORD PTR [esp+4] ;15.6
$LN3:
;;; if((i & 1) == 0)
test al, 1 ;17.6
$LN4:
jne .B1.3 ; Prob 40% ;17.2
Venlig hilsen
Mogens Hansen
| |
Niels Dybdahl (26-03-2004)
| Kommentar
Fra : Niels Dybdahl |
Dato : 26-03-04 23:49 |
|
> * klarhed i koden
For folk som ikke kender C er ingen af udtrykkene klare. Jeg personlig er
mere vant til bitudgaven, så den er faktisk klarere for mig, men jeg har
også en elektronikbaggrund. For folk med matematisk baggrund er modulus
udgaven måske klarere.
> * kodens korrekthed
> for en formodentlig lille performance forskel.
> Husk at de 2 udtryk generelt ikke er ækvivalente.
Måske ikke generelt, men i praksis er de for det meste. Hvis man skriver et
C program i dag, bruger man stort set altid mindst et API ud over standard
funktionerne. Derved er programmet allerede bundet så meget at de to udtryk
oftest er ækvivalente. Jeg kender faktisk ikke nogen platform, hvor de ikke
er ækvivalente.
> Spiller dette tilfælge nogen _reel_ rolle ?
Hvis et program bruger en del tid til at udføre en opgave, er det relevant
at finde ud af hvordan man kan gøre det hurtigere. Jeg har selv oplevet at
jeg kunne forbedre billedbehandlingstid med omkring en faktor 10 ved at
bruge tabelopslag istedet for beregninger. Jeg har fornylig forbedret andres
formatkonverteringer med en faktor 2-3. I begge tilfælde kræver det kendskab
til hvad kode en compiler laver og hvor lang tid det tager. At vide at AND
er hurtigere end division kan betyde meget.
Niels Dybdahl
| |
Mogens Hansen (27-03-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 27-03-04 10:38 |
|
Niels Dybdahl wrote:
>> * klarhed i koden
>
>
> For folk som ikke kender C er ingen af udtrykkene klare.
Hvor vil du hen med det ?
Det er _fuldkommen_ ligegyldigt i denne sammenhæng.
> Jeg personlig er
> mere vant til bitudgaven,
Hvad du er mest vant til er ligegyldigt i forbindelse med at rådgive andre.
Hvis rådet er dårligt er der grund til at advare imod det, og grund til
at lære og lægge vanerne om.
> så den er faktisk klarere for mig, men jeg har
> også en elektronikbaggrund.
Jeg har en baggrund som elektroingeniør.
Det forhindrer mig ikke i at forstå forskellen på bit operation og en
matematisk operation, og vælge den operation der direkte svarer til hvad
jeg har brug for.
Det oprindelige spørgsmål gik på hvordan man finder ud af om et tal er
er lige.
Man siger at et heltal "m" er lige, hvis og kun hvis der findes et
heltal "d", således at m=2d, hvilket er identisk med at resten ved
division (modulo) m-2d=0.
Det udtrykkes direkte (og idiomatisk) i C som
m % 2 == 0
fuldstændigt uafhængig af den binære repræsentation og performance.
> For folk med matematisk baggrund er modulus
> udgaven måske klarere.
>
>
>> * kodens korrekthed
>>for en formodentlig lille performance forskel.
>>Husk at de 2 udtryk generelt ikke er ækvivalente.
>
>
> Måske ikke generelt, men i praksis er de for det meste.
Der hvor jeg færdes til hverdag er det ikke tilstrækkeligt at tingene
fungerer "for det meste"
> Hvis man skriver et
> C program i dag, bruger man stort set altid mindst et API ud over standard
> funktionerne. Derved er programmet allerede bundet så meget at de to udtryk
> oftest er ækvivalente. Jeg kender faktisk ikke nogen platform, hvor de ikke
> er ækvivalente.
Vi står med 2 bud på løsninger, hvor det for den der bruger binært AND
gælder:
* Den udtrykker ikke direkte hvad man mener
* Den er ikke _garanteret_ til _altid_ at virke
* Der kan muligvis være en _lille_ performance forskel, men det er
svært at forstille sig at det i virkeligheden skulle spille nogen rolle.
På den baggrund er det uforståeligt at der er nogen der vil argumentere
for en sådan løsning.
Det er ikke et enestående eksempel, og det forklarer en del af hvorfor
der findes meget dårlig software fordi der bliver lavet unødvendige,
ukorrekte optimeringer.
Venlig hilsen
Mogens Hansen
| |
Thomas Krog (27-03-2004)
| Kommentar
Fra : Thomas Krog |
Dato : 27-03-04 15:24 |
|
> Måske ikke generelt, men i praksis er de for det meste. Hvis man skriver
et
> C program i dag, bruger man stort set altid mindst et API ud over standard
> funktionerne. Derved er programmet allerede bundet så meget at de to
udtryk
> oftest er ækvivalente.
selvom man bruger et API i et givent projekt kan man fint dele sin kode op
så størstedelen koden er platformsuafhængig. Fx. kan fysik, matematik og
algoritmik fint være platformsuafhængigt mens der er noget grafik- eller
netværkskode der er bundet til en bestemt platform/API. Dermed kan koden
hurtigere flyttes til en anden platform idet man kun behøver at ændre
grafikkoden.
/Thomas
| |
Niels Dybdahl (27-03-2004)
| Kommentar
Fra : Niels Dybdahl |
Dato : 27-03-04 22:02 |
|
> selvom man bruger et API i et givent projekt kan man fint dele sin kode op
> så størstedelen koden er platformsuafhængig. Fx. kan fysik, matematik og
> algoritmik fint være platformsuafhængigt mens der er noget grafik- eller
> netværkskode der er bundet til en bestemt platform/API. Dermed kan koden
> hurtigere flyttes til en anden platform idet man kun behøver at ændre
> grafikkoden.
Det lyder lidt akademisk. I kommercielle programmer bruger man normalt en
lang række APIer: F.eks et til brugerinterfacet, et til filsystemet, et til
en database, et til kommunikationskanaler og nogle til kodemoduler man har
andet steds fra. For det meste vil den største del af koden være bundet til
mindst et af disse APIer og vil være ret besværlig at flytte. Den del af
koden som ikke er bundet til et API, kan man derimod godt prøve at skrive
porterbart. Ironisk nok er det den sidste del af koden, som ofte er den
tidskritiske del og som man derfor gerne vil optimere, hvorved den bliver
mindre porterbar.
Jeg plejer at trække de dele af min kode ud som er tidskritisk og placerer
den i et modul for sig. Denne del optimerer jeg både via compileren og
manuelt, mens den øvrige del af koden ikke bliver optimeret (heller ikke af
compileren - det er alt for farligt hvis der er fejl i dens
optimeringsalgoritmer). Jeg anvender derfor for det meste samme kode til
debugging og til release.
Niels Dybdahl
| |
Mogens Hansen (28-03-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 28-03-04 10:19 |
|
"Niels Dybdahl" <niels@fjern.dettedybdahl.dk> wrote:
> > selvom man bruger et API i et givent projekt kan man fint dele sin kode
op
> > så størstedelen koden er platformsuafhængig. Fx. kan fysik, matematik og
> > algoritmik fint være platformsuafhængigt mens der er noget grafik- eller
> > netværkskode der er bundet til en bestemt platform/API. Dermed kan koden
> > hurtigere flyttes til en anden platform idet man kun behøver at ændre
> > grafikkoden.
>
> Det lyder lidt akademisk. I kommercielle programmer bruger man normalt en
> lang række APIer: F.eks et til brugerinterfacet, et til filsystemet, et
til
> en database, et til kommunikationskanaler og nogle til kodemoduler man har
> andet steds fra. For det meste vil den største del af koden være bundet
til
> mindst et af disse APIer og vil være ret besværlig at flytte.
Hmm...
Det forekommer mig at være uklart hvad begreberne API og platform her
opfattes som, og hvad sammenhængen mellem dem er.
Det forekommer mig også at være uklart hvad målet med argumentationen er i
forhold til denne tråd.
Der er ikke nogen en-til-en sammenhæng mellem et API og en platform (i
betydningen sammensætningen af hardware arkitektur og operativsystem - og
evt. compiler).
Der er derfor ikke nødvendigvis sådan at hvis et program benytter et API er
det bundet til en platform.
ACE, CORBA, Qt og Boost er eksempler på API'er der er uafhængige af
platformen.
Skulle brugen af sådanne API'er have indflydelse på hvordan man bestemmer om
et heltal er lige i C ?
Skulle brugen af sådanne API'er begrunde at man skulle spilde overvejelser
på hvorvidt en mindre klar, ikke portabel måde at bestemme om et heltal er
lige muligvis virker med en given C implementering, når det er almindelig
kendt viden at der findes en måde som er klar og garanteret virker ?
Venlig hilsen
Mogens Hansen
| |
Niels Dybdahl (28-03-2004)
| Kommentar
Fra : Niels Dybdahl |
Dato : 28-03-04 10:36 |
|
> Der er ikke nogen en-til-en sammenhæng mellem et API og en platform (i
> betydningen sammensætningen af hardware arkitektur og operativsystem - og
> evt. compiler).
> Der er derfor ikke nødvendigvis sådan at hvis et program benytter et API
er
> det bundet til en platform.
> ACE, CORBA, Qt og Boost er eksempler på API'er der er uafhængige af
> platformen.
Jeg kan godt finde masser af platforme hvor disse APIer ikke eksisterer.
Altså er de ikke universelt porterbare ligesom AND metoden til ulige tal
heller ikke er det.
Men hvis man ved at AND metoden kan anvendes alle de steder, hvor de APIer
man bruger findes, så bliver ens program ikke mindre porterbart af at man
bruger AND metoden.
> Skulle brugen af sådanne API'er begrunde at man skulle spilde overvejelser
> på hvorvidt en mindre klar, ikke portabel måde at bestemme om et heltal er
> lige muligvis virker med en given C implementering, når det er almindelig
> kendt viden at der findes en måde som er klar og garanteret virker ?
Nu er modulusfunktionen en af de funktioner som oftest er fejlimplementeret,
så der er ingen garanti for at den altid virker. Et program som bruger
modulusfunktionen er ikke universelt porterbart i praksis, kun i teorien.
Årsagen til dette er at der er to grundlæggende opfattelser af hvad modulus
burde gøre: m mod n kan enten levere et positivt tal fra 0 til n-1 eller
levere resten efter divisionen m/n. Jeg ved godt at diverse C standarder
definerer præcist hvad der skal ske, men desværre er det ikke alle compilere
som gør dette fejlfrit og jeg er heller ikke sikker på at de tidligste C
standarder definerede dette.
Niels Dybdahl
| |
Mogens Hansen (28-03-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 28-03-04 11:27 |
|
"Niels Dybdahl" <niels@fjern.dettedybdahl.dk> wrote:
[8<8<8<]
> > Der er derfor ikke nødvendigvis sådan at hvis et program benytter et API
> er
> > det bundet til en platform.
> > ACE, CORBA, Qt og Boost er eksempler på API'er der er uafhængige af
> > platformen.
>
> Jeg kan godt finde masser af platforme hvor disse APIer ikke eksisterer.
Og ... ?
Det var sammenblandingen mellem API og platform der var væsentlig at få rede
på.
[8<8<8<]
> > Skulle brugen af sådanne API'er begrunde at man skulle spilde
overvejelser
> > på hvorvidt en mindre klar, ikke portabel måde at bestemme om et heltal
er
> > lige muligvis virker med en given C implementering, når det er
almindelig
> > kendt viden at der findes en måde som er klar og garanteret virker ?
>
> Nu er modulusfunktionen en af de funktioner som oftest er
fejlimplementeret,
Baseret på hvilke målinger ?
Det forekommer mig at du forsøger at holde fast i et meget spinkelt strå.
> så der er ingen garanti for at den altid virker.
Man kan smide et lige så ligegyldigt modargument på banen: hvem siger at
bitwise AND _altid_ virker på _enhver_ compiler (eller CPU for den sags
skyld).
Man kan forestille sig en masse fejlscenarier, hvor man slet ikke er i stand
til at bestemme om et tal er lige eller ulige uanset metode: compileren er
håbløs defekt implementeret, CPUen er håbløs defekt implementeret, LSB af
databussen er kortsluttet til 0, processoren udsættes for kraftig elektrisk
støj, strømforsyningen til computeren fjernes osv.
Meningen af ethvert udtryk i ethvert programmeringssprog kan gøres
uforudsigeligt af en defekt implementering - men hvad hjælper det udsagn os
?
Diskuterer vi fejl i C implementeringer eller diskuterer vi hvordan man
bestemmer om et tal er lige i C ?
> Et program som bruger
> modulusfunktionen er ikke universelt porterbart i praksis, kun i teorien.
Under hvilke omstændighder er brugen af modulus til bestemmelse af om et tal
er lige i C ikke porterbart i praksis ?
Vær venligst konkret så vi kan få stoppet denne diskution.
> Årsagen til dette er at der er to grundlæggende opfattelser af hvad
modulus
> burde gøre: m mod n kan enten levere et positivt tal fra 0 til n-1 eller
> levere resten efter divisionen m/n.
Vi er formodentlig enige om at 0 er 0, således at
if(i %2 == 0)
opfører sig ens uansert om resultatet fra modulus er positiv eller negativ.
Sammenhængen mellem resultatet af division, multiplikation og modulo er i C
defineret således at der altid gælder
a == (a/b)*b + a%b
Kan du give blot eet eksempel på et scenarie hvor heltalsberegningen
i == (i/2)*2+0
ikke er sandt netop _kun_ for lige tal i C ?
Heltals udtrykket
i % 2 == 0
er i C sandt under eksakt samme betingelser som heltals udtrykket
i == (i/2)*2
er sandt - nemlig hvis og kun hvis i er lige.
Hvor svært kan det være at forstå ?
Venlig hilsen
Mogens Hansen
| |
Niels Dybdahl (29-03-2004)
| Kommentar
Fra : Niels Dybdahl |
Dato : 29-03-04 11:31 |
|
> > > Der er derfor ikke nødvendigvis sådan at hvis et program benytter et
API er
> > > det bundet til en platform.
> > > ACE, CORBA, Qt og Boost er eksempler på API'er der er uafhængige af
> > > platformen.
> >
> > Jeg kan godt finde masser af platforme hvor disse APIer ikke eksisterer.
>
> Og ... ?
> Det var sammenblandingen mellem API og platform der var væsentlig at få
rede på.
Ok; skåret ud i pap: Hvis et program benytter et af disse APIer, så er
programmet bundet til de platforme, hvor disse APIer eksisterer.
> > > Skulle brugen af sådanne API'er begrunde at man skulle spilde
overvejelser
> > > på hvorvidt en mindre klar, ikke portabel måde at bestemme om et
heltal er
> > > lige muligvis virker med en given C implementering, når det er
almindelig
> > > kendt viden at der findes en måde som er klar og garanteret virker ?
> > så der er ingen garanti for at den altid virker.
> Man kan forestille sig en masse fejlscenarier, hvor man slet ikke er i
stand
> til at bestemme om et tal er lige eller ulige uanset metode: compileren er
> håbløs defekt implementeret, CPUen er håbløs defekt implementeret, LSB af
> databussen er kortsluttet til 0, processoren udsættes for kraftig
elektrisk
> støj, strømforsyningen til computeren fjernes osv.
> Meningen af ethvert udtryk i ethvert programmeringssprog kan gøres
> uforudsigeligt af en defekt implementering - men hvad hjælper det udsagn
os ?
> Diskuterer vi fejl i C implementeringer eller diskuterer vi hvordan man
> bestemmer om et tal er lige i C ?
Jeg forstår godt at du er forvirret. Mogens Hansen argumenterer for at man
kan garantere noget virker, mens vi argumenterer for det modsatte.
> > Et program som bruger
> > modulusfunktionen er ikke universelt porterbart i praksis, kun i
teorien.
>
> Under hvilke omstændighder er brugen af modulus til bestemmelse af om et
tal
> er lige i C ikke porterbart i praksis ?
> Vær venligst konkret
Denne gren handler ikke længere om tal er lige eller ulige (Se Thomas Krogs
indlæg). Men her er noget alligevel:
Jeg stoler ikke på om en modulusfunktion leverer positive eller negative
resultater af negative argumenter uden at have afprøvet det først. Jeg har
to gange tidligere været ude for fejlimplementationer. Den ene var i en
Compas Pascal V 2.x og den anden var i en Microsoft C compiler, versionen
kan jeg ikke huske (4.0 eller senere).
Jeg mener ikke at fejlene ville betyde noget for anvendelsen til bestemmelse
af om et tal er lige, så længe man tester mod 0, men de betyder noget i
andre sammenhæng.
Denne
> ... så vi kan få stoppet denne diskution.
Du behøves ikke at deltage...
Niels Dybdahl
| |
Mogens Hansen (31-03-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 31-03-04 23:19 |
|
Niels Dybdahl wrote:
[8<8<8<]
> Ok; skåret ud i pap: Hvis et program benytter et af disse APIer, så er
> programmet bundet til de platforme, hvor disse APIer eksisterer.
Hvad har det at gøre med hvorvidt bitwise and kan benyttes til at
bestemme om et tal er lige ? Ingenting!
Man kan sagtens benytte f.eks. CORBA i en applikation og flytte den fra
en platform med 2'ers komplement til en platform med 1'ers komplement.
De to ting er ortogonale, og det giver derfor ingen mening at kæde dem
sammen.
[8<8<8<]
>>Diskuterer vi fejl i C implementeringer eller diskuterer vi hvordan man
>>bestemmer om et tal er lige i C ?
>
>
> Jeg forstår godt at du er forvirret. Mogens Hansen argumenterer for at man
> kan garantere noget virker,
Det er i C _garanteret_ at udtrykket
i % 2 == 0
er sandt hvis og kun hvis heltallet i er lige. Dette gælder for enhver
platform hvor C er implementeret og uanset om i er af signed eller
unsigned type.
Dette er således et korrekt svar på det oprindelige spørgsmål.
Det er i C _ikke_ garanteret at udtrykket
(i & 1) == 0
er sandt hvis og kun hvis heltallet i er lige.
Dette er således ikke et korrekt svar på det oprindelige spørgsmål (hvor
der intet var nævnt om antagelser om platform, compiler etc.).
Enig ?
> mens vi argumenterer for det modsatte.
Hvem er "vi" ?
Jeg har kun bemærket at Niels Dybdahl har påstået at modulus er en af de
funktioner der oftest er fejlimplementeret, og at et program der bruger
modulus ikke er porterbart i praksis.
[8<8<8<]
> Denne gren handler ikke længere om tal er lige eller ulige (Se Thomas Krogs
> indlæg). Men her er noget alligevel:
> Jeg stoler ikke på om en modulusfunktion leverer positive eller negative
> resultater af negative argumenter uden at have afprøvet det først.
Hvad har nogensinde fået dig til at tro at man kunne stole på det ?
Det er fuldstændigt velspecificeret at det er implementations defineret
hvad fortegnet af resultatet fra modulus er hvis ikke begge argumenter
er positive.
Det kan således variere fra compiler til compiler, og for den sags skyld
fra een version til en anden af samme compiler.
Det er i C _garanteret_, som jeg tidligere har nævnt i denne tråd, at
a == (a/b)*b + a%b
(såfremt b != 0)
Se C++ Standarden §5.6-4 eller C99 §6.5.5-6 for yderligere detaljer.
> Jeg har
> to gange tidligere været ude for fejlimplementationer.
Hvis du hentyder til hvorvidt modulusfunktionen leverer positive eller
negative resultater, hvis mindst eet af argumenterne er negativ, så er
det som påpeget ovenfor _ikke_ en fejl.
Det er _fuldstændigt_ i overvenstemmelse med specifikationen af C (og C++).
Fejlen består i at du ikke kender sproget tilstrækkeligt godt på dette
punkt, men skråsikkert antager at det er en fejl i compileren.
Jeg antog i mit tidligere indlæg at du rent faktisk kendte til dette, og
derfor talte om hyppigheden af rigtige fejlimplementeringer.
Det er netop _viden_ om sådanne deltaljer der gør at man kan skrive
programmer der _garanteret_ virker, i stedet for at antage at fejlen
ligger i compileren.
Det er sådanne detaljer der er væsentlige for med sikkerhed at kunne
sige at brugen af modulus i C _garanteret_ virker til bestemmelse af
hvorvidt et tal er lige eller ulige, og at bitwise and i C _ikke_ er
garanteret til at kunne bruges.
> Den ene var i en
> Compas Pascal V 2.x
Hvad har Pascal med opførslen af modulus i C at gøre ? Ingenting!
[8<8<8<]
> Jeg mener ikke at fejlene ville betyde noget for anvendelsen til bestemmelse
> af om et tal er lige, så længe man tester mod 0, men de betyder noget i
> andre sammenhæng.
Nu var det jo rent faktisk bestemmelse af hvorvidt et tal er lige som
tråden drejede sig om 
Venlig hilsen
Mogens Hansen
| |
Niels Dybdahl (02-04-2004)
| Kommentar
Fra : Niels Dybdahl |
Dato : 02-04-04 10:14 |
|
> Det er i C _garanteret_ at udtrykket
> i % 2 == 0
> Det er i C _ikke_ garanteret at udtrykket
> (i & 1) == 0
> er sandt hvis og kun hvis heltallet i er lige.
> Enig ?
Jeps
> > mens vi argumenterer for det modsatte.
> Hvem er "vi" ?
Det er os to. Du bragte selv en lang række eksempler på at man ikke kan
garantere at
programmer virker.
> > Denne gren handler ikke længere om tal er lige eller ulige (Se Thomas
Krogs
> > indlæg). Men her er noget alligevel:
> > Jeg stoler ikke på om en modulusfunktion leverer positive eller negative
> > resultater af negative argumenter uden at have afprøvet det først.
> Hvad har nogensinde fået dig til at tro at man kunne stole på det ?
Det er ikke mig som stoler på det, men dig der kan garantere at hvis f.eks
(-7)/2==3,
så er (-7)%2==-1 (se nedenfor).
> Det er i C _garanteret_, som jeg tidligere har nævnt i denne tråd, at
> a == (a/b)*b + a%b
> ...
> Fejlen består i at du ikke kender sproget tilstrækkeligt godt på dette
> punkt, men skråsikkert antager at det er en fejl i compileren.
Formlen a == (a/b)*b + a%b var ikke overholdt i disse tilfælde, så det var
fejl i
compilerne. Her er det dig som udtaler sig om noget som du ikke ved nok om.
> Nu var det jo rent faktisk bestemmelse af hvorvidt et tal er lige som
> tråden drejede sig om
Denne gren af tråden handler faktisk om noget andet.
Niels Dybdahl
| |
Mogens Hansen (02-04-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 02-04-04 15:34 |
|
Niels Dybdahl wrote:
[8<8<8<]
>> > mens vi argumenterer for det modsatte.
>>Hvem er "vi" ?
>
>
> Det er os to.
Hmm....
<citat>
Jeg forstår godt at du er forvirret. Mogens Hansen argumenterer for at
man kan garantere noget virker, mens vi argumenterer for det modsatte.
<citat/>
Så der står altså at Mogens Hansen argumenterer for at noget virker, men
vi (altså os to, Niels Dybdahl og Mogens Hansen) argumenterer for det
modsatte
[8<8<8<]
>>>Jeg stoler ikke på om en modulusfunktion leverer positive eller negative
>>>resultater af negative argumenter uden at have afprøvet det først.
>>
>>Hvad har nogensinde fået dig til at tro at man kunne stole på det ?
>
>
> Det er ikke mig som stoler på det, men dig der kan garantere at hvis f.eks
> (-7)/2==3,
> så er (-7)%2==-1 (se nedenfor).
Det har jeg ikke garanteret. Hvor mener du at jeg har garanteret det ?
Du har formodentlig skrevet forkert, således at du mente
(-7)/2==-3
og ikke at resultatet af division kunne blive positivt.
For udtrykket
(-7)/2
er der netop 2 mulige resultat-sæt i C (og C++)
1: (-7)/2== -3 (-7)%2== -1
2: (-7)/2== -4 (-7)%2== 1
Alle andre resultater er en fejl i compileren.
F.eks. vil
3: (-7)/2== -4 (-7)%2== -1
4: (-7)/2== -3 (-7)%2== 1
være en fejlimplementering
For begge tilladte resultatsæt gælder at
a == (a/b)*b + a%b
sådan som det er specificeret i sprog standarden, og som jeg har
refereret til.
Enig ?
[8<8<8<]
> Formlen a == (a/b)*b + a%b var ikke overholdt i disse tilfælde, så det var
> fejl i
> compilerne.
Hvilke tilfælde - jeg kan ikke se hvad du refererer til.
[8<8<8<]
> Her er det dig som udtaler sig om noget som du ikke ved nok om.
Hvad er det _helt_ præcist du mener at jeg har sagt som jeg ikke ved nok
om !!?
Jeg forstod at det du omtalte som fejl i compilernes implementering af
modulus funktion er at sommetider gav den positive resultater og
sommetider negative resultater for samme parametre (hvoraf eet skulle
være negativt) - og dermed havde forskellig opførsel fra compiler til
compiler.
Den forståelse fik jeg bl.a. fra dine udsagn:
<citat>
Jeg stoler ikke på om en modulusfunktion leverer positive eller negative
resultater af negative argumenter uden at have afprøvet det først. Jeg
har to gange tidligere været ude for fejlimplementationer.
<citat/>
og
<citat>
Nu er modulusfunktionen en af de funktioner som oftest er
fejlimplementeret, så der er ingen garanti for at den altid virker. Et
program som bruger modulusfunktionen er ikke universelt porterbart i
praksis, kun i teorien.
Årsagen til dette er at der er to grundlæggende opfattelser af hvad
modulus burde gøre: m mod n kan enten levere et positivt tal fra 0 til
n-1 eller levere resten efter divisionen m/n. Jeg ved godt at diverse C
standarder definerer præcist hvad der skal ske, men desværre er det ikke
alle compilere som gør dette fejlfrit og jeg er heller ikke sikker på at
de tidligste C standarder definerede dette.
<citat/>
som ubetinget kæder det ubestemte ved fortegnet sammen med
fejlimplementering i compilere.
Dette er, som vi nu formodentlig er enig om, _ikke_ en fejl i compilerne.
Hvis det ikke er det som du er de fejl du henviste til, kan du så ikke
helt præcist forklare hvad du mente.
Venlig hilsen
Mogens Hansen
| |
Byrial Jensen (02-04-2004)
| Kommentar
Fra : Byrial Jensen |
Dato : 02-04-04 19:59 |
|
Mogens Hansen wrote:
> For udtrykket
> (-7)/2
> er der netop 2 mulige resultat-sæt i C (og C++)
> 1: (-7)/2== -3 (-7)%2== -1
> 2: (-7)/2== -4 (-7)%2== 1
Det plejede at være sådan i C, men det er ikke tilfældet længere. I C99
er kun mulighed 1 tilladt.
| |
Mogens Hansen (02-04-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 02-04-04 21:34 |
|
"Byrial Jensen" <bjensen@nospam.dk> wrote:
> Mogens Hansen wrote:
> > For udtrykket
> > (-7)/2
> > er der netop 2 mulige resultat-sæt i C (og C++)
> > 1: (-7)/2== -3 (-7)%2== -1
> > 2: (-7)/2== -4 (-7)%2== 1
>
> Det plejede at være sådan i C, men det er ikke tilfældet længere. I C99
> er kun mulighed 1 tilladt.
Ok - tak.
Det lyder også meget fornuftigt. Man kan så håbe at C++ strammer tilsvarende
op.
Venlig hilsen
Mogens Hansen
| |
Ivar (02-04-2004)
| Kommentar
Fra : Ivar |
Dato : 02-04-04 23:47 |
|
Niels Dybdahl skrev:
> Jeg har
> to gange tidligere været ude for fejlimplementationer. Den ene var i en
> Compas Pascal V 2.x og den anden var i en Microsoft C compiler, versionen
> kan jeg ikke huske (4.0 eller senere).
Mange CP/M-compilere (hvis der nogen der kan huske CP/M) havde
fejlbehæftet modulus-rutine. Den mest bruge divisionrutine var fejlbehæftet
og kunne fejlagtigt finde på at sætte den mest betydende bit i resten.
8080 som CP/M var lavet til havde ingen instruktioner til division, så
de enkelte compilere havde deres egen løsning. Desværre havde den
typiske løsning fejl.
Ivar Magnusson
| |
Mogens Hansen (03-04-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 03-04-04 10:50 |
|
"Niels Dybdahl" <ndy@removethisesko-graphics.com> wrote:
> > At se bort fra gode compileres evne til at foretage optimeringer er
dumt.
>
> Nu er vi nogen som er nødt til at bruge MS Visual Studio. Jeg har prøvet
at
> compilere begge eksempler med følgende resultat:
>
[8<8<8< noget assembler kode]
>
> Optimeringen er sat til max speed.
> Så jo moderne compilere kan stadig optimere så håbløst at man kan gøre det
> bedre selv.
Håbløst er et voldsomt ord i denne forbindelse.
Jeg har lavet en _måling _ med AutomatedQA AQTime3.11, på en 700 MHz Pentium
III med et program oversat med Visual C++ .NET 2003 i Release style.
Programmet beregner for hvert heltal i et array om det er lige, og gemmer
resultatet i et array af bool.
Det er nogenlunde det mindste man fornuftigt kan bruge et svar på om tallet
er lige til, og dermed spiller performance af bestemmelsen af om tallet er
lige nogenlunde den størst mulige rolle.
Målingen viser at brugen af modulus er 2-5 % langsommere end brugen af
bitwise and (afhængig af størrelsen på arrayet som afgør om det kan ligge i
cache eller ej).
For programmer der bruger beslutningen til bare lidt mere vil forskellen
være endnu mindre.
Det syntes jeg nærmere er "ikke helt optimalt, men i praksis formodentlig
ubetydeligt" end "håbløst".
Programmet der blev brugt til målingen er
<C++ kode>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
void even_modulus(const vector<int>& vi, vector<bool>& even)
{
for(size_t i = 0; vi.size() != i; ++i) {
even[i] = (vi[i] % 2 == 0);
}
}
void even_bitwise_and(const vector<int>& vi, vector<bool>& even)
{
for(size_t i = 0; vi.size() != i; ++i) {
even[i] = ((vi[i] & 1)== 0);
}
}
int main()
{
const size_t elements = 10*1024;
vector<int> vi(elements);
vector<bool> even(elements);
for(size_t i = 0; vi.size() != i; ++i) {
vi[i] = i % numeric_limits<int>::max();
}
random_shuffle(vi.begin(), vi.end());
for(int i = 0; 100*1000 != i; ++i) {
even_modulus(vi, even);
even_bitwise_and(vi, even);
}
}
<C++ kode/>
Venlig hilsen
Mogens Hansen
| |
Igor V. Rafienko (03-04-2004)
| Kommentar
Fra : Igor V. Rafienko |
Dato : 03-04-04 18:00 |
|
[ Mogens Hansen ]
[ ... ]
> Målingen viser at brugen af modulus er 2-5 % langsommere end brugen
> af bitwise and (afhængig af størrelsen på arrayet som afgør om det
> kan ligge i cache eller ej).
Hvordan ser den genererte koden ut?
ivr
--
<html><form><input type crash></form></html>
| |
Mogens Hansen (03-04-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 03-04-04 19:16 |
|
"Igor V. Rafienko" <igorr@ifi.uio.no> wrote:
> [ Mogens Hansen ]
>
> [ ... ]
>
> > Målingen viser at brugen af modulus er 2-5 % langsommere end brugen
> > af bitwise and (afhængig af størrelsen på arrayet som afgør om det
> > kan ligge i cache eller ej).´
Jeg burde måske præcisere at det er funktionen "even_modulus" der samlet set
er 2-5% langsommere end funktionen "even_bitwise_and".
Vi kan også lige tage et par tal mere:
Borland C++Builder V6.0: 0.2-1.4%
Intel C++ V7.1: -5 - -7 % (altså modulus er hurtigst)
Hvad kan man så sige om Borland compilerens evne til at optimere modulus
udtrykket i forhold til Microsoft compileren ? *)
> Hvordan ser den genererte koden ut?
Jeg har ikke kigget detaljeret på den, men antaget at forskellen svarer til
hvad Niels Dybdahl tidligere har vist - og jeg selv har set.
<assembler dump fra del af even_modulus>
; 10 : even[i] = (vi[i] % 2 == 0);
mov ecx, DWORD PTR [ebx+8]
xor eax, eax
mov eax, esi
mov edx, eax
shr edx, 5
and eax, 31 ; 0000001fH
lea edx, DWORD PTR [ecx+edx*4]
mov ecx, eax
mov eax, DWORD PTR [edi+esi*4]
and eax, -2147483647 ; 80000001H
jns SHORT $L12271
dec eax
or eax, -2 ; fffffffeH
inc eax
$L12271:
mov eax, 1
jne SHORT $L12258
shl eax, cl
or DWORD PTR [edx], eax
</assembler dump fra del af even_modulus>
og
<assembler dump fra del af even_bitwise_and>
; 17 : even[i] = ((vi[i] & 1)== 0);
mov ecx, DWORD PTR [ebp+8]
xor eax, eax
mov eax, esi
mov edx, eax
and eax, 31 ; 0000001fH
shr edx, 5
lea edx, DWORD PTR [ecx+edx*4]
mov ecx, eax
mov al, BYTE PTR [edi+esi*4]
not al
test al, 1
mov eax, 1
je SHORT $L12452
shl eax, cl
or DWORD PTR [edx], eax
</assembler dump fra del af even_bitwise_and>
så det er nogenlunde som forventet ud fra Niels Dybdahl inlæg.
Venlig hilsen
Mogens Hansen
*)
Absolut ingenting på baggrund af de data!
Det er væsentlig når man måler på performance: man ved hvad man har målt og
ikke mere!
Man kunne umiddelbart fristes til at tro at Borland compileren optimerer
selve modulus udtrykket bedre end Microsoft compileren - men det er ikke
tilfældet.
De gør rund regnet det samme.
Den øvrige kode er blot dårligere, så selve modulus beregningen spiller en
mindre rolle!
| |
Michael Lund (03-04-2004)
| Kommentar
Fra : Michael Lund |
Dato : 03-04-04 21:23 |
|
> > Målingen viser at brugen af modulus er 2-5 % langsommere end brugen
> > af bitwise and (afhængig af størrelsen på arrayet som afgør om det
> > kan ligge i cache eller ej).
>
>
> Hvordan ser den genererte koden ut?
>
Og hvordan ændrer den sig hvis man bruger "unsigned int" i stedet for "int"
i modulo tilfældet.
Når man and'er så ved man jo noget om tallet. Kompileren er formentlig nødt
til at tage højde for både positive og negative tal i en modulo beregning.
mvh
Michael
| |
Mogens Hansen (04-04-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 04-04-04 10:00 |
|
"Michael Lund" <milund@kodehaj.dk> wrote:
[8<8<8<]
> Og hvordan ændrer den sig hvis man bruger "unsigned int" i stedet for
"int"
> i modulo tilfældet.
Det væsentlige er at for "int" er der ikke nogen garanti for at bitwise and
virker, og derfor er performance ligegyldig - sådan som Igor V. Rafienko
påpegede for et godt stykke tid siden.
Desuden er det væsentligt at der foreligger målinger for et program med
"int" hvor bitwise and formodentlig virker (kun positive tal, platform med
2'er komplement) oversat med 3 forskellige compilere, hvor een (Microsoft)
er _lidt_ langsommere med modulus, een (Borland) hvor man næsten ikke kan
måle forskel og een (Intel) hvor modulus er _lidt_ hurtigere.
På den baggrund er det åbenlyst at der ikke er nogen som helst baggrund for
at lave generelle antagelser om hvorvidt den ene metode er hurtigere end den
anden.
Desuden understreger målingerne at det er langt væsentligere at koden er
tydelig i forhold til hvad den skal gøre, at den virker korrekt og at
"optimeringer" (af denne størrelsesorden) sker på baggrund af målinger,viden
og faktiske problemer.
Det undrer mig til stadighed hvorfor det er så svært at forstå, og hvorfor
man ikke læser Igor V. Rafienko's råd og tænker sig om inden der bliver
argumenteret videre.
For "unsigned int", hvor bitwise and virker til bestemmelse af hvorvidt
tallet er lige, fås følgende målinger:
Microsoft Visual C++ .NET 2003:
even_bitwise_and: 102-105 %
even_modulus: 100 %
altså modulus er _lidt_ hurtigere end bitwise and.
Borland C++Builder V6:
even_bitwise_and: 101%
even_modulus: 100 %
altså modulus er _meget_ lidt hurtigere end bitwise and.
Intel C++ V7.1:
Compileren generer _eksakt_ samme kode for de 2 funktioner, og det får
(Microsoft) linkeren til at slå dem sammen (Remove Redundant COMDAT),
således at kun een funktion findes i exe-filen. Den bruges så ved kald til
begge funktioner.
Stik den !!!
> Når man and'er så ved man jo noget om tallet.
Principielt ved man (programmøren) ikke noget om platformen som compileren
ikke også har mulighed for at vide, og dermed kan compileren foretage
veloplyste optimeringer hvis den vil.
Venlig hilsen
Mogens Hansen
| |
Michael Lund (04-04-2004)
| Kommentar
Fra : Michael Lund |
Dato : 04-04-04 10:28 |
|
Hejsa,
> Desuden er det væsentligt at der foreligger målinger for et program med
> "int" hvor bitwise and formodentlig virker (kun positive tal, platform med
> 2'er komplement) oversat med 3 forskellige compilere, hvor een (Microsoft)
> er _lidt_ langsommere med modulus, een (Borland) hvor man næsten ikke kan
> måle forskel og een (Intel) hvor modulus er _lidt_ hurtigere.
> På den baggrund er det åbenlyst at der ikke er nogen som helst baggrund
for
> at lave generelle antagelser om hvorvidt den ene metode er hurtigere end
den
> anden.
Fuldstændig enig - det giver ikke meget mening at prøve at optimere på
compilerens vegne. Da skal man (som tidligere nævnt af en anden) optimere på
algortime niveau.
Jeg må undskylde mig med at jeg ikke har læst hvert eneste indlæg i denne
tråd.
> Desuden understreger målingerne at det er langt væsentligere at koden er
> tydelig i forhold til hvad den skal gøre, at den virker korrekt og at
> "optimeringer" (af denne størrelsesorden) sker på baggrund af
målinger,viden
> og faktiske problemer.
> Det undrer mig til stadighed hvorfor det er så svært at forstå, og hvorfor
> man ikke læser Igor V. Rafienko's råd og tænker sig om inden der bliver
> argumenteret videre.
Jeg prøvede ikke at argumentere videre, jeg prøvede blot at forklare hvofor
compileren i _nogle_ tilfælde er lidt langsommere til modulo. Jeg mener at
man til hver en tid skal skrive koden, så den er pænest og lade compileren
om at optimere den slags "små-pjat".
mvh
Michael
| |
Mogens Hansen (04-04-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 04-04-04 11:26 |
|
"Michael Lund" <milund@kodehaj.dk> wrote:
[8<8<8<]
> Jeg må undskylde mig med at jeg ikke har læst hvert eneste indlæg i denne
> tråd.
Ups - det det var absolut ikke møntet på dig.
Jeg undskylder og kan godt forstå at det kunne opfattes sådan.
Det er generelle betragtninger som følge af bl.a. denne tråd.
[8<8<8<]
> Jeg prøvede ikke at argumentere videre, jeg prøvede blot at forklare
hvofor
> compileren i _nogle_ tilfælde er lidt langsommere til modulo.
Jeg undskylder igen at det kunne opfattes som møntet på dig - det var ikke
meningen.
Venlig hilsen
Mognes Hansen
| |
Michael Lund (04-04-2004)
| Kommentar
Fra : Michael Lund |
Dato : 04-04-04 12:43 |
|
> > Jeg må undskylde mig med at jeg ikke har læst hvert eneste indlæg i
denne
> > tråd.
> Ups - det det var absolut ikke møntet på dig.
> Jeg undskylder og kan godt forstå at det kunne opfattes sådan.
Det er helt i orden
mvh
Michael
| |
Byrial Jensen (26-03-2004)
| Kommentar
Fra : Byrial Jensen |
Dato : 26-03-04 20:50 |
|
Mogens Hansen wrote:
> J. Nielsen wrote:
>
>>> Jeg vil umiddelbart tro at denne "muligheten" har absolutt ingen
>>> garantier for å virke. Alt gnålet om "hurtigst" er således svært lite
>>> relevant.
>>
>> Det forstår jeg sku ikke ... hvorfor skulle det ikke virke?
>
> Hvorfor skulle det virke ?
Jeg er enig i at det normalt ikke er smart at bruge bitvise operatorer
for finde ud af om at tal er lige eller ulige. Men for retfærdighedens
skyld må jeg hellere tilføje at udtrykket (tal & 1) _vil_ virke hvis tal
er en unsigned type, eller en signed type med en positiv værdi. Kravene
til repræsentation af heltal står i afsnit 6.2.6.2 i C99-standarden.
| |
Niels Dybdahl (26-03-2004)
| Kommentar
Fra : Niels Dybdahl |
Dato : 26-03-04 23:51 |
|
> Jeg er enig i at det normalt ikke er smart at bruge bitvise operatorer
> for finde ud af om at tal er lige eller ulige. Men for retfærdighedens
> skyld må jeg hellere tilføje at udtrykket (tal & 1) _vil_ virke hvis tal
> er en unsigned type, eller en signed type med en positiv værdi. Kravene
> til repræsentation af heltal står i afsnit 6.2.6.2 i C99-standarden.
Nu er denne diskussionsgruppe vel ikke bundet til C99 standarden, så gælder
det også alle tidligere standarder ?
Niels Dybdahl
| |
Byrial Jensen (02-04-2004)
| Kommentar
Fra : Byrial Jensen |
Dato : 02-04-04 20:07 |
|
Niels Dybdahl wrote:
>>Jeg er enig i at det normalt ikke er smart at bruge bitvise operatorer
>>for finde ud af om at tal er lige eller ulige. Men for retfærdighedens
>>skyld må jeg hellere tilføje at udtrykket (tal & 1) _vil_ virke hvis tal
>>er en unsigned type, eller en signed type med en positiv værdi. Kravene
>>til repræsentation af heltal står i afsnit 6.2.6.2 i C99-standarden.
>
> Nu er denne diskussionsgruppe vel ikke bundet til C99 standarden, så gælder
> det også alle tidligere standarder ?
Jeg vil tro at det gælder for unsigned typer i tidligere standarder. Jeg
er ikke sikker for positive værdier af signed typer. C99 stiller på
nogle punkter større krav til en implementation end tidligere standarder.
| |
Igor V. Rafienko (26-03-2004)
| Kommentar
Fra : Igor V. Rafienko |
Dato : 26-03-04 01:37 |
|
[ J. Nielsen ]
[ ... ]
> Det forstår jeg sku ikke ... hvorfor skulle det ikke virke?
Mogens gav (som vanlig) et utmerket svar på denne.
[ ... ]
> Det er vel en fordel selv at fortage optimeringerne?
Absolutt. Bortsett fra at fokuset på optimeringene skal være et helt
annet sted. Det gir mening å optimere på algoritmenivå (en O(n)
algoritme framfor O(n^n)), datastrukturnivå (en datastruktur som har
bedre aksesstider på et utvalg operasjoner og/eller bruker mindre
hukommelse. Igjen Big-Oh notasjon) eller lesbarhetsnivå (da koden
skrives primært for mennesker). Det å erstatte en matematisk
definisjon i koden med en bitoperasjon tjener _ingen_ av hensiktene
over. Tvert imot, det forringer lesbarheten og er således totalt
unyttig.
Når det gjelder optimeringen i akkurat dette tilfellet, så er strength
reduction på et så enkelt nivå noe enhver produksjonsklar kompilator
skal kunne gjøre. Og selv om en kompilator ikke skulle greie det,
_hvorfor_ skulle man bry seg om noen få klokkesykler (modulo tar
typisk lengre tid enn bitwise and) fra eller til før man har noen data
som utpeker den aktuelle testen som flaskehalsen? "Premature
optimization is the root of all evil" sa en vis mann en gang. Et meget
treffende ordtak for akkurat slike tilfeller.
> Jeg mener, skulle man nu få behov for at debugge sit kode på
> baggrund af en disassembling, så er man jo i problemer, hvis
> kompileren har optimeret koden?!
Eh? Dersom man må se på disassembly for å finne fram til feil, så vil
feilen i 9 av 10 tilfeller ligge mellom stolen og skjermen. Det finnes
langt bedre verktøy for å hjelpe en med debugging.
ivr
--
<html><form><input type crash></form></html>
| |
Troels Thomsen (26-03-2004)
| Kommentar
Fra : Troels Thomsen |
Dato : 26-03-04 11:03 |
|
>
> Det er vel en fordel selv at fortage optimeringerne?
>
Jeg prøvede lige at indsætte en modulus i et embedded projekt, og fik som
frygtet inkluderet modulus biblioteket. Lige denne compiler kunne altså ikke
finde ud af at erstatte modulus med en bitvis instruktion.
59 if (ee_setInlet%2 == 0)
\ 004A 6B86000A MOV.W R6,@ee_setInlet
\ 004E 79050002 MOV.W #2,R5
\ 0052 5F00 JSR @@Tab_?SS_MOD_L02
Hvis man virkelig ikke VIL have modulus'en , så lav en BOOL isEven(char a)
funktion, og vælg så den bitvise implementering, og skriv en passende
advarsel i dokumentationen til moduet! Eller placer funktionen i et modul
sammen med alle de andre platform specifikke metoder man som regel har i et
projekt.
Så har man lidt styr på sit generelle kode, og på det platform specifikke.
Hvis man synes det er fjollet at kalde en funktion hver gang, så få
compileren til at inline den, eller lav en makro.
mvh tpt
| |
Jesper Louis Anderse~ (26-03-2004)
| Kommentar
Fra : Jesper Louis Anderse~ |
Dato : 26-03-04 17:11 |
|
Troels Thomsen <troels.thomsen@mailteledk> wrote:
>>
>> Det er vel en fordel selv at fortage optimeringerne?
>
> Jeg pr?vede lige at inds?tte en modulus i et embedded projekt, og fik som
> frygtet inkluderet modulus biblioteket. Lige denne compiler kunne alts? ikke
> finde ud af at erstatte modulus med en bitvis instruktion.
Jeg synes godt nok at diskussionen efterhaanden er langt ude. En modulo
operation er selvfoelgeligt rimeligt dyr, specielt fordi den nok er
lavet i software paa moderne CPU'er. En bitwise operation er selvfoelgeligt
billigere fordi hardwaren som regel er indbygget i CPU'en og fordi et
bitwise and-array er hulens nemt at lave.
Diskussionen handler om hvad der er hurtigst. Fint nok, er det vist at
stedet i koden er flaskehalsen? Hvis nej, saa benyt modulo. Hvis ja og din
repraesentation af tal muliggoer anvendelsen af en bit-operation, saa benyt
dig af den. Muligvis med passende kommentar. Jeg er 99% sikker paa at
programmet ikke vinder hastigheden bare ved at kigge paa noget skaldet
smaatteri saasom en disassembly af noget i386 kode.
Der er en grund til at de fleste compilere udelader optimeringen. Den
betyder nok ikke saa meget at det kan betale sig at goere noget ved den
for alvor. Herrebevares, man kan godt genkende den - men det koster i
oversaettelseshastighed og jeg tvivler paa at stoerstedelen af diverse
programmer overhovedet vil benytte sig af det som sagt.
--
j.
| |
Troels Thomsen (29-03-2004)
| Kommentar
Fra : Troels Thomsen |
Dato : 29-03-04 13:32 |
|
>
> Jeg synes godt nok at diskussionen efterhaanden er langt ude.
Jeg holder meget af disse diskussioner der kører ud af en tangent fordi:
* Folk har en holdning og kæmper for den.
* Der afsløres detaljer vedr kode-forståelse og -stil, som jeg har lært
meget af i tidens løb.
Derudover var vi vist enige, eller ?
tpt
| |
Ivar (26-03-2004)
| Kommentar
Fra : Ivar |
Dato : 26-03-04 23:40 |
|
Igor V. Rafienko skrev:
> Så, hvis noen kunne forklare meg appellen i det bitvise svineriet, vil
> jeg være meget takknemlig.
C er ikke ret meget mere end en struktureret assembler. C er
_sproget_ til små microprocessorer. Til kraftige processorer, PC'er
osv kan man med fordel bruge mere avancerede sprog, som C++,
java og andre "glimmer-sprog".
Hvorfor tror du Chris har valgt C?
Jeg ved det ikke, men det kunne tænkes at han eller andre
har fundet det bedst for den processor, hvortil han skriver kode.
At bruge % til at tjekke om et tal er lige på en 8051 eller PIC
vil jeg kalde amatøragtig. Der kan man tale om svineri - svineri
med regnekraft.
%2 reddes selvfølgelig af mange compiler, men det er tåbeligt
at programmøren beder om division, som er det absolut dyreste
for de fleste microprocessor, når AND er blandt de billigste.
Ivar Magnusson
--
PC-programmører er som eunukker, de ved noget om
hvad der foregår, men når de selv skal, kan de ikke.
| |
Igor V. Rafienko (27-03-2004)
| Kommentar
Fra : Igor V. Rafienko |
Dato : 27-03-04 01:18 |
|
[ did@[nozpam]oncable.dk ]
[ ... ]
> Hvorfor tror du Chris har valgt C?
Jeg ser ikke relevansen til dette spørsmålet.
> Jeg ved det ikke, men det kunne tænkes at han eller andre har fundet
> det bedst for den processor, hvortil han skriver kode.
:)
> At bruge % til at tjekke om et tal er lige på en 8051 eller PIC vil
> jeg kalde amatøragtig. Der kan man tale om svineri - svineri med
> regnekraft.
Hvilken del av:
(...) _hvorfor_ skulle man bry seg om noen få klokkesykler (modulo tar
typisk lengre tid enn bitwise and) fra eller til før man har noen data
som utpeker den aktuelle testen som flaskehalsen?
.... var uklar? Regnekraft koster ingenting i det skala som det er
snakk om her. Det å følge slavisk den matematiske definisjonen av
"ulike" tall er det mest forklarende for _mennesker_ (og ikke bryr seg
om den eksakte bitrepresentasjonen av signed integers).
> %2 reddes selvfølgelig af mange compiler, men det er tåbeligt at
> programmøren beder om division, som er det absolut dyreste for de
> fleste microprocessor, når AND er blandt de billigste.
Neida. Heltallsdivisjon er langt i fra det dyreste (iallfall for en
viss definisjon av "microprosessor"), om enn dyrere enn bitwise and.
To, dagens stikkord er "strength reduction". Tre, og _igjen_ (dette må
være en av de dagene når jeg virkelig ikke når fram) -- det har
absolutt *ingen* relevans om man bruker 1, 10, 100 eller 1000
klokkesykler på den aktuelle testen, inntil det foreligger
kvantitative data som tilsier at nettopp den testen senker programmet
med såpass mye at det er aktuelt å se på akkurat den testen.
Det er tåpelig av programmereren å ikke adlyde matematikken. IMVHO.
ivr
--
<html><form><input type crash></form></html>
| |
Ivar (28-03-2004)
| Kommentar
Fra : Ivar |
Dato : 28-03-04 14:07 |
|
Igor V. Rafienko skrev:
> ... var uklar? Regnekraft koster ingenting i det skala som det er
> snakk om her. Det å følge slavisk den matematiske definisjonen av
> "ulike" tall er det mest forklarende for _mennesker_ (og ikke bryr seg
> om den eksakte bitrepresentasjonen av signed integers).
Prøv at kig omkrig dig, der masser af processorer i elektronik i din
hverdag, langt de fleste 8-bits. Der er masser af tilfælde hvor det er
billigere at give 10.000 kr ekstra om måneden for en god programmør,
fremfor at ofre 1 kr ekstra på regnekraft.
At du ikke bryder dig om binære tal, gør det ikke til dårlig kode.
> Neida. Heltallsdivisjon er langt i fra det dyreste (iallfall for en
> viss definisjon av "microprosessor"), om enn dyrere enn bitwise and.
Af de basale heltals-funktioner er division den mest komplekse.
Mange processorer har komplekse specielle funktioner, som fx
tabelopslag med interpolation, beregning af polynomium og hvad ved jeg,
men det har jo intet med sagen at gøre. Jeg farede i blækhuset
fordi du kaldte en stump god kode for dårlig - åbenbart fordi
du har det dårligt med binære tal.
> To, dagens stikkord er "strength reduction". Tre, og _igjen_ (dette må
> være en av de dagene når jeg virkelig ikke når fram) -- det har
> absolutt *ingen* relevans om man bruker 1, 10, 100 eller 1000
> klokkesykler på den aktuelle testen, inntil det foreligger
> kvantitative data som tilsier at nettopp den testen senker programmet
> med såpass mye at det er aktuelt å se på akkurat den testen.
Uha, eksekverings hastighed og udviklingstid er altid et tema for et
software-projet. Hvad der vejer mest er selvfølgeligt forskelligt
fra projekt til projekt. Men hvis der ikke er forskel på udviklingstiden
bør man vælge den bedste kode.
> Det er tåpelig av programmereren å ikke adlyde matematikken. IMVHO.
Det er svært at undgå.
% giver det mindst betydende ciffer i et valgt decimal system,
%2 giver det mindst betydende ciffer i det binære talsystem.
& giver de valgte cifre i det binære talsystem.
&1 giver det mindst betydende ciffer i det binære talsystem.
Ivar Magnusson
| |
Igor V. Rafienko (28-03-2004)
| Kommentar
Fra : Igor V. Rafienko |
Dato : 28-03-04 15:09 |
|
[ did@[nozpam]oncable.dk ]
[ ... ]
> Prøv at kig omkrig dig, der masser af processorer i elektronik i din
> hverdag, langt de fleste 8-bits. Der er masser af tilfælde hvor det
> er billigere at give 10.000 kr ekstra om måneden for en god
> programmør, fremfor at ofre 1 kr ekstra på regnekraft.
*Sukk*.
> At du ikke bryder dig om binære tal, gør det ikke til dårlig kode.
Hva har _binærtall_ med saken å gjøre?
> > Neida. Heltallsdivisjon er langt i fra det dyreste (iallfall for
> > en viss definisjon av "microprosessor"), om enn dyrere enn bitwise
> > and.
>
> Af de basale heltals-funktioner er division den mest komplekse.
Oi, nå er du plutselig gått fra:
[ sitat ]
.... men det er tåbeligt at programmøren beder om division, som er det
absolut dyreste for de fleste microprocessor,
[ /sitat ]
til "basale heltallsfunksjoner". Så _beleilig_.
Vi tar det en gang til:
* Divisjon er ikke den absolutt dyreste operasjonen for et meget
utbredt utvalg av microprosessorer. Heltalls eller ej.
* Heltallsdivisjon koster en del mer enn en del andre
heltallsoperasjoner på et godt utvalg av microprosessorer (det
skulle også forundre meg om det fantes en microprosessor der
heltallsdivisjon var billigere enn bitwise and)
Dog, dette er en digresjon som har _ingenting_ med saken å gjøre.
"modulo" kan godt koste tusen ganger mer enn "bitwise and", og det vil
fremdeles være like irrelevant.
[ ... ]
> Jeg farede i blækhuset fordi du kaldte en stump god kode for dårlig
> - åbenbart fordi du har det dårligt med binære tal.
"åpenbart"? Heh...
Som sagt -- *sukk*. Kritikken min er ikke rettet mot bruken av
bitrepresentasjonen av heltall. Hadde oppgaven gått ut på analysere de
minst signifikante bit i et tall, ville "modulo" operasjonen vært et
tåpelig valg. Og årsaken til dette ligger ikke i den relative
kostnaden av operasjonen på en CPU.
[ ... ]
> Hvad der vejer mest er selvfølgeligt forskelligt fra projekt til
> projekt. Men hvis der ikke er forskel på udviklingstiden bør man
> vælge den bedste kode.
Nå er jeg spent: hva skulle være "beste kode"?
[ ... ]
> % giver det mindst betydende ciffer i et valgt decimal system,
> %2 giver det mindst betydende ciffer i det binære talsystem.
Nei!
The result of the / operator is the quotient from the division of the
first operand by the second; the result of the % operator is the
remainder.
% gir deg resten etter divisjon, hvilket er det begrepet man opererer
med i definisjonen av ulike tall (_det_ er den opprinnelige oppgaven).
Det at _resten_ etter divisjon samsvarer med et bestemt siffer i
representasjonen for et gitt grunntall er en bieffekt (som man _kan_
utnytte i bestemte situasjoner), men ikke noe mer.
> & giver de valgte cifre i det binære talsystem.
> &1 giver det mindst betydende ciffer i det binære talsystem.
(Jeg lurer på hva "negative-zero bitwise-and 1" gir).
Men du husker selvsagt at den opprinnelige oppgaven gikk på å finne ut
hvorvidt et tall var like eller ulike, *ikke* på hvordan den binære
representasjonen til dette tallet så ut. Ser du hvor jeg vil nå?
Hele diskusjonen minner veldig om en vits jeg så en gang om hvordan
man skulle skrive en paper til IEEE. Uttrykket "1 == 1" ble omgjort på
et ganske fasinerende vis for å få et litt mer vitenskaplig preg over
seg.
ivr
--
<html><form><input type crash></form></html>
| |
Mogens Hansen (28-03-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 28-03-04 15:23 |
|
"Ivar" <did@[nozpam]oncable.dk> wrote:
[8<8<8<]
> Men hvis der ikke er forskel på udviklingstiden
> bør man vælge den bedste kode.
Alt andet lige må kode der garanteret virker være bedre end kode der ikke
garanteret virker.
[8<8<8<]
> &1 giver det mindst betydende ciffer i det binære talsystem.
Mindst betydende ciffer i det binære talsystem siger, som påvist, blot ikke
i sig selv noget om hvorvidt tallet er lige eller ulige.
Venlig hilsen
Mogens Hansen
| |
Jesper Louis Anderse~ (27-03-2004)
| Kommentar
Fra : Jesper Louis Anderse~ |
Dato : 27-03-04 04:16 |
|
Ivar <did@[nozpam]oncable.dk> wrote:
> C er ikke ret meget mere end en struktureret assembler.
Det er ikke en god analogi. Det kommer an paa hvor meget du placerer
i struktureret assembler, men for mig at se har C og assembler ret lidt
med hinanden at goere som sprog. C har simpelthen for mange
konstruktioner der ikke har 1-1 aekvivalens med en tilsvarende ISA. Her
er det faktum at C kan oversaettes til flere arkitekturer ret relevant,
da assembler typisk er bundet til en bestemt type mikroprocessor.
> At bruge % til at tjekke om et tal er lige p? en 8051 eller PIC
> vil jeg kalde amat?ragtig. Der kan man tale om svineri - svineri
> med regnekraft.
So what? Hvis kravene er at man skal spare cykler, saa har man en god
grund til at skulle spare cykler. Der skal mere til end "Det skal bare
vaere optimalt". Det kunne vaere at said operation ligger i et tight
loop. Det kunne vaere at er skulle spares stroem paa chippen, saa det
er vigtigt at den afslutter sine beregninger hurtigt. Men - uden nogen
viden om disse krav, saa er mikrooptimeringer af den type naeppe
relevante.
Hvis man har gang i en 8051 eller PIC, saa er det som regel fordi man
har gang i elektronik og har en hel anden boldgade end en moderne CPU.
Jeg vil paastaa at det ikke er hastighed der er vigtigt her, for hvis
det var ville man nok bare banke en stoerre chip paa og vaere ude over
problemet.
> %2 reddes selvf?lgelig af mange compiler, men det er t?beligt
> at programm?ren beder om division, som er det absolut dyreste
> for de fleste microprocessor, n?r AND er blandt de billigste.
Det vigtigste er ikke om programmoeren skriver koden paa maade A eller
B. Det vigtige er at han/hun om 3 maaneder stadig er i stand til at
vide hvad der foregaar. Man kan lave masser af ting hurtigt hvis man
kigger lidt paa hvad man kan goere med bitvis AND, OR, XOR, NOT og
venner. Men det hjaelper ikke hvis det resulterer i en fejl i programmet
eller en anden programmoer ikke kan forstaa hvad der foregaar. Det er
set med mine oejne meget vigtigere at holde koden ren end det er at
presse hastighed ud af den.
1. Korrekthed
2. Laesbarhed
3. Hastighed
Burde vaere skrevet ind som et mantra hos alle programmoerer, men naar
man kigger sig omkring, saa er det ikke tilfaeldet.
Og hvis man skal mikrooptimere paa en PC, saa gider man ikke laengere
kigge paa enkelte instruktioner foer til sidst. Det kan bedst betale
sig at goere noget ved algoritmen foerst, saa kigge paa cache og foerst
derefter kaster man sig over hvad din ISA siger.
--
j.
| |
Ivar (28-03-2004)
| Kommentar
Fra : Ivar |
Dato : 28-03-04 14:07 |
|
Jesper Louis Andersen skrev:
> > C er ikke ret meget mere end en struktureret assembler.
>
> Det er ikke en god analogi. Det kommer an paa hvor meget du placerer
> i struktureret assembler, men for mig at se har C og assembler ret lidt
> med hinanden at goere som sprog.
Der er selvfølgelig stor forskel, men C er det mest simple af de gængse
sprog.
> So what? Hvis kravene er at man skal spare cykler, saa har man en god
> grund til at skulle spare cykler. Der skal mere til end "Det skal bare
> vaere optimalt". Det kunne vaere at said operation ligger i et tight
> loop. Det kunne vaere at er skulle spares stroem paa chippen, saa det
> er vigtigt at den afslutter sine beregninger hurtigt. Men - uden nogen
> viden om disse krav, saa er mikrooptimeringer af den type naeppe
> relevante.
Lige gyldigt hvilket af ovenstående optimerings ønsker du vælger
vil & være at fortrække. Hvis man ønsker at programmet skal være
let læseligt for en java- eller visual basic-programmør, vil det være
udemærket at bruge %, men det er også den eneste optimerings
grund jeg kan se.
> Hvis man har gang i en 8051 eller PIC, saa er det som regel fordi man
> har gang i elektronik og har en hel anden boldgade end en moderne CPU.
> Jeg vil paastaa at det ikke er hastighed der er vigtigt her, for hvis
> det var ville man nok bare banke en stoerre chip paa og vaere ude over
> problemet.
Uha, økonomi er ikke programmørers stærke side.
> Og hvis man skal mikrooptimere paa en PC, saa gider man ikke laengere
> kigge paa enkelte instruktioner foer til sidst.
Nej, det bør være pr. refleks, hvis man arbejder med tidskritiske applikationer.
Jeg bryder mig ikke om at Igor kalder effektiv kode for svineri.
Ivar Magnusson
| |
Jesper Louis Anderse~ (28-03-2004)
| Kommentar
Fra : Jesper Louis Anderse~ |
Dato : 28-03-04 14:56 |
|
Ivar <did@[nozpam]oncable.dk> wrote:
> Der er selvf?lgelig stor forskel, men C er det mest simple af de g?ngse
> sprog.
Du garderer med "gaengse sprog". FORTRAN er simplere, Pascal er simplere.
C er et hamrende komplekst sprog med mange spidsfindigheder du ikke vil
se i moderne sprog. Desuden egner det sig ikke laengere saa godt til
lavniveauprogrammering paa moderne CPU'er fordi det er kommet for langt
vaek fra hardwaren. Ethvert sprog der tillader pointeraritmetik er svaert
at optimere paa, saa det gaar hurtigt (aliasing).
Der er stadig stor forskel paa assembler og deciderede sprog der skal
oversaettes. Bare det at sproget allokerer registre er et eksempel paa
hvor stor forskel der egentlig er.
> Lige gyldigt hvilket af ovenst?ende optimerings ?nsker du v?lger
> vil & v?re at fortr?kke. Hvis man ?nsker at programmet skal v?re
> let l?seligt for en java- eller visual basic-programm?r, vil det v?re
> udem?rket at bruge %, men det er ogs? den eneste optimerings
> grund jeg kan se.
Eller at du muligvis senere skal checke tallet modulo noget andet. Hvis
det er tilfaeldet, saa kommer du ikke langt med bitfedteri. Der er masser
af steder hvor det er smart at benytte de bitvise operatorer. Men jeg
synes det er overkill i lige netop det her tilfaelde. Det lader til at
vi er unenige omkring det.
> Uha, ?konomi er ikke programm?rers st?rke side.
Det kommer lidt an paa det. Stoerre chip betyder stoerre omkostning for
den enkelte dims man producerer. Det kan meget vel vise sig at man kan
spare de meromkostninger ved at optimere lidt hist og her. Det kan naeppe
betale sig at optimere mere end hoejst noedvendigt. Saa hvis det viser sig
at det er et problem, saa gider man da ikke betale en programmoer 10k hvis
5k kan goere det. Eller endnu bedre: Lade vaere med bekymre sig om det og
lade oversaetteren goere det bedre end programmoeren kan. For en merpris
af 0.
Paa den anden side opfatter jeg heller ikke mig selv som programmoer, saa
det kan vaere derfor.
>> Og hvis man skal mikrooptimere paa en PC, saa gider man ikke laengere
>> kigge paa enkelte instruktioner foer til sidst.
>
> Nej, det b?r v?re pr. refleks, hvis man arbejder med tidskritiske applikationer.
Der skal mere til end bare at vaelge effektive metoder lokalt i enkelte
funktioner hvis det er tidskritisk.
> Jeg bryder mig ikke om at Igor kalder effektiv kode for svineri.
Det goer han heller ikke. Han kalder kode uden omtanke for svineri. Det
han har ret i er at man skal foelge mantraet at "Premature optimization
is the root of all evil". Det kan ikke betale sig at optimere foer man
ved hvad det er man optimerer hen imod og hvordan ens maalinger viser at
det rent faktisk er det der er problemet. Det er dette praemis han
diskuterer paa. Selv om diskussionen efterhaanden er drejet et eller andet
ligegyldigt sted hen. Og hvorfor er det saa vigtigt? Fordi det typisk
er saadan at optimeret kode er svaerere at laese end ikke-optimeret kode.
Og korrekthed nu engang er det vi er interesseret i.
Desvaerre er det saadan at det kan vaere ligegyldigt om man koder en
enkelt operation paa maade A eller B, for det har ikke en doejt at goere
med om ens kode er effektiv i sidste ende. Du kan smide den bitvise AND
i en funktion for sig selv og erklaere den noinline, hvorefter at en
inlinet modulusoperation er hurtigere. Det skulle gerne illustrere min
pointe.
--
j.
| |
Mogens Hansen (27-03-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 27-03-04 10:36 |
|
Ivar wrote:
[8<8<8<]
> At bruge % til at tjekke om et tal er lige på en 8051 eller PIC
> vil jeg kalde amatøragtig.
Sådan har man forskellige målestokke.
Jeg opfatter unødvendige hack, manglende forståelse for problem og
løsnings domæne og uklar kode som amatøragtig.
8051 har direkte understøttelse for modulo - se instruktionen DIV og
bemærk hvad der ligger i register B. Den tager 4 mikrosekunder mod 1
mikrosekund på en klassisk 12 MHz 8051.
> Der kan man tale om svineri - svineri
> med regnekraft.
Al elektronik og software udvikling er svineri efter en eller anden
målestok.
Det er svineri med targets regnekraft at anvende C i stedet for
assembler til at skrive 8051 programmer.
Man vil formodentlig altid kunne finde et par clock-cycler der går til
spilde på den konto - og det er oftest fuldstændigt ligegyldigt.
Alt hvad man kan lave med en 8051 kan laves mere effektivt (hastighed,
strøm forbrug) med en ASIC, hvis man putter tilstrækkelig tid og penge i
det.
Venlig hilsen
Mogens Hansen
| |
Ivar (28-03-2004)
| Kommentar
Fra : Ivar |
Dato : 28-03-04 14:07 |
|
Mogens Hansen skrev:
> Sådan har man forskellige målestokke.
Selvfølgelig.
> Jeg opfatter unødvendige hack, manglende forståelse for problem og
> løsnings domæne og uklar kode som amatøragtig.
Jeg tager det for givet, at en C-programmør er fortrolig med binære tal.
> 8051 har direkte understøttelse for modulo - se instruktionen DIV og
> bemærk hvad der ligger i register B. Den tager 4 mikrosekunder mod 1
> mikrosekund på en klassisk 12 MHz 8051.
Ja, netop DIV og MUL er de to eneste der tager 4us og der ingen der
tager under 1us.
> Det er svineri med targets regnekraft at anvende C i stedet for
> assembler til at skrive 8051 programmer.
> Man vil formodentlig altid kunne finde et par clock-cycler der går til
> spilde på den konto - og det er oftest fuldstændigt ligegyldigt.
Det er et kompromis mellem udviklings omkostninger og afviklingshastighed.
Hvis man vælger at skrive i C, er der ingen grund til at lave dårlig kode.
> Alt hvad man kan lave med en 8051 kan laves mere effektivt (hastighed,
> strøm forbrug) med en ASIC, hvis man putter tilstrækkelig tid og penge i
> det.
Der er himmelvid forskel i udviklingsomkostningerne til de to
løsningsmodeller.
Ivar Magnusson
| |
Mogens Hansen (28-03-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 28-03-04 15:23 |
|
"Ivar" <did@[nozpam]oncable.dk> wrote:
[8<8<8<]
> Jeg tager det for givet, at en C-programmør er fortrolig med binære tal.
Enig.
Problemet er blot at binære tal ikke er een ting.
Vi tilbage ved de spørgsmål jeg stillede tidligere i tråden:
Hvilke binære repræsentationer af af heltal er tilladt for en C
implementering ?
Specielt, hvilken indflydelse har den anvendte binære repræsentation på
mindst betydende bit egnethed til bestemmelse af hvorvidt tallet er lige
eller ulige ?
>
>
> > 8051 har direkte understøttelse for modulo - se instruktionen DIV og
> > bemærk hvad der ligger i register B. Den tager 4 mikrosekunder mod 1
> > mikrosekund på en klassisk 12 MHz 8051.
>
> Ja, netop DIV og MUL er de to eneste der tager 4us og der ingen der
> tager under 1us.
Du bør også forklare hvorfor du finder et potentielt tab af 3 us
problematisk uden kvatitativt at have påvist at det er et problem, når der
formodentlig kan findes mange tilsvarende performancetab ved at anvende C i
stedet for assembler.
>
>
> > Det er svineri med targets regnekraft at anvende C i stedet for
> > assembler til at skrive 8051 programmer.
> > Man vil formodentlig altid kunne finde et par clock-cycler der går til
> > spilde på den konto - og det er oftest fuldstændigt ligegyldigt.
>
> Det er et kompromis mellem udviklings omkostninger og afviklingshastighed.
Netop.
> Hvis man vælger at skrive i C, er der ingen grund til at lave dårlig kode.
Vi er enige om at man ikke skal lave dårlig kode.
Men vi er åbenbart ikke enige om hvad dårlig kode er.
Kan vi blive enig om at god kode bl.a. har følgende egenskaber
1. Udfører garanteret den ønskede funktion korrekt
2. Koden udtrykker klart programmørens hensigt
3. Programmet opfylder de nødvendige performance krav
Kode der mangler en eller flere af disse egenskaber må følgelig være
dårligere end kode der opfylder disse egenskaber.
Hvis vi så tager det oprindelige spørgsmål "hvordan finder jeg ud af (i C,
ikke C++) om et tal er lige eller ulige?'" og vurderer de 2 løsningsforslag
som bliver diskuteret ud fra ovenstående kriterier får man:
For bitwise and løsningen:
1. Nej. Det kræver viden om den konkrete implementering at kunne afgøre
2. Det er der åbenbart uenighed om. I forhold til en almindelig definition
af hvad der forståes ved lige tal, således om man f.eks. kan finde det i et
almindeligt leksikon, forekommer sammenhængen mellem problemet og løsningen
ikke åbenlys
3. Formodentlig - men sproget i sig selv garanterer ikke performance
karakteristikken
For modulo løsningen:
1. Ja
2. Det er der åbenbart uenighed om. Løsningen ligger tættere på en
almindelig definition af hvad lige tal er: hvis rest fra division med 2 er
nul så lige
3. Formodentlig - men sproget i sig selv garanterer ikke performance
karakteristikken
Ud fra den analyse er der ingen tvivl om at modulo løsning er "god" og
bitwise and løsningen er "dårlig".
Bemærk at der er intet der forhindrer en compiler i at lægge samme assembler
kode ud for
if(i % 2 == 0)
og
if((i & 1) == 0)
såfremt på det på en given platform har identisk betydning.
Det er i denne tråd hævdet/påvist at være tilfældet for gcc og Intel C++.
Tilsvarende er der ikke noget der garanterer at en compiler lægger
tilnærmelsesvis optimal kode ud for udtrykket
if((i & 1) == 0)
>
>
> > Alt hvad man kan lave med en 8051 kan laves mere effektivt (hastighed,
> > strøm forbrug) med en ASIC, hvis man putter tilstrækkelig tid og penge i
> > det.
>
> Der er himmelvid forskel i udviklingsomkostningerne til de to
> løsningsmodeller.
Jeps.
Så er vi enige om at løsninger (8051 i stedet for en ASIC, C i stedet for
assembler) der på visse områder ikke er optimale (eksekveringshastighed,
strømforbrug) kan være et fornuftigt og brugbart design.
Venlig hilsen
Mogens Hansen
| |
Ivar (02-04-2004)
| Kommentar
Fra : Ivar |
Dato : 02-04-04 23:27 |
|
Mogens Hansen skrev:
> Problemet er blot at binære tal ikke er een ting.
I teorien er det ikke, men i praksis er det.
Ivar Magnusson
| |
Mogens Hansen (03-04-2004)
| Kommentar
Fra : Mogens Hansen |
Dato : 03-04-04 06:43 |
|
"Ivar" <did@[nozpam]oncable.dk> wrote:
>
> Mogens Hansen skrev:
>
>
> > Problemet er blot at binære tal ikke er een ting.
>
> I teorien er det ikke, men i praksis er det.
Det kommer an på hvor man udøver sin praksis.
Det er ikke så længe siden at der her på gruppen var en der havde spørgsmål
i relation til nogle oplevelser med anvendelse af C++ på en mainframe.
Det er ikke længe siden at Unisys frigav en ny mainframe i en serie der
bruger 1'ers komplement.
Maskiner med 1'ers komplement findes i den virkelige verden, selvom det
givetvis er langt mindre anvendt end 2'ers komplement.
Pointen i relation til denne tråd er at viden og antalgelser om platformens
binære repræsentation er _fuldstændig_ overflødig for at bestemme om et tal
er lige - der findes som vist en løsning der både er mere klar i sit udtryk
og garanteret virker uden yderligere antagelser.
Venlig hilsen
Mogens Hansen
| |
Troels Thomsen (29-03-2004)
| Kommentar
Fra : Troels Thomsen |
Dato : 29-03-04 16:15 |
|
>
> Jeg tager det for givet, at en C-programmør er fortrolig med binære tal.
>
Du kan jo se på denne tråd at nogen faktisk _havde_ glemt at tallene kunne
være negative og evt signed magnitude.
Det understøtter Mogens' udemærkede tommelfinger regel: "1) skriv hvad du
mener, 2) optimér hvis du får brug for det".
(og ja, hvis du sidder og laver en interrupt rutine eller et tight loop, så
ved du det pga din erfaring måske med det samme)
tpt
| |
Lasse Westh-Nielsen (24-03-2004)
| Kommentar
Fra : Lasse Westh-Nielsen |
Dato : 24-03-04 20:40 |
|
"Chris" <chris_PRIVACY_@ngweb.biz> wrote:
> Hvordan finder jeg ud af (i C, ikke C++) om et tal er lige eller
> ulige?
Du kan spørge om tallet modulo 2 er lig med 0 eller 1 (eller ej):
int n = noget;
if (n % 2 == 0) printf("n er lige!"); else printf("n er ulige!");
Mvh Lasse
--
Lasse Westh-Nielsen
lasse@daimi.au.dk
| |
Chris (24-03-2004)
| Kommentar
Fra : Chris |
Dato : 24-03-04 21:05 |
|
On Wed, 24 Mar 2004 20:27:40 +0100, Chris <chris_PRIVACY_@ngweb.biz>
wrote:
Tak, alle sammen.
Venligst
Chris
| |
|
|