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

неееееет, совсем не так; я предлагаю тебе систематизировать ТВОИ недовольства, хотелки, и затем даже идеи

Ок, я систематизировал свои недовольства — дальше мне что с этим делать? Можно распечатать, свернуть в трубочку, и засунуть в попу. Потому что они абсолютно точно не позволят заработать денег, не будут реализованы, а даже помешают заработать деньги тем, кто делает 3 нм техпроцесс.

меня тут лет 5 не было; ты о чем говоришь?

Я на лоре 14 лет с перерывами.

они просто толком никому не нужны.

мне нужны

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

тот лохотрон, что в кикстартере «может сделаю, а может и нет» — меня не устраивает

Я на лоре 14 лет с перерывами.

я примерно столько же, но тебя среди регистрантов не помню

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

я плохо представляю как такое может быть

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

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

Ты живёшь 60ми годами.

«рандомное» перестроение - это хз что, но в общем quicksort внутри себя чем-то подобным занимается, так что решаемо.

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

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

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

Надеюсь, я ответил на твой вопрос?

я примерно столько же, но тебя среди регистрантов не помню

А типа я тебя помню?

речь шла про то, что ты «Я этим занимался когда-то на LOR-е», я сказал, что 5 последних лет лора (а скорее даже 7) я пропустил, так что кинь пожалуйста ссылки или расскажи что ты делал

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

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

Главной ценностью в глальной экономике до сих пор была возможность сконцентрировав кучу ресурсов иметь возможность делать то, чт оне могут делать другие. TSMC может делать 5 нм, а ты — нет. Грубо говоря, если появится технология для массового производства очень дешевых смартфонов, которые не хуже 5 нм по своим свойствам, то какой-нибудь Apple прекратит свое существование — это только одна сторона. «Экономике» нужно больше оборота, больше трудоемкости, больше затрат, больше односторонней концентрации ресурсов, больше недовольных владельцев безнадежно устаревших iPhone 12, которые не могут прожить без тринадцатого — а эффективные процессоры и программы являются полной противоположностью этого вектора.

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

вот скажем язык, близкий к C++, но без UB и с вычислениями не на шаблонах, а на чем-то вменяемом — нужен довольно широкому кругу; бабла на этом срубить не видно как; вот можно попробовать собраться

Ой, тоже мне сеньёр, херов. Иди б-дерево сделай на своих массивах обсосанных

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

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

очень длинно ты написал; я тебя понял примерно так: «суперидея на 130 нм будет все равно хуже говна на 5 нм»

я подумаю; но даже и в таком случае получается что-то типа клуба по интересам а-ля кикстартер

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

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

Мой поинт в том, что если для закрытия файлов приходится колхозить плохой и сильно ограниченный аналог RAII, то нафига вообще такой менеджмент? Не лучше ли пользоваться полным RAII и тогда можно не только держать открытый файл внутри try-with-resources, но и спокойно запихать его в Rc и быть уверенным, что он закроется когда не будет больше нужен.

Реальный недостаток Rc только в том, что можно создать утечку циклом ссылок, но тут 2 момента: программист, если он добросовестно выполняет работу, относительно легко разомкнёт цикл, благо слабые указатели никто не отменял. А если он глуп или специально желает подгадить, то тут и GC не спасёт, всегда можно запилить статическую коллекцию и напихать туда ссылки на всё что угодно.

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

Ты опять попал пальцем в небо. Ну вот, скажем, есть другой компьютер который выделяет для тебя что-то и даёт на это что-то хендл. И позволяет обратиться к нему и по этому хендлу что-то сделать. Можно ли управлять этим с помощью сборки мусора? Да легко. Гораздо легче чем памятью, потому что хэндл ни на что не ссылается. Можно и вообще аналогично, хранить список всех хендлов и во время трассировки обрабатывать переменные типа хендл, искать те, которые уже недоступны. Этакий плагин к GC. Можно и попроще, завести объект-хранитель, и обращаться через него, а сам хранитель пусть управляется GC и в финалайзере сообщает серверу что объект, идентифицируемый хендлом, больше не нужен.

Как видишь, не железо и не другие компьютеры не позволяют использовать GC для всего, а исключительно неспособность GC хорошо выполнять работу. Кроме того, GC не масштабируется, вот когда после сборки выясняется, что памяти всё равно мало, можно взять и запустить сборку более старшего поколения. А что если, скажем, сервер сообщил тебе как-то что у него кончаются ресурсы, сможешь ли ты запустить сборку только этих хендлов? Нет. Придётся запускать сборку всех управляемых ресурсов. А значит чем больше будет точек, способных инициировать сборку, тем пессимистичнее будет работать GC.

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

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

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

