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

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

Всё с этим нормально. Таймеры ничего не гарантируют из того, что от них просят. Таймер срабатывает не раньше запрашиваемого времени. А уж когда именно – как планировщик решит. Если в системе 100К таймеров, и все они срабатывают одномоментно, то будут сильные «сдвиги».

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

Задача про таймеры не была сформулирована полностью в одном месте, соответственно и обсуждение в стиле «кто в лес, кто по дрова».

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

за такое кладут на рельсы или скидывают с крыши. потому что если вы заказали 5, а вдруг получили 7… значит вы куда-то опоздали на две секунды и поезд ушел.

значит вы куда-то опоздали на две секунды

да

и поезд ушел

нет

вот curl например на практике отваливается по 15000 мс таймауту с точностью 1 мс; это нужно кому-то, или точности 50% хватило бы?

вот curl например на практике отваливается по таймауту с точностью 1 мс; это нужно кому-то, или точности 50% хватило бы?

вот полетаешь на самолете, где точность временных интервалов в ПО, +- 50 процентов. да ты там на высоте обкакаешься, если взлетишь, а представляешь как садиться с точностью в 2 секунды? пролетишь мимо полосы и сядешь в гору.

я не предлагаю вот такие спецтаймеры использовать везде

и добавлю: на некоторых ОС для устранения побочных каналов передачи информации время невозможно узнать точнее, чем с точностью 1 секунда

Ну реалтайм же. Там аппаратные таймеры, и не стотыщ, а несколько.

Да ладно, посмотри сколько языков создано одиночками, а сколько языков сляпали за 2 недели на коленке. У одиночек проблемы начинаются на этапе популяризации, а не на этапе создания. Идеи можно брать из одного языка и перетаскивать в другой, для этого необязательно быть учёным. Изучить 5-10-20 языков тоже многим программистам под силу. Чтобы поддерживать язык, нужна команда от 1 до 20 человек где-то, в зависимости от его сложности. А теперь сравниваем с штатом ИТ-компании средней руки.

вот полетаешь на самолете, где точность временных интервалов в ПО, +- 50 процентов

и что такого? вот в геймдеве например «ой, нас вызвали через 500 мс вместо 50 мс? ничего страшного, пропускаем 10 кадров и рисуем сразу 11-й»

пора взрослеть, а ты все в игрушки играешь, реальная жизнь это вам не покер!

как будто это сильно другое

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

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

за вождение пластмассовых самосвалов денег не платят!

епрст, как ты меня расстроил!

а правда не платят? на соревнованиях на скорость радиоуправляемых моделей, например?

Там, кстати, реалтаймовые таймеры нужны будут))

а правда не платят? на соревнованиях на скорость радиоуправляемых моделей, например?

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

Представляю, если бы так работал ДВС или другая механика. Клапаны опустятся, поршень поднимется. А будет ли их танец синхронен или они встретятся в полёте - то мы не гарантируем.

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

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

Только не блокировки, а атомики. RC – вполне нормальная вещь, а от потоков, как таковых, нужно избавляться в сторону воркеров с мессаджингом и ФСД/ПСД между ними. Идея совсем разнести параллелизм по разным процессам плохая, так как IPC – дорогая штука. И делать ПСД в разделяемой памяти специально для параллелизма процессов люди могут просто не захотеть (как я, например).

Т.е. локальные для потока данные используют RC, разделяемые между потоками объекты – ARC. Последние вряд ли будут интенсивно создаваться/высвобождаться. Т.е. счетчики ссылок будут большую часть времени отдыхать. И всем хорошо.

Только не блокировки, а атомики.

А разве атомики - это не частный случай блокировок? Что такое ФСД/ПСД?

нужно избавляться в сторону воркеров с мессаджингом

Думаю, это зависит от задачи.

Нет. Другой класс примитива синхронизации. Атомики – lock-free, т.е. гарантии прогресса другие. Ну и они быстрее где-то на порядок, обычно.

ПСД/ФСД – персистентная/функциональная структуры данных. У них wait-free режим, и их можно свободно расшаривать между потоками. «Есть нюансы», но это основное направление, если хочется иметь динамические разделяемые данные с богатой семантикой. На Lock-free структурах данных много не вытянешь. Там есть несколько удачных дизайнов, но чем дальше в лес, тем сложность разработки – в небеса, а производительность – в пол.

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

