memchr()은 어떻게 작동합니까?

Question

배경 : 나는 대략 C's memchr과 동등한 기능의 순수한 D 언어 구현을 만들려고하고 있지만 포인터 대신 배열과 인덱스를 사용합니다. 그 이유는 std.string이 컴파일 타임 함수 평가와 함께 작동하기 때문입니다. 익숙하지 않은 사용자의 경우 특정 제한 사항이 충족되면 컴파일 타임에 함수를 평가할 수 있습니다. 한 가지 제한 사항은 포인터를 사용할 수 없다는 것입니다. 다른 하나는 C 함수를 호출하거나 인라인 어셈블리 언어를 사용할 수 없다는 것입니다. 문자열 라이브러리를 컴파일 할 때 컴파일 타임 코드 생성에 유용합니다.

질문 : 질문 : memchr은 어떻게하면 빨리 수행 할 수 있습니까? Win32에서 단순 루프를 사용하여 순수 D로 만들 수 있었던 모든 것은 경계 검사를 사용하지 않도록 설정하거나 루프를 풀는 것과 같은 명백한 최적화 기술을 사용하여 적어도 2 배 더 느립니다. 어떤 종류의 비 명백한 트릭을 사용할 수 있습니까? 문자열에서 문자를 찾는 것만 큼 간단합니다.

Answer 1

나는 GNU libc 님의 출처를 살펴볼 것을 권합니다. 대부분의 함수는 일반적인 최적화 된 C 버전의 함수와 가능한 한 많은 지원되는 아키텍처에 대해 최적화 된 어셈블리 언어 버전을 포함하며 컴퓨터 별 기법을 사용합니다.

x86-64 SSE2 version 이른 출구 pmovmskb/test/jcc의 오버 헤드를 상환하는 번 (네 벡터 16B)에 데이터의 전체 캐시 라인에 pcmpeqb의 결과를 결합한다.

gcc와 clang은 현재 초기 종료 조건이 if() break 인 루프를 자동 벡터 라이 제이션 할 수 없으므로 명백한 C 구현에서 순진한 바이트 단위로 바이트 단위로 만듭니다.

Answer 2

This implementation of memchr from newlib은 다른 사람이 memchr을 최적화하는 한 예입니다 (memchr은 제외하고 newlib 라이브러리의 다른 함수는 here입니다).

덧붙여 말하자면, MSVC 설치의 선택적 부분으로 MSVC 런타임 라이브러리의 대부분의 소스 코드를 사용할 수 있습니다 (그래서, 당신은 그것을 볼 수 있습니다).

Answer 3

memchr.c의 FreeBSD (BSD 라이선스) memchr()입니다. FreeBSD의 온라인 소스 코드 브라우저는 BSD 라이센스 코드 예제에 대한 좋은 참고 자료입니다.

void * 
memchr(s, c, n) 
    const void *s; 
    unsigned char c; 
    size_t n; 
{ 
    if (n != 0) { 
     const unsigned char *p = s; 

     do { 
      if (*p++ == c) 
       return ((void *)(p - 1)); 
     } while (--n != 0); 
    } 
    return (NULL); 
} 

Answer 4

memset과 memcpy는 일반적으로 기계 코드의 양이 매우 적습니다. inlining similar assembly code 없이는 그런 종류의 속도를 재현 할 수 없습니다. 구현시 고려해야 할 주요 문제점 중 하나는 data alignment입니다.

하나의 generic technique you may be able to use은 검색 할 문자열의 끝에 sentinel을 삽입하여 찾을 수 있습니다. 문자열 끝의 테스트를 루프 안쪽에서 루프 뒤쪽으로 이동할 수 있습니다.