벡터 및지도 검색이 정적 비교보다 훨씬 느린 이유

Question

1MB 크기의 파일을 구문 분석하고 처음 300KB를 읽고 특정 서명 수를 검색합니다. 내 전략은 각 바이트에 대해 해당 바이트가지도/벡터에 있는지/내가 서명의 시작 부분에있을 수있는 바이트가 무엇인지를 확인한 후 전체 서명을 찾습니다.이 예에서는 전체 바이트는 x37, x50 및 x52입니다. 파일 (90) (9 개 파일 실제로 10 배)의 총 처리 다음 코드는 2.122 초에서 실행 :

 byte * bp = &buffer[1]; 
     const byte * endp = buffer + bytesRead - 30; // a little buffer for optimization - no signature is that long 
     //multimap<byte, vector<FileSignature> >::iterator lb, ub; 
     map<byte, vector<FileSignature> >::iterator findItr; 
     vector<FileSignature>::iterator intItr; 
     while (++bp != endp) 
     { 
      if (*bp == 0x50 || *bp == 0x52 || *bp == 0x37) // Comparison line 
      { 
       findItr = mapSigs.find(*bp); 
       for (intItr = findItr->second.begin(); intItr != findItr->second.begin(); intItr++) 
       { 
        bool bMatch = true; 
        for (UINT i = 1; i < intItr->mSignature.size(); ++i) 
        { 
         if (intItr->mSignature[i] != bp[i]) 
         { 
          bMatch = false; 
          break; 
         } 
        } 

        if (bMatch) 
        { 
         CloseHandle(fileHandle); 
         return true; 
        } 
       } 
      } 
     } 

하지만, 내 초기 구현은 부진 84초에서 종료한다.

findItr = mapSigs.find(*bp); 
if (findItr != mapSigs.end()) 
... 

매우 유사한 구현도 매우 느린 처리 ​​결과 3 개 개의 값 (1백90초)를 함유하는 벡터를 사용 :

if (find(vecFirstChars.begin(), vecFirstChars.end(), *bp) != vecFirstChars.end()) 
{ 
    findItr = mapSigs.find(*bp); 
    ... 

를 유일한 차이점은 상기 "// 비교 선을"로 표시된 라인에 관련

그러나 벡터의 요소에 액세스하는 구현은 비교적 잘 수행합니다 (8.1 초). 안 정적 비교만큼 좋은,하지만 다른 옵션에 비해 여전히 훨씬 훨씬 더 :

if (vecFirstChars[0] == *bp || vecFirstChars[1] == *bp || vecFirstChars[2] == *bp) 
{ 
    findItr = mapSigs.find(*bp); 
    ... 

지금까지 (아래 구성 요소 (10)에 의해 영감을) 가장 빠른 구현 약 2.0 초에서 클러킹 다음입니다 :

은

bool validSigs[256] = {0}; 
validSigs[0x37] = true; 
validSigs[0x50] = true; 
validSigs[0x52] = true; 

while (++bp != endp) 
{ 
    if (validSigs[*bp]) 
    { 
    ... 

두 번째 char가 유효한지 확인하기 위해 2 개의 validSigs를 사용하도록 확장하면 총 실행 시간이 0.4 초가됩니다.

다른 구현이 더 잘 수행되어야한다고 생각합니다. 특히 더 많은 접두사 접두사로 확장되어야하며 검색은 O (log (n)) vs O (n)입니다. 내가 뭘 놓치고 있니? 내 유일한 어둠의 추측은 정적 비교와 (덜 현존하는) 벡터 인덱싱에서 레지스터 나 다른 위치에 캐시 된 비교 값이 읽기보다 훨씬 빠릅니다. 기억으로부터. 이것이 사실이라면 컴파일러에게 특정 값이 자주 사용된다는 것을 알릴 수 있습니까? 명백하지 않은 아래의 코드를 활용할 수있는 다른 최적화가 있습니까? 난 비주얼 스튜디오로 컴파일하고

는 2008 년

Answer 1

이 실행되는 명령어의 수에 내려 올 수있을만큼 간단합니다. 벡터, 맵 또는 찾아보기 테이블은 CPU 레벨 1 데이터 캐시에 완전히 상주하므로 메모리 액세스에 시간이 걸리지 않습니다. 룩업 테이블에 관해서는, 대부분의 바이트가 서명 프리픽스와 일치하지 않는 한, 분기 예측기는 흐름 제어가 시간을 차지하는 것을 중단 할 것이다. (그러나 다른 구조는 흐름 제어 오버 헤드가 발생합니다.) 그래서 간단히 말해서 벡터의 각 값을 비교할 때 차례로 3 번의 비교가 필요합니다. 맵은 O (로그 N)이지만 링크 된 데이터 구조를 탐색 할 때 계수 (big-O 표기법에서 무시 됨)가 큽니다. 룩업 테이블은 구조에 대한 액세스가 하나의 기계 명령어에 의해 완료 될 수 있고 그 이후 남아있는 모든 것이 0에 대한 하나의 비교이기 때문에 작은 계수를 갖는 O (1)이다.

성능을 분석하는 가장 좋은 방법은 valgrind/kcachegrind와 같은 프로파일 러 도구를 사용하는 것입니다.

Answer 2

"상수와 비교"는 3 개의 메모리 주소를 3 개의 상수와 비교합니다. 이 경우 컴파일러가 그렇게 느껴지면 언롤 (unroll) 또는 비트 최적화를 수행하는 것이 매우 쉽습니다.서면 ASM이 여기에있을 유일한 지점은 매우 예측 가능할 것입니다.

리터럴 3 요소 벡터 조회의 경우 벡터 값의 주소를 역 참조하기위한 추가 비용이 있습니다.

벡터 루프의 경우 컴파일러는이 시점에서 벡터가 얼마나 큰지 알 수 없습니다. 따라서 일반 루프를 작성해야합니다. 이 루프는 분기를 가지며 한 방향으로 2 번 분기 한 다음 다른 방향으로 분기합니다. 컴퓨터가 경험적 "분기가 지난 시간에 수행 한 방식"을 사용하면 많은 분기 예측 실패가 발생합니다.

이론을 검증하려면 분기를보다 예측 가능하게 만드십시오. 한 번에 최대 100 개의 입력 바이트에 대해 각 요소를 검색 한 후 다음 요소를 검색하십시오. 그러면 코드에서 33 %가 아닌 98 %의 순서로 순진한 분기 예측이 수행됩니다. 즉, 서명이 다 떨어질 때까지 서명 0에 대해 100 자 (또는 무엇이든)의 문자를 스캔 한 다음 서명 1에 100 자 (또는 무엇이든) 문자를 스캔하십시오. 그런 다음 서명을 스캔하려면 100 자의 다음 블록으로 이동하십시오. 분기 예측 실패를 피하려고하기 때문에 100을 선택했습니다. 몇 퍼센트 분기 예측 실패가 그리 나쁘지는 않은 것으로 생각합니다. :)

map 솔루션의 경우 잘 map은 높은 일정한 오버 헤드를 가지고 있으므로 느리다는 것은 꽤 예측할 수 있습니다. map의 주요 용도는 큰 n 조회와 코드 작성이 정말 쉽다는 사실입니다.