Shift-Operator und Performance

Regler schrieb:
> Hallo,
>
> ist euch schonmal aufgefallen, dass der Shift-Operator ziemlich viel
> Rechenleistung erfordert?
Bei einem x86er sicher nicht.

>

.

Ja ne is klar ;-)

> Ich vermute (beherrsche leider kein ASM), dass der Algorithmus rekursiv
> in ASM vom Compiler umgesetzt wird.
Rekursion? Was ist denn jetzt los?

> Weiß jemand mehr darüber, warum der Shift-Algorithmus so viele Ops
> braucht?
Tut er ja gar nicht auf einem x86er

> Hätte vermutet, dass der sehr effizient vom AVR umgesetzt
> werden kann. Liegts am Compiler (und gibt es gescheiten inline-ASM),
> oder am AVR und dessen OP-Set selbst?
Oh, jetzt redest du ja auf ein mal von AVRs. Da haben wir wohl 
aneinander vorbeigeredet ;-)

Es liegt einfach daran, dass der AVR als Maschinenzyklus nur einen 
einfachen Shift hat. Das heißt, wenn man um 4 shiften möchte, braucht 
man 4 einzelne Shifts.

Aber erst mal die Schuld auf Rekursion schieben? ;-) Informatik-Studium 
geschädigt? :-)

Rekursief geht's meistens schief!

Klaus Wachtler schrieb:
> Rekursief geht's meistens schief!

Eben! :-D Ich programmier schon ein paar Jährchen, mir ist aber noch nie 
was rekursives untergekommen (außer mal ne Knobelaufgabe damals anner 
Berufsschule).

Kannst ja mal Karl Heinz Buchegger fragen, mit wievielen rekursiven 
Sachen er schon so zu tun hatte in seiner Laufbahn ;-)

och, also ich brauche das öfter mal.

Es gibt etliche Sachen, die sich nicht rekursiv nicht vernünftig
erschlagen lassen (Suchen, Sortieren, Bäume durchlaufen...).

Eher weniger auf einem Controller, aber sonst schon.

Regler schrieb:
> Bin übrigens Maschbauer...

Das sind doch sowieso die besseren Programmierer!
Willkommen im Club.

Der Controller kann nur einzelne Shifts. Die muss man dann eben mehrmals 
beanspruchen. Mehr Arbeit gibt es bei groesseren Datentypen, zb einem 
Longword.

Klaus Wachtler schrieb:
> Rekursief geht's meistens schief!

Ach geh, Rekursion ist auch nicht mehr, was es mal war...

1

#include <stdint.h>

2

3

uint8_t lsl_n (uint8_t x, uint8_t n)

4

{

5

    return n ? lsl_n (x << 1, n-1) : x;

6

}

7

8

uint8_t lsl_7 (uint8_t x)

9

{

10

    return lsl_n (x, 7);

11

}

avr-gcc 4.5.1 -Os ... macht daraus

1

lsl_n:

2

.L3:

3

  tst r22

4

  breq .L2

5

  lsl r24

6

  subi r22,lo8(-(-1))

7

  rjmp .L3

8

.L2:

9

  ret

10

11

lsl_7:

12

  ror r24

13

  clr r24

14

  ror r24

15

  ret

Hehe! Mööööp. :-)

Johann L. schrieb:
> Ach geh, Rekursion ist auch nicht mehr, was es mal war...

Rekursionen sind eben so ineffektiv, daß sogar der Compiler sie nicht 
mag.

Ich wüßte auch kein Beispiel wo ne Rekursion Sinn macht.

Manchmal kann man damit ne sehr kurze Schreibweise erreichen, dafür 
sitzt man dann Stunden davor, um sie auch zu verstehen.

Programme mit ner Schleife sind dagegen in der Regel gut verständlich.


Peter

Regler schrieb:

> Liegts am Compiler (und gibt es gescheiten inline-ASM),
> oder am AVR und dessen OP-Set selbst?

