✔ [C++/STL] Miserable Performance mit std::map

[cwriter]

Hi

Ich weiss nicht, ob dies eine Frage oder eine Aussage werden soll.
Also beginne ich einfach mal mit meinen Beobachtungen:
Ich schreibe an einem Simulator für den RPi 1 B.
Dazu gehört offensichtlicherweise das Lesen und Ausführen von ARM-Instruktionen, was auf x86-Chips relativ aufwendig ist (>100 Bytes an x86-Code PRO ARM-Instruktion (wobei natürlich die MMU-Simulation recht viel dazu beiträgt). Entsprechend komme ich gerade mal auf 0.4 MIPS bei der Simulation auf einem modernen Skylake-Prozessor @ 2.4 GHz, während der ARM1176-jzfs @ 700 MHz im RPi knapp 1000 MIPS schafft.
Um dies zu umgehen (und ein bisschen mehr Leistung rauszukitzeln), habe ich zusätzlich einen Umkompilierer geschrieben, der die Instruktionen im Voraus übersetzt und dadurch merklich (gefühlt 10x) schneller ist als die Instruktion-für-Instruktion-Variante. Nun kann (und will) ich nicht alles Umkompilieren, da ich später auch Einzelschritte durch den Code will machen können. Das führt aber zum Problem, dass Branches (Jumps) im Voraus nicht umkompiliert werden können, denn ein Jump könnte aus einem vorkompilierten Block herausspringen - wo dann die langsamere Emulation wieder einspringen muss. Allerdings führte das zu extremen Leistungseinbussen, da die virtuelle (vereinfachte) Pipeline wieder gefüllt werden musste, die Register wieder angepasst werden mussten (z.B. x86 Status Register musste zum CPSR kopiert werden) usw.
Daher fügte ich Code ein, der die ARM-Adressen auf die x86 Adressen ummappen sollte, sodass bei Branches sehr viel Overhead entfiel.
Ich realisierte das mit einer std::map von ARM-Adresse auf x86-Adresse, und freute mich ob der erhaltenen Performance.
Irgendwann mass ich die Geschwindigkeit, kam auf die 0.4 MIPS und war sehr beschämt, da ich auf 10x langsamer gehofft und 500x langsamer erwartet hatte, die Simulation tatsächlich aber 5000x langsamer war.
Also schmiss ich Callgrind an und erhielt folgendes Bild:

Darin als einziges die Funktion: __gnu_cxx::__normal_iterator.
Der (leicht vereinfachte) Code:

auto x86addr = ret->getInstMap().find(ARM-addr);
size_t retval = size_t(((uint8_t*)ret->getCodeBaseAddr()) + x86_addr->second);
return retval;

Ich machte daraufhin 2 Optimierungen:
1) Ich cache die Adressen in einem Vektor, da wahrscheinlich dieselbe Adresse oft neu gebraucht wird
2) Ich Cache pro umkompilierten Abschnitt (statt wie bisher global in allen Abschnitten nach der Adresse zu suchen), da ein Codeabschnitt wahrscheinlich nicht alle anderen Bereiche braucht.

Code:

size_t CodeChunk::cached_resolve(size_t ARM_addr)
{
    //This function should be more efficient than the Recompiler::resolve function due to Chunk-local caches (it seems more likely that a function will call the same functions over and over)

    if(m_resolve_cache.size() > 0)
    {
        auto rnd = m_resolve_cache_iterator;
        do
        {
            if(std::get<0>(m_resolve_cache[m_resolve_cache_iterator]) == ARM_addr)
            {
                return std::get<1>(m_resolve_cache[m_resolve_cache_iterator]);
            }
        } while(rnd != (m_resolve_cache_iterator = (m_resolve_cache_iterator + 1) % m_resolve_cache.size()));
    }
    size_t resolv = m_recomp->resolve(ARM_addr);
    m_resolve_cache.push_back(std::tuple<size_t, size_t>(ARM_addr, resolv));
    return resolv;
}
//...
std::vector<std::tuple<size_t, size_t>> m_resolve_cache;

