64비트 정수에서 모든 집합 비트의 위치를 반환하는 가장 빠른 방법은 무엇입니까?

64비트 정수에서 모든 집합 비트의 위치를 반환하는 가장 빠른 방법은 무엇입니까?

저는 64비트 정수에서 모든 1비트의 위치를 얻는 빠른 방법이 필요합니다.를 들어, 를들어진, 어주예가 ,x = 123703배을열고싶다니습채우.idx[] = {0, 1, 2, 4, 5, 8, 9, 13, 14, 15, 16}비트 a priori의 수를 알고 있다고 가정할 수 있습니다.이것은 10~10회로¹⁵ 불릴¹² 것이므로 속도가 중요합니다.제가 지금까지 생각해낸 가장 빠른 대답은 64비트 정수의 각 바이트를 인덱스로 사용하여 해당 바이트에 설정된 비트 수와 해당 바이트의 위치를 제공하는 테이블로 사용하는 괴물성입니다.

int64_t x;            // this is the input
unsigned char idx[K]; // this is the array of K bits that are set
unsigned char *dst=idx, *src;
unsigned char zero, one, two, three, four, five;  // these hold the 0th-5th bytes
zero  =  x & 0x0000000000FFUL;
one   = (x & 0x00000000FF00UL) >> 8;
two   = (x & 0x000000FF0000UL) >> 16;
three = (x & 0x0000FF000000UL) >> 24;
four  = (x & 0x00FF00000000UL) >> 32;
five  = (x & 0xFF0000000000UL) >> 40;
src=tab0+tabofs[zero ]; COPY(dst, src, n[zero ]);
src=tab1+tabofs[one  ]; COPY(dst, src, n[one  ]);
src=tab2+tabofs[two  ]; COPY(dst, src, n[two  ]);
src=tab3+tabofs[three]; COPY(dst, src, n[three]);
src=tab4+tabofs[four ]; COPY(dst, src, n[four ]);
src=tab5+tabofs[five ]; COPY(dst, src, n[five ]);

COPY최대 8바이트까지 복사할 수 있는 스위치 문입니다.n로 설정된 와 바이에비수 배다니입열의 입니다.tabofs을 오셋을 제합니다공으로 합니다.tabXX번째 바이트에서 설정된 비트의 위치를 유지합니다.이것은 제온 E5-2609의 언롤드 루프 기반 방법보다 약 3배 더 빠릅니다. (아래 참조)현재 반복 중입니다.x지정된 비트 집합 수에 대한 사전순서입니다.

더 좋은 방법이 있습니까?

편집: 예제를 추가했습니다(나중에 수정했습니다).전체 코드는 http://pastebin.com/79X8XL2P 에서 사용할 수 있습니다. 참고: -O2를 사용하는 GCC는 최적화를 제거하는 것처럼 보이지만 인텔의 컴파일러는 그렇지 않습니다.

또한 아래의 의견 중 일부를 해결하기 위해 추가적인 배경을 제공하겠습니다.목표는 가능한 N개의 설명 변수의 우주에서 가능한 모든 K 변수의 부분 집합에 대해 통계 검정을 수행하는 것입니다. 현재 구체적인 목표는 N=41이지만, 최대 45-50까지 N이 필요한 일부 프로젝트를 볼 수 있습니다.검정에는 기본적으로 해당 데이터 하위 행렬의 인수 분해가 포함됩니다.의사 코드에서는 다음과 같은 것이 있습니다.

double doTest(double *data, int64_t model) {
  int nidx, idx[];
  double submatrix[][];
  nidx = getIndices(model, idx);  // get the locations of ones in model
  // copy data into submatrix
  for(int i=0; i<nidx; i++) {
    for(int j=0; j<nidx; j++) {
      submatrix[i][j] = data[idx[i]][idx[j]];
    }
  }
  factorize(submatrix, nidx);
  return the_answer;
}

