Comments 66
А вот если таргета в списке нет...
Как элемент списка может отсутствовать в списке?
В этом API предполагается что вызывающий код следит за тем, что он передает в API. В реальном коде там бы ещё стоял assert().
Представьте себе, что программа, которая итеративно обращает матрицу 64kx64k при каждом обращении к ее элементам будет делать две проверки — что индекс не отрицательный и что индекс не превосходит размера матрицы? Сколько при этом электричества и времени уйдет впустую?
А теперь напоминаю вам теорему Геделя о неполноте, которая говорит нам следующее — в достаточно полной формальной системе (а Rust, или на что вы намекаете, является такой системой) всегда можно построить такое утверждение, про которое невозможно в рамках этой системы доказать, истинно оно или ложно.
Для доказательства придется выйти за рамки этой системы (взять ручку с бумажкой).
К примеру, если элементы из списка удаляются на основе внешнего ввода (которому мы доверяем), формально, глядя на код обработки этого ввода, доказать уже ничего не получтися.
Я исхожу из предположения, что ввод приходит из внешней доверенной системы, на которую наша формальная система не распространяется.
Чтобы формальное доказательство и автовывод полноценно работали, придется научить аналитиков писать требования не канцелярским языком а языком формальных систем.
В противном случае, программа будет лоскутным одеялом для верификатора — вот сюда смотри, а тут
В ядре нередко опускают лишние проверки в угоду скорости.
То же самое делается добавлением в список псевдоэлементов head и tail и хранением ссылок на них в классе списка. Особенно полезно если список двусвязный и его может потребоваться перебирать с конца.
В каком таком классе. Где тут классы?
Ну замените слово класс на слово структура мысленно, что уж вы к словам придираетесь, тем более разница в данном контексте несущественная. Идея имеет смысл. Если рассуждать в терминах ООП, то сам по себе список и его элементы — это два отдельных типа, и, если это удобнее для решения конкретной задачи, то можно создать структуру для самого списка и хранить в ней head, tail, а так же любую дополнительную статистику, относящуюся к списку, а не к конкретному элементу (например, количество элементов, имя списка).
Теоретический: что с эффективностью? Взятие указателей и разыменования не бесплатные. Ветвление тоже, но там то хочется верить branch-prediction не подведет
Практический: ну да ну да, конечно «особый случай с if» — это плохой код, а ломать глаза над &(*p)->next, вспоминать в каком порядке применятся операторы, и вообще осознавать на кой хрен сделано именно так — дофига хороший?
Более того, ветвление только один раз в конце алгоритма, а дополнительное разыменовывание на каждой итерации
Ассемблерный код одинаковый для обоих вариантов: godbolt.org/z/676Mn4
Да где же:
Вариант Линуса:
mov rax, QWORD PTR [rsi+8]
mov QWORD PTR [rdx+8], raxТрадиционный:
lea rdi, [rdx+8]Не очень хорошее сравнение из-за различий имен меток: https://godbolt.org/z/b4xGv4
Причем, что можно заметить, в традиционном варианте даже нет финальной специальной обработки, все различие между листингами только внутри цикла.
все различие между листингами только внутри цикла.
Где?! Различие только на выходе из функции, в одну инструкцию. Цикл — дословно один и тот же.
mov rax, QWORD PTR [rdi]
cmp rax, rsi
je .L2
.L4:
mov rdx, rax
mov rax, QWORD PTR [rax+8]
cmp rsi, rax
jne .L4
Черт! Нужно себе минус поставить. Действительно, те кусочки относятся к коду после цикла. Еще и перепутал их местами, более короткий как раз у решения Линуса.
Во-вторых, когда считаете раскладку по исполнительным блокам, то не забывайте, что что то, что вы видите в коде и то, что исполняет процессор — сильно разные вещи. Уже лет 20 как. Например "
cmp+jne" — это не две инструкции, а одна (20.4: Instruction fusion), а регистровый mov — вообще не инструкция (20.13: Instructions with no latency). Не забывайте что lea считается не в ALU, кстати.Если же брать процессоры, где инструкции-таки можно считать пальчиком, то там тоже всё не так — можно на ARM глянуть или AVR.
Что почитать, чтобы в теории поднатаскаться? ;)
Во-вторых, когда считаете раскладку по исполнительным блокам, то не забывайте, что что то, что вы видите в коде и то, что исполняет процессор — сильно разные вещиинструкции надо сначала загрузить и декодировать, а уже потом оптимизировать и исполнять. Например я натыкался на случай когда sse3 код на интринсиках, будучи скомпилированным под AVX, давал 10+% прироста к быстродействию (при той же ширине регистра). За счет избавления от тех самых mov'ов (которые «вообще не инструкции»), т.к. AVX-аналоги SSE инструкций трехаргументные.
Я мимо шёл. На ARMv8 clang вариант Линуса короче на 5 инструкций: https://godbolt.org/z/xqbarc
Согласен. Код должен писаться для людей, а не для машины. Чем проще код для восприятия и чтения, тем лучше при прочих равных (если не страдает эффективность и корректность). Так дешевле поддерживать, меньше багов будет.
Просто в последние годы произошёл от медленной и невыгодной технологиии «Хуяк-и-в-продакшн» к «Ху…-релиз» (про суперсложную и невероятно медленную «Хуяк-хуяк и в продакшн» уже только аксакалы вспоминают).
Полностью согласен, но в некоторых случаях, как, например, часто используемый базовый код ядра, стоит написать "как производительнее", а не "как удобнее".
Всегда пишу вторым способом, и никаких сложностей восприятия это не создаёт, наоборот по-моему понятнее. В нём меньше сущностей поддерживается одновременно — это не только процессору хорошо, но и программисту, держащему их в голове. И проще мысленно проверить весь ход его выполнения благодаря отсутствию лишних ветвлений.
Ну и логически он ничуть не хуже первого: мы запоминаем место "сцепки" и пересоединяем её на другой элемент. А в первом варианте запоминается путь к сцепке. Просто многие видимо указатели считают какой-то непонятной магией и даже не пытаются на них навесить высокоуровенвые смысловые ярлыки, от того и проблемы.
Всё верно. Оттого и не создаёт для вас сложностей, потому что всегда так пишете, это для вас привычно :) У человека, который не писал на C много лет, от постоянных операций разыменования и взятия адреса рябит в глазах и приходится усиленно вчитываться в код, чтобы разобраться. Ну и сущностей там не особо меньше, так как "p" и "указатель на p" — это две сущности.
И нет, указатели — это не непонятная магия, а весьма простая и понятная магия вещь, но субъективно читать сложнее, если не пишешь такой код регулярно.
Да, я понимаю, что это ядро, и там подобного кода много, и люди, которые занимаются ядром, к такому привыкли. Я прекрасно понимаю, что в ядре производительность на первом месте. Но:
- Чтобы написать более сложный код в угоду производительности, надо сначала детально разобраться, сравнить и обосновать, что это будет действительно более производительно, и что этот эффект будет существенным, чтобы принести больший value, чем потребовать в дальнейшем поддержки. А то может получиться, что оптимизации компилятора сведут все старания на нет. Чем проще и прямолинейнее код, тем проще компилятору его оптимизировать, и, по итогу, он может оказаться более производительным, чем хитрозакрученная реализация. А может вообще этот код будет использоваться, условно, раз в год на списках из 5 элементов, и никакого ускорения никто в жизни не заметит, зато накрученная сложность увеличивает вероятность багов. Надо разумно подходить и без необходимости не усложнять код.
- Для многих элегантность определяется простотой понимания сторонним человеком без глубокого знания кода и, соответственно, стоимостью дальнейшей поддержки. Чтобы беглый взгляд на код давал возможность быстро и без особых усилий понять, что здесь происходит, и починить баг или расширить функциональность в связи с новыми требованиями.
Как известно, единственной измеримой метрикой качества кода является количество WTF в минуту на ревью :)
Интересно, что если написать один единственный тест на удаление из середины, и прогнать его с branch coverage, то первая реализация укажет на то, что покрытие явно недостаточно, а вот вторая нет.
Связные списки, трюки с указателями и хороший вкусХороший вкус — не использовать списки без крайней необходимости.
Кстати, в каких ситуациях может понадобиться писать свою реализацию списка? Хотя бы теоретическую ситуацию, мне пока не хватает опыта сразу придумать.
Когда пишешь какие-нибудь lock-free алгоритмы. Там односвязные списки практически единственное что можно использовать.
Если не привязываться к конкретному языку программирования то вот что нагуглилось
https://www.cs.tau.ac.il/~shanir/concurrent-data-structures.pdf
Все структуры данных (стеки, очереди, хешмапы, ...) используют linked list как деталь реализации
Если привязываться к языку то можете посмотреть реализацию в c# или java ConcurrentЧтоУгодно
Причина в том что lock-free фактчиески строится на одной команде cpu CAS https://en.wikipedia.org/wiki/Compare-and-swap
и это значит что мы можем поддерживать связный список в консистентном состоянии следующим образом:
- прочитать значение по указателю
- сделать операцию иммутабельным образом над значением по указателю (классическим методом)
- при помощи CAS заменить указатель на старый объект на новый. Если не получилось (кто-то другой влез перед нами), goto шаг 1.
При обработке пакетов данных надо было их удалять по мере собирания по порядку и по мере таймаута. Можно организовать их в 2 переплетенных списка на одних и тех же данных. Готовой реализации такой штуки, естественно, нет. Можно было бы, конечно, делать 2 различных списка указателей, но там расход памяти больше и лишние разыменовывания указателей.
Еще пример, если вы знаете, что у вас в списке не будет более N элементов, но он часто часто меняется. Тогда можно вместо указателей использовать индексы в массиве и, во первых, держать данные в куче, а во вторых избавиться от всех ненужных аллокаций.
Грубо говоря, когда вам нужно что-то нестандартное.
в каких ситуациях может понадобиться писать свою реализацию списка?
В программах на C постоянно этим занимаются. Потому что
- В стандартной библиотеке нет связного списка.
- Нет общепринятого менеджера зависимостей, через который можно было бы притащить библиотеку с реализацией списков.
Но менее понятный при беглом прочтении.
В "элегантном" коде есть серьёзный недостаток:
void remove_elegant(IntList *l, IntListItem *target)
{
IntListItem **p = &l->head;
while ((*p) != target) {
p = &(*p)->next;
}
*p = target->next;
}Видите? Вот это "p"! Это очень плохо! Назовите его по-человечески, разбейте трёхэтажное разыменование на несколько стадий с нормально названными переменными и количество WTF даже от не могущих в Си значительно сократится.
Например так:
void remove_elegant(IntList *l, IntListItem *target)
{
IntListItem **ptr2current_ptr = &l->head;
while ((*ptr2current_ptr ) != target) {
ptr2current_ptr = &((*ptr2current_ptr )->next);
}
*ptr2current_ptr = target->next;
}Я не выбрал ptr2ptr2current, потому что это 1) тавтологически повторяет тип 2) мы на самом деле не используем IntListItem current, только указатели на, они для нас самодостаточны.
Поддержу. Осмысленные имена переменных вместо a, b, p и т.п. — одно из отличий production-ready промышленного кода от лабы первокурсника. Ну и "l" в "list" неплохо было бы переименовать до кучи.
Я не выбрал ptr2ptr2current, потому что это 1) тавтологически повторяет типкороткое не говорящее имя переменной как раз отличный признак того, что назначение переменной проще описывается её типом (в объявлении) и контекстом. Префикс «ptr2ptr» для переменной, объявленной как **, это перебор. В конце концов, не просто так венгерка отмерла
Люблю этот трюк. Вот несколько задач на leetcode, которые я решил с его помощью:
701. Insert into a Binary Search Tree
1474. Delete N Nodes After M Nodes of a Linked List
1669. Merge In Between Linked Lists
Связные списки, трюки с указателями и хороший вкус