Hallo Zusammen
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.
Daniel A. schrieb:> Ich brauche also einen Allocator, der weiss, dass "hello + 6" teil der> Allokation "hello" ist.
Sehr ungewöhnlich.
Warum brauchst du das?
MaWin O. schrieb:> Daniel A. schrieb:>> 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.
Daniel A. schrieb:> normale Strings
std::string
> readonly Strings
const std::string
> Strings mit Referenz Counter
std::shared_ptr<std::string>
duck und wech...
Nikolaus S. schrieb:> MaWin O. schrieb:>> Daniel A. schrieb:>>> 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.
Niklas G. schrieb:>> readonly Strings>> const std::string
Wie oben beschreiben, ich mache da teils etwas härtere, nur zur runtime
relevante, Designentscheidungen, als const alleine sicherstellen könnte.
Daniel A. schrieb:> 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.
Daniel A. schrieb:> 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.
Daniel A. schrieb:> 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.
Daniel A. schrieb:> 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_ptr<std::string>,
std::unique_ptr<std::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.
Niklas schrieb:
> [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.
Thread beobachten
Seitenaufteilung abschalten