Tableau de bits de balayage pour le modèle de bits multiples

Question

J'écris un allocateur de mémoire qui est soutenu par une carte de bits (tableau de uint8_t) actuellement quand une demande d'allocation arrive je scanne le bitmap séquentiel de 0 à n bits et recherche un espace qui peut répondre à la demande. (un bit 1 indique que la page utilisée est 0) est maintenant libre) Maintenant, au lieu de chercher un espace un bit à la fois, y a-t-il une technique pour scanner le tableau plus rapidement? si une demande de mémoire de 3 pages arrive, je voudrais chercher 000 motif dans le tableau en une seule fois idéalement sans boucle? PS: Je n'utilise pas std::bitset car il n'est pas disponible pour le compilateur que j'utilise. Je pense que cela ne me permet pas de chercher plusieurs bits aussi.

EDIT: Les bits sont compressés en octets. Un uint8_t a 8 pages (1 par bit) codées.

Answer 1

Pour rechercher une page vide, vous pouvez parcourir le tableau de bits un octet complet à la fois et vérifier si elle est inférieure à 255. Si elle est plus petite, il y a au moins un bit zéro. Mieux encore, numériser 32 ou 64 bits (ints non signés) à la fois, puis affiner la recherche à l'intérieur de l'uint.

Pour optimiser un bit, vous pouvez suivre le premier octet avec un bit zéro (et mettre à jour cette position lors de la libération d'une page). Cela pourrait donner un faux positif une fois que vous aurez alloué cette page gratuite, mais au moins la prochaine fois que l'analyse commencera là au lieu de commencer au début.

Une numérisation de plusieurs pages peut être optimisée si vous souhaitez aligner des blocs plus gros sur une puissance de 2 (en fonction de vos structures de données). Par exemple, pour allouer 8 pages, vous ne rechercher un octet complet étant nul:

1 page: scan for any zero bit (up to 64 bits at a time) 
2 pages: scan for 2 zero bits at bit position 0,2,4,6 
3-4 pages: scan for zero nibble (for 3 pages, the fourth would be available for 1 page then) 
5-8 pages: scan for an empty byte 

for each of the above, you could first scan 64 bits at a time. 

De cette façon, vous n'avez pas à vous soucier (ou vérifier) ​​se chevauchent zéro plages à l'octet/uint32/uint64 limites.

Pour chaque type, une position de départ avec le premier bloc libre pourrait être conservée/mise à jour.

Answer 2

Pas une réponse complète à votre question (je suppose) mais j'espère que la fonction suivante peut aider.

template <typename I> 
bool scan_n_zeros (I iVal, std::size_t num) 
{ 
    while (--num) 
     iVal |= ((iVal << 1) | I{1}); 

    return iVal != I(-1); 
} 

Il retourne (si je l'ai écrit correctement) truesi (pas où) il y a au moins num bit zéro consécutif iVal.

Ce qui suit est un exemple de travail complet quand T est uint8_t

#include <iostream> 

template <typename I> 
bool scan_n_zeros (I iVal, std::size_t num) 
{ 
    while (--num) 
     iVal |= ((iVal << 1) | I{1}); 

    return iVal != I(-1); 
} 

int main() 
{ 
    uint8_t u0 { 0b00100100 }; 
    uint8_t u1 { 0b00001111 }; 
    uint8_t u2 { 0b10000111 }; 
    uint8_t u3 { 0b11000011 }; 
    uint8_t u4 { 0b11100001 }; 
    uint8_t u5 { 0b11110000 }; 

    std::cout << scan_n_zeros(u0, 2U) << std::endl; // print 1 
    std::cout << scan_n_zeros(u0, 3U) << std::endl; // print 0 
    std::cout << scan_n_zeros(u1, 4U) << std::endl; // print 1 
    std::cout << scan_n_zeros(u1, 5U) << std::endl; // print 0 
    std::cout << scan_n_zeros(u2, 4U) << std::endl; // print 1 
    std::cout << scan_n_zeros(u2, 5U) << std::endl; // print 0 
    std::cout << scan_n_zeros(u3, 4U) << std::endl; // print 1 
    std::cout << scan_n_zeros(u3, 5U) << std::endl; // print 0 
    std::cout << scan_n_zeros(u4, 4U) << std::endl; // print 1 
    std::cout << scan_n_zeros(u4, 5U) << std::endl; // print 0 
    std::cout << scan_n_zeros(u5, 4U) << std::endl; // print 1 
    std::cout << scan_n_zeros(u5, 5U) << std::endl; // print 0 
}