인접 단어 시퀀스에서 임의의 비트 범위를 추출하는 가장 효율적인 방법은 무엇입니까?

Question

std::vector 또는 uint64_t 요소를 저장하는 다른 시퀀스 컨테이너 (경우에 따라 deque)가 있다고 가정합니다.

이제이 벡터를 연속 비트 인 size() * 64의 시퀀스로 보겠습니다. 주어진 [begin, end) 범위의 비트에 의해 형성된 단어를 찾으려면 end - begin <= 64이 주어 지므로 단어가 맞습니다.

제가 지금 가지고있는 해결책은 결과를 구성하는 두 단어를 찾아 개별적으로 마스크하고 결합합니다. 이후 가능한 한 효율적으로,이 모든 코드를 if 브랜치 mispredictions 발생하지 않도록 코드를 시도했습니다, 그래서 예를 들어, 코드는 모두 전체 범위가 단어에 맞는 때 또는 두 때 걸쳐 작동합니다 단어, 다른 경로를 취하지 않고. 이렇게하려면 >> 및 << 연산자와 같이 지정된 금액만큼 단어를 이동하지만 n이 64보다 큰 경우 정상적으로 처리하는 함수 인 shiftl 및 shiftr 함수를 코딩해야합니다. 그렇지 않으면 정의되지 않은 동작입니다. .

또 다른 요점은 코드화 된 것처럼 get() 함수가 수학적 의미에서 공백 범위에도 사용할 수 있다는 것입니다. begin == end뿐만 아니라 begin> end 인 경우에도이 함수를 호출하는 주 알고리즘에 필요합니다. 다시 말하지만, 저는이 경우 단순히 분기하고 0을 반환하지 않고이 작업을 시도했습니다.

그러나 어셈블리 코드를 보면 이러한 모든 작업이 너무 단순 해 보이기 때문에 너무 단순 해 보입니다. 이 코드는 성능이 중요한 알고리즘에서 실행됩니다.이 알고리즘은 너무 느리게 실행됩니다. valgrind이 함수는 2 억 3 천만 번 호출되었고 총 실행 시간의 40 %를 차지하므로 더 빨리 수행해야합니다.

이 작업을 수행하는 더 간단하고 효율적인 방법을 찾도록 도와 줄 수 있습니까? 너무 커서에 대해 많이 신경 쓰지 않습니다. g++ 및 clang 모두를 사용하여 컴파일 할 수있는 한 x86 SIMD 내장 함수 (SSE3/4/AVX ecc ...) 또는 컴파일러 내장 함수를 사용하는 솔루션은 괜찮습니다.

내 현재 코드는 아래에 포함되어 있습니다 :

using word_type = uint64_t; 
const size_t W = 64; 

// Shift right, but without being undefined behaviour if n >= 64 
word_type shiftr(word_type val, size_t n) 
{ 
    uint64_t good = n < W; 

    return good * (val >> (n * good)); 
} 

// Shift left, but without being undefined behaviour if n >= 64 
word_type shiftl(word_type val, size_t n) 
{ 
    uint64_t good = n < W; 

    return good * (val << (n * good)); 
} 

// Mask the word preserving only the lower n bits. 
word_type lowbits(word_type val, size_t n) 
{ 
    word_type mask = shiftr(word_type(-1), W - n); 

    return val & mask; 
} 

// Struct for return values of locate() 
struct range_location_t { 
    size_t lindex; // The word where is located the 'begin' position 
    size_t hindex; // The word where is located the 'end' position 
    size_t lbegin; // The position of 'begin' into its word 
    size_t llen; // The length of the lower part of the word 
    size_t hlen; // The length of the higher part of the word 
}; 

// Locate the one or two words that will make up the result 
range_location_t locate(size_t begin, size_t end) 
{ 
    size_t lindex = begin/W; 
    size_t hindex = end/W; 
    size_t lbegin = begin % W; 
    size_t hend = end % W; 

    size_t len = (end - begin) * size_t(begin <= end); 
    size_t hlen = hend * (hindex > lindex); 
    size_t llen = len - hlen; 

    return { lindex, hindex, lbegin, llen, hlen }; 
} 