Assembler kann für den Fall helfen, wo nur eine 1 geschoben wird um eine 
Maske zu erhalten. Ich hab mal in meinen Quellen gebuddelt, wo ich sowas 
in 'ner zeitkritischen ISR hatte (avr-as):

1

// r25 = 1 << r24

2

ldi  25, 1

3

sbrc 24, 1

4

ldi  25, 4

5

sbrc 24, 2

6

swap 25

7

sbrc 24, 0

8

lsl  24

Wenn ich's recht sehe, dürfte ein C-Compiler eine solche Sequenz 
allerdings nicht verwenden für 1 << n. (Ich steh irgendwie auf Kriegsfuß 
mit den C promotion rules.)

Peter Dannegger schrieb:
> Johann L. schrieb:
>> Ach geh, Rekursion ist auch nicht mehr, was es mal war...
>
> Rekursionen sind eben so ineffektiv, daß sogar der Compiler sie nicht
> mag.

Wahrscheinlich nimmt er sie hier nur nicht, weil er sie selbst nicht 
verstanden hat :-)

>
> Ich wüßte auch kein Beispiel wo ne Rekursion Sinn macht.

Wieviele willst du?

ARM dran schrieb im Beitrag #1926629:
> Minimaler "Recursive Descend"-Parser.
> Schnell hingeschrieben, leicht zu verstehen.

Da muß ich gestehen, daß ich davon absolut 0,nix Ahnung habe.

Ich programmiere nur MCs und daher habe ich damit nichts zu tun.
Da benutze ich nur ganz einfache Parser (Kommandostring, Parameter 1, 
... Parameter n) ohne Rekursion.


Peter

Peter Dannegger schrieb:

> Ich wüßte auch kein Beispiel wo ne Rekursion Sinn macht.

1

void fatal (const char * msg)

2

{

3

    fprintf (stderr, msg);

4

    exit (1);

5

}

6

7

void fprintf (FILE * stream, const char * fmt, ...)

8

{

9

   ...

10

   if (EOF == fputs (..., stream))

11

   {

12

       fatal ("Ein schwerer Fehler ist aufgetreten!\n");

13

   }

14

   ...

15

}

@Johann L.

Lustig.
Wenn stderr EOF liefert, läßt Du also einfach den Stack überlaufen.


Peter

Andreas B. schrieb:
> Johann L. schrieb:
>> Wenn ich's recht sehe, dürfte ein C-Compiler eine solche Sequenz
>> allerdings nicht verwenden für 1 << n. (Ich steh irgendwie auf Kriegsfuß
>> mit den C promotion rules.)
>
> Abgesehen davon, dass die letzte Zeile wohl "lsl 25" heißen sollte, ist

Ja.

> doch das einzige was fehlt, dass r25=0 sein müsste falls eines der Bits
> 3-7 in r24 gesetzt ist. Das dürfte wohl vor oder nach dieser Sequenz
> behandelt worden sein.

Nö, dass muss nicht behandelt werden, da in C unspezifiziert ist wenn 
weiter als die Typbreite geschoben wird. Allerdings versteh ich die 
C-Regel da nicht ganz, ob da er nach 16 Bit promoted werden muss. In dem 
Falle wär's kein Ersatz.

Jedenfalls bekomm ich es momentan mit avr-gcc nicht hin, einen 8-Bit 
Shift erzeugen zu lassen (4.5.1). Es muss aber gehen, sonst gäb es im 
gcc keine Pattern dafür. Möglicherweise ist's irgende Optimierung die 
sich wieder mal selber ins Knie schiesst. In dem Falls wäre die Sequenz 
in avr-gcc ok (natürlich mit r25 und nur für O2+, da die Sequemz 2 Byte 
länder ist als ne Schleife. Wobei letztere allerdings den Eingabewert 
zerstört und er nicht wiederverwendbar ist. Wenn also ne Kopie nötig 
wird, ist es sogar für Os gleich gut).

