mikrocontroller.net

Forum: Compiler & IDEs Ringpuffer vs Linkedlist


Autor: Alexander Poddey (alexatmikro)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
ich habe daten, die manchmal per irq schlagartig anfallen, und 
langfristig über uart weggeschickt werden müssen. da die uart verbindung 
ggf. unterbrochen sein kann, hab ich bisher eine linked-list 
programmiert, die dynamisch wachsen kann (vom irq handler gefüllt), und 
von oben abgearbeitet wird, sobald zeit dazu ist.

aufbau düfte klar sein:
eine struktur, die ein datenfeld und einen pointer 'next' auf die 
nächste instanz der struktur enthält, ein pointer der struktur als 
'nexttoprocess' und eine 'appendhere' die auf die letzte instanz zeigt.
beim anfügen wird ein addhere.next alloziiert,
beim abarbeiten wird nexttoprocess auf den nächsten gesetzt, der erste 
freigegeben usw.

hat den vorteil, daß es nicht wie beim ringpuffer zum überlauf kommen 
kann (solange der sram noch was hergibt).
nachteil: die daten liegen ggf. im speicher verstreut und man hat nen 
gewissen overhead.

und genau da bin ich mir nicht sicher:
ich habe
typedef struct ll_type {
  uint8_t *dat;   //allocatable int array, hold the data
  struct ll_type *next;
}ll_type;

also ein dynamisches dat array, so daß ich mal 8 und mal n*8 bit daten 
speichern kann.
wie groß ist denn dann der overhead? (sizeof(ll_type)) gibt 8bit
,d.h. ich benötige 8bit zum zeigen auf den nächsten container,+die größe 
für die im datarray gespeicherten daten?
-> für 8bit daten also overhead:daten = 1:1 (wenn man den nexttoprocess 
und addhere vernachlässigt)?


am ringpuffer gefällt mir nicht, daß derspeicher ja permanet für andere 
'tasks' unbrauchbar ist. gibts noch ne andere möglichkeit?

alex

Autor: holger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>am ringpuffer gefällt mir nicht, daß derspeicher ja permanet für andere
>'tasks' unbrauchbar ist.

Das stimmt, aber er benötigt pro Byte wesentlich weniger Speicher als 
deine
LinkedList. Und wenn du sehr viele Daten puffern musst zerstört dir
deine Liste wesentlich früher andere Speicherbereiche wenn die Liste
z.B. in den Stack wandert. Beim Ringpuffer kannst du die Notbremse
ziehen, weil du weisst wie groß er ist ! Und es ist ein Trugschluss das
deine LinkedList nicht auch permanent Speicher belegt. Du musst immer
so viel Speicher freilassen das deine Liste da auch reinpasst !

Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
holger wrote:
>>am ringpuffer gefällt mir nicht, daß derspeicher ja permanet für andere
>>'tasks' unbrauchbar ist.
>
> Das stimmt, aber er benötigt pro Byte wesentlich weniger Speicher als
> deine
> LinkedList. Und wenn du sehr viele Daten puffern musst zerstört dir
> deine Liste wesentlich früher andere Speicherbereiche wenn die Liste
> z.B. in den Stack wandert. Beim Ringpuffer kannst du die Notbremse
> ziehen, weil du weisst wie groß er ist ! Und es ist ein Trugschluss das
> deine LinkedList nicht auch permanent Speicher belegt. Du musst immer
> so viel Speicher freilassen das deine Liste da auch reinpasst !

Nicht bei dynamischer Speicherverwaltung. Für Daten im Byte-Bereich 
halte ich einen Ringpuffer allerdings auch für wesentlich sinnvoller 
als eine verknüpfte Liste. Kann es denn vorkommen, dass du die Daten die 
reinkommen überhaupt nicht mehr rauskriegst? Dann würde ich mal das 
Konzept des ganzen Aufbaus überdenken...

