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

Абсолютно не очевиден, в том-то и дело.

Т.е. он может быть очевиден конкретно тебе, так как ты это всё ешь каждый день. Но даже среди опытных (без сарказма) программистов этот фактор часто не учитывают.

Вот пример, ради которого я этот тест и сделал:

khrundel> И никакие будущие гигабайтные кэши тебе не помогут, они, ввиду своих размеров, чуток добавят латентности себе и RAM и только отчасти скомпенсируют рост частот и количества ядер.

Я аж подпрыгнул. Неужели этот тезис не очевиден??

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

Ну вот в случае std::set у нас будет 40 байт на узел, минимум. Против 48 намеренных не так уж много.

Претензии были в основном к методике измерений.

Если хочется более компактного контейнера

Мне в какой-то момент показалось именно Вы за memory bandwidth сражаетесь. Особенно в контексте нашей недавней дискуссии на тему DRAM parallelism.

плюс даже возможно неверен.

Хех…

А аист1 че-то упорствует со своей не-лог шкалой. А без лог-шкалы нихрена не видно

А аист1 че-то упорствует со своей не-лог шкалой.

а если взять шкалу - логарифм логарифма… все на свете будет плоским совсем.

Там, в идеале, должно быть 4 прямых на Log-log. L1, L2, L3 и RAM. В этом тесте пересечение произошло в L3. Для другой структуры, если учесть замечания bugfixer по избыточности std::set, оно может произойти в другом месте, скорее в L2. Пересечения может и не быть вообще, и тогда – «это интересно»: BST сольет везде BTREE. Это будет значить, что в BST есть какой-то грубый косяк дизайна.

Стабильность итераторов.

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

Поэтому мне нужна тестовая нагрузка. А без нее намерять можно что кому нравится.

Пересечения может и не быть вообще, и тогда – «это интересно»: BST сольет везде BTREE. Это будет значить, что в BST есть какой-то грубый косяк дизайна.

Позволю себе не согласиться. Микро-тесты - оно такое…

А это потом еще отлаживать и сопровождать. Причем, другим людям.

Ну это вы может тут работаете, а я развлекаюсь. Push-у свои limits, так сказать.

Давай придумывай нагрузку для LRU.

И вот тут надо поподробнее.

Дык. Куда уж подробнее. Либо insert / delete invalidate iterators, или нет. Мы хотим чтобы не invalidate.

Мне в какой-то момент показалось именно Вы за memory bandwidth сражаетесь.

Тут я сражался за точку пересечения графиков. Которая попала «красиво» в L3 вообще без какого-либо шаманства с настройками тестов. У меня есть старый график примерно такого же бенчмарка, только вместо btree – PackedTree – n-арное упакованное дерево префиксных сумм. Это немного хуже, чем btree в плане OoOE (там сумма при поиске элементов делается). Так вот, там перелом тоже в конце L2 происходит (Core 2 Quad Q9300, но это сейчас уже не точно).

Вы

Ко мне здесь всем можно обращаться «на ты».

Давай, чтобы интересней было, не LRU, а 2Q.

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

Т.е. я его смогу засунуть в SWMRStore, когда тот с диском напрямую, без mmap, будет работать.

ок, познакомлюсь с ним

С потоками не связывайся. Это потом надо делать отдельно, а рамках заданной модели параллелизма.

Ко мне здесь всем можно обращаться «на ты».

Какой Вы, слово бы правильное подобрать, «либеральный», так скажем, товарищ… И по факту - тоже 4х значный ;) Может на пивко где пересечёмся? RVR например (если они ещё не разорились)?

Да, с потоками я пока что связываться не буду.

Познакомился с 2Q, посмотрел твой код. Что-то у меня со всем этим дело идет с каким-то сильным напрягом и трудом, может сегодня день такой.

1. ARC поприятней выглядит, но пусть 2Q

2. Почему бы 2Q из постгреса не утащить?

