sort - order array in c#




Por que o processamento de um array ordenado é mais lento que um array não classificado? (2)

O LINQ não sabe se a sua lista está ordenada ou não.

Como o parâmetro Count with predicate é o método de extensão para todos os IEnumerables, acho que ele nem sabe se está sendo executado na coleção com acesso aleatório eficiente. Então, ele simplesmente verifica cada elemento e o Usr explicou por que o desempenho diminuiu.

Para explorar os benefícios de desempenho do array ordenado (como a pesquisa binária), você terá que fazer um pouco mais de codificação.

Eu tenho uma lista de 500.000 Tuple<long,long,string> gerados aleatoriamente nos quais estou realizando uma simples pesquisa "entre":

var data = new List<Tuple<long,long,string>>(500000);
...
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);

Quando eu gero minha matriz aleatória e executo minha pesquisa para 100 valores gerados aleatoriamente de x , as pesquisas são concluídas em cerca de quatro segundos. Sabendo das grandes maravilhas que a classificação faz na pesquisa , no entanto, decidi classificar meus dados - primeiro por Item1 , depois por Item2 e finalmente por Item3 - antes de executar minhas 100 pesquisas. Eu esperava que a versão ordenada executasse um pouco mais rápido por causa da predição de ramificação: meu pensamento foi que uma vez que t.Item1 <= x ao ponto em que Item1 == x , todas as verificações adicionais de t.Item1 <= x preveriam a ramificação corretamente como "não take ", acelerando a parte final da pesquisa. Para minha surpresa, as buscas levaram o dobro do tempo em uma matriz ordenada !

Tentei alterar a ordem em que executei meus experimentos e usei semente diferente para o gerador de números aleatórios, mas o efeito foi o mesmo: as pesquisas em uma matriz não classificada foram executadas quase duas vezes mais rápido que as pesquisas na mesma matriz, mas classificado!

Alguém tem uma boa explicação desse efeito estranho? O código fonte dos meus testes segue; Eu estou usando o .NET 4.0.

private const int TotalCount = 500000;
private const int TotalQueries = 100;
private static long NextLong(Random r) {
    var data = new byte[8];
    r.NextBytes(data);
    return BitConverter.ToInt64(data, 0);
}
private class TupleComparer : IComparer<Tuple<long,long,string>> {
    public int Compare(Tuple<long,long,string> x, Tuple<long,long,string> y) {
        var res = x.Item1.CompareTo(y.Item1);
        if (res != 0) return res;
        res = x.Item2.CompareTo(y.Item2);
        return (res != 0) ? res : String.CompareOrdinal(x.Item3, y.Item3);
    }
}
static void Test(bool doSort) {
    var data = new List<Tuple<long,long,string>>(TotalCount);
    var random = new Random(1000000007);
    var sw = new Stopwatch();
    sw.Start();
    for (var i = 0 ; i != TotalCount ; i++) {
        var a = NextLong(random);
        var b = NextLong(random);
        if (a > b) {
            var tmp = a;
            a = b;
            b = tmp;
        }
        var s = string.Format("{0}-{1}", a, b);
        data.Add(Tuple.Create(a, b, s));
    }
    sw.Stop();
    if (doSort) {
        data.Sort(new TupleComparer());
    }
    Console.WriteLine("Populated in {0}", sw.Elapsed);
    sw.Reset();
    var total = 0L;
    sw.Start();
    for (var i = 0 ; i != TotalQueries ; i++) {
        var x = NextLong(random);
        var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
        total += cnt;
    }
    sw.Stop();
    Console.WriteLine("Found {0} matches in {1} ({2})", total, sw.Elapsed, doSort ? "Sorted" : "Unsorted");
}
static void Main() {
    Test(false);
    Test(true);
    Test(false);
    Test(true);
}
Populated in 00:00:01.3176257
Found 15614281 matches in 00:00:04.2463478 (Unsorted)
Populated in 00:00:01.3345087
Found 15614281 matches in 00:00:08.5393730 (Sorted)
Populated in 00:00:01.3665681
Found 15614281 matches in 00:00:04.1796578 (Unsorted)
Populated in 00:00:01.3326378
Found 15614281 matches in 00:00:08.6027886 (Sorted)

Quando você está usando a lista não classificada, todas as tuplas são acessadas em ordem de memória . Eles foram alocados consecutivamente na RAM. As CPUs adoram acessar memória sequencialmente porque podem solicitar especulativamente a próxima linha de cache para que ela sempre esteja presente quando necessário.

Quando você está classificando a lista, você a coloca em ordem aleatória, porque as chaves de ordenação são geradas aleatoriamente. Isso significa que a memória acessa os membros da tupla é imprevisível. A CPU não consegue pré-buscar memória e quase todo acesso a uma tupla é uma falta de cache.

Este é um bom exemplo de uma vantagem específica do gerenciamento de memória do GC : estruturas de dados que foram alocadas juntas e usadas juntas funcionam muito bem. Eles têm grande localidade de referência .

A penalidade de falta de cache supera a penalidade de previsão de filial salva neste caso.

Tente mudar para um conjunto de struct . Isso restaurará o desempenho porque não é necessário nenhum cancelamento de ponteiro em tempo de execução para acessar os membros da tupla.

Chris Sinclair observa nos comentários que "para o TotalCount em torno de 10.000 ou menos, a versão ordenada é mais rápida ". Isso ocorre porque uma lista pequena se encaixa totalmente no cache da CPU . Os acessos à memória podem ser imprevisíveis, mas o destino está sempre em cache. Eu acredito que ainda há uma pequena penalidade porque até mesmo uma carga do cache leva alguns ciclos. Mas isso não parece ser um problema porque a CPU pode manipular várias cargas pendentes , aumentando assim o rendimento. Sempre que a CPU atingir uma espera pela memória, ela ainda acelerará no fluxo de instrução para enfileirar quantas operações de memória puder. Essa técnica é usada para ocultar a latência.

Esse tipo de comportamento mostra como é difícil prever o desempenho em CPUs modernas. O fato de sermos apenas 2x mais lentos ao passar do acesso sequencial à memória aleatória me diz o quanto está acontecendo sob as capas para ocultar a latência da memória. Um acesso à memória pode parar a CPU por 50 a 200 ciclos. Dado que o número um poderia esperar que o programa se tornasse 10x mais lento ao introduzir acessos aleatórios de memória.





language-agnostic