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

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

Весьма ценное замечание, хотя и возможно неточное.

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

Бремя доказательства тезиса о том, что «вектора всегда лучше списков» – на тебе. Это твой тезис.

Хрюндель khrundel дал неформальное доказательство этого тезиса, но ты видимо не заметил его в его простынях.

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

Тут бы хорошо терминологию согласовать.

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

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

Вот так и получаются мифы о полезности списков в RT. Метод «Каша из топора». Сначала берём список, потому что «гарантированно O(1) при вставке в начало, а нам ничего другого и не нужно». Потом начинаем не вписываться, переписываем список под свой, без аллокации, с пулами. Потом попадаем на случай когда пул кончается, чешем репу, обнаруживаем что иногда данные можно не добавлять, если места нет, или можно быстро освободить с другого конца, они уже неактуальны и вряд ли понадобятся. В итоге получаем рабочую релизацию. А то, что при текущем подходе вместо списка работал бы обычный, даже не реаллоцируемый массив, как бы уже зачем готовое переписывать?

Ты сравниваешь яблоки с апельсинами, т.е. структуру с O(1) в худшем случае со структурой с амортизированным O(1) и худшим O(N), тестируя при этом не сам контейнер, а malloc().

У последних задержки высокие, и мы все имеем неприятность с ними бороться в виде задержек поколенческой сборки мусора. Там ведь тоже стоимость выделения и высвобождения памяти амортизированное O(1).

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

Сначала берём список, потому что «гарантированно O(1) при вставке в начало, а нам ничего другого и не нужно».

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

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

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

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

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

В твоем случае (2*2 = 5) можно затребовать у него его аксиоматику натуральных чисел и его правила вывода (пусть даже неформально) и затем найти неверную аксиому или правило вывода.

В частности, он под вектором понимает в том числе и дерево (в т.ч. из векторов), которое полностью описывается владеющими ссылками.

Тогда совсем не понятен его тезис, что «списки не нужны» (см выше парой постов). Дерево – это список, только не линейный. И разница тут в том, что отличие обычного линейного списка от линейного списка векторов в том, что в первом случае у нас вектор длины 1. Т.е. добавляется еще один настраиваемый параметр – размер «чанка».

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

(обойдемся без бенчмарков :)

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

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

Дерево – это список, только не линейный.

Сколько раз мне написать, что у вас с ним разная терминология? (это уже 2-й раз)

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

В общем, подменить линейный список массивом ты можешь, если речь идет только о добавлении в начало/конец контейнера,

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

То, что он по существу прав, я понимаю.

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

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

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

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

Мои возражения к его аргументам направлены на то, чтобы (более) четко определить границу «ненужности». И тут дело будет не только в терминологии, но еще и в самой логике.

В деке с дырками дырки как будут заполняться?

Имеются 3 способа, вроде как удобные для раста, и 4-й, неудобный.

1. Игнорировать дырки

2. В дополнение к п.1 время от времени собирать дырки (этакий локальный GC).

3. Порезать дек на несколько (с помощью владеющих указателей) и собирать дырки там с помощью п. 1 и 2.

4. Порезать дек на несколько (с помощью произвольных указателей) и собирать дырки там с помощью п. 1, 2 и 3.

Прав, если говорить о том, что «в общем случае» гибридные дизайны лучше классических. Т.е. дизайнить физическую раскладку данных памяти нужно так, чтобы минимизировать случайные переходы, пусть и ценой большего физического объема вычислений (стоимость случайного перехода – 50-300 тактов процессора).

Я всем этим каждый день (после основной работы) занимаюсь.

Но, кроме общих, есть еще и частные случаи. И они вовсе не обязательно определяются алгоритмом. А еще и (это уже подсказка экспертам) – объемом данных и общим паатерном доступа (х). Сейчас уже довольно большие и быстрые L2/L3. Интенсивно эксплуатируемая структура данных, типа очереди задач, будет с высокой вероятностью плотно сидеть в кэше.

(х) Именно поэтому, микробенчмарки типа того, что использовали мы с сабжем, вообще говоря, бесполезны. Они не создают реалистичного паттерна. Поэтому-то я и намерял всего 6-26 нс задержки в DDR.

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

В его Полном Собрании Сочинений ориентироваться сложно, но мне так кажется, что он об этом не говорил.

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

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

И это только первый, самый очевидный вариант. А их еще несколько.

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

UPDATE: особенно если в рантайме можно менять числовые параметры гибридизации.

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

С++ тут в полном пролете.

Ну, не совсем. В compile-time C++ тут очень хорош. Шаблонизированные POD-типы позволяют раскладывать данные по памяти очень тонко. А вот чтобы такого эффекта добиться в рантайме как раз и нужен динамический компилятор С++.

Ну, не совсем. В compile-time C++ тут очень хорош. Шаблонизированные POD-типы позволяют раскладывать данные по памяти очень тонко.

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

Еще пример скрипа на физическом уровне: char* вместо условного byte* для сырой памяти. И емнип определение (т.е. typedef, у плюсов это каждой бочке затычка) int8_t через char выливалось в неожиданные баги (или неожиданное отсутствие оптимизации) в этом случае.

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

Я вот очень долго с тобой общался на эту тему и долго тебя не понимал из-за отсутствия конкретных примеров и странного, по-моему, подхода у тебя. По-моему, тебе не компилятор там нужен, тебе нужна partial specialization исполняемого кода в рантайме. Почти что jit.

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

Ты сравниваешь яблоки с апельсинами, т.е. структуру с O(1) в худшем случае со структурой с амортизированным O(1) и худшим O(N), тестируя при этом не сам контейнер, а malloc().

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

