[perf] LinkedList vs ArrayList: сколько стоит копирование куска памяти?
Благодаря посту про ритуальные вопросы на собеседованиях, узнал кое-что новое.
Благодаря современным достижениям в области жывотноводства ворочание объемами до 4кб можно считать бесплатными, т.е. O(1). И это порядочно меняет реальную стоимость операций.
Новость тут не в том, что на малых объемах код так себя ведёт. Новость тут в том, что это аж 4кб и это дофига!
Предупреждение: копирование таки реально O(N), но только на достаточно больших N. Мы просто уточняем понятие “достаточно большой” в нынешнее время.
Так например, давайте забенчим, сколько занимает вставка элемента в начало LinkedList<byte> и List<byte>. Согласно referencesource, вставка в начало List происходит копированием остальной памяти: (см. “List.Insert”). В теории оно должно быть O(N).
Код бенча:
Прим. к бенчу: мы передаем IEnumerable, а не коллекцию. Поэтому capacity у List расходится с реальным количеством элементов в списке. Т.е. в среднем как минимум одна вставка происходит без необходимости расширять List.
Почему я говорю про копирование, а бенчу LinkedList+List? Мне лень два раза похожие бенчи делать. Не берите дурного примера с меня.
Построим график скорости выполнения операции вставки в начало:
Левая ось — время, в наносекундах (меньше — лучше). Нижняя ось — количество элементов в списке. Всплески на графике — следствие хренового подхода к бенчу (в основном).
Пока что мы видим, что для Array List на области 0кб-8кб все еще есть линейноподобный тред. Но вот на области 0кб-2кб его практически нет. Давайте переделаем бенч и нарисуем более детальный график в этой области:
Что же мы видим? Говорить о наличии O(N) трендлайна становится куда труднее. Все больше похоже на O(1).
Всплески уже нельзя списать на “я пользовался хромом во время бенча”. Дело в том, что всплески у ArrayList приходятся на степени двойки (16, 32, 64, 128, 256, 512, 1024). Эти всплески объясняются тем, что в этих точках количество элементов совпадает с capacity и необходимо дополнительное расширение. Всплеска на 2048 нет, потому что такой точки нет на графике. Извините, лень перерисовывать.
Итак при размере в 4096 байт мы можем считать, что копирование выполняется за O(1). Либо более строже — при размере в 2048 байт.
Если считать, что типичный элемент массива занимает 4 байта (размер int или размер указателя), то это дает нам 1024 или 512 элементов.
Потом LinkedList конечно же отыгрывается. Но это уже вне топика.