По мнению SO - всё не так однозначно с атомиками. А если заглянуть под капот, то там найдётся цена промаха мимо кеша плюс блокировка памяти для других процессов

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

ПСД/ФСД – персистентная/функциональная структуры данных

Понял, ну это тоже не панацея, я бы сказал. Мне почему-то кажется, что это просто очередная мода. Хотя плюсы вполне понятны.

По мнению SO - всё не так однозначно с атомиками. А если заглянуть под капот, то там найдётся цена промаха мимо кеша плюс блокировка памяти для других процессов

И при всём при том, атомики значительно быстрее, хотя это зависит и от ОС, и от процессора.

Мне почему-то кажется, что это просто очередная мода.

Мода только-только еле-еле начинается. Так что никакого хайпа. И, разумеется, оно – не панацея. Просто лучше в общем случае ничего пока нет. У ПСД полный wait-free по доступу к данным, читатели и писатели не мешают друг-другу, snapshot isolation прямо из коробки. Практически любую прикладную модель данных можно сконвертировать в ПСД (через прямое и промежуточное представление в виде деревьев).

Есть минусы.

1. Основной минус, что это – деревья. Т.е. добавляется O(Log N) на все точечные операции. Хэш-таблицу персистентной не сделать.

2. Каждое обновление создает новую версию структуры, и несколько параллельных писателей не могут никак пересечься, если эти версии не сливать (merge), как ветки сливаются в git. Слияние версий в ПСД – отдельная тема. Универсального алгоритма нет, хотя есть широкий класс структур (CRDT), для которых автоматическое слияние определено в общем случае.

Вот есть проект РСУБД, которая, на сколько я сейчас знаю, имеет именно персистентный движок под капотом.

Мода только-только еле-еле начинается. Так что никакого хайпа.

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

Вот есть проект РСУБД,

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

Слияние версий в ПСД – отдельная тема. Универсального алгоритма нет, хотя есть широкий класс структур (CRDT), для которых автоматическое слияние определено в общем случае.

Выглядит обнадёживающим. Бросила гребень - вырос лес.

И при всём при том, атомики значительно быстрее, хотя это зависит и от ОС, и от процессора.

Угу, и там же написано, что на тех железках, где их нет, их делают через мьютексы.

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

Хэш-таблицу персистентной не сделать

Годнота, мы почти в безопасности.

Странно, мне казалось ясным, что это путь, уже лет 5-10 назад.

Многим это казалось ясным давным-давно, но волны хайпа это не запускало. Кто-то что-то тихо пилил, и вот, напилил. Опять же, очень тихо.

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

MVCC в версионщиках делается по совсем другой технологии, и тому есть технические причины. Во-первых, в версионщиках может быть только одна ветка истории (частичная персистентность), потому что там используются не деревья, а списки, сортированные по txnid. Во-вторых, CoW исторически очень плохо дружил с HDD из-за вызываемой копированием фрагментации, поэтому ПСД для внешней памяти не делали. На SSD ситуация на много лучше. И там внутри вообще LFS (тоже вариант CoW/ПСД). В общем, аналога Git на классической MVCC РСУБД не получить никак (без существенной потери в скорости и необходимости переписывать запросы).

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

Верное замечание. Но для случая ПСД в RAM, отлично работает обычный ARC (несколько параллельных писателей) или даже просто RC (несколько линеаризованных писателей). Т.е. это, да, не совсем wait-free. Тем более, что история обычно огораживается блокировкой, берущейся на короткое время. Но в блочных ПСД атомиков мало, атомики быстры, и нарваться на конфликт, реально снижающий производительность – это надо очень постараться. Примерно, как поймать теоретический худший случай для жэш-таблицы.

Годнота, мы почти в безопасности.

Вся многопоточная аналитика проходит мимо вас :)

Блокировки не композиционны. Всё, что остается – это STM. А если ты «за STM», то от них пара шагов до ПСД. STM гораздо более низкоуровневая и семантически ограниченная. Но работает по тому же принципу.

Во-первых, в версионщиках может быть только одна ветка истории