안에 이 했습니다. 중 ~한 인텔파보위드일해다이니버이약전을의딩습했를다니집보내게그하순중진코시합이다니간해에료안야완케를스이일=55▁is▁a▁i10-▁time▁naive-▁in▁the인%▁that▁ph▁spent▁the▁this▁for의다보▁a▁in▁of41▁coded니집▁which▁an▁version▁up▁~내▁15▁of중10▁should▁~▁case텔▁days▁n▁complete41게▁of%하▁intel순▁15진약getIndices()따라서 빠른 버전을 사용하면 하루 또는 그 이상을 절약할 수 있습니다.저도 NVidia Kepler를 위한 구현 작업을 하고 있지만, 불행히도 제가 안고 있는 문제(어처구니없는 수의 작은 행렬 연산)는 하드웨어(어처구니없이 큰 행렬 연산)에 이상적으로 적합하지 않습니다.즉, 본 논문은 매트릭스의 차원이 컴파일 시간에 정의된다는 경고와 함께 루프를 공격적으로 풀고 레지스터에서 전체 인수 분해를 수행하여 내 크기의 매트릭스에서 수백 GFLOPS/s를 달성하는 것처럼 보이는 솔루션을 제시합니다.(이 루프 언롤링은 Phi 버전에서도 오버헤드를 줄이고 벡터화를 개선하는 데 도움이 될 것입니다.getIndices()더욱 중요해질 것입니다!)그래서 이제 제 커널은 다음과 같이 보여야 한다고 생각합니다.

double *data;  // move data to GPU/Phi once into shared memory
template<unsigned int K> double doTestUnrolled(int *idx) {
  double submatrix[K][K];
  // copy data into submatrix
  #pragma unroll
  for(int i=0; i<K; i++) {
    #pragma unroll
    for(int j=0; j<K; j++) {
      submatrix[i][j] = data[idx[i]][idx[j]];
    }
  }
  factorizeUnrolled<K>(submatrix);
  return the_answer;
}

Phi 버전은 모델=0에서^N 2(또는 테스트를 위한 하위 집합)까지 'cilk_for' 루프에서 각 모델을 해결하지만, 이제 GPU에 대한 일괄 작업과 커널 발사 오버헤드를 상각하려면 K=1에서 41비트 세트 각각에 대해 모델 번호를 사전 순서로 반복해야 합니다(Doynax가 언급한 대로).

EDIT 2: 이제 방학이 끝났으니, 여기 icc 버전 15를 사용한 제온 E5-2602에 대한 몇 가지 결과가 있습니다.벤치마크에 사용한 코드는 http://pastebin.com/XvrGQUat 입니다. 정확히 K비트가 설정된 정수에 대해 비트 추출을 수행하기 때문에 아래 표의 "기본" 열에서 측정한 사전 기록 반복에 대한 오버헤드가 있습니다.이러한 작업은 N=48을 사용하여 2회 수행됩니다³⁰(필요에 따라 수행됨)

" 고유의 "CTZ" 는 gcc 내인루프입다니는하용사를 __builtin_ctzll가장 낮은 순서의 비트 세트를 얻으려면:

for(int i=0; i<K; i++) {
    idx[i] = __builtin_ctzll(tmp);
    lb = tmp & -tmp;    // get lowest bit
    tmp ^= lb;      // remove lowest bit from tmp
} 

Mark는 Mark의 루프에 대한 분기가 없습니다.

for(int i=0; i<K; i++) {
    *dst = i;
    dst += x & 1;
    x >>= 1;
} 

Tab1은 다음과 같은 복사 매크로가 있는 원래 테이블 기반 코드입니다.

#define COPY(d, s, n) \
switch(n) { \
case 8: *(d++) = *(s++); \
case 7: *(d++) = *(s++); \
case 6: *(d++) = *(s++); \
case 5: *(d++) = *(s++); \
case 4: *(d++) = *(s++); \
case 3: *(d++) = *(s++); \
case 2: *(d++) = *(s++); \
case 1: *(d++) = *(s++); \
case 0: break;        \
}

