Как стать автором
Обновить

Правила хорошего вкуса от Линуса Торвальдса. Делаем код быстрее, проще и понятнее

Время на прочтение 5 мин
Количество просмотров 48K
Всего голосов 70: ↑57 и ↓13 +44
Комментарии 145

Комментарии 145

Побольше бы примеров — реально интересная тема.

Там кроме утечки проблема с удалением последнего элемента.

Разве? entry->next у последнего будет нулём, соответственно prev->next обнулится в последнем стейтменте

Да, меня уже поправили. Пишу в основном на С++, поэтому отвык от трюков "указатель на указатель".

Эта штука удаляет ноду по указателю. Следовательно, указатель надо ещё где-то получить. Подозреваю, это пример какой-то внутренней функции.

А указатель берет из другой функции и сразу его передает в эту. А эта другая функция всегда, в случае ошибки, возвращает NULL.
ЛЮБЫЕ входящие аргументы нужно проверять на корректность :-( Даже если лично вы не предполагали, что эта функция(метод) будет использована где-то, кроме как у вас.
Давайте не мешать C и Java, а? Проверки всего и вся и, в результате, всё равно неработающие, но зато умеющие показывать невразумительные сообщения об ошибках — это Java.

В C/C++ принят иной подход: проверки осуществляются там и тогда, когда про это явно написано. И нигде более. Скажем написано что delete принимает NULL и ничего не делает — значит передавать туда можно, не написано что free может его принимать — значит нельзя и никаких проверок там не будет.

Спорить о философиях — бессмысленно, ходить со своим уставом в чужой монастырь — тем более.
Отнюдь, и вероятно в обоих случаях.
Случай с памятью — возможно, функция служит лишь для открепления элемента. То есть, список предназначен чтобы иметь указатели на объекты, но не владеть ими в плане памяти.
Случай с последним элементом — какая там по вашему ошибка? В последнем элементе next должен быть nullptr, следовательно next предпоследнего элемента встанет в next последнего, то есть nullptr. Вы думали, цикл while останавливается на последнем элементе, на самом деле он останавливается на указателе на указатель next предпоследнего.

Ответил комментарию выше

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

Может вы поясните каким образом и почему она будет неоптимальна с т.з. кэш-промахов? Интересно. Спасибо.

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

Вероятно ничего не имелось ввиду. Думаю что вам надо почитать вики, ибо ваши заявления не имеют смысла. «поочередное обращение к „далеко-расположенным“ » никак не виляет на кеш, но я могу вам задать тот же вопрос — каким образом оно влияет?

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

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

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

Опять какая-то муть. Все остальные «байты» итак пишутся. Я конечно понимаю, что отвечать на вопросы прямо вы не можете, но всё же:

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


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

Вот это — хамство. Вы можете считать ответ на вопрос неправильным, но это ответ именно на ваш вопрос. Хамить людям, которые не хамили вам — нехорошо.

Вы можете считать ответ на вопрос неправильным

Дело не в том, что я что-то там считаю — дело в том, что ваш ответ не состоятельный. И вам объяснили почему.

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

Какое отношение ваш ответ имеет к предмету обсуждаемому здесь? Вы можете хоть каким-то образом объяснить — где конкретно в данном случае это проявляется и каким образом решение предложенной автором первоначального коммента решает проблему?

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

Минусанул — не отвечал, после сослался на другой коммент и выкатил первую ссылку из гугла, которую нагуглил после прочтения чужого коммента, при это ни тот коммент, ни его ссылка к теме отношения не имеют — после минуснул и слился. Типичный эксперт.
он обычный балабол
Вот сейчас обидно было.
Дело не в том, что я что-то там считаю — дело в том, что ваш ответ не состоятельный. И вам объяснили почему.

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


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

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

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

По ссылке сравнение обхода по столбцам и строкам, что вызвано не «поочередное обращение к „далеко-расположенным“ в памяти данным», а разницей между шириной чтения реальной и используемоей — т.е. основная часть пропускной способности летит в трубу и кеш тут непричём. Что собственно там и написано.

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

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

А не, не — я подумал, что мне ответил alan008, а оказалось автор оригинального коммента.

В целом всё остаётся к силе.

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

Может это реально не вы меня минусовали и я ошибся, но не особо это что-то меняет итак понятно почему.

Если производительность важна, то однозначно да.


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

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

Проблема в том, что кроме параметра "красоты" код должен быть рабочим. По этому параметру плохи оба варианта.
Исходный пример делает по сути detach, не удаляя саму ноду списка.
Пример "со вкусом" оставляет утечку entry->next — т.к. "удалённая" нода перезаписывается копией следующей — но исходная останется висеть в памяти. Не говоря о том, что он свалится при удалении хвоста, у которого нет next

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

Да, точно. Там присваивание указателей.

Можно добавить одну переменную — читаемость повысится, строк меньше станет
for (r = 0; r < GRID_SIZE; ++r) {
	for (c = 0; c < GRID_SIZE; ++c) {
		bool itsEdge = (r == 0 || c == 0 || c == GRID_SIZE - 1 || r == GRID_SIZE - 1);
		if(itsEdge) grid[r][c] = 0;
	}
}

Ради того, чтобы засетать края квадрата проходить по всем его элементам? Серьёзно?

Так, погодите, я писал про исправление самого первого варианта автора.

for (r = 0; r < GRID_SIZE; ++r) {
	for (c = 0; c < GRID_SIZE; ++c) {
		// Верхний край
		if (r == 0)
			grid[r][c] = 0;
		// Левый край
		if (c == 0)
			grid[r][c] = 0;
		// Правый край
		if (c == GRID_SIZE - 1)
			grid[r][c] = 0;
		// Нижний край
		if (r == GRID_SIZE - 1)
			grid[r][c] = 0;
	}
}


И исправление только по поводу читаемости, понятности, количества строк.
А почему это условие сразу в if не налепить? Раз уж решили написать самую длинную строку в мире, надо довести дело до конца.
Как это зачем? Речь шла о читаемости, а не производительности.

Легко понять вот такое?
if(r == 0 || c == 0 || c == GRID_SIZE - 1 || r == GRID_SIZE - 1) grid[r][c] = 0;

Нет, не легко, вообще не ясно.

В моей же варианте мы явно говорим, что сначала мы проверяем край это или нет.
А потом в зависимости от этого уже что-то делаем
в общем-то несложно.
Стоило только поставить перед выражением if, как стало нечитаемо, вы правы.
Использование связного списка само по себе является плохим вкусом и неэффективным кодом в 99 процентах ситуаций. Реализация своего списка является плохим вкусом в 100 процентах ситуаций. Ну и по-мимо «вкуса» код еще должен быть понятен читателю. Первый кусок может и не слишком изящен, зато вполне понятен.

Второй пример — отличный контраргумент в споре о том, нужны ли алгоритмы. Никакой вменяемый программист, который понимает работу алгоритмов, не будет реализовывать n^2 решение для задачи, явно требующей линейного времени. Да и вообще, подозреваю что большинство бы реализовало сразу же последний вариант, т.к. он очевиден. Так что здесь скорее не о вкусе, а вообще о понимании, что ты делаешь.
НЛО прилетело и опубликовало эту надпись здесь
Программисты на С настолько суровы, что не используют библиотеки? Ну и в любом случае, связный список — очень плохая структура данных. Особенно если ты стеснен в ресурсах (если нет, зачем вообще писать на С?)
Что значит «плохая структура данных»? У нее есть своя область применения, в т.ч. и в системном программировании. Linux-сообшество — достаточно открытое на самом деле, если вы предложите (и реализуете) более эффективную альтернативу, к вам наверняка прислушаются.
Конечно, есть, поэтому и 99 процентов вместо 100. Но в целом нужно очень хорошо понимать, зачем тебе здесь список. В посте же речь идет о хорошем вкусе в целом (просто от Линуса). И вот использование списков и велосипедная реализация стандартных структур данных — весьма плохой вкус.
Вкус еще имеет отношение к языку и предметной области. Dependency hell в C совершенно не приветствуется, тем более ядру желательно не иметь никаких зависимостей и адаптировать все под свои задачи.
НЛО прилетело и опубликовало эту надпись здесь
Статья называется «Правила хорошего вкуса», а не «Правила хорошего вкуса языка С». Я не пишу на С, но если там нет общепризнанных библиотек для таких простых вещей, то все, по-видимому, плохо.

Я вообще ничего не имею против С программистов, но реализовывать одни и те же вещи раз за разом это НЕ хороший вкус. И дело даже не в криворукости, а в потраченном времени. Посмотрите на какую-нибудь реализацию std::sort в stl и подумайте, сколько времени понадобилось бы «не криворукому» программисту на аналогичную по эффективности и гибкости реализацию, учитывая дебаг, оптимизацию, тестирование и бенчмаркинг.
Вы чуть путаете. std::sort() это всё же С++, а «чистый си» используется порой в областях, где применение этой библиотеки невозможно, например на микроконтроллерах без «кучи».
Я в курсе, что это С++. Это просто пример стандартного и общеизвестного алгоритма, который, тем не менее, долго и сложно реализовывать на должном уровне.

Я не знаком с миром микроконтроллеров, но это слишком узкая специфика, давайте может вообще о программировании для картриджей NES поговорим? Если какая-то область разработки полна велосипедов и костылей и при этом работает, это не значит, что у них все в порядке со вкусом/качеством итд.
ОК, linux kernel устроит? Там тоже нет стандартной «кучи». И да, область не «слишком узкая» на самом деле, и именно в ней наиболее активно, сейчас, живётся «pure C», но это уже ИМХО.
Зачем сейчас писать на C? Только ради эфективности. Использовать стандартные библиотеки — далеко не всегда эфективно. Они зачастую слишком общие, там есть много лишних проверок и т.д. и т.п.
Вот тот пример от Линуса — он не только сделал код короче. Он ещё и убрал один условный переход чем сильно облегчил жизнь процессору. Теперь процессору не надо будет сбрасывать конвеер, если предсказатель переходов ошибся.
> Зачем сейчас писать на C?
Наверное потому, что компилятор простой и потому удобно писать вещи вроде ОС? В плане производительности некоторое подмножество С++ не хуже будет.

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

list довольно широко используется в ядре. Во-первых, удобно добавлять/удалять элементы в начало (+ в конец в double linked-list), а индексация не так часто нужна. Во-вторых, объекты бывают довольно тяжёлыми, поэтому (пере-)выделять и копировать память лишний раз не станут (что в случае динамического массива происходит периодически). Думаю, немаловажен и детерминизм списка: мы точно не начнём возиться с памятью, когда нам нужно найти кандидата из процессов на квант времени. Хоть hard real-time и не поддерживается, в ядре важна детерминированность.


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

Скорее всего так и есть, я же и говорю «99 процентов». Меня просто зацепила ассоциация хорошего вкуса и связного списка. Всё-таки не так много людей работает на уровне ядра, так что для большинства месадж выходит несколько странный.
По поводу объектов, кстати, ничто не мешает хранить указатели в массиве, сами объекты двигать не нужно тогда. Конечно, это лишний переход по указателю, но в списке их гораздо больше. Для добавления в конец и начало есть дек (хотя никогда не тестировал его производительность). Но если для ядра амортизация не подходит, то да, прийдется использовать список.
«Я не пишу на С», «Я не знаком с миром микроконтроллеров», " скачки по указателям, которые мажут мимо кэша" может тебе не стоит пытаться обсуждать вещи, в которых ты не разбираешься?
Пост о правилах хорошего вкуса, а не о программировании на С или программировании микроконтроллеров. Не я свернул общение на эту тему. Общие принципы программирования и хороший вкус в общих чертах языконезависимы (в рамках парадигмы, по крайней мере).
Не то, чтобы очень узкая, особенно если прибавить всякие системные штуки вроде ядра Linux с похожими требованиями. Вы же не ожидали, что Линус будет рассказывать о веб-программировании, правда?
Ядро Линукса — «вещь в себе», и да, это везьма узкоспецифчная вещь. Не приходилось читать его код раньше, но быстрая проверка показала, что они знают о повторном использовании кода. Так что не знаю, о чем тут спорить.
Ну, собственно, да, там есть своя реализация связного списка, и все ее используют. Кстати, ту же реализацию Линус вставил в git, по-видимому, просто чтобы не плодить зависимостей.
НЛО прилетело и опубликовало эту надпись здесь
> Пример с std::sort, кстати, очень в тему. Как раз то самое громоздкое и пр.
Меня очень радует ваша самоуверенность и пренебрежение к работе других людей. Вы ведь никогда не тестировали производительность std::sort, правда? И, кстати, привести пример «приспособления к данным»? А вообще не вижу смысла что-то объяснять, у вас явно есть очень четкая позиция.
НЛО прилетело и опубликовало эту надпись здесь
C-реализацию хэш-таблицы vs std::map и std::set.

Я могу не глядя в реализации сказать, что O(1) обычно быстрее O(log n), не говоря уже об ужасной аллокации памяти в деревьях (как в списках, только хуже). Вы, кстати, хэш-таблицу не на списках писали, я надеюсь?

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

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

При написании уеб-говнокода (херак, херак и в продакшн), да, дело во времени. При написании ядра операционки — в здравомыслии. Линус специалист по второму. Об этом и рассказывает и учит. Зачем ему учить первому? «специалистов» по первому учить не надо, они сами плодятся.

>нужно понимать, что отсутствие хорошей стандартной библиотеки — это недостаток, а не достоинство.

На уровне ядра «стандартная библиотека» — это только то, что они написали сами. Это не достоинство и не недостаток, это реальность. Да и в любом другом случае, стандартная библиотека не появляется ниоткуда божественным провидением. И её, сурпрайз, приходится кому-то писать. И даже херак-херак код далеко не всегда, оу, ещё один сурпрайз, состоит из последовательного применения функций стандартной библиотеки.
Ох, еще раз объясню: о времени речь идет когда есть готовая библиотека. Т.е. кто-то утверждает, что «зачем тянуть эту громоздкую библиотеку, лучше сам навелосипедю, т.к. я умный и здравомыслящий», я же с этим не согласен, т.к. какой бы ты ни был умный, вряд ли у тебя найдется достаточно времени для реализации вроде бы базовых вещей на достаточном уровне (если ты, конечно, не занимаешься разработкой соотвественной библиотеки).
Еще короче: велосипедить — плохо.
Если решения нет, то его, естественно, придется создать, я этого ни в коем случае не отрицаю. Просто заметьте, что в наше время львиная доля базовых, не очень базовых и совсем не базовых вещей уже реализована. Хоть свой Bolgenos пилите, ядро Linux вот прям по ссылке доступно.
>Т.е. кто-то утверждает, что «зачем тянуть эту громоздкую библиотеку, лучше сам навелосипедю, т.к. я умный и здравомыслящий»,

Кто утверждает? Линус?? Вы серьёзно? Кто этот «кто-то»?
По-моему вы выдумали какую-то глупость и пытаетесь «кого-то» убедить, что это глупость. А о том, что мир не заканчивается и даже не начинается на херак-херак коде даже услышать не в состоянии. Тем не менее, это так. А статья вообще не об этом.
НЛО прилетело и опубликовало эту надпись здесь
что O(1)

Вы, кстати, хэш-таблицу не на списках писали, я надеюсь?

Такие взаимоисключающие параграфы.

Я могу не глядя в реализации сказать,

А ничего, что O(1) стоит 4кб на елемент минимум? А уж про время ресайза я даже не говорю.

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

Ужасные аллокации( что это?) проблемы stl в который не завезли вменяемый аллокатор.
Я просто не считаю себя умнее группы других людей, работавших над данной конкретной задачей достаточно долгое время.

А над какой задачей работали эти люди? И какое-такое «долгое время»?

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

Это достоинство. При осмысленном использование си — это не язык — это подход.

Ну и кто вообще сказал, что stl — это «хорошая библиотека»/«хороший подход» с т.з. производительности? Это хорошая обобщенная библиотека и продукт ограниченный рамками заранее определённого интерфейса и интеграции.
А что мешает реализовать std::sort() для массивов без кучи?
Ничто не мешает. Но тот факто что «if the algorithm fails to allocate memory, std::bad_alloc is thrown» толсто намекает на тот факт, что куча — таки нужна.

И вообще — этот один std::sort может породить столько кода, что сожрёт половину места под программу на контроллере — и всё равно будет тормозить потому что обтимизирован под объёмы которые в микроконтроллер просто не влезут.

Стандартные библиотеки почти всегда работают не так уж хорошо, на самом деле. Их используют не потому, что нельзя сделать быстрее, а потому, что сделать быстрее и «правильнее» с точки зрения конкретной задачи банально дольше и сложнее.
Мне кажется, что эволюция средств программирования подошла к такому этапу в своём развитии, на котором мы хорошо представляем тот небольшой оптимальный набор структур данных для коллекций, который покрывает 0.999 потребностей приложений. И мы знаем, как оптимально этот набор реализовывать для тех или иных условий исполнения: микроконтроллеры или многоядерные процессоры, много памяти или мало, и т.д.

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

Как пример: тема юниядер (unikernels) в ML. Ребята умудряются загружать виртуальную машину с полноценным web-сервером за время dns-ответа клиенту.
И мы знаем, как оптимально этот набор реализовывать для тех или иных условий исполнения: микроконтроллеры или многоядерные процессоры, много памяти или мало, и т.д.
Знаем, да. Чего мы не знаем — так это способа сделать нечто что будет работать хорошо везде. Можно сделать библиотеку, которая будет отлично работать на микроконтроллерах, но тогда на NUMA-системах она будет «сливать», можно сделать что-то, что будет отлично работать на серверах с 128 процессорами — но тогда на одном она будет тормозить и т.д. и т.п.

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

То, что ML умеет загрузить виртуальную машину за время dns-ответа — это круто, конечно, но говорит скорее о том, что dns-ответ — штука медленная. И, потом, они явно не на микроконтроллере это делают. А сервер на микроконтроллере вполне может понадобится — и что вы будете делать если уже заложились на использование отдельной виртуальной машины для каждого запроса?
Для чистого С есть qsort из stdlib.h
Без «кучи».
Он без кучи, но с, потенциально, очень глубокой рекурсией. А стек на микроконтроллерах ограничен.
НЛО прилетело и опубликовало эту надпись здесь
Не все поголовно, конечно, настолько криворуки. Но большинство, действительно, именно настолько криворуки. Нередко на практике сталкиваешься с тем, что какой-нибудь «оптимизированный» Си-код работает медленней, чем его аналог на Lisp или даже на Python. Причина либо в том, что авторы не до конца понимают особенности работы процессоров или памяти, либо в том, что у них не хватает ресурсов написать всё хорошо.
НЛО прилетело и опубликовало эту надпись здесь
Это настолько фантастическое предположение, что хотелось бы увидеть примеры.
Примеры? Виндовс? :)
Когда ещё были в ходу компакт диски (или ещё раньше, когда флопы), при попытке обращения к дефектному диску колом вставала вся операционка.
А когда у меня на работе была вин2000, я по приходу включал компьютер и шёл к коллегам пить кофе. Как раз к возвращению она успевала загрузиться (не всегда). Вот что она делала? ;) лучше бы она была написана на лиспе. :)
Код Виндовс — вполне себе неплох. И оформлен хорошо, читется легко. Лично мне он кажется эталоном оформления голого Си кода.

