"11111111" --> 255 : wie am effektivsten?

[loki1985]

aha.

wie rechne ich dann 2 hoch 2?

2 * pow(2)?

/EDIT: hat sich erledigt, habs in der DJGPP C DOC gefunden. danke

[Bashar]

(1 << k) ist am effizientesten

[junix]

@Volkard:
Welchen signifikaten Vorteil hat deine Schreibweise gegenüber dieser hier?

char ergebnis=0; 
    while(*wertstring)
    {
       ergebnis |= (*wertstring++-'0');
       ergebnis <<= 1;
    }

Mal abgesehen von der Tatsache, dass die obige Schreibweise leserlicher ist?

ICh hab sie auch mal durch den Compiler geschickt um das Argument der optimaleren Compilierung der unleserichen Variante (halte ich eh für ein Gerücht) zu entkräften.

Es sei mir verziehen. Ich habe nur einen Atmel AVR Compiler von IAR zur Hand gehabt. Die beiden Varianten spucken mir folgenden Assembler aus.

// Deine Schreibweise (126 Cycles)
    ;char ergebnis=0; 
    R18,0x00
    while(*wertstring) 
    LD      R16,Z
    TST     R16
    BREQ    0x3A8E
    ;ergebnis=2*ergebnis+*wertstring++-'0';
    LDI     R16,0x02
    MUL     R18,R16
    LD      R18,Z
    ADD     R18,R0
    SUBI    R18,0x30
    ADIW    R30,1
    RJMP    0x3A7A
    ;PORTB = ergebnis;
    OUT     _A_PORTB,R18

// Meine Schreibweise: (118 Cycles)
    ; char ergebnis=0; 
    LDI     R19,0x00
    ; while(*(wertstring))
    LD      R16,X
    TST     R16
    BREQ    0x3AAC
    ;    ergebnis |= (*wertstring++-'0');
    MOVW    R30,R26
    LD      R16,Z
    SUBI    R16,0x30
    OR      R19,R16
    ADIW    R26,1
    ;   ergebnis <<= 1;
    LSL     R19
    RJMP    0x3A98

Wie man sieht, ist die leserlichere Variante sogar mit weniger CPU-Zyklen belastet als die obige Variante.
Ich habs mal nachgeschaut. Die 8 Zyklen mehr stammen aus der Multiplikation die der COmpiler hier offensichtlich nicht als Shift nach links erkannt hat.

-junix

[Vertexwahn]

mal ne dumme frage - wie "rechnest" du die CPU Cycles aus? entspricht ein Cyle einem Takt?

[junix]

Äh ja, 1 Cycle = 1 Takt. Jedes Assemblerkommando hat bestimmte Kosten an Cycles... daraus lässt sich die gesamtlaufzeit des Abschnitts errechnen, bzw. mit dem AVR Studio (in meinem Fall) kann ich das bequem ablesen wieviele cycles zwischen zwei Haltepunkten vergangen sind.

[volkard]

junix schrieb:

@Volkard:
Welchen signifikaten Vorteil hat deine Schreibweise gegenüber dieser hier?

char ergebnis=0; 
    while(*wertstring)
    {
       ergebnis |= (*wertstring++-'0');
       ergebnis <<= 1;
    }

Mal abgesehen von der Tatsache, dass die obige Schreibweise leserlicher ist?

sie war schneller eingetippt. der leser meiner postings muss eh den code kapieren und dann was eigenes schreiben. außerdem sind wir hier im C-forum. die haxors nehmen mich nicht ernst, wenn der code wie kindergartencode aussieht.

aber dein gefummle mit | und << finde ich nicht ok. ich verlasse mich gar nicht auf eine interne darstellung oder so, sondern mache nur mathe. da heißt es *2 und +.
also meinetwegen

int ergebnis=0;
for(char* pos=wertstring;*pos!='\0';++pos){
   ergebnis += *wertstring-'0';
   ergebnis *= 2;
}

ICh hab sie auch mal durch den Compiler geschickt um das Argument der optimaleren Compilierung der unleserichen Variante (halte ich eh für ein Gerücht) zu entkräften.

