Effiziente Stringzerlegung (Parser)

Pria

was ist der ast denn genau für eine art baum?

hustbaer

Du willst nen AST aufbauen, und weisst nichtmal was das ist?
Eieiei...

http://en.wikipedia.org/wiki/Abstract_syntax_tree

volkard

hustbaer schrieb:

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.

Durch Spezialisieren kriegt man Fallunterscheidungen weg, Mutexe; und man bekommt ein wenig mehr Speicherlokalität (beim Parser-Lauf hüpfen Seiten der Atomtabelle in den Speicher, beim Simulationslauf hüpfen sie alle wieder raus).

Trie::Node* allocNode(){
   //Alignment steht fest
   //size steht auch fest
   //signethreaded, ätsch
   if(last==end)
      allocPage();
   return last++;

Was man nun drunterlegt, ist eher egal.

q.push_back(Trie::Node());
   return &*q.last();

Aber selbst wenn er 5x schneller ist... 5x "quasi nix" tut auch nicht sehr weh, wenn man dazwischen deutlich mehr als "nix" macht.

Jo, wenn new/delete vorher nur 5% der gesamten Laufzeit brauchten, kann man die Allokatoren so hoch optimieren, wie man will, man wird nicht mehr als 5% der gesamten Laufzeit sparen können.

Bei unvorstellbar vielen Strings würde der Pool auch nicht soo viel Prozente mehr Speed bringen, aber evtl das Minütchen am Ende sparen, wenn der gesamte Baum wieder gelöscht wird, wenn jeder Speicherbereich angefaßt wird, um ihn auszuketten.

hustbaer

Ja, klar, wenn man für jede Node-Art nen eigenen Pool macht wird es noch schneller. Mutexen weg ist sowieso klar - wobei das auch general-purpose Allokatoren schon können (Thread-Caches und so - einmal alle 100 oder 1000 Allocations ne Mutex locken tut nicht sehr weh).

Ich vermute auch dass der Unterschied zwischen einem Pool pro Node-Art vs. einen einzigen Variable-Size-Pool relativ gering ausfallen wird.
Müsste man aber auch alles ausprobieren, einfach so behaupten trau' ich mich das nicht. Gerade die Sache mit Cache-Lokalität kann ich schwer abschätzen. Das eine zusätzliche "if" + Table-Lookup + "and" ist sicher kaum spürbar.

Bzw. man könnte dem Compiler auch noch etwas helfen das "if" + Table-Lookup wegzumachen, zumindest wenn er inlinen kann:

#ifdef MAX_ALIGN == 16
    inline size_t MakeAlignmentMask(size_t size) // constexpr?
    {
        return size <= 4 ?
            (
                size <= 2 ? ~(size-1) : ~size_t(3)
            )
            :
            (
                size <= 8 ? ~size_t(7) : ~size_t(15)
            );
    }
#elif MAX_ALIGN == 8
    inline size_t MakeAlignmentMask(size_t size)
//...

Und wenn er nicht inlinen kann, dann ist der Funktionsaufruf vermutlich viel teurer als die zwei "ifs" die durch die "?" entstehen.

volkard

hustbaer schrieb:

Und da waren das viel viel mehr als 100 Takte. Eher so 2000+.

Hmm.

hustbaer

Ich hab' ja geschrieben ich müsste das nochmal probieren.
Ich glaube das war mit XP mit dem alten XP Allokator, der bekanntermassen ziemlich lahm ist.

Der LFH sollte das viel besser können.