Gestione memoria senza rami?

Question

Qualcuno ha pensato a come scrivere un gestore di memoria (in C++) completamente privo di diramazioni? Ho scritto un pool, uno stack, una coda e una lista collegata (allocata dal pool), ma mi chiedo quanto sia plausibile scrivere un gestore di memoria generale senza branch.

Questo è tutto per contribuire a creare un framework davvero riutilizzabile per fare una solida CPU concomitante, in-order e cache friendly.

Modifica: da branchless intendo senza effettuare chiamate di funzione dirette o indirette e senza utilizzare ifs. Ho pensato che probabilmente potrei implementare qualcosa che prima modifica la dimensione richiesta a zero per le chiamate false, ma in realtà non ha ottenuto molto di più. Sento che non è impossibile, ma l'altro aspetto di questo esercizio è quindi di profilarlo su detti processori "ostili" per vedere se vale la pena provare così tanto per evitare la ramificazione.

Answer 1

Mentre io non credo che questo sia una buona idea, una soluzione sarebbe quella di avere secchi pre-assegnati dei vari log dimensioni, stupido pseudocodice:

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; 
}; 

(Si sarebbe naturalmente anche sostituire lo std::vector con un semplice array + contatore).

MODIFICA: Per rendere questo robusto (ovvero gestire la situazione in cui il bucket è vuoto), è necessario aggiungere qualche forma di diramazione.

EDIT2: Ecco una piccola funzione branchless log2:

//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 
} 

Questo dà il risultato corretto per le allocazioni < 33.554.432 byte. Se hai bisogno di allocazioni più grandi dovrai passare al doppio.

Ecco uno link su come i numeri in virgola mobile sono rappresentati in memoria.

Answer 2

L'unico modo che conosco per creare un allocatore senza diramazione è di riservare tutta la memoria che potenzialmente utilizzerà in anticipo. Altrimenti ci sarà sempre qualche codice nascosto da vedere se stiamo superando una certa capacità attuale, sia che si trovi in ​​un file nascosto push_back in un vettore che verifica se la dimensione supera la capacità utilizzata per implementarla o qualcosa del genere.

Ecco un esempio di questo tipo di allocazione fissa che ha un metodo malloc e free completamente privo di diramazioni.

class FixedAlloc 
{ 
public: 
    FixedAlloc(int element_size, int num_reserve) 
    { 
     element_size = max(element_size, sizeof(Chunk)); 
     mem = new char[num_reserve * element_size]; 

     char* ptr = mem; 
     free_chunk = reinterpret_cast<Chunk*>(ptr); 
     free_chunk->next = 0; 

     Chunk* last_chunk = free_chunk; 
     for (int j=1; j < num_reserve; ++j) 
     { 
      ptr += element_size; 
      Chunk* chunk = reinterpret_cast<Chunk*>(ptr); 
      chunk->next = 0; 
      last_chunk->next = chunk; 
      last_chunk = chunk; 
     } 
    } 

    ~FixedAlloc() 
    { 
     delete[] mem; 
    } 

    void* malloc() 
    { 
     assert(free_chunk && free_chunk->next && "Reserve memory exhausted!"); 
     Chunk* chunk = free_chunk; 
     free_chunk = free_chunk->next; 
     return chunk->mem; 
    } 

    void free(void* mem) 
    { 
     Chunk* chunk = static_cast<Chunk*>(mem); 
     chunk->next = free_chunk; 
     free_chunk = chunk; 
    } 

private: 
    union Chunk 
    { 
     Chunk* next; 
     char mem[1]; 
    }; 
    char* mem; 
    Chunk* free_chunk; 
}; 

Dal momento che è totalmente senza rami, è segfaults semplicemente se si tenta di allocare più memoria di quanto inizialmente riservati. Ha anche un comportamento indefinito per provare a liberare un puntatore nullo. Ho anche evitato di occuparmi dell'allineamento per semplificare l'esempio.