Por que o processamento de uma matriz classificada é mais lento que uma matriz não classificada?

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

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 por 100 valores gerados aleatoriamente x, as pesquisas são concluídas em cerca de quatro segundos. No entanto, conhecendo as grandes maravilhas que a classificação faz na pesquisa , decidi classificar meus dados - primeiro Item1, depois Item2e finalmente Item3- antes de executar minhas 100 pesquisas. Eu esperava que a versão classificada tivesse um desempenho mais rápido por causa da previsão de ramificação: meu pensamento é que, quando chegamos ao ponto em que Item1 == xtodas as verificações adicionais t.Item1 <= xpreveriam a ramificação corretamente como "não tomada", acelerando a parte final do procurar. Para minha surpresa, as pesquisas levaram o dobro do tempo em uma matriz classificada !

Tentei alternar na ordem em que conduzi meus experimentos e usei sementes diferentes para o gerador de números aleatórios, mas o efeito foi o mesmo: pesquisas em uma matriz não classificada eram quase duas vezes mais rápidas que as pesquisas na mesma matriz, mas ordenado!

Alguém tem uma boa explicação para esse efeito estranho? O código fonte dos meus testes segue; 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 a memória sequencialmente porque podem solicitar especulativamente a próxima linha de cache, para que ela esteja sempre presente quando necessário.

Ao classificar a lista, você a coloca em ordem aleatória, porque suas chaves de classificação são geradas aleatoriamente. Isso significa que os acessos de memória aos membros da tupla são imprevisíveis. A CPU não pode buscar previamente a memória e quase todo acesso a uma tupla é um erro de cache.

Este é um bom exemplo de uma vantagem específica do gerenciamento de memória do GC : as estruturas de dados que foram alocadas em conjunto e usadas em conjunto têm um desempenho muito bom. Eles têm ótima localidade de referência .

A penalidade por falta de cache supera a penalidade de previsão de ramificação salva neste caso.

Tente mudar para um structmúltiplo. Isso restaurará o desempenho porque nenhuma referência de ponteiro precisa ocorrer no 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 classificada apresenta desempenho mais rápido ". Isso ocorre porque uma pequena lista se encaixa inteiramente no cache da CPU . Os acessos à memória podem ser imprevisíveis, mas o destino está sempre em cache. Acredito que ainda haja uma pequena penalidade, porque 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 a taxa de transferência. Sempre que a CPU aguarda uma espera pela memória, ela ainda avança no fluxo de instruções para colocar na fila o maior número possível de operações de memória. Essa técnica é usada para ocultar a latência.

Esse tipo de comportamento mostra o quão difícil é prever o desempenho em CPUs modernas. O fato de sermos apenas duas vezes mais lento quando passamos do acesso seqüencial para o aleatório pela memória me diz o quanto está acontecendo nos bastidores para ocultar a latência da memória. Um acesso à memória pode paralisar a CPU por 50-200 ciclos. Dado que o número um poderia esperar que o programa se tornasse> 10x mais lento ao introduzir acessos aleatórios à memória.

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

Como Count com predicate parâmetro é o método de extensão para todos os IEnumerables, acho que ele nem sabe se está executando a coleção com acesso aleatório eficiente. Portanto, ele simplesmente verifica todos os elementos e o Usr explicou por que o desempenho ficou mais baixo.

Para explorar os benefícios de desempenho da matriz classificada (como pesquisa binária), você precisará fazer um pouco mais de codificação.