HASHSET desempenho adicionar vs contém para os elementos existentes

Question

Por algum motivo, parece o Add operação em a HashSet é mais lento que o Contains operação quando o elemento já existe no HashSet.

Aqui está a prova:

    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

Por que é Contains mais rápido que Add Para elementos já existentes?

Nota: estou usando isso Stopwatch Extensão de outra pergunta.

    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;
    }

ATUALIZAR: O teste interno revelou que o grande desempenho ocorre apenas na versão x64 da estrutura .NET. Com a versão de 32 bits da estrutura, parece ser executada em velocidade idêntica a acrescentar (na verdade, parece que a versão com o contém executa uma porcentagem mais lenta em algumas execuções de teste) em versões x64 da estrutura, a versão com a contém parece execute cerca de 15% mais rápido.

Answer 1

O AddifNotPresent faz uma divisão adicional que contém não executa. Dê uma olhada no IL para contém:

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

Isso está calculando o local do balde para o código de hash. O resultado é salvo no local da memória local 1.

O AddifNotPresent faz algo semelhante, mas também salva o valor calculado no local 2, para que ele possa inserir o item na tabela de hash nessa posição se o item não existir. Isso faz isso, porque um dos locais é modificado posteriormente no loop que procura o item. De qualquer forma, aqui está o código relevante para 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

De qualquer forma, acho que a divisão extra é o que está fazendo com que o adicione mais tempo do que contém. À primeira vista, parece que essa divisão extra pode ser levada em consideração, mas não posso dizer com certeza sem gastar um pouco mais de tempo decifrando o IL.

Answer 2

Interessante, na minha máquina (Dell Latitude D630, Dual-Core 2,2 GHz) Estou obtendo resultados quase idênticos para ambos os testes, a menos que eu execute o cronômetro contra um null ação antes dos testes. Por exemplo:

Eu corro os testes com o código exato que você deu na pergunta:

Without Contains(): 8205794
With Contains():    8207596

Se eu modificar o código dessa maneira:

Depois:

Stopwatch watch = new Stopwatch();
int size = 10000;
int iterations = 10000;

Adicionar:

watch.Time(null, 0);

Meus resultados se tornam:

Without Contains(): 8019129
With Contains():    8275771

Isso me parece que algo estranho está acontecendo dentro do Stopwatch Isso está causando essas flutuações.

Answer 3

Meu palpite é que você executou seu teste do Visual Studio, o que causou o inline AddIfNotPresent em Add Para serem suprimidos, você está vendo o resultado de um nível extra de indireção nas chamadas de método.

Se eu compilar e correr da linha de comando para remover qualquer truque vs ...

> csc /o+ /t:exe Program.cs
> Program.exe

... Então não há diferença de desempenho.

Saídas de amostra (representante de um número maior de testes):

35036174
35153818

35225763
34862330

35047377
35033323