AVR/ATmega uint32_t Deinterleaving optimieren

[Eckhart (Gast)]

Hallo Leute,

weil hier jemand beim Routing offenbar nicht wirklich nachgedacht hat, 
brauche ich jetzt eine Routine, die mir aus 32 Bit alle geraden und alle 
ungeraden Bits rausholt.

Mein erster Ansatz:

    void deinterleave( uint32_t in, uint16_t* odd, uint16_t* even)
    {
        uint32_t mask = 0x80000000;

        while( mask > 0)
        {
            *even = *even << 1;
            if(( mask & in) > 0)
            {
                *even = *even | 0x0001;
            }
            mask = mask >> 1;

            *odd = *odd << 1;
            if(( mask & in) > 0)
            {
                *odd = *odd | 0x0001;
            }
            mask = mask >> 1;
        }
    }

Zielsystem ist ein ATmega168, da erzeugt man mit 32 Bit-Variablen eh 
schon viel (ASM-)Code.
Mir geht es aber hauptsächlich um Geschwindigkeit.

Sieht da jemand noch Optimierungspotential?

[Frickelfritze (Gast)]

Eckhart schrieb:
> Sieht da jemand noch Optimierungspotential?

Lokale Kopie von even und odd anlegen (also keine dauernden
Zugriffe per Pointer) und am Ende der Auswertung erst
zurückgeben.

[STK500-Besitzer (Gast)]

zwei Mal die gleiche  Schleife?
Warum nicht einfach einen else-Zweig?
Oder, da die Länge des Datenwortes bekannt ist (32 Bits), einfach die 
eine Menge von 32 Subtrahieren.

[Eckhart (Gast)]

Frickelfritze schrieb:
> Lokale Kopie von even und odd anlegen (also keine dauernden
> Zugriffe per Pointer) und am Ende der Auswertung erst
> zurückgeben.

Tatsächlich, das ist ca. 30% schneller (mit Oszi nachgemessen):

    // 760 us @ 1 MHz
    void deinterleave2( uint32_t in, uint16_t* odd_p, uint16_t* even_p)
    {
        uint32_t mask = 0x80000000;
        uint16_t odd  = *odd_p;
        uint16_t even = *even_p;

        while( mask > 0)
        {
            even = even << 1;
            if(( mask & in) > 0)
            {
                even = even | 0x0001;
            }
            mask = mask >> 1;

            odd = odd << 1;
            if(( mask & in) > 0)
            {
                odd = odd | 0x0001;
            }
            mask = mask >> 1;
        }

        *odd_p  = odd;
        *even_p = even;
    }

Dankeschön :-)

[Anja (Gast)]

Eckhart schrieb:
> Mir geht es aber hauptsächlich um Geschwindigkeit.

Warum nimmst Du dann nicht 2 Tabellen mit je 256 Einträgen die dir 
jeweils ein Nibble ausrechnen?
Wenn es nicht ganz so schnell gehen muß reicht eine Tabelle mit 128 
Einträgen.

Gruß Anja

[Frickelfritze (Gast)]

Eckhart schrieb:
> Dankeschön :-)

Gerne.

(na das war einfach)

[Norbert (Gast)]

Um Platz zu sparen nimm zwei 16Byte Tabellen und arbeite "Nibble-weise" 
an den Daten. Dabei hilft der SWAP Befehl ungemein.
Loop-unroll wird auch noch ein wenig bringen.

[Mario M. (thelonging)]

Da es sich um AVR handelt, kann man auch die eingebaute Funktion zum 
Bit-Kopieren nutzen.