Когда ещё были в ходу компакт диски (или ещё раньше, когда флопы), при попытке обращения к дефектному диску колом вставала вся операционка.

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

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

Когда у меня на работе была В2000, она была эталоном и скорости и стабильности в мире Вин. ХР на том же железе загружалась медленнее. Не представляю, что с ней надо сделать, чтобы загрузка так растянулась.
>Код Виндовс — вполне себе неплох. И оформлен хорошо, читется легко. Лично мне он кажется эталоном оформления голого Си кода.

И даже не снятся по ночам переменные вида lpctszStr = «blabla»?
Счастливый вы человек!

>Вы, веротяно, имеете в виду врмена 9х

Ноусэр! Тёмные времена 9х я объехал на варпе (os/2 warp). Это были nt4 и xp.

>Когда у меня на работе была В2000, она была эталоном и скорости и стабильности в мире Вин.

Как вы, наверное, понимаете, мне от этого ничуть не легче.

>Не представляю, что с ней надо сделать, чтобы загрузка так растянулась.

Ничего сверх того, что она сама позволяла. Там вообще мало что было — JDK, эклипс, фотошоп, ну, и вездесущий офис. Ума не приложу что она всё это время делала, но, подозреваю, что на лиспе она сделала бы это быстрее :).
Ещё у 2к любимым развлечением было залочить файло, присланное по самбе так, что и с админскими правами их нельзя было удалить (это не моя делала — соседняя).
Ума не приложу что она всё это время делала, но, подозреваю, что на лиспе она сделала бы это быстрее :).

