Forum: Compiler & IDEs Bitshift schlecht implementiert?


von Philipp B. (philipp_burch)


Lesenswert?

Hallo zusammen,

ich bin gerade dabei, ein Programm für einen ATmega644 mit dem GCC zu 
erstellen. Das geht auch nicht schlecht, der GCC produziert in den 
meisten Fällen ganz ordentlichen Code. Aber eben nur in den meisten 
Fällen. Was mir aufgefallen ist, ist, dass die Bitschieberei scheinbar 
nicht so toll implementiert ist...
Am extremsten ist das bei diesem Code:
1
void rf_send(const uint32_t address) {
2
  RDD_MOSI |= _BV(PIN_MOSI);
3
  rf_dir(RF_DEFCHANNEL, 0);
4
  _delay_us(5);
5
  rf_sendspi((uint8_t)(address >> 20));
6
  rf_sendspi((uint8_t)(address >> 12));
7
  rf_sendspi((uint8_t)(address >> 4));
8
  rf_sendspi((uint8_t)(address << 4) | (uint8_t)((RF_MyAddress >> 24) & 0x0F));
9
  rf_sendspi((uint8_t)(RF_MyAddress >> 16));
10
  rf_sendspi((uint8_t)(RF_MyAddress >> 8));
11
  rf_sendspi((uint8_t)RF_MyAddress);
12
  uint8_t i;
13
  for (i = 0; i < RF_LEN_DATA / 8; i++) {
14
    rf_sendspi(RF_Data_TX[i]);
15
  }
16
  RPO_TRWCE &= ~_BV(PIN_TRWCE);
17
  _delay_ms(1);
18
  RPO_TRWCE |= _BV(PIN_TRWCE);
19
  rf_dir(RF_DEFCHANNEL, 1);
20
}
RF_MyAddress ist ebenfalls ein uint32_t. Zugegeben, diese Schieberei ist 
nicht ganz ideal, da ich ein Offset von 4 Bit ausgleichen muss (address 
und RF_MyAddress beinhalten jeweils 28 Bit Daten). Aber was der GCC da 
produziert (Optimierung -Os) ist doch etwas krass:
1
@00000259: rf_send
2
92:       void rf_send(const uint32_t address) {
3
+00000259:   92EF        PUSH    R14              Push register on stack
4
+0000025A:   92FF        PUSH    R15              Push register on stack
5
+0000025B:   930F        PUSH    R16              Push register on stack
6
+0000025C:   931F        PUSH    R17              Push register on stack
7
+0000025D:   93CF        PUSH    R28              Push register on stack
8
+0000025E:   93DF        PUSH    R29              Push register on stack
9
+0000025F:   017B        MOVW    R14,R22          Copy register pair
10
+00000260:   018C        MOVW    R16,R24          Copy register pair
11
93:         RDD_MOSI |= _BV(PIN_MOSI);
12
+00000261:   9A25        SBI     0x04,5           Set bit in I/O register
13
94:         rf_dir(RF_DEFCHANNEL, 0);
14
+00000262:   E060        LDI     R22,0x00         Load immediate
15
+00000263:   E186        LDI     R24,0x16         Load immediate
16
+00000264:   940E01F9    CALL    0x000001F9       Call subroutine
17
+00000266:   E08D        LDI     R24,0x0D         Load immediate
18
+00000267:   958A        DEC     R24              Decrement
19
+00000268:   F7F1        BRNE    PC-0x01          Branch if not equal
20
96:         rf_sendspi((uint8_t)(address >> 20));
21
+00000269:   01D8        MOVW    R26,R16          Copy register pair
22
+0000026A:   01C7        MOVW    R24,R14          Copy register pair
23
+0000026B:   E124        LDI     R18,0x14         Load immediate
24
+0000026C:   95B6        LSR     R27              Logical shift right
25
+0000026D:   95A7        ROR     R26              Rotate right through carry
26
+0000026E:   9597        ROR     R25              Rotate right through carry
27
+0000026F:   9587        ROR     R24              Rotate right through carry
28
+00000270:   952A        DEC     R18              Decrement
29
+00000271:   F7D1        BRNE    PC-0x05          Branch if not equal
30
+00000272:   940E01EE    CALL    0x000001EE       Call subroutine
31
97:         rf_sendspi((uint8_t)(address >> 12));
32
+00000274:   01D8        MOVW    R26,R16          Copy register pair
33
+00000275:   01C7        MOVW    R24,R14          Copy register pair
34
+00000276:   E0FC        LDI     R31,0x0C         Load immediate
35
+00000277:   95B6        LSR     R27              Logical shift right
36
+00000278:   95A7        ROR     R26              Rotate right through carry
37
+00000279:   9597        ROR     R25              Rotate right through carry
38
+0000027A:   9587        ROR     R24              Rotate right through carry
39
+0000027B:   95FA        DEC     R31              Decrement
40
+0000027C:   F7D1        BRNE    PC-0x05          Branch if not equal
41
+0000027D:   940E01EE    CALL    0x000001EE       Call subroutine
42
98:         rf_sendspi((uint8_t)(address >> 4));
43
+0000027F:   01D8        MOVW    R26,R16          Copy register pair
44
+00000280:   01C7        MOVW    R24,R14          Copy register pair
45
+00000281:   E0E4        LDI     R30,0x04         Load immediate
46
+00000282:   95B6        LSR     R27              Logical shift right
47
+00000283:   95A7        ROR     R26              Rotate right through carry
48
+00000284:   9597        ROR     R25              Rotate right through carry
49
+00000285:   9587        ROR     R24              Rotate right through carry
50
+00000286:   95EA        DEC     R30              Decrement
51
+00000287:   F7D1        BRNE    PC-0x05          Branch if not equal
52
+00000288:   940E01EE    CALL    0x000001EE       Call subroutine
53
99:         rf_sendspi((uint8_t)(address << 4) | (uint8_t)((RF_MyAddress >> 24) & 0x0F));
54
+0000028A:   0CEE        LSL     R14              Logical Shift Left
55
+0000028B:   0CEE        LSL     R14              Logical Shift Left
56
+0000028C:   0CEE        LSL     R14              Logical Shift Left
57
+0000028D:   0CEE        LSL     R14              Logical Shift Left
58
+0000028E:   9180037E    LDS     R24,0x037E       Load direct from data space
59
+00000290:   9190037F    LDS     R25,0x037F       Load direct from data space
60
+00000292:   91A00380    LDS     R26,0x0380       Load direct from data space
61
+00000294:   91B00381    LDS     R27,0x0381       Load direct from data space
62
+00000296:   2F8B        MOV     R24,R27          Copy register
63
+00000297:   2799        CLR     R25              Clear Register
64
+00000298:   27AA        CLR     R26              Clear Register
65
+00000299:   27BB        CLR     R27              Clear Register
66
+0000029A:   708F        ANDI    R24,0x0F         Logical AND with immediate
67
+0000029B:   298E        OR      R24,R14          Logical OR
68
+0000029C:   940E01EE    CALL    0x000001EE       Call subroutine
69
100:        rf_sendspi((uint8_t)(RF_MyAddress >> 16));
70
+0000029E:   91800380    LDS     R24,0x0380       Load direct from data space
71
+000002A0:   940E01EE    CALL    0x000001EE       Call subroutine
72
101:        rf_sendspi((uint8_t)(RF_MyAddress >> 8));
73
+000002A2:   9180037E    LDS     R24,0x037E       Load direct from data space
74
+000002A4:   9190037F    LDS     R25,0x037F       Load direct from data space
75
+000002A6:   91A00380    LDS     R26,0x0380       Load direct from data space
76
+000002A8:   91B00381    LDS     R27,0x0381       Load direct from data space
77
+000002AA:   2F89        MOV     R24,R25          Copy register
78
+000002AB:   2F9A        MOV     R25,R26          Copy register
79
+000002AC:   2FAB        MOV     R26,R27          Copy register
80
+000002AD:   27BB        CLR     R27              Clear Register
81
+000002AE:   940E01EE    CALL    0x000001EE       Call subroutine
82
102:        rf_sendspi((uint8_t)RF_MyAddress);
83
+000002B0:   9180037E    LDS     R24,0x037E       Load direct from data space
84
+000002B2:   940E01EE    CALL    0x000001EE       Call subroutine
85
+000002B4:   E6C8        LDI     R28,0x68         Load immediate
86
+000002B5:   E0D3        LDI     R29,0x03         Load immediate
87
105:          rf_sendspi(RF_Data_TX[i]);
88
+000002B6:   9189        LD      R24,Y+           Load indirect and postincrement
89
+000002B7:   940E01EE    CALL    0x000001EE       Call subroutine
90
104:        for (i = 0; i < RF_LEN_DATA / 8; i++) {
91
+000002B9:   E083        LDI     R24,0x03         Load immediate
92
+000002BA:   37CE        CPI     R28,0x7E         Compare with immediate
93
+000002BB:   07D8        CPC     R29,R24          Compare with carry
94
+000002BC:   F7C9        BRNE    PC-0x06          Branch if not equal
95
107:        RPO_TRWCE &= ~_BV(PIN_TRWCE);
96
+000002BD:   9843        CBI     0x08,3           Clear bit in I/O register
97
---- c:\programme\WinAVR\avr\include\util\delay_basic.h -------------------------------------------
98
105:        __asm__ volatile (
99
+000002BE:   ED80        LDI     R24,0xD0         Load immediate
100
+000002BF:   E097        LDI     R25,0x07         Load immediate
101
+000002C0:   9701        SBIW    R24,0x01         Subtract immediate from word
102
+000002C1:   F7F1        BRNE    PC-0x01          Branch if not equal
103
---- src\rf.c -------------------------------------------------------------------------------------
104
109:        RPO_TRWCE |= _BV(PIN_TRWCE);
105
+000002C2:   9A43        SBI     0x08,3           Set bit in I/O register
106
110:        rf_dir(RF_DEFCHANNEL, 1);
107
+000002C3:   E061        LDI     R22,0x01         Load immediate
108
+000002C4:   E186        LDI     R24,0x16         Load immediate
109
+000002C5:   940E01F9    CALL    0x000001F9       Call subroutine
110
+000002C7:   91DF        POP     R29              Pop register from stack
111
+000002C8:   91CF        POP     R28              Pop register from stack
112
+000002C9:   911F        POP     R17              Pop register from stack
113
+000002CA:   910F        POP     R16              Pop register from stack
114
+000002CB:   90FF        POP     R15              Pop register from stack
115
+000002CC:   90EF        POP     R14              Pop register from stack
116
+000002CD:   9508        RET                      Subroutine return

Ganz toll finde ich da besonders die Schleife bei der Verschiebung um 20 
Bit, die durch den folgenden Cast ja ohne Weiteres entfallen könnte, 
sowie solche Spielereien:
1
+0000028E:   9180037E    LDS     R24,0x037E       Load direct from data space
2
+00000290:   9190037F    LDS     R25,0x037F       Load direct from data space
3
+00000292:   91A00380    LDS     R26,0x0380       Load direct from data space
4
+00000294:   91B00381    LDS     R27,0x0381       Load direct from data space
5
+00000296:   2F8B        MOV     R24,R27          Copy register
6
+00000297:   2799        CLR     R25              Clear Register
7
+00000298:   27AA        CLR     R26              Clear Register
8
+00000299:   27BB        CLR     R27              Clear Register

Ahja. Man lade vier Register um sie dann auch gleich wieder zu 
überschreiben. Ganz toll.

Ich will ja nicht sagen, dass der GCC schlecht optimiert, noch verlange 
ich, dass jeder Code bis in's letzte Detail ausgefeilt ist. Doch bei -Os 
dürfte man doch eigentlich schon erwarten, dass wenigstens solche 
offensichtlichen Ehrenrunden vermieden werden. Die schlagen sich ja dann 
sowohl auf der Codegrösse, als auch auf der Ausführungszeit nieder...

Also, zum Schluss auch noch meine Frage:
Wie könnte ich den Code umschreiben, dass er besser optimiert wird? Oder 
gibt es nur die Möglichkeit, das ganze Zeug direkt in Assembler zu 
schreiben? Letzteres möchte ich eigentlich vermeiden, nicht weil ich ASM 
nicht mag, sondern weil das schlussendlich wohl mehr Probleme produziert 
als löst...


Danke schonmal für alle (konstruktiven) Antworten und freundliche 
Grüsse,
Philipp

von Andreas K. (a-k)


Lesenswert?

GCC lebt davon, dass er von Leuten verbessert wird. Mach es! Du hast 
keinen Anspruch darauf, dass andere es tun.

Ausserdem kannst du der Optimierung auch im Quellecode nachhelfen. Statt
1
  rf_sendspi((uint8_t)(address >> 20));
2
  rf_sendspi((uint8_t)(address >> 12));
schreibst du einfach
1
  rf_sendspi((uint16_t)(address >> 16) >> 4);
2
  rf_sendspi((uint16_t)(address >> 8) >> 4);

von Philipp B. (philipp_burch)


Lesenswert?

Andreas Kaiser wrote:
> GCC lebt davon, dass er von Leuten verbessert wird. Mach es! Du hast
> keinen Anspruch darauf, dass andere es tun.

Ich wusste doch, dass das kommt ;)
Würde ich gerne tun, leider habe ich vom Compilerbau wenig bis keine 
Ahnung. Wenn es so trivial wäre, wäre es auch bestimmt schon gemacht.

> Ausserdem kannst du der Optimierung auch im Quellecode nachhelfen. Statt
>
1
>   rf_sendspi((uint8_t)(address >> 20));
2
>   rf_sendspi((uint8_t)(address >> 12));
3
>
> schreibst du einfach
>
1
>   rf_sendspi((uint16_t)(address >> 16) >> 4);
2
>   rf_sendspi((uint16_t)(address >> 8) >> 4);
3
>

Ja, genau sowas habe ich gesucht. Danke! Mal sehn, was er draus macht.

von Benedikt K. (benedikt)


Lesenswert?

Probier mal -O1 oder - O2. Die erzeugen nach meiner Erfahrung einen 
kleineren und schnelleren Code.

von Andreas K. (a-k)


Lesenswert?

> Probier mal -O1 oder - O2. Die erzeugen nach meiner Erfahrung einen
> kleineren und schnelleren Code.

Bringt hier nichts. Der Compiler müsste mehr Lösungensansätze für 32bit 
Shifts implementieren als er tut. Also beispielsweise Shifts in 2 Stufen 
realisieren, die erste mit n*8 durch Byteversatz, dann den Rest. Bei 
16bit macht er das, bei 32bit offenbar nicht.

Sowas ist entweder drin und wirkt immer, oder es ist nicht drin. 
Optimierung hat darauf meist wenig Einfluss.

von Andreas K. (a-k)


Lesenswert?

> Wenn es so trivial wäre, wäre es auch bestimmt schon gemacht.

So schwierig dürfte es tatsächlich nicht sein. Jedenfalls nicht die 
reine Shiftoptimierung, die ich grad skizziert habe. Dazu muss man nur 
entsprechenden Code für die betreffenden Shiftoperationen einbauen.

Erheblich schwieriger ist es, Erkenntnisse, die von der Reihenfolge der 
Operationen her später gewonnen werden, in vorherige Operationen 
zurückwachsen zu lassen. Also zu erkennen, dass nur 8 Bits vom Ergebnis 
gebraucht werden, und dies nicht erst danach, sondern bereits in der 
Shiftoperation selbst zu berücksichtigen.

von Stefan Salewski (Gast)


Lesenswert?

>void rf_send(const uint32_t address) {

Könnte einer der C-Gurus vielleicht mal kurz erklären was hier das 
Attribut "const" bewirkt bzw. warum es notwendig ist? Ich kenne "const" 
eher in Verbindung mit Zeigern. Auf den ersten Blick würde ich denken, 
address ist ein konstanter 32-bit-Wert, d.h. dass nur Aufrufe wie 
rf_send(1), rf_send(2) usw. erlaubt sein sollen. Ist das gemeint?

Gruß

Stefan Salewski

von Philipp B. (philipp_burch)


Lesenswert?

@Andreas:

Die Änderung hat schon einiges bewirkt, vielen Dank!
1
96:         rf_sendspi((uint16_t)(address >> 16) >> 4);
2
+00000269:   01C8        MOVW    R24,R16          Copy register pair
3
+0000026A:   27AA        CLR     R26              Clear Register
4
+0000026B:   27BB        CLR     R27              Clear Register
5
+0000026C:   E0B4        LDI     R27,0x04         Load immediate
6
+0000026D:   9596        LSR     R25              Logical shift right
7
+0000026E:   9587        ROR     R24              Rotate right through carry
8
+0000026F:   95BA        DEC     R27              Decrement
9
+00000270:   F7E1        BRNE    PC-0x03          Branch if not equal
10
+00000271:   940E01EE    CALL    0x000001EE       Call subroutine
11
97:         rf_sendspi((uint16_t)(address >> 8) >> 4);
12
+00000273:   27BB        CLR     R27              Clear Register
13
+00000274:   2FA1        MOV     R26,R17          Copy register
14
+00000275:   2F90        MOV     R25,R16          Copy register
15
+00000276:   2D8F        MOV     R24,R15          Copy register
16
+00000277:   E0F4        LDI     R31,0x04         Load immediate
17
+00000278:   9596        LSR     R25              Logical shift right
18
+00000279:   9587        ROR     R24              Rotate right through carry
19
+0000027A:   95FA        DEC     R31              Decrement
20
+0000027B:   F7E1        BRNE    PC-0x03          Branch if not equal
21
+0000027C:   940E01EE    CALL    0x000001EE       Call subroutine
22
98:         rf_sendspi((uint8_t)(address >> 4));
23
+0000027E:   01D8        MOVW    R26,R16          Copy register pair
24
+0000027F:   01C7        MOVW    R24,R14          Copy register pair
25
+00000280:   E0E4        LDI     R30,0x04         Load immediate
26
+00000281:   95B6        LSR     R27              Logical shift right
27
+00000282:   95A7        ROR     R26              Rotate right through carry
28
+00000283:   9597        ROR     R25              Rotate right through carry
29
+00000284:   9587        ROR     R24              Rotate right through carry
30
+00000285:   95EA        DEC     R30              Decrement
31
+00000286:   F7D1        BRNE    PC-0x05          Branch if not equal
32
+00000287:   940E01EE    CALL    0x000001EE       Call subroutine

Ist noch nicht ideal, aber schon ein grosses Stück besser als mit den 20 
Schleifendurchläufen :)


EDIT: btw, kann es sein, dass der GCC den swap-Befehl nicht kennt? Damit 
liessen sich die Verschiebungen um 4 Bit wesentlich effizienter 
gestalten.

EDIT2: O1 und O2 machen unwesentlich grösseren Code, optimiert wird aber 
leider nicht besser.

von Andreas K. (a-k)


Lesenswert?

Wer sich dran versuchen will: In gcc\config\avr\avr.c sind dafür die 
Funktionen a/lshrqi3_out (8bit), -shrhi3_out (16bit) und -shrsi3_out 
(32bit) zuständig. Bei 8- und 16bit sind die meisten Shiftcounts 
handoptimiert, bei 32bit nur 8,16,24,31.

von Philipp B. (philipp_burch)


Lesenswert?

@Stefan:

"const" bewirkt hier, dass der Parameter in der Funktion nicht verändert 
werden kann. Das kann u.U. dem Compiler etwas bei der Optimierung 
helfen. Und es schliesst Fehlerquellen aus.

von Andreas K. (a-k)


Lesenswert?

> EDIT: btw, kann es sein, dass der GCC den swap-Befehl nicht kennt? Damit
> liessen sich die Verschiebungen um 4 Bit wesentlich effizienter
> gestalten.

Doch er kennt ihn. An genau dieser Stelle greift nun doch die vom 
Benedikt skizzierte Optimierungseinstellung, weil die Swap-Variante 
deutlich länger ist:
1
  mov r25,r17
2
  mov r24,r16
3
  clr r26
4
  clr r27
5
  swap r25
6
  swap r24
7
  andi r24,0x0f
8
  eor r24,r25
9
  andi r25,0x0f
10
  eor r24,r25

von Hagen R. (hagen)


Lesenswert?

Zugriffe auf 32Bit
1
typedef union {
2
  uint16_t word;
3
  struct {
4
    uint8_t a,b;
5
  };
6
} uint16_t_u;
7
8
typedef union {
9
  uint32_t dword;
10
  struct {
11
    uint8_t a,b,c,d;
12
  };
13
} uint32_t_u;
14
15
typedef union {
16
  uint32_t dword;
17
  struct {
18
    uint16_t a,b;
19
  };
20
} uint32_t_s;
21
22
#define L8(v)    (((uint16_t_u)v).a)
23
#define H8(v)    (((uint16_t_u)v).b)
24
25
#define L16(v)   (((uint32_t_s)v).a)
26
#define H16(v)   (((uint32_t_s)v).b)
27
28
#define LL8(v)   (((uint32_t_u)v).a)
29
#define LH8(v)   (((uint32_t_u)v).b)
30
#define HL8(v)   (((uint32_t_u)v).c)
31
#define HH8(v)   (((uint32_t_u)v).d)

also dann so
1
  rf_sendspi(HL8(RF_MyAddress));
2
  rf_sendspi(LH8(RF_MyAddress));
3
  rf_sendspi(LL8(RF_MyAddress));

das produziert den besten code unter gcc.

Dann Linksshift auf einem ATMega mit einem Shift größer als 1 immer als 
Multplikation machen, das ist im Durchschnitt schneller und kompakter.

Statt
1
  X = Y << i;
2
3
// also
4
  
5
  X = Y * PowerOf2[i];

Gruß Hagen

von Stefan Salewski (Gast)


Lesenswert?

Philipp Burch schrieb:

>"const" bewirkt hier, dass der Parameter in der Funktion nicht verändert
>werden kann. Das kann u.U. dem Compiler etwas bei der Optimierung
>helfen. Und es schliesst Fehlerquellen aus.

Ah ja, danke. Hatte ich wohl auch irgendwann mal gelesen aber wieder 
vergessen!

von Andreas K. (a-k)


Lesenswert?

> Dann Linksshift auf einem ATMega mit einem Shift größer als 1 immer als
> Multplikation machen, das ist im Durchschnitt schneller und kompakter.

Bei 32bit Operationen und nicht konstantem Faktor? Na wenn du meinst...

von Hagen R. (hagen)


Lesenswert?

probiers einfach aus, fertig.

Eine MUL benötigt 2 Takte, ein Links Shift des gleichen Bytes um I Bits 
benötigt 2 * i Takte minimal, ohne den Branch zu berücksichtigen.

Gilt logischerweise nur für Megas die eine HW-MUL unterstützen.
Normalerweise setzt man solche Optimierungen im Compiler voraus, sie 
sind Standard. Klar das dies für GCC nicht gelten kann, lebt dieser von 
der Eigenintiative ambtionierter Programmierer.

Ich denke das keiner hier GCC oder deren Entwickler angreifen möchte, 
esw geht einfach nur darum zu lernen was der GCC wann macht und was man 
als klein Hausmittelt so in seiner Apotheke hat um Kleinigkeiten besser 
machen zu können. Es ist wohl auch klar das man mit solchen Tricks die 
Kompatibilität des C Source aufhebt, auch dies ist logisch. (Nur um den 
vielen gutgemeinten Ratschlägen die auf solche Threads folgen 
vorzubeugen)

Gruß Hagen

von Benedikt K. (benedikt)


Lesenswert?

Andreas Kaiser wrote:
>> EDIT: btw, kann es sein, dass der GCC den swap-Befehl nicht kennt? Damit
>> liessen sich die Verschiebungen um 4 Bit wesentlich effizienter
>> gestalten.
>
> Doch er kennt ihn. An genau dieser Stelle greift nun doch die vom
> Benedikt skizzierte Optimierungseinstellung, weil die Swap-Variante
> deutlich länger ist:

Genau aus diesem Grund verwende ich immer O1 oder O2 und nie Os. Denn 
der Compiler versucht bei Os zwanghaft den kleinsten Code zu erzeugen. 
Das sind oftmals dumme Schleifen (wie auch hier), oder bei y=x/128 wird 
kein Shift verwendet, sondern die Divisionsroutine, da der Aufruf kürzer 
ist (vorausgesetzt die Routine wird wo anderst sowiso benötigt). Die 
Geschwindigkeitssteigerung liegt je nach Code bei bis zu >100%.

von Andreas K. (a-k)


Lesenswert?

Ok, stimmt auch bei 32bit, ist aber abhängig von der Shiftcount. Bei 
kleiner Shiftcount ist der Shift schneller als die Laufzeitfunktion zur 
Multiplikation.

von Philipp B. (philipp_burch)


Lesenswert?

@Hagen:

WTF, das ist wohl die ultimative Optimierung (Bitfelder und 
Multiplikation) :)
1
96:         rf_sendspi(HH8(address) * 0x0f | HL8(address) >> 4);
2
+0000026A:   E06F        LDI     R22,0x0F         Load immediate
3
+0000026B:   2ED6        MOV     R13,R22          Copy register
4
+0000026C:   9ED1        MUL     R13,R17          Multiply unsigned
5
+0000026D:   2D80        MOV     R24,R0           Copy register
6
+0000026E:   2411        CLR     R1               Clear Register
7
+0000026F:   2F90        MOV     R25,R16          Copy register
8
+00000270:   9592        SWAP    R25              Swap nibbles
9
+00000271:   709F        ANDI    R25,0x0F         Logical AND with immediate
10
+00000272:   2B89        OR      R24,R25          Logical OR
11
+00000273:   940E01EE    CALL    0x000001EE       Call subroutine
12
97:         rf_sendspi(HL8(address) * 0x0f | LH8(address) >> 4);
13
+00000275:   9ED0        MUL     R13,R16          Multiply unsigned
14
+00000276:   2D80        MOV     R24,R0           Copy register
15
+00000277:   2411        CLR     R1               Clear Register
16
+00000278:   2D9F        MOV     R25,R15          Copy register
17
+00000279:   9592        SWAP    R25              Swap nibbles
18
+0000027A:   709F        ANDI    R25,0x0F         Logical AND with immediate
19
+0000027B:   2B89        OR      R24,R25          Logical OR
20
+0000027C:   940E01EE    CALL    0x000001EE       Call subroutine
21
98:         rf_sendspi(LH8(address) * 0x0f | LL8(address) >> 4);
22
+0000027E:   9CDF        MUL     R13,R15          Multiply unsigned
23
+0000027F:   2D80        MOV     R24,R0           Copy register
24
+00000280:   2411        CLR     R1               Clear Register
25
+00000281:   2D9E        MOV     R25,R14          Copy register
26
+00000282:   9592        SWAP    R25              Swap nibbles
27
+00000283:   709F        ANDI    R25,0x0F         Logical AND with immediate
28
+00000284:   2B89        OR      R24,R25          Logical OR
29
+00000285:   940E01EE    CALL    0x000001EE       Call subroutine
30
99:         rf_sendspi((LL8(address) * 0x0f) | (HH8(RF_MyAddress) & 0x0f));
31
+00000287:   9CDE        MUL     R13,R14          Multiply unsigned
32
+00000288:   2D20        MOV     R18,R0           Copy register
33
+00000289:   2411        CLR     R1               Clear Register
34
+0000028A:   9180037E    LDS     R24,0x037E       Load direct from data space
35
+0000028C:   9190037F    LDS     R25,0x037F       Load direct from data space
36
+0000028E:   91A00380    LDS     R26,0x0380       Load direct from data space
37
+00000290:   91B00381    LDS     R27,0x0381       Load direct from data space
38
+00000292:   2F8B        MOV     R24,R27          Copy register
39
+00000293:   708F        ANDI    R24,0x0F         Logical AND with immediate
40
+00000294:   2B82        OR      R24,R18          Logical OR
41
+00000295:   940E01EE    CALL    0x000001EE       Call subroutine
42
100:        rf_sendspi(HL8(RF_MyAddress));
43
+00000297:   91800380    LDS     R24,0x0380       Load direct from data space
44
+00000299:   940E01EE    CALL    0x000001EE       Call subroutine
45
101:        rf_sendspi(LH8(RF_MyAddress));
46
+0000029B:   9180037F    LDS     R24,0x037F       Load direct from data space
47
+0000029D:   940E01EE    CALL    0x000001EE       Call subroutine
48
102:        rf_sendspi(LL8(RF_MyAddress));
49
+0000029F:   9180037E    LDS     R24,0x037E       Load direct from data space
50
+000002A1:   940E01EE    CALL    0x000001EE       Call subroutine
51
+000002A3:   E6C8        LDI     R28,0x68         Load immediate
52
+000002A4:   E0D3        LDI     R29,0x03         Load immediate

Der Code wird zwar absolut hässlich, aber das soll's mir an der Stelle 
wert sein. Hab' vielen Dank!

@Benedikt:

Leider bringt O2 auch an der Stelle nicht die gewünschte Verbesserung, 
da bereits keine Schleifen mehr existieren, die noch wegoptimiert werden 
könnten...


Und keine Sorge, ich habe nicht vor, den Code mit einem anderen Compiler 
zu kompilieren, daher kann ich schon solche "Hacks" machen.


EDIT:
Und hier noch die Variante mit einem "normalen" Shift:
1
96:         rf_sendspi(HH8(address) << 4 | HL8(address) >> 4);
2
+0000026A:   2F81        MOV     R24,R17          Copy register
3
+0000026B:   9582        SWAP    R24              Swap nibbles
4
+0000026C:   7F80        ANDI    R24,0xF0         Logical AND with immediate
5
+0000026D:   2F90        MOV     R25,R16          Copy register
6
+0000026E:   9592        SWAP    R25              Swap nibbles
7
+0000026F:   709F        ANDI    R25,0x0F         Logical AND with immediate
8
+00000270:   2B89        OR      R24,R25          Logical OR
9
+00000271:   940E01EE    CALL    0x000001EE       Call subroutine

Hat jemand Lust, die Zyklen zusammenzuzählen? ;D

von Hagen R. (hagen)


Lesenswert?

rf_sendspi(HH8(address) * 0x0f | HL8(address) >> 4);

ist aber nicht identisch zu

rf_sendspi(HH8(address) << 4 | HL8(address) >> 4);

du multiplizierst mit 0x0F = 15 statt mit 0x10 = 16 = 2^4.

In diesem Falle ist 2. Lösung aber effizienter !

Gruß Hagen

von Hagen R. (hagen)


Lesenswert?

>Ok, stimmt auch bei 32bit, ist aber abhängig von der Shiftcount. Bei
>kleiner Shiftcount ist der Shift schneller als die Laufzeitfunktion zur
>Multiplikation.

Laufzeitfunktion ? Einfache Miltiplikationen, zb. ein Byte * Byte werden 
auf einem Mega der eine HW-MUL hat direkt umgesetzt. Da wird keine 
Laufzeitbiliothek benötigt. Bei der Division ist das was anderes.

Das Beispiel aus diesem Thread arbeitet nicht mit 32Bit Zahlen sondern 
nur mit Bytes.

Normale Shifts die nicht 8,16,24 sind werden als simple Schleifen 
gebaut. Ein Byte kann maximal um +7 Bits geschoben werden. Da der GCC 
den Shiftwert nicht optimiert wird bei einem Variablen Shift im 
Durchschnitt der Wert 3 vorkommen, ergo 3*2 = 6 Takte. Im Gegensatz zu 2 
Takten ohne Branches bei der MUL.

Auch bei den Shift mit 8,16,24 arbeitet der GCC ineffizient. In diesem 
Falle fügt er unnötige CLR und MOV der selben Register ein.
Das ist aber nicht nur GCC spezifisch auch der Keil hat solche Sachen 
drauf.

Ok ich gebe zu das sind jetzt schon Tricks die ziemlich am Rande der 
sauberen Programmierung stehen und bei denen man sich die Frage stellen 
muß ob sie wirkich notwendig sind. Aber es zu wissen, das man noch was 
rausholen kann und den Compiler besser vesteht, hat auch seinen Wert.

Gruß Hagen

von Andreas K. (a-k)


Lesenswert?

> Laufzeitfunktion ?

Ich sprach ausdrücklich von 32bit Operationen. Da steckt zwar auch der 
MUL-Befehl dahinter, aber halt ein paar mehr davon.

von Hagen R. (hagen)


Lesenswert?

Ok, aber auch dann wäre die MUL schneller. Zb. ein 16 Bit um 2^5 
shifted. Als normale Schleife sind das 3 * 5 Takte, 3 Takte weil ja 2 
Bytes shift + 1 Takt Schleife. Per MUL würden 3 MULs ausreichen, also 6 
Takte statt 15.

Je größer der Datentypen je höher der Aufwand für die Schleife wie auch 
MUL, aber das Ratio veräöndert sich immer mehr zu Gunsten der MUL.

Gruß Hagen

von Philipp B. (philipp_burch)


Lesenswert?

Hagen Re wrote:
> rf_sendspi(HH8(address) * 0x0f | HL8(address) >> 4);
>
> ist aber nicht identisch zu
>
> rf_sendspi(HH8(address) << 4 | HL8(address) >> 4);
>
> du multiplizierst mit 0x0F = 15 statt mit 0x10 = 16 = 2^4.

Argh, Schande über mein Haupt. Du hast natürlich recht.

> In diesem Falle ist 2. Lösung aber effizienter !
>
> Gruß Hagen



Erstmal ein grosses Dankeschön für eure Vorschläge, so ist es jetzt kein 
Problem mehr. Ob eine Operation nun drei Takte länger dauert oder nicht 
ist mir ja eigentlich auch egal, aber wenn halt eine Schiebeoperation 
dermassen ineffizient erzeugt wird, dann bin ich schon froh um solche 
Optimierungen.

von Andreas K. (a-k)


Lesenswert?

Hagen Re wrote:

> Ok, aber auch dann wäre die MUL schneller.

Nochmal: 32 Bits. Zweiunddreissig. Nicht 8 Bits, nicht 16 Bit. Der 
Multiplikationsbefehl multipliziert aber nur 8x8=>16.

Die Libfcn enthält folglich 10 MULs und noch ein paar mehr ADD/ADCs, 
insgesamt ~48 Takte plus Overhead weil Funktionsaufruf statt 
Inline-Code. Die Schleife braucht 7 Takte/Iter, d.h. ab ungefähr n=8 
dürfte die Multiplikation im Vorteil sein.

von Hagen R. (hagen)


Lesenswert?

Hm, lass uns mal streiten ;)

