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

Пример годный, да. Сделать можно просто, сохраняя в контейнере список открытых итераторов и обновляя их при обновлении дерева.

Пример годный, да. Сделать можно просто, сохраняя в контейнере список открытых итераторов и обновляя их при обновлении дерева.

Мне реально такое требовалось.

А теперь переходим к случаю, когда у нас не два, а два миллиона итераторов (правда это мне не требовалось).

Мне реально такое требовалось.

В случае b-tree потребуется в итераторе, при каждой итерации, сохранять информацию для полного восстановления итератора в худшем случае. Т.е. опять небольшой (обычно) штраф при чтении + штраф при обновлении контейнера (обновление итератора не бесплатное).

А теперь переходим к случаю, когда у нас не два, а два миллиона итераторов (правда это мне не требовалось).

Вообще не вопрос. Интрузивный список итераторов нас спасет в этой кошмарной ситуации. Количество дополнительной работы при обновлении контейнера будет запредельным – это да. Поэтому я в дизайне взаимодействия контейнера и итераторов предпочитаю сохранять и восстанавливать итераторы явно. Мне «ехать», а не «шашечки». Тем более, что обычно операции над контейнерами делаются через [e]DSL, так как вручную они всё равно слишком громоздки.

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

Ну так вот ее похоже можно сделать не запредельной, а вполне приемлемой, и даже может незаметной, о чем я и написал ранее: Rust и двусвязный список (комментарий)

Это если у тебя только один, классический, вид b-tree. У меня – целое семейство, да еще есть и эфемерные, и персистентные. Придумывать для каждого типа контейнера оптимальный способ обновления итераторов – забодаться можно. Источник постоянных ошибок.

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

Один важный коммент, который я не успел сделать в моем коде: у меня h(a,b) гарантированно отличалась от a и от b. Так что свои итераторы a & b я удалить не мог, но вот что с ними случится при ребалансировке — вопрос был открытый.

Придумывать для каждого типа контейнера оптимальный способ обновления итераторов – забодаться можно.

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

Я предпочитаю не решать нерешаемых задач :-)

(слайсы не считаем)

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

Я предпочитаю не решать нерешаемых задач :-)

(Не)решаемость она такая, от личности решателя сильно зависит :-)

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

(Не)решаемость она такая, от личности решателя сильно зависит :-)

Я тебе могу сказать, что любые личности решателей, включая гениев, ничтожны по сравнению с присущей сложностью мира. Остальное – это «ошибка выжившего».

Один из вариантов ответа на это — такая сложность специально сделана для того, чтобы было побольше нерешаемых задач, которые можно успешно решать :-)

Между «успешно решать» и «успешно решить» – большая разница.

:)

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

У меня для тебя хорошие новости. Важнейшая во Вселенной задача поиска кратчайшего представления битовой строки, т.е. Задача Познания, вычислима в пределе. Т.е. решать её можно до бесконечности и всегда иметь некоторый прогресс. А вот решить её в общем случае нельзя.

Конечно. А в расте как-то не так?

Скорее всего так. Я не в плане раст или не раст, а в том, что, возможно, слишком тяжело будет, тяжелее чем список. Впрочем, само устройство b-дерева таково, что можно и без балансировки, удалять большими поддеревьями. Так что в принципе наколхозить кастомное.

Память под таймеры в таком подходе будет занята пока время не истечёт

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

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

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

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

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

Она и в вашем случае кончится. Если не раньше.

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

Дословно:

Он очень эффективен когда в программе создаются таймеры с одинаковой задержкой.

Если задержка не одинакова, то он не эффективен, но работает. И, как по мне, это лучше, чем получать отлуп в рантайме.

Впрочем, само устройство b-дерева таково, что можно и без балансировки, удалять большими поддеревьями.

Дельная мысль, но это работает только если удалять непрерывным куском. А если нет — то будет ребалансировка.

Я тут еще немножко подумал о timer-list. Он крайне поучителен во многих моментах. Сначала отмазки:

1. Если timer-list удастся написать на сейф расте, то это не означает, что раст хороший. В продакшене надо писать напрямую, а не лавировать между ограничениями.

2. Да, самый прямой способ организовать timer-list — это двухсвязный список. Но мне интересно сделать его на деревьях и кажется получится быстрее.

Теперь по сути:

У тебя сохранился твой старый вариант на std::map и тесты скорости? Мне кажется минимальное портирование (т.е. замена итераторов на поиск в btree::map) ускорит твои таймеры.

Правда в таком варианте нет гранулярности. Гранулярность тоже можно сделать, но это надо уже немного другое btree.

Именно btree для bulk updates весьма неудобно. Лучше b+tree (в варианте без sibling links).

Небольшой лайфхак для ЛОРа: чтобы искать по всему треду, а не по страницам, тыкни на кнопку «Показать удаленные комментарии»

Вот кстати получился отличный use case под 100 000 итераторов. Посмотри выше по треду, что eao197 хочет видеть от timer-list.

timer-list можно сделать без гранулярности на основе btree::map, а можно с гранулярностью на основе ordered_multimap, но тогда нужно чтобы все наши 100 000 итераторов на элементы не инвалидировались при вставке-удалении. Что я вроде придумал как делать без напряга, если конечно че-нить не упустил.

Гранулярность вставки и исполнения таймеров вроде как дает сильную экономию ЦП и на исполнении таймеров, и на сортировке вставляемых таймеров.

Bottom line: неинвалидирующиеся итераторы нужны!

Латтнером который llvm и clang сделал.

Латтнер придет, порядок наведет.

Я из всех тех страшных слов на https://circt.llvm.org/ знаю только SystemC.

Нужны, конечно же. Но нарушается принцип don’t pay for what you don’t use. Так что они нужны как опция.

