Effiziente Stringzerlegung (Parser)

Pria

Moin,

ich möchte gerne einen processor-emulator schreiben. Bevor jetzt einige mit dem Dragon Book ankommen, wäre erstmal der erste schritt eine vernünftige Zerlegung des Eingabetextes anhand einer Gramatik in einen AST.

Die Syntax soll auf jeden Fall dynamisch zur Laufzeit eingelesen werden können, daher kommt eigentlich nur EBMF in Frage oder?

Dann stellte sich mir wiederum die Frage in welcher Weise ich die Stringzerlegung in einzelne Tokens möglichst effizient gestalten kann. Einerseits könnte ich den String in eine char* packen und anhand von char-vergleichen matches finden, andererseits mit std::string operationen. Klingt jetzt beides aber nicht gerade optimal, sowohl performance als auch speichertechnisch.

Was ich mir dazu noch überlegt hatte, wäre in irgendeiner Form einen Hashwert zu erzeugen und bestimmte Abschnitte mit dem Haschwert zu vergleichen, so also die Matches zu verifizieren.

Hat jemand eventuell noch eine andere möglichst performante Idee wie man das erledigen könnte?

[Edit]
Oder bietet sich da ein generierter fixer Parser besser an? Ich möchte den Parser gerne mit teilweise unterschiedlicher Syntax für mehrere Aufgaben im Programm verwenden.
[/Edit]

Der nächste Schritt wäre dann die Tokens anahnd der Syntaxdefinition in einen AST zu packen.

Bitte ein Bit

Ich kenne da einen Parsergenerator namens GNU Bison

http://www.gnu.org/software/bison/

hustbaer

Parser mit fixer Grammatik werden wohl meistens schneller sein als Parser mit dynamisch ladbarer Grammatik. Und vor allem vermutlich einfacher umzusetzen.

Wenn du also nur ein paar verschiedene Parser mit unterschiedlicher Grammatik hast, deren Grammatik aber nicht irgendwie zur Laufzeit geladen werden muss, wäre vermutlich besser genau darauf auch zu verzichten, und einfach 2-3 verschiedene Parser zu implementieren.

Was das String-Handling angeht: viel schneller als mit zwei const char* (Zeiger auf Anfang und Ende) wird es wohl nicht werden.
Wenn du keine Digraphen/Trigraphen o.ä. verwendest könntest du in der Token Liste dann auch einfach Zeiger auf den originalen Input-String abspeichern, damit würdest du dir einiges an dynamischer Speicheranforderung sparen.

Wenns dir also um beste Runtime Performance geht, halte ich das Arbeiten mit Zeigern für eine gute Idee. Wenn du das Ding dagegen möglichst schnell implementiert bekommen willst, bietet sich vermutlich eher an std::string o.Ä. zu verwenden.

Und noch ein Tip: guck dir Boost.Spirit an. Hab' damit noch nie selbst gearbeitet, aber angeblich kann man damit recht einfach und schnell Parser zusammenbauen, indem man sie direkt in C++ in einer an EBNF angelehnten Syntax hinschreibt.

Nexus

Zu Boost.Spirit2 gibts auf dem Portal hier auch einen Artikel, du könntest ihn dir mal anschauen. Flex/Bison ist halt schon etwas älter und C-basiert, ausserdem benötigt es externe Tools, während Spirit komplett in C++ integriert ist.

Pria

hustbaer schrieb:

Parser mit fixer Grammatik werden wohl meistens schneller sein als Parser mit dynamisch ladbarer Grammatik. Und vor allem vermutlich einfacher umzusetzen.

Wenn du also nur ein paar verschiedene Parser mit unterschiedlicher Grammatik hast, deren Grammatik aber nicht irgendwie zur Laufzeit geladen werden muss, wäre vermutlich besser genau darauf auch zu verzichten, und einfach 2-3 verschiedene Parser zu implementieren.

Sagen wir mal so, ich würde einfach mal beides machen. Zum einen für die performancekritischen Sektionen einen vordefinerten Parser nehmen, zum anderen aber auch die Möglichkeit haben dynamisch ein Pattern zu laden.

Ich werde erstmal versuchen die dynamische Variante zu implementieren, eventuell kann man ja vor"kompilierte" Syntax laden oder sowas um das zu beschleunigen.

hustbaer schrieb:

Was das String-Handling angeht: viel schneller als mit zwei const char* (Zeiger auf Anfang und Ende) wird es wohl nicht werden.
Wenn du keine Digraphen/Trigraphen o.ä. verwendest könntest du in der Token Liste dann auch einfach Zeiger auf den originalen Input-String abspeichern, damit würdest du dir einiges an dynamischer Speicheranforderung sparen.

Wenns dir also um beste Runtime Performance geht, halte ich das Arbeiten mit Zeigern für eine gute Idee

