Rust и двусвязный список

Все несколько сложнее: есть несколько дисциплин (механизмов) обслуживания таймеров

timer-wheel - это какой-то частный случай таймеров, вообще не интересный для рассмотрения. я говорил об ОБЩЕЙ имплементации таймеров на списке.

вместо списка, для более высокой скорости вставки (ибо сортировано по времени срабатывания) можно использовать и бинарное дерево(видимо это и называют timer-heap), но его надо балансировать и тепе. но это однозначно не массив. при тысячах таймеров нужно использовать дерево, но это какие-то достаточно уникальные случаи.

timer-wheel - это какой-то частный случай таймеров

Как раз он и позволяет безболезненно обслуживать большое количество таймеров. Большое – это когда больше нескольких сот тысяч таймеров.

Ну я согласен, что можно так возразить, про отсутствие динамической памяти.

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

Возвращаясь к теме, то, что на Расте не получается сделать безопасный список, оказалось правдой, можно поставить звёздочку.

Как раз он и позволяет безболезненно обслуживать большое количество таймеров. Большое – это когда больше нескольких сот тысяч таймеров.

это частный случай.

программный таймер это обьект который можно создать когда угодно, удалить когда-угодно, запустить на любой интервал когда угодно, деактивировать, не удаляя когда угодно. для программных таймеров аллокирование несущественно. существенна рандомность их активации/деактивации/срабатывания.

а timer-wheel - это не программные таймеры по самому определению. это просто списки хуков или обьектов в кольцевом буфере, где по фиксированному тику выбирается первый список, пускается, а потом засовывается в хвост буфера. чисто какой-то time-sharing ресурсов или еще что.

это частный случай.

Когда вы в программе имеете, скажем, 40K одновременных подключений, и с каждым подключением у вас связано, минимум, 3-4 таймера, то этот частный случай становится именно тем, что вам нужен.

а timer-wheel - это не программные таймеры по самому определению

Аминь.

Об этом и не знает наш уважаемый собеседник, которого, впрочем, я вижу, тут уже почти единогласно загнобили.

По большей части он говорит правильные вещи. Но, во-первых, у него явно какой-то пунктик по поводу применимости списков. Списки, конечно, редко применяемая на практике структура, но чтобы вот такой хейт, это странно.

Во-вторых, мне думается, что упускаются какие-то важные нюансы в обсуждении деталей. Например, говорится о том, что когда мы итерируемся по списку, то вымываются значения из кэша. Но при этом не говорится, что когда мы делаем вставку в середину (или начало) вектора, то из-за элементарного memmove мы получаем отнюдь не меньшее вымывание кэша. И, более того, если в векторе лежат элементы с кастомными операторами перемещения (не говоря уже про операторы копирования), то это будут еще большие накладные расходы.

В общем, здесь человек как-то нездорово себя ведет, хотя он явно в теме разбирается.

Возвращаясь к теме, то, что на Расте не получается сделать безопасный список, оказалось правдой, можно поставить звёздочку.

Однако, в главном-то он прав: ну нет простого способа в Rust сделать список, ну и что? Кому нужно, тот возьмет непростой способ и сделает.

Я не понимаю, какие далеко идущие выводы можно сделать после того, как вы «поставили звездочку». Все равно в среднем по больнице Rust будет безопаснее C++, не говоря уже про чистый Си.

Аминь.

программный таймер это абстракция для действий, выполнямых в некий момент момент времени с базовым интерфейсом :

class Timer {
  void start()
  void stop()
  void set_interval(int fmillseconds)
  void set_periodic(bool);
  virtual on_time()=0; ///хук при срабатывании
}

а timer wheel вообще делается на одном таймере, что в своем хуке крутит списки(или массивы) еще каких-то хуков. то есть это один единственный таймер со сложной семантикой.

Ну я говорю аминь. Если вы в это веруете, то кто я такой, чтобы подвергать сомнению вашу веру?

Так существующие языки через это и вымирают

Пусть так, но языки которые вообще не развиваются умирают ещё быстрее, это ложная альтернатива.

Там даже больше, благодаря inline namespace, у этих типов разный манглинг и они не мешают друг другу и там можно собирать даже с двумя разными стандартными библиотеками libc++ и libstdc++ и это будет работать…

И как это будет работать, если мы получаем строку из одной библиотеки и хотим передать в другую, а это разные строки?

И как это будет работать, если мы получаем строку из одной библиотеки и хотим передать в другую, а это разные строки?