Не понял, в Оракле реально в каждой транзации существует свой мир. Мир изолируется от прочих миров на момент начала транзакции и до конца транзакции он не видит иных миров и существует как бы один. С ним я давно не работал, правда, могу наврать. В Firebird миры не совсем изолированы, например, конфликты обновлений могут сразу проявиться, до фиксации. В обоих случаях, в момент фиксации транзакции СУБД пытается слить версии. При конфликте уже не помню что, то ли одну транзакцию нужно убить, то ли можно поправить. Чем не гит? Тем, что есть выделенная ветка master и нельзя ветвить ветви. Но это уже частности, всё равно в один момент существует несколько различных версий одной и той же таблицы.

Вся многопоточная аналитика проходит мимо вас :)

Не понял, но звучит угрожающе.

Блокировки не композиционны.

Бог ещё хранит нас.

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

Эта параллельность (свой мир) только для самой последней версии на момент старта транзакции. Взять и начать изменять произвольную версию, т.е. отбранчеваться от неё, в MVCC СУБД нельзя. Базовые структуры данных не позволят эффективно разрешать версии. Это можно у них делать быстро (за логарифмическое время) для линейной истории, но не для древовидной. Тогда как в ПСД разрешение делается за логарифмическое время (от количества версий) для любой формы DAG истории.

MVCC СУБД, в целом, хранит промежуточные версии записей только пока транзакция активна. Потом они вычищаются сборщиком мусора. Или персистируются через SAVEPOINT.

Практически любую прикладную модель данных можно сконвертировать в ПСД (через прямое и промежуточное представление в виде деревьев).

где берется память для копий в этом псд? если из кучи - там мьютекс во всей своей красе…или уже сделали неблокирующий хипменеджер?

jemalloc чем-то принципиально не устраивает?

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

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

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

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

то они будут специфичны для каждой структуры

Ну так какие проблемы сделать его специфичным для, например, блочной ПСД с размером блока 4К? Общая блочная структура самой ПСД известна – это, например, персистентное b+tree (без sibling links).

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

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

Там еще NUMA-aware, до кучи)) Так что проблем много, но они не специфичны именно для ПСД. Важный момент в том, что ПСД при доступе к, собственно, данным обеспечивают wait-free, и там синхронизация уже не нужна. После того, как мы сделали общий каркас многопоточной ПСД (фреймворк), все частные дизайны уже ничего ни про какую многопоточность уже не знают.

Куда большую проблему представляет дорогой merge. Распараллеливание писателей в ПСД будет ограничиваться, в первую очередь, именно в это месте, а не на аллокаторе. Если нужно поведение как в СУБД (транзакции над линейной историей версий), то, скорее всего, придется линеаризовывать писателей (читатели при этом параллельные и не блокирующиеся). Аналитические и гибридные СУБД одобрят.

Кто сказал что не нужен?

А кто сказал, что нужен?

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

Раз он не нужен, обошел, составил список нод, сделал free.

Ты написал, что графы надо делать на указателях.

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

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

Если ты бы не был упорытышем, было бы понятно, что претензия к твоему божку в том, что оно делает это одним только методом. Хочешь ты того, не хочешь, тебя поставили в стойло и говорят - делай вот так и никак иначе. Удобство и адкеватность такого решения, походу, никого, включая тебя, в вашей секте не волнует. И претензия к тебе не из-за графов/списков/етц, а из-за мудатской позиции «мы сказали делать надо только вот так, делайте вот так, а все кто против - априори дебилы», что, собственно своими высерами ты успешно демонстрируешь на протяжении всего треда.
С теми же графами, ты рассматриваешь случаи, когда тебе удобно иметь его целиком в векторе, случаев, когда тебе это граф не всрётся после удаления целой ветки для тебя нет, как и нет проблем, которые за этим последует с великами, которыми ты будешь героически решать тобой же созданный геморр. Причём великами, которые уже давно существуют в язычках с гц, которые ты поливаешь говном, но сам предлагаешь делать на них косплей, шизик.

не несло дичь о страшно дорогих растущих массивов

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

Если возможности обойтись без списка нет, нужно взять паузу, подумать пару часиков, и придумать как всё-таки обойтись без списка.
Я знаю 2:
Возможно бывают и другие, но там надо думать.

Вот в этом твоя проблема. Если ты не знаешь - не значит, что их нет и что они не нужны. А «не юзать ссылочные структуры, юзать любые костыли и избегать их любым способом» - позиция барана.

