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

списки враждебные веют над нами, темные лиспы нас злобно гнетут!

может мне написать лисп на массивах вместо хрюнделя? я могу, только не совсем понятно — зачем

в непростой ситуации надо действовать, как подсказывает сердце.

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

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

Сомневаюсь, что они смогут сделать на нём встроенный общелисп (имеющий общий стек с растовой программой), т.к. там сборка мусора обязательна. Как они её сделают на родных указателях?

Во-первых, когда пробка рассосётся, тебе нужно будет сжать твои деки,

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

Ну и давай сравним с потреблением твоих списков. Думаешь фрагментированный в труху твоим списком хип после того как пробка рассосётся на что-то будет пригодным?

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

фейспалм.

Я ведь описал уже, если машина в твоём списке продвигается, то ты точно так же должен обсчитать перекрёсток, иначе «перекрёсток» уедет вместе с машиной, на которую он указывает. Так же нужно будет учитывать вероятность пустоты участка. Так что имеем if (cursor[n] != cursor[n-1]) cursor[n].move_next(); против if(!deque[n].is_empty())deque[n+1].push_front(deque[n].pop_back())

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

В-третьих, ЕМНИП я приводил это как пример полезности курсоров. По сути дела, ты и впилил курсоры в своё решение на массиве

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

Однако в реальности она равна O(N) на каждом шаге,

Никто тебя за язык не тянул. Рассказывай, где там O(N), что там N например.

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

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

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

Итого, будучи причёсанной и приведённой к состоянию паритета с решением на одном деке, твоё решение будет содержать 1 список на относительно небольшое количество нод (~в 20 раз меньше чем количество машин), 1 большой массив указателей для быстрого поиска ноды по индексу машины, и по массиву в каждой ноде.

Тогда и только тогда у тебя получится соответствующая 1 простой деке.

10 дек по 1000 айтемов?

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

Кстати, в твоём бенче, как ты сам пишешь, на размере в 100 млн список начинает работать быстрее, это и есть то, что конкретно в данном случае означает O(). Какой вывод ты из этого сделаешь? Предлагаю два варианта:

• списков в 100 млн элементов не бывает
• будем страдать, потому что списки не нужны

Вот конкретно что ты написал:

Примитивнейший односвязный список на 10 млн начинает обгонять вектор, но не то что бы сильно, на 100 млн разбегается, там вектор аж на 40% медленнее чем простейший список. Вероятно если увеличивать количество элементов, наступит момент, когда реаллокация станет слишком дорогой, тогда возможно и стандартный список обгонит наконец вектор, однако 100 млн записей по 64 байта - это уже 6 гигов. Не великовато-ли для простенького контейнера? И стоит ли оно, учитывая как ушатает этот список кучу?

Нет, 6 гигов - это не великовато для «простенького контейнера». «Ушатает кучу» - это гуманитарное блеяние. Я бы на твоём месте подумал бы о смене профессии. Что-нибудь гуманитарное, например, дворник, тебе бы подошло.

Дальше этого места не читал.

Это настолько же избитая отмазка как и «у моей подруги с её парнем».

Откуда эти цифры?

От тебя. Ты же предложил моделировать пробку. Много ли перекрёстков там будет? Много ли машин поместятся между перекрёстками? Если я и ошибся, ну пусть на 1 порядок.

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

Кстати, в твоём бенче, как ты сам пишешь, на размере в 100 млн список начинает работать быстрее, это и есть то, что конкретно в данном случае означает O().

Да ты что? Правда что ли? O(N) всё-таки победило? Ты, кстати, посмотрел в википедии что это значит?

Какой вывод ты из этого сделаешь? Предлагаю два варианта: списков в 100 млн элементов не бывает

