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

ПыСы. Что-то мне подсказывает Вы deque пытаетесь изобрести. Хех.

Хозяйке на заметку: подсказывалку можно калибровать, пройдясь по комментам пользователя.

Два этих условия нас мгновенно приводят к очереди (или стеку) построенной поверх деки. Что я упускаю?

То, что на самом деле это не условия, а послабления. (Я их назвал ограничениями, но имел в виду «ограничения на ограничения»).

Несмотря на эти послабления у нас остается ограничение «О(1) на перенос элемента из середины контейнера во фронт». И у деки с этим не очень, прямо скажем.

Ты правильно схватил мысль насчет удаления. Я классифицирую мутирующие операции контейнера не как «вставка, удаление», а как «вставка, настоящее удаление, перенос».

Насчет переноса из одного списка в другой — у меня было указано LRU, где это не требовалось. В общем случае это потребуется.

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

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

Я-то предполагал, что дизайн будет без unordered_map. Т.е. роль unordered_map играет TLB и адреса объектов в памяти. Вот в таком дизайне ускорение QueueT имело бы явный смысл.

Еще раз: я преполагал свою оптимизацию для случая, когда у нас все объекты (элементы кэша 2Q) лежат прямо в памяти (или в арене, или в контейнере с прямой адресацией), и мы обращаемся к ним по их адресам, а не по ключу в unordered_map. Или для чего-то похожего в смысле высоких требований по скорости.

UPDATE: может это и стоит забенчить для начала. Насколько unordered_map торомзит intrusive_list (или наоборот).

Я на «ты» предпочитаю общаться на форумах, со всеми. Тут в одном треде очень легко перескочить с темы, которую ты знаешь сильно лучше собеседника, на тему, которую ты знаешь сильно хуже. И обратно.

То, что у меня там unordered_map, не должно сбивать с толку. Что было под рукой, то и влепил, зная, что потом легко могу заменить на более производительный контейнер. Просто эти «более производительные» могут вести себя «странно», что может добавить проблем при отладке. И всякие такие оптимизации имеет смысл делать тогда, когда подсистема уже устоялась (т.е. после make it correct).

Я когда Меморию только начинал, я по производительности упарывался. И сразу писал «самый быстрый код» и «самую высокопроизводительную архитектуру». Потом я задолбался это всё вместе отлаживать и переписывать, и полюбил простой, понятный, предсказуемый, стабильный и медленный код (который, тем не менее, всё равно будет быстрее той же Java). Кто-то всю жизнь пишет один этот несчастный (или счастливый) кэш, вылизывая его до умопомрачения. А у меня, условно, 1000 таких «кэшей» в архитектуре, причем самописных. И если что-то останется медленным, то, «не судьба». Я фокусируюсь на «make it correct». Ты не доверишь свои данные БД, которая их теряет. Какая бы быстрая она не была. Понимаешь?

У меня совершенно нет претензий к мемории по поводу unordered_map. Я говорил о том, что мне туда лезть с оптимизацией intrusive_list бесполезно. Лучше для начала забенчить intrusive_list vs. intrusive_list+unordered_map.

К мемории у меня другая, если так можно выразиться, претензия. Мне не понятно, как кто-то придет и начнет использовать или хотя бы изучать код совершенно без комментариев и *так* написанный. В функции attach похоже на троекратное повторение кода (insert_and_cut, вставка c удалением лишнего для очередей A1i,A1o,Am), а сверху дополнительно похоже что дублирование кода функции has_entry. Это создает сильный WTF при изучении и вопросы «а может там не повторение и я что-то не вижу».

Я уж даже подумал — а не генеришь ли ты свой код чем-то.

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

Наконец, для меня это все в мемории интересно по мотивам создания языка, а не потому, что я это решил использовать.

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

Я фокусируюсь на «make it correct».

Это отдельная, отличная тема для разговора.

Вот ты говоришь Copilot, Copilot... а он сможет хотя бы сгенерить простой sample usage для твоего класса?

Это не интерфейсная часть кода, поэтому документировать её нет особого смысла. «Без единого комментария» превратится в «комментарии ничего не проясняют». Сейчас в opensource oversupply, поэтому сейчас людей надо мотивировать смотреть и использовать любой код. Банально – или деньгами, или славой, или ожиданиями продвижения по социальным лифтам, трудоустройством в распиаренную корпорацию и т.п. Мы пользователя откровенно разбаловали. Но очевидным становится это только тогда, когда в каком-нибудь log4j найдут критическую багу и окажется, что весь этот проект тянут 3.5 человека в свободное от работы время, в полном забвении со стороны пользователей. Opensource по факту в глубоком кризисе. И делать сейчас что-то с «ориентацией на использование» – это пустая трата своей жизни. Нужны, если вообще возможны, другие мотивы. Я, например, служу Железному Господину. ЖГ – это полу-шутливое название квинтессенции Здравого Смысла, для которого есть некоторая надежна на материализацию и даже олицетворение в виде benevolent (к нам) ИИ. Вот для него и делается Мемория.