Используя полные имена. Они разные у Clang и GCC, и у старых строк и новых.

Ну потом можно получить указатель на const char* строки GCC и создать строку Clang и передать в функцию которая ожидает строку Clang.

https://gcc.godbolt.org/z/KhahPj5ob

https://www.youtube.com/watch?v=rUESOjhvLw0

Просто языкам с грузом совместимости при прочих равных развиваться тяжелее, больше грехов накапливается и в итоге кто-то может решить, что проще всё сделать заново. Не вижу тут ложности альтернативы.

Я не понимаю, какие далеко идущие выводы можно сделать после того, как вы «поставили звездочку».

А это уже отдельная тема. Пока и сам не знаю. Во всяком случае, желания утащить в свой язык именно это решение из Раста желания пока не возникло.

Используя полные имена. Они разные у Clang и GCC, и у старых строк и новых.

Ок, познавательно. Хотя, конечно, не слишком изящно.

Но изначально речь шла о том, чтобы собрать приложения используя разные объектные файлы. Так вот, если у нас есть доступ к исходникам, то не проще ли поправить и не страдать ерундой? А если надо именно объектные файлы использовать, то это ведь не всегда получится. Прописан то будет, скорее всего, std::string.

Просто языкам с грузом совместимости при прочих равных развиваться тяжелее

А не бывает языков без «груза совместимости». Язык или сохраняет обратную совместимость, развивается и обрастает «особенностями» или остаётся экспериментальным (и по сути мёртвым).

Не вижу тут ложности альтернативы.

Эта ветка обсуждения началась с вопроса как ещё при проектировании языка заложить возможность развиваться не накапливая «грехи». Поэтому предлагать тут вариант «взять и сделать заново» совсем не в тему.

Прописан то будет, скорее всего, std::string.

это всё равно сокращение в новых версиях gcc и всегда для clang.

В этом и смысл inline namespace.

Нужно будет поменять в заголовочных файлах на полные имена и линковаться со старым объектным файлом к которому нет исходников.

Но в целом я согласен, что это не изящно.

Вот тут кто-то тоже подобным интересовался: https://stackoverflow.com/a/12546314/4544798

Нужно будет поменять в заголовочных файлах на полные имена

Вот это больше всего меня смущает. Понятное дело, что лучше так, чем никак, но всё равно.

А как же CоW строки, которые были раньше в GCC?

А что, когда-то в стандарте обызывали делать CoW строки? Нет там такого, это уже оптимизации компилятороделов. Хоть буду я собирать с -std=c++98, хоть с -std=c++23, там будет одна и та же версия libstdc++.

нет, речь идёт лишь о форме работы с наследием. Конвертировать всё в новый стандарт - это лучше, чем поддерживать Эн старых. Попытка поддержания старых увеличивает накладные расходы и в итоге снижает конкурентоспособность. В то время как дружественное отношение к унаследованному прикладному коду её увеличивает.

Но в общем-то я не пытаюсь тебе это продать. Я только пытался объяснить, в меру сил, свою точку зрения на вопрос. Для меня как разработчика поддержание эн старых стандартов - это хуже, чем конвертер, позволяющий забыть про них. Для меня как для пользователя - лучше.

Если вопрос - как заложить, то в го над вопросом подумали, сделав язык таким, что его можно конвертировать. В Си из-за препроцессора это получается гораздо сложнее.

А так-то вообще лучше сделать эн экспериментальных языков, и когда они будут достаточно хороши, выложить сразу финальный релиз своего языка, и больше его не развивать.

Эта ветка обсуждения началась с вопроса как ещё при проектировании языка заложить возможность развиваться не накапливая «грехи».

Рискуя оказаться К.О., скажу: выкатив первую версию языка, сказать: а вот эта вот фича может вам показаться странной, но она специально сделана для упрощения миграции на следующие версии (и обратно на предыдущие, если зарулили слишком вперед на экспериментальную версию).

И это видимо не конвертер, хотя конвертер тоже нужен. Особенно конвертер с экспериментальной ветки обратно... но это явно не про раст, где советуют «в ночном билде это уже исправили».

Кстати: какие по-твоему наиболее крупные изменения языка удалось сгладить с помощью конвертера редакций? (Депрекейт одной функции в пользу другой это очень маленькие изменение, за исключением случая когда функции очень привязаны к языковой модели).

