다중 비트 패턴에 대한 스캔 비트 배열

Question

현재 할당 요청이있을 때 비트 맵 (배열 uint8_t)에 의해 지원되는 메모리 할당기를 작성하고 있습니다. 0에서 n 비트까지 비트 맵 순차를 스캔하고 요청을 이행 할 수있는 공간. (비트 1은 0으로 표시된 페이지가 사용 된 페이지를 나타냅니다.) 공간을 한 번에 한 비트 씩 검색하는 대신 전체 배열을 더 빠르게 스캔하는 기술이 있습니까? 즉, 3 페이지 메모리 요청이 도착하면 하나의 배열에서 000 패턴을 검색하고 싶습니다. 이상적으로 루프를 수행하지 않습니까?

추신 : 내가 사용하고있는 컴파일러에서는 사용할 수 없으므로 std::bitset을 사용하고 있지 않습니다. AFAIK는 여러 비트를 검색하지 못하게합니다.

EDIT : 비트는 8Y이트 (비트 당 1 비트)가 인코딩 된 uint8_t 하나의 바이트로 패킹됩니다.

Answer 1

하나의 빈 페이지를 스캔하려면 한 번에 한 바이트 씩 전체 바이트를 반복하고 255보다 작은 지 확인하십시오. 크기가 더 작은 경우 적어도 하나의 제로 비트가 있습니다. 한 번에 32 또는 64 비트 (부호없는 정수)를 스캔 한 다음 uint 내부의 검색 범위를 좁히는 것이 좋습니다.

비트를 최적화하려면 첫 번째 바이트를 0 비트로 추적하고 페이지를 비울 때 해당 위치를 업데이트하십시오. 무료 페이지를 할당하면 위양성이 떨어질 수 있지만 적어도 다음에 스캔을 시작할 때부터 시작할 수 있습니다.

데이터 구조에 따라 큰 블록을 2의 거듭 제로 정렬하려는 경우 여러 페이지의 스캔을 최적화 할 수 있습니다. 예를 들어, 당신은 단지 전체 바이트가 제로가되는 검사 것이다, 8 페이지를 할당합니다 :

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. 

이 방법, 당신은 바이트/UINT32/UINT64에서 0의 범위 중복에 대해 걱정할 필요가 (또는 확인)하지 않는 경계.

각 유형에 대해 첫 번째 자유 블록이있는 시작 위치를 유지/업데이트 할 수 있습니다.

Answer 2

귀하의 질문에 대한 완전한 대답이 아니지만 다음 기능이 도움이되기를 바랍니다.

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

    return iVal != I(-1); 
} 

(I 올바르게 작성한 경우) 그것은 반환 true경우 (없는 경우) iVal 적어도 num 연속 제로 비트가 있습니다. T이 작업 폼 UINT16 그래서 난 그룹 UINT16에 2 바이트 다음 창을 한 바이트를 밀어 다음에 바이트에서의 트란 지션을 설명 할 수있는 것 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 
}