3. У тебя там с виду лишние методы, например attach — зачем? (Вроде достаточно get, put, можно добавить has)

4. 2Q в пейпере как-то неряшливо описана, нужно свое описание. У индуса arpitbhayani чуть получше вроде.

5. Я так понял что A1_in это FIFO из id+payload, A1_out это FIFO из id, AМ это LRU из id+payload в стандарном 2Q? А у тебя что-то другое?

6. У тебя рабочий пример к ней в коде есть? Где?

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

8. Зачем тебе свой Optional?

9. У тебя нагрузки для тестирования кэша есть? У Постгреса наверно должны быть.

1. ARC поприятней выглядит, но пусть 2Q

ARC патентованный. Утянуть можно, но практического смысла нет. 2Q хватит «за глаза».

2. Почему бы 2Q из постгреса не утащить?

Тоже можно. Я исходник взял для того, чтобы тебе было во что смотреть. Я когда алгоритм LIRS пытался понять, несколько дней потратил на медитации над доками. Был бы код, это бы сильно помогло.

3. У тебя там с виду лишние методы, например attach — зачем

В Мемории семантика кэша немного неканоническая. RAII блокирует записи в кэше, с которыми идет работа. Это чтобы их нельзя было вытолкнуть. get() отсоединяет запись от кэша, убирая её из списков. А attach() возвращает её в списки снова, давая возможность её вытолкнуть.

5. Я так понял что A1_in это FIFO из id+payload, A1_out это FIFO из id, AМ это LRU из id+payload в стандарном 2Q? А у тебя что-то другое?

Вроде да. У меня более-менее стандартная имплементация с поправкой на блокирование записей.

6. У тебя рабочий пример к ней в коде есть? Где?

Ссылка

Снэпшоты LMDBStore используют этот кэш для хранения блоков, которые были вытащены из нижележащей БД (LMDB в данном случае) для работы с ними. Кэш этот живет только пока живет снэпшот, поэтому он, обычно, маленький. Как L1 у CPU.

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

Мемория сейчас на этапе «Make it run». Нет смысла причесывать код, который потом, возможно, будет удален/переписан.

8. Зачем тебе свой Optional?

Это сейчас alias на бустовский optional.

9. У тебя нагрузки для тестирования кэша есть? У Постгреса наверно должны быть.

Какого-то бенчмарка для этого еще нет.

Я в New-York City обитаю. Если ты в наших краях, то можем пересечься)

4х значный

?)

Left, right, parent, value, color + alignment = 5*8 bytes.

и вдруг оказалось, что ЧК дерево тоже двусвязно

И не только оно, а и большинство других деревьев. Без parent link сложно организовать итерацию по дереву. Там итератор должен хранить весь путь от корня до текущего элемента. В случае сбалансированных деревьев это вполне нормально, так как длина такого пути логарифмическая. А вот в общем случае – длина может быть и N. Так себе итератор получится.

Т.е. еще одна практически важная структура данных, оказывается, не DAG.

И если двусвязный список еще можно запихнуть в массив, и, тем самым, сделать вид, что «списки просто не нужны». То вот дерево в монолитный массив запихнуть будет сильно труднее. Кто хочет, может потренироваться. Такие схемы есть, но они все статические: добавление элемента – O(N).

Без parent link сложно организовать итерацию по дереву.

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

то есть даже без пользовательских итераторов парент нужен по любому.

Хм, надо подумать. Спасибо за идею. Мне казалось, что parent при вставке будет получен при спуске к месту вставки.

Хм, надо подумать. Спасибо за идею. Мне казалось, что parent при вставке будет получен при спуске к месту вставки

при вставке - да. а при удалении никакого спуска уже нет.

Так нам же надо сначала найти удаляемый элемент, так мы и путь к нему получим. Я тут неявно апеллирую к функциональным деревьям. Там parent links в принципе нет. Но я сейчас сходу не скажу, как ребалансировка в функциональном BST делается.

