In einem Projekt vor etwa zehn Jahren haben wir festgestellt, dass die dynamischen Zuweisungen von std::vector zu einem erheblichen Leistungsverlust geführt haben. In diesem Fall wurden viele kleine Vektoren zugewiesen, so dass die schnelle Lösung darin bestand, eine vektorartige Klasse zu schreiben, die ein stapelbasiertes vor-zugeordnetes char -Array umgab, das als roher Speicher für seine Kapazität verwendet wurde. Das Ergebnis war ein static_vector<typename T, std::size_t Max> . So etwas ist leicht genug zu schreiben, wenn Sie ein paar Grundlagen kennen, und Sie finden einige solche Bestien im Internet . Tatsächlich hat boost jetzt auch einen .
Wenn wir jetzt an einer eingebetteten Plattform arbeiten, benötigen wir ein static_basic_string . Das wäre eine Zeichenfolge, die eine feste maximale Speichermenge auf dem Stapel vorverteilt und diese als ihre Kapazität verwendet.
Zuerst dachte ich, das sollte ziemlich einfach sein (es könnte immerhin auf der vorhandenen static_vector basieren), aber wenn ich noch einmal auf die Schnittstelle von std::basic_string schaue, bin ich mir nicht mehr so sicher. Es ist viel komplexer als die Schnittstelle std::vector . Besonders die Implementierung der Familie von find() functions std::basic_string ist mehr als nur eine mühsame Aufgabe.
Das hat mich wieder zum Nachdenken gebracht. Denn dafür wurden Allokatoren geschaffen: Ersetzen Sie die Allokation basierend auf new und delete mit anderen Mitteln. Zu sagen, dass die Allokator-Schnittstelle unhandlich ist, wäre jedoch eine Untertreibung. Es gibt ein paar Artikel, die es erklären, aber es gibt einen Grund, warum ich in den letzten 15 Jahren so viele selbstgewählte Allokatoren gesehen habe.
Also hier ist meine Frage:
Wenn Sie ein basic_string Lookalike implementieren müssten, wie würden Sie das machen?
static_basic_string ? std::basic_string ? Wie immer gibt es eine ziemlich wichtige Einschränkung für uns: Da wir auf einer eingebetteten Plattform arbeiten, sind wir an GCC 4.1.2 gebunden, so dass wir nur C ++ 03, TR1 und Boost 1.52 einsetzen können / sup>
Die erste Frage ist: Wie viel von der extra Schnittstelle brauchst du?
benutzen? Die meisten von std::string können zusätzliche Schnittstellen sein
trivial implementiert mit Funktionen in <algorithm> (z.
std::find , std::find_if und std::search ), und in vielen
Fälle, es gibt große Teile davon, die sowieso nicht verwendet werden.
Implementieren Sie es einfach nach Bedarf.
Ich denke nicht, dass Sie dies mit einem benutzerdefinierten Zuordner machen können. Der einzige Weg, um den Speicher "on stack" zu bekommen, wäre es zu deklarieren als Mitglied des benutzerdefinierten Zuordners, der alle erstellen würde Arten von Problemen beim Kopieren von ihnen. Und Allokatoren müssen sein kopierbar, und die Kopien müssen idempotent sein.
Vielleicht finden Sie eine kostenlose Implementierung im Netz von
std::string , das die kleine Zeichenfolgenimplementierung verwendet; dann
modifiziere es so, dass die Cutoff-Größe (darüber hinaus dynamisch) verwendet wird
Zuweisung) ist größer als alle Strings, die Sie tatsächlich verwenden. (Dort
sind mehrere Open-Source-Implementierungen der Standardbibliothek
verfügbar; der mit g ++ gelieferte verwendet immer noch COW, aber
Ich vermute, dass die meisten anderen SSO verwenden.)
Es ist einfach, schreibe einen Stapelzuordner, hier ist ein Beispiel:
Mit Zuordnern können Sie ebenso einfach z. B. aus einer speicherabgebildeten Datei, d. h. aus dem Laufwerk, oder aus einem statischen Array von char s zuordnen.
LLVM ADT verfügt über die Klasse SmallString . Es hat auch SmallVector und viele andere nützliche Klassen.
Während die aktuelle LLVM-Codebasis in Richtung C ++ 11 wandert, unterstützen (nicht so-) alte Versionen von LLVM C ++ 03.
Ein ausgezeichneter Ausgangspunkt ist Alexandrescus richtlinienbasierte String-Klasse, die in diesem Dr. Dobbs beschrieben wird Artikel . Es enthält eine SSO-Richtlinie, die grundsätzlich das tut, was Sie wollen (suchen Sie die Seite nach SmallStringOpt ) und ist leicht zu ändern, wenn / wie Sie es für notwendig halten. Es ist älter als C ++ 11, also geht es dir auch gut.
Es gibt viele basic_string -Implementierungen, einige vollständig basierend auf dynamischer Zuweisung, einige andere auf dynamische Zuweisung nur für Strings, die breiter als eine gegebene Länge sind (tatsächlich verwenden sie ihren eigenen internen Puffer, wenn es passt).
Die Verwendung eines Zuordners ist wahrscheinlich nicht der richtige Weg, da die Schnittstelle zwischen der Zeichenfolge und dem Zuordner davon ausgeht, dass das Zuordnungsobjekt Teil des Containers ist, der zugewiesene Speicher jedoch von außerhalb des Containers selbst stammt. Sie können es arrangieren, indem Sie einen Allokator mit POSIX alloca implementieren, mit allen Nachteilen .
Das Problem beim Implementieren von Strings auf Stack ist, dass man es nicht dynamisch wachsen lassen kann (vielleicht hat der Stack zu diesem Zeitpunkt etwas mehr), aber man muss auch auf Operationen wie += achten, die einen String länger machen können und länger.
Sie enden also mit der Vorabzuweisung (als ein Array oder als zugeordneter Puffer, innerhalb Ihrer Klasse oder innerhalb eines Zuordners ändert sich das Problem nicht) eine Menge an Bytes, die Sie entweder verschwenden, aber nicht alle füllen, oder indem Sie sie nicht verwenden, wenn die Zeichenfolge zu groß geworden ist und dynamisch sein muss.
Es gibt wahrscheinlich einen Kompromiss zwischen dem Speicher-zu-Cache-Kommunikationsprozess (normalerweise mit 128 Byte oder 4 KByte), aber es ist stark hardwareabhängig, so dass sich die Komplexität nicht leisten wird.
Eine günstigere Lösung kann ein Zuordner sein, der immer noch auf dem Heap allokiert, aber die zurückgegebenen Blöcke behalten und wiederverwenden kann (bis zu einem bestimmten Limit), was die Notwendigkeit verringert, das System nach zugewiesen / freigegeben zu fragen.
In diesem Fall kann die Leistung jedoch nicht unbedingt von Vorteil sein, wenn das zugrundeliegende System new/delete bereits auf diese Weise implementiert.
Ich würde eine Kombination von implementierungsdefinierten VLAs und Standardalgorithmen verwenden, sollte ich denken.
Dies ist ein funktionierender Code, aber NICHT DEN EMPFOHLENEN WEG .
Dieser Code hat viele Spuren, um zu zeigen, was er macht. Es überprüft nicht, dass die Größe der Zuordnungsanforderung den Puffer nicht überschreitet. Sie können dies überprüfen, wenn nötig. Beachten Sie, dass std :: basic_string versucht, mehr als nötig zuzuordnen.
%Vor%Dieser Code wurde auf GCC und LLVM getestet und funktioniert wie erwartet (oder unerwartet).
Die Syntax ist unhandlich. Es ist nicht möglich, von basic_string abzuleiten und den Puffer einzubetten. Ein weitaus besserer Weg besteht darin, eine kleine spezialisierte buffer_string-Klasse mit der erforderlichen Teilmenge der basic_string-Schnittstelle zu erstellen.
Tags und Links string c++ allocator stack-allocation