du bist auf dem richtigen weg.

Es sei mir verziehen. Ich habe nur einen Atmel AVR Compiler von IAR zur Hand gehabt. Die beiden Varianten spucken mir folgenden Assembler aus.

nein, nicht verziehen.

// Deine Schreibweise (126 Cycles)
    ;ergebnis=2*ergebnis+*wertstring++-'0';
    LDI     R16,0x02
    MUL     R18,R16

// Meine Schreibweise: (118 Cycles)
    ;   ergebnis <<= 1;
    LSL     R19
    RJMP    0x3A98

Wie man sieht, ist die leserlichere Variante sogar mit weniger CPU-Zyklen belastet als die obige Variante.
Ich habs mal nachgeschaut. Die 8 Zyklen mehr stammen aus der Multiplikation die der COmpiler hier offensichtlich nicht als Shift nach links erkannt hat.

darauf bin ich auch gekommen.
unverzeichlich, zuerst mit einem mist-compiler zu optimieren und dann auch noch darauf was zu behaupten. natürlich sind die beiden versionen identisch bist auf compilerdummheit. bereits der Watcom (als er noch verkauft wurde) hat zuverlässig multiplikationen zu shifts umgesetzt.

[volkard]

junix schrieb:

Äh ja, 1 Cycle = 1 Takt. Jedes Assemblerkommando hat bestimmte Kosten an Cycles... daraus lässt sich die gesamtlaufzeit des Abschnitts errechnen, bzw. mit dem AVR Studio (in meinem Fall) kann ich das bequem ablesen wieviele cycles zwischen zwei Haltepunkten vergangen sind.

muss ganz schon veraltet sein.
war es nicht so, daß die kosten bereits nicht mehr abschättzbar sind, seit bei sprüngen ein pfad vorausberechnet wird und der andere nicht und wenn der prozessor richtig geraten hat, kostet der sprung einen takt und wenn nicht, dann 13 straftakte? war es nicht so, daß die befehle eingelesen werden, und statt sie gleich zu verarbeiten, sie bei rechenbefehlen in die nächste freie alu gestopft werden, aber wenn alle 4 alus voll sind, dauerts auf einmal voll lange? war es nicht so, daß moderne compiler ram-zugriffe und interne rechnungen versuchen zu verschränken, weil dann weniger gewartet werden muss?

also kurz gesagt, takte zählen auf weisen wie vor 15 jahren ist echt nicht mehr drin.

[junix]

volkard schrieb:

außerdem sind wir hier im C-forum. die haxors nehmen mich nicht ernst, wenn der code wie kindergartencode aussieht.

*lol*

volkard schrieb:

aber dein gefummle mit | und << finde ich nicht ok. ich verlasse mich gar nicht auf eine interne darstellung oder so, sondern mache nur mathe.

Ok, Endianportabel ist der Code nicht. Da hast du recht.

volkard schrieb:

int ergebnis=0;
for(char* pos=wertstring;*pos!='\0';++pos){
   ergebnis += *wertstring-'0';
   ergebnis *= 2;
}

