Bei einem meiner Projekte habe ich sehr viele string Datentypen mit diversen Memory Managemant Anforderungen, und es läuft langsam aus dem Ruder. Ich habe normale Strings, readonly Strings, Strings mit Referenz Counter, solche mit Hashes, welche mit einem eindeutigen Pointer aus einem Hash-set, und Kombinationen davon, sowie Sachen die zwischen manchen konvertieren.
Jetzt will ich zumindest mal das Memory Managemant vereinfachen, und das Reference Counting in einen eigenen Allocator verschieben. Ich habe dann Funktionen, die je nachdem die Strings kopieren, oder Referenden Counting machen, abhängig davon, woher die Dinger kommen. Wird also dann relativ Transparent gehandhabt werden, und ich kann dann viele Schnittstellen viel Toleranter gestalten, was für Daten sie annehmen.
In example.c im Anhang sieht man, wie ich mir das gedacht habe.
Mein Hauptproblem ist nun, ich möchte solche Sachen machen können:
1
char*hello=dpa_dup("Hello Sunny World!",19);
2
dpa_ref(hello+6);// rc 1->2
3
dpa_ref(hello);// rc 2->1
4
dpa_put(hello+6);// rc 2->0, "Hello Sunny World!" wird freigegeben
Ich brauche also einen Allocator, der weiss, dass "hello + 6" teil der Allokation "hello" ist. Ich muss irgendwie an die selben Metadaten kommen. Ob der Allokator eine Funktion dafür hat, oder eine um den Anfang der Allokation zu ermitteln, ist egal, ich brauche einfach was, um da nachher ran zu kommen.
Ansonsten habe ich den Rest der API schon mal vorbereitet (siehe Anhang). Ich brauche nur noch einen Allocator, der die Funktionen dpa_mem_impl_realloc und dpa_mem_impl_find_allocation_start implementiert, und dem ich meine Funktionen dpa_internal_allocate_pages und dpa_internal_free_pages mitgeben kann (die sind wrapper um mmap herum, die aus einem 1TB grossen, per mmap PROT_NONE reservierten Bereich, pages neu mappen und zurück geben).
Einen Allocator zu finden, der ein realloc bereitstellt, ist ja kein Problem. Das Problem ist einen zu finden, mit dem ich dpa_mem_impl_find_allocation_start umsetzen kann. Oder halt sonst wo meine Metadaten ablegen kann.
Selber schreiben würde ich den Allocator eher ungern. Das richtig und effizient hin zu kriegen ist schwierig.
Ich brauche also einen Allocator, der weiss, dass "hello + 6" teil der
Allokation "hello" ist.
Sehr ungewöhnlich.
Warum brauchst du das?
Finde ich auch ungewöhnlich. Normalerweise behält man eine (weitere) Referenz auf hello+0 um den gesamten Speicher freigeben zu können. Denn es ist m.E. nicht mal offensichtlich ob mit dpa_put(hello + 6) der Speicher von hello+0 bis hello+5 gekürzt oder auch mit freigegeben werden soll. Das kann man mit free(hello) oder realloc(hello, 6) steuern.
Ich brauche also einen Allocator, der weiss, dass "hello + 6" teil der
Allokation "hello" ist.
Sehr ungewöhnlich.
Warum brauchst du das?
Finde ich auch ungewöhnlich. Normalerweise behält man eine (weitere)
Referenz auf hello+0 um den gesamten Speicher freigeben zu können. Denn
es ist m.E. nicht mal offensichtlich ob mit dpa_put(hello + 6) der
Speicher von hello+0 bis hello+5 gekürzt oder auch mit freigegeben
werden soll. Das kann man mit free(hello) oder realloc(hello, 6)
steuern.
Wenn ich eine Funktion habe, ich übergebe ihr einen Member eines Structs, und etwas anderes braucht das später noch, dann muss ich eine design Entscheidung auf API Ebene treffen. Halte ich eine Referenz auf das darüberliegende Struct irgendwo vor? Muss / kann ich es kopieren? Soll die Funktion davon wissen, oder lasse ich den Caller das regeln? etc.
Wenn ich wenn möglich refcounting direkt im Allokator mache, wird die Situation simpler und Homogener. Der Allokator muss ja sowieso wissen, wie Gross der Speicherbereich ist, auf den ein Pointer zeigt, um ihn freizugeben. Er müsste die Referenz also schon in gewisser Weise haben.
Damit muss man nun auf API Ebene keine design Entscheidung mehr treffen, ob man diese behält, oder nicht, usw. Das Problem wird reduziert auf die Frage, ob und wo man die Daten kopiert. Eine Änderung in der Implementation, aber nicht an der API oder den Datenstrukturen. Ich kopiere sie nicht -> Äquivalent zum Behalten einer Referenz auf den Block. Ich kopiere sie in der Funktion -> nur ein zusätzlicher Funktionsaufruf dort. Ich kopiere sie vor dem Funktionsaufruf -> auch nur ein Funktionsaufruf dort.
Ausserdem unterteile ich den Speicher per Adresse in 3 Teile: Nicht von mir angelegt, Mir Refcounting rw, ohne Refcounting readonly (selber speicher nochmal gemappt mit anderen Zugriffsrechten). Wenn ich die readonly Adressbereiche so nutze, dass ich sie nicht nur als nur Lesbar, sondern als Unveränderbar behandle, kann ich noch weitere Optimierungen machen. Ich weiss nicht nur, wann ich meine Daten nicht ändern werde, sondern, dass niemand das tut. Und damit kann ich dann bei const Parametern weitere Optimierungen machen, nämlich, unveränderbaren Speicher nicht zu kopieren. Darum muss ich mich dann also auch nicht mehr selbst kümmern. Ein paar unnötige Kopien wird es trotzdem geben, ich habe noch keinen Check eingebaut, wo die .rodata der Anwendung hin gemappt wurden, das wäre noch optimierungsfähig. Dennoch, recht nun auch hier eine einzige API um alles abzudecken.
Damit muss man nun auf API Ebene keine design Entscheidung mehr treffen,
ob man diese behält, oder nicht, usw.
Also in C++ macht man es genau so. Der Parametertyp einer Funktion gibt an, ob kopiert wird oder nicht, oder die Funktion "owner" wird, ob Referenzzählung gemacht wird. Das dynamisch zur Laufzeit zu unterscheiden erschwert die Fehlersuche und ist ineffizient.
Ich weiss nicht nur, wann ich meine Daten nicht ändern werde,
sondern, dass niemand das tut. Und damit kann ich dann bei const
Parametern weitere Optimierungen machen, nämlich, unveränderbaren
Speicher nicht zu kopieren.
Klingt verdreht; eine Funktion/API welche Daten zum Auslesen bekommt, kopiert den Speicher eigentlich nie, sondern nimmt an, dass er konstant bleibt. Der Aufrufer muss dafür sorgen dass nichts geändert wird und ggf. die Kopie machen. Auch das braucht nicht zur Laufzeit entschieden werden.
Meistens weiss eine Funktion, wann sich der Wert einer Variable verändern kann. Aber sobald dass nicht mehr der fall ist, und/oder eine Unterfunktion das Objekt für länger behält, muss man es eventuell schon rein vorsichtshalber mal kopieren. Auch wenn das gar nicht nötig wäre. Ein X* lässt sich halt in ein const X* Konvertieren. Woher kam das Objekt noch gleich, lebt es lang genung, etc.? Klar, man kann immer mehr und strengere Typen drauf werfen, um das zu beschreiben. Und APIs darauf beigen, für die diversen Fälle.
Aber ich bin an einem Punkt angekommen, wo ich viele Typen habe, viele Semantiken unterstützen will, und das ganze unübersichtlich wird. Darum streiche ich das ganze und Wechsel einer simpleren, universelleren API.
Aber sobald dass nicht mehr der fall ist, und/oder eine
Unterfunktion das Objekt für länger behält, muss man es eventuell schon
rein vorsichtshalber mal kopieren.
Klingt nach einem Design-Fehler. Solche Probleme hab ich auch bei stark asynchroner Programmierung noch nicht gesehen. Unnötiges Kopieren ist sowieso ineffizent, das vermeidet man soweit wie möglich.
Woher kam das
Objekt noch gleich, lebt es lang genung, etc.?
Bei vernünftiger Architektur ist das alles klar ersichtlich. Durch Verwendung der richtigen Typen (std::string, const std::string&, std::string_view, std::shared_ptrstd::string, std::unique_ptrstd::string...) dokumentiert sich der Code selbst, und es ist genau zu ersehen wo Objekte erstellt, "owned", referenziert, gelöscht werden.
Das ist doch gerade der /Sinn/ von nativen Sprachen wie C und C++, dass man den Speicher explizit selbst verwaltet. Wenn man das nicht will, kann man auch Java nutzen. Da gibt es für alles den "String"-Typ, der ist immer read-only und muss zum Modifizieren kopiert werden, ist somit auch bei echten Konstanten effizient, Garbage Collection inklusive.
Ich habe es mit einer Library zutun. Mit dynamischen Baumstrukturen, eine art DOM. Dazu noch diverse Parser und Serializer. Und wenn es nicht nötig ist, komme ich tatsächlich ohne Kopieren aus. Aber ich habe Situationen, wo sich nur der Besitzer von Speicher ändert, und solche, wo der Speicher nicht statisch ist, und ich ihn kopieren muss, und ein paar andere Fälle. Und die APIs decken das auch alles ab. Aber Simpel ist das Design nicht mehr, und das gefällt mir nicht. Wie schon gesagt, ich habe mittlerweile nur schon mindestens ~5 String Typen. Und Situationen, wo ich einen hashed String brauche, aber einen refcounted string habe, oder umgekehrt, oder auch mal einen hashed refcounted string (oder war es refcounted hashed, ich weiss nicht mehr...), sind lästig, wenn ich da mal rein laufe, und dann auch mal was um designe...
Ich will ehrlich gesagt auch nicht wirklich darüber diskutieren, ob ihr meinen Ansatz toll findet oder nicht. Ich will einen neuen Ansatz ausprobieren, und dafür Fehlt mir nur noch diese eine kleine Sache, der Allocator. Bitte helft mir damit weiter.
Da deine Strings anscheinen zu C-Strings kompatibel sein sollen, kannst du eh nur Unterreferenzen auf Endbereiche des Originalstrings erstellen - echte Substrings (von-bis) gehen nicht, da denen die \0 fehlen würde. Du könntest also die Verwaltungsinformationen (ref-counts etc) hinter den String packen - dort sind sie per p+strlen(p) jederzeit zu finden.
Allzu sinnvoll finde ich das aber nicht - ein eigenständiger String-Typ wäre deutlich flexibler.
Wie schon gesagt, ich habe viele String typen. Wenn du in example.c im ersten Beitrag schaust (https://www.mikrocontroller.net/attachment/highlight/595363), dort habe ich ein struct für die Strings mit länge, pointer, (der auch nicht unbedingt null terminiert sein muss). Das sind aber auch nur Beispiele, ich könnte das an vielen Orten verwenden.
[Java] Da gibt es für alles den "String"-Typ, der ist immer read-only
und muss zum Modifizieren kopiert werden, ist somit auch bei echten
Konstanten effizient, Garbage Collection inklusive.
Lua macht das auch so. Zusätzlich werden Strings "interned", d.h. Kopien vereinheitlicht. Ist zwar beim Erzeugen einmalig etwas mehr Arbeit, danach sind String-Vergleiche aber nur noch Pointer-Vergleiche. Da bei Lua Variablen- und Feldnamen auch reguläre Strings sind, ist das ein wichtiges Kriterium. Dass dabei auch noch Speicher gespart wird, ist ein positiver Nebeneffekt.