Autor: Uhu Uhuhu (uhu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Vermutlich meinst Bytes, statt Bit...

Die ökonomischste Lösung ist der Ringpuffer: Er nutzt den Speicher am 
besten und der Code, der ihn verwaltet, ist wesentlich einfacher und 
kleiner, als eine ausgewachsenen Heapverwaltung - die braucht nämlich 
neben dem nicht eben kleinen Code selbst nochmal für jedes allokierte 
Objekt einen ähnlichen Overhead, wie deine verzeigerte Liste.

Falls es sich bei deiner Hardware um einen µC mit nicht ausgesprochen 
üppigem RAM handelt, würde ich generell von verzeigerten Listen abraten. 
Nicht nur wegen des Overheads, sondern vor allem auch wegen der damit 
sprunghaft ansteigenden Anzahl möglicher Speicherlayout-Konstellationen 
und der der Probleme durch Speicherverschnitt und scheiternden 
Speicherallokationen.

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
µC und dynamische Speicherverwaltung sind in der Regel sehr 
gegensätzlich, wenn der Mikroprozessor kein Betriebssystem, bzw eine MMU 
hat.. Würde ich jetzt einfach mal sagen.

Also bei "kleinen" 8-Bittern sollte man sowas eigentlich unterlassen, da 
es den Speicher fragmentiert.

Autor: Alexander Poddey (alexatmikro)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
also der µC ist ein ARM SAM7X256, sram könnte man als komfortabel 
beschreiben...

>Vermutlich meinst Bytes, statt Bit...

hm? wieso? eine uint8_t sind doch 8bit oder? 
size(uint8_t)=8=size(ll_type), oder seh ich's grad net?

>Du musst immer
>so viel Speicher freilassen das deine Liste da auch reinpasst !

na ja, ich hab 3 stellen, an denen daten schubweise ankommen, aber 
eigentlich nicht an allen 3 gleichzeitig -> der speicher ist dann für 
alle nutzbar.
beim ringpuffer muß ich entweder 3 stück mit der jeweils maximal 
auftretenden größe einrichten, oder wieder nen handler schreiben, der 
die datenblöcke 'gemischt' speichern kann...

>Kann es denn vorkommen, dass du die Daten die
>reinkommen überhaupt nicht mehr rauskriegst?

eigentlich nicht. ich hab z.B. eine Funkstrecke, die ggf. mal gestört 
sein kann etc.

>sondern vor allem auch wegen der damit
>sprunghaft ansteigenden Anzahl möglicher Speicherlayout-Konstellationen

wo ist das ein problem? ggf für den optimizer? klar, der speicher wird 
fragmentiert, da sich die linked-liste halt durch den freien speicher 
bewegt...
ah, ein malloc für ein array könnte scheitern, wenn derenstprechende 
speicherbereich nicht kontinuierlich zu haben ist - richtig?
(ich programmier sonst eher code für simulationscluster, da ist speicher 
kein thema ;-))

nochmal zum overhead:
so groß ist der ja nicht (oder verrechne ich mich):
wir haben n datensätze -> (n-1)*8bit für die Zeiger zwischen den 
datensätzen, 2*8bit für den zeiger auf den ersten und letzen satz.
->(n+1)*8bit

wenn ich z.B. 10 uint32_t sätze speicher, brauch ich im ringpuffer 
(10+2)*32bit=384bit, in derlinkedliste 11*8bit+10*32bit=408bit

oder überseh ich was?

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du willst ja die Daten schnell einfüllen können, in einem IRQ.
Bei der Linked list hast du dann einen malloc-Aufruf in deiner ISR, mit 
ziemlich unvorhersehbarer Laufzeit. Mal abgesehen davon, dass du dann 
alle weiteren mallocs/frees im Hauptprogram mit abgeschalteten IRQs 
ausführen musst, weils sonst deinen Heap zerschiesst.

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>  (n-1)*8bit für die Zeiger zwischen den...

Dein Zeiger ist sicher nicht nur 8 Bit breit, sonst könnte man damit ja 
nur 256Bytes RAM adressieren. Unter einer komfortablen SRAM-Menge 
versteh ich etwas mehr...

