Почему O(1) проигрывает O(n): структуры данных в Go на реальном железе

[unreal_undead2]

O(1) — это только момент перецепления указателей. До нужного места ещё надо дойти:

А если побенчмаркать вставку в начало (может это самый частый случай в конкретной задаче) ? ;)

[dixmod]

Справедливо, этого случая в статье нет. Вставка в начало - как раз то, где у списка обхода нет вообще: голова всегда под рукой, а слайсу нужен memmove всего массива. Тут список должен выигрывать, и заметно.

Добавил замер в модуль, прогоню и вернусь с цифрами. Заодно интересно посмотреть на второй шаг: список, собранный вставками в начало - это ровно тот самый разбросанный список из статьи. Если по нему потом хоть иногда ходят, выигрыш на вставке может съесться на обходе. Вот это и хочу замерить, а не угадать.

[unreal_undead2]

Да и заголовок обманчив - вставка по индексу (с получением элемента обходом с начала) в списке это таки O(n), в тексте это всё таки сказано. Если надо вставлять в середину, но элемент списка индентифицируется указателем на него - тогда, как и со вставкой в начало, будет O(1) и опять же ожидается выигрыш от списка.

[dixmod]

Принимаю. По индексу у обоих O(n), и массив выигрывает на константах. «O(1)» - учебное утверждение, а не мой замер.

Про указатель - согласен, это и есть вывод статьи: третья колонка, 3.4-3.6 нс против ~19 мкс.

Вставку в начало из соседнего комментария тоже померил: 15.9 мкс против 0.5 нс на 100k.

Одна поправка к полному счёту: указатель надо откуда-то взять, обычно из map плюс её память и lookup. И если по списку иногда ходят, возвращается ×322, потому что после серии вставок узлы разъезжаются.

[dixmod]

Пошёл мерить, и вы правы, случай зря пропущен.

100k элементов: слайсу на вставку в начало нужен memmove всего массива, 15.9 мкс. Списку две записи указателя, 0.5 нс, и от размера это не зависит. Аллокацию узла мерю отдельно, там первая версия бенчмарка сама села в лужу: escape analysis утащил узел на стек, и получилось 0.3 нс при 0 allocs/op, то есть аллокация «быстрее» обычного присваивания. Переписал. Но даже десятки наносекунд тут картину не меняют.

Дальше я собирался возразить, что выигрыш съест обход, список-то из вставок в начало это ровно тот самый разбросанный. Померил: не съест. Обход миллиона 1.90 мс, у плотного 1.77 мс, у разбросанного 158 мс. Ведёт себя как плотный. Дошло почему: последовательные аллокации кладут узлы по возрастающим адресам, а обход идёт по убывающим. Шаг регулярный, этого хватает.

Так что возражения нет, вставка в начало - нормальный случай для списка, без оговорок. Узлы разъедутся только если между вставками аллоцируется что-то ещё, вот тогда обход и поедет в сторону тех самых 158 мс.

Замеры добавил в модуль: BenchmarkInsertFront и BenchmarkTraversePrepended.