Конвертировать всё в новый стандарт - это лучше, чем поддерживать Эн старых. Попытка поддержания старых увеличивает накладные расходы и в итоге снижает конкурентоспособность. В то время как дружественное отношение к унаследованному прикладному коду её увеличивает.

А чересчур дружественное отношение может пользователям вредить. Смотри последующую дискуссию про f.

Эта ветка обсуждения началась с вопроса как ещё при проектировании языка заложить возможность развиваться не накапливая «грехи».

Один из вариантов ответа — правильно вводить новые фичи. Как антипример пойдет конечно же с++.

ЕМНИП сначала была только перегрузка функций: f(int), f(float), f(double). Потом завезли шаблоны, и появилась возможность template<class T> f(T arg). И вместо того, чтобы эти две возможности сделать исключающими друг друга по какому-то разумному принципу, их решили сделать совместно используемыми, и для этого навертели такие правила, которые вряд ли кто-то помнит полностью. (И еще ЕМНИП была статья Александреску, как эти правила сломать, стремясь к чему-то хорошему).

Один из вариантов ответа — правильно вводить новые фичи.

Для правильного введения новых фич нужна прозорливость.

Для правильного введения новых фич нужна прозорливость.

Ну или хотя бы подумать заранее, куда и в какую сторону язык в принципе может развиваться в будущем (хотя и не обязательно будет развиваться).

Прозорливость как раз нужна для того, чтобы отделить те направления, в которых будет развиваться, от тех, в которые не будет.

Вы разыскали пропозал, судьба которого неизвестна. Может быть в итоге будет так, как написано в пропозале. А может и нет.

Тут, конечно, есть разница в наших подходах из-за разницы в целях. Меня больше интересует найти что-то ценное, чтобы это взять себе и потом убежать как можно скорее, пока не отобрали.

И вместо того, чтобы эти две возможности сделать исключающими друг друга по какому-то разумному принципу

Интересно как это возможно?

По типу D, где вызов шаблона обязательно нужно указывать посредством !?

Мне тоже интересно как это сделать правильно — но и опять, постановка правильного вопроса это более половины дела.

Я бы поступил тут по-жестче, так как первая фича является почти полной подфичей второй (хотя это скорее сейчас, раньше это было не так).

Например бы запретил шаблонную f при наличии перегруженных f (или даже просто f) — в смысле, вываливался бы по ошибке при наличии обоих f в области видимости (хотя тут тоже есть более мягкие варианты). А чтобы чужие хедера в старом стиле можно было бы подключать не меняя, ввел бы какой-то forget f (предполагая, что пользователь сам перефасует перегруженную abandoned_library::f в шаблонную f)

Прозорливость как раз нужна для того, чтобы отделить те направления, в которых будет развиваться, от тех, в которые не будет.

Ну или хотя бы для того, чтобы понять, какая фича окажется более универсальной и/или выиграет.

Понятное дело, что лучше так, чем никак, но всё равно.

Ну да, разработчики компилятора и стандартной библиотеки возможно лучше всех умеют в stable ABI, некоторые библиотеки тоже стараются поддерживать ABI в рамках версии, типа Qt и Gtk.

Но сторонние библиотеки не всегда так стараются, и вот вчера из Discord сообщения по теме, как люди вынуждены развивать проект на старых компиляторах: https://imgur.com/a/A2GZPyZ

Нет там такого, это уже оптимизации компилятороделов.

Которая тем не менее присутствовала в одном из самых популярных компиляторов.

А что, когда-то в стандарте обызывали делать CoW строки?

В стандарте как раз в определённый момент это запретили (опосредованно).

Рискуя оказаться К.О., скажу: выкатив первую версию языка, сказать: а вот эта вот фича может вам показаться странной, но она специально сделана для упрощения миграции на следующие версии (и обратно на предыдущие, если зарулили слишком вперед на экспериментальную версию).

Я всё ещё хотел бы увидеть, что это может быть за фича такая.

Особенно конвертер с экспериментальной ветки обратно…

Если фича не косметическая (что не особо и интересно), а позволяет делать нечто фундаментально новое, то как это будет выглядеть? Ну представим, что в языке не было инлайн ассемблера (или дженериков или макросов), а в экспериментальной ветке он появился. Как мигрировать назад?

но это явно не про раст, где советуют «в ночном билде это уже исправили».

В смысле исправили? Обычно в найтли доступны или в принципе новые фичи или расширение существующих. Каких-то громких случаев, приходилось с нетерпением ждать фикса бага как-то и не припоминаю.

