c# - элемента - удалить элемент массива со сдвигом java




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

У меня есть список из 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 запросов. Я ожидал, что отсортированная версия будет выполняться немного быстрее из-за предсказания ветвления: я думал, что как только мы t.Item1 <= x до точки, где Item1 == x , все дальнейшие проверки t.Item1 <= x будут правильно предсказать ветвь, поскольку «no взять ", ускоряя хвостовую часть поиска. К моему большому удивлению, поиски занимали в два раза больше сортированного массива !

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

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

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

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

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


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

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

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

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

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

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

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





language-agnostic