void deinterleave( uint32_t in, uint16_t* odd, uint16_t* even)
{
    uint8_t i0, i1, i2, i3, el, eh, ol, oh;

    i0 = in;
    i1 = in >> 8;
    i2 = in >> 16;
    i3 = in >> 24;

    el = __builtin_avr_insert_bits (0x88886420, i0, 0);
    el = __builtin_avr_insert_bits (0x6420ffff, i1, el);
    ol = __builtin_avr_insert_bits (0x88887531, i0, 0);
    ol = __builtin_avr_insert_bits (0x7531ffff, i1, ol);
    eh = __builtin_avr_insert_bits (0x88886420, i2, 0);
    eh = __builtin_avr_insert_bits (0x6420ffff, i3, eh);
    oh = __builtin_avr_insert_bits (0x88887531, i2, 0);
    oh = __builtin_avr_insert_bits (0x7531ffff, i3, oh);

    *odd = oh << 8 | ol;
    *even= eh << 8 | el;
}

[Peter D. (peda)]

Man könnte das auch ausrollen, dürfte vom Code auch nicht viel mehr 
sein:

    void deinterleave2( uint32_t in, uint16_t* odd_p, uint16_t* even_p)
    {
        uint16_t odd = 0;
        uint16_t even = 0;

        if( in & 1<<0 ) odd |= 1<<0;
        if( in & 1<<1 ) even |= 1<<0;
        if( in & 1<<2 ) odd |= 1<<1;
        if( in & 1<<3 ) even |= 1<<1;
        if( in & 1<<4 ) odd |= 1<<2;
        if( in & 1<<5 ) even |= 1<<2;
// usw.
        if( in & 1<<30 ) odd |= 1<<15;
        if( in & 1<<31 ) even |= 1<<15;
        *odd_p  = odd;
        *even_p = even;
    }

[asdfasd (Gast)]

Hier noch ne portable Variante:

static uint16_t packeven(uint32_t x)
{                       
    x &= 0x55555555;    
    x |= x>>1;          
    x &= 0x33333333;    
    x |= x>>2;          
    x &= 0x0f0f0f0f;    
    x |= x>>4;          
    x &= 0x00ff00ff;    
    x |= x>>8;          
    return x;
}

void deinterleave(uint32_t x, uint16_t *odd, uint16_t *even)
{
    *even = packeven(x);
    *odd = packeven(x>>1);
}

[Eckhart (Gast)]

Ich habe jetzt die Variante mit den zwei Tabellen umgesetzt.
Ich hatte da erst einen Knoten im Kopf, weil ich 'eigentlich' einen 
uint64_t zerlegen muß. Das wäre mit einer Tabelle etwas 'viel' geworden 
;-)

Ich habe die Funktionen jetzt getrennt, da ich die Ergebnisse nicht 
gleichzeitig brauche:

    uint8_t odd16( uint8_t high, uint8_t low)
    {
        union                                      
        {                                          
            uint8_t u8; 
            struct
            {                                      
                uint16_t a : 4;                    
                uint16_t b : 4;                    
            };                                     
        } result; 
        
        result.a = pgm_read_byte( &odd_bits[ low]);        
        result.b = pgm_read_byte( &odd_bits[ high]);       

        return result.u8;                          
    }

Anbei noch der Generator für die Tabellen, falls das mal jemand 
benötigt...
Danke für den entscheidenden Tipp von Anja und auch für die anderen 
Vorschläge, auch wenn ich die jetzt nicht mehr ausprobieren werden.
Ich vermute aber, daß die vielen Shifts auch etwas Zeit kosten.
Das kann ja der geneigte Leser jetzt selbst testen :-)

[Kaj G. (Firma: RUB) (bloody)]

Eckhart schrieb:
> Ich habe die Funktionen jetzt getrennt, da ich die Ergebnisse nicht
> gleichzeitig brauche:
Das ist aber undefiniertes Verhalten.
Laut C-Standard darfst du nur den Teil eines Union lesen, den du zu 
letzt geschrieben hast, und das tust du nicht.
Du schreibst als letztes b des anonymen structs, liest aber result.u8.