Этот ответ. Ещё раз напоминаю тебе: не «списков», а «контейнеров». Забудь слово «список». Список - это в коде, а в задаче «последовательность», «стек», «очередь», «контейнер». Итак, бывают ли контейнеры на 100 млн элементов? Практически нет. Не в твоей работе уж точно. Но если тебе повезло и тебе досталась задача, в которой таки присутствует один или даже пара таких контейнеров, то это вполне повод чуток заморочиться и сделать контейнер на основе vector<vector<T>>. Если тебе нужно ворочить гигибайтами, это вполне повод подумать, и это даже не будет называться «страдать».

В любом случае, я ради смеха даже готов не спорить с идеей «после 10 млн можно подумать о целесообразности использования списка». Сам я в это не верю, так как 10 миллионами выделений мелких объектов ты ушатаешь хип, но это чисто умозрительное предположение, возможно в реале и не так. Вопрос, ты используешь списки только для 10млн+? Или и для хранения 100 элементов выбираешь список, потому что «вставка O(1)»?

А чего ты на свой же коммент отвечаешь, клоун? Чтоб я не увидел уведомление что ли?

Нет, 6 гигов - это не великовато для «простенького контейнера».

Не ври.

«Ушатает кучу» - это гуманитарное блеяние.

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

Я бы на твоём месте подумал бы о смене профессии. Что-нибудь гуманитарное, например, дворник, тебе бы подошло.

Врёшь. Ты даже на своём месте не смог о таком подумать. Чувак, ты, якобы выпускник того старого, с советскими традициями, МГУ, уже неделю пытаешься придумать задачу, которая не решалась бы списками более эффективно чем с использованием массивов. Ты, блин, на третьем курсе должен был бы, разбуженным ночью, за 10 минут придумать пару нетривиальных задач, пригодных для олимпиады по программированию среди первокурсников. Вместо этого ты, с высоты 20летнего опыта, гордо предлагаешь вставлять в середину последовательности и удалять оттуда.

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

Я стараюсь не читать чушь.

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

Что я вру, что 6 гб - это не многовато для простенького контейнера? Доказывай. Утверждение, что 6гб многовато для простенького контейнера - это уже и есть чушь, причём запредельная.

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

Или жду новых откровений о том, что вставка в середину не нужна.

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

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

Ещё неизвестно, что «ушатает кучу» меньше, 10 миллионов одинаковых объектов (пулы объектов вообще-то являются нормой в продвинутых приложениях, и они, к слову отметить, могут реализовываться с помощью списков, когда пустой объект ссылается на следующий пустой объект. Я не так много аллокаторов видел, но в той паре, которую я видел, это всегда было так). Или её больше ушатают осколки периодически перевыделяемого массива, которые все имеют разную длину.

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

Вместо этого ты, с высоты 20летнего опыта, гордо предлагаешь вставлять в середину последовательности и удалять оттуда.

Моя задача не в том, чтобы тебя победить, мне это ничего не даст. На моё мнение о Расте это мало повлияет, потому что я вижу, что некомпетентен вообще, а значит и про Раст толком ничего рассказать не сможешь из того, что меня интересует. А моё мнение о тебе уже составлено. Моя задача состоит в том, чтобы ты потратил на спор на порядок больше ресурсов, чем я. Так ты ответишь за обзывательства. Пока что я думаю, коэффициент лишь 3:1, будем работать дальше.

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

Вот и всё, что нам следует знать о ненужности списков.

Забудь слово «список». Список - это в коде, а в задаче «последовательность», «стек», «очередь», «контейнер».

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

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

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

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

20 страниц ты уклоняешься от признания этого факта, хотя не только я тебе пытался его объяснить. С его учётом, список и массив нельзя ставить на одну доску. Поэтому их нельзя назвать одним словом «контейнер», если не оговаривать при этом, что это контейнеры с разными API.

Что я вру, что 6 гб - это не многовато для простенького контейнера?

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

Хуже дурака только дурак-врунишка.

Доказывай.