Так и тут с заполнением, если ты готов выдать списку фору в виде быстрого аллокатора на пуле, ну ок, дай тогда такую же фору вектору с преаллокацией нужного размера. Или вообще сделай пул векторов. Тогда он будет вставлять по O(1) и вообще любую реализацию списков порвёт. Если не готов - учитывай и стоимость аллокации. Без неё списков не бывает.

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

Ну вот ты меня правильно понимаешь.

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

Кстати, дарю цифры для сносок: ⁽⁰¹²³⁴⁵⁶⁷⁸⁹⁾

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

Вот тут твоя ошибка похоже, хотя надо бенчить.

Поиск не нужен в случае «элементу самому (асинхронно?) расхотелось быть в середине списка, и захотелось удалиться оттуда и стать в начало».

Это проблемы легаси. Я думал, ты скажешь про проблему алиасинга и оптимизатор, но с С++17, когда появился std::launder<>, её порешали на уровне стандарта. А до этого, да, пользовались хаками. Я ориентируюсь на современное состояние языка.

Логический уровень от физического неплохо отделяется через ZCO. Хотелось бы еще иметь метапрограммирование уровня AST, чтобы проще было преобразовывать уровни, но это всё дела будущего.

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

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

Почти что jit.

Это просто обобщение. В СУБД это всё уже давно, там мы на каждый запрос можем создавать по индексу. И платить за это, ессно, так как тут нет ничего бесплатного. И там тоже JIT, и даже ML (ну, типа, когда оптимальная структура b-tree аппроксимируется нейросетями).

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

Для меня это не странно, у меня похожие склонности.

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

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

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

И там тоже JIT, и даже ML (ну, типа, когда оптимальная структура b-tree аппроксимируется нейросетями).

Как я не люблю, когда какая-то обезьяна (я про ML) за меня че-то решает.

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

ML

(Продолжаю возмущаться) мне иногда нужен императивный SQL. То есть сделай вот именно такие циклы, и не лезь со своими идиотскими оптимизациями.

В случае ETL это достаточно часто так, поскольку:
1. я сам уже прилично данные изучил
2. цена ошибки может быть 100х по времени
3. я проверил свой execution plan на выборке или даже на прошлых прогонах.

Какой-нить приличный язык есть на эту тему?

Давай так…

Я согласен с тобой, что в тех случаях, когда необходимо интенсивное линейное чтение, то выбор в пользу std::vector<> будет оправдан по результатам бенчмарков, даже если иногда нужна «вставка в середину» вектора.

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

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

То же самое касается и LinkedHashMap.

Скажем так, структуры данных требуют другого типа/формата мышления, так как относятся к другому классу описательной сложности. Там кобинаторика «во все поля». Чем проще (в смысле схемы) наши структуры данных, тем лучше, даже если это приводит к некоторому проседанию по производительности. Потому что там чуть что, и ты закопался в комбинаторном взрыве сложности взаимодействия множества степеней свободы элементов данных.

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

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

Ты хочешь сказать, что у тебя сильно больше 1М разумных вариантов на структуру?

Какой-нить приличный язык есть на эту тему?

Всё, что тебе дает dataflow-граф в явном виде))

Всё, что тебе дает dataflow-граф в явном виде))

Это разве то, что я прошу? Я прошу похожее на SQL с явно заданным execution plan.

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

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

На самом деле это именно «адаптация по частотам».

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

А в случае «адаптации по частотам» аспирант (или даже студент) сможет объяснить, даже не зная самих частот. А тем более — зная.

Я согласен с тобой, что в тех случаях, когда необходимо интенсивное линейное чтение, то выбор в пользу std::vector<> будет оправдан по результатам бенчмарков, даже если иногда нужна «вставка в середину» вектора.

Или если линейное чтение вообще не нужно, и мы можем потерпеть 70% вектора пустым.

Не суть. Используй методы, которые дают интерпретируемость модели.

И эти методы — это точно не нейросетка.

UPDATE: точно не нейросетка в рантайме (в пре-компайл-тайме она все же может дать интерпретируемую модель)

Не суть. Я же говорю, если хочется заниматься структурами данных, то нужна «матчасть». Это, в первую очередь, тервер. А лучше – AIT. Теория позволяет семплить эффективные дизайны.

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

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

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

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

Я кстати говорил, что *обоснованные* претензии к расту найти не так то просто.

Во-первых, когда пробка рассосётся, тебе нужно будет сжать твои деки, или у тебя утечка памяти. Кроме того, ты будешь обсчитывать все перекрёстки, даже если на них никакие машины не пытаются встроиться. В-третьих, ЕМНИП я приводил это как пример полезности курсоров. По сути дела, ты и впилил курсоры в своё решение на массиве и заплатил за это цену, которую ты пытался изобразить отсутствующей «маленький move» или что-то там в этом роде. Однако в реальности она равна O(N) на каждом шаге, если считать самый простой случай, когда один перекрёсток на 100 машин, допустим. Но допустим, ты частично отбился, но не за счёт разумности твоей идеи, а за счёт того, что моделирование взаимодействия объектов по идее это N^2 от количества объектов, т.к. все объекты взаимодействуют со всеми. На этом фоне сложность работы даже с массивом может потеряться.

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

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

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

И второе, что я настаиваю: LRU-кэша может оказаться недостаточно для развенчивания расторелигии.

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

У всех разные цели.

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

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

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

Гарантированное время зависит не от доли дырок, а от максимального расстояния между дырками. Если я правильно понимаю, как работает ДДР4, то она читает кэшлиниями, и за 26 мс (за которые читались рандомные указатели) гарантированно прочитает 64 байта даже при самых худших условиях. А при хороших может прочитать и 512 байт.

Т.е. дырки в 60 байт при объекте (это скорее всего указатель) в 4 байта нас устроят.

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

так это работать надо, wget | grep unsafe там или что, а не на форуме трындеть

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

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