Ausserdem verlaesst sich dein Code auf die Annahme, was die Anordnung im 
Speicher angeht, naemlich das result.a immer das untere Nibble und 
result.b immer das obere Nibble ist.
Insgesamt nicht schoen und nicht zu empfehlen.

Eckhart schrieb:
> daß die vielen Shifts auch etwas Zeit kosten
Zumindestens in dem Vorschlag von Peter Dannegger sind alle 
Shiftoperationen zur Compilezeit bekannt. Der Compiler wird das 
wahrscheinlich optimieren und da gar nichts shiften.
Aus:

        if( in & 1<<0 ) odd |= 1<<0;
        if( in & 1<<1 ) even |= 1<<0;
        if( in & 1<<2 ) odd |= 1<<1;
        if( in & 1<<3 ) even |= 1<<1;

wird dann vermutlich:

        if( in & 0x01 ) odd |= 0x01;
        if( in & 0x02 ) even |= 0x01;
        if( in & 0x04 ) odd |= 0x02;
        if( in & 0x08 ) even |= 0x02;
        /*  usw.  */

[Peter D. (peda)]

Eckhart schrieb:
> Ich vermute aber, daß die vielen Shifts auch etwas Zeit kosten.

32bit Schieben muß der AVR in 4 8Bit-Schiebeinstruktionen zerlegen (4 
Zyklen).
Das spart man sich mit dem Ausrollen. Da muß der Compiler nur ein Bit im 
Register testen (SBRC) und ein Bit setzen (ORI),  ergibt 2 Zyklen je 
Bit. Das sind dann 32 Zyklen für die Zerlegung von 32Bit in 16Bit odd 
oder even.

Hast Du mal gemessen, wie lange die Tabelle braucht?
Meine Erfahrung ist, daß Structelemente <8Bit nicht sonderlich 
effizienten Code ergeben, da der Compiler das ja mit 8Bit-Befehlen 
emulieren muß.

[Leo C. (rapid)]

Kaj G. schrieb:
> Das ist aber undefiniertes Verhalten.

Dabei ist es gerade hier so einfach, die Sache richtig zu machen.

uint8_t odd16( uint8_t high, uint8_t low)
{
    return pgm_read_byte( &odd_bits[ low]) |
               (uint8_t) (pgm_read_byte( &odd_bits[ high]) << 4);
}

Im Ergebnis gleich, aber schöner wirds, wenn man das PROGMEM Geraffel 
durch __flash ersetzt:

const __flash uint8_t odd_bits[]  = {...};

uint8_t odd16( uint8_t high, uint8_t low)
{
    return odd_bits[ low] | (uint8_t) (odd_bits[ high] << 4);
}

Der (uint8_t) cast sorgt dafür, daß der Compiler für die Shift-Operation 
einen swap- statt mul-Befehl verwendet. Spart nochmal ca. 2 Taktzyklen.

[Eckhart (Gast)]

...es hat mir doch keine Ruhe gelassen...
Die Variante mit den zwei Tabellen habe ich noch auf eine Tabelle 
reduziert.
Es werden im oberen Nibble die even-Bits und im unteren Nibble die 
odd-Bits gespeichert.

Ich habe jetzt alle(?) Varianten implementiert und getestet.
Hier sortiert nach Laufzeit:

Autor     Merkmal                      Größe (avr-nm)   Laufzeit
-------   --------------------------   --------------   --------
Eckhart   32-Bit-Maske & Schleife      156              752 us
asdfasd   portable Version             194              264 us
Leo       Tabelle mit Bitshift         432 (mit Tab.)   152 us
Peter D.  if & or - ausgerollt         284              152 us
Mario M.  __builtin_avr_insert_bits    146              100 us
Anja      Tabelle mit Unions           385 (mit Tab.)    88 us

Bei der Variante von asdfasd und Mario M. sind even und odd vertauscht 
(oder es ist dort richtig und bei allen anderen falschrum :-)