Я уж даже подумал — а не генеришь ли ты свой код чем-то.

Ты близок к истине :)

Наконец, для меня это все в мемории интересно по мотивам создания языка, а не потому, что я это решил использовать.

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

Copilot – языковая модель, с некоторыми (фрагментарными) возможностями онтологического вывода. Чтобы Copilot-like модели могли работать с кодом, этот код должен быть «типовой» и встречаться в обучающей выборке достаточное количество раз.

Грубо говоря, если бы вокруг было всяких меморий, как веб-фреймворков, то Copilot смог бы это всё «отрефакторить». Но меморий вокруг нет ни одной. Код в Мемории особенный в том смысле, что там идет борьба (наличными средствами С++) с комбинаторной сложностью взаимодействия различных структур данных друг с другом. В обычной работе программисты с такими проблемами не сталкиваются на столько, что у них даже нет понимания, зачем нужны мономорфные дженерики. Поэтому и достаточного количества кода для Copilot-а не наберется.

Кстати, когда CLion только появлялся, мои друзья использовали тогдашнюю версию Мемории для тестирования этой IDE. CLion практически сразу висла после открытия проекта, пытаясь его проиндексировать (они что-то там накастыляли в UI-потоке). С каждой новой версией CLion висла всё позже и позже и с какого-то момента научилась открывать этот проект нормально.

Я на «ты» предпочитаю общаться на форумах, со всеми.

А я - нет. Зовите меня снобом, но абс никогда не знаешь с кем общаешься нынче… В этом смысле господин aist1 проверку прошёл - не «зазнался»…

Хозяйке на заметку: подсказывалку можно калибровать, пройдясь по комментам пользователя.

А вот для этого старенький я ужо - никакого времени не хватит. Отчасти потому и пред посыл…

То, что на самом деле это не условия, а послабления.

Мне было бы реально проще если бы Вы описали все требования (гарантии?) которые Вы к конкретной структуре предъявляете.

Упускаешь, что же именно он имеет ввиду под «настоящим удалением».

Очень бы хотелось услышать определение. Под «ненастоящим» удалением мы подразумеваем «пометить entry как dead», или что-то ещё?

Под «ненастоящим» удалением мы подразумеваем «пометить entry как dead», или что-то ещё?

Под ненастоящим удалением я подразумеваю удаление, за которым сразу же следует вставка в тот же список в случае LRU (а в общем случае, видимо, и в другой список)

Мне было бы реально проще если бы Вы описали все требования (гарантии?) которые Вы к конкретной структуре предъявляете.

Требования к моей коллекции: быть быстрее интрузивного списка только на том множестве операций, которые требуются при реализации LRU (или 2Q) на интрузивном списке. Поскольку хороших таймингов нет (хорошие это было бы что-то вроде 1p+2r+2w+0.1b, где p это проход по указателю, r это чтение данных в размере 4-8 байт, w это запись в размере 4-8 байт, b это случай неправильного предсказания перехода) пусть будет О(...).

Для коллекции, замещающей интрузивный список внутри LRU это (если не упустил что-то):
1. удаление с конца за О(1);
2. вставка в начало за О(1);
3. перенос из середины в начало за О(1).

По памяти, видимо ограничение «занимать не более чем в 2 раза больше, чем список».

я подразумеваю удаление, за которым сразу же следует вставка в тот же список в случае LRU

Я бы назвал это «move». Кмк, моделировать это как erase + insert не совсем правильно - можно обойтись патчингом пары ptrs (если всё сделать правильно).

Для коллекции, замещающей интрузивный список внутри LRU это (если не упустил что-то):

3. перенос из середины в начало за О(1).

Ты про чтение забыл. Удаляемый элемент еще найти надо.

Ты про чтение забыл. Удаляемый элемент еще найти надо.

Надо, но не мне :-)

Если ты про настоящее удаление, то там удаление с конца, а конец списка и помнить можно.

Если ты про перенос из центра во фронт — то там поверху списка нужен либо map (через который мы будем находить элемент), либо прямые адреса элементов в памяти.

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