В B+tree без parent links все операции делаются нормально, включая групповые. Только муторно. Обновление итераторов, если таковое надо, тоже сильно труднее делается. В общем случае для эфемерных деревьев, наличие parent link всё сильно упрощает. Не сильно высокая цена вопроса.

Хм, надо подумать. Спасибо за идею. Мне казалось, что parent при вставке будет получен при спуске к месту вставки.

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

Я написал об этом своими словами вот тут: Rust и двусвязный список (комментарий)

Пока, кстати, хорошего жизненного примера «негарантированного родителя при вставке» я еще не вижу. Щас попробую нарисовать свой, похожий на жизненный: Rust и двусвязный список (комментарий)

при вставке - да. а при удалении никакого спуска уже нет.

Я думаю, что вопрос вовсе не в разнице вставка/удаление, а в другом.

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

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

Тут, понятно, возникнет вопрос «а почему бы нам тогда не отрезольвить ДНС сразу?». Потому что пример не жизненный, а нарисован. А хочется жизненный.

Дык. Куда уж подробнее. Либо insert / delete invalidate iterators, или нет. Мы хотим чтобы не invalidate.

Итераторы тоже разные бывают. И это напрямую связано с моими компромиссами, про которые ты спрашивал.

В случае LRU имеются ограничения:

1. Итераторы не инкрементируются
2. Итераторы существуют в количестве 1 штука на элемент
3. Сплайсы не нужны
4. Вставка только с краю, причем только с одного
5. Настоящее удаление только с краю, причем только с одного

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

Но и когда тебе нужны сплайсы, вполне возможно, chunked array тоже выиграет. Ради любопытства сформулируй свою задачу.

А зачем аксиома о равенстве, да еще такая стремная?

Немного подумав, я полагаю, что без нее 2х2=4 верно, но будет означать «если вам сильно повезет, то вы получите 2х2=4, но вы можете также получить в своем натуральном ряде и что-то другое, например 2х2=187 даже при непротиворечивой аксиоматике»

Это ведь немного не то, что люди понимают под 2х2=4, правда?

Или чуть более красиво «если в вашем натуральном ряде умножение и сложение однозначно определено (и ваша аксиоматика непротиворечива), то 2х2=4».

Но это снова немного не то, что люди понимают под 2х2=4.

любой труд должен быть оплачен

Ну вот ты совершенно бесплатно понизил в 2 раза вероятность того, что ты не физик (в истории про буквы л).

Можешь теперь меня бояцца (или бояццо? я не силен в современном правописании).

https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%86%D0%B8%D0%B1%D0%B5%D0%BB

Я не спорю с твоим написанием (это было бы смешно). Я про другое говорю.

Я про другое говорю.

совсем, совсем другое?…

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

так о чем думаете вы, милейший a–?

Не вижу тут никакой блокировки, вижу очереди — две очереди машин.

А очередь – это разве не блокировка? Если у тебя неблокирующая очередь, то тебе понадобится backpressure. Те же яйца, только в профиль.

Ты серьезно что ли?

backpressure можно делать интеллектуально, например не пускать слишком много машин в город, если у нас слишком большие очереди на перекрестках.

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

Или, альтернативно, тебе придется иметь и блокировки, и backpressure.

так о чем думаете вы, милейший a–?

1. хорошо бы перечитать тред с начала

2. хорошо бы набросить че-то заново, т.к. емнип завтра тред пропадет с первой страницы сайта

UPDATE: рано пока набрасывать, здесь еще много необговоренного

Я так понял что A1_in это FIFO из id+payload, A1_out это FIFO из id, AМ это LRU из id+payload в стандарном 2Q? А у тебя что-то другое?

Вроде да. У меня более-менее стандартная имплементация с поправкой на блокирование записей.

А мне кажется что нет, у тебя не 2Q.

