Подтвердить что ты не робот

Почему .NET group by (намного) медленнее, когда число ведер растет

Учитывая этот простой фрагмент кода и 10 миллионов массивов случайных чисел:

static int Main(string[] args)
    {
        int size = 10000000;
        int num =  10; //increase num to reduce number of buckets
        int numOfBuckets = size/num;
        int[] ar = new int[size];
        Random r = new Random(); //initialize with randum numbers
        for (int i = 0; i < size; i++)
            ar[i] = r.Next(size);

        var s = new Stopwatch();
        s.Start();
        var group = ar.GroupBy(i => i / num);
        var l = group.Count();
        s.Stop();

        Console.WriteLine(s.ElapsedMilliseconds);
        Console.ReadLine();
        return 0;
    }

Я сделал некоторую производительность при группировке, поэтому, когда количество ведер составляет 10 тыс., расчетное время выполнения составляет 0,7 с, для 100 тыс. ведер - 2 с, для 1 м - 7,5 с.

Интересно, почему. Я предполагаю, что если GroupBy реализован с использованием HashTable, может возникнуть проблема с коллизиями. Например, изначально хеш-таблица готовится к работе, чтобы сказать 1000 групп, а затем, когда число групп растет, необходимо увеличить размер и выполнить повторную запись. Если бы это было так, я мог бы написать свою собственную группу, где я бы инициализировал HashTable с ожидаемым количеством ведер, я сделал это, но это было только немного быстрее.

Итак, мой вопрос: почему количество ведер сильно влияет на производительность GroupBy?

EDIT: работающий под режимом освобождения, меняет результаты на 0,55, 1,6, 6,5 с соответственно.

Я также сменил группу. ToArray на фрагмент кода ниже, чтобы принудительно выполнить группировку:

foreach (var g in group)
    array[g.Key] = 1;

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

EDIT2: Вы можете увидеть рабочий код из mellamokb здесь pastebin.com/tJUYUhGL

4b9b3361

ОТВЕТЫ

Ответ 1

Я почти уверен, что это показывает влияние местоположения памяти (различные уровни кэширования) и распределение объектов alos.

Чтобы проверить это, я сделал три шага:

  • Улучшите бенчмаркинг, чтобы избежать ненужных деталей и сбора мусора между тестами
  • Удалите часть LINQ, заполнив Dictionary (что эффективно, что GroupBy делает за кулисами)
  • Удалите даже Dictionary<,> и покажите ту же тенденцию для простых массивов.

Чтобы показать это для массивов, мне нужно увеличить размер ввода, но он показывает тот же рост.

Здесь короткая, но полная программа, которая может быть использована для проверки словаря и стороны массива - просто переверните, какая строка закомментирована посередине:

using System;
using System.Collections.Generic;
using System.Diagnostics;

class Test
{    
    const int Size = 100000000;
    const int Iterations = 3;

    static void Main()
    {
        int[] input = new int[Size];
        // Use the same seed for repeatability
        var rng = new Random(0);
        for (int i = 0; i < Size; i++)
        {
            input[i] = rng.Next(Size);
        }

        // Switch to PopulateArray to change which method is tested
        Func<int[], int, TimeSpan> test = PopulateDictionary;

        for (int buckets = 10; buckets <= Size; buckets *= 10)
        {
            TimeSpan total = TimeSpan.Zero;
            for (int i = 0; i < Iterations; i++)
            {
                // Switch which line is commented to change the test
                // total += PopulateDictionary(input, buckets);
                total += PopulateArray(input, buckets);
                GC.Collect();
                GC.WaitForPendingFinalizers();
            }
            Console.WriteLine("{0,9}: {1,7}ms", buckets, (long) total.TotalMilliseconds);
        }
    }

    static TimeSpan PopulateDictionary(int[] input, int buckets)
    {
        int divisor = input.Length / buckets;
        var dictionary = new Dictionary<int, int>(buckets);
        var stopwatch = Stopwatch.StartNew();
        foreach (var item in input)
        {
            int key = item / divisor;
            int count;
            dictionary.TryGetValue(key, out count);
            count++;
            dictionary[key] = count;
        }
        stopwatch.Stop();
        return stopwatch.Elapsed;
    }