Tab2는 Tab1과 동일한 코드이지만 복사 매크로는 단일 복사본으로 8바이트만 이동합니다(doynax 및 Lưu Vĩnh Phuc의 아이디어를 가져옵니다...그러나 이것이 정렬을 보장하지는 않습니다.):

#define COPY2(d, s, n) { *((uint64_t *)d) = *((uint64_t *)s); d+=n; }

여기 결과가 있습니다.Tab1이 CTZ보다 3배 더 빠르다는 제 초기 주장은 (제가 테스트하던) 큰 K에만 적용되는 것 같습니다.마크의 루프는 내 원래 코드보다 빠르지만, 브랜치를 제거하는 것은COPY2매크로는 K > 8에 대한 케이크를 가져갑니다.

 K    Base    CTZ   Mark   Tab1   Tab2
001  4.97s  6.42s  6.66s 18.23s 12.77s
002  4.95s  8.49s  7.28s 19.50s 12.33s
004  4.95s  9.83s  8.68s 19.74s 11.92s
006  4.95s 16.86s  9.53s 20.48s 11.66s
008  4.95s 19.21s 13.87s 20.77s 11.92s
010  4.95s 21.53s 13.09s 21.02s 11.28s
015  4.95s 32.64s 17.75s 23.30s 10.98s
020  4.99s 42.00s 21.75s 27.15s 10.96s
030  5.00s 100.64s 35.48s 35.84s 11.07s
040  5.01s 131.96s 44.55s 44.51s 11.58s

여기서 성능의 핵심은 랜덤 정수에서 비트 위치를 미세하게 최적화하는 것보다 더 큰 문제에 초점을 맞추는 것이라고 생각합니다.

샘플 코드와 이전 SO 질문으로 판단하면 K 비트가 순서대로 설정된 모든 단어를 열거하고 이 중에서 비트 인덱스를 추출하는 것입니다.이것은 문제를 크게 단순화합니다.

그렇다면 각 반복은 비트 위치를 재구성하는 대신 비트 배열의 위치를 직접 증가시킵니다.이 시간의 절반은 단일 루프 반복과 증가를 수반합니다.

다음과 같은 것들이 있습니다.

// Walk through all len-bit words with num-bits set in order
void enumerate(size_t num, size_t len) {
    size_t i;
    unsigned int bitpos[64 + 1];

    // Seed with the lowest word plus a sentinel
    for(i = 0; i < num; ++i)
        bitpos[i] = i;
    bitpos[i] = 0;

    // Here goes the main loop
    do {
        // Do something with the resulting data
        process(bitpos, num);

        // Increment the least-significant series of consecutive bits
        for(i = 0; bitpos[i + 1] == bitpos[i] + 1; ++i)
            bitpos[i] = i;
    // Stop on reaching the top
    } while(++bitpos[i] != len);
}

// Test function
void process(const unsigned int *bits, size_t num) {
    do
        printf("%d ", bits[--num]);
    while(num);
    putchar('\n');
}

특별히 최적화되지는 않았지만 일반적인 아이디어를 얻을 수 있습니다.

여기 테스트 없이는 알 수 없는 더 빠른 매우 간단한 것이 있습니다.대부분은 설정된 비트 수와 설정되지 않은 비트 수에 따라 달라집니다.분기를 완전히 제거하기 위해 이 기능을 해제할 수 있지만 오늘날의 프로세서를 사용하면 속도가 빨라질지 모르겠습니다.

unsigned char idx[K+1]; // need one extra for overwrite protection
unsigned char *dst=idx;
for (unsigned char i = 0; i < 50; i++)
{
    *dst = i;
    dst += x & 1;
    x >>= 1;
}

