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

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

Если это специально не запретить, то может быть например что 7=3. Можно было неформально написать, что «равны те и только те объекты, которые равны по построению через 1 и next», но я это написал более формально.

А в случае действительных чисел равенство исключительно по построению не прокатывает, например 0.999999... = 1.000000...

может вам отдельный топик сделать -

доказать, что 2*2 = 4.
тег - "хочется странного". 

по спискам есть чонить?

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

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

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

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

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

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

у тебя явно должны быть приоритеты и/или скобки; стиль «2 + 3 * 4 равно 20» я отвергаю

Для этого и будет последний этап с синтаксическим анализатором через БНФ по науке. Для начального этапа - это лишнее, потому что подразумевает создание неявных временных переменных для результата скобок. Кроме того, в моём случае порядок вычисления един и для операторов, и для процедур. Всегда слева направо. Это ускоряет разработку (да и читаемость после привычки).

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

Дерево, например, или DAG.

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

У меня табы запрещены. Кому нравится 2 пробела, тот пусть делает себе язык с двумя пробелами. Мы же тут говорим о прототипе языка, либо о каком-то нишевом DSL-е.

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

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

(Что же касается отступов — то я за них, но для любителей можно оставить возможность дублировать отступы скобками.)

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

Дядя, тебе такие слова, как «слэнг», «жаргон» известны? Вот это (хип) оно.

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

«переключитЬся» - это слово в данном случае пишется с мягким знаком. Что сделатЬ? ПереключитЬся.

Но я боюсь Вы сдуетесь на первом же предложении.

Но ЗАПЯТАЯ я боюсь ЗАПЯТАЯ вы (с маленькой буквы, а не с большой, поскольку это не официальная переписка) сдуетесь на первом же предложении.

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

напишите СВОЙ нормальный

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

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

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

Мне надо было переписывать прототип с Питона на C++ стандарта 98. Я тогда замучался многие рутинные избыточные вещи делать, типа инициализации вектора через дополнительный массив. С тех пор многое улучшили в стандарте, а что не улучшили, то можно флагами компилятора вытянуть. Но всё равно, много ещё избыточного осталось для моих задач.

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

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

Ты спросил, какой тип данных может повлиять на результат. Обычно, под number crunching понимаются любые compute-интенсивные задачи (т.е. сложность выше, чем O(N)), куда так же, условно, входит и сортировка. В случае обработки линейных списков, сортировки и матричных операций доминирует линейный или регулярный паттерны доступа к памяти, которые кэши обрабатывают хорошо. Поэтому массив, как базовая структура данных, обычно предпочтителен.

В случае «числодробилки» на нерегулярных структурах (деревья, графы) всё может быть по другому.

когда массивы лучше: когда у вас изначально «табличная» организация данных.

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

ПыСы:

Поскольку den73, как говорит, поместил меня в игнор

Ещё один гвоздик в гроб его адекватности. В этом треде Вы выглядите как один из самых трезвомыслящих…

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

Всё верно. Мы идем от алгоритма и того паттерна доступа к памяти, который он создает. Дальше, подбираем раскладку данных по памяти (т.е. структуру данных) так, чтобы максимизировать производительность на заданной архитектуре памяти.

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

a-- вызвался побенчмаркать LRU-кэш со списком на chunked array. Очень интересно, какой дизайн у него в итоге получится, учитывая, что chunked array теряет одно из важных преимуществ списка – стабильность итераторов при обновлении контейнера.

В этом треде Вы выглядите как один из самых трезвомыслящих…

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

Я тут провел бенчмарк std::set<u64> против absl::btree_set<u64> на чтение при одинаковом размере датасета. Скоро опубликую график.

Просто я «ем» дизайны на основе массивов на завтрак, обед и ужин. А потом мне они еще и снятся.

Welcome to my world :)

Я тут провел бенчмарк std::set<u64>

Может не в тему, но мы тут намедни «серьёзно вляпались»: оказывается hasher в std::unordered_set/map возвращает size_t, что приводит к очень серьёзной просадке в 32bit при 64bit ключе. Хозяйке на заметку…