    static TimeSpan PopulateArray(int[] input, int buckets)
    {
        int[] output = new int[buckets];
        int divisor = input.Length / buckets;
        var stopwatch = Stopwatch.StartNew();
        foreach (var item in input)
        {
            int key = item / divisor;
            output[key]++;
        }
        stopwatch.Stop();
        return stopwatch.Elapsed;
    }
}

Результаты на моей машине:

PopulateDictionary:

       10:   10500ms
      100:   10556ms
     1000:   10557ms
    10000:   11303ms
   100000:   15262ms
  1000000:   54037ms
 10000000:   64236ms // Why is this slower? See later.
100000000:   56753ms

PopulateArray:

       10:    1298ms
      100:    1287ms
     1000:    1290ms
    10000:    1286ms
   100000:    1357ms
  1000000:    2717ms
 10000000:    5940ms
100000000:    7870ms

В более ранней версии PopulateDictionary использовался класс Int32Holder и создавался по одному для каждого ведра (когда поиск в словаре не удался). Это было быстрее, когда было небольшое количество ведер (по-видимому, потому, что мы проходили путь поиска по словарю один раз на итерацию, а не дважды), но были значительно медленнее и закончились нехваткой памяти. Разумеется, это также способствовало бы фрагментированному доступу к памяти. Обратите внимание, что PopulateDictionary указывает емкость, с которой можно начать, чтобы избежать эффектов копирования данных в тесте.

Цель использования метода PopulateArray состоит в том, чтобы удалить как можно больше кода структуры, оставив при этом меньше воображения. Я еще не пробовал использовать массив настраиваемой структуры (с различными размерами структуры), но это может быть и то, что вы тоже хотели бы попробовать.

EDIT: я могу воспроизвести странность более медленного результата для 10000000, чем 100000000 по желанию, независимо от порядка тестирования. Я пока не понимаю, почему. Это может быть специфично для конкретного процессора и кеша, которые я использую...

- EDIT -

Причина, по которой 10000000 медленнее, чем результаты 100000000, связана с тем, как работает хеширование. Еще несколько тестов объясняют это.

Прежде всего, давайте посмотрим на операции. Там Dictionary.FindEntry, который используется в индексе [] и в Dictionary.TryGetValue, а там Dictionary.Insert, который используется в индексировании [] и в Dictionary.Add. Если бы мы просто выполнили FindEntry, тайминги будут расти, как мы ожидаем:

static TimeSpan PopulateDictionary1(int[] input, int buckets)
{
    int divisor = input.Length / buckets;
    var dictionary = new Dictionary<int, int>(buckets);
    var stopwatch = Stopwatch.StartNew();
    foreach (var item in input)
    {
        int key = item / divisor;
        int count;
        dictionary.TryGetValue(key, out count);
    }
    stopwatch.Stop();
    return stopwatch.Elapsed;
}

Это реализация не имеет дело с хеш-коллизиями (потому что их нет), что делает поведение, как мы ожидаем. Как только мы начнем сталкиваться с столкновениями, тайминги начинают падать. Если у нас столько ведер как элементов, очевидно, что меньше столкновений... Точнее, мы можем точно определить, сколько коллизий существует:

static TimeSpan PopulateDictionary(int[] input, int buckets)
{
    int divisor = input.Length / buckets;
    int c1, c2;
    c1 = c2 = 0;
    var dictionary = new Dictionary<int, int>(buckets);
    var stopwatch = Stopwatch.StartNew();
    foreach (var item in input)
    {
        int key = item / divisor;
        int count;
        if (!dictionary.TryGetValue(key, out count))
        {
            dictionary.Add(key, 1);
            ++c1;
        }
        else
        {
            count++;
            dictionary[key] = count;
            ++c2;
        }
    }
    stopwatch.Stop();
    Console.WriteLine("{0}:{1}", c1, c2);
    return stopwatch.Elapsed;
}

Результат выглядит примерно так:

10:99999990
       10:    4683ms
100:99999900
      100:    4946ms
1000:99999000
     1000:    4732ms
10000:99990000
    10000:    4964ms
100000:99900000
   100000:    7033ms
1000000:99000000
  1000000:   22038ms
9999538:90000462       <<-
 10000000:   26104ms
63196841:36803159      <<-
100000000:   25045ms