Это ещё почему?

Хейтерс гонна хейт потому что.
И даже не снятся по ночам переменные вида lpctszStr = «blabla»?
Счастливый вы человек!

А вы не путайте код интерфейса Win32 для юзерспейса и код ядра.

Ноусэр! Тёмные времена 9х я объехал на варпе (os/2 warp). Это были nt4 и xp.

Тогда не верю про «вставала колом вся операционка». Или вы очень вольно используете слова «вся операционка».

Как вы, наверное, понимаете, мне от этого ничуть не легче.

Как вы, наверно, понимаете, это значит, что вы что-то делаете не так.

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

Да хоть 100 прикладных программ. При чем тут загрузка системы?
>А вы не путайте код интерфейса Win32 для юзерспейса и код ядра

А код интерфейса Win32 не является виндосом? Как интересно! А чем он является? Может линуксом? Или макосью?

>Тогда не верю про «вставала колом вся операционка»

Пожимая плечами — не может быть потому что не может быть никогда? А, ну-ну. Разумеется.

> Или вы очень вольно используете слова «вся операционка».

Ну, поскольку с вашей точки зиения, как выяснилось, отдельные части виндоса виндосом не являются, то, таки да. Например, таймер, скорее всего, продолжал тикать. «вся операционка, кроме таймера» — так устроит? Только вот это ничего не меняет.