추신: 질문의 샘플 출력이 잘못되었습니다. http://ideone.com/2o032E 을 참조하십시오.

최소한의 수정으로:

int64_t x;            
char idx[K+1];
char *dst=idx;
const int BITS = 8;
for (int i = 0 ; i < 64+BITS; i += BITS) {
  int y = (x & ((1<<BITS)-1));
  char* end = strcat(dst, tab[y]); // tab[y] is a _string_
  for (; dst != end; ++dst)
  {
    *dst += (i - 1); // tab[] is null-terminated so bit positions are 1 to BITS.
  }
  x >>= BITS;
}

의 BITS테이블의 크기를 결정합니다. 8, 13 및 16은 논리적 선택입니다.각 항목은 0으로 종단되고 오프셋이 1개인 비트 위치를 포함하는 문자열입니다.즉, 탭[5]은"\x03\x01"내부 루프가 이 오프셋을 고정합니다.

더 약더효적: 교체간을 합니다.strcat 안쪽 루프 by 리고내 프루그 by 부▁loop리.

char const* ptr = tab[y];
while (*ptr)
{
   *dst++ = *ptr++ + (i-1);
}

루프에 분기가 포함된 경우 루프를 풀면 분기 예측 변수에 도움이 되지 않기 때문에 루프가 약간 번거로울 수 있습니다.그 결정은 기꺼이 컴파일러에게 맡기겠습니다.

한 가지 고려하고 있는 것은tab[y]문자열에 대한 포인터 배열입니다.합니다: 다은매유사니다합우음다니."\x1"는 의접사니다입미의 입니다."\x3\x1" 사, 시로 각은 실, 하작지로 시작합니다."\x8"는 을 나타내는 문자열의 접미사입니다.이 몇 나 필요한지까지 필요한지 궁금합니다.tab[y]사실은 필요합니다.예를 들어 위의 논리에 따르면,tab[128+x] == tab[x]-1.

[편집]

쓰지 , 당신은 의 탭 합니다. 다음으로 시작하는 128개의 탭 항목이 필요합니다."\x8"절대 다른 문자열의 접미사가 아니기 때문입니다.그도래.tab[128+x] == tab[x]-1할 수 두 명령을 저장할 수 .char const* ptr = tab[x & 0x7F] - ((x>>7) & 1)(설定)tab[]다음을 가리키다\x8)

char를 사용하면 속도를 높이는 데 도움이 되지 않지만 실제로 계산하는 동안 더 많은 AND와 부호/제로 확장이 필요한 경우가 많습니다.캐시에 적합해야 하는 매우 큰 어레이의 경우에만 더 작은 int 유형을 사용해야 합니다.

다른 개선할 수 있는 것은 복사 매크로입니다.가능하면 바이트 단위로 복사하는 대신 전체 단어를 복사