// Main function. 
template<typename Container> 
word_type get(Container const&container, size_t begin, size_t end) 
{ 
    assert(begin < container.size() * W); 
    assert(end <= container.size() * W); 

    range_location_t loc = locate(begin, end); 

    word_type low = lowbits(container[loc.lindex] >> loc.lbegin, loc.llen); 

    word_type high = shiftl(lowbits(container[loc.hindex], loc.hlen), loc.llen); 

    return high | low; 
} 

가 대단히 감사합니다.

Answer 1

채팅에서 발표했듯이 세련된 답변을 추가합니다. 여기에는 세 부분으로 나뉘며 각 부분에는 그 부분에 대한 설명이 이어집니다.

첫 번째 부분 인 get.h는 내 해결책이지만 일반화되고 하나의 수정으로 해결됩니다.

두 번째 부분 인 got.h는 질문에 게시 된 원래 알고리즘으로 서명되지 않은 유형의 STL 컨테이너에서 작동하도록 일반화되었습니다.

세 번째 부분 인 main.cpp에는 정확성과 성능을 검증하는 단위 테스트가 포함되어 있습니다.

#include <cstddef> 

using std::size_t; 

template < typename C > 
typename C::value_type get (C const &container, size_t lo, size_t hi) 
{ 

    typedef typename C::value_type item; // a container entry 
    static unsigned const bits = (unsigned)sizeof(item)*8u; // bits in an item 
    static size_t const mask = ~(size_t)0u/bits*bits; // huge multiple of bits 

    // everthing above has been computed at compile time. Now do some work: 

    size_t lo_adr = (lo  )/bits; // the index in the container of ... 
    size_t hi_adr = (hi-(hi>0))/bits; // ... the lower or higher item needed 

    // we read container[hi_adr] first and possibly delete the highest bits: 

    unsigned hi_shift = (unsigned)(mask-hi)%bits; 
    item hi_val = container[hi_adr] <<hi_shift>> hi_shift; 

    // if all bits are in the same item, we delete the lower bits and are done: 

    unsigned lo_shift = (unsigned)lo%bits; 
    if (hi_adr <= lo_adr) return (hi_val>>lo_shift) * (lo<hi); 

    // else we have to read the lower item as well, and combine both 

    return (hi_val<<bits-lo_shift | container[lo_adr]>>lo_shift); 

} 

위의 첫 번째 부분은 내 원래 솔루션이지만 부호없는 정수 유형의 모든 STL 컨테이너에서 작동하도록 일반화되었습니다. 따라서 32 비트 정수 또는 128 비트 정수를 사용하고 테스트 할 수 있습니다. 난 여전히 아주 작은 숫자에 대해서는 부호없는을 사용하지만 size_t로 대체 할 수도 있습니다. 알고리즘은 거의 수정되지 않고 작은 수정으로 - 컨테이너의 총 비트 수를 lo라고하면 이전의 get()은 컨테이너 크기 바로 위에있는 항목에 액세스합니다. 이것은 지금 고쳐졌습니다.

#include <cstddef> 

using std::size_t; 

// Shift right, but without being undefined behaviour if n >= 64 
template < typename val_type > 
val_type shiftr(val_type val, size_t n) 
{ 
    val_type good = n < sizeof(val_type)*8; 
    return good * (val >> (n * good)); 
} 

// Shift left, but without being undefined behaviour if n >= 64 
template < typename val_type > 
val_type shiftl(val_type val, size_t n) 
{ 
    val_type good = n < sizeof(val_type)*8; 
    return good * (val << (n * good)); 
} 

// Mask the word preserving only the lower n bits. 
template < typename val_type > 
val_type lowbits(val_type val, size_t n) 
{ 
    val_type mask = shiftr<val_type>((val_type)(-1), sizeof(val_type)*8 - n); 
    return val & mask; 
} 

// Struct for return values of locate() 
struct range_location_t { 
    size_t lindex; // The word where is located the 'begin' position 
    size_t hindex; // The word where is located the 'end' position 
    size_t lbegin; // The position of 'begin' into its word 
    size_t llen; // The length of the lower part of the word 
    size_t hlen; // The length of the higher part of the word 
}; 