Klingt gut der Ansatz, wird mich aber erstmal einiges an hirnschmalz kosten. Ich hatte so etwas bereits in C# implementiert, jedoch mehr oder weniger rudimentär (und langsam bis zum erbrechen) und bräuchte da erstmal einen konkreten Denkanstoss für c++. Wie würde ich am besten Anfangen sagen wir mal überhaupt erstmal das Pattern einzulesen und dann damit die ersten tokens aus einem eingabestring zu bekommen?

volkard

WAS kostet denn da so voel Zeit?
Allokierungen, sagen wir mal 100 Takte pro new, dann packt er 10Mio Tokens pro Sekunde. Sollte nicht das Problem sein.
Oder sind es die String-Vergleiche, um zu schauen, was man mit dem Token dann machen will?

Die beiden Zeiger halte ich auch für sehr gut.

hustbaer

@volkard
Naja kommt drauf an welche Grössenordnung von "schnell" man anstrebt.
Es gibt z.B. XML-Parser die von der Grössenordnung her vergleichbar mit strlen() sind.
Das bekommt man nie im Leben hin wenn man anfängt das File in Teilstrings zu zerhacken die man als std::string abspeichert.

volkard schrieb:

Allokierungen, sagen wir mal 100 Takte pro new, dann packt er 10Mio Tokens pro Sekunde. Sollte nicht das Problem sein.

Mach mal nen Benchmark.
Bzw. sollte ich auch nochmal machen. Das letzte mal als ich geguckt hab war noch auf nem älteren XP ohne Low-Fragmentation-Heap.
Und da waren das viel viel mehr als 100 Takte. Eher so 2000+.

Pria

was wäre denn die beste methode um sowas effizient zu speichern?

hustbaer

Die effizienteste Methode wären "geborgte Strings". Quasi ein Ding was den Anfang und Ende eines Strings kennt, den Speicher aber nicht besitzt.

Wie sowas aussehen könnte kannst du z.B. diesem Paper entnehmen:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3334.html#classstd_1_1basic__string__ref

Im klassischen Fall Parser kann man diese string_ref Dinger - wie sie in dem oben verlinkten Proposal heissen - dann einfach direkt in den Speicherbereich des Source-Files verweisen lassen.
Dazu muss man natürlich garantieren dass der Speicher nicht freigegeben wird so lange man noch mit diesen string_ref Dinger arbeitet. Was im Normalfall aber kein Problem darstellen sollte.

Die Frage ist aber ob sich der Aufwand lohnt. In den meisten Fällen wird wohl an anderen Stellen schon so viel Zeit draufgehen, dass man den Unterschied den man mit so einer Optimierung rausholen kann kaum merkt.

theta

Ev. lohnt es sich auch mal ein Blick in den Sourcecode von Pugixml zu werfen.

Pria

ich habe das System so konzipiert, dass nur mit und auf char-pointern gearbeitet wird und maximal für die indexierung ein int-pointer, daraus extrahiere ich sowohl bei der pattern zerlegung, als auch beim parservorgang die entsprechenden codezeilen ohne irgendwas ausser pointern zu speichern.

die performance ist bislang ganz ok

das problem nun ist, dass ich die struktur noch irgendwie festhalten muss. Die Frage ist jetzt inwieweit ich z.b. einen Binär- oder AVL-Baum dazu nutzen kann oder welche struktur ich dafür verwenden sollte oder reicht auch eine verkettete liste?

hustbaer

Pria schrieb:

das problem nun ist, dass ich die struktur noch irgendwie festhalten muss. Die Frage ist jetzt inwieweit ich z.b. einen Binär- oder AVL-Baum dazu nutzen kann oder welche struktur ich dafür verwenden sollte oder reicht auch eine verkettete liste?

Stellt sich die Frage was du mit dieser Struktur dann machen willst.
Und wie Aufbau-Performance <-> Verwende-Performance zu gewichten ist.

Grundsätzlich kann man so nen AST sogar mit einfachen und superschnellen Zeiger-Weiterschiebe-Pool-Allokatoren aufbauen. Also zumindest so lange er nach dem Parsen nicht modifizierbar sein muss.

Ist aber natürlich auch aufwendiger als einfach std::vector , std::map & Friends zu verwenden.

Also hier wieder die Frage ob es sich auszahlt.

volkard

Der AST gibt doch von selber vor, wie er gespeichert sein will.

volkard

Das führt zu nichts. Eine Atomtabelle wird die geborgten Strings (mit Hash-Werten) versägen, rate ich mal. Strings müssen nicht quasi instant gespeichert werden können, sondern quasi instant erkannt werden können, oder sehe ich das falsch? Bin aber hier raus, weil mir die Dame nicht antwortet.

Pria

hustbaer schrieb:

Grundsätzlich kann man so nen AST sogar mit einfachen und superschnellen Zeiger-Weiterschiebe-Pool-Allokatoren aufbauen. Also zumindest so lange er nach dem Parsen nicht modifizierbar sein muss.

Ist aber natürlich auch aufwendiger als einfach std::vector , std::map & Friends zu verwenden.