Übrigens führt das dazu, daß ein n-facher Shift um 1 in C ein anderes 
Ergebnis haben kann als einen Wert n-fach zu Shiften, nämlich wenn die 
Shiftweite breiter ist als der Typ.

Simon K. schrieb:

> Kannst ja mal Karl Heinz Buchegger fragen, mit wievielen rekursiven
> Sachen er schon so zu tun hatte in seiner Laufbahn ;-)


Ach, gar nicht mal so wenig.
Sobald es um Bäume geht wird es eigentlich meistens rekursiv. Und Bäume 
finden sich bei dem was ich beruflich mache sowieso mehr als genug.
Bei Listen ist Rekursion auch möglich, aber eher selten.

Für mich ist Rekursion oft ein sehr natürlicher Zugang zu vielen 
Problemstellungen und ein Werkzeug, das ich nicht missen möchte :-)
Hat man erst mal die Denkweise intus, ist Rekursion auch nicht einfacher 
oder schwieriger als das Denken in Schleifen. Übrigens ist die 
pragmatische Sichtweise der Objektorientierung (darum kümmere ich [das 
Objekt] nicht selber, sondern das delegiere ich an ein anderes Objekt, 
das ist dafür zuständig) nicht ganz unähnlich der Sichtweise mit der man 
Rekursionen zu Leibe rücken kann.

Allerdings ist bei Mikrocontrollern der benötigte Stack immer relativ 
schwer hervorzusehen, weshalb man sowas eher vermeidet. Also ich 
zumindest :-)

Klar, bei Bäumen gehts schon fast gar nicht anders als rekursiv. Hat man 
aber auch selten bei Mikrocontrollern.

Regler schrieb:

> Muss aber gestehen, das ich mich vielleicht in der Terminologie
> vergriffen habe!?

Vielleicht eine Konfusion Rekursion/Iteration?

Regler schrieb:
> Korrigier mich, wenn ich falsch liege, aber viele Filter sind doch
> rekursiv (in der Zeit-Domäne) implementiert, da sonst VIEL zu aufwendig.
> Ich denke da an Killer-Berechnungen wie Matrizeninversionen
> (Stichwort:Sherman-Morrison-Woodbury), aber auch an den einfachen
> Moving-Average-Filter.

Stimmt schon. Gewisse digitale Filterstrukturen werden rekursiv 
implementiert. Das heißt aber meines Wissens, dass das Ausgangssignal 
wieder in die nächste Berechnung mit einfließt.
Das heißt aber noch lange nicht, dass solche Filter rekursiv 
programmiert werden (müssen).

Rekursion lässt sich ggf. iterativ umformulieren. Im Fall der 
Endrekursion tut dies bereits der GNU-Compiler, wie Johann oben 
demonstrierte.

Regler schrieb:
> Häh?
> Wie will man einen rekursiven Filter nichtrekursiv implementieren? Oder
> anders: Der Unterschied zwischen "rekursiv implementiert" und "rekursiv
> programmiert" leuchtet mir gerade nicht richtig ein.

Wenn der Filter rekursiv ist, heißt das nur, dass das Ergebnis beim 
letzten Durchlauf dies mal wieder mitverwendet wird.
Wie willst du einen rekursiven Filter denn rekursiv implementieren? ;-)

Ein Beispiel für einen rekursiven Moving-Average Filter ist:

1

#define N    8

2

3

....

4

5

static int32_t Wert;

6

int32_t NeuerWert = Eingabequelle;

7

8

Wert = (Wert * (N-1) + NeuerWert) / N;

9

10

....

Deswegen hat das mit einer programmiertechnischen Rekursion überhaupt 
nichts zu tun.

> Ich denke du meinst den Unterschied "rekursiv in der Zeitdomäne" und
> "rekursiv im Programmablauf". Da liegt auch (glaub ich) der Grund meiner
> "Konfusion". ;)
Ja. Das ist zwar der gleiche Begriff mit der gleichen Bedeutung, aber 
die Anwendung ist grundverschieden.