Autor: Uhu Uhuhu (uhu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> hm? wieso? eine uint8_t sind doch 8bit oder?
> size(uint8_t)=8=size(ll_type), oder seh ich's grad net?

Sizeof liefert die Länge in BYTE zurück.

>> sondern vor allem auch wegen der damit
>> sprunghaft ansteigenden Anzahl möglicher Speicherlayout-Konstellationen
>
> wo ist das ein problem? ggf für den optimizer? klar, der speicher wird
> fragmentiert, da sich die linked-liste halt durch den freien speicher
> bewegt...

Der Heap verleitet dazu, von einer näherungsweise unendlichen Resource 
auszugehen und Situationen mit Speichermangel garnicht in Betracht zu 
ziehen. Das ist eine Fiktion, die schon so mancher 'gut getesteten' 
Applikation den Ruf gekostet hat...

Das ist keine Frage des Optimizers, sonder des Software-Testers. Der 
Heap produziert sehr schnell so viele mögliche Speicherlayouts, daß man 
die nicht im entfernten auch nur einigermaßen testen kann. Ein gut 
verborgener Adressierfehler schlägt dann eben nur alle 5 Stunden mal zu, 
statt alle 5 Sekunden bei einem statischen Design - viel Spaß beim 
Suchen...

Dazu kommt, daß die kritischen Layouts meistens nicht erkannt und schon 
garnicht provoziert werden können, weil der Heap-Aufbau nicht ohne 
weiteres nachvollzogen werden kann.

> oder überseh ich was?

Ja. Siehe oben.

@Ernst Bachmann:
> Du willst ja die Daten schnell einfüllen können, in einem IRQ.
> Bei der Linked list hast du dann einen malloc-Aufruf in deiner ISR, mit
> ziemlich unvorhersehbarer Laufzeit. Mal abgesehen davon, dass du dann
> alle weiteren mallocs/frees im Hauptprogram mit abgeschalteten IRQs
> ausführen musst, weils sonst deinen Heap zerschiesst.

Sehr gut erkannt, das hatte ich noch garnicht in Betracht gezogen.

Ob die Heapverwaltung auf dem ARM threadsafe ist, weiß ich nicht, aber 
vermutlich eher nicht.

Autor: holger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>size(uint8_t)=8=size(ll_type), oder seh ich's grad net?

sizeof(uint8_t)=8
 das ist korrekt


>typedef struct ll_type {
>  uint8_t *dat;   //allocatable int array, hold the data
>  struct ll_type *next;
>}ll_type;


sizeof(uint8_t *) ist was anderes als 8 ;)

Autor: Uhu Uhuhu (uhu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
holger wrote:
>>size(uint8_t)=8=size(ll_type), oder seh ich's grad net?
>
> sizeof(uint8_t)=8
>  das ist korrekt

Hast du das ausprobiert?

uint8_t sieht mir eher wie 8 Bit aus, also müßte sizeof (uint8_t) == 1 
sein.

Nachtrag:

   #define   INT8_MAX   0x7f
   #define   UINT8_MAX   (__CONCAT(INT8_MAX, U) * 2U + 1U)

Also ist es 1 Byte.

Autor: holger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Hast du das ausprobiert?

Nö ;)

>uint8_t sieht mir eher wie 8 Bit aus, also müßte sizeof (uint8_t) == 1
>sein.

Du hast recht. sizeof gibt die Anzahl Bytes zurück.
Ich geh lieber schlafen.

Autor: holger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Ich geh lieber schlafen.

Korrektur:
Ich geh besser schlafen ;)

Autor: alexatmk (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hallo,

entschuldigt, hab's grad nochmal ausprobiert
sizeof(uint8_t) ist 1 :schäm:
sizeof(uint8_t *) ist 8

ich hätte eigentlich erwartet, daß der zeiger auf einem 32bit system 
32bit braucht. 8bytes ist ja irre viel...

hmm, dann sieht meine overheadbetrachtung ganz anders aus :-(


> ziemlich unvorhersehbarer Laufzeit. Mal abgesehen davon, dass du dann
> alle weiteren mallocs/frees im Hauptprogram mit abgeschalteten IRQs
> ausführen musst, weils sonst deinen Heap zerschiesst.

interessanter punkt. ich hab zwar ein handling, damit sichergestellt 
ist, daß die linked-liste nicht gelichzeitig von 2 'tasks' bearbeitet 
wird, bisher die linkedliste aber noch nicht in einer irq routine 
verwendet (sondern dort daten in eine variable geschrieben, die ich 
mittels noicht-irq routine dann in die linkedliste fülle).

hab mich überzeugt:
ich werd wohn 'n ringpuffer verwenden. muß mal den naßcomputer arbeiten 
lassen, vielleicht fällt mir was gescheites ein um eine ringpuffer für 
verschiedene bereiche zu verwenden....


gruß
alex

Autor: Rufus Τ. Firefly (rufus) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> sizeof(uint8_t *) ist 8
>
> ich hätte eigentlich erwartet, daß der zeiger auf einem 32bit system
> 32bit braucht. 8bytes ist ja irre viel...

Was ist das für ein "32-Bit-System"? Üblich wären 4 Bytes.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.