Das Resultat: (TL;DR: Die Auflösung ist komplett von der ersten "Seite" an Kosten verschwunden, einzig das miss-resolve ist noch zu finden, allerdings verschwindend bei längerer Laufzeit und bei weitem nicht mehr so teuer wie zuvor).



Nun zur eigentlichen Frage / Aussage:
Ja, es ist eine Optimierung, und nein, man kann vom Standard nicht wirklich "perfekte" Performance in jedem Fall erwarten. Aber sowas finde ich dann schon echt fragwürdig.
Wofür ist std::map dann noch gut?
1) Es ist langsamer als ein (mehr oder weniger klug angelegter) std::vector.
2) Für grosse Maps sollte man ohnehin optimierte Datenbanken wie sqlite, postgres, mysql und Co. verwenden.
3) const maps können locker als sortierte Arrays implementiert und damit sehr viel günstiger sein.

Also was heisst das nun?
Für mich heisst es: Finger weg von std::map.
Was heisst es für den Leser? Habe ich eine falsche Analyse gemacht, falsche Schlüsse gezogen oder mache ich etwas generell falsch? Kann ich noch mehr optimieren? Verwendet der Leser std::maps und wenn ja, warum?


Gruss
cwriter

 

[sheel]

Hi

grad nur für was kurzes Zeit, aber:

a) Wofür ist std::iota gut? ... Im Standard ist einges, was imho 99% überflüssig ist. std::map kommt da noch gut weg.
b) Für große DBs ist man nicht immer in der Lage, eine DB nachzurüsten (egal ob es wegen der Plattform oder Firmenregeln zu externen Abhängigkeiten oder ...) ist

 

[cwriter]

a) Wofür ist std::iota gut? ... Im Standard ist einges, was imho 99% überflüssig ist. std::map kommt da noch gut weg.

Ich denke, es gibt hier 2 Bereiche:
1) Überflüssig weil selten verwendet / notwendig / in wenigen Minuten selbst zu schreiben (std::iota)
2) Fehlleitend wie std::map. Man lernt: "Hat man sortierbare Schlüssel, dann ist eine Map gut geeignet, da balancierter Baum." Was man aber lernen sollte, ist: "Algorithmen sind Pflasterwerk. Arrays gewinnen durch Cache-Locality immer".
Und klar, für 0815 Terminkalender o.ä. wird std::map völlig i.O. sein und man spart sich die halbe Stunde, sich was besseres auszudenken, aber einen SQL-Server (mit Hauptlast SELECTs) würde ich mir nach dieser Erfahrung nicht mit std::maps zusammenbauen wollen.
Das einzige, was ich mir noch vorstellen kann, sind schnellere Inserts (wobei das nur eine Vermutung ist, die Rebalancierung eines Baumes kostet auch...)

b) Für große DBs ist man nicht immer in der Lage, eine DB nachzurüsten (egal ob es wegen der Plattform oder Firmenregeln zu externen Abhängigkeiten oder ...) ist

Naja, benutzt man freiwillig eine (Standard)-Map für eine Datenbank? Und wenn ja, wofür? Alles mit low-latency-Anforderungen fällt ja alleine durch fehlende Cache-Locality weg.
Und sich einer externen Datenbank zu verweigern... Naja, bei kleinen Datenmengen ( < 50 GB) mag das ja noch einigermassen gehen, aber darüber dürfte die Effizienz doch zu leiden beginnen.

Jedenfalls erinnert mich das Ganze ein bisschen an die Geschichte von std::list und Stroustrup, der in einem Talk erklärt, dass std::sort auf std::list ein Vielfaches langsamer als std::sort auf std::vector ist, obwohl man doch lerne, dass häufiges Verschieben bei Listen schneller ist.

Gruss
cwriter