Die Version gefällt mir massiv besser. v.A. weil da auch nciht der Ursprungspointer verändert wird. Und lesen kann mans sogar auch (o;
Frage: Wie kann ich mit Mathe verhindern, dass Mist passiert, wenn der String z.B. ne 3 enthält?

Es sei mir verziehen. Ich habe nur einen Atmel AVR Compiler von IAR zur Hand gehabt. Die beiden Varianten spucken mir folgenden Assembler aus.

nein, nicht verziehen. [...] unverzeichlich, zuerst mit einem mist-compiler zu optimieren und dann auch noch darauf was zu behaupten. natürlich sind die beiden versionen identisch bist auf compilerdummheit.[/quote]Nana... Mist-Compiler würd ich den mal so nicht nennen. Der Witz ist nur, dass ich 0 Optimierung eingestellt hatte... D.h. er übersetzt den Code 1:1 wie er da steht. War mir auch klar, dass der Code identisch sein muss... Wollte das nur auch bewiesen haben, bevor da wer kommt und was anderes behauptet.

-junix

[junix]

volkard schrieb:

junix schrieb:

[...]Jedes Assemblerkommando hat bestimmte Kosten an Cycles... [...]

[...] also kurz gesagt, takte zählen auf weisen wie vor 15 jahren ist echt nicht mehr drin.

Lieber Volkard. Kurz gesagt scheinst du überlesen zu haben, dass es sich beim Atmel AVR um einen Embedded Prozessor handelt. Da ich grad keinen anderen Compiler so zur Hand hatte. Hier kannst du also schlicht nicht die Massstäbe ansetzen, wie du sie für Highperformance-CPUs benutzt.

-junix

[volkard]

junix schrieb:

Frage: Wie kann ich mit Mathe verhindern, dass Mist passiert, wenn der String z.B. ne 3 enthält?

wozu?
enthält ein "binärstring" ne 3, ist der dezimalwert dessen einfach undefiniert.

[junix]

Naja vielleicht hätts nen Weg gegeben den Binärstring zu "prüfen" ohne, das ich durchs ganze char-array durchsteigen muss. Wobei mir einfällt ein "& 0x01" müsste eigentlich auch wieder Endian-unabhängig sein oder?

[edit]Ja, ich weiss, es wurde nach dem effektivsten Weg gefragt. Nur stellt sich die Frage ob man die Verantwortung immer eins nach oben schiebt oder nicht. Wobei eigentlich ... die Eingabeprüfung müsste es übernehmen... stimmt schon...[/edit]

[Vertexwahn]

> also kurz gesagt, takte zählen auf weisen wie vor 15 jahren ist echt nicht mehr drin.

welche Bücher muss man den lesen um herauszufinden wie die takte gezählt werden? in so manchen Assemblerbuch (Assemblerbuch von Reiner Backer, Assemblerprogrammierung von Wolfgang Link) wird so etwas nicht behandlet - ich nehm mal an das die meisten C/C++ autoren auch nicht auf das thema eingehen... mmh... oder vielleicht sollte ich das Intel IA-32 Developer Manuel lesen... vielleicht erfahr ich da mehr...?

[volkard]

junix schrieb:

[edit]Ja, ich weiss, es wurde nach dem effektivsten Weg gefragt. Nur stellt sich die Frage ob man die Verantwortung immer eins nach oben schiebt oder nicht. Wobei eigentlich ... die Eingabeprüfung müsste es übernehmen... stimmt schon...[/edit]

ich schiebe binärstings umher, die auch von nem programm generiert wurden. ich würde sicher nicht deine lib verwenden, die eingeabeprüfung dabei macht.
ich würd emich aber über ne lib freuen, die zwei funktionen bereitstellt, eine die prüft und eine, die rechnet.

[junix]

Wenn du Volkards Posting nochmals liest, wirst du herausfinden, dass Taktezählen bei aktuellen PC-Prozessoren nicht mehr möglich ist. Ich hatte lediglich die Chance dies zu tun, weil ich grad eine Embedded CPU neben mir liegen habe. Diese haben nicht derart ausgefeilte Prefetch und Cache Techniken.

Ansonsten gibts nur eines um takte zu zählen:
CPU im Single Process Modus laufen lassen und irgend einen Pin zu Beginn der Operation auf High legen und am Ende wieder auf Low zu legen. Ergebnis: Ein Rechtecksignal mit welchem man die Ausführungszeit ausrechnen kann. Diese Zeit dann durch die Taktfrequenz dividiert...

Aber zum Glück gehts auch ohne oszilloskop und die Intel CPUs haben irgendwo ein Stück Hardware (ein sog. High resolution Timer) auf welches auch [msdn]QueryPerformanceCounter[/msdn] [msdn]QueryPerformanceFrequency[/msdn](WinAPI) zugreift.

Damit dürfte sich sowas machen lassen...

-junix

[junix]

Ich hatte da noch was in den Bookmarks zum Thema High Resolution Counter:
http://www.intel.com/design/pentium4/manuals/25366814.pdf

Kapitel 15.9 Performance Monitoring Overview.
bzw. 15.12 (für generell 686)

-junix