Чё доказывать, дурак? Что 6 гигов в памяти да ещё и в 1 простеньком контейнере (не в каком-нибудь б-дереве, а вот просто так сложено) никто не хранит? Ты вообще в курсе, что, например, 32битные программы, которых ещё полно, под процесс 2 или 3 гига адресов выделяют? В прикладном коде уже 1 гиг данных заставляет переходить либо на работу с файлами (стриминг, отображение), либо на на какую-нибудь СУБД? А ты собрался вот под одно хранилище 64байтных записей 100 миллионов добавлять. Обычное дело, фигли, всегда так делаем.

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

О, теперь это уже «наиболее благоприятная ситуация»? Идиоты типа тебя бухтели, что даже простое добавление в конец массива, это O(N) в худшем случае и ай-ай-ай. Я доказал что на практике это не влияет. Я мог бы сделать благоприятную для массива ситуацию просто добавив туда кроме заполнения 10 пробегов по контейнеру. Или просто пару раз бы прокрутил цикл в котором сначала N раз push_back(), потом N раз pop_back(). В этих случаях вектор бы уделал списки раз в 10 даже при N = миллиарду. Но я честный, я замерял одно, операцию добавления с учётом возможности реаллокации.

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

Давай вставку в середину списка по номеру хотя бы.

Эта песня хороша, начинай сначала. Я же тебе уже твою пробку промоделировал.

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

Потом я тебе покажу вставку по номеру в примитивнейшую, основанную на массиве структуру.

Ты вообще в курсе, что, например, 32битные программы, которых ещё полно, под процесс 2 или 3 гига адресов выделяют?

Хахаха.

Вот и всё, что нам следует знать о ненужности списков.

Ты уже согласен на «не буду спорить с «можно подумать»»? Я бы назвал это полной капитуляцией.

я бы согласился на слово «контейнер», но ты игнорируешь то, что в списке у тебя есть произвольное количество условно-бесплатных курсоров

Ну да, положить N элементов в список, а потом положить рядом массив из N курсоров - отличная идея. А vector<unique_ptr<N>> или vector<shared_ptr<N>> не лучше будет?

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

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

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

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

Теперь алаверды тебе: по рации с полицейского вертолёта сообщили что если считать от конца дороги то в 3й синей ниве сидит грабитель. Синие нивы из общего списка составляют 0.3%. Как ты модифицируешь свою модель, чтоб решать такие задачи? Заметь, я не мухлюю, предлагая тебе искать машину по индексу, я и тут на голову честнее тебя.

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

Не надо мутить воду. Идентификатор машины, например, госномер - это не то, о чём я говорил. Я говорил об идентичности объекта «машина», которая в программе позволяет отличать эту машину от вон той. В твоём решении с деками этого нет, поэтому в твоей модели с машинами уже чего-то не хватает. А в списке это есть. Более того, если у меня есть список объектов «машина», выделенных на куче, то я легко добавлю хеш-таблицу или б-дерево для поиска этих же объектов по госномеру (но не забываем, что госномер - это не способ идентифицировать объект «машина», например, он может быть заляпан грязью, дублироваться или просто отсутствовать).

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

гуманитарное

дворник

«Технари» поражают широтой своих знаний.

Идиоты типа тебя бухтели, что даже простое добавление в конец массива, это O(N) в худшем случае и ай-ай-ай. Я доказал что на практике это не влияет.

Что ты доказал? У тебя есть замер максимального времени операции?

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

Поправка: это то что ты называешь «гуманитарным блеянием», потому что ты - дурак. А вменяемый человек пользуется знаниями, здравым смыслом, и проверяет. Я вот знаю, что существуют разные реализации хипа, есть GC, где хип мелких объектов дефрагментируется при сборке мусора, есть ручные, где дефрагментации нет, но есть оптимизации, стремящиеся снизить влияние мелких аллокаций. Поэтому я и пишу, что список в расте/плюсах на 100 миллионов айтемов размером около 64 байта - это «ушатать хип». Если потом нам потребуется 10 миллионов айтемов по 640 байт, то не факт что аллокатор сможет их нам выдать, хотя вроде как размер тот же.

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

