C 또는 C++의 비트 맵에서 부울 표현식을 효율적으로 실행

Question

C 또는 C++의 비트 맵에서 부울 표현식을 실행하는 가장 효율적인 방법은 무엇입니까? 예를 들어, 내가 4 비트 비트 맵 (a, b, c, d)을 가지고 있다고 가정 해 봅시다. 자, 내가 (a AND b) OR (c AND d)과 같은 간단한 부울 표현식을 가지고 있다고 가정 해 봅시다. 부울 표현식을 어떻게 표현하여 효과적으로 비트 맵에 적용 할 수 있습니까? 예제와 같이 주어진 부울 식에 적용 할 수있는 제네릭 솔루션을 찾고 있습니다. 다른 말로 표현하면 부울 표현식을 "컴파일"하여 부울로 효율적으로 비트 맵을 축소하는 데 사용할 수있는 다른 데이터 구조를 찾는 방법을 찾고 있습니다.

비트 맵 구조는 데이터베이스 레코드에 대한 필터링 작업의 결과입니다. 모든 레코드에는 자체 비트 맵이 있으며 비트 맵의 ​​모든 비트는 개별 필터링 규칙의 결과입니다. 부울 식은 이러한 필터링 규칙을 결합하여 레코드가 데이터베이스 쿼리의 결과에 포함되어야하는지 여부를 결정하는 데 사용됩니다. 부울 연산으로 결합 할 수있는 최대 64 개의 개별 필터링 규칙이있을 수 있으므로 필요하면 비트 맵을 unsigned long long int으로 나타낼 수 있습니다.

해결 방법은 속도면에서 효율적이어야하며 비트 맵 구조를 변경하면 안됩니다. 부울 표현식을 다른 구조로 변환하는 것은 캐시 될 수 있기 때문에 (적어도 현재 사용중인 경우) 메모리 효율적이거나 빠를 필요는 없습니다. 변환 된 부울 표현식을 사용하여 비트 맵을 축소하는 것은 빠르고 효율적이어야합니다.

참고 : 부울 표현식은 중첩 사용하여 AND 및 OR 작업 (NO 문 IF)되어

• .
• 솔루션은 64 비트 CPU의 가용성을 전제로합니다.
• 해결 방법은 CPU에 종속적이어서는 안됩니다 (64 비트 주소 지정 옆에 있음).
• 이 솔루션은 다른 특정 하드웨어 (예 : GPU)의 가용성을 가정해서는 안됩니다.
• 모든 비트 맵이 메모리에 있습니다.
• 매우 많은 수의 비트 맵 (수십억 개)이있을 수 있습니다.
• 비트 맵은 한 번에 하나씩 업데이트됩니다.

Answer 1

표현식을 이진 트리로 표현할 수 있으며 두 노드 유형에 대해 두 클래스를 사용할 수도 있습니다. 또한 각 노드에 작업을 매개 변수화 할 수 있지만 그럴 가치는 없습니다. 아마도 하나의 입력으로 노드를 만들 수도 있습니다. 노드 입력은 비트 맵 또는 다른 노드의 위치이므로 비트 맵의 ​​인덱스를 매개 변수로 사용하는 전자의 경우 하위 클래스를 만들고 있습니다. And 노드에 대한 value 함수를 작성하고 Or 노드를 완성하여이 코드를 마칩니다.

typedef unsigned long long Bitmap; 
Bitmap bitmap; 

struct Node { 
    virtual bool value()=0; 
}; 

struct AbsNode : public Node { 
    int bit; 
    bool value() {return (bitmap>>bit)&1; } 
} 

struct AndNode : public Node { 
    Node *operandA, *operandB; 
    etc. 
} 

Answer 2

비트 맵에서 AND 또는 OR 연산을 사용하는 가장 효율적인 방법은 하드웨어 지원을 사용하는 것입니다. 많은 그래픽 프로세서가 두 비트 맵에서 작업을 수행 할 수 있습니다. 이를위한 C++ 표준 라이브러리 작업은 없습니다.

비트 맵에서 각 비트, 바이트, 단어 또는 더블 워드에 대해 연산을 수행해야합니다.

다음으로 효율적인 방법은 루프를 풀는 것입니다. 분기 명령어는 실행 사이클을 낭비하며 (데이터 명령어에 사용될 수 있음) 명령 파이프 라인을 지우고 다시로드하는 시간을 낭비 할 수 있습니다.