Обратите внимание на значение "36803159". Это отвечает на вопрос, почему последний результат быстрее, чем первый результат: он просто должен делать меньше операций - и поскольку кэширование в любом случае терпит неудачу, этот фактор больше не имеет значения.

Ответ 2

10k расчетное время исполнения составляет 0,7 с, для ковшей 100 тыс. - 2 с, для 1 м - 7,5 с.

Это важный шаблон для распознавания кода профайла. Это один из стандартных соотношений времени и времени выполнения программных алгоритмов. Просто наблюдая за поведением, вы можете многое рассказать о способе реализации алгоритма. И наоборот, конечно, из алгоритма вы можете предсказать ожидаемое время выполнения. Отношение, которое аннотируется в Big Oh notation.

Самый быстрый код, который вы можете получить, амортизируется O (1), время выполнения едва увеличивается при удвоении размера проблемы. Класс "Словарь < > ведет себя таким образом, как продемонстрировал Джон. Увеличение времени по мере того, как задание становится большим, является" амортизированной" частью. Побочный эффект словаря, который должен выполнять линейный поиск O (n) в ведрах, которые продолжают увеличиваться.

Очень распространенный шаблон - O (n). Это говорит о том, что в алгоритме, который выполняет итерацию по коллекции, существует одиночный цикл for(). O (n ^ 2) говорит вам, что есть два вложенных цикла for(). O (n ^ 3) имеет три и т.д.

То, что вы получили, находится между ними, O (log n). Это стандартная сложность алгоритма разделения и покорения. Другими словами, каждый проход разбивает проблему на две части, продолжая меньший набор. Очень часто вы видите его в алгоритмах сортировки. Двоичный поиск - это тот, который вы нашли в своем учебнике. Обратите внимание, как log₂ (10) = 3,3, очень близко к инкременту, который вы видите в своем тесте. Perf начинает танковать бит для очень больших наборов из-за плохой локальности ссылки, проблемы кэша процессора, которые всегда связаны с алгоритмами O (log n).

Единственное, что Джон говорит, это то, что его догадка не может быть правильной, GroupBy(), конечно, не использует словарь < > . И это невозможно по дизайну, Dictionary < > не может предоставить упорядоченную коллекцию. Где GroupBy() должен быть заказан, он говорит об этом в библиотеке MSDN:

Объекты IGrouping приводятся в порядке, основанном на порядке элементов в источнике, который создавал первый ключ каждой группы IGrouping. Элементы в группировке выводятся в том порядке, в котором они появляются в источнике.

Не нужно поддерживать порядок, что делает Dictionary < > fast. Ведение порядка всегда стоит O (log n), двоичное дерево в вашем учебнике.

Короче говоря, если вы действительно не заботитесь о порядке, и вы наверняка не будете использовать случайные числа, то вы не хотите использовать GroupBy(). Вы хотите использовать словарь < > .

Ответ 3

Есть (по крайней мере) два фактора влияния: во-первых, поиск хэш-таблицы требует только O (1), если у вас есть идеальная хеш-функция, которой не существует. Таким образом, у вас есть хеш-коллизии.

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

Ответ 4

Здесь есть несколько факторов.

Хеши и группировки

Как работает группировка, создается хеш-таблица. Затем каждая отдельная группа поддерживает операцию "добавить", которая добавляет элемент в список добавления. Если говорить прямо, это похоже на Dictionary<Key, List<Value>>.

Таблицы хэшей всегда сгруппированы. Если вы добавите элемент в хэш, он проверяет, есть ли достаточная емкость, а если нет, воссоздает хеш-таблицу с большей емкостью (точнее: new capacity = count * 2 с подсчетом количества групп). Однако большая емкость означает, что индекс ведра больше не верен, а это значит, что вам нужно перестроить записи в хеш-таблице. Этот метод Resize() в Lookup<Key, Value> делает это.

"Группы" работают как a List<T>. Они также являются общими, но их легче перераспределить. Если быть точным: данные просто копируются (с Array.Copy в Array.Resize) и добавляется новый элемент. Поскольку нет повторного хеширования или расчета, это довольно быстрая операция.

Первоначальная емкость группировки равна 7. Это означает, что для 10 элементов вам необходимо перераспределить 1 раз, для 100 элементов 4 раза, для 1000 элементов 8 раз и так далее. Поскольку каждый раз вам нужно повторно отображать больше элементов, ваш код становится немного медленнее каждый раз, когда количество ведер растет.