Der Aufwand wärs mir wert und natürlich brauch der Baum danach nicht mehr modifiziert zu werden sondern wird dann so entsprechend weitergereicht.

wie sähe denn soetwas ungefähr aus?

hustbaer

volkard schrieb:

Eine Atomtabelle wird die geborgten Strings (mit Hash-Werten) versägen, rate ich mal. Strings müssen nicht quasi instant gespeichert werden können, sondern quasi instant erkannt werden können, oder sehe ich das falsch?

Hm. Auch möglich. Die geborgten Strings sind toll wenn es viele viele verschiedene Strings gibt. Was ja gerade bei Sourcecode nicht wirklich der Fall ist, da wird ja viel wiederholt - selbst Bezeichner kommen ja typischerweise mehr als 1x vor.

Und mit der Atomtabelle kann man wieder nen schnellen Zeiger-Weiterschiebe Allokator verwenden, weil man am Schluss ja eh nur die ganze Tabelle auf einmal wegwirft.

Müsste man ausprobieren, aber ich behaupte mal du könntest da richtig liegen

hustbaer

Pria schrieb:

wie sähe denn soetwas ungefähr aus?

Wo genau hast du Schwierigkeiten dir etwas vorzustellen?

hustbaer schrieb:

Und mit der Atomtabelle kann man wieder nen schnellen Zeiger-Weiterschiebe Allokator verwenden, weil man am Schluss ja eh nur die ganze Tabelle auf einmal wegwirft.

Meinst du mit den "schnellen Zeiger-Weiterschiebe Allokatoren" die gute alte std::deque?

hustbaer

@deck
Nein.

Ich meine sowas in der Art (grob skizziert):

// Im Headerfile
namespace {

    inline size_t MakeAlignmentMask(size_t size)
    {
        static const size_t masks[MAX_ALIGNMENT] = {
            ~size_t(0), ~size_t(1), ~size_t(3), ~size_t(7), ... };

        if (size < MAX_ALIGNMENT)
            return masks[size];
        else
            return MAX_ALIGNMENT;
    }

} // namespace

// Im Headerfile
inline void* FastPoolAllocator::Allocate(size_t size)
{
    // Neuen Block besorgen wenn nötig
    if (size > m_offset)
        GetNewBlock(size);
    assert(m_offset >= size);

    // "Zeiger" weiterschieben
    m_offset -= size;
    m_offset &= GetAlignmentMask(size);

    // Tadaaa - fertig

    return m_currentBlockBegin + m_offset;
}

// Egal wo
void FastPoolAllocator::GetNewBlock(size_t size)
{
    size_t const blockSize = size > m_defaultBlockSize ? size : m_defaultBlockSize;
    m_blocks.reserve(m_blocks.size() + 1); // Sicherstellen dass push_back nicht fehlschlägt

    m_currentBlockBegin = static_cast<char*>(::operator new(blockSize));
    m_offset = blockSize;
    m_blocks.push_back(m_currentBlockBegin);
}

void FastPoolAllocator::~FastPoolAllocator()
{
    // Alle Blöcke freigeben
    // ...
}

// Deallokationsfunktion gibt's keine, weil immer nur der ganze Pool auf einmal weggeworfen werden kann
// Bzw. man könnte zu Debuggingzwecken eine Deallokationsfunktion machen die z.B. einfach nur mitzählt
// wie viele Blöcke freigegeben wurden (und in der Allokationsfunktion natürlich auch mitzählen wie viele angefordert wurden).
// In Releasebuilds sollte die Deallokationsfunktion aber nicht auftauchen. Bzw. maximal inline als leere Funktion definiert sein, damit sie hübsch rausoptimiert wird.

Viel schneller als das wirds nicht.

Den if (size > m_offset) Test kann man theoretisch loswerden wenn man vorher weiss wie viel Speicher maximal benötigt wird. Evtl. könnte man hier auch Guard-Pages verwenden, aber das wird dann schon reichlich funky.

Dann bleibt lediglich noch die Alignment-Sache. Hier könnte man max. noch fixes Alignment verwenden. Könnte aber sein dass man dadurch sogar langsamer wird, weil man den Cache dann schlechter ausnutzt.

hustbaer

Wobei ich selber immer einer von denen bin, die predigen dass hochoptimierte generische Allokatoren schon sehr schnell sind, und man kaum nen nennenswerten Vorteil durch spezialisierte Allokatoren rausholen kann.

Ich bin zwar (*aus-dem-fenster-lehn*) sicher dass man, wenn man nur die Allokationen betrachtet, mit so einem Weiterschiebe-Allokator auf deutlich weniger als 50% der Laufzeit kommt als mit dem besten generischen Allokator. Vermutlich sogar weniger als 25%. Aber selbst wenn er 5x schneller ist... 5x "quasi nix" tut auch nicht sehr weh, wenn man dazwischen deutlich mehr als "nix" macht.