Tempos de execução inesperados para o código HashSet

28

Então, originalmente, eu tinha esse código:

import java.util.*;

public class sandbox {
    public static void main(String[] args) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < 100_000; i++) {
            hashSet.add(i);
        }

        long start = System.currentTimeMillis();

        for (int i = 0; i < 100_000; i++) {
            for (Integer val : hashSet) {
                if (val != -1) break;
            }

            hashSet.remove(i);
        }

        System.out.println("time: " + (System.currentTimeMillis() - start));
    }
}

Demora cerca de 4s para executar os loops aninhados no meu computador e não entendo por que demorou tanto. O loop externo executa 100.000 vezes, o loop for interno deve executar 1 vez (porque qualquer valor de hashSet nunca será -1) e a remoção de um item de um HashSet é O (1), portanto, deve haver cerca de 200.000 operações. Se normalmente existem 100.000.000 de operações em um segundo, como meu código leva 4s para ser executado?

Além disso, se a linha hashSet.remove(i);for comentada, o código leva apenas 16ms. Se o loop for interno for comentado (mas não hashSet.remove(i);), o código leva apenas 8ms.

davidSC
fonte
4
Confirmo suas descobertas. Eu poderia especular sobre o motivo, mas espero que alguém inteligente publique uma explicação fascinante.
Khelwood
11
Parece que o for valloop está ocupando o tempo. O removeainda é muito rápido. Algum tipo de sobrecarga que configura um novo iterador após a modificação do conjunto ...?
Khelwood
O @apangin forneceu uma boa explicação em stackoverflow.com/a/59522575/108326 sobre por que o for valloop é lento. No entanto, observe que o loop não é necessário. Se você deseja verificar se existem valores diferentes de -1 no conjunto, seria muito mais eficiente verificar hashSet.size() > 1 || !hashSet.contains(-1).
markusk

Respostas:

32

Você criou um caso de uso marginal de HashSet, em que o algoritmo se degrada para a complexidade quadrática.

Aqui está o loop simplificado que leva tanto tempo:

for (int i = 0; i < 100_000; i++) {
    hashSet.iterator().next();
    hashSet.remove(i);
}

o async-profiler mostra que quase todo o tempo é gasto dentro do java.util.HashMap$HashIterator()construtor:

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
--->        do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

A linha destacada é um loop linear que procura o primeiro bloco não vazio na tabela de hash.

Como Integerpossui o trivial hashCode(por exemplo, hashCode é igual ao número em si), verifica-se que os números inteiros consecutivos ocupam principalmente os buckets consecutivos na tabela de hash: número 0 vai para o primeiro bucket, número 1 vai para o segundo bucket, etc.

Agora você remove os números consecutivos de 0 a 99999. No caso mais simples (quando o bucket contém uma única chave), a remoção de uma chave é implementada como anulando o elemento correspondente na matriz do bucket. Observe que a tabela não é compactada ou reformulada após a remoção.

Portanto, quanto mais chaves você remover do início da matriz do balde, mais HashIteratorprecisará encontrar o primeiro balde não vazio.

Tente remover as chaves da outra extremidade:

hashSet.remove(100_000 - i);

O algoritmo se tornará dramaticamente mais rápido!

apangin
fonte
11
Ahh, me deparei com isso, mas o demiti após as primeiras execuções e pensei que isso poderia ser uma otimização do JIT e passei a analisar via JITWatch. Deveria ter executado o async-profiler primeiro. Droga!
Adwait Kumar
11
Bastante interessante. Se você faz algo como o seguinte no circuito, ele acelera-lo, reduzindo o tamanho do mapa interno: if (i % 800 == 0) { hashSet = new HashSet<>(hashSet); }.
Gray - Então, pare de ser mau