Дерево можно упаковать в массив

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

Так что ты снова обосрался, поздравляю.

Лол. Если от всех воняет говном, может обосрался ты?

Просто штатный аллокатор в Linux, да, глобально огорожен.

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

А кто сказал, что нужен?

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

Раз он не нужен, обошел, составил список нод, сделал free.

В этом решении прекрасно всё.

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

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

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

Где, лол. Это твоя позиция все делать исключительно через ту жопу, которую указал твой гуру.

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

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

Ну вот, начал сдавать назад. Ещё раз привожу цитату: «Графы. В графы руст тоже не умеет, надо костылить его через вектор?». Опять из контекста выдернули и ты имел в виду что-то иное?

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

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

С теми же графами, ты рассматриваешь случаи, когда тебе удобно иметь его целиком в векторе, случаев, когда тебе это граф не всрётся после удаления целой ветки для тебя нет, как и нет проблем

Чувак, графы всегда должны быть целиком. Даже на языке с GC, где нет вот всей этой мутотени с освобождением. Просто тупо понадобится тебе в отладчике посмотреть что не так с вершинам, выбывшими из графа. Да и нет никакой проблемы в расте сделать граф через жопу, как ты хочешь. Можно колхозить на поинтерах в unsafe. Можно в safe, через Rc<RefCell<Vertex>>. Оба варианта убитые, но можно. В ансейф вообще 1 в 1 как C. В варианте с Rc<RefCell<Vertex>> будет почти как ты описал, будешь пихать указатели на потерявшие связность вершины в контейнер, разница только в том, что вместо вызова free в цикле у тебя будет пробег по контейнеру и удаление всех рёбер из каждой вершины(чтоб отцепившиеся подграфы циклическими ссылками утечку памяти не создали) + потом удаление самого контейнера.

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

«Прочей срани» не было. Было про разрастание и «рандомное перестроение». Про перестроение я ответил, приведя в пример quicksort. Ну а насчёт разрастания - тебя никто за язык не тянул, сам эту тупость написал.

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

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

А «не юзать ссылочные структуры, юзать любые костыли и избегать их любым способом» - позиция барана.

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

Лол. Если от всех воняет говном, может обосрался ты?

Не от всех, а от 2-3х человек в теме. В особой теме, срачевой. В такой теме вполне вероятна ситуация, что 3 одновременно обосрутся, почему бы и нет.

По существу есть что возразить?

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

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

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

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

Меня поражает твоя упоротость. Ты написал очевидную глупость. Тебе разжевали.

А, так ты шиз и вас там много. С этого надо было начинать.

Не через жопу и не гуру. Все нормальные люди моделируют графы массивами.

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

Опять из контекста выдернули и ты имел в виду что-то иное?

Очевидно, что граф - это частный случай ссылочной структуры. Да, таки ты выдернул из контекста, как всегда.

Понимаю твою боль.

Не «понимаю», а «понимаем», не забывай своих друзей шизов.

Чувак, графы всегда должны быть целиком.

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

Просто тупо понадобится тебе в отладчике посмотреть

А если не понадобится, то что? Будешь на всякий случай копить мусор? Ты точно шиз. С помойки домой не носишь?

Оба варианта убитые, но можно.

А в каком-то случае вариант с массивами будет не вариант. И?

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

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

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

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

Вот ты - баран. Тупой как пробка

Лол. Ну, что, извинения за барана будут?

В такой теме вполне вероятна ситуация, что 3 одновременно обосрутся, почему бы и нет.

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

Я ж не религиозный фанатик, чтобы их не использовать вообще.

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

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

Могу, представляешь, даже граф сделать на массивах. И стек.

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

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

DOM - это дерево. Да, это частный случай графа, но и одна вершина без рёбер тоже частный случай графа. Ты мне обещал не какие-то смешные вырожденные случаи, а самый настоящий граф, об этом и была речь. Если тебе нужно было дерево - надо было так и писать, сделать его на расте гораздо проще чем более обобщённый граф. Я даже согласился ради смеха на связный орграф, в котором есть корневая вершина, так что в случае потери связности понятно, какую половину графа надо грохнуть. Более того, я тебе писал о вершинах, доступных по более чем одному пути, и ты не возражал на это и продолжал свистеть про то что рёбер достаточно. Так что давай дурачка не будешь включать и рассказывай, как ты собрался грохать вершину, которая 1) может иметь дуги на другие вершины и 2) может сама иметь несколько входящих дуг и может ссылаться (в т.ч. и опосредовано) на какую-то вершину, доступную не только через удаляемую.

