Улучшение "перемешивания" эффективности

Question

Сейчас я использую следующий код для создания расширения Shuffle:

public static class SiteItemExtensions
{
    public static void Shuffle<T>(this IList<T> list)
    {
        var rng = new Random();
        int n = list.Count;
        while (n > 1)
        {
            n--;
            int k = rng.Next(n + 1);
            T value = list[k];
            list[k] = list[n];
            list[n] = value;
        }
    }
}

Я ищу более быстрый и эффективный способ сделать это. Прямо сейчас, используя класс секундомера, требуется около 20 секунд, чтобы перетасовать 100 000 000 предметов. У кого-нибудь есть идеи как сделать это быстрее?

Answer 1

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

            int k = 0; rng.Next(n + 1);  // silly change

Теперь во внутреннем цикле есть больше операторов, но это намного быстрееТо, что вы видите, - это эффект кеша процессора.Этот алгоритм имеет очень плохую локальность кэша, и вероятность того, что следующий элемент, который будет считан из массива, уже находится в кэше, очень мала.Который занимает дорогое путешествие к более медленным внешним кэшам и до невероятно медленной шине памяти.Вероятность того, что элементы из необходимого позже массива будут загружены в кеш, очень высока.Но вероятность того, что они все еще существуют, когда это необходимо, очень мала, ваш список просто слишком велик, чтобы уместить кеш.Однако использование реалистичных размеров списков является очевидным решением.Запуск его 100 000 раз в списке из 1000 элементов в 3 раза быстрее.

Answer 2

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

Постепенно уменьшая количество элементов, я получаю следующие результаты (на List<int>):

count      time (s)     slowdown
100000000  16.0429005   11.99215276436421
10000000   01.3377832   20.37312930505406
1000000    00.0656641   13.36837069158574
100000     00.0049119

Обратите внимание на большое замедление между 10 ^ 6 и 10 ^ 7. Я увеличил количество элементов в 10 раз, но время увеличилось в 20 раз. Вероятно, именно здесь мой ЦП больше не может помещать большую часть массива на 2-й (и последний на моем ЦП) уровень кэша.

Кстати, вы можете получить секунду или две (но потерять общность), заменив IList<T> на List<T> в сигнатуре метода и избежав штрафа за интерфейсный вызов на []:

IList<T>:   16.0429005 s
List<T>:    14.3529349 s

Для записи в Visual C ++ 2010 std::random_shuffle на std::vector<int> с 100000000 элементов занимает ...

17.947 s

... так что вы, вероятно, уже так быстро, как только можете.

(ПРИМЕЧАНИЕ. Тесты C # и C ++ выполнялись в соответствующих конфигурациях Release вне отладчика.)