Скоро опубликую график.

a– вызвался побенчмаркать LRU-кэш со списком на chunked array.

Ждём с нетерпением (без сарказма).

std::set<uint64_t> против absl::btree_set<uint64_t>, R9 5950X DDR4-3600, всё штатное. Тестируется производительность операций чтения при случайном паттерне с включенным OoOE. Т.е. мы смотрим максимум того, на что способна структура данных на этом железе, а не одну только память.

std::set имеет высокую избыточность, расход памяти по данным RSS процесса на 1 элемент составляет примерно 48 байт. Для btree_set эта величина значительно лучше: 9.29. Т.е. при том же размере памяти, btree_set будет вмещать примерно в 5 раз больше полезных данных.

Тест делает создает дерево заданного размера (1KB, 2KB, 4… 1GB) и делает на нем 1M случайных поисков. Результаты приведены на графике.

Размеры кэшей: 64KB, 512KB, 32MB.

Видно, что std::set опережает btree_set пока данные хорошо помещаются в L1 и L2, и только где-то в начале L3 наступает «перелом»: btree_set начинает незначительно вырываться вперед. В RAM отрыв btree_set уже в приличных 1.8 раза. Фактор «больших кэшей», а они сейчас бодренько так растут, приводит к тому, что нам (при выборе базовой структуры данных) всегда нужно учитывать, где будут сидеть данные основное время работы. В этом состояло моё второе возражение на аргументы khrundel.

Исходники: benchmark_bree.cpp, becnhmark_stdset.cpp benchmark_common.hpp и gnuplot script.

Сделай пожалуйста лог. масштаб по вертикали, а то около нуля вообще ниче не видно.

UPDATE: глянул — у тебя данные прямо в скрипте. Тогда мне и самому легко, хотя по-моему и людям нужен именно лог.

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

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

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

std::set имеет высокую избыточность, расход памяти по данным RSS процесса на 1 элемент составляет примерно 48 байт.

Ой-ё-ёй. Так нельзя. Мы же оба понимаем что с этим можно бороться (custom allocators etc)? Overhead должен быть не больше 3х pointers per node.

Однозначно лог. картинка лучше твоей.

как бы пора уже в хидерах писать #pragma once, а не нагружать их сложносочиненными, якобы уникальными дефайнами. лет 20 уже это стало общей практикой. не?

Там при всём желании получается минимум 5х8 = 40 байт. Так что кастомный аллокатор погоды не сделает.

Так я только за! пруф

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

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

reset
set term svg enhanced size 880,460
set output 'BTree-Set.svg'
set title "absl::btree_-set<uint64_-t> vs std::set<uint64_-t> Random Read Performance,\n1 Million Random Reads"
set xlabel "Memory Block Size, Kb"
set ylabel "Performance, operations/sec\n\n"
set ytics format "%g"
set logscale x 2
set logscale y 2
set xtics 1, 4, 1048576
#set ytics 1e6, 2
set ytics 1e6, 1.25892541179416721042
set yrange[2e6:]
set format y '%5.3g'
set grid xtics ytics
set key top right
plot '-' title 'absl::btree_-set' w lp, '-' title 'std::set' w lp

Видно что при увеличении блока в 2 раза количество операций падает сначала на полдецибелла…

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

Видно что при увеличении блока в 2 раза количество операций падает сначала на полдецибелла, затем на 1 децибелл.

Счас дедушка_ау выйдет из леса и скажет, что в децибелле одна лишняя буковка. а в предложении нехватает запятой. зы. и даже двух.

Чет я когда писал, явно ощущал дискомфорт с количеством букв л.

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

Там при всём желании получается минимум 5х8 = 40 байт.

Я вижу 3x8. Откуда ещё 2 появляются?

a-- вызвался побенчмаркать LRU-кэш со списком на chunked array. Очень интересно, какой дизайн у него в итоге получится, учитывая, что chunked array теряет одно из важных преимуществ списка – стабильность итераторов при обновлении контейнера.

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