Кстати: какие по-твоему наиболее крупные изменения языка удалось сгладить с помощью конвертера редакций?

Я бы сказал, что крупных ломающих изменений пока что и не было. Но вообще когда указывать dyn для трейтов стало обязательным, то руками это было бы править достаточно напряжно так как изменений банально много, а тупая автозамена тут бы не справилась.

Но сторонние библиотеки не всегда так стараются, и вот вчера из Discord сообщения по теме, как люди вынуждены развивать проект на старых компиляторах: https://imgur.com/a/A2GZPyZ

Весело. (:

Если узел ни с чем не связан и нахер не нужен - да, пропал. Бывает и такое.

Кто сказал что не нужен? А как с несвязным графом будем поступать?

Мне не нужен контейнер - я его не использую. Нужен - использую. Это у тебя альтернативы нет.

Ты с темы-то не съезжай. Ты написал, что графы надо делать на указателях. И что на массивах их делать не следует, причём не просто не следует, а если кто сделает, так это прям что-то позорное, цитирую тебя: «Графы. В графы руст тоже не умеет, надо костылить его через вектор?»

Сильные заявления требуют сильных доказательств. А я вместо них вижу обосравшегося школьника, который надеется, что если он не отквотил вопросы, на которые он ответить не может, то я забуду и он соскочит.

Нет уж, изволь отвечать. Как ты будешь делать на указателях несвязный граф. Как будешь освобождать память от этого графа? Я жду вообще-то. Ты же не трепло кукурузное, не ссышь пары простых вопросов, верно?

Разупорись. Претензии не к массиву, а к твоей упоротости.

Ух ты, вон оно оказывается. А раньше-то как пел:

Ой, тоже мне сеньёр, херов. Иди б-дерево сделай на своих массивах обсосанных или какой-нибудь поисковый граф. Костыльщики херовы, сначала сломали себе ноги, а потом пытаются выплясывать.

А теперь вдруг всё поменялось, и оказывается их высочество вовсе и никогда не говорило ничего про списки/массивы, не несло дичь о страшно дорогих растущих массивов (ты, кстати, бенч-то запустил, проверил?), оказывается местный дурачок обеспокоен моей «упоротостью».

Я всё ещё хотел бы увидеть, что это может быть за фича такая.

И я :-)

Каких-то громких случаев, приходилось с нетерпением ждать фикса бага как-то и не припоминаю.

Ожиданий я не помню, и не думаю что они там были — мозилла это не майкрософт и не яббл все же. А вот «багфикс и новые фичи в нагрузку» — скорее всего что очень даже было. У меня скриншотик был про багфикс в найтли, и без него разговор к сожалению получается беспредметный.

Если фича не косметическая (что не особо и интересно), а позволяет делать нечто фундаментально новое, то как это будет выглядеть? Ну представим, что в языке не было инлайн ассемблера (или дженериков или макросов), а в экспериментальной ветке он появился. Как мигрировать назад?

Ты перечислил фичи, а не проблемы. Полностью новая и независимая фича типа инлайн-ассемблер не ведет к feature clash, и не мешает тем, кто ей не пользуется, при условии безглючности.

Я попробую в твоих ситуациях сформулировать возможные проблемы — хотя это все чистые гипотезы.

Реальные проблемы по моим воспоминаниям были в плюсах при тотальном переходе на const (скорее неудобства), и в шаблонах при смене семантики около 2008 года (In a template definition, unqualified names will no longer find members of a dependent base). Возможно кто-то еще что вспомнит.

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

1. Сделать выхлоп всех этих функций в ассемблер целиком и записать в отдельные файлы. Остальное компилировать старой версией.

2. Независимость фич, типа «дайте мне компилятор без этого вашего ассемблера, но с новыми дженериками». Кому нужен ассемблер — пусть ручками пишет на асме и линкует.

Более реальная проблема: «Мы перешли на эти ваши дженерики, а все наши библиотеки с перегруженными функциями, хотим откатиться назад на перегрузку». Решение: раскрыть дженерики по таким-то типам примерно как g++ -E.

Но вообще когда указывать dyn для трейтов стало обязательным

Практически это только смена синтаксиса, я правильно понимаю?

Смысл в том, что взяв одну версию компилятора с последующей сборкой с разными диалектами крестов, не будет никаких ABI расхождений, оба бинаря будут иметь дело с одинаковыми строками, если есть пруфы обратного - тогда можно что-то обсуждать. Это позволяет компилить разными стандартами и линковать в целое (изначально ведь об этом речь шла).