// Locate the one or two words that will make up the result 
template < typename val_type > 
range_location_t locate(size_t begin, size_t end) 
{ 
    size_t lindex = begin/(sizeof(val_type)*8); 
    size_t hindex = end/(sizeof(val_type)*8); 
    size_t lbegin = begin % (sizeof(val_type)*8); 
    size_t hend = end % (sizeof(val_type)*8); 

    size_t len = (end - begin) * size_t(begin <= end); 
    size_t hlen = hend * (hindex > lindex); 
    size_t llen = len - hlen; 

    range_location_t l = { lindex, hindex, lbegin, llen, hlen }; 
    return l; 
} 

// Main function. 
template < typename C > 
typename C::value_type got (C const&container, size_t begin, size_t end) 
{ 
    typedef typename C::value_type val_type; 
    range_location_t loc = locate<val_type>(begin, end); 
    val_type low = lowbits<val_type>(container[loc.lindex] >> loc.lbegin, loc.llen); 
    val_type high = shiftl<val_type>(lowbits<val_type>(container[loc.hindex], loc.hlen), loc.llen); 
    return high | low; 
} 

이 두번째 부분은, 위의 got.h, 어떤 부호없는 정수 유형의 STL 컨테이너를 받아 들일뿐만 아니라 일반화 질문에 원래의 알고리즘이다. get.h와 마찬가지로이 버전은 컨테이너 유형을 정의하는 단일 템플릿 매개 변수를 제외한 다른 정의를 사용하지 않으므로 다른 항목 크기 나 컨테이너 유형을 쉽게 테스트 할 수 있습니다.

#include <vector> 
#include <cstddef> 
#include <stdint.h> 
#include <stdio.h> 
#include <sys/time.h> 
#include <sys/resource.h> 
#include "get.h" 
#include "got.h" 

template < typename Container > class Test { 

    typedef typename Container::value_type val_type; 
    typedef val_type (*fun_type) (Container const &, size_t, size_t); 
    typedef void (Test::*fun_test) (unsigned, unsigned); 
    static unsigned const total_bits = 256; // number of bits in the container 
    static unsigned const entry_bits = (unsigned)sizeof(val_type)*8u; 

    Container _container; 
    fun_type _function; 
    bool _failed; 

    void get_value (unsigned lo, unsigned hi) { 
     _function(_container,lo,hi); // we call this several times ... 
     _function(_container,lo,hi); // ... because we measure ... 
     _function(_container,lo,hi); // ... the performance ... 
     _function(_container,lo,hi); // ... of _function, .... 
     _function(_container,lo,hi); // ... not the performance ... 
     _function(_container,lo,hi); // ... of get_value and ... 
     _function(_container,lo,hi); // ... of the loop that ... 
     _function(_container,lo,hi); // ... calls get_value. 
    } 

    void verify (unsigned lo, unsigned hi) { 
     val_type value = _function(_container,lo,hi); 
     if (lo < hi) { 
     for (unsigned i=lo; i<hi; i++) { 
      val_type val = _container[i/entry_bits] >> i%entry_bits & 1u; 
      if (val != (value&1u)) { 
       printf("lo=%d hi=%d [%d] is'nt %d\n",lo,hi,i,(unsigned)val); 
       _failed = true; 
      } 
      value >>= 1u; 
     } 
     } 
     if (value) { 
     printf("lo=%d hi=%d value contains high bits set to 1\n",lo,hi); 
     _failed = true; 
     } 
    } 

    void run (fun_test fun) { 
     for (unsigned lo=0; lo<total_bits; lo++) { 
     unsigned h0 = 0; 
     if (lo > entry_bits) h0 = lo - (entry_bits+1); 
     unsigned h1 = lo+64; 
     if (h1 > total_bits) h1 = total_bits; 
     for (unsigned hi=h0; hi<=h1; hi++) { 
      (this->*fun)(lo,hi); 
     } 
     } 
    } 

    static uint64_t time_used () { 
     struct rusage ru; 
     getrusage(RUSAGE_THREAD,&ru); 
     struct timeval t = ru.ru_utime; 
     return (uint64_t) t.tv_sec*1000 + t.tv_usec/1000; 
    } 

public: 

    Test (fun_type function): _function(function), _failed() { 
     val_type entry; 
     unsigned index = 0; // position in the whole bit array 
     unsigned value = 0; // last value assigned to a bit 
     static char const entropy[] = "The quick brown Fox jumps over the lazy Dog"; 
     do { 
     if (! (index%entry_bits)) entry = 0; 
     entry <<= 1; 
     entry |= value ^= 1u & entropy[index/7%sizeof(entropy)] >> index%7; 
     ++index; 
     if (! (index%entry_bits)) _container.push_back(entry); 
     } while (index < total_bits); 
    } 

    bool correctness() { 
     _failed = false; 
     run(&Test::verify); 
     return !_failed; 
    } 

    void performance() { 
     uint64_t t1 = time_used(); 
     for (unsigned i=0; i<999; i++) run(&Test::get_value); 
     uint64_t t2 = time_used(); 
     printf("used %d ms\n",(unsigned)(t2-t1)); 
    } 

    void operator() (char const * name) { 
     printf("testing %s\n",name); 
     correctness(); 
     performance(); 
    } 

}; 