프로세서의 데이터 캐시를 효과적으로 사용하여 효율성을 높일 수도 있습니다. 한 무리의 변수를로드하고, 연산을 수행하고, 결과를 저장하고 반복합니다.

또한 프로세서의 워드 크기를 사용하여 그룹으로 가져와야합니다. 32 비트 프로세서는 한 번에 32 비트를 가져 오는 것을 아주 좋아합니다. 이렇게하면 한 페치로로드되는 4 비트 픽셀 8 세트가 제공됩니다. 그렇지 않으면 한 번에 8 비트를 가져와야하므로 32 비트의 1 페치와 비교하여 8 비트의 4 페치가 발생합니다.

uint8_t * p_bitmap_a = &Bitmap_A[0]; 
uint8_t * p_bitmap_b = &Bitmap_B[0]; 
uint8_t * p_bitmap_c = &Bitmap_C[0]; 

// C = A AND B 

for (unsigned int i = 0; i < bitmap_size/4; ++i) 
{ 
    uint32_t a = *((uint32_t*) p_bitmap_a); 
    uinte2_t b = *((uint32_t*) p_bitmap_b); 
    uint32_t c = a & b; 
    *((uint32_t *) p_bitmap_c) = c; 
    p_bitmap_a += sizeof(uint32_t); 
    p_bitmap_b += sizeof(uint32_t); 
    p_bitmap_c += sizeof(uint32_t); 
} 

편집 : 1 :

여기에 핵심 알고리즘의 작업에 도움을 줄 수 지침이있을 수 있습니다
귀하의 프로세서. 예를 들어, ARM7 프로세서는 하나의 명령어로 메모리에서 많은 레지스터를로드 할 수 있습니다. 프로세서 명령어 세트를 연구하십시오. 프로세서 관련 지침을 활용하려면 인라인 어셈블리 언어를 사용해야 할 수 있습니다.

편집 2 : 스레딩 & 병렬 처리.

비트 맵이 큰 경우가 아니면 여러 스레드 실행 또는 병렬 실행을 유지 관리하는 오버 헤드가 이점보다 클 수 있습니다. 예를 들어, 다른 CPU 코어와 동기화하는 오버 헤드가 200ms이고 중단없이 비트 맵을 처리하는 것이 1000ms라면 단일 비트 맵 (비트 맵을 다른 코어 프로세스로 처리하기 위해 1200ms)에서 병렬 처리를 사용하면 시간이 낭비됩니다.

1. 하나의 스레드가 메모리 (버퍼)에 데이터베이스에서 비트 맵을 가져옵니다 : 당신이 많은 비트 맵이있는 경우

   , 당신은 병렬 처리 또는 다중 스레드를 사용하여 약간의 시간을 얻을 수 있습니다.

2. 다른 스레드가 비트 맵을 처리하고 나가는 버퍼에 저장합니다.
3. 세 번째 프로세스는 버퍼링 된 비트 맵을 데이터베이스에 씁니다.

데이터베이스와 같은 외부 소스에서 비트 맵을 가져 오는 경우이 입출력이 병목 현상이됩니다. 이것은 최적화하거나 스풀링해야하는 부분입니다.

Answer 3

비트 맵이 항상 이고 보장되는 경우은 항상 4 비트가되어야하며, 비트는 char의 하위 4 비트에 적합하며 모든 비트 맵에는 가능한 값은 16 개뿐입니다.

특정 부울 표현식의 경우 16 개의 가능한 비트 조합 각각에 대해 평가하여 16 개의 결과 비트 세트를 제공합니다. 열 여섯 비트 INT로 조립 : 비트 1 비트 제로, false, false, false에서 false, false, false, false, true, 등등.

이제 임의의 부울 대 임의의 비트 맵에 대한 수표가된다 :

1. 는 4 비트 (int)로 비트 맵을 치료, 1 << (4 bit int)을 평가합니다.
2. 해당 시프트 결과를 사용하고 C++ & 연산자를 사용하여 부울 연산의 캐시 된 16 비트 int 값을 테스트합니다.

false의 경우 == 0, 참이면 != 0을 반환합니다.

두 지침으로 줄이면 : shift 및 and이 가장 빠릅니다.

이것은 부울 테스트의 숫자가 매우 작고 부울 테스트가 인 경우이 비싸지 만, 수십억 비트의 비트 맵을 사용한다고 가정하기 때문에 많은 많은 비트 맵에서 같은 부울 연산을 사용하게 될 것입니다.