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

Gast #1290005
Lesenswert?

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
Persönliche Seite #1290102
Lesenswert?

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.
1
#include <avr/pgmspace.h>
2

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

7
uint16_t bar (uint16_t i)
8
{
9
    static const void ** labels[] PROGMEM = 
10
    {
11
        && label0,
12
        && label1
13
    };
14
    
15
    if (i < sizeof (labels) / sizeof (labels[0]))
16
    {
17
        void ** addr = (void**) pgm_read_word (& labels[i]);
18
        goto *addr;
19
    }
20
    
21
    return 0;
22
    
23
    
24
    label1:
25
        return 2;
26
        
27
    label0:
28
        return i+1;
29
}

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

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

oder

Mit Google-Account einloggen

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren