비트 필드의 모든 빈 슬롯을 방문하십시오.

Question

저는 uint64의 배열을 가지고 있으며 설정되지 않은 모든 비트 (0s)에 대해 몇 가지 평가를 수행합니다.

평가는 대단히 비싸지 만 매우 적은 비트가 설정되지 않았습니다. 프로파일 링은 발견 할 때 다음 번 설정되지 않은 비트 논리에 많은 시간을 소비한다고 말합니다.

(Core2duo에서) 더 빠른 방법이 있습니까?

for(int y=0; y<height; y++) { 
    uint64_t xbits = ~board[y]; 
    int x = 0; 
    while(xbits) { 
    if(xbits & 1) { 
     ... with x and y 
    } 
    x++; 
    xbits >>= 1; 
    } 
} 

(약 방법/SIMD/CUDA는-ISE에이 흥미로운 접한다면 어떤 토론!) 내가 제안

Answer 1

다음은 빠른 마이크로 벤치 마크입니다. 시스템 통계를 얻을 수 있다면 실행하고 자신의 알고리즘을 추가하십시오!

명령 줄 :

g++ -o bit_twiddle_mirco_opt bit_twiddle_mirco_opt.cpp -O9 -fomit-frame-pointer -DNDEBUG -march=native 

그리고 코드 :

#include <stdio.h> 
#include <stdlib.h> 
#include <sys/time.h> 
#include <stdint.h> 

static unsigned long get_usecs() { 
    struct timeval tv; 
    gettimeofday(&tv,NULL); 
    return tv.tv_sec*1000000+tv.tv_usec; 
} 

enum { MAX_HEIGHT = 64 }; 
uint64_t board[MAX_HEIGHT]; 
int xsum, ysum; 

void evaluate(int x,int y) { 
    xsum += x; 
    ysum += y; 
} 

void alphaneo_unrolled_8(int height) { 
    for(int y=0; y < height; y++) { 
     uint64_t xbits = ~board[y]; 
     int x = 0;  
     while(xbits) { 
      if(xbits & (1 << 0)) 
       evaluate(x,y); 
      if(xbits & (1 << 1)) 
       evaluate(x+1,y); 
      if(xbits & (1 << 2)) 
       evaluate(x+2,y); 
      if(xbits & (1 << 3)) 
       evaluate(x+3,y); 
      if(xbits & (1 << 4)) 
       evaluate(x+4,y); 
      if(xbits & (1 << 5)) 
       evaluate(x+5,y); 
      if(xbits & (1 << 6)) 
       evaluate(x+6,y); 
      if(xbits & (1 << 7)) 
       evaluate(x+7,y); 
      x+=8; 
      xbits >>= 8; 
     } 
    } 
} 

void will_while(int height) { 
    for(int y=0; y<height; y++) { 
     uint64_t xbits = ~board[y]; 
     int x = 0; 
     while(xbits) { 
      if(xbits & 1) 
       evaluate(x,y); 
      xbits >>= 1; 
      x++; 
     } 
    } 
} 

void will_ffs(int height) { 
    for(int y=0; y<height; y++) { 
     uint64_t xbits = ~board[y]; 
     int x = __builtin_ffsl(xbits); 
     while(x) { 
      evaluate(x-1,y); 
      xbits >>= x; 
      xbits <<= x; 
      x = __builtin_ffsl(xbits); 
     } 
    } 
} 

void rnd_board(int dim) { 
    for(int y=0; y<dim; y++) { 
     board[y] = ~(((uint64_t)1 << dim)-1); 
     for(int x=0; x<dim; x++) 
      if(random() & 1) 
       board[y] |= (uint64_t)1 << x; 
    } 
} 

void test(const char* name,void(*func)(int)) { 
    srandom(0); 
    printf("testing %s... ",name); 
    xsum = ysum = 0; 
    const unsigned long start = get_usecs(); 
    for(int i=0; i<100000; i++) { 
     const int dim = (random() % MAX_HEIGHT) + 1; 
     rnd_board(dim); 
     func(dim); 
    } 
    const unsigned long stop = get_usecs(); 
    printf("%lu usecs (check %d,%d)\n",stop-start,xsum,ysum); 
} 

int main() { 
    test("will_while()",will_while); 
    test("will_ffs()",will_ffs); 
    test("alphaneo_unrolled_8()",alphaneo_unrolled_8); 
    return 0; 
} 

Answer 2

:

내 현재 코드는 고 1의 제비를 건너 뛸 수 있습니다 특정 값에서 어떤 비트가 명확한지를 알려주는 일종의 조회 테이블 (사용 가능한 리소스에 따라 바이트 별 또는 단락)을 사용합니다.

Answer 3

나는이 8 개 계산에 7 루프 체크, 7 개 추가, 7 이동을 제거하면

for(int y=0; y < height; y++) { 

    uint64_t xbits = ~board[y]; 
    int x = 0; 

    while(xbits) { 
     if(xbits & (1 << 0)) { 
      ... with x and y 
     } 
     if(xbits & (1 << 1)) { 
      ... with x and y 
     } 
     if(xbits & (1 << 2)) { 
      ... with x and y 
     } 
     if(xbits & (1 << 3)) { 
      ... with x and y 
     } 
     if(xbits & (1 << 4)) { 
      ... with x and y 
     } 
     if(xbits & (1 << 5)) { 
      ... with x and y 
     } 
     if(xbits & (1 << 6)) { 
      ... with x and y 
     } 
     if(xbits & (1 << 7)) { 
      ... with x and y 
     } 
     x+=8; 
     xbits >>= 8; 
    } 
} 

뭔가를 시도 할 수있는 루프 풀기와 같은 몇 가지 최적화 점, 생각할 수

...

그들은 예를 들어 설정되어 있다면, 그냥 연속 1 개의를 무시 생각할 수

또 다른 방법

while (xbits) { 

    if (xbits & 0xF) { 

      // Process for the four bits !!! 
    } 

    xbits >>= 4; 
} 

경고 : 비트가 너무 많이 흩어져 있으면 위의 방법으로 작업 속도가 느려질 수 있습니다 .-(

Answer 4

모든 바이트를 한 번에 처리 할 수있는 테이블을 고려한 적이 있습니까? 본질적으로 단일 첨자 조작으로 바이트에 설정되지 않은 "x"값의 목록을 검색합니다 (실제 "x"를 얻기 위해 8 * byte-within-uint64를 추가 할 것임)

한 바이트를 사용하여 1-8 비트 숫자 값 하나를 저장함으로써 (이 비트를 압축 할 수는 있지만 값을 가지도록하는 이점은 다소 우위를 점할 수 있음), 최대 값을 가질 것이라고 가정함으로써 4 개의 0 값 비트 (더 많은 0 비트를 갖는 바이트 값은 이스케이프 코드로 코드화 될 수 있는데, 이는 종래의 비트 논리를 트리거 할 수 있으며, 이는 그러한 이벤트의 낮은 확률을 감안할 때 허용 될 수 있음), 256 * 4 바이트 = 1k

Answer 5

Hacker's Delight은 루프 언롤 이진 검색을 제안합니다. 그다지 빠르지는 않지만 드문 ds/바이트/니블/등. 모든 비트가 설정됩니다.

불행하게도 Core2 Duo가 아닌 Phenom을 얻을 수있는 경우 POPCNT를 사용하여 빠른 비트 수 집합 비트 함수를 작성할 수 있습니다. 그런 다음에 다음 해제 비트의 인덱스 얻을 수 있습니다 :

pop(x & (~x-1)) 

x & (~x-1) 다음 제로 비트 위의 설정 비트를 지 웁니다; POPCNT를 사용하여 나머지 비트를 계산하면됩니다.

여기 바이트와 가공 한 예입니다 : 당신이 조립할 수 사용하고자하는 경우

01101111 x 
    10010000 ~x 
    10001111 ~x-1 
    00001111 x & ~x-1 
pop(00001111) => 4 

Answer 6

, BSF (비트 스캔 앞으로) 작업이 사용하는 것입니다. 그래도 1 비트를 찾았으므로 비트 마스크를 반전시켜야합니다.IIRC에서 XOR은 결과가 0이면 제로 플래그를 설정하므로 BSF를 시도하기 전에 해당 플래그를 테스트 할 수 있습니다. x86에서 BSF는 32 비트 레지스터에서 작동하므로 값을 분할해야합니다. (하지만 처음에는 32 비트 정수를 사용해야합니다.)

Answer 7

하나의 접근법 - 니블로 분할 한 다음 스위치를 사용하여 니블에서 비트를 선택하십시오. 선택한 비트가 컴파일 타임에 알려지고 코드를 풀 수 있도록 템플릿을 사용하십시오.

template < int i, int x > 
struct process_bit { 
    inline static void apply (int y) { }; 
}; 

template < int x > 
struct process_bit < 1, x > { 
    inline static void apply (int y) { 
     evaluate (x, y); 
    } 
}; 

template < int x, int n > 
inline void process_nibble_bits (int y) { 
    process_bit < x & 1, n >::apply(y); 
    process_bit < (x >> 1) & 1, n + 1 > ::apply(y); 
    process_bit < (x >> 2) & 1, n + 2 > ::apply(y); 
    process_bit < (x >> 3) & 1, n + 3 > ::apply(y); 
} 


template < int n > 
inline void process_nibble (uint64_t xbits, int y) { 
    uint64_t nibble = (xbits >> n) & 0xf; 
    if (nibble) { 
     switch (nibble) { 
      case 0: 
      process_nibble_bits < 0, n > (y); 
      break; 
      case 1: 
      process_nibble_bits < 1, n > (y); 
      break; 
      case 2: 
      process_nibble_bits < 2, n > (y); 
      break; 
      case 3: 
      process_nibble_bits < 3, n > (y); 
      break; 
      case 4: 
      process_nibble_bits < 4, n > (y); 
      break; 
      case 5: 
      process_nibble_bits < 5, n > (y); 
      break; 
      case 6: 
      process_nibble_bits < 6, n > (y); 
      break; 
      case 7: 
      process_nibble_bits < 7, n > (y); 
      break; 
      case 8: 
      process_nibble_bits < 8, n > (y); 
      break; 
      case 9: 
      process_nibble_bits < 9, n > (y); 
      break; 
      case 10: 
      process_nibble_bits < 10, n > (y); 
      break; 
      case 11: 
      process_nibble_bits < 11, n > (y); 
      break; 
      case 12: 
      process_nibble_bits < 12, n > (y); 
      break; 
      case 13: 
      process_nibble_bits < 13, n > (y); 
      break; 
      case 14: 
      process_nibble_bits < 14, n > (y); 
      break; 
      case 15: 
      process_nibble_bits < 15, n > (y); 
      break; 
     } 
    } 
} 

template < int i, int n > 
struct bit_tree { 
    inline static void apply (uint64_t xbits, int y) { 
     // each call to here represents scan of bits in [ n, n + 2i) 
     bit_tree <i>> 1, n > ::apply(xbits, y); 
     bit_tree <i>> 1, n + i > ::apply(xbits, y); 
    }; 
}; 


template < int i, int n > 
struct bit_tree_with_guard { 
    inline static void apply (uint64_t xbits, int y) { 
     // each call to here represents scan of bits in [ n, n + 2i) 
     // so this branch to execute if any in [ n, n + i) are set 

     if (xbits & (((((uint64_t) 1LL) << i) - 1) << n)) 
      bit_tree <i>> 1, n > ::apply(xbits, y); 

     if (xbits & (((((uint64_t) 1LL) << i) - 1) << (n + i))) 
      bit_tree <i>> 1, n + i > ::apply(xbits, y); 
    }; 
}; 

// put guards on 8 and 16 bit blocks (for some reason using inheritance is slower) 
template < int n > 
struct bit_tree < 8, n > { 
    inline static void apply (uint64_t xbits, int y) { 
     bit_tree_with_guard < 8, n > ::apply (xbits, y); 
    } 
}; 
template < int n > 
struct bit_tree < 16, n > { 
    inline static void apply (uint64_t xbits, int y) { 
     bit_tree_with_guard < 16, n > ::apply (xbits, y); 
    } 
}; 


template < int n > 
struct bit_tree < 2, n > { 
    inline static void apply (uint64_t xbits, int y) { 
     process_nibble <n> (xbits, y); 
    } 
}; 


void template_nibbles(int height) { 
    for (int y = 0; y < height; y++) { 
     uint64_t xbits = ~board[y]; 
     bit_tree< 32, 0>::apply (xbits, y); 
    } 
} 

는 최대한 빨리 FFS 버전과 아니에요 실행,하지만 다른 휴대용 것보다 터치 더 나은, 그리고 결과에 그들과 함께 일관되게 나타납니다

$ bin\bit_twiddle_micro_opt.exe            
testing will_while()... 3375000 usecs (check 1539404233,1539597930)   
testing will_ffs()... 2890625 usecs (check 675191567,1001386403)    
testing alphaneo_unrolled_8()... 3296875 usecs (check 1539404233,1539597930) 
testing template_nibbles()... 3046875 usecs (check 1539404233,1539597930)  

모든 나무를 사용하여 길은 어떤 이득도주지 않는 것처럼 보입니다. 니블 스위치를 사용하지 않으면 속도가 느려집니다. 누구든지 C++만을 사용하여 손으로 16 가지 경우를 작성하지 않아도되는 방법을 알고 있습니까?

Answer 8

다른 답변이 좋다.

당신은 최하위 1 비트를 찾는 루프를 다음 단어를 반전하고, 수 :

int x = something; 

int lsb = x^((x-1) & x); 

i.e. if x = 100100 
a = (x - 1) = 100011 // these two steps turn off the lsb 
b = (a & x) = 100000 
c = (x^b) = 000100 // this step detects the lsb 
lsb = c 

그런 다음 작업이 완료되면, 말할 제로에 대한 x ^= lsb 및 테스트를 할 여기 내 기여합니다.

lsb (실제 비트)를 비트 수로 바꾸려면 조회 테이블 또는 언 롤드 이진 검색이 필요한 것일 수 있습니다.

원하는 것을 원하십니까?

Answer 9

당신이 설정되지 않은 비트,

if (xbits != ((uint64_t)-1)) 
{ 
    // regular code goes here 
} 

는 승리 할 것입니다 아마도 간단한 드문 일이 될 것이라고 생각합니다. 그런 식으로 일반적인 경우 (단어의 모든 비트가 설정되어 있음) 한 번에 64 비트를 건너 뛸 수 있습니다.

Answer 10

귀하의 프로파일 링은 대부분 내부 while 루프에서 시간을 보내고 있음을 나타내거나 ~ board [y] 계산을 수행 한 다음 y를 즉시 증가시키는 데 소비하고 있습니까?

후자 인 경우 두 번째 레벨 비트 맵을 사용하는 것이 더 좋을 수 있습니다.지도의 각 비트가 보드 비트 맵에서 전체 64b 단어를 제거합니다. 그러면 앞으로 더 공정한 비트를 건너 뛸 수 있습니다. 운이 좋으면 비트 맵의 ​​전체 캐시 라인을로드하지 않아야합니다.

비트 맵에 설정된 비트 수는 어떻게됩니까?

Answer 11

룩업 테이블 버전의 변형 : 8 비트의 다음 unset 비트에 대한 찾아보기 테이블이 있습니다. 8 비트 블록을 검사하고 AND와 0xFF를 비교하여 결과가 여전히 0xFF인지 비교합니다. 그렇다면 표를 건너 뛰고 그렇지 않으면 건너 뜁니다.

Answer 12

설정되지 않은 비트가 거의 없다면 비트 필드를 전혀 사용하지 않고 스파 스 표현을 사용하십시오. 그 말은, 각 unset 비트의 인덱스를 포함하는 정수 배열을 유지하는 것입니다. 설정되지 않은 비트를 반복하는 것은 배열을 반복하는 것입니다. 비트 설정 및 삭제는 더욱 복잡해 지지만 설정되지 않은 비트를 찾는 것이 가장 비용이 많이 드는 작업 인 경우 스파 스 표현을 사용하면 성공할 수 있습니다.