inline COPY(unsigned char *dst, unsigned char *src, int n)
{
switch(n) { // remember to align dst and src when declaring
case 8:
    *((int64_t*)dst) = *((int64_t*)src);
    break;
case 7:
    *((int32_t*)dst) = *((int32_t*)src);
    *((int16_t*)(dst + 4)) = *((int32_t*)(src + 4));
    dst[6] = src[6];
    break;
case 6:
    *((int32_t*)dst) = *((int32_t*)src);
    *((int16_t*)(dst + 4)) = *((int32_t*)(src + 4));
    break;
case 5:
    *((int32_t*)dst) = *((int32_t*)src);
    dst[4] = src[4];
    break;
case 4:
    *((int32_t*)dst) = *((int32_t*)src);
    break;
case 3:
    *((int16_t*)dst) = *((int16_t*)src);
    dst[2] = src[2];
    break;
case 2:
    *((int16_t*)dst) = *((int16_t*)src);
    break;
case 1:
    dst[0] = src[0];
    break;
case 0:
    break;
}

또한 [x] 및 n[x] 탭은 서로 가까이 액세스하는 경우가 많으므로 항상 동시에 캐시에 있는지 확인하기 위해 메모리에 탭을 가까이 둡니다.

typedef struct TAB_N
{
    int16_t n, tabofs;
} tab_n[256];

src=tab0+tab_n[b0].tabofs; COPY(dst, src, tab_n[b0].n);
src=tab0+tab_n[b1].tabofs; COPY(dst, src, tab_n[b1].n);
src=tab0+tab_n[b2].tabofs; COPY(dst, src, tab_n[b2].n);
src=tab0+tab_n[b3].tabofs; COPY(dst, src, tab_n[b3].n);
src=tab0+tab_n[b4].tabofs; COPY(dst, src, tab_n[b4].n);
src=tab0+tab_n[b5].tabofs; COPY(dst, src, tab_n[b5].n);

것은, 마막으중건한요로지▁last.gettimeofday성능 계산을 위한 것이 아닙니다.대신 Query Performance Counter를 사용하면 훨씬 정확합니다.

코드가 1바이트(256개 항목) 인덱스 테이블을 사용하고 있습니다.2바이트(65536엔트리) 인덱스 테이블을 사용하면 2배 속도를 높일 수 있습니다.

안타깝게도 3바이트 테이블 크기는 16MB로 CPU 로컬 캐시에 들어가지 않으며 속도만 느려질 수 있습니다.

세트 비트의 수가 희소하다고 가정하면,

int count = 0;
unsigned int tmp_bitmap = x;        
while (tmp_bitmap > 0) {
    int next_psn = __builtin_ffs(tmp_bitmap) - 1;
    tmp_bitmap &= (tmp_bitmap-1);
    id[count++] = next_psn;
}

문제는 당신이 직위들의 수집을 어떻게 할 것인가 하는 것입니다.
만약 여러분이 그것을 여러 번 반복해야 한다면, 네, 지금처럼 그것들을 한 번 모아서 많은 것을 반복하는 것이 흥미로울 수도 있습니다.
그러나 한 번 또는 몇 번만 반복하기 위한 것이라면, 중간 위치 배열을 만들지 않고 비트에서 반복하는 동안 발생한 각 1에서 처리 블록 폐쇄/함수를 호출하는 것이 좋습니다.

다음은 제가 Smalltalk에서 쓴 비트 반복기의 순진한 예입니다.

LargePositiveInteger>>bitsDo: aBlock
| mask offset |
1 to: self digitLength do: [:iByte |
    offset := (iByte - 1) << 3.
    mask := (self digitAt: iByte).
    [mask = 0]
        whileFalse:
            [aBlock value: mask lowBit + offset.
            mask := mask bitAnd: mask - 1]]

LargePositiveInteger는 바이트 숫자로 구성된 임의 길이의 정수입니다.lowBit는 가장 낮은 비트의 순위에 응답하며 256개의 항목이 있는 룩업 테이블로 구현됩니다.

C++ 2011에서는 마감을 쉽게 통과할 수 있으므로 번역이 쉬울 것입니다.

uint64_t x;
unsigned int mask;
void (*process_bit_position)(unsigned int);
unsigned char offset = 0;
unsigned char lowBitTable[16] = {0,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0}; // 0-based, first entry is unused
while( x )
{
    mask = x & 0xFUL;
    while (mask)
    {
        process_bit_position( lowBitTable[mask]+offset );
        mask &= mask - 1;
    }
    offset += 4;
    x >>= 4;
}

이 예제는 4비트 테이블로 설명되지만 캐시에 맞는 경우 13비트 이상으로 쉽게 확장할 수 있습니다.

분기 예측을 위해, 내부 루프는 다음과 같이 다시 작성될 수 있습니다.for(i=0;i<nbit;i++)를 nbit=numBitTable[mask]스위치를 사용하여 언롤링합니다(컴파일러가 할 수 있습니까?). 하지만 먼저 성능을 측정할 수 있습니다.

이것이 너무 느린 것으로 밝혀졌습니까?
조잡하지만CPU .

void mybits(uint64_t x, unsigned char *idx)
{
  unsigned char n = 0;
  do {
    if (x & 1) *(idx++) = n;
    n++;
  } while (x >>= 1);          // If x is signed this will never end
  *idx = (unsigned char) 255; // List Terminator
}

루프를 풀고 64개의 참/거짓 값 배열을 생성하는 것이 여전히 3배 더 빠릅니다(이것은 원하는 것이 아닙니다).

void mybits_3_2(uint64_t x, idx_type idx[])
{
#define SET(i) (idx[i] = (x & (1UL<<i)))
  SET( 0);
  SET( 1);
  SET( 2);
  SET( 3);
  ...
  SET(63);
}

여기 1바이트(8비트)용으로 작성된 엄격한 코드가 있지만, 64비트로 쉽게 확장될 것입니다.

int main(void)
{
    int x = 187;

    int ans[8] = {-1,-1,-1,-1,-1,-1,-1,-1};
    int idx = 0;

    while (x)
    {
        switch (x & ~(x-1))
        {
        case 0x01: ans[idx++] = 0; break;
        case 0x02: ans[idx++] = 1; break;
        case 0x04: ans[idx++] = 2; break;
        case 0x08: ans[idx++] = 3; break;
        case 0x10: ans[idx++] = 4; break;
        case 0x20: ans[idx++] = 5; break;
        case 0x40: ans[idx++] = 6; break;
        case 0x80: ans[idx++] = 7; break;
        }

        x &= x-1;
    }

   getchar();
   return 0;
}

출력 배열은 다음과 같아야 합니다.

ans = {0,1,3,4,5,7,-1,-1};

"64비트 정수에서 모든 비트의 위치를 빠르게 가져올 수 있는 방법이 필요합니다"를 문자 그대로 받아들인다면...

나는 이것이 몇 주 전의 일이라는 것을 알고 있지만, 호기심으로, 나는 CBM64와 아미가와의 조립 시절에 산술 시프트를 사용한 다음 캐리 플래그를 검토했던 것을 기억합니다. - 만약 그것이 설정되었다면 시프트 비트는 1이었고, 명확하다면 0입니다.

예: 왼쪽 산술 시프트(비트 64에서 비트 0으로 이동)의 경우...

pseudo code (ignore instruction mix etc errors and oversimplification...been a while):

    move #64+1, counter
    loop. ASL 64bitinteger       
    BCS carryset
    decctr. dec counter
    bne loop
    exit

    carryset. 
    //store #counter-1 (i.e. bit position) in datastruct indexed by counter
    jmp decctr

...당신이 그 생각을 이해하기를 바랍니다.

그 이후로 어셈블리를 사용하지 않았지만 위와 유사한 C++ 인라인 어셈블리를 사용하여 여기서 비슷한 작업을 할 수 있는지 궁금합니다.적절한 데이터 구조를 구축하여 전체 변환을 어셈블리(극소수의 코드 행)로 수행할 수 있습니다.C++는 단순히 답을 검토할 수 있습니다.

만약 이것이 가능하다면 저는 그것이 꽤 빠르다고 생각합니다.

로그 및 전원 공급 기능의 시간에 따라 간단한 솔루션이지만 가장 빠르지는 않을 수 있습니다.

#include<math.h>

void getSetBits(unsigned long num){

    int bit;
    while(num){
        bit = log2(num);
        num -= pow(2, bit);

        printf("%i\n", bit); // use bit number
    }
}

복잡도 O(D) | D는 설정 비트의 수입니다.

언급URL : https://stackoverflow.com/questions/20713017/what-is-the-fastest-way-to-return-the-positions-of-all-set-bits-in-a-64-bit-inte