해시 세트 성능 ADD VS는 기존 요소에 포함됩니다
-
06-07-2019 - |
문제
어떤 이유로 든 그것은 보인다 Add
a HashSet
보다 느립니다 Contains
요소가 이미 존재하는 경우 작동 HashSet
.
증거는 다음과 같습니다.
Stopwatch watch = new Stopwatch();
int size = 10000;
int iterations = 10000;
var s = new HashSet<int>();
for (int i = 0; i < size; i++) {
s.Add(i);
}
Console.WriteLine(watch.Time(() =>
{
for (int i = 0; i < size; i++) {
s.Add(i);
}
}, iterations));
s = new HashSet<int>();
for (int i = 0; i < size; i++) {
s.Add(i);
}
// outputs: 47,074,764
Console.WriteLine(watch.Time(() =>
{
for (int i = 0; i < size; i++) {
if (!s.Contains(i))
s.Add(i);
}
}, iterations));
// outputs: 41,125,219
왜 Contains
보다 빠른 Add
이미 존재하는 요소에 대해?
참고 : 나는 이것을 사용하고 있습니다 Stopwatch
다른 질문에서 확장.
public static long Time(this Stopwatch sw, Action action, int iterations) {
sw.Reset();
sw.Start();
for (int i = 0; i < iterations; i++) {
action();
}
sw.Stop();
return sw.ElapsedTicks;
}
업데이트: 내부 테스트에 따르면 큰 성능 차이는 .NET 프레임 워크의 X64 버전에서만 발생합니다. 32 비트 버전의 프레임 워크가 포함 된 경우 추가 속도로 추가되는 것처럼 보입니다 (실제로 포함 된 버전은 일부 테스트 실행에서 백분율이 느리게 실행되는 것으로 보입니다). 약 15% 더 빨리 실행하십시오.
해결책
AddifnotPresent는 수행되지 않는 추가 분할을 수행합니다. 포함 된 IL을 살펴보십시오.
IL_000a: call instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0)
IL_000f: stloc.0
IL_0010: ldarg.0
IL_0011: ldfld int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
IL_0016: ldloc.0
IL_0017: ldarg.0
IL_0018: ldfld int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
IL_001d: ldlen
IL_001e: conv.i4
IL_001f: rem
IL_0020: ldelem.i4
IL_0021: ldc.i4.1
IL_0022: sub
IL_0023: stloc.1
이것은 해시 코드의 버킷 위치를 계산하는 것입니다. 결과는 로컬 메모리 위치에 저장됩니다 1.
AddIfnotPresent는 비슷한 작업을 수행하지만 위치 2에서 계산 된 값을 저장하므로 항목이 존재하지 않으면 해당 위치의 해시 테이블에 항목을 삽입 할 수 있습니다. 위치 중 하나가 항목을 찾는 루프에서 나중에 수정되기 때문에 저장합니다. 어쨌든 다음은 addifnotpresent의 관련 코드입니다.
IL_0011: call instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0)
IL_0016: stloc.0
IL_0017: ldloc.0
IL_0018: ldarg.0
IL_0019: ldfld int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
IL_001e: ldlen
IL_001f: conv.i4
IL_0020: rem
IL_0021: stloc.1
IL_0022: ldarg.0
IL_0023: ldfld int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
IL_0028: ldloc.0
IL_0029: ldarg.0
IL_002a: ldfld int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets
IL_002f: ldlen
IL_0030: conv.i4
IL_0031: rem
IL_0032: ldelem.i4
IL_0033: ldc.i4.1
IL_0034: sub
IL_0035: stloc.2
어쨌든, 나는 여분의 분열이 추가 된 원인이 포함 된 것보다 더 많은 시간이 걸린다고 생각합니다. 언뜻보기에는 여분의 분열이 고려 될 수있는 것처럼 보이지만 IL을 해독하는 데 시간을 조금 더 쓰지 않고는 확실하게 말할 수는 없습니다.
다른 팁
흥미롭게도 내 컴퓨터 (Dell Latitude D630, Dual-Core 2.2 GHz)에서 스톱워치를 실행하지 않으면 두 테스트에 대해 거의 동일한 결과를 얻고 있습니다. null
테스트 전의 조치. 예를 들어:
질문에서 제공 한 정확한 코드로 테스트를 실행합니다.
Without Contains(): 8205794
With Contains(): 8207596
이 방식으로 코드를 수정하면 다음과 같습니다.
후에:
Stopwatch watch = new Stopwatch();
int size = 10000;
int iterations = 10000;
추가하다:
watch.Time(null, 0);
내 결과는 다음과 같습니다.
Without Contains(): 8019129
With Contains(): 8275771
이것은 이상한 일이 Stopwatch
이는 이러한 변동을 일으키고 있습니다.
내 생각에 당신은 비주얼 스튜디오에서 테스트를 실행하여 AddIfNotPresent
~ 안으로 Add
억제하려면 메소드 호출에서 추가 간접 수준의 결과가 나타납니다.
명령 줄에서 컴파일하고 실행되면 VS Trickery를 제거합니다 ...
> csc /o+ /t:exe Program.cs
> Program.exe
... 그러면 성능 차이가 없습니다.
샘플 출력 (더 많은 수의 테스트 대표) :
35036174
35153818
35225763
34862330
35047377
35033323