Если кто-то достаёт откуда-то какое-то протухшее бинарное дерьмо без исходников и хочет с ним что-то слинковать, то крестовых стандартов это касается слабо.

В общем ты много банальностей написал, вперемежку с бредом. Поэтому просто укажу на ошибки:

типовая общая иллюстративня задача - есть N обьектов, и M множеств в которых они могут находиться. есть какие-то условия по которым обьекты из одного множества попадают в другое. реализовывать это массивах может только псих. поскольку ему придется иметь M массивов с указателями на обьекты, размером не менее N, которые в основном будут пустыми.

Ты какую-то херобору придумал. Зачем тебе разреженные массивы совершенно непонятно. Разве что ты решил множества реализовать чем-то типа битовой карты, но вместо битов заюзал элементы массива

достоинство массива не скорость перебора(у списка тоже высокая скорость перебора)

Не соответствует действительности. У списка очень медленная скорость перебора, из-за непредсказуемого обращения к памяти. Каждый переход к следующей ноде будешь по сотне циклов ждать.

если критична задача скорости поиска обьекта во множестве, это не массив, не список, а дерево типа бинарного, оно будет по любому быстрее перебора массива(если только не частный случай массива - сортированный и неизменяемый, тогда бинарный на нем поиск).

Даже сбалансированные бинарные деревья показывают плохие результаты по скорости поиска. Каждый переход по указателю - это дорого. Поэтому там где надо от бинарных деревьев отказались в пользу чего-то более похожего на массивы - б-деревьев. Условно, вместо того чтоб сравненить и в зависимости от меньше/больше пойти в левую или правую сторону, а потом ещё (N-1) раз так (т.е. сузить интервал поиска 2^N раз) лучше находясь в одной ноде тупо пробежать по массиву размером 2^N и найти тот же интервал с переходом по всего одному указателю.

Если же тебе реально нужно искать, используй хэш-таблицу. И знаешь, как в современных либах реализованы хэш-таблицы? Правильно, самым всратым по мнению первокурсника способом - массивом с открытой адресацией. Вместо красивых в теории бакетов.

если есть пруфы обратного - тогда можно что-то обсуждать.

Не про стандарт, но про продукты одной крупной корпорации.

Библиотека Abseil. Они, в частности, забекпортили string_view на С++14, но сделали это так, что если собираем с -std=c++14, то используется abseil-овская версия. А если с -std=c++17, то – уже из стандартной библиотеки. В результате, модули, собранные с разными версиями стандарта, друг с другом не линкуются. И такой полезный для организма трюк, как использование С++14 в API и С++2х в реализации уже не прокатывает.

И вишенкой на торте идет то, что они не могут бампнуть версию С++ для Tensorflow. Так и сидят на 14-й.

Такой веселый дизайн.

для этого вычисляется время его срабатывания (текущее+заданный интервал) и он вставляется в сортированный по моментам срабатывания список таймров (чем раньше сработает, тем ближе к голове), в нужное место. список этот интрузивный естессно.

Ну вот тут и проблема. Искать нужное место в списке долго будет. Поэтому в задачу и добавили условие, что таймауты одинаковые, чтоб список не проседал от поиска места вставки, вставлялись в конец.

и не надо ничего выдумывать на «массивах». массив это только для рандомного доступа. а рандомный доступ тут не нужен вообще.

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

Поэтому правильное правило выбора контейнера другое. Если можно не использовать связные структуры типа списка или бинарного дерева - не использовать их. Если возможности обойтись без списка нет, нужно взять паузу, подумать пару часиков, и придумать как всё-таки обойтись без списка. И только если наступила полная уверенность что да, только список и ничего больше не подходит, тогда можно браться за него.

По большей части он говорит правильные вещи. Но, во-первых, у него явно какой-то пунктик по поводу применимости списков.

Это не пунктик, я в общем-то давно уже написал, что есть ситуации когда списки нужно применять. Я знаю 2:

• у тебя в ТЗ требование делать список (например лабу задали)
• API принимает данные только в виде списка.

Возможно бывают и другие, но там надо думать. Вот в примере с таймерами подумал, и сделал через deque.