>Как вы, наверно, понимаете, это значит, что вы что-то делаете не так.

Стандартный приём демагогии микрософта. Разумеется, что-то не так. Посмел вставить в сидюк сбоящий диск. Вот я подлец-то какой! На какой страничке eula, говорите, запрещено вставлять в сидюк сбоящий диск?

>Да хоть 100 прикладных программ. При чем тут загрузка системы?

Вот и мне интересно. Впрочем, нет. Не было интересно ни тогда — вызывало только раздражение, не интересно и теперь — проще проголосовать ногами. Всего лишь отметил этот печальный факт.
А код интерфейса Win32 не является виндосом? Как интересно! А чем он является? Может линуксом? Или макосью?

Я имею в виду декларации API, не распаляйтесь. Да, э то не «код Windows».

Стандартный приём демагогии микрософта. Разумеется, что-то не так. Посмел вставить в сидюк сбоящий диск. Вот я подлец-то какой! На какой страничке eula, говорите, запрещено вставлять в сидюк сбоящий диск?

Да нет, просто со времен 95-98 ни разу такого не было, хотя диски самой разной сбойности читал. Вот и удивляюсь.
>Я имею в виду декларации API, не распаляйтесь. Да, э то не «код Windows».

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

Чего угодно — это декларации для взаимодействия с системой, а не сама система.