asdfasd schrieb:
> Hier noch ne portable Variante:
Ist gar nicht so schlecht, wie ich erst wegen der 32-Bit-UNDs dachte...

Leo C. schrieb:
> Der (uint8_t) cast sorgt dafür, daß der Compiler für die Shift-Operation
> einen swap- statt mul-Befehl verwendet. Spart nochmal ca. 2 Taktzyklen.
Die Unions scheinen beim AVR-GCC recht performant implementiert zu sein.

Leo C. schrieb:
> Im Ergebnis gleich, aber schöner wirds, wenn man das PROGMEM Geraffel
> durch __flash ersetzt:const __flash uint8_t odd_bits[]  = {...};
Das kannte ich noch nicht, sehr schön.

Mario M. schrieb:
> el = __builtin_avr_insert_bits (0x88886420, i0, 0);
Schön klein, aber ohne Kommentar echt unlesbar :-)

Kaj G. schrieb:
> Das ist aber undefiniertes Verhalten.
> Laut C-Standard darfst du nur den Teil eines Union lesen, den du zu
> letzt geschrieben hast, und das tust du nicht.
> Du schreibst als letztes b des anonymen structs, liest aber result.u8.
>
> Ausserdem verlaesst sich dein Code auf die Annahme, was die Anordnung im
> Speicher angeht, naemlich das result.a immer das untere Nibble und
> result.b immer das obere Nibble ist.
> Insgesamt nicht schoen und nicht zu empfehlen.
Du klingst wie meine Großmutter...
C-Standard hin oder her: Für den AVR-GCC ist es offenbar definiert und 
ich finde es relativ gut lesbar. Und die schnellste Variante ist es auch 
noch.

Anbei noch die Quellen.

[Kaj G. (Firma: RUB) (bloody)]

Eckhart schrieb:
> Du klingst wie meine Großmutter...
Mag sein. Ob es Dir passt oder nicht:
Ich mache dich lediglich darauf aifmerksam, dass du dich auf 
undefiniertes verhalten verlaesst. Es mag jetzt funktionieren, kann aber 
schon mit der naechsten Version vom GCC ganz anders aussehen. Und sei es 
nur, weil jemand langeweile hat und den ganzen schlonz umbaut.
Und sollte es so kommen sehe ich Dich und andere, die sich auf dieses 
Verhalten verlassen, ueber Bugs im GCC und die dummen Entwickler 
schimpfen.
Das Problem liegt dann aber an Euch, und nicht am GCC und nicht an 
dessen Entwickler.

Eckhart schrieb:
> C-Standard hin oder her
Sorry, aber auf den Standard kann ich mich verlassen, auf alles andere 
nicht. Du kannst auch mit Autoreifen die nur bis 190km/h zugelassen sind 
250km/h fahren... scheiss auf den TÜV, die Reifenhersteller und alles 
andere. Wird schon gut gehen, du weisst ja was du tust... Wer braucht 
schon Standards und technische Spezifikationen, die machen das Leben ja 
nur unnoetig schwer.

Eckhart schrieb:
> Für den AVR-GCC ist es offenbar definiert
Was genau gibt es an "undefiniertes Verhalten" nicht zu verstehen?
Es ist nicht definiert, es ist mehr oder minder irgendwas implementiert. 
Riesiger Unterschied!

Eckhart schrieb:
> ich finde es relativ gut lesbar.
Mag sein, aendert aber nichts daran das es ziemlich schlechter Code ist, 
den ich dir bei jedem Code-Review um die Ohren hauen wuerde.

Eckhart schrieb:
> Und die schnellste Variante ist es auch
> noch.
Mag sein, Geschwindigkeit ist aber nicht alles. Wenn du Geschwindigkeit 
brauchst, mach es mit (inline) ASM, aber nicht mit C-Code der sich auf 
undefiniertes Verhalten verlaesst.