1. LRU крутит та же нитка, что часто обращается к элементам, или другая?

2. LRU владеет объектами или как? То есть может ли элемент удаляться из LRU по инициативе самого элемента (или владельца элемента), а не по инициативе крутильщика LRU.

3. Размер элемента (величиной до 8 байт или существенно больше?)

4. Где-то есть реалистичные тесты? Я вот что-то нарыл https://github.com/nitnelave/lru_cache

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

Sidenote: меня всегда возмущало 8 байт на указатель. Нежели нельзя 4 байта? или допустим 5?

Собственно про это я и хочу спросить всех (особенно ждущего bugfixer), чтобы лепить что-то приближенное к действительности.

Ваш покорный не верит в универсальность и микро-бенчмаркс. С реалистичными тестами - самая печалька: пока в прод не выпустите - не поймёте хорошо оно работает, или не очень. А вообще - начните с самого простого - single-threaded container с семантикой std::list, ну или близкий (мне даже очень интересно стало какие компромиссы Вы собрались делать).

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

Value and alignment сразу отбрасываем (как неизбежные потери). Для color можно «украсть» 1бит из parent ptr. Что я упускаю?

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

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

С цветом согласен. А почему value отбросили?

Sidenote: меня всегда возмущало 8 байт на указатель. Нежели нельзя 4 байта? или допустим 5?

размер указателя определяется разрядностью - если 32 бита - то 4 байта, если 64 бита - 8 байт и по другому нельзя, потому что адрес берется в регистр такой разрядности. и выровнено должно быть на такую границу.

видно что аист орудует в 64 битной модели.

В данном тесте можно и 4 байта, так как размер кучи – 1GiB, но это не принципиально. Пересечение графиков сместится влево немного.

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

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

single-threaded container с семантикой std::list,

Я бы не сказал что это самое простое, ну ладно.

Как понимать семантику списка? Что можно держать неограниченное количество итераторов на элементы списка, и расходы на поддержание их валидными приблизить к нулю? Мой компромисс — это «приблизить к 0» как «сделать примерно равным количеству вставок/удалений, а не количеству итераторов».

Когда тут раньше шла речь про очередь из таймеров, емнип там стояла именно такая задача — расходы на поддержание итераторов валидными желательно привести к 0 или сделать небольшими. Но там совсем не LRU, а очередь. И там мне ситуация понятна в том смысле, что ясно что от этой очереди хотят. А от LRU не ясно.

Просто забей. Потратишь кучу времени ни на что.

и по другому нельзя

речь конечно же идет о 5-байтовых адресах в 64-битной модели

да и 4 байта можно двигать на несколько бит и получить возможность адресовать, скажем, 16ГБ полезных данных

С цветом согласен. А почему value отбросили?

Я просто sizeof(value) «overhead’ом» не считаю - это Вы заплатите так или иначе.

Просто забей. Потратишь кучу времени ни на что.

Да я понимаю что на практике оно вряд ли нужно. Но интересно.

Если же ты по-прежнему думаешь, что LRU на списках нельзя ускорить — то тогда я принципиально попытаюсь.

Ну вот в случае std::set у нас будет 40 байт на узел, минимум. Против 48 намеренных не так уж много. Если хочется более компактного контейнера (цвет вынести в поинтер, указатели – 4-байтные и тп.), свой аллокатор, нужно тащить кастомное дерево. Что я делать не хочу. Не в этом цель теста. А во том, чтобы показать, что точка перелома графиков лежит в L3 для данного процессора. Это значит, что тщательно придуманный «дизайн на массивах» может IRL слить просто потому, что данные сидели в кэше. А разработчик этого не учел.

Может и можно, но зачем? Дизайн усложняется многократно. А это потом еще отлаживать и сопровождать. Причем, другим людям.

Как понимать семантику списка?

Давайте формализуем:

1. Amortized constant time insertion or deletion at random position (подчёркиваю - меня даже «amortized» устроит).
2. Стабильность итераторов.
3. Constant time splice().

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

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