Performance - großes switch-statement - jump-table ?

[balu (Gast)]

Hallo zusammen,

als Anfänger in der Embedded Programmierung habe ich eine (vielleicht 
triviale) Frage bei der mir sicher jemand einen Tip geben kann?

Innerhalb meines Programms befindet sich ein großes switch-statement, 
das sehr häufig ausgeführt wird. Der Wertebereich über den "geswitched" 
wird erstreckt sich von 0-256, die einzelnen Cases(werte) sind 
allerdings nicht unbedingt aufeinanderfolgend. Avr-gcc scheint mir immer 
ein binary-search daraus zu generieren ich hätte aber lieber einen 
jump-table o.ä. Ich konnte avr-gcc allerdings nie dazu bewegen einen 
jump-table zu generieren  auch wenn der Wertebereich über den der switch 
ging voll ausgeschöpft war.

Als nächstes habe ich versucht gcc's label-as-value zu verwenden (jeder 
case ein label, ein array mit allen labels erstellen ala &&LABEL... und 
dann mit dem Wert der switch-expression in das array mit goto * 
array[expr] springen). Das hat allerdings den großen Nachteil, dass ich 
das Array im RAM halten muss (was für einen atmega128 ca. 512 byte 
bedeutet).

Was macht man in so einem Fall typischerweise? Wieso verwendet avr-gcc 
(4.1.2) keine jump-tables? Könnte ich nicht ein vielfaches der 
switch-expression(0-256) im Programmcode springen und von dort über das 
Label den jeweiligen Fall abarbeiten?

Gruß Balu

[Falk B. (falk)]

Man könnte das auch mit Funktionspointern in einem Array machen. Die 
kann man problemlos in den Flash packen und es macht die Sache 
übersichtlicher.

MFG
Falk

[(prx) A. K. (prx)]

Läss sich das goto nicht mit Array im ROM und pgm_read_word oder so 
kombinieren?

[balu (Gast)]

Danke für die schnelle Antwort,

ist das ganze dann nicht wieder langsamer dadurch, dass auf den Flash
zugegriffen werden muss? Im Endeffekt müsst ich aber nur 16-bit lesen 
oder?

Gruß Balu

[(prx) A. K. (prx)]

Flash lesen ist kaum langsamer als indirekt RAM lesen, insgesamt um 2 
Takte nehme ich an. Und bei der von dir gesuchten switch-table wär's ja 
auch nicht anders.

[Johann L. (gjlayde)]

Möglicherweise fehlt avr-gcc das Pattern "tablejump", wobei das "casesi" 
vorhanden ist, sollte also gehen.
Aber 100% sicher bin ich da nicht, ob das casesi auch funzt ohne 
tablejump, müsste ich durch gcc durch...

Ob man von aussen per --param an die Thresholds kommt, hab ich auf die 
schnelle auch net gesehen in der gcc-Doc. Hab leider keine Quelle hier 
zum greppen.

Computed goto-Labels kannst du auch ins Flash legen. Das ist vielleicht 
übersichtlicher als 256 Funktionen. Das Beispiel ist für 16-Bit PC und 
GNU-C.

#include <avr/pgmspace.h>

#if (__GNUC__ > 3) && !defined (__AVR_2_BYTE_PC__)
#error Nur fuer 2-Byte PC
#endif

uint16_t bar (uint16_t i)
{
    static const void ** labels[] PROGMEM = 
    {
        && label0,
        && label1
    };
    
    if (i < sizeof (labels) / sizeof (labels[0]))
    {
        void ** addr = (void**) pgm_read_word (& labels[i]);
        goto *addr;
    }
    
    return 0;
    
    
    label1:
        return 2;
        
    label0:
        return i+1;
}

Das Lesen aus dem Flash kostet pro Byte (incl. evtl. post-inc) 1 
Taktzyklus.

Die Adressberechnung ist da nicht mitgerechnet, die kostet bei der 
RAM-Variante aber das gleiche.

Johann

[Simon K. (simon)]

Gibts nen Grund warum man einen doppelten Zeiger verwenden muss bei der 
Geschichte?

[Johann L. (gjlayde)]

Simon K. schrieb:
> Gibts nen Grund warum man einen doppelten Zeiger verwenden muss bei der
> Geschichte?

Muss man glaub garnicht. Sowas müsste auch gehen:

    if (i)
      goto *((void*) 0);
    else
      goto *((void*) bar);

Ich faand's nur seltsam, void* zu schreiben, weil man ja dereferenziert 
und ein void-Objekt bekommt. Das kenn ich nur von

   (void) i;

[Balu (Gast)]

Danke an alle! Hat funktioniert. Viel schneller als das große 
Switch-statement ist es leider nicht, dafür ist der Code aber um einiges 
kleiner.
Gruß Balu