Я думаю, что эти обобщения являются крупнейшими вкладчиками в небольшой рост времени, так как количество ведер растет. Самый простой способ проверить эту теорию - вообще не делать никаких обобщений (тест 1) и просто помещать счетчики в массив. Результат может быть показан ниже в коде для FixArrayTest (или вам нравится FixBucketTest, который ближе к тому, как работают группы). Как вы можете видеть, тайминги # buckets = 10... 10000 одинаковы, что верно в соответствии с этой теорией.

Кэш и случайный

Генераторы кеширования и случайных чисел не являются друзьями.

Наш небольшой тест также показывает, что, когда количество ведер растет выше определенного порога, вступает в игру память. На моем компьютере это размер массива примерно 4 МБ (4 * количество ковшей). Поскольку данные случайные, случайные куски ОЗУ будут загружены и выгружены в кеш, что является медленным процессом. Это также большой скачок скорости. Чтобы увидеть это в действии, измените случайные числа на последовательность (называемую "тест 2" ) и - поскольку теперь страницы данных могут быть кэшированы - скорость будет оставаться одинаковой.

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

Тестовый код

static void Main(string[] args)
{
    int size = 10000000;
    int[] ar = new int[size];

    //random number init with numbers [0,size-1]
    var r = new Random();
    for (var i = 0; i < size; i++)
    {
        ar[i] = r.Next(0, size);
        //ar[i] = i; // Test 2 -> uncomment to see the effects of caching more clearly
    }

    Console.WriteLine("Fixed dictionary:");
    for (var numBuckets = 10; numBuckets <= 1000000; numBuckets *= 10)
    {
        var num = (size / numBuckets);
        var timing = 0L;
        for (var i = 0; i < 5; i++)
        {
            timing += FixBucketTest(ar, num);
            //timing += FixArrayTest(ar, num); // test 1
        }
        var avg = ((float)timing) / 5.0f;

        Console.WriteLine("Avg Time: " + avg + " ms for " + numBuckets);
    }

    Console.WriteLine("Fixed array:");
    for (var numBuckets = 10; numBuckets <= 1000000; numBuckets *= 10)
    {
        var num = (size / numBuckets);
        var timing = 0L;
        for (var i = 0; i < 5; i++)
        {
            timing += FixArrayTest(ar, num); // test 1
        }
        var avg = ((float)timing) / 5.0f;

        Console.WriteLine("Avg Time: " + avg + " ms for " + numBuckets);
    }
}

static long FixBucketTest(int[] ar, int num)
{
    // This test shows that timings will not grow for the smaller numbers of buckets if you don't have to re-allocate
    System.Diagnostics.Stopwatch s = new Stopwatch();
    s.Start();
    var grouping = new Dictionary<int, List<int>>(ar.Length / num + 1); // exactly the right size
    foreach (var item in ar)
    {
        int idx = item / num;
        List<int> ll;
        if (!grouping.TryGetValue(idx, out ll))
        {
            grouping.Add(idx, ll = new List<int>());
        }
        //ll.Add(item); //-> this would complete a 'grouper'; however, we don't want the overallocator of List to kick in
    }
    s.Stop();
    return s.ElapsedMilliseconds;
}

// Test with arrays
static long FixArrayTest(int[] ar, int num)
{
    System.Diagnostics.Stopwatch s = new Stopwatch();
    s.Start();

    int[] buf = new int[(ar.Length / num + 1) * 10];
    foreach (var item in ar)
    {
        int code = (item & 0x7FFFFFFF) % buf.Length;
        buf[code]++;
    }

    s.Stop();
    return s.ElapsedMilliseconds;
}

Ответ 5

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

Попробуйте следующее:

int size = 2500000; //10000000 divided by 4
int[] ar = new int[size];
//random number init with numbers [0,size-1]
System.Diagnostics.Stopwatch s = new Stopwatch();
s.Start();

for (int i = 0; i<4; i++)
{
var group = ar.GroupBy(i => i / num); 
//the number of expected buckets is size / num.
var l = group.ToArray();
}

s.Stop();

вычисление 4 раза с более низкими значениями.