Gestionnaire de mémoire sans branchement?

Question

Quelqu'un a-t-il pensé à écrire un gestionnaire de mémoire (en C++) complètement libre de toute branche? J'ai écrit un pool, une pile, une file d'attente et une liste chaînée (allouée à partir du pool), mais je me demande comment il est plausible d'écrire un gestionnaire de mémoire générale sans branche.

Ceci est tout pour aider à faire un cadre vraiment réutilisable pour faire en même temps solide, en ordre CPU et le cache de développement convivial.

Edit: Je veux dire par sans sans branches faire des appels de fonction directe ou indirecte, et sans utiliser ifs. J'ai pensé que je pourrais probablement implémenter quelque chose qui change d'abord la taille demandée à zéro pour les faux appels, mais qui n'a pas vraiment beaucoup plus que cela. Je pense qu'il est impossible, mais l'autre aspect de cet exercice est le profilage alors sur lesdits processeurs « hostiles » pour voir si cela vaut la peine d'essayer aussi dur que cela pour éviter de branchement.

Answer 1

Bien que je ne pense pas que ce soit une bonne idée, une solution serait d'avoir des seaux préalloués de divers journal tailles, stupide pseudocode:

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

(Vous feriez bien sûr aussi remplacez le std::vector par un simple tableau + compteur).

EDIT: Pour rendre ceci robuste (c'est-à-dire gérer la situation où le godet est vide), vous devrez ajouter une forme de branchement.

EDIT2: Voici une petite fonction log2 de branches:

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

Cela donne le résultat correct pour les allocations < 33554432 octets. Si vous avez besoin d'allocations plus importantes, vous devrez passer en double.

Voici un link à la façon dont les nombres à virgule flottante sont représentés en mémoire.

Answer 2

La seule façon que je connaisse pour créer un allocateur vraiment est de réserver sans agence toute la mémoire, il utilisera potentiellement à l'avance. Sinon, il y aura toujours un code caché quelque part pour voir si nous dépassons la capacité actuelle, que ce soit dans un push_back caché dans un vecteur qui vérifie si la taille dépasse la capacité utilisée pour l'implémenter ou quelque chose de ce genre.

Voici un exemple grossier d'allocation fixe qui a une méthode complètement sans branches malloc et free.

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

Comme il est tout à fait sans agence, il segfaults simplement si vous essayez d'allouer plus de mémoire que initialement réservée. Il a également un comportement indéfini pour essayer de libérer un pointeur nul. J'ai également évité de traiter avec l'alignement pour un exemple plus simple.