eine 32Bit  8Bit MUL benötigt 4 8x8Bit MUL + 1 ADD + 2 ADC, nicht mehr 
und nicht weniger.

4*2 + 3 Takte also  macht 11 Takte, vorrausgesetzt wir vernachlässigen 
mal das Laden der Register, da dies bei beiden Methoden mit festen 
Overhead einhergeht.

Ein Shift über 4 Bytes benötigt 4 Takte + 1 Takt Spungbefehlt, macht 5 
Takte um 1 Bit zu schieben.

1 Bit = 5 Takte
2 Bit = 10 Takte
31 Bit = 155 Takte

5+10+...155 / 31 = 80 Takte im Durchschnitt. Also wenn man vorraussetzt 
das gleichverteilt im Bereich von 1 bis 31 Bits ein 32 Bit Wert links 
geschoben wird so belaufen sich die Kosten auf

Shiftloop = 80 Takte im Durchschnitt
MUL Methode = konstante 11 Takte

Na das nenn ich mal ein ordentliches Ratio, oder ?

Klar, wenn man C Source voraussetz und die auf Univeralität 
programmierte MUL Methode der Standardlib die nicht nur 32x8 Bit sondern 
auch 32x16 und 32x32 rechnen kann, dann sind das 48 Takte. Aber auch das 
ist besser als die 80 Takte mit Loops.