Ещё неизвестно, что «ушатает кучу» меньше, 10 миллионов одинаковых объектов (пулы объектов вообще-то являются нормой в продвинутых приложениях, и они, к слову отметить, могут реализовываться с помощью списков, когда пустой объект ссылается на следующий пустой объект. Я не так много аллокаторов видел, но в той паре, которую я видел, это всегда было так). Или её больше ушатают осколки периодически перевыделяемого массива, которые все имеют разную длину.

В этом весь ты.

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

Моя задача не в том, чтобы тебя победить, мне это ничего не даст.

Поэтому ты всем написавшим в тему на меня жалуешься?

На моё мнение о Расте это мало повлияет, потому что я вижу, что некомпетентен вообще,

Как? Обидно слушай. Я тебя научил тому как в расте делается «наследование», я тебе объяснил, почему растовые курсоры ниочём. Наконец я дал тебе реализацию двусвязного списка на безопасном расте с бесконечным числом курсоров. Можно сказать, всё что ты знаешь о расте ты узнал от меня (впрочем, это не комплимент мне, ты просто полез нихера не зная). И вот теперь я «некомпетентен вообще»?

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

«Я не обосрался, я просто троллил». Ты у нас просто кладезь нелепых отмазок.

просто «вот в этом частном случае не хуже» - и это недостаточное основание чтоб считать списки нужными

Быть лучше - это не значит быть нужным. Вот тут я с тобой согласен.

Не надо мутить воду. Идентификатор машины, например, госномер - это не то, о чём я говорил. Я говорил об идентичности объекта «машина», которая в программе позволяет отличать эту машину от вон той.

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

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

Ты туп как пробка

Что заполнение списка сожрёт у тебя больше времени чем массива. И зачем мне замер максимального времени? Мне достаточно суммарного.

Мне нужно больше попкорна.

Ты совсем тупой?

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

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

«список в 10 млн ушатает хип» (читай: сделает формально свободную память непригодной для использования)

Когда я смотрел в сторону реализаций аллокаторов в последний раз (а это было лет 15-17 назад), то продвинутые аллокаторы использовали разные арены для объектов разного размера. Т.е., для объектов до 32b – одну арену, для объектов до 64b – другую, до 128b – третью и т.д. Объекты свыше какого-то порога уже сваливались в общую кучу.

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

В этом плане как раз создание+наполнение+удаление списков (особенно если списки разной емкости) гораздо меньше фрагментирует хип, чем создание+наполнение+удаление векторов. Особенно если у нас списки хранят однотипные объекты. Т.к. векторам как раз нужны непрерывные куски памяти. И найти такой кусок размером в 10KiB может быть и невозможно, даже если суммарно свободных блоков 200KiB или даже 200MiB.

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

Ну добавлю я в структуру «машина» суррогатный ключ id.

У тебя есть id машины. И как ты узнаешь id следующей за ней машины?

Объекты свыше какого-то порога уже сваливались в общую кучу.

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

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

Это, само по себе, отлично, но не годится (х) в качестве логического аргумента. Дело в том, что вы оба делаете, с одной стороны, довольно широкие заявления. А с другой, приводите весьма частные задачи в подтверждение этих широких заявлений. Это, конечно, вполне валидная стратегия, но только в случае, когда мы хотим опровергнуть некое обобщающее высказывание через приведение контрпримера. В нашем же случае это не работает, так как нельзя определить, что значит «опровержение». Что «в общем» значит, что вектор быстрее списка на линейной аллокации? А ничего, само по себе, еще не значит. И мы попадаем из области верифицируемой логики в область субъективных экспертных оценок, т.е. просто мнений (если отбросить лейблы профессионального опыта).

