Comments 66
… в начало-то?
http://stackoverflow.com/questions/4544804/in-what-cases-should-i-use-memcpy-over-standard-operators-in-c
В примере не for, а вообще ручное копированое без проверок, но вкрадце — другие ассемблерные команды, которых получается меньше, и они работают быстрее. В C# так сильно не углублялся и даже не знаю, есть ли подобные оптимизации в этом языке, но почему бы и нет?
Источник: https://msdn.microsoft.com/en-us/library/k4yx47a1(v=vs.110).aspx
Вот кстати парочка сслок про эту опитимзацию:
1. https://stuff.mit.edu/afs/sipb/project/hurddev/tb/libc/sysdeps/mach/pagecopy.h — код макроса, который собственно копирует страницы и вызывается из memcpy
2. https://sourceware.org/ml/libc-alpha/2014-01/msg00274.html — а это, похоже неудачная, попытка удалить эту оптимизацию из glibc (и хитрая ОС, похоже, это Hurd).
На самом деле, если тип имеет свойство (trait) is_trivially_move_constructible, то вектор будет использовать memcpy.
Можно сделать комбинированный контейнер: в пределах блока, скажем, страницы, данные хранятся как массив, сами блоки — произвольно с двунаправленными ссылками. Тогда и добавление в начало дешевое (выделили страницу, записали элемент в самый конец ее, связали ее с предыдущей первой страницей, потом при добавлении в начало идем по странице назад, как в стеке), и изменение размера дешевое, и проход по контейнеру не так плох — в пределах страницы данные будут в кеше, мисс один, когда переходим на следующую.
Ну по сути ваш вариант — это LinkedList, затюненый под жизненные реалии
Именно, ведь об этом и идет речь в статье.
При N много большем чем размер страницы big-O у них (классический LinkedList vs. ваш вариант) одинаковый.
Да, но если говорить о последовательном переборе, то… «жизненные реалии». Плюс дешевая вставка.
Фундаментальная — не запрещает. Но в .net реализовано не так.
Только, во первых по памяти вы проиграете
Тут уж как в золотом законе механики.
а во вторых, константы в ассимптотическом анализе увеличатся (из-за логики по определению какой блок, в какую сторону сдвигаем и т.п.)
Верно, но при последовательном просмотре у нас все так же элементы попадают в кэш — раз, меньше выгрузки-загрузки страниц памяти — два.
Ну и да, с уменьшением размера блока структура все больше походит на linked list
Размер блока можно задать, это не вопрос.
Подождите, а какая в "варианте со связанными блоками" стоимость доступа к произвольному элементу? Разве O(1)?
… тогда это не динамический массив, а хитрый вариант связанного списка. Это само по себе не плохо, но просто не та структура, с которой разговор начался.
И да, я действительно могу себе представить задачи, где эта структура полезна.
Потому что блок вам надо еще найти (видимо перебирая блоки подряд). То есть у вас будет что-то вроде O(n/размер блока)+O(размер блока) что, внезапно, эквивалентно O(n).
Вставка в динамический массив O(1)
В лучшем случае
O(f(n)) определяет верхнуюю границу сложности алгоритма (т.е. наихудший случай для алгорима), так что не имеет значение в начало или конец массива производится вставка, верхняя граница сложности будет O(n).
Для лучшего случая (т.е. нижней границы сложности алгоритма) есть свое обозначение через Ω, про которое все всегда забывают.
Точнее, дополнения методами расширения на IEnumerable/другие интерфейсы для LINQ методов, по скорости сравнимых с RawArrayFor, дерева на динамическом массиве, и т. д.?
Если объекты достаточно маленькие (от 16 до 32 байтов или меньше в разных ситуациях), то стоит рассмотреть вариант хранения их по значению (struct в .NET), а не в объекте.
Откуда взяты эти цифры, чем плоха структура меньше 16 байт?
Судя по всему, автор не понимает Big-O. Вне зависимости от того, на какое константное число раз вставок будет больше, чем проходов, O(F(x)) не изменится.
т.е. мы имеем для массива вставку и проход = O(n) + 5O(n) = O(n)
для связного списка O(n) + 5O(1) = O(n)
Делаем графики, они действительно растут примерно одинаково, но это почему-то:
> Неожиданные для многих результаты.
> Чтобы производительность стала хуже, отношение вставок к проходам должно измениться, а не только размер коллекции.
Если делать ТОЛЬКО вставки, то связный список будет СУЩЕСТВЕННО лучше, только об этом говорит Big-O. Он не говорит ни о конкретной реализации, ни о том, кто из двух O(n) быстрее. Ему, если хотите, всё равно. Для Big-O разница в 2 раза — это не «неплохой отрыв», это пшик.
Для реальных применений, конечно, разница даже в миллисекунду может иметь значение. Но тут единственное правило — измеряйте. Big-O даёт отличный старт для поиска оптимального решения и оно не «подводит», как написано в заголовке (или, как у оригинала, «обманывает»).
Если быть точнее, Big-O говорит о том, как изменяется производительность алгоритма при изменении n. Какой из двух разных алгоритмов будет лучше он не говорит.
А вот какой из двух разных алгоритмов одного класса (!) будет лучше — да, он не говорит. Там уже есть смысл упражняться в оптимизациях и сравнениях (чем и занимается автор статьи), но это уже вопросы куда более мелкие.
Ничто не мешает существовать алгоритму с O(n), на каждое n которого на практике тратиться секунда, имея в то же время аналог с O(n^2), где на каждое n тратится миллисекунда.
> что их нет смысла даже сравнивать
Для начала стоит еще взглянуть на сложность по памяти, а то так недалеко и сортировку подсчетом везде брать.
Да, не мешает. Пусть n равен миллиону. Первый выполнил за 11 дней, второй — за более чем 31 год. Если у нас задача только для ограниченных n, мы вернулись к эмпирическому правилу измерений. Собственно, и ваши «секунда» и «миллисекунда» — это тоже результат измерений, а не приближения уровня Big-O. Не стоит путать эти вещи, как сделал автор.
> Для начала стоит еще взглянуть на сложность по памяти, а то так недалеко и сортировку подсчетом везде брать.
Сомневаюсь, что сортировку со временем O(n^2) стоит использовать везде. Сложность по памяти, конечно, тоже стоит учитывать.
Например:
есть алгоритм А где одна операция стоит 1 (секунду, или мили секунду, или наносекунду) с O(n^2)
и есть алгоритм B где одна операция стоит 1000 c O(n), так вот есть такое n где алгоритм А «обойдет» по скорости В
в данном случае при n > 1000.
Какую бы вы стоимость одной операции вы не взяли всегда найдется такое n, где O(n) «быстрее» O(n^2). Это из определения Big-O, потому что стоимость операции это константа, которая зависит от архитектуры, ос и т.д.
А автор статьи сравнил теплое с мягким, Big-O это не о железе и реализациях, это абстракция.
Конечно не всегда уместно использовать «быстрые» алгоритмы, но помогает вначале сделать выбор и оно не «обманывает» если знать определение.
Ради смеха можно реализовать список при помощи массивов и посмотреть на «скорость».
[Benchmark]
public int LinkedListFor()
{
var local = linkedList;
int sum = 0;
var node = local.First;
for (int i = 0; i < local.Count; i++)
{
checked
{
sum += node.Value;
node = node.Next;
}
}
return sum;
}
А работает почему-то гораздо быстрее, чем foreach.
Ответ кроется в реализации метода List<T>.Enumerator.MoveNext()
, который используется конструкцией foreach
:
1) Он проверяет, не изменился ли List<T>
.
2) Он проверяет выход за границы массива.
Когда CLR видит стандартную конструкцию вида for (int i = 0; i < array.Lengh; i++)
, она (среда выполнения) убирает проверку на выход за границы массива. Из-за этого RawArrayFor
работает так быстро.
Когда CLR видит конструкцию вида foreach (var x in array)
, где array
— это обычный массив, она заменяет foreach
на обычный for
, а дальше применяется упомянутая выше оптимизция. Из-за этого RawArrayForEach
работает так же быстро.
Когда CLR встречает конструкцию for(...)
или foreach(...)
, работающую с List<T>
или любой другой динамической коллекцией, все становится плохо:
а) При использовании for(...)
CLR не может убрать проверки на выход за границу коллекции, т. к. размер списка может быть изменен другим потоком во время работы цикла.
2) При использовании foreach(...)
CLR не может заменить его на for(...)
, т. к. при обходе коллекции каждый раз проверяется отсутствие изменений и инвалидация итератора в противном случае.
Разве CLR не может увидеть, что других потоков нет и никто на динамическую коллекцию не претендует? И выкинуть связанные с этим проверки.
Для проверки утверждения стоит собрать однопоточное простое приложение и заглянуть в диспетчер системы.
Если поток создан не нами, а самой CLR, она в курсе, кто и зачем в нем требует объекты, так что это не должно ей мешать. Она же знает, что в своем потоке не трогает объект, знает, что объект трогается только в одном пользовательской потоке, что мешает оптимизировать?
И указатель на метод после компиляции (метода), и указатель на коллекцию будут находиться в соответствующих таблицах, до них можно докопаться reflection-ом и другими методами.
Просматривать по месту компиляции: «уплывет этот указатель куда-нибудь в другой поток или нет» — тяжело или невозможно, но в любом случае очень дорого.
И в конце-концов, ничто не мешает под debugger-ом/reflection-ом добавить/убрать элемент в эту динамическую коллекцию. Если циклы for/foreach не будут проверять размер обходимой коллекции — должны получить нативную ошибку (этот факт проверю в неуправляемом коде, не натыкался раньше).
Нет, не может.
А почему?
Потому что на момент JIT-компиляции (а оптимизация происходит именно тогда) jitter понятия не имеет, что происходит с объектом за пределами метода. Возможно, если объект локален для метода и никуда не передается (в бенчмарках в посте — не так) — можно было бы сделать такую оптимизацию, но для этого надо точно знать, что происходит внутри вызываемых методов коллекций (откуда CLR знать, что то, что лежит за этим IList
не является генератором?), что тоже требует времени.
Если по делу, мне вот какая штука всегда была интересна… В Objective-C есть такая штука, как class cluster. Если коротко, идея их такая: под интерфейсом-фасадом публичного класса (например, NSNumber — класс, который хранит числа: как целые, так и с плавающей точкой) могут прятаться в качестве реализации универсального приватного интерфейса объекты разных приватных классов, оптимизированные под конкретный тип (например, для хранения интов, чаров, и т.д.). К чем я это…
Если взять такую идею и перенести её на коллекции вообще, то, как мне кажется, возможно выделить основные поведения для групп коллекций — например, достаточно двух: «массив» и «словарь» — и сделать набор реализаций, оптимизированных под конкретный стиль работы с коллекцией. Больше вставок — в реализации список. Больше проходов по элементам — значит массив.
А дальше можно сделать либо автоматический выбор реализации в зависимости от стиля использования коллекции (теоретически — вплоть до сбора статистики использования коллекции во времени), либо дать пользователю возможность выбирать нужную реализацию вручную.
В плюсах такую фичу можно легко реализовать вообще без каких-либо потерь на динамическом полиморфизме — с помощью шаблонов.
Интересно было бы сравнить быстродействие std::unordered_map и мапу, сделанную на базе std::vector как массив пар. Скорее всего, std::unordered_map будет обходить по скорости наивную реализацию с помощью std::vector на достаточно небольшом количестве элементов.
П.С.: Кстати, по поводу операций вставки и удаления в «плотных» структурах данных. Насколько я знаю, для оптимизаций ещё используется техника nondestructive удаления элементов, когда вместо удаления и сдвига элементов делается swap с «незанятым» элементом в выделенном блоке данных. Такой подход работает как раз в ситуациях, когда нас не интересует порядок элементов. В данном случае подойдёт.
Ссылки:
1. Ссылка на cppreference.
2. Весьма хорошая статья в блоге bannalia.
Ну это же очевидно. O-большое начинает работать только для больших значений n. Для маленьких значений гораздо чаще самая простая структура работает быстрее, чем сложная. Даже если у второй ассимптотика лучше. Потому что map требует, допустим, 100500*log(n) операций, а массив — 42*n. Map обгонит массив только для весьма больших n. Нужно всегда помнить о константе, спрятанной за O().
динамический массив будет эффективнее связного списка пока вставок на порядок больше, чем проходов
Сперва подумал, что я чего-то не понимаю. Но потом заглянул в оригинал. У Вас ошибка в переводе: в оригинале стоит предлог «until», а не «while». То есть правильно: «динамический массив будет эффективнее связного списка до тех пор, пока вставок не станет на порядок больше, чем проходов».
https://www.youtube.com/watch?v=LrVi9LHP8Bk
Прошу понять меня правильно, пишу из желания дополнить и улучшить, и потому что лежит в хабе математика, а тема математики до конца не раскрыта.
О-нотация никогда не говорила о фактическом времени исполнения алгоритма на конкретно определенном размере данных! Она говорит о потенциале скорости алгоритма при росте N (в т.ч. не ограниченном). В статье об этом написано, хотя несколько косвенно. Так для малых N конечно всегда простые алгоритмы будут быстрее, потому что накладные расходы одной простой операции с данными будут меньше, но при росте N значимость времени одной итерации обработки уменьшается (потому что это константа) и становиться важно только как быстро растет их количество.
Аргумент про пакетную оптимизацию памяти на это не влияет, т.к. размер кеша ограничен и это приводит лишь к линейной оптимизации (примите за N «следующие 64 байта данных уже готовые к обработке» и поймете, что на бесконечности ничего не изменилось)
Таким образом приведенные в шапке кривые скорости — теоретические
на практике каждая реализация алгоритма будет иметь некий разный линейный сдвиг (а если алгоритм с «прогревом» то и статичный), и у тяжелых реализаций он будет больше, и получиться что каждый из алгоритмов (исключая совсем лузерские) будет лидировать по фактической скорости на некотором размере данных, но крайний правый диапазон всегда будет за алгоритмом с наилучшим О()
А теперь о чем написано не было «Если углубиться в математику»: O() подсчитанное для «вставки» работает только для вставки, когда отношение проходов к вставкам 0:1. Миксовать два разных O() просто пропорционально их складывая нельзя! Потому что фактическая скорость равна O(вставки)*t_вставки и O(прохода)*t_прохода — вот тогда их можно будет пропорционально складывать. И еще одно свойство, объясняющее почему так получилось — потому что миксовались алгоритмы с Линейным O(n) — и линейное же пропорциональное отношение t_вставки/t_проходы соответственно смогло это скомпенсировать до равенства. В общем случае для операций с нелинейной сложностью O() это будет не так. Так что описанный случай «подведения O» — не более чем частный!
(На самом деле мне кажется что автор оригинала намеренно его подстроил, потому что зная как использовать O нотацию в оценках, это довольно тривиальное следствие)
Когда «О» большое подводит