Eckhart schrieb:
> Du klingst wie meine Großmutter...
Und du klingst wie all die Firmen die jedes mal rumheulen, wenn ein 
poeser Hacker ueber Sicherheitsluecken in ihren Produkten berichtet, und 
besagten Entdecker am liebsten sofort erschiessen lassen wuerden. Man 
koennte ja auch mal Danke sagen, dass da jemand den Mist aufraeumt den 
man selber verzapft hat und einfach nur unwillens war es selber in 
ordnung zu bringen, weil man sich lieber wie ein bockiges Kind verhalten 
hat. Man selbst ist ja  schliesslich unfehlbar und alle anderen haben ja 
gar keine Ahnung.

Anstatt dich zu beklagen das ich "wie deine Grossmutter" klinge, 
solltest du froh sein und dich bedanken das dich jemand auf sowas 
hinweist. Aber hey, wenn du an dich selbst den Anspruch stellst 
moeglichst schlechten Code zu schreiben, soll mir das auch egal sein. 
Mehr als dir sagen das du dein Haus, ohne vernueftiges Fundament, auf 
Moor baust kann ich auch nicht machen.

Und das ist hier sogar kostenlos fuer dich. Es gibt Firmen, die 
verdienen damit ein schweine Geld.

[Carl D. (jcw2)]

> Es mag jetzt funktionieren, kann aber schon mit der naechsten Version vom
> GCC ganz anders aussehen. Und sei es nur, weil jemand langeweile hat und
> den ganzen schlonz umbaut.

Keine Sorge, selbst die mit Einführung der Multiplikationsbefehle 
suboptimale Festlegung von Tmp-/Zero-Register auf R0 und R1 hat bis 
heute noch niemand ändern wollen. Und wenn doch was geändert werden 
sollte, dann derbreselt es den ASM-Code genauso.

[asdfasd (Gast)]

> Bei der Variante von asdfasd [...] sind even und odd vertauscht

Bei mir fangen die Bits rechts mit 0 an ;-)

> Ist gar nicht so schlecht, wie ich erst wegen der 32-Bit-UNDs dachte

Nun ja, für ne 8bit-CPU ohne Barrelshifter ist die Version nicht so der 
Bringer. Die ist für Kisten mit 32bit-Registern und Barrelshifter 
gedacht. Die mögen auch den linearen Code ohne Verzweigungen und 
Speicherzugriffe. Und 64bit nach 2x32bit kostet gerade mal eine 
AND/OR-Kombination mehr. Mir ging es eher um den anderen Lösungsansatz.

Für AVR gefällt mir die builtin-insert-bits-Variante am besten.

[asdfasd (Gast)]

Nur zur Anschauung, wie kompakt die packeven-Funktion auf ARM ist:

packeven:
        and     r0, r0, #1431655765
        orr     r0, r0, r0, lsr #1
        and     r0, r0, #858993459
        orr     r0, r0, r0, lsr #2
        and     r0, r0, #252645135
        orr     r0, r0, r0, lsr #4
        and     r0, r0, #16711935
        orr     r0, r0, r0, lsr #8
        uxth    r0, r0
        bx      lr

[Kaj G. (Firma: RUB) (bloody)]

Eckhart schrieb:
> Ich habe jetzt alle(?) Varianten implementiert und getestet.
> Hier sortiert nach Laufzeit:Autor     Merkmal                      Größe
> (avr-nm)   Laufzeit
> -------   --------------------------   --------------   --------
> Eckhart   32-Bit-Maske & Schleife      156              752 us
> asdfasd   portable Version             194              264 us
> Leo       Tabelle mit Bitshift         432 (mit Tab.)   152 us
> Peter D.  if & or - ausgerollt         284              152 us
> Mario M.  __builtin_avr_insert_bits    146              100 us
> Anja      Tabelle mit Unions           385 (mit Tab.)    88 us