для программирования в стиле icon

Я даже не знаю, что это такое.

Например, когда ты пишешь a = b + c + d, то даже сишка здесь выводит тип

А не факт, что это хорошо.

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

Не кажется. Я своё мнение о С++ составил ещё до того, как узнал слово ЛОР.

джаве не нужна ведь есть C#

Наверное. Но уже поздно. Лисп-то нужен, но не всем.

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

Рассуждения об этике заиграли новыми красками.

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

Ну не подходит Java для DBMS.

Если забыть о том, что в Постресе таки есть gc, а в Оракле вообще что-то намутили (rollback segments too small - от всё, что я помню об этом).

Я даже не знаю, что это такое.

https://en.wikipedia.org/wiki/Icon_(programming_language)

так что тебе осталось придумать хорошее применение оператору «исключающее что-ли» — я на тебя надеюсь!

Степень оптимизированности не имеет никакого отношения к разговору, но ты снова заводишь ту же шарманку, а GC все равно бывает быстрее.

Не бывает.

На что я здесь должен отвечать?

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

Не ответил на мой аргумент с циклической ссылкой на дерево из значения дерева.

Конечно ответил, дурик. Цитирую себя: «делай ноды через Rc, а парент - через Weak и всё, проблема решена».

Дерево - это по определению что-то не имеющее циклических связей. Вот так просто. Да, в реальной жизни реализации узлов дерева часто нуждаются в ссылке на парента, но эта ссылка особая, через ссылки на детей невозможно вернуться в тот же узел. Соответственно ссылка на парента не владеющая. И, внезапно, у Rc (причём не только в расте), есть младший брат, слабый указатель, который может создать Rc, если объект ещё жив, но сам выживание объекта не обеспечивает.

Тоннами невменяемой лапши вспомогательных структур API, которые по итогу не масштабируются

Нет, дурик. Это вот твоё «зачем эти всякие сложности, они слишком душат, надо руками всё делать и следить» - вот это не масштабируется. В этом и смысл, да, тебе поначалу трудно понять все эти RefCell’ы, непривычно, кажется что лучше плюнуть и сделать на сырых указателях. Но в реале понять что такое Rc<RefCell<>> не так сложно, я вот про раст 2 раза в год вспоминаю и то исключительно в срачах на лоре, и то как-то понял. Зато потом уже сможешь решать задачи вот этими вспомогательными штуками ничуть не сложнее чем с помощью такой же невменяемой лапши как циклы, исключения, ассоциативные массивы и прочее. И знать, какие гарантии тебе дают эти штуки, и если ошибёшься, компилятор тебе объяснит.

Они могут знать сколько угодно — только решить они ее не могут.

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

А я тебе ответил, почему на сложных примерах твое «решение» не будет работать.

Нет конечно. Ты просто не знал что в расте такое можно, а возразить что-то надо было. Но в общем да, хранение данных в расте внутри замыканий сложнее аналогичной задачи в языках с GC. Одна проблема: сложнее ровно настолько же насколько просто хранение данных сложнее. Да, надо знать кто будет владеть.

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

Ну как сказать… В некотором роде и в языках с GC можно сказать что myObject = null - это «без 5 минут ручное освобождение памяти». С точки зрения труда программиста по крайней мере.

Ссылки замыканий на замыкания.

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

Суть функциональных языков заключается в том, что все данные хранятся в замыканиях — это альтернатива объектам

А ты не путаешь часом функциональные языки с джаваскриптом?

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

Вопрос не в том, что там под капотом

Я демонстрирую захват переменной в расте замыканием.

Ты: «а там всё равно под капотом копирование в структурку и вызов метода»

Я: «а где не так?»

Ты: «а неважно как под капотом, важно чтоб удобно».

Внимание, вопрос: ты сам дебил или других дебилами считаешь?

Ответил уже: Си, DSL.

Дебилушко, ты просто наугад слова пишешь что ли? Вопрос был о правильно реализованном языке по-настоящему высокого уровня. Хаскел не подходит, SQL (кстати, чем не domain specific language?) - тоже. Какой нахрен C? Да и DSL - это слишком обобщённо, видимо ссышь опять попасться.

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