Я бы назвал это «move». Кмк, моделировать это как erase + insert не совсем правильно - можно обойтись патчингом пары ptrs (если всё сделать правильно).

Я согласен с этими соображениями, но слово move занято std::move, так что я не уверен что в списке имеет смысл использовать слово move. Но я не настаиваю. Может как раз наоборот оно и нужно.

Я бы назвал это «move».

А еще возможна точка зрения, что это splice диапазона (range) длиной в 1 элемент и в тот же самый список (а не в другой).

либо прямые адреса элементов в памяти

У тебя chunked array, какие еще прямые адреса элементов в памяти?))

но слово move занято std::move, так что я не уверен что в списке имеет смысл использовать слово move

Дарю: «rotate». Не благодарите :)

Ты про чтение забыл. Удаляемый элемент еще найти надо.

У тебя chunked array, какие еще прямые адреса элементов в памяти?))

a--: Ключевой момент, должен заметить. И именно то место откуда требование к стабильности итераторов появляется.

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

Тут надо заметить, что в случае списка и аллокации в пуле, когда пул берет память под записи тоже чанками, будет фрагментация чанков пула. Но меньше, чем в случае chunked array. Учитывая, что кэши обычно ограниченного размера, в худшем случае размер пула будет равен максимально допустимому размеру кэша.

У тебя chunked array, какие еще прямые адреса элементов в памяти?))

Щас расскажу случай, приближенный к реальности, с прямыми адресами.

Допустим, мы — Гугль. Юзер запросил поиск, который может дать 1000 результатов (100 страниц по 10 результатов). Мы, понятное дело, не считаем сразу 100 страниц, а создаем Итератор по результатам поиска и считаем только первую страницу. Этот Итератор создается в пуле фиксированного размера и его прямой адрес записывается в LRU кэш.

Последние эн миллионов поисковых строк лежат в Другом Кэше, который тоже как-то управляется, но как — не важно. Рядышком с поисковой строкой лежит прямой указатель на Итератор. При выталкивании Итератора из LRU кэша указатель на него обнуляется и в кэше поисковых строк (т.к. Итератор внутри себя еще и содержит ссылку на поисковую строку в Другом Кэше). При выталкивании поисковой строки из Другого Кэша Итератор выталкивается и из LRU кэша тоже.

После выталкивания Итератора из LRU кэша и обнуления указателя на него рядом с поисковой строкой выполняется деструктор Итератора.

Таким образом у LRU кэша нет обязанности отвечать «где лежит Итератор» — это и так известно. Прямые адреса, гы-гы. Необходимости в map<ПоисковаяСтрока,Итератор> нет. Но у LRU кэша есть обязанность обнулить ссылку на Итератор, выталкиваемый из LRU кэша по случаю:
1. недостатка места в LRU кэше (т.е. в пуле Итераторов)
2. выталкивания поисковой строки, владеющей Итератором, из Другого Кэша

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

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

И какие тут проблемы?

(насчет прямых адресов ответил багфиксеру)

Если мы элементы не перемещаем, то и чанки не сливаются вообще. Они постепенно прореживаются до состояния 1 элемент на чанк.

Юзер запросил поиск, который может дать 1000 результатов (100 страниц по 10 результатов). Мы, понятное дело, не считаем сразу 100 страниц

Это называется paging. То что у Вас элемент LRU это на самом деле 10 индивидуальных результатов поиска ни в одном глазу не делает этот контейнер «chunked array» структурой. Я (мы?) ожидал(и) совсем другого. И я бы пошёл гораздо дальше: кому интересно считать и кешировать 1000 результатов если условный юзер дальше первых 10 / 20 / 30 с огромной вероятностью не пойдёт?

ПыСы: и довольно фундаментальный вопрос - откуда ограничение в 1000 берётся? Почему не 10k или не миллион?

ПыПыСы:

Щас расскажу случай, приближенный к реальности, с прямыми адресами.

Допустим, мы — Гугль.

Если это реально то что Google делает behind the scenes - лично я в компетенции их сотрудников довольно сильно разочарован… Был лучшего мнения, правда.

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

Так его это устраивает. Он не за глобальную/универсальную справедливость, а за свою «сермяжную правду» борется. Ну как может.

То что у Вас элемент LRU это на самом деле 10 индивидуальных результатов поиска ни в одном глазу не делает этот контейнер «chunked array» структурой.

Не делает. Меня весьма удивило то, что ты в пейджинге усмотрел мою попытку найти «chunked array».

И я тут не собирался рассказывать тебе про chunked array. Я рассказывал про возможность прямых адресов (и отсутствие unordered_map) в похожей на реалистичную ситуации.

