Почему обработка отсортированного массива медленнее, чем несортированный массив?
У меня есть список из 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)
Ответы
Ответ 1
При использовании несортированного списка все кортежи доступны в порядке памяти. Они были выделены последовательно в ОЗУ. ЦП любят последовательно получать доступ к памяти, поскольку они могут умозрительно запросить следующую строку кэша, чтобы она всегда присутствовала при необходимости.
Когда вы сортируете список, вы помещаете его в случайный порядок, потому что ваши ключи сортировки генерируются случайным образом. Это означает, что доступ к памяти для членов кортежа непредсказуем. ЦП не может предварительно запрограммировать память, и почти каждый доступ к кортежу является пропуском кеша.
Это хороший пример для конкретного преимущества управления памятью GC: структуры данных, которые были распределены вместе и используются вместе, работают очень хорошо. Они имеют большую локальность ссылки.
В этом случае штраф из пропусков кеша перевешивает сохраненный штраф предсказания ветвления.
Попробуйте переключиться на struct -tuple. Это приведет к восстановлению производительности, поскольку во время выполнения во время выполнения не требуется разыменовать указатель, чтобы получить доступ к элементам кортежа.
Крис Синклер отмечает в комментариях, что "для TotalCount около 10 000 или менее отсортированная версия выполняет быстрее". Это связано с тем, что небольшой список полностью помещается в кеш процессора. Доступ к памяти может быть непредсказуемым, но цель всегда находится в кеше. Я считаю, что по-прежнему существует небольшой штраф, потому что даже загрузка из кеша занимает несколько циклов. Но это, похоже, не проблема, потому что процессор может манипулировать несколькими невыполненными нагрузками, тем самым увеличивая пропускную способность. Всякий раз, когда процессор достигает ожидания в памяти, он все равно ускоряется вперед в потоке команд, чтобы поставить в очередь столько операций памяти, сколько может. Этот метод используется для скрытия латентности.
Такое поведение показывает, насколько сложно прогнозировать производительность на современных процессорах. Тот факт, что мы только в 2 раза медленнее при переходе от последовательного к случайному доступу к памяти, подскажет, сколько времени происходит под обложками, чтобы скрыть латентность памяти. Доступ к памяти может остановить CPU на 50-200 циклов. Учитывая, что номер один может ожидать, что программа станет > 10x медленнее при вводе случайных обращений к памяти.
Ответ 2
LINQ не знает, отсортирован ли список, или нет.
Так как Count с предикатным параметром является методом расширения для всех IEnumerables, я думаю, что он даже не знает, работает ли он над коллекцией с эффективным случайным доступом. Таким образом, он просто проверяет каждый элемент, и Usr объясняет, почему производительность снижается.
Чтобы использовать преимущества производительности отсортированного массива (например, двоичный поиск), вам нужно будет немного немного кодировать.
