Vorstellung Playlist Optimierung

Software
1

Hi,
Ich wollte euch mal meinen Entwurf für das Handling der Playlisten vorstellen. Die Branch ist hier zu finden: GitHub - laszloh/ESPuino at devel/playlist_improvements

Die Branch ist mein Developemnt Branch ohne rebase & leanup, somit könnt ihr alle wundervollen blutigen Details und jedes einzelne Fail das ich auf dem Weg begegnet bin miterleben :laughing:

Kurze Vorstellung des Systems

Die Klassenstruktur ist relativ einfach, es gibt eine abstrakte Klasse Playlist, die von allen anderen arten von Playlists implementiert werden. Die Playlist stellt einige Helper zur Verfügung, wie zB einen std-lib Memory-Allocator (der PSRAM bevorzugt) oder ein Sortier-Algorithmus für Strings. Durch die Vererbung haben alle Klassen zugriff darauf.

566×668 38 KB

Es wird ein Pointer auf eine mit new dynamisch alloktierte Playlist mit der Queue an den AudioPlayer_Task übergeben, der sich dadurch nicht mehr um die Implementierung im Hintergrund kümmern muss. Die Task ist für die Vernichtung der alten Playlist verantwortlich, sobald eine neue Playlist durch die Queue empfangen wird.


Einige Kommentare zu der Implementation, da wahrscheinlich da Fragen aufkommen werden :smiley:

Verwendung von std::vector statt manueller Allokation
Wenn ihr in der Histroie schaut, war die erste Implementation vergleichbar zu unserer jetzigen Lösung mit manueller Allokation von Speicher für ein Array von char* Zeigern. Das funktioniert relativ gut, bis ich an den Punkt gekommen bin, dass ich den Pointer-Array auch vergrößern müssen könnte. Plus zwei Zählvariablen, eines für die Capacity und eines für die aktuelle Auslastung. An dem Punkt habe ich std::vector kurz aufgemacht und bemerkt, dass ich das gerade Rad neu erfinde…

Ich verwende std::vector mit einer initialen Größe von 64. Die GCC Version von std::vector implementiert ein Growth-Faktor von 2 (order 1.5), d.h. wenn der Allokierte Speicher ausgeht, wird dieser verdoppelt. Damit garantiert std::vector ein push_back mit amortisierende Faktor O(n). Damit sollten wir max 2-4 realloc’s benötigen (beim 4. hätten wir eine Playlist mit 1024 Einträgen). Das sollte reichen :slight_smile:

Das spielt natürlich keine Rolle, wenn die Größe des Arrays zum Zeitpunkt des Aurufs bekannt ist, dann reserviere ich genau die nötige Größe vom Anfang an.

Ein riesen Plus, std::vector ruft beim Zerstören den Destruktur von jedem Eintrag im Array auf, damit müssen wir uns um ein Punkt weniger kümmern.


Verwendung von std::string
Der große Vorteil von std::string über String ist, dass ein Allokator definiert werden kann. Damit können wir std::string in den PSRAM verschieben, wenn dieser verfügbar ist. Der Allokator wird von std::string (eigentlich std::basic_string) verwendet, sobald dynamischer Speicher benötigt wird (sowol String als auch std::string haben einen internen Buffer, der bei Zeichenketten < ~10 Zeichen verwendet wird).

Vorteil über manuelles Arbeiten ist, dass sich schon jemand Gedanken um die Vernichtung des Speichers gemacht hat, d.h. sobald der Desktruktor von der Playlist aufgreufen wird, wird auch die std::string vernichtet.


Cache File
Das Handling der File habe ich geändert. Ich füge aktuell einen Header am Anfang ein, der neben der Anzahl an Einträgen, einem 16bit flag Feld auch, einer „magic Wert“ + Version hat (plus CRC um die Integrität zu erkennen). Das hat den Vorteil, dass wir automatisch veraltete Playlists erkennen können (also wenn sich zB die Struktur des Header oder die Anzahl/Position der Flags sich geändert hat) und entsprechend reagieren können.

Ein großer Nachteil dieser Lösung ist, dass wir nicht Rückwärtskompatibel sind. Die aktuelle SW stürzt mit einem Memory-Fehler ab, sobald versucht wird, den neuen Header zu lesen.

Ich spiele auch mit einer Idee, das Handling des Cache Files aus der Playlist zu extrahieren. Also ca solch eine Struktur:

1019×495 52.1 KB