Да и как быть со Спольски? Он подробно описывал «венгерскую» нотацию, какая она должна быть, почему всё пошло не так и про то, что именно вариант «не так» прижился и широко распространился и в мс тоже (не говоря о том, что это был рекомендованый вариант во всей мс документации). Неужели Джоэль соврал?

Отчасти да. «Неправильная» венгерская нотация используется в API, продуктах MS типа офиса и прочего юзерспейса. Внутри этого нет.
внутренний код МС может быть хорош или нет — иррелевантно. Лишь бы работало корректно. А вот API — лицо любого проекта. API windows пока что худшее, с чем мне приходилось иметь дело
внутренний код МС может быть хорош или нет — иррелевантно. Лишь бы работало корректно. А вот API — лицо любого проекта. API windows пока что худшее, с чем мне приходилось иметь дело

Эмм, ну вообще-то мы именно об этом говорили.
>Чего угодно — это декларации для взаимодействия с системой, а не сама система

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

>Отчасти да. «Неправильная» венгерская нотация используется в API, продуктах MS типа офиса и прочего юзерспейса. Внутри этого нет.

Ну, вот, оказывается, что и Джоэль всё врёт! Он-то утверждает, что в офисе использовалась «правильная» венгерская нотация (которая называлась, внимание, венгерской нотацией для приложений), а в остальном виндовс, во всей документации — дебильная (которая так и называлась, внимание-внимание, системная венгерская нотация. Системная, Карл!). Врёт значит. И виндовсе ничто виндовсом не является. Супер. Вы хоть понимаете насколько ценными выглядят ваши утверждения? Кстати, ваше имя не д`Артаньян случайно?
Зы пошёл жечь книги лгунишки Спольского. Один д`Артаньян открыл мне глаза на его истинную сущность…
Графическая оболочка — это же не виндовс, правда? Всё, что угодно, но не виндовс. Или, вот, ядро. Оно же — ядро системы, оно же не система., ага? Смешно.