int main() 
{ 
    typedef typename std::vector<uint64_t> Container; 
    Test<Container> test(get<Container>); test("get"); 
    Test<Container> tost(got<Container>); tost("got"); 
} 

위의 3 부분, MAIN.CPP, 단위 테스트 클래스를 포함하고 get.h 그들에게 적용 got.h, 그 약간, 내 솔루션과 질문의 원본 코드입니다 수정 됨. 단위 테스트는 정확성을 확인하고 속도를 측정합니다. 그들은 256 비트의 컨테이너를 생성하고, 일부 데이터로 채우고, 컨테이너 항목에 더해지는 많은 비트의 모든 가능한 비트 섹션을 읽고, 많은 병리학 적 케이스를 읽고, 각 결과의 정확성을 검증함으로써 정확성을 검증합니다. 동일한 섹션을 다시 읽고 사용자 공간에서 사용 된 스레드의 시간을보고함으로써 속도를 측정합니다.

Answer 2

get() 및 get()에서 사용하는 모든 도우미 함수를 대체합니다. 조건부 분기를 포함하고 약 16 개의 산술 연산을 저장합니다. 즉, 일반적으로 더 빠르게 실행해야합니다. 최적화 된 컴파일로 매우 짧은 코드도 생성됩니다. 마지막으로 case == container.size() * W에서 container [container.size()]에 액세스하게하는 버그를 해결합니다.

가장 까다로운 부분은 hi가 0 인 경우를 제외하고 hi에서 1을 뺀 "hi- (hi> 0)"입니다. 1을 빼면 hi가 단어 경계 바로 위를 가리키는 경우를 제외하고는 아무 것도 바뀌지 않습니다. 즉, hi % 64 == 0. 이 경우 상위 컨테이너 항목에서 0 비트가 필요하므로 컨테이너 항목을 조금만 사용하면 충분합니다. hi_off를 계산하기 전에 1을 뺀 다음 "hi_off == lo_off"조건을 확인하면 더 간단한 경우로 넘어갑니다.

이 간단한 경우에는 컨테이너 항목이 하나만 있으면되고 양측에 일부 비트가 잘립니다. hi_val은 그 엔트리이고, 상위 비트는 이미 잘려져 있기 때문에 남은 것은 더 낮은 비트를 삭제하는 것뿐입니다.

덜 간단한 경우 우리는 하단 컨테이너 항목을 읽고, 사용하지 않는 바이트를 제거한 다음 두 항목을 결합해야합니다.

namespace { 
    size_t const upper_mask = ~(size_t)0u << 6u; 
    unsigned const lower_mask = (unsigned)~upper_mask; 
} 

word_type get (Container const &container, size_t lo, size_t hi) 
{ 
    size_t lo_off = lo  >>6u; assert (lo_off < container.size()); 
    size_t hi_off = hi-(hi>0)>>6u; assert (hi_off < container.size()); 
    unsigned hi_shift = lower_mask&(unsigned)(upper_mask-hi); 
    word_type hi_val = container[hi_off] <<hi_shift>> hi_shift; 
    unsigned lo_shift = lower_mask&(unsigned)lo; 
    if (hi_off == lo_off) return hi_val >> lo_shift; // use hi_val as lower word 
    return (hi_val<<W-lo_shift | container[lo_off]>>lo_shift) * (lo_off<hi_off); 
}