고정 길이 배열 간에 동일한 바이트 수를 확인하는 가장 빠른 방법

StackOverflow https://stackoverflow.com/questions/116485

  •  02-07-2019
  •  | 
  •  

문제

"비교"하고 둘 사이에 얼마나 많은 요소가 같은지 확인해야 하는 16개 요소(문자)로 구성된 2개의 배열이 있습니다.

이 루틴은 수백만 번 사용될 예정이므로(일반적인 실행 횟수는 약 6천만~7천만 번) 최대한 빨라야 합니다.저는 C++(기록상 C++Builder 2007)로 작업하고 있습니다.

지금은 간단합니다.

matches += array1[0] == array2[0];

16번 반복됨(프로파일링은 for 루프를 사용하여 수행하는 것보다 30% 더 빠른 것으로 나타남)

더 빠르게 작업할 수 있는 다른 방법이 있나요?

환경 및 데이터 자체에 대한 일부 데이터:

  • 저는 C++Builder를 사용하고 있는데, 고려해야 할 속도 최적화가 없습니다.나는 결국 다른 컴파일러로 시도해 볼 것이지만 지금은 이 컴파일러를 사용하고 있습니다.
  • 데이터는 대부분 다를 것입니다.100% 동일한 데이터는 일반적으로 매우 드뭅니다(1% 미만일 수도 있음).
도움이 되었습니까?

해결책

업데이트:이 답변은 내 의견이 아래 제공된 소스 코드와 일치하도록 수정되었습니다.

SSE2 및 popcnt 명령어를 사용할 수 있는 경우 최적화를 사용할 수 있습니다.

16바이트는 SSE 레지스터에 잘 맞습니다.C++ 및 어셈블리/내장 기능을 사용하여 두 개의 16바이트 배열을 xmm 레지스터에 로드하고 cmp합니다.이는 비교의 참/거짓 조건을 나타내는 비트마스크를 생성합니다.그런 다음 movmsk 명령어를 사용하여 비트마스크의 비트 표현을 x86 레지스터에 로드합니다.그러면 이것은 모든 1을 계산하여 얼마나 많은 실제 값이 있는지 확인할 수 있는 비트 필드가 됩니다.하드웨어 popcnt 명령은 레지스터의 모든 1을 계산하는 빠른 방법이 될 수 있습니다.

이를 위해서는 특히 어셈블리/내장 및 SSE에 대한 지식이 필요합니다.두 가지 모두에 대한 웹 리소스를 찾을 수 있어야 합니다.

SSE2 또는 popcnt를 지원하지 않는 시스템에서 이 코드를 실행하는 경우 배열을 반복하고 펼쳐진 루프 접근 방식으로 차이점을 계산해야 합니다.

행운을 빌어요

편집하다:어셈블리를 모른다고 표시했으므로 내 대답을 설명하는 몇 가지 샘플 코드는 다음과 같습니다.

#include "stdafx.h"
#include <iostream>
#include "intrin.h"

inline unsigned cmpArray16( char (&arr1)[16], char (&arr2)[16] )
{
    __m128i first = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr1 ) );
    __m128i second = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr2 ) );

    return _mm_movemask_epi8( _mm_cmpeq_epi8( first, second ) );
}

int _tmain( int argc, _TCHAR* argv[] )
{
    unsigned count = 0;
    char    arr1[16] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 };
    char    arr2[16] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 };

    count = __popcnt( cmpArray16( arr1, arr2 ) );

    std::cout << "The number of equivalent bytes = " << count << std::endl;

    return 0;
}

몇 가지 참고사항:이 함수는 SSE2 명령어와 Phenom 프로세서(제가 사용하는 머신)에 도입된 popcnt 명령어를 사용합니다.나는 SSE4를 탑재한 최신 Intel 프로세서에도 popcnt가 있다고 생각합니다.이 함수는 CPUID에 대한 명령어 지원을 확인하지 않습니다.SSE2 또는 popcnt가 없는 프로세서에서 사용되는 경우 함수는 정의되지 않습니다(아마 잘못된 opcode 명령을 받게 될 것입니다).해당 감지 코드는 별도의 스레드입니다.

