해시 세트 성능 ADD VS는 기존 요소에 포함됩니다

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

  •  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
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top