Wo ist jetzt mein Rechenfehler ?

Gruß Hagen

von Rolf Magnus (Gast)


Lesenswert?

> Wo ist jetzt mein Rechenfehler ?

Du hast für die Bitschieberei zuwenig Takte veranschlagt ;-)
Ein branch-Befehl braucht zwei Takte, wenn er springt. Macht also 6 
Takte pro geschobenem Bit, nicht 5. Beim letzten Durchlauf wird zwar 
nicht gesprungen, was einen Takt spart, aber den braucht man dafür dann 
zum Initialisieren des Schleifenzählers.

von Andreas K. (a-k)


Lesenswert?

Bis auf den Sprung nirgends. Jetzt sind wir beisammen. Ich schrieb, auf 
Basis der Libfunktion, dass kleine Shiftcounts drunter liegen. Du, dass 
die optimale aber nirgend realisierte Multiplikation ebenso wie die 
mittlere angenommene Shiftcount drüber liegen. Kein Widerspruch, stimmt 
beides.

Wenn wir weiter streiten wollen, dann allenfalls über die angenommene 
Gleichverteilung bei den Shiftcounts ;-).

von Hagen R. (hagen)


Lesenswert?

;)

Ok, das mit dem Branch stimmt. Und bei der MUL Methode müssen wir auf 
Grund der Eigenheiten das der AVR immer über Register r1:r0 geht wohl 
auch noch par Takte hinzurechnen, für die MOVW Opcodes, falls wir mehr 
als 8 Bit schieben wollen.

