Branchless Speichermanager?

Question

Hat jemand darüber nachgedacht, wie man einen Speichermanager (in C++) schreibt, der komplett branchfrei ist? Ich habe einen Pool, einen Stack, eine Warteschlange und eine verkettete Liste (Zuweisung aus dem Pool) geschrieben, aber ich frage mich, wie plausibel es ist, einen Zweig-freien General-Speicher-Manager zu schreiben.

Dies ist alles, was dazu beiträgt, ein wirklich wiederverwendbares Framework für eine solide, gleichzeitige, in-order-CPU- und Cache-freundliche Entwicklung zu schaffen.

Edit: von Branchless ich meine, ohne direkte oder indirekte Funktionsaufrufe und ohne Wenns zu tun. Ich habe gedacht, dass ich wahrscheinlich etwas implementieren kann, das zuerst die angeforderte Größe für falsche Anrufe auf Null ändert, aber nicht wirklich viel mehr als das hat. Ich fühle, dass es nicht unmöglich ist, aber der andere Aspekt dieser Übung ist dann profilieren es auf besagten "unfreundlichen" Prozessoren, um zu sehen, ob es sich lohnt, so hart zu versuchen, um Verzweigungen zu vermeiden.

Answer 1

Während ich glaube nicht, das ist eine gute Idee, würde eine Lösung sein vorab zugewiesene Eimer verschiedenen Protokoll Größen dumm Pseudo-Code haben: auch

class Allocator { 

    void* malloc(size_t size) { 
     int bucket = log2(size + sizeof(int)); 
     int* pointer = reinterpret_cast<int*>(m_buckets[bucket].back()); 
     m_buckets[bucket].pop_back(); 
     *pointer = bucket; //Store which bucket this was allocated from 
     return pointer + 1; //Dont overwrite header 
    } 

    void free(void* pointer) { 
     int* temp = reinterpret_cast<int*>(pointer) - 1; 
     m_buckets[*temp].push_back(temp); 
    } 

    vector< vector<void*> > m_buckets; 
}; 

(Sie würde natürlich Ersetzen Sie die std::vector durch einen einfachen Array + Zähler).

EDIT: Um dies robust (d. H. Behandeln die Situation, wo der Eimer leer ist) müssen Sie eine Form der Verzweigung hinzufügen.

EDIT2: Hier ist eine kleine branchless log2 Funktion:

//returns the smallest x such that value <= (1 << x) 
int 
log2(int value) { 
    union Foo { 
     int x; 
     float y; 
    } foo; 
    foo.y = value - 1; 
    return ((foo.x & (0xFF << 23)) >> 23) - 126; //Extract exponent (base 2) of floating point number 
} 

Dies gibt das richtige Ergebnis für die Zuweisungen < 33.554.432 Bytes. Wenn Sie größere Zuweisungen benötigen, müssen Sie zu Doppel wechseln.

Hier ist ein link, wie Gleitkommazahlen im Speicher dargestellt werden.

Answer 2

Die einzige Weise, die ich kenne, um einen wirklich zellenlosen Zuordner zu erstellen, ist, den ganzen Speicher zu reservieren, den es möglicherweise im Voraus verwenden wird. Sonst wird es immer irgendeinen versteckten Code geben, um zu sehen, ob wir die aktuelle Kapazität überschreiten, ob es nun in einem versteckten push_back in einem Vektor ist, der prüft, ob die Größe die Kapazität überschreitet, die verwendet wird, um es zu implementieren oder etwas Ähnliches.

Hier ist ein solches grobes Beispiel für eine feste Zuordnung, die eine vollständig branchless malloc und free Methode hat.

Da es völlig zweiglos ist, segfold es einfach, wenn Sie versuchen, mehr Speicher zuzuweisen als ursprünglich reserviert. Es hat auch undefiniertes Verhalten für den Versuch, einen Nullzeiger freizugeben. Ich habe es auch vermieden, sich mit der Ausrichtung zu befassen, um ein einfacheres Beispiel zu geben.