А если не понадобится, то что? Будешь на всякий случай копить мусор?

LOL. Вот ты думаешь что не понадобится. А потом во время отладки понадобилось. Что будешь делать? Переписывать реализацию графа?

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

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

Лол. Ну, что, извинения за барана будут?

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

Ты всё с ног на голову ставишь. Современные CPU не такие уж и медленные при случайном обращении к памяти. Задержки там в среднем 20нс примерно, так как иерархия кэшей и предвыборка отрабатывают. Чтобы твои массивы давали значительное преимущество при чтении, они должны быть довольно большими. А чем больше массив, тем дольше произвольная вставка в него. Чтобы апдейты не падали в пол, массивы должны быть довольно маленькими, всего несколько строк кэша. Скажем, 256 байт. После чего процессор уже делает лишнюю работу, сканируя линейные диапазоны в поисках данных. Вот и все твои массивы.

Я когда-то давным-давно, еще на core 2 duo, тестировал поиск в std::set<int64_t> против PakedTree<int64_t>. Последнее – это сбалансированное N-арное дерево префиксных сумм, упакованное в массив. Для 16-арного дерева размер узла составляет 16*8=128 байт или 2 строки кэша L2. Там на графике видно, что пока данные умещаются в L1, std::set<> уверенно лидирует по чтению (contains(key)), в разы. PackedTree просто делает слишком много работы. В L2 производительность выравнивается, а в RAM PackedTree уже вырывается вперед, опять же, «в разы». И там можно увидеть, что sweet spot – это 32-арное дерево (256 байт). Потом производительность падает, так как количество работы, которую нужно делать для сканирования узла уже больше, чем задержки в RAM.

PackedTree – дерево статическое, полностью упакованное в массив. Если сделать узлы «ссылками на массивы», то ничего бы существенно не поменялось в плане чтения. Зато дерево бы стало динамическим. Но вот скорость вставки была бы существенно ниже, чем в std::set<> (на core 2 duo).

Кстати, насчет работы на Rust. Свалилась мне сейчас в ящик вот такая ваканися. Fluvio. Стриминговая платформа на Rust. OSS, ASLv2. На сколько я вижу, Rust начинает тут теснить Golang, как язык для обработки данных. Java в этой области уже давно в стагнации, и заслуженно.

так как иерархия кэшей и предвыборка отрабатывают.

Это невозможно. Чтоб префетчнуть 2ю ноду, надо знать значение указателя в 1й ноде, а она ещё не подгрузилась.

Я когда-то давным-давно, еще на core 2 duo, тестировал поиск в std::set<int64_t> против PakedTree<int64_t>.

Искал что такое, не нашёл. В общем по твоему описанию это b-tree которому ноды выделяются в массиве? В общем ты доказал, что массив лучше чем теоретическое O(logN).

Я ещё раз кину ссылку: https://www.youtube.com/watch?v=M2fKMP47slQ

1. Линейный поиск в несортированном массиве круче любых реализаций до 40 айтемов, круче чем std::map где-то примерно до 12 айтемов, а 12 айтемов состоящих из пары 32битных значений - это 96 байт, кэш-строка.

2. boost::flat_map (просто отсортированный массив с бинарным поиском) ведёт себя получше чем std::map но не то что бы сильно. При этом заметны несколько особых точек, когда время сильно уходит вверх, это 400 айтемов (1 килобайт), 800000 айтемов (6 мб).

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

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

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

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

struct DLLNode {

int nextid;
int previd;
int value;

}