A1_in и A1_out должны быть разных типов (A1_out без payload). А у тебя это не видно и статические типы у них одинаковы.

И даже если предположить, что ты там payload отцепляешь в eviction_fn_ (что мне совсем не очевидно, и комментариев про это ноль), то все равно A1_in и A1_out лучше сделать статически разных типов, не?

В Мемории семантика кэша немного неканоническая.

Лично мне семантика примерно в 10 раз интереснее, чем код. Особенно неканоническая (она уже в 100 раз).

Или, альтернативно, тебе придется иметь и блокировки, и backpressure.

неужели невозможно придумать lock-free перекрестки и дорожную сеть? это элементарно, ватсон! если впереди вас машина - строится новая дорога огибающая ее и вы продолжаете движение… а после вас дорога разрушается.

Или, альтернативно, тебе придется иметь и блокировки, и backpressure.

BP на блокирующих очередях не нужно. Если consumer не может сейчас принять элемент, то producer блокируется.

А мне кажется что нет, у тебя не 2Q.

Это именно что 2Q в плане базового алгоритма.

Лично мне семантика примерно в 10 раз интереснее, чем код.

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

И даже если предположить, что ты там payload отцепляешь в eviction_fn_ (что мне совсем не очевидно, и комментариев про это ноль),

Отцепляю в функторе.

то все равно A1_in и A1_out лучше сделать статически разных типов, не?

Ну сделай разными типами, L1I нужно больше кода!)

Ну сделай разными типами, L1I нужно больше кода!)

Твой код (а-ля 2Q) можно использовать 3 способами:

1. Читать примерно как детектив с его резкими и неожиданными сюжетными поворотами

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

3. Усомниться в работоспособности собственной мыслительной системы :-)

Использование же твоего кода для ознакомления с идеей 2Q, или в бенче (я уж не говорю про продакшен) — весьма затруднительно.

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

Альтернативно, ты можешь взять за образец реализацию из PG, но там вряд ли будет сильно проще, так как это тоже «практическая реализация».

Код IRL редко бывает «простым и красивым».

Вспоминать, как должен быть устроен правильный язык на основе С++

Языком (как мы привыкли его себе понимать) мы тут мало чего добьемся. Тут как раз и нужен LS и платформа для метапрограммирования, с ним интегрированная. Чтобы можно было интерактивно проследить как раскрываются метапрограммы и как потом используется код. А раскрывать это всё «в голове» – это надо мотивацию очень сильную иметь.

У моего кода есть одно неоспоримое преимущество: он есть и он используется.

У моего кода есть одно неоспоримое преимущество: он есть и он используется мной. // FIXED

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

Если ты сделаешь пример использования для самого простого случая — скажем, кэша объектов без деструкторов в арене — то я могу попробовать заняться своим делом. И, кстати, сомневаюсь что кто-то снаружи будет использовать код без комментариев и без sample usage.

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

используется мной

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

Не надо использовать мой код, он тебе дан для справки. У тебя, кроме того, будет совсем другая реализация, так как у chunked array нет стабильных итераторов. А у меня всё на интрузивных списках сделано.

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

Я, вообще-то, сначала собрался именно использовать твой код, предоставив drop-in replacement для QueueT. Хотя из-за этих непонятных мне eviction_fn_ могу завязнуть.

Понятно что drop-in будет ИСКЛЮЧИТЕЛЬНО в рамках тех вызовов, что ты делаешь в своем классе, а не вообще как замена boost::intrusive::list

Я тебе сразу советовал забить. IRL кэши делаются под специфические требования использования, поскольку они сильно оптимизируются.

Если ты всё же хочешь попробовать, то делай сначала самую базовую реализацию. Make it run. А потом её подтянем под требования.

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

4. Вставка только с краю, причем только с одного

5. Настоящее удаление только с краю, причем только с одного

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

возможно, chunked array тоже выиграет.

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

Что я упускаю?

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