Hallo,
ich weiß dass es zu dem Thema schon unzählige Threads gibt. eigentlich
ist ein Ringbuffer ja auch eine einfache Sache aber irgendwie habe ich
gerade ein kleines Problem und komme nicht auf die Lösung.
Ich habe mir dazu auch den Artikel
https://www.mikrocontroller.net/articles/FIFO#FIFO_als_Bibliothek
angesehen.
und das erste Codebeispiel entspricht ziemlich genau dem was ich auch
selber geschrieben habe.
hier die Stelle aus dem Artikel
1
#define BUFFER_FAIL 0
2
#define BUFFER_SUCCESS 1
3
4
#define BUFFER_SIZE 23
5
6
structBuffer{
7
uint8_tdata[BUFFER_SIZE];
8
uint8_tread;// zeigt auf das Feld mit dem ältesten Inhalt
9
uint8_twrite;// zeigt immer auf leeres Feld
10
}buffer={{},0,0};
11
12
//
13
// Stellt 1 Byte in den Ringbuffer
14
//
15
// Returns:
16
// BUFFER_FAIL der Ringbuffer ist voll. Es kann kein weiteres Byte gespeichert werden
17
// BUFFER_SUCCESS das Byte wurde gespeichert
18
//
19
uint8_tBufferIn(uint8_tbyte)
20
{
21
//if (buffer.write >= BUFFER_SIZE)
22
// buffer.write = 0; // erhöht sicherheit
23
24
if((buffer.write+1==buffer.read)||
25
(buffer.read==0&&buffer.write+1==BUFFER_SIZE))
26
returnBUFFER_FAIL;// voll
27
28
buffer.data[buffer.write]=byte;
29
30
buffer.write++;
31
if(buffer.write>=BUFFER_SIZE)
32
buffer.write=0;
33
34
returnBUFFER_SUCCESS;
35
}
36
37
//
38
// Holt 1 Byte aus dem Ringbuffer, sofern mindestens eines abholbereit ist
39
//
40
// Returns:
41
// BUFFER_FAIL der Ringbuffer ist leer. Es kann kein Byte geliefert werden.
42
// BUFFER_SUCCESS 1 Byte wurde geliefert
43
//
44
uint8_tBufferOut(uint8_t*pByte)
45
{
46
if(buffer.read==buffer.write)
47
returnBUFFER_FAIL;
48
49
*pByte=buffer.data[buffer.read];
50
51
buffer.read++;
52
if(buffer.read>=BUFFER_SIZE)
53
buffer.read=0;
54
55
returnBUFFER_SUCCESS;
56
}
Nun aber zu der Frage, da beim
- Lesen des Speichers immer auf read==write (dann leer)
- beim Schreiben auf write+1=read (Vereinfach dargestellt, wegen dem
Überlauf, dann voll)
abgefragt wird, entsteht immer eine Zelle in die nicht geschrieben
werden kann.
bsp. read steht auf 5, write auf 4 es soll geschrieben werden, was aber
nicht ausgeführt wird da write+1 = read ist, somit kann die leere stelle
4 nicht beschrieben werden.
Wie kann man alle Stellen verwenden?
Bei nur einem Byte des Speichers wäre mir das relativ egal. aber da es
darum geht, jeweils eine struct mit viel speicher zu verwenden, so ist
es schon interessant wenn ich einen Speicher von z.B. 3
"Speicherplätzen" benötige ob ich dann wegen der eigenheit speicher für
4 zur Verfügung stellen muss.
Vielen Dank
verwirrt schrieb:> Wie kann man alle Stellen verwenden?
Die Belegung nicht über den Zeigervergleich machen, sondern separat
mitzählen, wie viele Elemente belegt sind.
verwirrt schrieb:> Wie kann man alle Stellen verwenden?
Gar nicht.
Das ist der Preis den man beim Ringpuffer für die Unabhängigkeit des
Lesers und Schreibers zahlt.
Ansonsten bräuchte man eine Semaphore, Mutex oder eine andere Art von
Locking.
Übrigens ist Dein Ringpuffer nicht interrupt-fest, wenn im C Compier der
Optimizer eingeschaltet wird. Die read und write Indizes müssten
volatile sein (jedenfalls der der im Interrupt verwendet wird).
uint8_tread;// zeigt auf das Feld mit dem ältesten Inhalt
6
7
uint8_twrite;// zeigt immer auf leeres Feld
8
9
}buffer={{},0,0};
und die Bedingung (write == read) als Buffer leer definiert ist,
dann kannst du nicht alle "Speicherstellen" nutzen.
Weil, wenn du nun doch ein weiteres Element speicherst, erhöhst du den
write und dann wäre er auf read was wieder bedeuten würde, Buffer leer
...obwohl er komplett voll wäre.
Du könntest natürlich deine Struktur erweitern:
1
structBuffer{
2
uint8_tdata[BUFFER_SIZE];
3
uint8_tread;// zeigt auf das Feld mit dem ältesten Inhalt
4
uint8_twrite;// zeigt immer auf leeres Feld
5
size_tlevel;// Anzahl der gespeicherten Daten/Bytes etc.
6
}buffer={{},0,0};
Dann würde die Logik nicht an write, read hängen, sondern an "level".
Ob das nun wirklich schöner/besser ist, mh...
Jim M. schrieb:> Gar nicht.
Unsinn.
> Das ist der Preis den man beim Ringpuffer für die Unabhängigkeit des> Lesers und Schreibers zahlt.
Die Frage ist, ob man die im konkreten Fall überhaupt braucht.
> Ansonsten bräuchte man eine Semaphore, Mutex oder eine andere Art von> Locking.
Nur, wenn der Zugriff aus zwei verschiedenen Kontexten stattfinden. z.
B. Interrupt + Hauptschleife oder von zwei verschiedenen CPUs aus.
Bau Buffer_In() doch so um, das write immer auf das letzte beschriebene
Feld zeigt. Dann muss eigentlich nur buffer.write++; früher ausgefhürt
werden und alles andere kann so bleiben.
verwirrt schrieb:> Wie kann man alle Stellen verwenden?
Wie schon mehrfach beantwortet, mit mehr Aufwand. Aber grade der sollte
in der Bibliothek vermieden werden, Geschwindigkeit war oberste
Priorität. In der Praxis spielt die eine ungenutzte Speicherzelle keine
Rolle, wenn man nicht gerade einen FIFO mit 10kB structs anlegt.
um es nochmal kurz zu erwähnen, das Beispiel stammt nicht von mir,
sondern hier aus dem wiki :)
Das mit dem Threadsave ist mir bewust, ich weiß aber in diesem Fall
nicht was schief gehen soll, der read (nicht im Interrupt) würde im
schlimmsten Fall unterbrochen werden und hätte trotz ausgelesenem Wert
den readzeiger nicht hochgezählt, was nach dem zurückkehren aus dem
(write) Interrupt fortgesetzt werden würde. ok, das hieße das bei vollem
Buffer nicht geschrieben werden könnte. Das gilt natürlich nur unter der
Vorraussetzung dass das schreiben des Readzeigers (als Teil des
Incements) Atomar sein muss.
Ich würde immer einen Zähler mitlaufen lassen.
Denn bei mir kommt es öfter vor, dass ich später auch die Anzahl wissen
möchte. Dann hat sich das gleich damit erledigt.
verwirrt schrieb:> abgefragt wird, entsteht immer eine Zelle in die nicht geschrieben> werden kann.
... dann überdenke mal deine write/in Funktion!
Beispiel:
uint8_t writeBuf(irNEC_t *data) {
if (!((irBuf->r + 1 - irBuf->w) % (uint8_t) IR_BUF_SIZE)) return 0;
//full
irBuf->data[irBuf->w++] = *data;
if (irBuf->w >= IR_BUF_SIZE) irBuf->w = 0;
return 1;
}
PittyJ schrieb:> Ich würde immer einen Zähler mitlaufen lassen. Denn bei mir kommt es> öfter vor, dass ich später auch die Anzahl wissen möchte. Dann hat sich> das gleich damit erledigt.
Meistens lohnt der Aufwand nicht, zumindest wenn bytebuffer verwendet
werden:
Speicher spart man nicht, die Anzahl kann auch so schnell berechnet
werden. Und man hat einen Zähler, der in beiden Tasks beschrieben wird.
Meist ist nur dafür ein Lock notwendig, alle anderen werden in einem
Teil nur gelesen.
PittyJ schrieb:> Ich würde immer einen Zähler mitlaufen lassen.> Denn bei mir kommt es öfter vor, dass ich später auch die Anzahl wissen> möchte. Dann hat sich das gleich damit erledigt.
Ist aber in Summe langsamer.
[Bezieht sich auf Anwendungen, wo eine Seite in einer ISR läuft]
Der Vorteil dieser Art Ringspeicher ist, dass sie, selbst ohne atomares
inc/dec, Lock-less funktionieren. Jeweils eine Seite ändert den Index,
die andere liest ihn nur[1].
Führt man einen zusätzliches Datum ein (full-flag/counter), kommt man
üblicherweise um Locks nicht herum - beide Seiten ändern das gleiche
Feld, mehrere Felder müssen konsistent gehalten werden.
foobar schrieb:> Der Vorteil dieser Art Ringspeicher ist, dass sie, selbst ohne atomares> inc/dec, Lock-less funktionieren. Jeweils eine Seite ändert den Index,> die andere liest ihn nur[1].
Nö, das geht auch nicht, denn die Indices bzw. Pointer sind nicht
zwingend atomar! Nur wenn deine CPU atomare Zugriffe auf die beteiligten
variablen OHNE Zusatzmaßnahmen in Software GARANTIERT, geht es ohne
Verriegelung (neudeutsch Lock)
Falk B. schrieb:> Nur wenn deine CPU atomare Zugriffe auf die beteiligten> variablen OHNE Zusatzmaßnahmen in Software GARANTIERT
Interessant!
Ich ging bisher immer davon aus, dass uint8 immer atomar funktioniert.
Meine eigene Ringbuffer-Implementierung, die ich privat seit Jahren auf
verschiedensten Systemen nutze, definiert Leser und Schreiber mit
unsigned int, sodass je nach System eine 8-16-32Bit breite Variable
angelegt wird, die dann auch auf jedem Targetatomar
inkrementiert/dekrementiert.
Denkfehler oder Wissenslücke meinerseits?
Iwo schrieb:> Ich ging bisher immer davon aus, dass uint8 immer atomar funktioniert.
Nur, wenn die Architektur überhaupt uint8_t im RAM zugreifen kann.
Das können nicht alle.
Mache lesen bei einem 8-Bit Schreibzugriff ein ganzes Maschinenwort,
manipulieren das Byte und schreiben das Wort zurück.
> denn die Indices bzw. Pointer sind nicht zwingend atomar!
Das setze ich als gegeben aus - load und store müssen atomar sein. Die
Read-modify-write-Instruktionen aber nicht.
Iwo schrieb:> Interessant!>> Ich ging bisher immer davon aus, dass uint8 immer atomar funktioniert.
Mag sein, aber sind deine Pointer uint8_t? Oder deine Indices? Im
Spezialfall ja, allgemein NEIN!
> Meine eigene Ringbuffer-Implementierung, die ich privat seit Jahren auf> verschiedensten Systemen nutze,
Was nicht bedeutet, daß deine Implementierung wasserdicht ist. Du kannst
auch sehr lange viel Glück haben.
> definiert Leser und Schreiber mit> unsigned int,
Wer ist Leser und Schreiber?
> sodass je nach System eine 8-16-32Bit breite Variable> angelegt wird, die dann auch auf jedem Targetatomar> inkrementiert/dekrementiert.
Wer sagt das daß immer atromar ist?
> Denkfehler oder Wissenslücke meinerseits?
Möglichweweise beides. Aber ohne konkreten Code ist das eher schwer
diskutierbar.
foobar schrieb:>> denn die Indices bzw. Pointer sind nicht zwingend atomar!>> Das setze ich als gegeben aus
Schon mal ein Fehler!
>- load und store müssen atomar sein.
Das ist weniger das Problem, wenn gleich auch das groß genug ist.
> Die> Read-modify-write-Instruktionen aber nicht.
Aha. Und wie paßt das dann mit deiner Aussage zusammen?
"
[Bezieht sich auf Anwendungen, wo eine Seite in einer ISR läuft]
Der Vorteil dieser Art Ringspeicher ist, dass sie, selbst ohne atomares
inc/dec, Lock-less funktionieren. Jeweils eine Seite ändert den Index,
die andere liest ihn nur[1]."
Au0erdem, was meinst du mit "dieser Art Ringspeicher"?
kannAllesBesser! schrieb:> uint8_t writeBuf(irNEC_t *data) {> if (!((irBuf->r + 1 - irBuf->w) % (uint8_t) IR_BUF_SIZE)) return 0;
struct {uint8_t r, w; irNEC_t data[IR_BUF_SIZE];} fifo, *irBuf = &fifo;
verwirrt schrieb:> abgefragt wird, entsteht immer eine Zelle in die nicht geschrieben> werden kann.
Zur Prüfung durch die vielen "Experten" hier ...
Es gibt keine ungenutzte Belegung im Circular Buffer und benötigt auch
keinen extra Zähler.
kannAllesBesser! schrieb:> Zur Prüfung durch die vielen "Experten" hier ...> Es gibt keine ungenutzte Belegung im Circular Buffer und benötigt auch> keinen extra Zähler.
Doch. Wenn Du %BUFSIZE rechnest, hast Du nur BUFSIZE Zahlen. Und damit
kannst Du nicht BUFFSIZE Elemente PLUS 0 zählen.
Oder Du packst das mal in einen zusammenhängenden Code.
Iwo schrieb:> sodass je nach System eine 8-16-32Bit breite Variable> angelegt wird, die dann auch auf jedem Targetatomar> inkrementiert/dekrementiert.
Abgesehen davon, dass int nicht 8 Bit sein dürfte: Ja, wenn es atomar
ist, geht das wasserdicht. Wenn Zweifel bestehen (zumal mit %), dann
halt einen Wrapper (bzw. je einen für Lesen und Schreiben) drum, der auf
"atomaren" Plattformen zu nix zerfällt. Oder wenn klar ist, wer wen
unterbricht (Interrupt die Main-Task), dann geht es auch ohne Lock
sauber.
Also z.B. 2 Funktionen für Lesen und schreiben: Je ein Paar für
Schreiben im Interrupt und lesen im Main und umgekehrt.
>>> denn die Indices bzw. Pointer sind nicht zwingend atomar!>>>> Das setze ich als gegeben voraus>> Schon mal ein Fehler!>>>- load und store müssen atomar sein.>> Das ist weniger das Problem, wenn gleich auch das groß genug ist.
Natürlich geht das nicht mit jedem beliebigen Datentyp. Man wählt den
Typ der Indizes extra so, dass sie atomar gelesen und geschrieben
werden. Fertig. Evtl ergeben sich dadurch Einschränkungen (z.B. max
256-Byte-Buffer). Und jetzt komm bitte nicht mit "aber wenn es keinen
gibt" ...
>> Die Read-modify-write-Instruktionen aber nicht.>> Aha. Und wie paßt das dann mit deiner Aussage zusammen?>> "Der Vorteil dieser Art Ringspeicher ist, dass sie, selbst ohne atomares> inc/dec, Lock-less funktionieren. [...]"
Increment/decrement sind read-modify-write Instruktionen: load memory,
increment, store memory - da darf jeweils beliebig Zeit zwischen
vergehen, dürfen Interrupts ausgeführt werden, selbst schlafen ist
erlaubt[2]. Einzig load und store müssen atomar sein - was kein Problem
ist.
> Außerdem, was meinst du mit "dieser Art Ringspeicher"?
So einen, wie er im Eingang gezeigt wurde[1]: Nur ein Schreib- und ein
Lese-Index, ein unbenutzes Element im Buffer zur Unterscheidung zwischen
leer (w==r) und voll (w+1==r), keine zusätzlichen Flags, Zähler, etc.
[1] Eine Sache macht ihn nicht-IRQ-fest: die Modulo-Checks schreiben
evtl erstmal einen ungültigen Index und korrigieren anschließend - ist
aber ein Implementationsfehler, kein prinzipieller.
[2] Als Beispiel ein Ausschnitt aus meinen UART-Routinen: schau mal,
wann txw gelesen, erhöht und geschrieben wird.
Jim M. schrieb:> Übrigens ist Dein Ringpuffer nicht interrupt-fest, wenn im C Compier der> Optimizer eingeschaltet wird. Die read und write Indizes müssten> volatile sein (jedenfalls der der im Interrupt verwendet wird).
kurze frage dazu, ja ich habe das in meinem richtigen code schon mit
volatile, aber ebend nur weil das halt irgendwann mal so gesagt wurde.
Die Frage die sich mir stellt, ist das wirklich nötig?
soweit ich das verstanden habe ist volatile (frei nach mir) die Angabe
an den Compiler, Achtung diese Variable kann außerhalb deines
Sichbereichs geändert werde, also nicht wegoptimieren, nicht im speicher
behalten.
Dieses trift imho dann zu wenn z.B. auf eine Variable mittels extern
zugegriffen wird.
Aber in dem Beispiel hier ist es ja so, das der Compiler innerhalb einer
(.c) Datei "sieht" das die Modulglobale (static) Variablen buffer.write
bzw buffer.read in verschiedenen Funktionen verwendet werden.
Warum also sollte der Compiler hier egal in welcher Optimierungsstufe
etwas bei dem Zugriff auf die Variable tun?
verwirrt schrieb:> Dieses trift imho dann zu wenn z.B. auf eine Variable mittels extern> zugegriffen wird.
Nein, überhaupt nicht.
Es geht bei der Überlegung darum, dass im Maschinenmodell der C-Sprache
es kein Multithreading und keine Interrupts gibt.
Der Compiler kann also annehmen, dass alle Funktionen nacheinander, in
welcher Anordnung auch immer, aufgerufen werden. Aber niemals parallel
laufen können.
Wenn du dann in einer Funktion hintereinander
1
a += 1
2
b += 1
3
a -= 1
machst, dann darf der Compiler die Operationen auf a komplett verwerfen.
Das kann natürlich in der Praxis fatal sein, wenn zwischen den
a-Operationen etwas anderes laufen darf.
Das ist nur ein Beispiel. Optimierungsmöglichkeiten hat der Compiler
noch viel mehr.
Deshalb: Wenn eine Variable in einem Interrupt irgendwie angefasst wird
(auch lesend!), dann volatile.
ja richtig innerhalb einer Funktion darf der compiler Schritte
optimieren, weglassen etc. aber beim einstieg in die Funktion darf er
doch wohl nicht davon ausgehen das die Variable den gleichen Wert hat
wie vor 3 Wochen als die Funktion das letzte mal durchlaufen wurde.
in dem Fall Ringbuffer wird ja jeweils nur lesend auf die Variablen
zugegriffen
bsp:
es wird die readfunktion von der writefunktion unterbrochen
read()
{
lese buffer.write in register
INTERRUPT
write()
{
buffer.write++
}
INTERRUPT ende
bewerte buffer.write in register (um 1 niedriger als in der
buffer.write)
lese ggf Buffer Stelle Aus
buffer.read++
}
ich hoffe es ist ungefähr ersichtlich wie das gemeint ist.
an welcher Stelle würde der Compiler denn hier etwas wegoptimieren
können?
Es geht nicht darum das ich kein volatile da hin schreiben will, sondern
dass ich verstehen will an welcher Stelle das passiert.
oder anders gefragt bei dem Beispiel oben
1
a+=1
2
b+=1
3
a-=1
was würde es für einen Unterschied machen ob es static uint8_t a oder
volatile static uint8_t a wäre?
verwirrt schrieb:> was würde es für einen Unterschied machen ob es static uint8_t a oder> volatile static uint8_t a wäre?
static uint8_t a
global scope, könnte nach einmal lesen, die ganze weitere zeit in einem
register gehalten werden oder auch nur abschnittsweise ohne neu
einlesen.
volatile static uint8_t a
global scope, muss IMMER neu eingelesen werden, kann also nicht
"zwischen gespeichert" werden.
verwirrt schrieb:> ich hoffe es ist ungefähr ersichtlich wie das gemeint ist. an welcher> Stelle würde der Compiler denn hier etwas wegoptimieren können?
Du hast Recht, dass gewisse Kombinationen kein volatile erfordern. Aber
genau dann schadet es meist nicht, weil der Zugriff dann meist nur
einmalig erfolgt.
Die Analyse (nötig/nicht nötig) ist zu selten wirklich umfassend, meist
fehlerhaft und mit der kleinsten Änderung obsolete.
verwirrt schrieb:> aber beim einstieg in die Funktion darf er> doch wohl nicht davon ausgehen das die Variable den gleichen Wert hat> wie vor 3 Wochen als die Funktion das letzte mal durchlaufen wurde.
Doch darf er!
Denn schließlich weiß er genau, welche Register verändert wurden, in den
letzten 3 Wochen.
Zudem macht er ja auch Funktionen inline, von denen man es nie erwarten
würde.
Arduino Fanboy D. schrieb:> Doch darf er!> Denn schließlich weiß er genau, welche Register verändert wurden, in den> letzten 3 Wochen.> Zudem macht er ja auch Funktionen inline, von denen man es nie erwarten> würde.
Das gilt (wenn überhaupt) nur für C++.
In C muss eine "ganz normale" Funktion (void foo(void)) damit rechnen,
von irgendwoher aufgerufen zu werden. Und kann nicht annehmen, dass
irgendetwas genauso war wie beim letzten mal.
A. S. schrieb:> In C muss eine "ganz normale" Funktion (void foo(void)) damit rechnen,> von irgendwoher aufgerufen zu werden. Und kann nicht annehmen, dass> irgendetwas genauso war wie beim letzten mal.
Ein kleiner Test, würde dir das Gegenteil beweisen!
OK, kannst du nicht...
Dann zeige ich es dir:
Eine ganz normale *.c Datei, etwas minimalistisch, ok
1
voidinit()
2
{
3
DDRB|=_BV(PB5);
4
}
5
6
intmain()
7
{
8
init();
9
for(;;);
10
}
Der Compiler Output, etwas gekürzt:
1
0000007c<__bad_interrupt>:
2
7c:0c940000jmp0;0x0<__vectors>
3
4
00000080<main>:
5
6
voidinit()
7
{
8
DDRB|=_BV(PB5);
9
80:259asbi0x04,5;4
10
}
11
12
intmain()
13
{
14
init();
15
for(;;);
16
82:ffcfrjmp.-2;0x82<main+0x2>
17
18
00000084<_exit>:
19
84:f894cli
20
21
00000086<__stop_program>:
22
86:ffcfrjmp.-2;0x86<__stop_program>
Wie man sieht, hat es die Funktion init() inline gemacht, obwohl du
sagst, das darf er nicht.
Natürlich kann man in einem Ringpuffer alle Elemente benutzen. Der Trick
ist, die Zähler nicht bis BUFFSIZE sondern bis 2*BUFFSIZE laufen
zulassen und erst dann umzubrechen.
Die Füllmenge des Puffers ist dann: (write < read)? (write-read +
2xBUFFSIZE) : (write-read) Für den Index muss man dann rechnen: (read >
=BUFFSIZE) ? (read - BUFFSIZE) : (read).
Wenn die Elementzahl ne Zweierpotenz ist, dann kann man den Index
einfach read%BUFFSIZE und den Füllstand (write-read)%(2*BUFFSIZE)
rechnen.
Die Read/Write Zähler sollten (/müssen) als "volatile" deklariert werden
außerdem sollten diese der native Datenbreite der CPU entsprechen
(Kleiner geht außer bei bestimmten Architekturen auch).
Arduino Fanboy D. schrieb:> Wie man sieht, hat es die Funktion init() inline gemacht, obwohl du> sagst, das darf er nicht.
Zeig doch mal die Compileroptionen. Denn eigentlich darf er das wirklich
nicht, ich vermute mal es es ist "-funit-at-a-time" oder ähnliches
gesetzt.
Dafür
Arduino Fanboy D. schrieb:> Andreas M. schrieb:>> Compileroptionen.
Na dann schau doch mal was "-flto" bewirkt. Und disambliere mal das .o
file und nicht das ".elf" bzw vergleiche die beiden mal...
Kleiner Tip: Es ist nicht der Compiler der init() wegoptimiert, sondern
der Linker.
Andreas M. schrieb:> Kleiner Tip: Es ist nicht der Compiler der init() wegoptimiert, sondern> der Linker.
Ich weiß!
bzw, kann schon sein...
Tut aber nichts zur Sache.
Oder möchtest du mir sagen, dass LTO irgendwie verwerflich ist?
PS:
Habe mir mal den Spaß gegönnt und die ganzen LTO Options entfernt
Das Ergebnis ist exakt das gleiche.
init() wird inline eingebunden.
> was "-flto" bewirkt.
Habe geschaut.
Resultat: In diesem Fall wirkungslos.
(so wie ich es auch erwartet habe)
Arduino Fanboy D. schrieb:> Andreas M. schrieb:>> Kleiner Tip: Es ist nicht der Compiler der init() wegoptimiert, sondern>> der Linker.> Ich weiß!> bzw, kann schon sein...> Tut aber nichts zur Sache.>> Oder möchtest du mir sagen, dass LTO irgendwie verwerflich ist?
Nein, es ging darum das Du behauptest hast:
Arduino Fanboy D. schrieb:> A. S. schrieb:>> In C muss eine "ganz normale" Funktion (void foo(void)) damit rechnen,>> von irgendwoher aufgerufen zu werden. Und kann nicht annehmen, dass>> irgendetwas genauso war wie beim letzten mal.> Ein kleiner Test, würde dir das Gegenteil beweisen!
Was falsch ist. Ein C-Compiler, genauso wie ein C++ Compiler oder ein
Fortran Compiler oder ... MUSS eine nicht statisch oder inline markierte
Funktion als global verfügbares Symbol in einer Objektdatei ablegen.
Eben damit dieses Symbol aus einer anderen Objekt Datei heraus gebunden
werden kann. Und damit darf der Compiler auch keine Annahmen bezüglich
des Aufrufs der Funktion treffen, da er gar nicht wissen kann wer, wann
oder ob überhaupt die Funktion aufgerufen werden wird.
Der C-Standard geht sogar noch weiter: Selbst wenn in einer C-Datei zwei
Funktion mit exakt dem gleichen Code aber unterschiedlichem Namen
definiert sind, muss der C-Compiler daraus zwei unterschiedliche
Symboladressen generieren. Er darf im allgemeinen nicht beide Symbole
auf die gleiche Zieladresse zeigen lassen. ISO C99 Abschnitt 6.5.9.6
Pointervergleiche gilt auch für Funktionspointer. Es gibt darüber in den
gcc, clang mailinglisten diverse Diskussionen.
Der Compiler wird es bei Optimierung so lösen, dass er an der
Symboladresse der zweiten Funkion ein Sprung auf den Einsprungpunkt der
ersten legt oder ein NOP einfügt. Hier mal als Beispiel:
https://godbolt.org/z/oMfbq5
LTO ist jedoch etwas völlig anderes. Bei LTO interessiert sich der
Linker überhaupt nicht für den vom Compiler erzeugten Objektcode, Statt
dessen nimmt er die ganzen IR Bäume aus den mit LTO Flag kompilierten
Objektdateien und optimiert diese in ihrer Gesamtheit unter der Annahme
das es exakt ein extern sichtbares Symbol gibt ( bei AVR die
Vektortabelle, bei einem "PC" Programm die main() Funktion. Dann kann
der Linker natürlich eine ganze Menge mehr Annahmen machen, denn er
kennt das komplette Program. Damit kann der Linker dann den Code viel
weiter optimieren als es der C-Compiler alleine könnte, denn er "weis"
nun ganz genau wann und wo welche Funktion wie oft aufgerufen wird oder
ob diese überhaupt verwendet wird.
Effektiv gesehen ist LTO nichts anders als den gesamten Quellcode in
eine einzige Datei zu schreiben, alle Deklarationen statisch zu machen
(Bis auf main oder der Vektortabelle) und diese eine C Datei in den
Compiler zu Füttern
Arduino Fanboy D. schrieb:> PS:> Habe mir mal den Spaß gegönnt und die ganzen LTO Options> entferntcompiler.c.flags=-c -g -Os {compiler.warning_flags} -std=gnu11> -ffunction-sections -fdata-sections -MMD> compiler.c.elf.flags={compiler.warning_flags} -Os -g -Wl,--gc-sections> Das Ergebnis ist exakt das gleiche.> init() wird inline eingebunden.>>> was "-flto" bewirkt.> Habe geschaut.> Resultat: In diesem Fall wirkungslos.> (so wie ich es auch erwartet habe)
Klar, der Compiler darf natürlich selbständig inlinen, aber er muss
init() trotzdem als Objekt anlegen. Das Du das Symbol am Ende nicht
siehst liegt an "-ffunction-sections -fdata-sections" welches bewirkt,
dass das zusätzliche, extern sichtbare init in einer eigenen Section
landet, welche wiederum der Linker entsorgt, da init() nicht weiter
verwendet wird.
Andreas M. schrieb:> Dann kann> der Linker natürlich eine ganze Menge mehr Annahmen machen, denn er> kennt das komplette Program. Damit kann der Linker dann den Code viel> weiter optimieren als es der C-Compiler alleine könnte,
Genau genommen ist’s auch bei lto der Compiler, der das alles macht.
Link-time optimization ist da etwas irreführend.
Oliver
Oliver S. schrieb:> Genau genommen ist’s auch bei lto der Compiler, der das alles macht.> Link-time optimization ist da etwas irreführend.
Ich denke es heißt so, weil die "große" Optimierung dann während des
Aufrufs des Linkers passiert, am Ende steht dann ja das ausführbare
Programm. Das der im Hintergrund dann wieder Teile des Compilers
aufruft...klar. Wobei man bei clang/llvm Compiler und Linker sowieso
nicht mehr so ohne weiteres trennen kann, letzlich benutzen beide die
gleiche Bibliothek im Hintergrund.
Andreas M. schrieb:> Was falsch ist. Ein C-Compiler, genauso wie ein C++ Compiler oder ein> Fortran Compiler oder ... MUSS eine nicht statisch oder inline markierte> Funktion als global verfügbares Symbol in einer Objektdatei ablegen.> Eben damit dieses Symbol aus einer anderen Objekt Datei heraus gebunden> werden kann. Und damit darf der Compiler auch keine Annahmen bezüglich> des Aufrufs der Funktion treffen, da er gar nicht wissen kann wer, wann> oder ob überhaupt die Funktion aufgerufen werden wird.
interessant... wo finde ich das im C++ Standard?
verwirrt schrieb:> Wie kann man alle Stellen verwenden?> Bei nur einem Byte des Speichers wäre mir das relativ egal. aber da es> darum geht, jeweils eine struct mit viel speicher zu verwenden, so ist> es schon interessant wenn ich einen Speicher von z.B. 3> "Speicherplätzen" benötige ob ich dann wegen der eigenheit speicher für> 4 zur Verfügung stellen muss.
Also, du willst partout mit dem Kopf durch die Wand, ohne mal eine
Fallunterscheidung in Erwägung zu ziehen.
Selbige würde ich allerdings als Allererstes tun:
a) Wenn du einen klassischen Fall für einen Ringpuffer hast, also viele
Bytes zum Drucken oder sowas ähnliches, dann schert dich ein unbenutztes
Byte schlichtweg garnicht.
b) wenn du hingegen nur ganz wenige Elemente hast, diese dafür aber groß
sind (wie dein Beispiel mit dem Array aus 3 Struct's), dann ist ein
Ringpuffer einfach nur fehl am Platze.
Dort macht man es sinnvollerweise anders, indem man jedem Struct ein
Zähl- bzw. Alters-Byte hinzufügt. Die schreibende Instanz (z.B. ISR)
sucht in dem Array nach einem Eintrag, der als leer markiert ist. Findet
sie einen, dann sucht sie nach dem größten Altersbyte, versieht den
neuen Struct mit einem um 1 erhöhten Altersbyte und schreibt dann den
neuen Struct an die leere Stelle. Findet sie keine leere Stelle, dann
entweder "FAIL" oder irgend etwas intelligenteres deiner Wahl.
Die lesende Instanz sucht im Array nach dem Eintrag mit dem kleinsten
Altersbyte, liest es aus, und dann numeriert sie alle anderen Einträge
neu durch, vom kleinsten beginnend. Dann wird der ausgelesene Eintrag
als ungültig erklärt, z.B. ne 0 als Altersbyte hinein geschrieben.
Bei diesem Vefahren kann es Lücken im Zählbyte geben, aber die sind
egal, da es ja nur drauf ankommt, die Reihenfolge zu bewahren. Ebenso
ist es egal, ob da nun alles atomar erfolgt, weil bei diesem Verfahren
keine Instanz der anderen dazwischenschreibt.
W.S.
Andreas M. schrieb:> Nein, es ging darum das Du behauptest hast:>> ....>> Was falsch ist. Ein C-Compiler, genauso wie ein C++ Compiler oder ein> Fortran Compiler oder ... MUSS eine nicht statisch oder inline markierte> Funktion als global verfügbares Symbol in einer Objektdatei ablegen.
Nun, dabei habe ich doch gar keine Aussagen, zu Objekt Dateien, gemacht.
Interessiert mich auch nicht sonderlich.
Das, was ins Flash gebrannt wird, das macht die Musik.
Bisher waren die Irrtümer ehr auf deiner Seite!
1. darf nicht inline machen - tut es aber
2. -funit-at-a-time - has no effect
3. LTO machts inline - hat in dem Beispiel keine Wirkung
Natürlich muss die Toolchain Wissen darüber haben (ob Compiler oder
Linker ist mir dabei egal), welche Register in Nutzung sind, und welche
nicht, denn sonst könnte es ja gar nicht dessen Nutzung optimieren.
Aber wenn es dich glücklich macht:
Ja, du hast in allem recht.
Immer.
So uns jetzt ziehe weiter und suche dir einen anderen den du für blöd
erklären kannst.
Bei mir hast du es ja jetzt geschafft.
Meinen herzlichen Dank dafür.
@ Arduino Fanboy D.
Ich finde es, schade, dass es am Ende immer so ausarten muss. Ohne jetzt
da die Art der Auseinandersetzung bewerten zu wollen, fand ich die
Ausführungen von Andreas M. wie Compiler/Linker arbeiten rein inhaltlich
schon interessant (auch wenn am Ende natürlich gilt "Wichtig is' aufm
Platz" also was geflasht wird).
Jörg schrieb:> Ich finde es, schade, dass es am Ende immer so ausarten muss.
Ich weiß gar nicht, was du willst...
Die mir weit überlegende Fachkompetenz des Andreas M. habe ich neidlos
anerkannt und mich sogar für den ungerechtfertigten Einlauf bedankt.
Ein mehr an Demut kann ich nicht leisten....
Tiefer komme ich nicht runter.
Es war vielleicht falsch von mir, das mit dem Inhaltlichen auf Andreas
M. beschränkt zu haben.
Ich habe jedenfalls von Euch beiden was gelernt. Danke dafür (das meine
ich ohne jegliche Ironie) und ich hoffe, dass solche Diskussionen auch
in Zukunft noch geführt werden. Und jetzt kann der Thread hoffentlich in
Frieden ruhen ...
verwirrt schrieb:> Wie kann man alle Stellen verwenden?
Das Problem ist, dass (read_index == write_index) dann mehrdeutig wird -
entweder der Puffer ist randvoll oder leer. Diese Mehrdeutigkeit musst
du vermeiden. Dazu genügt ein Flag, welches angibt, ob der letzte
Zugriff lesend oder schreibend war. Man kann auch einen Zähler mitlaufen
lassen.
Der Haken ist, dass Zähler oder Flag von beiden Seiten benutzt werden,
also ein Lock brauchen.
foobar schrieb:> Einzig load und store müssen atomar sein - was kein Problem ist.
Erstens: Wenn nur load/store atomar sind, aber das inc/dec nicht, dann
funktioniert der Puffer nur mit genau einem Producer und genau einem
Consumer. Das solltest du erwähnen.
Zweitens: Wenn der Compiler das Alignment deiner Variablen nicht
garantieren kann, sind load/store möglicherweise auf keinem Datentypen
atomar. Das ist mir mal sehr böse auf die Füße gefallen.
Arduino Fanboy D. schrieb:> den ungerechtfertigten Einlauf
Die Aussagen von Andreas waren alle sachlich, nicht persönlich. Also gab
es auch keinen Einkauf, für niemanden.
Unsachlich wurde es an anderer Stelle und nicht von Andreas.
Also bitte bleib bei der Sache ;)