Она и в вашем случае кончится. Если не раньше.

Да, кончится, и да раньше, в тот момент, когда будет нагрузочное тестирование. Почешут репу, докупят памяти или разнесут обработки запросов на несколько параллельных серверов. Но не будет ситуации, когда рассчитывая на обработку N запросов в секунду, протестировали для верности на 2N и всё работало, а потом, в процессе эксплуатации, всё упало даже на N/4 и только от того, что удалённый чужой сервер вдруг стал медленнее отвечать.

Если задержка не одинакова, то он не эффективен, но работает. И, как по мне, это лучше, чем получать отлуп в рантайме.

Не, практически работать не будет. Представляем ситуацию: 90% таймеров устанавливаются на T и 10% на T/2. При этом реальный запрос отрабатывается в среднем за T/10. И очередь разрослась до пары тысяч. Это будет означать, что в голове очереди будут стоять пара таймеров реально подвисших запросов, потом куча ещё неотменённых T/2 таймеров, потом куча T-таймеров. Это значит при каждой 10м запросе, если реализовывать совсем тупо, то будет проход с конца примерно половины списка. И даже никак не сократить, не выбрать правильный конец для вставки T/2. Так себе решение для хай лоад.

В общем надо по отдельной очереди для каждого значания таймаута вводить, в нашем случае 1 очередь для T и одна для T/2. Ну и как-то внушение проводить, чтоб сильно большое разнообразие таймаутов не использовали.

У тебя сохранился твой старый вариант на std::map и тесты скорости?

Нет, это дело было где-то в 2003-ем или в 2004-ом году. Плюс это все было внутри тогда еще закрытой разработки.

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

Так себе решение для хай лоад.

ну вы тут просто нереальные сцуко-архитекторы. то что делает таймер(например вызывая хук) при активации должно занимать ПРЕНЕБРЕЖИМО МАЛОЕ ВРЕМЯ по сравнению с тиком таймерной очереди, и разумеется таймер не может вызвать ни одну функцию, что может быть заблокирована, поскольку это остановит обработку очереди таймеров.

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

потому работа таймерной очереди это - последовательная выборка ВСЕХ созревших на данном тике таймеров, активация их хуков (или проброс мессаги в очередь адресата ивента таймера), и либо запихивание таймера обратно в очередь (если стоит признак periodic), либо - забыли о нем и все. то есть фактически тот тред или та активность, что крутит таймеры, тратит основное время только на выборку и вставку в список.

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

ну вы тут просто нереальные сцуко-архитекторы. то что делает таймер(например вызывая хук) при активации должно занимать ПРЕНЕБРЕЖИМО МАЛОЕ ВРЕМЯ по сравнению с тиком таймерной очереди,

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

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

Как бы в этом месте alysnix все правильно написал, он явно более в теме, чем все остальные.

Ну и как-то внушение проводить, чтоб сильно большое разнообразие таймаутов не использовали.

Удержу 100 000 таймеров с большим разнообразием таймаутов на самом бюджетном ноуте. Без раста. Дорого. Гарантия.

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

А так и делают. Чего все с этими таймерами возбудились? Это либо простой интрузивный список, либо heap, если нужна очередь с приоритетами.

Чего все с этими таймерами возбудились?

Для тех кто забыл, напомню, что khrundel здесь один против всех в попытках доказать, что спискам в современном мире не место.

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

он явно более в теме

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

Чего все с этими таймерами возбудились?

Не-не, пример очень поучительный (по крайней мере для меня). Там реальные потребности сделать структуру данных, про которую Раст считает, что в ней потребности нет.

Раст не может так же в деревья с parent links. Как и в обобщенные графы владения с циклами. Мы теперь что, отменим все такие структуры данных? Этак слишком много отменять придется. Так и до потери полноты по Тьюрингу недалеко.

Для 100000+ периодических таймеров просто делается heap с абсолютным временем срабатывания. А дальше, на каждом тике планировщика выбираем topN таймеров, которые «созрели». И всё, не надо никаких «массивов». У них асимптотика на удаление таймера будет очень плохая, если делать всё одним массивом.

У массивов хорошее линейное чтение, но как раз в этом случае оно вообще ни при чем. Тут доминировать будет время, затраченное в обработчике таймера. heap и topN решают.

Таких структур хорошо накидать побольше и поконкретнее.

У меня постепенно созревает представление, как с ними работать, сохранив идеи раста. Понятно, что это будет другой язык, rust done right.

rust done right.

Golang?))

ты смеешься что ли? где в голанге хоть что-то о владении и лайфтаймах?

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

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

Но, как правило, за успехами ЯП стоит та или иная сила.

Кхм.

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

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

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

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

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

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

а еще, напомню, и таймеры для того, чтобы завершить задачу по таймауту; и какая тебе разница — завершится она по таймауту через 5с или 7с ?

а еще, напомню, и таймеры для того, чтобы завершить задачу по таймауту; и какая тебе разница — завершится она по таймауту через 5с или 7с ?

если надо через 5с и завершай через 5с. 5 сек - очень длинный таймаут(если тик - 1 мс = раз в 5 тыщ тиков) и такие события относительно редкие для данной реализации. проблемы там если таймаут - несколько тиков и тыщи таймеров. но это не ваш случай.

5 сек - очень длинный таймаут

5 с это вполне обычный таймаут при доставании чего-то через интернет

5 с это вполне обычный таймаут при доставании чего-то через интернет

а я разве против? у меня самого такие, если что.

Какое здесь количество экспертов по таймерам! Я уж лучше помолчу.

тогда ответь на изначальный вопрос: если у тебя таймаут 5с, а таймер активировался через 7с — ты тогда с ножом и пистолетом побежишь искать автора библиотеки таймеров, или скажешь «нормально»?