Померил SoA-вариант, vals []int64 плюс next []int32. Результат интереснее
Обход миллиона по порядку: указатели 1.77 мс, индексы 2.43 мс, то есть индексы на 38% хуже. Обход того же миллиона вразброс: указатели 158.2 мс, индексы 67.9 мс, индексы в 2.3 раза лучше. На ста тысячах то же направление, слабее.
Получается, индексы помогают там, где локальность уже потеряна, и мешают там, где она есть. На упорядоченном обходе узел из 16 байт читается одним потоком, а SoA требует двух независимых чтений плюс проверку границ. На разбросанном выигрывает меньший рабочий набор связей: 4 МБ next против 16 МБ узлов.
Разрыв с массивом при этом сокращается вдвое, но не закрывается - ×138 вместо ×322 на миллионе. И цена случайного порядка обхода падает с ×89 до ×28 относительно упорядоченного варианта, то есть остаётся главным фактором.
Так что представление на индексах работает, но как средство от плохой локальности, а не как способ её получить. Получить её даёт та самая компактизация, про которую вы написали: 1.77 мс против 158 мс - это ×89, и никакая смена представления столько не даёт.
массив, сдвиг хвоста - 17.4 мкс список с обходом - 28.8 мкс список с готовым указателем - 1.02 нс
×17 000 в пользу списка, и от размера не зависит: 1.04 нс на тысяче, 1.02 нс на ста тысячах. Здесь вы правы полностью, и в статье этой операции действительно не было.
Заодно закрыл аллокацию узла из соседней ветки: вставка в начало через &node{} - 20 нс, 16 B/op, 1 allocs/op. Против 15.9 мкс у сдвига слайса это ×784.
Но средняя строка таблицы - про то, о чём я писал выше: как только за узлом надо идти обходом, список проигрывает массиву даже на удалении, где у него O(1) против O(n). 28.8 против 17.4 мкс.
То есть граница ровно там, где вы её и провели. Указатель в руках - список вне конкуренции. Указатель надо искать - выигрывает массив.
Асимптотика на этой границе не меняется, меняется только то, кто добывает узел
Принимаю. По индексу у обоих O(n), и массив выигрывает на константах. «O(1)» - учебное утверждение, а не мой замер.
Про указатель - согласен, это и есть вывод статьи: третья колонка, 3.4-3.6 нс против ~19 мкс.
Вставку в начало из соседнего комментария тоже померил: 15.9 мкс против 0.5 нс на 100k.
Одна поправка к полному счёту: указатель надо откуда-то взять, обычно из map плюс её память и lookup. И если по списку иногда ходят, возвращается ×322, потому что после серии вставок узлы разъезжаются.
100k элементов: слайсу на вставку в начало нужен memmove всего массива, 15.9 мкс. Списку две записи указателя, 0.5 нс, и от размера это не зависит. Аллокацию узла мерю отдельно, там первая версия бенчмарка сама села в лужу: escape analysis утащил узел на стек, и получилось 0.3 нс при 0 allocs/op, то есть аллокация «быстрее» обычного присваивания. Переписал. Но даже десятки наносекунд тут картину не меняют.
Дальше я собирался возразить, что выигрыш съест обход, список-то из вставок в начало это ровно тот самый разбросанный. Померил: не съест. Обход миллиона 1.90 мс, у плотного 1.77 мс, у разбросанного 158 мс. Ведёт себя как плотный. Дошло почему: последовательные аллокации кладут узлы по возрастающим адресам, а обход идёт по убывающим. Шаг регулярный, этого хватает.
Так что возражения нет, вставка в начало - нормальный случай для списка, без оговорок. Узлы разъедутся только если между вставками аллоцируется что-то ещё, вот тогда обход и поедет в сторону тех самых 158 мс.
Замеры добавил в модуль: BenchmarkInsertFront и BenchmarkTraversePrepended.
Справедливо, этого случая в статье нет. Вставка в начало - как раз то, где у списка обхода нет вообще: голова всегда под рукой, а слайсу нужен memmove всего массива. Тут список должен выигрывать, и заметно.
Добавил замер в модуль, прогоню и вернусь с цифрами. Заодно интересно посмотреть на второй шаг: список, собранный вставками в начало - это ровно тот самый разбросанный список из статьи. Если по нему потом хоть иногда ходят, выигрыш на вставке может съесться на обходе. Вот это и хочу замерить, а не угадать.
Хитрости не потребовалось. У меня кэшируется живая статистика, и там обычный sync.RWMutex с double-checked locking: горячий путь под RLock, на промахе берём Lock и перепроверяем условие внутри. Без этой перепроверки десять горутин, упёршихся в истёкший TTL, сходят в базу десять раз вместо одного.
singleflight тут избыточен: он дедуплицирует по ключу и окупается, когда ключей много. У меня ключ один.
Слабое место: пока держится Lock, читатели ждут вместе с ним. Запрос долгий - встали все. Вот тут singleflight мягче, а stale-while-revalidate ещё мягче.
И от нескольких инстансов мьютекс не спасает вообще: каждый сходит в базу сам. Если за кэшем что-то дорогое, нужен SET NX.
А у вас как?
Информация
В рейтинге
280-й
Откуда
Москва, Москва и Московская обл., Россия
Дата рождения
Зарегистрирован
Активность
Специализация
Бэкенд разработчик, Архитектор программного обеспечения
Померил SoA-вариант, vals []int64 плюс next []int32. Результат интереснее
Обход миллиона по порядку: указатели 1.77 мс, индексы 2.43 мс, то есть индексы на 38% хуже. Обход того же миллиона вразброс: указатели 158.2 мс, индексы 67.9 мс, индексы в 2.3 раза лучше. На ста тысячах то же направление, слабее.
Получается, индексы помогают там, где локальность уже потеряна, и мешают там, где она есть. На упорядоченном обходе узел из 16 байт читается одним потоком, а SoA требует двух независимых чтений плюс проверку границ. На разбросанном выигрывает меньший рабочий набор связей: 4 МБ
nextпротив 16 МБ узлов.Разрыв с массивом при этом сокращается вдвое, но не закрывается - ×138 вместо ×322 на миллионе. И цена случайного порядка обхода падает с ×89 до ×28 относительно упорядоченного варианта, то есть остаётся главным фактором.
Так что представление на индексах работает, но как средство от плохой локальности, а не как способ её получить. Получить её даёт та самая компактизация, про которую вы написали: 1.77 мс против 158 мс - это ×89, и никакая смена представления столько не даёт.
Померил
Удаление из середины, 100 000 элементов:
массив, сдвиг хвоста - 17.4 мкс
список с обходом - 28.8 мкс
список с готовым указателем - 1.02 нс
×17 000 в пользу списка, и от размера не зависит: 1.04 нс на тысяче, 1.02 нс на ста тысячах. Здесь вы правы полностью, и в статье этой операции действительно не было.
Заодно закрыл аллокацию узла из соседней ветки: вставка в начало через &node{} - 20 нс, 16 B/op, 1 allocs/op. Против 15.9 мкс у сдвига слайса это ×784.
Но средняя строка таблицы - про то, о чём я писал выше: как только за узлом надо идти обходом, список проигрывает массиву даже на удалении, где у него O(1) против O(n). 28.8 против 17.4 мкс.
То есть граница ровно там, где вы её и провели. Указатель в руках - список вне конкуренции. Указатель надо искать - выигрывает массив.
Асимптотика на этой границе не меняется, меняется только то, кто добывает узел
Принимаю. По индексу у обоих O(n), и массив выигрывает на константах. «O(1)» - учебное утверждение, а не мой замер.
Про указатель - согласен, это и есть вывод статьи: третья колонка, 3.4-3.6 нс против ~19 мкс.
Вставку в начало из соседнего комментария тоже померил: 15.9 мкс против 0.5 нс на 100k.
Одна поправка к полному счёту: указатель надо откуда-то взять, обычно из map плюс её память и lookup. И если по списку иногда ходят, возвращается ×322, потому что после серии вставок узлы разъезжаются.
Пошёл мерить, и вы правы, случай зря пропущен.
100k элементов: слайсу на вставку в начало нужен memmove всего массива, 15.9 мкс. Списку две записи указателя, 0.5 нс, и от размера это не зависит. Аллокацию узла мерю отдельно, там первая версия бенчмарка сама села в лужу: escape analysis утащил узел на стек, и получилось 0.3 нс при 0 allocs/op, то есть аллокация «быстрее» обычного присваивания. Переписал. Но даже десятки наносекунд тут картину не меняют.
Дальше я собирался возразить, что выигрыш съест обход, список-то из вставок в начало это ровно тот самый разбросанный. Померил: не съест. Обход миллиона 1.90 мс, у плотного 1.77 мс, у разбросанного 158 мс. Ведёт себя как плотный. Дошло почему: последовательные аллокации кладут узлы по возрастающим адресам, а обход идёт по убывающим. Шаг регулярный, этого хватает.
Так что возражения нет, вставка в начало - нормальный случай для списка, без оговорок. Узлы разъедутся только если между вставками аллоцируется что-то ещё, вот тогда обход и поедет в сторону тех самых 158 мс.
Замеры добавил в модуль:
BenchmarkInsertFrontиBenchmarkTraversePrepended.Справедливо, этого случая в статье нет. Вставка в начало - как раз то, где у списка обхода нет вообще: голова всегда под рукой, а слайсу нужен memmove всего массива. Тут список должен выигрывать, и заметно.
Добавил замер в модуль, прогоню и вернусь с цифрами. Заодно интересно посмотреть на второй шаг: список, собранный вставками в начало - это ровно тот самый разбросанный список из статьи. Если по нему потом хоть иногда ходят, выигрыш на вставке может съесться на обходе. Вот это и хочу замерить, а не угадать.
Хитрости не потребовалось. У меня кэшируется живая статистика, и там обычный
sync.RWMutexс double-checked locking: горячий путь подRLock, на промахе берёмLockи перепроверяем условие внутри. Без этой перепроверки десять горутин, упёршихся в истёкший TTL, сходят в базу десять раз вместо одного.singleflightтут избыточен: он дедуплицирует по ключу и окупается, когда ключей много. У меня ключ один.Слабое место: пока держится
Lock, читатели ждут вместе с ним. Запрос долгий - встали все. Вот тут singleflight мягче, а stale-while-revalidate ещё мягче.И от нескольких инстансов мьютекс не спасает вообще: каждый сходит в базу сам. Если за кэшем что-то дорогое, нужен
SET NX.А у вас как?