Вот, например, у меня есть фремворк для мудьтипоточного программирования а-ля Seastar. Там есть очереди между потоками. И я беру, и заменяю очередь на списках на кольцевой буфер. И получаю кратную потерю производительности на ping-тесте (мотаем пакет последовательно туда-сюда). Хотя, казалось бы, массив, все дела. Что это показывает? Ничего. Это не говорит ни о том, что массивы хуже списков вообще, ни даже о том, что они хуже на одной этой задаче.

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

(х) Так как мы тут, в общем-то, развлекаемся, и никакие объемы работы проводить не собираемся, то можно остановиться на принципе eat your own dog food. Т.е. если уважаемый khrundel так любит массивы, пусть покажет, как он на них всё делает. Мы с тобой – не анонимы, опенсорсники, и наш «рацион» легко верифицируем.

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

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

Есть отдельные случаи, когда простые дизайны перестают работать. Например, GC на современных объемах RAM. И тут хочешь-не-хочешь, а придется делать иначе, усложнять, арены, пулы, ARC/RC и т.д.

Я именно для этого и использую «дизайны на массивах», чтобы решить проблему больших объемов структурированных данных в RAM и внешней памяти. А не «для скорости». Массивы для скорости далеко не всегда хорошо, pointer chasing всё еще strong, пока мы сидим в кэшах. А кеши сейчас большие. И GC далеко не всегда плохо. Надо просто размер кучи держать ограниченным.

Например, GC на современных объемах RAM.

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

И я беру, и заменяю очередь на списках на кольцевой буфер. И получаю кратную потерю производительности на ping-тесте (мотаем пакет последовательно туда-сюда). Хотя, казалось бы, массив, все дела. Что это показывает? Ничего

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

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

на коротких мессагах кольцевой буфер точно быстрей.

на коротких мессагах кольцевой буфер точно быстрей.

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

1. Make it run. (crude design, end-to-end tests)
2. Make it correct. (test coverage)
3. Make it fast. (benchmarks)

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

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

(х) Эта стратегия не работает на собеседованиях. Если её применить там, то, скорее всего, собеседование будет провалено. Программисты сами быстрый код с ходу не пишут, но от других требуют.

Make it run. (crude design, end-to-end tests)
Make it correct. (test coverage)
Make it fast. (benchmarks)

А что, на русском языке это правило не формулируется?

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

Я так подозреваю, что уж обычные очереди (a-la mailbox) между потоками под обычные нагрузки вылизаны до последней степени (очередь с таймерами, про которые шла речь раньше, я отношу к необычным, т.к. там есть отмена мессаджей).

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

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

В английском виде оно лучше гуглится. Мопедик-то не мой.

Эта стратегия не работает на собеседованиях. Если её применить там, то, скорее всего, собеседование будет провалено. Программисты сами быстрый код с ходу не пишут, но от других требуют.

Я думаю проблема не в этом, а в том, что на собеседовании четко не определяется — какой именно навык проверяется у собеседуемого.

Примеры:

1. быстро решить задачу
2. написать самый быстрый код для задачи
3. показать максимально известный тебе объем знаний вокруг задачи
4. показать свои способности решать принципиально новые для тебя задачи
5. показать, как ты мыслил при решении задачи
6. показать, как ты решаешь большую задачу постепенно (и не до конца — в стиле TDD)
7. << добавить свой вариант >>

Все это совершенно разные виды спорта (хотя 4 и 5 немного близки, примерно как бег и бег с препятствиями, гы-гы).

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

Программисты сами быстрый код с ходу не пишут, но от других требуют.

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

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

А statement как переводить? По-моему только стейтмент.

Добро пожаловать в многоязыковой мир! Чувствуй себя как дома, you are welcome!

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

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

А, да. Давай, педалируй тему. Ты сейчас допедалируешься до того, что правила форума придется менять, так как они нарушают законодательство РФ (и многих других стран). Требование всё переводить на русский язык нарушает права людей, для которых он является не родным. Это – языковая дискриминация :)