Почему обработка отсортированного массива медленнее, чем не отсортированного массива?

У меня есть список из 500000 случайно сгенерированных Tuple<long,long,string> объектов, по которым я выполняю простой поиск между ними:

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

Когда я генерирую свой случайный массив и запускаю поиск по 100 случайно сгенерированным значениям x, поиск завершается примерно за четыре секунды. Однако, зная о чудесах, которые сортировка делает для поиска , я решил отсортировать свои данные - сначала по Item1, затем по Item2, наконец, по Item3- перед выполнением моих 100 поисков. Я ожидал, что отсортированная версия будет работать немного быстрее из-за предсказания ветвления: я думал, что, как только мы доберемся до точки, где Item1 == xвсе дальнейшие проверки t.Item1 <= xбудут предсказывать ветвление правильно, как «не брать», ускоряя хвостовую часть поиск. К моему удивлению, поиски заняли вдвое больше времени в отсортированном массиве !

Я попытался переключить порядок, в котором я проводил свои эксперименты, и использовал другое начальное число для генератора случайных чисел, но эффект был тот же: поиск в несортированном массиве выполнялся почти в два раза быстрее, чем поиск в том же массиве, но сортируется!

У кого-нибудь есть хорошее объяснение этого странного эффекта? Исходный код моих тестов приведен ниже; Я использую .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)

Когда вы используете несортированный список, все кортежи доступны в порядке . Они были последовательно расположены в оперативной памяти. Процессоры любят обращаться к памяти последовательно, потому что они могут спекулятивно запрашивать следующую строку кэша, поэтому она всегда будет присутствовать при необходимости.

Когда вы сортируете список, вы помещаете его в случайный порядок, потому что ваши ключи сортировки генерируются случайным образом. Это означает, что доступ к памяти для членов кортежа непредсказуем. Процессор не может предварительно извлечь память, и почти каждый доступ к кортежу является пропуском кеша.

Это хороший пример конкретного преимущества управления памятью GC : структуры данных, которые были выделены вместе и используются вместе, работают очень хорошо. У них отличное месторасположение .

В этом случае штраф за пропуск кеша перевешивает сохраненный штраф за предсказание перехода .

Попробуйте переключиться на struct-tuple. Это восстановит производительность, потому что не требуется разыменование указателя во время выполнения для доступа к членам кортежа.

Крис Синклер отмечает в комментариях, что «для TotalCount около 10000 или меньше, отсортированная версия работает быстрее ». Это связано с тем, что небольшой список целиком помещается в кэш процессора . Доступ к памяти может быть непредсказуемым, но цель всегда находится в кэше. Я считаю, что все еще есть небольшое наказание, потому что даже загрузка из кэша занимает несколько циклов. Но, похоже, это не проблема, поскольку процессор может манипулировать несколькими невыполненными нагрузками , увеличивая тем самым пропускную способность. Всякий раз, когда ЦП ожидает ожидания памяти, он все еще ускоряется в потоке команд, чтобы поставить в очередь столько операций с памятью, сколько он может. Эта техника используется, чтобы скрыть задержку.

Такое поведение показывает, насколько сложно прогнозировать производительность на современных процессорах. Тот факт, что мы только в 2 раза медленнее при переходе от последовательного к произвольному доступу к памяти, говорит мне, сколько всего происходит под прикрытием, чтобы скрыть задержку памяти. Доступ к памяти может остановить процессор на 50-200 циклов. Учитывая это число, можно ожидать, что программа станет> в 10 раз медленнее при введении случайного доступа к памяти.

LINQ не знает, отсортирован ли ваш список или нет.

Поскольку Count с параметром предиката является методом расширения для всех IEnumerables, я думаю, он даже не знает, работает ли он над коллекцией с эффективным произвольным доступом. Итак, он просто проверяет каждый элемент, и Usr объяснил, почему производительность снизилась.

Чтобы использовать преимущества производительности отсортированного массива (например, бинарный поиск), вам придется немного больше кодировать.