64 비트 유형을 사용합니까?

Question

나는 컴파일러를위한 해시 함수를 작성 중이며 __int64 데이터 유형을 자주 사용한다. 컴파일러는 서로 다른 OS에서 지원되도록 설계되었습니다. 나는 __int64이 내 타겟 시스템을위한 대부분의 주요 C++ 컴파일러에 의해 컴파일 될 수있는 타입이므로 그게 문제가 아님을 안다. 해시 함수를 사용하여 큰 문자열을 작고 빠르게 비교할 수 있으며 64 비트 OS에서 이상하게 작동합니다. 하지만 32 비트 OS에서 이점을 없애기 위해 충분히 큰 성능 저하가 있습니까? 32 비트 정수를 사용할 수는 있지만 해시 함수의 효율성을 크게 떨어 뜨립니다.

편집 : 맞춤 코드이며 매우 간단합니다. 첫 번째 해시 함수는 12 개의 영숫자 (밑줄 포함) 문자에서 고유 한 64 비트 int를 생성합니다. 그런 다음 클래스는 64 비트 해시의 주소 연결 목록을 만들어 해시를 12 자 이상 처리하고 비교 연산자를 오버로드합니다. 오버로드 된 비교는 단락되어 주소 링크 된 목록을 비교합니다. 내 컴퓨터에서 테스트를 실행하여 무작위로 큰 해시 (100 - 300 자)를 자체 (최악의 시나리오)와 비교하여 비교 한 결과 문자열 비교보다 빠름이 입증되었습니다. 해시를 생성하는 오버 헤드를 더 잘 시뮬레이트하기 위해 미리 생성 된 대형 해시의 비교 테스트를 실행하여 비교했습니다. 이것은 코드 최적화가 해제 된 상태로 모두 실행됩니다. 10 억 개의 해시 비교와 10 억 개의 문자열 비교로 해시는 약 16 %의 시간이 걸렸습니다. 이것은 64 환경에서 모두였습니다. 나는 테스트를 실행하는 32 비트 컴퓨터가 없습니다

Answer 1

64 비트 크기의 정수는 32 비트 x86 아키텍처에서 전혀 느리지 않습니다. 32 비트 정수만큼 빠르지는 않지만 분명히 느리지는 않습니다. x86 또는 x64와 상관없이 해시에 64 비트 int를 사용하는 것은 무모하지 않습니다. 추가 오버 헤드는 불필요한 동적 할당 또는 실패한 알고리즘과 비교하여 최소 일 것입니다.

Answer 2

해시 함수의 효율성을 크게 떨어 뜨릴 수 있습니까? 검사를 해봤 니? (i) 해시 된 항목의 수가 2^16을 훨씬 초과하고 (ii) 64 비트 해시를 계산하는 것이 저렴한 경우 확실하게 64 비트가 32 비트보다 우수한 해시입니다. 귀하의 경우 (i) 또는 (ii) 중 어느 것이 사실입니까? 성능이 중요한 경우 기본 운영 체제에 따라 다른 해시 함수를 사용할 수 있습니다. 그렇지 않으면, 나는 말할 것이다 : 32 비트 버전과 64 비트 버전 쓰기; 64 비트 시스템과 32 비트 시스템에서 둘 다 시도해보십시오. 너는 그 헛소리를 끝내는 것이 가치가 있는지를 보게 될 것이다.

Answer 3

컴파일러가 가장 빠른 코드를 생성한다고 생각하기 때문에 4 개의 32 비트 변수를 비교하는 것이 두 개의 64 비트 변수를 비교하는 것보다 빠르다고 생각하지 않습니다. 프로세서가 64 비트 연산을 지원하지 않으면, 컴파일러는 두 단계로 비교하는 코드를 생성합니다.
물론 이것은 컴파일러에 따라 다릅니다.

---

어쨌든, 더 빨리 당신의 비교를하게됩니다 다른 도구가 있지만, 한 번에 심지어 8 * 4 바이트를 비교할 수 있습니다 예를 들어,의 vectorial 작업 (SSE 확장에 의해 제공), 모든 곳에서 사용할 수 없습니다있다.

가능한 한 코드를 최적화해야하는 경우 시스템에서 지원할 때만 최적화를 활성화하기 위해 일부 전 처리기 지시문을 추가하는 것이 좋습니다.

Answer 4

내가 사용했던 모든 해시 함수는 문제를 방지하기 위해 바이트 배열 (uchar)의 값을 반환합니다.