Wehmutstropfen / Verbesserungpotenziale / Ideen
Ein großer schmerzhafter Punkt ist, dass die FreeRTOS Queues nicht c++ tauglich sind. Dadurch das wir mit xQueueSend einen POD (Plain Old Data) pointer übergeben, bin ich gezwungen mich manuell um die Allkation & Deallikation (mit new & delete) zu kümmern. Würden wir c++ Klassen übergeben können, könnten wird zB mit smart pointern arbeiten. Das würde uns einen weiteren Punkt von der Kopfschmerz liste streichen.

Ich hatte mir an dem Punkt überlegt, ob wir statt einer FreeRTOS-Queue einen einzelnen smart-pointer Objekt zu erstellen. Dieser würde, geschützt durch einem Semaphore, die Funktion der Queue übernehmen (die aktuell eh nur 1 Element tief ist).

Aktuell spiele ich mich aber noch mit dem Gedanken, diese Änderung auch einzubauen.


Unit Tests
Dank dem Klassensystem kann ich deren Funktion relativ einfach mit Unit Tests prüfen. Als Beispiel ist hier der Unit test von der FolderPlaylist: ESPuino/test_main.cpp at devel/playlist_improvements · laszloh/ESPuino · GitHub

Um die Tests durchzuführen, müsst ihr in VSCode das Chemie-Symbol drücken ().
image

Die ESP Tests laufen lokal auf dem ESP, dieser wird jeweils mit den einzelnen Test programmiert.


Wie immer sind Ideen gerne Willkommen :slight_smile:

4 „Gefällt mir“
2

Was wäre denn der Use Case dafür? Also warum sollte man eine aktive Playlist verändern wollen?
Oder habe ich es falsch verstanden und es geht darum, dass wenn man eine aktive Playlist hat und eine neue Karte auflegt, die zu einer größeren Playlist führt, dass nicht der ganze Speicher freigegeben + reallokiert werden muss, sondern stattdessen der Speicher „wiederverwendet“ + vergrößert wird?

Im Grunde müsste man das nicht mit einer Queue machen, da jetzt auch nicht ständig in Massen neue Playlist-Objekte reinkommen, bei denen man einen Mechanismus braucht, um auch keine Elemente zu „vergessen“. Ich hab’s damals mit einer Queue gemacht, da mir das konzeptionell gefallen hat und ich einfach mal mit Queues arbeiten wollte. Da hängt jetzt mein :heart: nicht dran, dass das auf immer und ewig so bleibt.

Zwingend notwendig ist auf jeden Fall abwärtskompatibel. Kann man dann schauen, inwiefern rückwärtskompatibel notwendig sein wird.

Mal ganz ungeachtet der fachlichen Thematik finde ich es sehr cool, wie du das hier beschrieben hast. Also dass du deine Konzepte beschreibst und auch, was du dir dabei gedacht hast. Dafür ein :+1: von mir - ich mag sowas! Ich finde es immer wichtig, Leuten Dinge zu erklären - deswegen habe ich mir auch so viel Arbeit gemacht.

1 „Gefällt mir“
3

Mein Use-Case ist bei der Erstellung der Playlist, nicht bei der Veränderung. Da habe ich mich vielleicht ein wenig undeutlich ausgedrückt.
Eine dynamische Reallocation ist notwendig, wenn die Anzahl der Einträge am Anfang nicht bekannt sind. Als Beispiel wenn alle Dateien in einem Ordner in die Playlist übertragen werden müssen. Da wir zum Startzeitpunkt nicht wissen, wie viele Dateien in einem Ordner sind, muss ich entweder mit File.openNextFile() den Ordner 2x durchgehen (das 1. Mal für die Anzahl an Dateien in dieser und das 2. Mal um die Pfade auszulesen) oder aber das char-Array ist in der Lage sich dynamisch zu vergrößern (also wenn wir mehr als die Pi * Daumen = 64 Einträge brauchen).
Das gleiche Problem haben wir zB mit der M3U Datei, bei der wir beim Start nicht wissen, wie viele Einträge uns erwarten (bei dieser ist es noch nerviger, da hier teilweise in der Version 2 Meta-Daten drin sein können).

