Effiziente Stringzerlegung (Parser)

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.

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.