Специально для тебя: сарказм.

Чуваку не нравится, что злой компилятор запрещает лезть к списку, построенному на однопоточных компонентах, из нескольких потоков. В C/C++/Java можно же! Понять, что ругань компилятора - это не баг, а фича ему, как и любому хейтеру раста, мозгов не хватает. Приходится вот приводить другой пример, когда так же компилятор зачем-то докапывается до кода, с той только разницей, что идея о том, что нельзя возращать из функции указатель на локальную переменную, как-то более широко распространена.

Эй, в Постгресе не GC, а арена для сессионных данных. Это всё же не одно и то же, хоть и близко.

Но чтобы было понятнее, почему я так говорю, я поясню.

В Java трассирующий GC на основе поколений, который лучше всего работает, когда перманентное поколение «маленькое». Чем оно больше, тем больше задержки. И это как раз случай БД, которая кэширует в памяти много стейта.

Справедливости ради, там можно запилить свой GC, оптимизированный под БД (я фантазирую). Но пилить его придется на С++.

Идеально было бы, если бы можно было явным образом разделять heap и off-heap. И, боюсь соврать, с Java 17 это в рамках Panama стало намного проще, чем было раньше.

Тебе тоже не хватает репрессий?

Эй, в Постгресе не GC, а арена для сессионных данных. Это всё же не одно и то же, хоть и близко.

А это что тогда?

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

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

и те же вопросы про идею «дескрипторы вместо указателей» в целом

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

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

Это VACCUM. Таки да, сборщик мусора, но это другой уровень. И, таки, да, у Pg с ним куча той же головной боли, что и у Java со своими GC.

Я тебя не понял)

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

насколько я понимаю, тебе для твоего желания «прямой работы с числами с произвольной длиной» придется всего лишь сделать маленькую программную надстройку над AVX, которая будет резать произвольную длину на размер AVX; и ты почему-то считаешь, что не ты должен сделать эту надстройку, а производитель ЦП; почему он сделает это сильно лучше тебя — вот это мне как раз и непонятно

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

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

Уже отвечал — это проблемы одной конкретной Java, которые не имеют отношения к проблемам GC

А что с Java не так, что не позволяет в ней волшебному GC развернуться? Java - один из самых востребованных в бизнесе языков, есть несколько реализаций виртуальных машин для него, даже вроде коммерческие альтернативы. Если где-то в природе существует хотя бы десяток человек, знающие как сделать хороший GC, их бы золотом осыпали за допиливание GC в джаве. Вместо этого пишут код, который проверяет, какие параметры функций не сохраняются нигде после выхода из неё и всё ради того чтоб заменить аналог Foo* bar = new Foo(); на Foo _bar(); Foo* bar = &_bar;

Может ровно наоборот, во всяких игрушечных языках GC кое-как справляется, а вот в конкретной Java, которую ентерпрайз использует, приходится как-то по капельки производительность выжимать?

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

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

Дай бог, дай бог. У мозиллы не получилось

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

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

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

Кстати, тебе ссылки принёс, чисто поржать:

• https://docs.rs/lockfree/latest/lockfree/index.html
• https://github.com/Marthog/rust-stm

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

На фоне того же раста, где для любого alter table/alter procedure нужно грохнуть всю БД целиком, это в любом случае ангельские крылья в голубом небе.

я тебя не понял

ты хочешь что-то типа alter class Car add field color:RGB ?

В случае условного AVX это будет несколько команд. А я хочу всю эту работу делать за 1 такт.

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

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

В случае условного AVX это будет несколько команд. А я хочу всю эту работу делать за 1 такт.

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

теперь я тебя не понимаю

ты думаешь транзисторов из нынешнего AVX хватит на тысячи мелких ядер?

а то лишних транзисторов-то каждый горазд попросить

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

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

Тут же параллельно проходит In-memory computing. Суть такова, что если, например, аппаратно реализовать rank/select над символьными последовательностями, то можно эти операции выгрузить прямо в чипы DRAM/HBM (с их большим внутренним параллелизмом), что будет очень энергоэффективно.

Просто этот образ персистентен и может принимать эн параллельных соединений.

причем из разных языков, а не только из лиспа

Ты не представляешь, но, таки да.

я действительно не умею считать баланс по транзисторам

максимум что я знаю: 2 операции за такт требуют во сколько-то раз больше shadow registers или че-то в этом духе