А пунктиком это кажется только от того, что такое впечатление всегда бывает, когда кто-то спорит с сумасшедшими. Если увидеть середину спора человека с 3мя плоскоземельщиками тоже может сложиться впечатление, будто он какой-то странный, стучит ногами и говорит что Земля круглая, и вообще, почему круглая, если она - шар. Однако один из моих оппонентов упорно пишет, что вектор нужен только если необходима индексация, а если она не нужна, то список получше будет, а другой на голубом глазу предлагает моделировать графы указателями и без общего контейнера для вершин. Видимо без GC жизни не представляет.

Но при этом не говорится, что когда мы делаем вставку в середину (или начало) вектора, то из-за элементарного memmove мы получаем отнюдь не меньшее вымывание кэша.

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

И, более того, если в векторе лежат элементы с кастомными операторами перемещения (не говоря уже про операторы копирования), то это будут еще большие накладные расходы.

В расте это не проблема, перемещение всегда через memcpy, а неявных консрукторов копирования не бывает.

Но реальность такова, что принцип компенсации не работает, бедные люди бывают одновременно ещё и больными, глупыми и злыми. В нашем случае такой злой и больной бедняк - это структура данных типа список.

Да, так, если это современная RAM. Но ведь можно сделать гибрид списка и массива, чем-то похожий на B-tree:

 ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ ┌─
→│ │A│B│C│D│ │E│F│G│H│I│ │J│ │K│L│⇄│M│ │ │ │N│ │ │O│P│Q│R│ │S│ │T│U│⇄│V
 └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ └─
    ⇵ ⇵ ⇵ ⇵   ⇵ ⇵ ⇵ ⇵ ⇵   ⇵   ⇵             ⇵     ⇵ ⇵ ⇵ ⇵   ⇵   ⇵      
    ▒ ▒ ▒ ▒   ▒ ▒ ▒ ▒ ▒   ▒   ▒             ▒     ▒ ▒ ▒ ▒   ▒   ▒      

Здесь латинским буквами обозначены ненулевые указатели, ▒ это нагрузка (payload). Массив указателей имеет длину в кэшлинию (64 байта). И все это предназначено для реализации LRU.

Без понятия почему в расте используется эпохи, и некоторые говорят что в С++ нужны эпохи, когда отличий от стандарта нет никаких.

Придумался ещё один аргумент: есть набор библиотек-зависимостей и при переходе на новый стандарт не хочется их обновлять (даже если там используется условный auto_ptr), получать новые предупреждения и т.д. Да, можно руками подобрать нужный устраивающий последний стандарт для каждой библиотеки, но с эпохами это работает автоматически.

Практически это только смена синтаксиса, я правильно понимаю?

Ну да. Было ещё несколько изменений с добавлением новых ключевых слов, но хоть сами изменения может и значительные (вроде асинков), но с точки зрения «ломания» - это просто добавление ключевого слова.

Поэтому там где надо от бинарных деревьев отказались в пользу чего-то более похожего на массивы - б-деревьев.

б дерево - все равно дерево! это списочная структура, а не массив. не надо цепляться к словам, и какое там дерево - совершенно неважно в оспаривании вздорного утверждения что списки не нужны. б-деревья нужны? значит нужны списки. графы нужны? значит нужны списки. приоритетные очереди нужны? значит нужны списки. хеш таблицы нужны? значит списки тоже нужны, там в массиве хранятся головы списков коллизий.

список это фундаментальный тип данных вне зависимости от кешей процессора или еще чего-то там.

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

кстати реализуй лисп на массивах.

кстати реализуй лисп на массивах.

Дерево можно упаковать в массив, но массив – фундаментально статичная структура данных. Мы не модем иметь одновременно O(1) на access() и на insert(). При O(1) на insert() массив вырождается в список. Можно иметь O(Log N) на обе операции, и тогда мы получаем b-tree.

Ну и вишенка на торте. Линейное адресное пространство памяти – виртуальное. И таблица отображения – это дерево.

Видимо ты назвал access то, что википедия называет search. Чет я задумался — а search вообще может быть быстрее O(log N)?

а search вообще может быть быстрее O(log N)?

хеш-таблица

Ты худший случай не учитываешь :)

даже простейшие хеш функции дают очень приличное распределение на данных общего типа.. а так - да. теоретически может выродиться в попадание в один слот.

Если мне не изменяет память, то для массива самое лучшее, что можно получить для insert() это O(sqrt(N)), если хочется O(1) для access(). Пруфов не найду. Видел когда-то давно в каком-то пейпере.

Еще надо учитывать, что все эти оценки в данном случае уже носят чисто теоретический интерес, так как там, скорее всего, будут плохие скрытые константы.