struct DoubleLinkedList {

DLLNode*	nodes;

DoubleLinkedList(int size):size(){
	links = malloc (size * sizeof(DLLNode*));
	nodes = malloc (size * sizeof(DLLNode));

	nodes[0].nextid = 1;
	nodes[0].previd = size-1;
	links[0] = &nodes[0];
	for(int i=1; i<(size-1); ++i) {
		nodes[i].nextid = i + 1;
		nodes[i].previd = i - 1;
		nodes[i].value  = 0;
		links[i] = &nodes[i];
	}
	nodes[size-1].nextid = 1;
	nodes[size-1].previd = size - 2;
	links[size-1] = &nodes[size-1];

~DoubleLinkedList(){
	free(links);
	free(nodes);
}

private

static DLLNode* links;
int size;

};

На самом деле links вообще не обязателен. Достаточно индекса.

Индекс хорош тем, что элементарно проверяется на границы допустимого. Адрес сам по себе не имеет четких границ.

P.S. Кстати вопрос. При попытке найти обычный динамический массив в RUST во первых выскакивает, что массив обязан быть с фиксированным во время компиляции числом элементов, что есть нонсенс само по себе. Но так же выдают вариант использования Вектора, в который надо добавлять значения по одному, вместо обычной адресовки к любому элементу. Это такая мода или какой в этом глубокий смысл? Язык в котором нет массивов переменной длины по поему не имеет право на существование. В нормальных языках есть многомерные массивы такого же поведения. К С тут претензий нет. Но к RUST точно есть. Это обязано быть частью языка, а не каким-то там crate-ом.

Это во многом объясняет, как хорошо работают префетчи. В теории, в связанной структуре типа списка, чего-то напрефетчить невозможно.

Ты сильно недооцениваешь возможности иерархии памяти. R9 5950X, DDR4 3600 на штатных таймингах. Читаем большой массив по псевдослучайным индексам. В теории тут префетчер тоже ничего не может сделать, так как он вообще работает только в пределах одной страницы.

#include <memoria/core/tools/random.hpp>
#include <memoria/core/tools/time.hpp>

#include <memoria/core/strings/format.hpp>

using namespace memoria;

int main(void) 
{
    size_t buf_size = 1024*1024*1024ull; // 8GB
    size_t idx_size = buf_size / 16;

    int64_t t0, t1;
    volatile uint64_t sum{};

    auto tx = getTimeInNanos();
    {
        std::vector<uint64_t> buffer_(buf_size);
        std::vector<uint64_t> indices_(idx_size);

        for (auto& v: buffer_) {
            v = getBIRandomG(1000);
        }

        for (auto& v: indices_) {
            v = getBIRandomG(buf_size);
        }

        t0 = getTimeInNanos();
        for (uint64_t ii: indices_) {
            sum += buffer_[ii];
        }
        t1 = getTimeInNanos();
    }
    auto tz = getTimeInNanos();

    double ns_in_ms = 1000000;
    double time = t1 - t0;

    println("Done. {} ops in {:1.2f} ms, {:1.2f} ns/op", idx_size, time/ns_in_ms, time/idx_size);
    println("Setup time: {:1.2f} ms, total {:1.2f} ms, sum = {}", (t0 - tx)/ns_in_ms, (tz - tx)/ns_in_ms, sum);

    return 0;
}

Получаем:

time ./pseudo_latency 
Done. 67108864 ops in 462.98 ms, 6.90 ns/op
Setup time: 6378.55 ms, total 6991.18 ms, sum = 33516944502

real	0m6.993s
user	0m4.932s
sys	0m2.058s

7 ns на одно обращение к памяти, что примерно равно 30 тактам. Эффективная средняя задержка в 10 раз меньше, чем средняя задержка RAM.

Суть в чем? Суть в том, что производительность – штука ну очень сейчас контринтуитивная и зависит от распределения данных. Если иерархия памяти (на которую выделяется хренова туча кремния) сможет предсказать паттерн доступа к данным (как в случае выше), то производительность будет на порядок выше худшего случая. Фактор влияния распределения данных говорит о том, что бенчмаркать нужно IRL, а не на стенде.

Линейный поиск в несортированном массиве круче любых реализаций до 40 айтемов, круче чем std::map где-то примерно до 12 айтемов, а 12 айтемов состоящих из пары 32битных значений - это 96 байт, кэш-строка.

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

В общем, идея такая, что каждое обращение в память – это 30-300 тактов. И за это время процессор может выполнить 60-1000 операций. Этот вычислительный бюджет можно потратить на более эффективную кодировку данных в памяти, «помогающей» процессору в работе. И, несмотря на то, что процессор делает вроде бы значительно больше работы в пересчете не одну операцию алгоритма, итоговая производительность будет значительно выше «наивной реализации».