Auf alle Fälle benutze ich den MUL Trick immer dann wenn ich zb. in 
meinen Grafik Libraries oä. per Inline Assembler arbeite. Dieser Schritt 
ist eh kontraproduktiv aus Sicht der Portierbarkeit, also kann man auch 
solche Tricks da anwenden. Gerade bei Ausgabe von Bitmapfonts oder 
kodierten Bitmaps benötigt man oft Shifts. Als erstes baue ich die 
Datenformate immer so das ich mit Links Shifts auskomme statt mit Rechts 
Shifts. Dann kann ich später für die ATMega's das per MULs optimieren. 
Das macht dann schon einen großen Unterschied in der Performance aus, 
wenn zb. ein Fontzeichen 14x12 Pixel hat und pro Pixel shifted werden 
muß.

Oder bei sehr zeitkritischen ISRs. Dort ist es wünschenswert das die ISR 
sehr schnell arbeitet aber noch viel wichtiger das sie mit konstanten 
Taktanzahlen auskommt. Dh. die ISR soll immer die gleiche Taktanzahl 
besitzen um damit im Gesamtsystem besser berechnebar zu sein. Und die 
MUL Methode benötigt immer die gleiche Taktanzahl unabhängig wieviele 
Bits geschoben werden. Die Loop Methode logischerweise nicht.