Почему? Я просто указал на то, что венгерская нотация, которая не понравилась моему собеседнику, применяется не везде. Об этом же говорит Д.С.

Ну, вот, оказывается, что и Джоэль всё врёт! Он-то утверждает, что в офисе использовалась «правильная» венгерская нотация (которая называлась, внимание, венгерской нотацией для приложений)

А давайте мы предметно обсудим, с конкретными цитатами? Я готов отступить от «продуктах MS типа офиса и прочего юзерспейса.» к «продуктах MS юзерспейса и документации» и признать, что я неправ относительно именно офиса. Это не меняет сути — есть «правильная» ВН, есть «дебильная». И есть код вовсе без ВН, о котором я и говорил.

а в остальном виндовс, во всей документации — дебильная

Насколько я помню его заметку, он вел речь как раз о пользовательской венгерской нотации (пользовательской — в смысле применяемой с «пользовательской» стороны, не со стороны ядра, 0 кольца).
(которая так и называлась, внимание-внимание, системная венгерская нотация. Системная, Карл!). Врёт значит.

Любой может найти код, скажем, диспетчера памяти NT, да чего угодно и убедиться самостоятельно — «дебильной» венгерской нотации там нет. Название «системная» скорее всего относится как раз к системному API.

Зы пошёл жечь книги лгунишки Спольского. Один д`Артаньян открыл мне глаза на его истинную сущность…

Какая экспрессия. Человек спросил «Спольски врет?» — это не я предложил такую форму общения. Замечу, слово «врет» не обязательно означает намеренную ложь. Я всего лишь сказал, что такое-то и такое-то утверждение не соответствует действительности, остальное — ваше воображение дорисовывает. Будьте спокойнее.
Так еще, на всякий случай. Вот цитата из MS style guide:
Variable Names
Variable names are either in «initial caps» format, or they are unstructured. The following two sections describe when each is appropriate.
Note that the NT OS/2 system does not use the Hungarian naming convention used in some of the other Microsoft products.
Какое отношение имеет Windows к скорости Lisp или Python .vs. С? Прошу озаботиться чтением вопроса
Виндовс написана (была) на си. Если бы была написана на лиспе, думаю и то быстрее бы работала. :) вы же просили примеров — это пример.
давайте на секунду вспомним, что на уровне ядра лисп попросту не заработает
Неочевидно. Даже если железные лисп-машины в расчёт не принимать.
Если не теоретизировать, то стандартный pystone (python) работает в 100 раз медленнее, чем drystone, написанный на С.
Вы часто работаете в тестах? Я — никогда. :)
В конце-концов, даже если вы действительно работаете в тестах, это всего лишь означает, что drystone написан хорошо. А вы просили обратные примеры :).
Он написан одинаково. Простой порт с С на Питон.

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

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

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

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

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

А я этого и не утверждал. Я утверждал совершенно другое.

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

Ну-у-у! Менять правила в ходе игры некрасиво.

Для списков и очередей я бы назвал стандартной queue.h. Но оно такое, полностью на макросах.

НЛО прилетело и опубликовало эту надпись здесь
Не то, чтобы это прямо стандартная библиотека в полном смысле слова, т.е. включённая в стандарт, да и библиотекой это не назвать, но всё-таки «оно» есть: https://linux.die.net/man/3/queue
НЛО прилетело и опубликовало эту надпись здесь
Программисты на С настолько суровы, что не используют библиотеки?

Так вот приведен пример кода такой библиотеки, что не так? Почему вы думаете, что это велосипед?

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

Серьезно? Вот в NT двусвязный список применяется, например, для связки структур типа EPROCESS в кольцо. Очень удобно и затрат накладных — ноль целых, мал-мала десятых.
Предложите альтернативу, учитывая, что элементы в памяти расположены произвольно, добавление/удаление происходит редко. Отдельный вектор с постоянным ресайзом?
Так вот приведен пример кода такой библиотеки, что не так? Почему вы думаете, что это велосипед?

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

Вот в NT двусвязный список применяется, например, для связки структур типа EPROCESS в кольцо. Очень удобно и затрат накладных — ноль целых, мал-мала десятых.

Не знаком с этим, к сожалению. Возможно, это тот случай из 1 процента. А, вероятно, отдельный вектор был бы оптимальнее, с учетом того, что добавление/удаление происходит редко, как вы сами сказали.
Последний вариант автора, который он считает красивым, подходит только для квадратных массивов. Его решение не универсальное, не подойдет для случая, если row_size != col_size. Потому, как уже отмечалось выше, верх и низ обрабатываем memset, а право/лево в одном цикле. Так будет универсальнее.

Да даже не важно, квадратные массивы, или нет.


Код понятным должен быть.
Как нормальные люди рисуют рамку?


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


Про первоначальный вариант я вообще молчу.

так чисто для размятия мозга

for i in range(max(cols,rows)):
    # up
    grid[0][min(cols-1,i)] = 0
    # down
    grid[rows-1][min(cols-1,i)] = 0
    # left
    grid[min(rows-1,i)][0] = 0
    # right
    grid[min(rows-1,i)][cols-1] = 0
второй вариант разыменует нулевой указатель, если его передать.
Это псевдокод.
Первый тоже. Там везде есть entry->next.

Просто Линус в основном пишет код для ядра. А там немного другой подход к некоторым вещам. Например — не надо передавать нулевые указатели в функции, которые их не ожидают.
Мне одному показалось, что решение Линуса не оптимально в случае удаления не последнего элемента из конца списка?
В случае «некрасивого» решения это просто сращивание указателей, не очень красиво, но эффективно, а в случае «красивого» — это проход по всему списку от начала до конца — множество обращений к памяти, практически исключение процессорного кеша из применения, так как элементы списка не обязаны лежать линейно и т.п.? Или я что-то не понял из статьи?
Хм, а как мы можем найти конец списка не пройдя по нему? Список то односвязный.
Я ж говорю, что-то упустил и поэтому не понял нюанса. Почему-то решил что двусвязный.
Спасибо!
Посыл у статьи отличный. Устранение условных операторов особенно полезно в шейдерах. Когда я начал их писать, нашёл для себя много способов избежать их применения.
Честно говоря, после такого введения об указателях на указатели, я не ожидал, что автор остановится на том решении, с которого я бы начал. Я думал, что в итоге он запузырит что-нибудь вроде:

char* p = &grid[0][0];
for (int i = 0; i < GRID_SIZE;)
    *p = *(p + (GRID_SIZE-1) * i++) =
    *(p + (GRID_SIZE-1) * i) =
    *(p++ + (GRID_SIZE-1) * GRID_SIZE) = 0;

А потом будет рассказывать о хорошем вкусе :)
Но нет… Он вовремя остановился… Видимо, у него и правда есть хороший вкус.
*(p + (GRID_SIZE-1) * i++) и *(p + (GRID_SIZE-1) * i) — это одно и то же значение, а p++ в конце ломает логику, потому что левая и правая границы должны быть вертикальными, а будут диагональными.
Думаю, обе проблемы имеют общую причину. Я решил избавиться от фигурных скобок, записав все присваивания одной строкой, но совсем забыл про точки следования. Похоже без фигурных скобок не обойтись. Нужно как минимум три строки.
На самом деле таки две. Просто перенести p++ и i++ в for :-)
Если перенести в for, то можно и в одну строку уложиться. Только надо ещё заменить второе i на (i+1).
По той же причине, что и описал автор статьи, мне ужасно не нравится классическая реализация синглтона. Где инициализация происходит только один раз, а дальше if висит бесполезным грузом:

static Singleton getInstance()
{
    if(mInstance == null)
    {
        mInstance = new Singleton();
    }
    return mInstance;
}

Поэтому я в какой-то момент перешёл на ручную иницализацию при запуске приложения:

static void initInstance()
{
    mInstance = new Singleton(); 
}

static Singleton getInstance()
{
    return mInstance;
}

синглтон на то и синглтон, чтобы его не приходилось вручную инициализировать и деинициализировать. Пользуйся синглтоном Майерса (в байткоде будет проверка флага на инициализированность) или не пользуйся синглтоном вообще. В современных процах есть branch prediction на худой конец.
static const Singleton& getInstance() 
{
    static Singleton instance;
    return instance;
}

И никаких висячих if.

там внутри будет if. Это и есть синглтон Майерса

Нууу да. Там выходит что-то типа такого:


Скрытый текст
`instance(): # @instance()
pushq %rbp
movq %rsp, %rbp
movb guard variable for instance()::instance(%rip), %al
testb %al, %al
jne .LBB0_3
movl guard variable for instance()::instance, %edi
callq __cxa_guard_acquire
testl %eax, %eax
je .LBB0_3
movl instance()::instance, %edi
callq Singleton::Singleton()
movl guard variable for instance()::instance, %edi
callq __cxa_guard_release
.LBB0_3:
movl instance()::instance, %eax
popq %rbp
ret`

Если уж лишний test мешает, то, наверное, можно, презрев приличия, сохранить в этом месте локальную копию указателя на объект. Только с потоками не налажать.
НЛО прилетело и опубликовало эту надпись здесь
Придерживаюсь такого же подхода. Программа должна быть читаемой и объяснять _что_ требуется выполнить, а не _как_. Оптимизировать нужно только те места, где реально необходима оптимизация. На С сам давно не писал, но могу предположить, что в приведенных выше примерах компилятор вполне может выполнить оптимизацию так, чтобы эти примеры выполнялись абсолютно одинаково как по скорости, так и по результату. А если не видно разницы — зачем усложнять понимание?
компилятору сложновато даются оптимизации при работе с указателями
«Инициализация краёв сетки со вкусом» — серьезно?
Я бы такой говнокод как в первом и во втором варианте не написал бы никогда в принципе, даже в детстве, на моем спектруме это бы просто год работало бы.
Как вообще полное решение могло в голову автору прийти?
В последнем примере кода с сеткой можно сократить число итераций на 1, воспользовавшись тем, что есть пересечения краев. Но придется учесть частный случай, когда сетка состоит из одного элемента.
Пример конечно интересный, но попробуйте обойтись без условия если матрица не квадратная, т.е. если
GRID_SIZE_X != GRID_SIZE_Y, что обычно встречается на практике.
Как тут было замечено строки (или столбцы, в зависимости от последовательности выделения памяти) лучше обнулять с помощью memset(...), а потом столбцы (или строки) в цикле. Нет условий и максимальная скорость работы.

де факто там получится оптимально первая строка кроме последней ячейки, потом цикл по правому краю, кроме последней строки (+ левый край через адрес+1), потом нижняя строка, кроме первого элемента )


а вот использовать цикл или memset — не так уж и важно. современные компиляторы очень хорошо оптимизируют такой код, и for может оказаться быстрее за счет использования векторных инструкций. библиотека может оказаться не оптимизированной под ваш target.

Цикл по-любому лучше. Из моего примера, приведённого ниже, оптимизатор вообще убирает первый цикл для матриц шириной 100 и менее элементов. Без всяких там векторных инструкций. Просто тупо забивает строку в матрице 8-байтой константой, сдвигаясь на 8 байт в каждой следующей инструкции. Чуть больше десяти инструкций для матрицы размером 100.
Если вообще без условий, то нужно два цикла:
for (char *p = &grid[0][0], *q = p+GRID_X; p < q; p++) *p = *(p + GRID_X*(GRID_Y-1)) = 0;
for (char *p = &grid[0][0], *q = p+GRID_X*GRID_Y; p < q; p += GRID_X) *p = *(p + GRID_X-1) = 0;

Но на мой вкус лучше делать одним циклом с разумным минимумом условий:
char *p = &grid[0][0], *q = p;
for (int i = 0; i < max(GRID_X, GRID_Y); i++, p++, q += GRID_X) {
    if (i < GRID_X) *p = *(p + GRID_X*(GRID_Y-1)) = 0;
    if (i < GRID_Y) *q = *(q + GRID_X-1) = 0;
}
недурновкусный код, конечно, красиво выглядит, но, может быть, удобнее явно видеть обработаны ли «особые случаи»
чем больше ветвлений if тем медленнее код! меньше ifov быстрее код!
Первый код как манная каша — все понятно, в горле не застрянет. А второй дает возможность подумать, распробовать… Именно этот «вкус» я думаю и имел в виду Торвальдс. Согласен, вкуснее.
Зато первый читается легче.
>А как вы можете применить концепцию «хорошего вкуса» в своих проектах?

К примеру, на CMS Drupal функционал каталога можно реализовать (1) кастомным кодом, (2) используя контриб модули Ubercart или Commerce, (3) используя встроенные штатные модули Taxonomy + Views.

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

ИМХО, если нет супер критических требований по производительности, можно забить на все эти оптимизации по уменьшению количеству проходов по циклам, условий и т.д… На первом месте должна стоять простота, читабельность и понятность кода, даже в ущерб производительности и меньшему объему кода (понятное дело что совсем маргиналить с трема влоежными циклами или еще чем-то — не надо). В 90% задачах разницы в скорости все-равно не будет видно а более короткий код далеко не всегда более читабельный код.

Мне кажется или в вашем коде возникнет проблема если массив будет пустым?

И правда, очень красивое решение, и лучше не сделаешь, как ни крути.


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