бессмысленное усложнение языка

Ну если ты так говоришь…

Просто переписать C++, выкинув из него лишний мусор и UB в особенности, сделает язык на порядок лучше — но этого почему-то никто не может сделать. Это сложно? Для этого нужно быть дофига экспертом-архитектором?

Если подумать, то да - сложно. Вот выкинешь ты несколько очевидных кривостей - поломаешь, допустим, 1% кода. Это много или мало?.. Ломать дальше? Где остановиться? Задача «обновления» кода плохо решается даже если ты предоставишь инструмент, который заставит вручную фиксить, если возникла какая-то неоднозначность в старом коде после твоих улучшений. А уж если окажется так, что поведение может поменяться, но поймёшь ты это только по неверным результатам в рантайме, то на такое вообще никто не согласится.

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

Дженерики - полиморфны?

так что ЛЮБАЯ критика уместна, даже, до определенной степени, критика вида «мне было трудно его изучать»

Даже если человеку вообще ничего не даётся?..

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

если недостатки найдены — значит язык плохой

Ну да, конечно. «Дурацкое название» - и всё, недостаток найден. Закапываем, язык плохой.

На мой взгляд, Rust-у в блокчейне нечего ловить

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

С++ не надо «исправлять». В смысле, пусть его развивают те, кто развивает и в рамках устоявшегося процесса.

С++ требуется радикально улучшать тулинг, и вот уже в рамках тулинга можно код тщательно обвешать аннотациями и санитайзерами на основе аннотаций. Будет не так изящно, как BC в Rust, но результат — тот же или лучше.

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

Который ты всё равно вызываешь, когда создаешь структуру, которую в этот список засовываешь. Молодец, сэкономил две спички.

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

И что делать потом? Сдвигать? Игнорировать дырку? Использовать индексы массива как ссылки и сделать свою аллокацию сверху?

не нужно вызывать free

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

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

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

Надеюсь, я ответил на твой вопрос?

Да я сразу понял, что не могу == не нужно. Классика отмазок же.

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

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

потому что списки - говно

Ога, молоток - говно, поэтому придумали пилу.

Ога, молоток - говно, поэтому придумали пилу.

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

Который ты всё равно вызываешь, когда создаешь структуру, которую в этот список засовываешь. Молодец, сэкономил две спички.

Или не вызываю. Структуры разные бывают. Но это неважно. Важно то, что накладные расходы на связный список будут выше чем на вектор, а значит если для тебя список - это 2 спички, то вектор стоит 1 спичку.

И что делать потом? Сдвигать? Игнорировать дырку? Использовать индексы массива как ссылки и сделать свою аллокацию сверху?

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

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

Нет, не подразумевает, внезапно. Если у тебя разбросано 10 ссылок на ноды, то рано или поздно одну из этих нод удалят.

Да я сразу понял, что не могу == не нужно. Классика отмазок же.

Доказать что твоё решение хуже стандартного = «ты просто не умеешь» и «классика отмазок»? Далеко пойдёте, молодой человек.

мне обидно читать обзывалки. В свой адрес особенно, но и в адрес третьих лиц тоже.

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

П - последовательность.

причем из разных языков, а не только из лиспа

Это несущественно, можно и на лиспе такое сделать. Так-то все эти языки должны всё равно разговаривать с сервером на языке sql, для них только телефоны с разной розеткой сделаны. Я в данном случае не продвигаю лисп, а просто обращаю внимание на сходства, мимо которых все проходят. Чтобы стало ещё интереснее - ОС линукс сам по себе хранит состояние в образе, который является частично персистентным. Программы - это аналоги лисповых функций (точнее, процедур, но не суть). Их можно горячо заменять, и можно подключаться по ssh извне. Эту аналогию не осиливают чуть менее, чем все. Тот, кто осилил и знает лисп, может вообразить себе лисп-машину и заплакать от того, как бесцельно он проводит годы своей жизни в линуксе. Я уже наплакался до полного истощения сил, но, как тут byko3y уже написал, хорошее никому не нужно. Все привыкли есть говно и будут с пеной у рта защищать ту точку зрения, что так и надо жить. Но, вспоминая, что наша миссия - это защищать людей от компьютеров, мы прославим линукс и тоже присоединимся к этой точке зрения. Чем дольше ИТ-шники будут давиться говном, тем дольше люди выживут.