프로파일 64 비트 시스템에 설정 구현 내 시스템에

Question

관련 정보 : Core2Duo T6500 GCC (GCC) 4.4.1 20090725 (레드햇 4.4.1-2)

기본 세트 구현을 사용하여, 저장되는 각 세트는 실제로 저장된 세트의 사전 식 순서 일 뿐이며 Union, Intersection, elementQ 등과 같은 Set 조작에 대한 표준 비트 조작을 사용할 수 있습니다.

제 질문은 세트의 크기를 결정하는 것에 관한 것입니다. Cliquer 같은 구현은 사용하십시오

static int set_bit_count[256] 

주어진 가능한 8 비트 문자열에 얼마나 많은 비트를 저장하기 위해, 다음 알고리즘이 세트의 크기를 결정하기 위해 한 번에 8 개 비트를 통해 갈 것입니다.

1. 레지스터 캐시 또는 RAM보다 빠른 8 배속 이상의 경우이 속도를 낭비 것 :

   나는 그런 식으로 두 가지 문제가있다.

2. 64 비트 컴퓨터에서 int 동작이 느리다는 말은하지 않습니다. unsigned long long int은 64 비트 CPU의 표준 연산 정수라고 가정합니다.

는하지만 난 그냥 모든 것이 레지스터에 저장 될 수있는대로 빨리 할 수있는 간단한

while(x) 
    x&=x-1; 
    ++count; 

를 사용하여 상상. 그러나 단점이라면 명백한 8x 배가 아닌 다른 작업을 할 수 있을까요?

또한 테스트를 시작할 수있는 아이디어가 전혀없는 int, uint, unsigned long, unsigned long long의 다양한 조합이 있습니다.

이 주제에 대한 에세이를 알고 있습니까?

이 주제에 대한 다른 의문 사항은 알고 계십니까?

당신은 이것에 대한 통찰력을 갖고 있습니까?

프로필을 작성하는 방법에 대한 제안 사항이 있습니까? 나는 gprof를 사용한 적이 없다. 그리고 time.h를 사용하면 초 단위보다 정밀해질 수 없습니다.

내가 그렇게하면 매우 감사 할 것입니다.

Answer 1

대부분의 경우 (내가 지금 테스트 너무 게으른 해요하지만), 가장 빠른이

int popcount(unsigned x) { 
    int count; 
#if defined(__GNUC__) 
    __asm__("popcnt %1,%0" : "=r" (count) : "r" (x)); 
#elif defined(_MSC_VER) 
    __asm { 
     POPCNT x, count 
    }; 
#else 
    /* blah, who cares */ 
    for (count = 0; x; count += x&1, x >>= 1); 
#endif 
    return count; 
} 

것 물론, 컴파일러의 내장 내장 함수를 사용하는 것이 더 좋을 것입니다. 그리고 일반적으로 현재 구현 된 플랫폼에 가장 적합한 구현을 선택하도록 컴파일러를 신뢰합니다.

Answer 2

비트 패턴을 생성하기 위해 난수 생성기를 사용하여 두 가지 구현을 프로파일 링합니다. 루프의 끝에서 출력 할 각 반복 (예 : 비트 수의 배타적 OR) 중에 무언가를 축적하면서 많은 반복을 반복합니다. 누적 및 인쇄가 필요하므로 컴파일러가 중요성을 최적화하지 않습니다. (CPU가 SSE4.2을 지원하지 않는 경우이 폭발하지만.)