И я бы пошёл гораздо дальше: кому интересно считать и кешировать 1000 результатов если условный юзер дальше первых 10 / 20 / 30 с огромной вероятностью не пойдёт?

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

Юзер запросил поиск, который может дать 1000 результатов (100 страниц по 10 результатов). Мы, понятное дело, не считаем сразу 100 страниц

не считаем

^^^^^^^^^^^ читай тут

Если мы элементы не перемещаем, то и чанки не сливаются вообще. Они постепенно прореживаются до состояния 1 элемент на чанк.

Да. Поэтому элементы все же придется перемещать когда-то.

И, привет сборка мусора стоимостью O(N) ?

У тебя chunked array, какие еще прямые адреса элементов в памяти?))

Немного подумав, я пришел к мысли как еще ускорить твой дизайн, выкинув нафиг и unordered_map. Причем, похоже, даже и в многопоточке. В варианте «один поток крутит LRU/2Q, а другой достает закэшированные элементы без unordered_map».

Правда, есть сомнения в том, что все это ускорение кому-то интересно в случае кэширования, где по условию процесс доставания элементов мимо кэша достаточно медленный.

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

UPDATE: именно про модели доступа (проще говоря, указатели) в Раст мы и разговариваем в этой теме.

И, привет сборка мусора стоимостью O(N) ?

Нет, все будет чистенько сразу.

UPDATE: но пул конечно придется иметь раза в 2 больше среднего значения.

UPDATE2: даже если что-то снаружи вынудит нас разводить мусор, то занятость чанков очень легко трекать битами, и рекурсия не нужна. Короче все быстро.

Ну Ок. Показывай дизайн, когда созреет)

Я думаю начать лучше с того, что я чуть причешу твой 2Q и приделаю к нему sample usage, а ты поправишь ошибки если что.

Потом сделаю к нему генератор нагрузки.

Потом забенчу твой 2Q.

Потом забенчу твой 2Q vs. unordered_map+intrusive_list vs. intrusive_list.

Как-то так вроде.

Как тебе удобнее))

TwoQueueCache довольно просто оторвать от Мемории. Не пытайся её сейчас собрать, там какие-то фантомные зависимости от окружения, я работаю над этим.

Я вижу что просто оторвать. Я так и собирался сделать.

Кстати, вопрос. Ты умеешь в вероятностное программирование?

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

Так вот, генератор нагрузки на кэш хорошо делать через вероятностное программирование. Если не в курсе, как оно работает (оно довольно таки простое в базисе), в Сети много материала. Пригодится.

UPD: Поддержка ВП будет в рантайме Мемории, а так же предполагаются соответствующие DSL.

Я пока не приходя в сознание ковыряюсь. Вот оторвал твое 2Q от Мемории.

Последние эн миллионов поисковых строк лежат в Другом Кэше, который тоже как-то управляется, но как — не важно. Рядышком с поисковой строкой лежит прямой указатель на Итератор.

Я рассказывал про возможность прямых адресов (и отсутствие unordered_map) в похожей на реалистичную ситуации.

То что Вы «спрятали» map в «Другой Кэш» и заявили «мне пофиг как оно там устроено» не отменяет факта что она в том или ином виде необходима.

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

И дальше по тексту. Слов много, а вот смысла маловато.

Предлагаю на этом остановиться - мы на разных языках разговариваем.

То что Вы «спрятали» map в «Другой Кэш» и заявили «мне пофиг как оно там устроено» не отменяет факта что она в том или ином виде необходима.

1. А зачем map дублировать во втором кэше?

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

P.S. не надо по моему веселому троллингу делать вывод о внутренностях Гугла а то меня уволят

Слов много, а вот смысла маловато.

Там действительно не самый лучший вариант, можно получше сделать.

Избавиться от map, может быть, и хорошая идея с точки зрения микро-бенчмарка, но не очень хорошая с точки зрения использования кэша. В Мемории 2Q разрешает ID в блок, и первичным ключом будет ID, а не «адрес» блока. Который эфемерен и существует только для блоков, загруженных в RAM. А так ты просто переносишь необходимость хранить и поддерживать этот mapping на пользователя кэша, который (mapping) будет примерно одинаковым для большинства использований. Ну и зачем нам такое дублирование кода?

Если хочешь повышенной гибкости, то сделай map опциональным.

Не совсем так.

Для микробенча я предлагаю полный кейс. Т.е. да, map там будет у пользователя кэша, но *именно* за счет этого он будет более эффективен, чем был бы у самого кэша.

Как отвязать map от кэша я не думал, но видимо стоит подумать.