C#에서 해시 테이블이 C++보다 빠릅니까?

Question

여기 제가 조사해 본 호기심이 있습니다. .NET Dictionary 클래스는 계속 실행중인 테스트에서 STL unordered_map과 비교하여 엄청나게 빠르며 그 이유를 알 수 없습니다.

(0.5 초 대 내 컴퓨터 4 초) 나는 C# 및 C에 내 자신의 해시 테이블을 구현하는 경우, 다른 한편으로

(비주얼 스튜디오 2008 익스프레스 SP1의 STL 대 .NET 3.5 SP1), ++ , C++ 버전은 C# 1의 두 배 정도 빠르며, 이는 네이티브 컴퓨터 코드가 가끔 더 빠른 상식을 강화하기 때문에 정상입니다. ("때때로"라고 말했죠.) 두 언어로 같은 사람이되어서, 마이크로 소프트의 C# 코더가 마이크로 소프트의 C++ 코더가 놀 수있는 트릭이 뭔지 궁금합니다. 필자는 컴파일러가 이러한 트릭을 독자적으로 수행 할 수있는 방법을 상상할 수 없으며, 임의의 함수 호출로 간주해야하는 것을 최적화하는 문제를 겪고 있습니다.

정수를 저장하고 검색하는 간단한 테스트입니다.

C 번호 :

const int total = (1 << 20); 
int sum = 0; 
Dictionary<int, int> dict = new Dictionary<int, int>(); 
for(int i = 0; i < total; i++) 
{ 
    dict.Add(i, i * 7); 
} 

for(int j = 0; j < (1 << 3); j++) 
{ 
    int i = total; 
    while(i > 0) 
    { 
     i--; 
     sum += dict[i]; 
    } 
} 
Console.WriteLine(sum); 

C++ :

const int total = (1 << 20); 
int sum = 0; 
std::tr1::unordered_map<int, int> dict; 
for(int i = 0; i < total; i++) 
{ 
    dict.insert(pair<int, int>(i, i * 7)); 
} 

for(int j = 0; j < (1 << 3); j++) 
{ 
    int i = total; 
    while(i > 0) 
    { 
     i--; 
     std::tr1::unordered_map<int, int>::const_iterator found = 
      dict.find(i); 
     sum += found->second; 
    } 
} 
cout << sum << endl; 

Answer 1

두 가지 버전이 루프 동안 당신의 C++의 각 패스에 반복자를 구축하는, 동등하지 않다. CPU 시간이 걸리고 결과를 던집니다.

Answer 2

코드 수준에서 약간의 차이가 있습니다. 순서가 지정되지 않은 맵이 쌍을 취한다는 사실은 Add에서 두 매개 변수를 전달할 때 C#이 더 빠를 때 이러한 개체의 생성을 강제합니다.

또 다른 요점은 해시 테이블 자체의 구현입니다. 해시 함수를 구현하거나 충돌을 처리하는 방법은 다른 성능 패턴을 유발합니다.

정렬 및 캐싱, 일부 알고리즘의 JIT 친숙성 및 두 가지 다른 언어로 구현 된 두 가지 구현을 비교하는 것은 매우 어려워지고 비교할 수있는 유일한 작업은 현재 수행중인 특정 작업입니다. 적은 수의 요소로 시도하거나 순서가 아닌 임의의 요소에 액세스하려고하면 매우 다른 결과가 표시 될 수 있습니다.

Answer 3

명시 적 메모리 관리 비용을 측정하고 있습니다. 더 많은 통계를 볼 수 있습니다 here. 이것은 relevant too.이며 CLR에 결정론적인 마무리를 추가하는 Chris Sells' attempt은 주목할만한 것입니다.