История изменений

Имхо, обсуждать структуры данных в отрыве от патернов доступа и патернов собственно данных - довольно бессмысленное занятие.

Всё верно. Мы идем от алгоритма и того паттерна доступа к памяти, который он создает. Дальше, подбираем раскладку данных по памяти (т.е. структуру данных) так, чтобы максимизировать производительность на заданной архитектуре памяти.

Списки право на жизнь не просто имеют, а иногда даже являются оптимальными. Например, в случае LRU-кэша. Там важна быстрая вставка, а линейного чтения нет, так что кэши не при делах. Возражение khrundel тут состоит в том, что речь не идет о списке, как об основном контейнере. Однако, на практике мы именно что комбинируем контейнеры для получения нужных нам гарантий.

a-- вызвался побенчмаркать LRU-кэш со списком на chunked array. Очень интересно, какой дизайн у него в итоге получится, учитывая, что chunked array теряет одно из важных преимуществ списка – стабильность итераторов при обновлении контейнера.

В этом треде Вы выглядите как один из самых трезвомыслящих…

Просто я «ем» дизайны на основе массивов на завтрак, обед и ужин. А потом мне они еще и снятся. К слову, такие дизайны выбираются не столько из-за скорости (она, сырая, не факт, что выше будет). А из-за значительно лучшей компактности. Т.е. в ту же память можно напихать больше информации, что в конечном итоге и повышает быстродействие.

Я тут провел бенчмарк std::set<u64> против absl::btree_set<u64> на чтение при одинаковом размере датасета. Скоро опубликую график.

Имхо, обсуждать структуры данных в отрыве от патернов доступа и патернов собственно данных - довольно бессмысленное занятие.

Всё верно. Мы идем от алгоритма и того паттерна доступа к памяти, который он создает. Дальше, подбираем раскладку данных по памяти (т.е. структуру данных) так, чтобы максимизировать производительность на заданной архитектуре памяти.

Списки право на жизнь не просто имеют, а иногда даже являются оптимальными. Например, в случае LRU-кэша. Там важна быстрая вставка, а линейного чтения нет, так что кэши не при делах. Возражение khrundel тут состоит в том, что речь не идет о списке, как об основном контейнере. Однако, на практике мы именно что комбинируем контейнеры для получения нужных нам гарантий.

a-- вызвался побенчмаркать LRU-кэш со списком на chunked array. Очень интересно, какой дизайн у него в итоге получится, учитывая, что chunked array теряет одно из важных преимуществ списка – стабильность итераторов при обновлении контейнера.

В этом треде Вы выглядите как один из самых трезвомыслящих…

Просто я «ем» дизайны на основе массивов на завтрак, обед и ужин. А потом мне они еще и снятся. К слову, такие дизайны выбираются не столько из-за скорости (она, сырая, не факт, что выше будет). А из-за значительно лучшей компактности. Т.е. в ту же память можно напихать больше информации, что в конечном итоге и повышает быстродействие.

Я тут провел бенчмарк std::set против absl::btree_set на чтение при одинаковом размере датасета. Скоро опубликую график.