Gruß Hagen

von Philipp B. (philipp_burch)


Lesenswert?

Da ist mir doch gleich noch eine Ungereimtheit aufgefallen:
1
121:          if (RPI_MISO & _BV(PIN_MISO)) *s_address |= (1UL << 24);
2
+000002CF:   9B1E        SBIS    0x03,6           Skip if bit in I/O register set
3
+000002D0:   C008        RJMP    PC+0x0009        Relative jump
4
+000002D1:   E040        LDI     R20,0x00         Load immediate
5
+000002D2:   E050        LDI     R21,0x00         Load immediate
6
+000002D3:   E060        LDI     R22,0x00         Load immediate
7
+000002D4:   E071        LDI     R23,0x01         Load immediate
8
+000002D5:   2AE4        OR      R14,R20          Logical OR
9
+000002D6:   2AF5        OR      R15,R21          Logical OR
10
+000002D7:   2B06        OR      R16,R22          Logical OR
11
+000002D8:   2B17        OR      R17,R23          Logical OR
12
+000002D9:   2F89        MOV     R24,R25          Copy register
13
+000002DA:   958A        DEC     R24              Decrement
14
+000002DB:   F7F1        BRNE    PC-0x01          Branch if not equal
Kann mir jemand erklären, was die Schleife dort am Ende soll? R25 
beinhaltet den Wert 2. Soll das eine etwas andere Variante darstellen um 
ein Register zu nullen? Warteschleife oder sowas hat's nicht in der 
Nähe.