나는 이 코드의 시간을 측정하지 않았습니다.내가 더 빠르다고 생각하는 이유는 한 번에 16바이트를 분기 없이 비교하기 때문입니다.이를 환경에 맞게 수정하고 시간을 내어 자신에게 적합한지 확인해야 합니다.나는 이것을 VS2008 SP1에서 작성하고 테스트했습니다.

SSE는 자연스러운 16바이트 경계에 정렬된 데이터를 선호합니다.이를 보장할 수 있다면 속도가 추가로 향상되어야 하며 _mm_loadu_si128 지침을 정렬이 필요한 _mm_load_si128로 변경할 수 있습니다.

다른 팁

핵심은 CPU가 지원하는 가장 큰 레지스터를 사용하여 비교를 수행한 다음 필요한 경우 바이트로 대체하는 것입니다.

아래 코드는 4바이트 정수를 사용하는 방법을 보여 주지만 SIMD 아키텍처(최신 Intel 또는 AMD 칩)에서 실행 중인 경우 정수 기반 루프로 폴백하기 전에 하나의 명령어로 두 배열을 비교할 수 있습니다.요즘 대부분의 컴파일러는 128비트 유형을 기본적으로 지원하므로 ASM이 필요하지 않습니다.

(SIMD 비교의 경우 배열은 16바이트로 정렬되어야 하며 일부 프로세서(예: MIPS)에서는 int 기반 비교를 위해 배열이 4바이트로 정렬되어야 합니다.

예:

int* array1 = (int*)byteArray[0];
int* array2 = (int*)byteArray[1];

int same = 0;

for (int i = 0; i < 4; i++)
{
  // test as an int
  if (array1[i] == array2[i])
  {
    same += 4;
  }
  else
  {
    // test individual bytes
    char* bytes1 = (char*)(array1+i);
    char* bytes2 = (char*)(array2+i);

    for (int j = 0; j < 4; j++)
    {
      same += (bytes1[j] == bytes2[j];
    }
  }
}

MSVC 컴파일러가 SIMD에 대해 정확히 무엇을 지원하는지 기억이 나지 않지만 다음과 같은 작업을 수행할 수 있습니다.

// depending on compiler you may have to insert the words via an intrinsic
__m128 qw1 = *(__m128*)byteArray[0];
__m128 qw2 = *(__m128*)byteArray[1];

// again, depending on the compiler the comparision may have to be done via an intrinsic
if (qw1 == qw2)
{
    same = 16;
}
else
{
    // do int/byte testing
}

예를 들어 배열의 위치를 ​​제어할 수 있는 능력이 있다면, 예를 들어 메모리에 배열을 차례로 배치하면 첫 번째 액세스 시 배열이 CPU 캐시에 로드될 수 있습니다.

이는 CPU와 캐시 구조에 따라 다르며 시스템마다 다릅니다.

다음에서 메모리 계층 구조와 캐시에 대해 읽을 수 있습니다. Henessy & Patterson의 컴퓨터 아키텍처:정량적 접근 방식

절대적으로 가장 낮은 설치 공간이 필요하다면 어셈블리 코드를 사용하겠습니다.나는 한동안 이 작업을 수행하지 않았지만 MMX(또는 SSE2/3일 가능성이 더 높음)에는 아주 적은 명령만으로 해당 작업을 정확하게 수행할 수 있는 지침이 있을 것이라고 확신합니다.

일치하는 경우가 일반적인 경우 값을 16 대신 32비트 정수로 로드하여 한 번에 2개를 비교할 수 있습니다(그리고 일치 항목 2개로 계산).

두 개의 32비트 값이 다음과 같은 경우 ~ 아니다 동일하면 별도로 테스트해야 합니다(그리고 상위 및 하위 16비트 값도 확인).

코드는 더 복잡하지만 더 빨라야 합니다.

64비트 시스템을 대상으로 하는 경우 64비트 정수로 동일한 트릭을 수행할 수 있습니다. 실제로 한계를 뛰어넘고 싶다면 어셈블러에 들어가서 128비트로 작업할 수 있는 다양한 벡터 기반 명령어를 사용하는 방법을 살펴보세요. 한 번에.

마법의 컴파일러 옵션은 시간에 따라 크게 달라집니다.특히 SSE 벡터화를 생성하면 속도가 크게 향상될 수 있습니다.

이는 플랫폼 독립적이어야 합니까, 아니면 이 코드가 항상 동일한 유형의 CPU에서 실행됩니까?최신 x86 CPU로 제한한다면 다음을 사용할 수 있습니다. MMX 한 클럭 틱에 8바이트 배열을 조작할 수 있는 명령어입니다.AFAIK, gcc를 사용하면 C 코드에 어셈블리를 포함할 수 있으며 Intel의 컴파일러(icc)는 특정 어셈블리 지침을 직접 호출할 수 있는 래퍼인 내장 함수를 지원합니다.SSE와 같은 다른 SIMD 명령어 세트도 이를 위해 유용할 수 있습니다.

배열의 값 사이에 연결이 있습니까?일부 바이트는 다른 바이트보다 동일할 가능성이 더 큽니까?값에 본질적인 순서가 있을 수 있나요?그런 다음 가장 가능성이 높은 사례에 맞게 최적화할 수 있습니다.

데이터가 실제로 무엇을 나타내는지 설명하면 이러한 유형의 무차별 비교를 불필요하게 만드는 메모리의 데이터를 표현하는 완전히 다른 방법이 있을 수 있습니다.데이터가 실제로 무엇을 나타내는지 자세히 설명하고 싶으십니까??

하나의 진술만큼 더 빠르나요?

matches += (array1[0] == array2[0]) + (array1[1] == array2[1]) + ...;

16번을 작성하는 것이 간단한 루프보다 빠르면 컴파일러가 형편없거나 최적화가 설정되어 있지 않은 것입니다.

짧은 답변:병렬 하드웨어에서 벡터 연산을 수행하지 않는 한 더 빠른 방법은 없습니다.

배열 대신 포인터를 사용해 보십시오.

p1 = &array1[0];
p2 = &array2[0];
match += (*p1++ == *p2++);
// copy 15 times.

물론 가장 빠른 방법을 확인하려면 이를 다른 접근 방식과 비교하여 측정해야 합니다.

그리고 이 루틴이 처리에 병목 현상을 일으킨다고 확신하시나요?실제로 이를 최적화함으로써 애플리케이션 전체의 성능이 향상됩니까?다시 말하지만, 오직 측정만이 알 수 있습니다.

배열이 저장되는 방식을 수정할 수 있는 방법이 있습니까?아마도 32비트 컴파일러를 사용하고 있다는 점을 고려하면 한 번에 1바이트를 비교하는 것은 매우 느립니다.대신 4개의 정수(32비트) 또는 2개의 long(64비트)에 16바이트를 저장한 경우 각각 4번 또는 2번의 비교만 수행하면 됩니다.

스스로에게 물어봐야 할 질문은 데이터를 4개의 정수 또는 2개의 긴 배열로 저장하는 데 드는 비용입니다.데이터 등에 얼마나 자주 액세스해야 합니까?

항상 좋은 오래된 x86 REPNE CMPS 명령어가 있습니다.

한 가지 추가 가능한 최적화:대부분의 경우 배열이 동일할 것으로 예상하는 경우 첫 번째 단계로 memcmp()를 수행하고 테스트가 true를 반환하는 경우 응답으로 '16'을 설정하는 것이 약간 더 빠를 수 있습니다.물론 배열이 매우 자주 동일할 것으로 예상하지 않는다면 속도가 느려질 뿐입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top