Ich hatte das 2-fache Iterieren über ein Ordner ausprobiert, da gab es merkbar große zeitliche Unterschiede (in dem 100ms Bereich), vor allem wenn gerade eine Wiedergabe von der SD Karte am laufen war. Das war der Grund, wieso ich zu std::vector gegriffen habe (wie gesagt, Rad neu Erfinden wollte ich dann doch nicht :slight_smile: ).
Unsere aktuelle Lösung mit 1fachem Durchlauf und alle Pfade in einem durchgehenden char Buffer im RAM zu speichern führt zu einem doppelten Speicherverbrauch (1x alle Pfade in dem Buffer + dann alle Pfade im char**-Array). Da ist die Reallokation nur von dem Pointer-Array (sizeof(void*) → 4 byte / Eintrag), bzw hier std::string Instanzen (sizeof(std::string → 24 byte / Eintrag ) ökonomischer.

Bei einer neuen Playlist wird der Speicher freigegeben und dann neu Allokiert, da die Playlists in sich geschlossen sind und voneinander nichts wissen. Auch muss die neue Playlist ja angelegt werden, während die Alte noch läuft, dh. wir können den Speicher der alten nicht wiederverwenden.


Passt, ich schaue mir das dann an, wie wir das ohne einer Queue machen können. Dadurch wird das System sicherlich noch ein wenig mehr Kugelsicher.

Gegen Queues ist auch nichts auszusetzten, die sind eine gute Lösung für die Übergabe von Daten zwischen Tasks. Einfach zu verwneden und kommen mit allem was man braucht. Nur leider ist FreeRTOS nur für c geschrieben, damit weiß es halt nichts von Klassen.


Ok, hier muss ich fragen, was verstehst du unter „rückwärtskompatibel“? Alte playlistcache.csv + neue SW?

Das ist kein Problem, da die neue Cache ein Header hat der so aussieht:

struct BinaryCacheHeader
    {
        uint16_t magic;
        uint16_t version;
        uint16_t flags;
        uint32_t count;
        uint32_t crc;
        uint8_t sep;
    };

Der Header selbst wird binär von der Klasse ausgewertet.

Magic und Version sind in der Klasse hart Kodiert (magic ist die Textfolge „CF“ und Version aktuell 0x01). Danach folgen die wichtigen Daten, die Flags und die anzahl an Einträgen in der Datei. Über dies 10 Bytes wird dann ein CRC32 gerechnet, d.h. wenn ein Bit geändert wird ergibt das eine ganz neue Zeichenfolge beim CRC und die Funktion sagt „nope!“ :no_good_man:.
Der Separator ist ein „#“, das den Header von den Rest der Daten abtrennt (und auch Teil des Headers, d.h. wenn der 15. Charakter nicht „#“ sagen wir auch „nope!“).

Der Header selbst ist binär, d.h. in dieser finden sich (wenn man es mit einem Text-Editor öffnet) „random“ Zeichen.

Um einen gültigen Header zu bekommen müsste nun in der alten Playlist alles zutreffen, d.h. ein sehr kurzes Dateipfad mit 14 Zeichen und sehr vielen Specialzeichen (die meisten nicht einmal Sichtbar, da sie Steuerzeichen in ASCII sind) und einer CRC Hashkollision (welche schon in sich zwischen 1:100.000 und 1:1.000.000 ist). Wenn das bei jemand passiert, würde ich ihm dringend Raten beim Euromillionär mit zu spielen :smiley:

Sobald der Header als fehlerhaft markiert wurde breche ich das Lesen der Datei ab und gebe an den Aufrufer zurück. Aktuell liest dieser dann den Ordner ganz normal, als gäbe es kein Cache File und überschreibt dann die fehlerhafte Datei. Damit ist für das Nächste Mal dann eine Valide Datei da und wir lesen ihn ein.

Gruß,
Laszlo


edit: Mir kommt gerade die Eingebung, dass ich den CRC auch über die ganze Datei rechnen könnte. Dann würde ein Schreibfehler (oder wenn der Nutzer manuell was editiert) sofort zu einem „Ausfall“ der Datei führen. Muss mir mal das morgen in Ruhe durch den Kopf gehen lassen.

1 „Gefällt mir“
4

Stimmt. Ich muss zugeben, dass ich an dieses Problem gar nicht gedacht habe. Ist schon ein paar Jährchen her, als ich die Playlist-Generierung programmiert habe. Das Caching kam dann später.
Ok, akzeptiert.

Abwärtskompatibel: Neue Software muss ein altes Cachefile-Format lesen + migrieren können.
Rückwärtskompatibel: Alte Software erkennt neues Cachefile-Format, löscht das File und legt es neu an. Ganz einfach verhindern, dass Leute in Probleme laufen, weil sie in DEV was testen und dann doch wieder zurückgehen.

2 „Gefällt mir“
5

Ok, das kann das System jetzt schon in dem Sinne dass eine alte/fehlerhafte Cache-File erkannt und gelöscht wird. Damit ist sicher gestellt, dass immer eine gültige Cache File abliegt (gültig im Sinne des Formates, nicht dass sich der Inhalt des Ordners seit dem geändert hat).

Ok, das wird schwierig, wenn zB der Master draufgespielt wird. Die aktuelle SW siehtkeine Möglichkeit voreine Cache File zu validieren. Es liest aktuell stur die Datei in die Variable serializedPlaylist, das dann an jeder ‚#‘ getrennt wird. Da gibt es keine Abfrage oder sequenz, die ich verwenden könnte um das neue Format inkompatibel zu machen (Ideen sind willkommen :smile:).
Die einzige Lösung die mir gerade einfällt ist einen neuen Namen für die Cachefile zu vergeben oder die „playlistcache2.csv“ von der Dev-Branch zu nutzen (wobei csv als Endung für das Cache-File format nicht die Beste ist, da es jetzt eigentlich eine Binary-File ist).

Wenn das neue Cache File Format verwendet wird (also zB downgrade der SW von CachFile Version 5 auf Version 3), ist auch eine Rückwärtskompabilität gegeben, da die Header-Version hart verglichen wird. D.h. wenn die Version in der Datei größer ist als erwartet, wird die Datei auch als ungültig markiert.

1 „Gefällt mir“
6

@laszloh Zunächst Hut ab vor Deiner Arbeit & der tollen Doumentation, Daumen hoch :+1:

Die Playlist in eine eigene Klasse zu packen finde ich gut weil man die Komplexität etwas verringern könnte.
Die ganze Speicherverwaltung geht bei Dir ja schon in den Profibereich! Problem habe ich dort noch nicht gehabt weil meine Box geht irgendwann in den Deep-Sleep und bootet dann komplett neu. Habe also keinen 24/7 Betrieb. Trotzdem sorgen Deine Verbesserungen natürlich für einen stabileren Betrieb & sind sicher willkommen!

Zum Playlist Cache bin ich etwas ziegespalten weil ich halte sie für obsolet: Ich habe sie vor einigen Monaten komplett deaktiviert. Grund ist diese Optimierung, damit wird der Cache aus meiner Sicht überflüssig. Habe die beschleunigte Dateiauflistung eigentlich nur für das Laden des Verzeichnisbaums in der Weboberfläche eingebaut, sollte aber für die Playlist-Generierung auch den Turbo einschalten. War nur als Hack gedacht aber könnte hier sicher helfen. Evt. kann das hier mit einfließen oder zunächst getrennt im Dev-Branch?

Nicht falsch verstehen, möchte das Thema hier nicht kapern!

3 „Gefällt mir“
7

Oh nice, das Feature ist gemergt und in 2.0.7 verfügbar. Damit können wir die Funktion direkt in der Dev-Branch verwenden. In der Main müssten wir das Feature manuell einbauen.

Das werde ich nächste Woche einbauen und testen, wie viel ich damit rausholen kann. Wenn das schneller wird als das Lesen & Parsen der Cache-Datei, dann brauchen wir den Cache definitiv nicht. Deine Tests sind auf jeden Fall erfolgsversprechend, eine Reduktion von 2s auf 100ms ist beachtlich :slight_smile:.

Das löst auch den Punkt mit wie stellen wir sicher, dass die Cache Synchron zum Inhalt des Ordners ist.

2 „Gefällt mir“
8

Leider nicht ganz: Man kann bei der jetzt offiziellen Funktion getNextFilename() nicht unterscheiden ob es sich um eine Datei oder Verzeichnis handelt. Habe daher das FS angepasst. Werde das die nächsten Tage im Nachbarthread vorstellen & dokumentieren.

4 „Gefällt mir“
9

Well, that’s a bummer… Ja, ob es ein Ordner ist oder nicht, wäre schon interessant und wichtig gewesen :smile:.

Ich habe mir dein Code angeschaut, könntest du statt dem trainling slash (wobei dafür sollte es eher name = name + "/"; sein) ein std::pair<String, bool> zurückgeben?

also so:

std::pair<String, bool> VFSFileImpl::getNextFileName() {
[...]
return {name, (file->d_type == DT_DIR)};
}

Damit können wir es so aufrufen: auto [path, isDir] = folder.getNextFileName() und dann path und isDir als String und bool verwenden (I :heart: c++17) :smile: .

Ist eine größere Änderung gegenüber der normalen FS lib, aber mMn zeig es mehr, was wir da machen.

10

Sehr coole Sache was hier entsteht! Gefällt mir :slight_smile: .
Wenn die Cache-Files tatsächlich aufgelöst oder aktuell gehalten werden können wäre das richtig gut! Hatte jetzt schon paarmal in einzelnen Ordner Datein hinzugefügt, diese waren aber dann nicht gecached und wurde erst nach manuellem löschen der Cache-Files auch abgespielt in den entsprechenden Playmodi…