EDIT: Und gleich nochwas: Was ist das Problem, wenn ich die Zeile so 
abändere?
1
if (RPI_MISO & _BV(PIN_MISO)) HH8(*s_address) |= 0x01;
Da haut mir der Compiler den Fehler "error: invalid lvalue in 
assignment" um die Ohren...

von Philipp B. (philipp_burch)


Lesenswert?

Oha, Kommando zurück. In der nächsten Zeile steht ja _delay_us(1) ich 
Idiot... Damit hat sich das Problem wohl erledigt. Warum aber die zweite 
Möglichkeit mit HH8() nicht funktioniert ist mir immer noch nicht ganz 
klar...

von Μαtthias W. (matthias) Benutzerseite


Lesenswert?

Hi

und was verbirgt sich hinter HH8()?

Matthias

von Philipp B. (philipp_burch)


Lesenswert?

Siehe den Beitrag von Hagen etwas weiter oben: 
Beitrag "Re: Bitshift schlecht implementiert?"

von Philipp B. (philipp_burch)


Lesenswert?

Niemand eine Idee, warum das nicht geht? Sind die Elemente einer Union 
schreibgeschützt oder so? Kaum, oder?
Ausserdem motzt er ja den lvalue an und da kommt doch eigentlich nur 
HH8(*s_address) rechts vom '=', sowie 0x01 in Frage. Was soll daran 
falsch sein?

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.