Die Laufzeit von z.B. Pedas Funktion ist durch die ganzen if's abhaengig 
von den Daten. Die Laufzeit variiert. Das hast du bei der Version von 
Anja oder asdfasd aber nicht. Du muesstest also fuer alle Varianten 
jeweils den Best-Case (kein Bit ist gesetzt), den Worst-Case (alle Bit 
sind gesetzt) und einen Mittelfall testen. Wobei bei dem Mittelfall ggf. 
die Shifts beruecksichtig werden muessen (nur die unteren 16 Bit sind 
gesetzt vs. nur die oberen 16 Bit sind gesetzt).

[Peter D. (peda)]

Eckhart schrieb:
> Peter D.  if & or - ausgerollt         284              152 us

Schon erstaunlich, welchen gewaltigen Overhead der AVR-GCC noch einfügt.
Anbei mal das Listing, da zähle ich aber nur 194 Bytes. Wie kommst Du 
auf 284?
Die nackten SBRC+ORI benötigen dabei 128 Bytes = 64 Zyklen.


Kaj G. schrieb:
> Die Laufzeit von z.B. Pedas Funktion ist durch die ganzen if's abhaengig
> von den Daten.

Nö.
SBRC+ORI braucht immer 2 Zyklen (2+0 oder 1+1).

[Markus F. (mfro)]

Kaj G. schrieb:
> Mag sein. Ob es Dir passt oder nicht:
> Ich mache dich lediglich darauf aifmerksam, dass du dich auf
> undefiniertes verhalten verlaesst. Es mag jetzt funktionieren, kann aber
> schon mit der naechsten Version vom GCC ganz anders aussehen. Und sei es
> nur, weil jemand langeweile hat und den ganzen schlonz umbaut.
> Und sollte es so kommen sehe ich Dich und andere, die sich auf dieses
> Verhalten verlassen, ueber Bugs im GCC und die dummen Entwickler
> schimpfen.

Schön geschrieben, bloß nicht (mehr) wahr:

6.5.2.3 Structure and union members

If the member used to read the contents of a union object is not the 
same as the member last used to store a value in the object, the 
appropriate part of the object representation of the value is 
reinterpreted as an object representation in the new type as described 
in 6.2.6 (a process sometimes called ‘‘type punning’’). This might be a 
trap representation.

C99 und C11 erlauben das (im Gegensatz zu C++) explizit.

[Eckhart (Gast)]

Peter D. schrieb:
> Wie kommst Du auf 284?
Das kann ich jetzt nicht mehr ganz nachvollziehen. Mit 'deinterleave.c' 
von weiter oben erhalte ich das hier:

$ avr-gcc --version
avr-gcc (GCC) 7.1.0
Copyright (C) 2017 Free Software Foundation, Inc.
[...]

$ avr-gcc -c  -mmcu=atmega168 -I. -gdwarf-2   -Os -funsigned-char -funsigned-bitfields -fpack-struct -fshort-enums -Wall -Wstrict-prototypes  -std=gnu99 -DF_OSC=1000000 -DF_CPU=1000000 -MD -MP deinterleave.c

$ avr-nm --print-size --size-sort --radix=decimal deinterleave.o
00000122 00000008 T init_LED
00000746 00000072 T deinterleave4
00000000 00000082 T main
00000646 00000100 T deinterleave3
00000000 00000122 t packeven
00000286 00000146 T deinterleave1
00000130 00000156 T deinterleave0
00000818 00000170 T deinterleave5
00000432 00000214 T deinterleave2
00000000 00000256 R even_odd_bits

Da sind es nur noch 214 Bytes. Die Ursache war vielleicht, weil ich im 
anderen Testprogramm mehr Code in der main drin hatte und daher mehr 
Register gesichert werden mussten.

[Peter D. (peda)]

Hier nochmal ne optimierte Variante mit Returnwert statt Pointer. Damit 
spart man massig an Overhead ein.
Pointer sollte man besser sparsam verwenden auf dem AVR.