«Вкус — это способность судить о прекрасном»
И. Кант
Дирк Хондел, один из тех, кто стоял у истоков Linux, однажды сказал о создателе Linux Линусе Торвальдсе: «Линус не только блестящий программист: у него хороший вкус. Торвальдс находит простые и разумные пути решения проблем, умеет всё «разложить по полочкам». Сложные вещи он делает простыми. По-моему, это и есть главное отличие превосходного программиста от просто хорошего».
В недавнем интервью, примерно на 14-й минуте, Линус Торвальдс коснулся темы «хорошего вкуса в программировании». Хороший вкус? Ведущий попросил его остановиться на этом подробнее, и Линус, пришедший не с пустыми руками, показал пару слайдов.
Сначала был продемонстрирован пример плохого вкуса в программировании, для того, чтобы на его фоне лучше было видно достоинства кода более качественного.
Пример плохого вкуса в программировании
Это – функция, написанная на C, которая занимается удалением объектов из связанного списка. Она состоит из 10 строк кода.
Линус привлёк внимание к управляющей конструкции if в нижней части функции. Именно этим фрагментом он был особенно недоволен.
Я поставил видео на паузу и внимательно рассмотрел слайд. Я совсем недавно писал что-то подобное. По сути, Линус сказал, что у меня плохой вкус. Проглотив обиду, я продолжил смотреть видео.
Я уже сталкивался с тем, что Линус объяснял аудитории. А именно, речь шла о том, что при удалении объектов из связанного списка нужно рассмотреть два случая. Первый – когда объект находится где-нибудь в середине списка. Второй – для объекта в начале списка. Такой подход вынуждает использовать конструкцию if и приводит к написанию безвкусного кода.
Но, если сам Линус признаёт необходимость использования условного оператора, почему же такой подход его не устраивает?
Дальше он показал аудитории второй слайд. Это был пример той же функции, но на этот раз написанной со вкусом.
Пример хорошего вкуса в программировании
То же самое, что в предыдущем примере делалось в десяти строк кода, теперь укладывается в четыре.
Но сама по себе длина текста программы не особенно важна. Важен подход, который приводил к появлению условного оператора в конце первого примера. В новом коде дополнительные условия проверять не нужно. Код был переработан так, что и для удаления элемента из середины списка, и для удаления первого элемента, применяется один и тот же подход.
Линус объяснил новый код, сказал, что самое главное заключается в устранении пограничного случая, после чего разговор переключился на другую тему.
Размышления о хорошем вкусе в программировании
Какое-то время я размышлял над примером. Линус был прав. Второй фрагмент гораздо лучше. Если бы это был тест на различение хорошего и плохого вкуса в программировании, я бы этот тест провалил. Мысль о том, что можно обойтись без этого злосчастного условия, никогда не приходила мне в голову. И я не раз писал подобное, так как часто работаю со связанными списками.
Пожалуй, главная ценность вышеописанного примера даже не в том, что он демонстрирует хороший способ удаления элементов из связанного списка. Главное здесь то, что этот пример заставляет размышлять о том, что код, который ты написал, реализации небольших алгоритмов, разбросанные по программе, можно улучшить такими путями, о которых ты и не подозревал.
Вот на эту идею я и обратил особое внимание, когда решил пересмотреть тексты своего свежего проекта. Возможно, это судьба, но моя программа тоже написана на C.
Насколько я понимаю, в центре внимания вопроса о хорошем вкусе в программировании лежит устранение пограничных случаев, которые имеют тенденцию проявляться в коде как условные операторы. Хороший вкус в программировании выражается, таким образом, в сокращении количества условий, которые приходится проверять.
Хочу рассказать об одном удачном примере улучшения моего кода.
Инициализация краёв сетки со вкусом
Ниже показан алгоритм, который я написал для того, чтобы инициализировать элементы вдоль краёв сетки, которая представлена в виде многомерного массива:
grid[rows][cols].Цель этого кода заключалась лишь в том, чтобы инициализировать значения для элементов, которые располагаются по краям – то есть, меня здесь интересовали верхняя и нижняя строки, и правый и левый столбцы.
Для того, чтобы это сделать, я, в исходном варианте программы, прошёлся в цикле по каждому элементу сетки, и, используя условный оператор, проверил, находится ли он на краю. Вот как это выглядело:
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;
}
}Хотя всё работало как надо, было понятно, что код далеко не идеален. А именно, вот основные проблемы этого фрагмента:
- Код слишком сложно устроен. Использование четырёх условных операторов в двух вложенных циклах выглядит неуклюже.
- Код неэффективен. При условии, что переменная GRID_SIZE установлена в значение 64, тело внутреннего цикла выполнится 4096 раз только для того, чтобы найти 256 элементов на краях.
Линус, вероятно, согласился бы с тем, что этот код нельзя отнести к образцам хорошего вкуса.
Повозившись какое-то время с программой, я смог уменьшить сложность алгоритма, реализация которого теперь содержала лишь один цикл for, который содержал четыре условия. Это было небольшое улучшение в плане уменьшения сложности структуры кода, но серьёзное – в производительности. Теперь выполняется лишь 256 проходов цикла, один для каждого элемента, расположенного на краю. Вот, как выглядел тот же фрагмент после улучшения.
for (i = 0; i < GRID_SIZE * 4; ++i) {
// Верхний край
if (i < GRID_SIZE)
grid[0][i] = 0;
// Правый край
else if (i < GRID_SIZE * 2)
grid[i - GRID_SIZE][GRID_SIZE - 1] = 0;
// Левый край
else if (i < GRID_SIZE * 3)
grid[i - (GRID_SIZE * 2)][0] = 0;
// Нижний край
else
grid[GRID_SIZE - 1][i - (GRID_SIZE * 3)] = 0;
}Стало лучше? Да. Но выглядит всё это просто отвратительно. Этот код не из тех, которые можно понять с первого взгляда. Только одно это заставило меня двигаться дальше.
Я продолжил экспериментировать, задался вопросом о том, а можно ли ещё что-то улучшить. Ответ был однозначным: «Да, можно». И то, к чему я в итоге пришёл, было настолько поразительно просто и элегантно, что я, честно говоря, не мог поверить в то, что для того, чтобы до этого додуматься, мне пришлось потратить столько времени.
Вот то, что у меня получилось. Здесь лишь один цикл и никаких условных операторов. Более того, тело цикла исполняется лишь 64 раза. Этот вариант значительно проще и производительнее первого.
for (i = 0; i < GRID_SIZE; ++i) {
// Верхний край
grid[0][i] = 0;
// Нижний край
grid[GRID_SIZE - 1][i] = 0;
// Левый край
grid[i][0] = 0;
// Правый край
grid[i][GRID_SIZE - 1] = 0;
}В этом коде в каждой итерации цикла инициализируется четыре разных граничных элемента. Код просто устроен и весьма эффективен в плане производительности. Его легко читать. Этот вариант не идёт ни в какое сравнение с первым и даже со вторым.
В итоге результатами я остался абсолютно доволен.
Есть ли у меня вкус к программированию?
И что же, теперь я программист, код которого отвечает правилам хорошего вкуса?
Мне хочется надеяться, что так оно и есть, но не из-за того, что я смог переделать неудачный фрагмент своей программы, который показал выше, да и другие тоже, которые в статью не включил. Всё дело в том, что проявление хорошего вкуса в программировании – это нечто большее, нежели некий фрагмент текста. Линус и сам говорил, что пример, который он привёл, слишком мал для того, чтобы должным образом проиллюстрировать его точку зрения.
Я полагаю, что Линус имел в виду то, что разработчики, обладающие «хорошим вкусом к программированию», отличаются от других тем, что они уделяют время на осмысление того, что они создают, перед тем, как начинают писать код.
Они определяют границы компонентов, с которыми работают, и то, как эти компоненты взаимодействуют. Они стремятся удостовериться, в том, что всё хорошо друг с другом сочетается, стараются добиться изящества кода и процесса его исполнения.
Результат такого подхода похож на код, который привёл Линус, да и на мой тоже, только в другом, более крупном, масштабе.
А как вы можете применить концепцию «хорошего вкуса» в своих проектах?
Комментарии (137)
ivan386
28.10.2016 14:29+6
Главное при этом не забывать высвободить память.TargetSan
28.10.2016 14:43+3Там кроме утечки проблема с удалением последнего элемента.
moachi
28.10.2016 14:54Разве? entry->next у последнего будет нулём, соответственно prev->next обнулится в последнем стейтменте
TargetSan
28.10.2016 14:59Да, меня уже поправили. Пишу в основном на С++, поэтому отвык от трюков "указатель на указатель".
andy_p
28.10.2016 16:27+2Хм… А если элемента entry нет в списке?
Все свалится.TargetSan
28.10.2016 16:38+1Эта штука удаляет ноду по указателю. Следовательно, указатель надо ещё где-то получить. Подозреваю, это пример какой-то внутренней функции.
Ckpyt
31.10.2016 08:49А указатель берет из другой функции и сразу его передает в эту. А эта другая функция всегда, в случае ошибки, возвращает NULL.
ЛЮБЫЕ входящие аргументы нужно проверять на корректность :-( Даже если лично вы не предполагали, что эта функция(метод) будет использована где-то, кроме как у вас.khim
31.10.2016 13:12+1Давайте не мешать C и Java, а? Проверки всего и вся и, в результате, всё равно неработающие, но зато умеющие показывать невразумительные сообщения об ошибках — это Java.
В C/C++ принят иной подход: проверки осуществляются там и тогда, когда про это явно написано. И нигде более. Скажем написано чтоdeleteпринимает NULL и ничего не делает — значит передавать туда можно, не написано чтоfreeможет его принимать — значит нельзя и никаких проверок там не будет.
Спорить о философиях — бессмысленно, ходить со своим уставом в чужой монастырь — тем более.
Shifty_Fox
28.10.2016 14:58Отнюдь, и вероятно в обоих случаях.
Случай с памятью — возможно, функция служит лишь для открепления элемента. То есть, список предназначен чтобы иметь указатели на объекты, но не владеть ими в плане памяти.
Случай с последним элементом — какая там по вашему ошибка? В последнем элементе next должен быть nullptr, следовательно next предпоследнего элемента встанет в next последнего, то есть nullptr. Вы думали, цикл while останавливается на последнем элементе, на самом деле он останавливается на указателе на указатель next предпоследнего.
Dionis_mgn
28.10.2016 14:30+5Если массив будет действительно большим, финальная версия будет неоптимальна из-за кэш-промахов. В таких случаях есть смысл разбить цикл на три (верхняя строка, нижняя строка, столбцы).
selgjos
29.10.2016 00:44-1финальная версия будет неоптимальна из-за кэш-промахов.
Может вы поясните каким образом и почему она будет неоптимальна с т.з. кэш-промахов? Интересно. Спасибо.
alan008
29.10.2016 14:51Вероятно, имелось в виду, что поочередное обращение к "далеко-расположенным" в памяти данным потребует постоянной перегрузки данных между кэшем данных процессора и оперативной памятью. Вики
selgjos
30.10.2016 17:47Вероятно ничего не имелось ввиду. Думаю что вам надо почитать вики, ибо ваши заявления не имеют смысла. «поочередное обращение к „далеко-расположенным“ » никак не виляет на кеш, но я могу вам задать тот же вопрос — каким образом оно влияет?
poxu
30.10.2016 21:53Когда процессор читает из памяти байт — он копирует его из оперативной памяти в кеш. На всякий случай копирует не только его, но и его соседей. В достаточно большом количестве. Поэтому, если читаешь или пишешь соседние байты, то считывать данные в кеш много раз не надо — достаточно одного.
А если читаешь или пишешь не соседние байты, то нужно копировать их в кеш по много раз.selgjos
31.10.2016 23:38Когда процессор читает из памяти байт — он копирует его из оперативной памяти в кеш. На всякий случай копирует не только его, но и его соседей.
Процессор никак не может читать из памяти. Он с нею никак не связан. Никаких «случаев» нету — память читается в кеш, а в кеше минимальная адресуемая единица — кешлайн.
Поэтому, если читаешь или пишешь соседние байты, то считывать данные в кеш много раз не надо — достаточно одного.
Опять какая-то муть. Все остальные «байты» итак пишутся. Я конечно понимаю, что отвечать на вопросы прямо вы не можете, но всё же:
что поочередное обращение к «далеко-расположенным» в памяти данным потребует постоянной перегрузки данных между кэшем данных процессора и оперативной памятью.
Имеем юзкейкес «линейное чтение из 2-х мест». На основании чего «копия памяти» из места А будет инвалидировать «копию памяти» из места Б?poxu
01.11.2016 08:28Я конечно понимаю, что отвечать на вопросы прямо вы не можете
Вот это — хамство. Вы можете считать ответ на вопрос неправильным, но это ответ именно на ваш вопрос. Хамить людям, которые не хамили вам — нехорошо.
selgjos
01.11.2016 23:22Вы можете считать ответ на вопрос неправильным
Дело не в том, что я что-то там считаю — дело в том, что ваш ответ не состоятельный. И вам объяснили почему.
Вы влезли в разговор и попытались ответить, но опять же ничего не смогли, кроме как ретрансляции поверий уровня детского садика. При этом даже не можете понять, либо хоть как-то пытаться их взять логически с вопросом.
Какое отношение ваш ответ имеет к предмету обсуждаемому здесь? Вы можете хоть каким-то образом объяснить — где конкретно в данном случае это проявляется и каким образом решение предложенной автором первоначального коммента решает проблему?
То, что автор мне ничего не ответит я знал изначально и написал это только лишь для того, чтобы те кто его плюсанул/почитал поняли, что он обычный балабол. Так бы человек читающий поверил, а так задумается — а понимает ли этот пассажир то, о чём собственно говорит.
Минусанул — не отвечал, после сослался на другой коммент и выкатил первую ссылку из гугла, которую нагуглил после прочтения чужого коммента, при это ни тот коммент, ни его ссылка к теме отношения не имеют — после минуснул и слился. Типичный эксперт.poxu
03.11.2016 16:40Дело не в том, что я что-то там считаю — дело в том, что ваш ответ не состоятельный. И вам объяснили почему.
Тот факт, что мой ответ не состоятельный — не повод хамить. Не повод вести себя так, как ведёте себя вы. То, что из вашего коментария можно вычленить, что инвалидация кеша в данном случае не происходит — хорошо. То, что вы попутно показали себя грубияном — плохо.
То, что автор мне ничего не ответит я знал изначально и написал это только лишь для того, чтобы те кто его плюсанул/почитал поняли, что он обычный балабол.
Было бы гораздо лучше, чтобы вы писали коментарии не для того, чтобы окружающие понимали, что кто-то там балабол, а для того, чтобы рассказать окружающим как оно на самом деле.
Dionis_mgn
31.10.2016 00:47За меня уже пояснили. Но я могу добавить ссылочку на неплохой пример с годным объяснением.
selgjos
01.11.2016 00:19Т.е. никто из вас ответить прямо на вопрос не может? Хотя судя по ссылочке ясно — очередное «слышал звон да не знаю где он» как следствие мышления на уровне «ключевых слов».
По ссылке сравнение обхода по столбцам и строкам, что вызвано не «поочередное обращение к „далеко-расположенным“ в памяти данным», а разницей между шириной чтения реальной и используемоей — т.е. основная часть пропускной способности летит в трубу и кеш тут непричём. Что собственно там и написано.
Осталось только понять каким образом связан юзкейс тот и тот, что представлен в статье. В данном случае никак обход изменить нельзя — он всегда будет по столбцам. При этом запись в столбцы никак не будет вытеснять строки, ибо хитов в столбец будет ровно один, а строку намного больше.
Если проще — между итерациями данные(строк) в кеше никуда не пропадут, ибо имеют больший приоритет из-за частоты использования.
selgjos
01.11.2016 00:24+1А не, не — я подумал, что мне ответил alan008, а оказалось автор оригинального коммента.
В целом всё остаётся к силе.
Ну и да, каким образом «ссылочка на пример» имеет отношение к данному юзкейсу? Мне интересно. В очередной раз тутошние экперты оказались настоящими экспертами.Dionis_mgn
02.11.2016 15:36Да, Вы правы. Кэш-линии первой и последней строк не инвалидируются при подходе автора статьи. Спасибо.
selgjos
03.11.2016 01:25Не, ну раз так бывает — я даже попрошу прощения. Если человек может отвечать за свои слова, то он не балабол. Конечно изначально это было в утвердительной форме и утверждать то в чём не уверен не очень хорошо, но всё же — я ценю. Не обижайтесь.
Может это реально не вы меня минусовали и я ошибся, но не особо это что-то меняет итак понятно почему.
akzhan
29.10.2016 08:29Если производительность важна, то однозначно да.
Причем абсолютно верно, что столбцы одним циклом, ибо скорее всего правая предыдущая ячейка в том же блоке памяти, что текущая левая.
q1b
28.10.2016 14:37+2Кажется его личный пример каким-то выдуманным для статьи. Не думаю, что нужно посмотреть выступление Линуса, чтобы понять, что первый вариант плох.
TargetSan
28.10.2016 14:41Проблема в том, что кроме параметра "красоты" код должен быть рабочим. По этому параметру плохи оба варианта.
Исходный пример делает по сути detach, не удаляя саму ноду списка.
Пример "со вкусом" оставляет утечкуentry->next— т.к. "удалённая" нода перезаписывается копией следующей — но исходная останется висеть в памяти. Не говоря о том, что он свалится при удалении хвоста, у которого нетnext
knotri
28.10.2016 14:55-6Можно добавить одну переменную — читаемость повысится, строк меньше станет
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; } }poxu
28.10.2016 15:09+19Ради того, чтобы засетать края квадрата проходить по всем его элементам? Серьёзно?
knotri
30.10.2016 15:22Так, погодите, я писал про исправление самого первого варианта автора.
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; } }
И исправление только по поводу читаемости, понятности, количества строк.
LifeKILLED
28.10.2016 16:30+1А почему это условие сразу в if не налепить? Раз уж решили написать самую длинную строку в мире, надо довести дело до конца.
knotri
30.10.2016 15:20-1Как это зачем? Речь шла о читаемости, а не производительности.
Легко понять вот такое?
if(r == 0 || c == 0 || c == GRID_SIZE - 1 || r == GRID_SIZE - 1) grid[r][c] = 0;
Нет, не легко, вообще не ясно.
В моей же варианте мы явно говорим, что сначала мы проверяем край это или нет.
А потом в зависимости от этого уже что-то делаем
daiver19
28.10.2016 15:25+7Использование связного списка само по себе является плохим вкусом и неэффективным кодом в 99 процентах ситуаций. Реализация своего списка является плохим вкусом в 100 процентах ситуаций. Ну и по-мимо «вкуса» код еще должен быть понятен читателю. Первый кусок может и не слишком изящен, зато вполне понятен.
Второй пример — отличный контраргумент в споре о том, нужны ли алгоритмы. Никакой вменяемый программист, который понимает работу алгоритмов, не будет реализовывать n^2 решение для задачи, явно требующей линейного времени. Да и вообще, подозреваю что большинство бы реализовало сразу же последний вариант, т.к. он очевиден. Так что здесь скорее не о вкусе, а вообще о понимании, что ты делаешь.
kloppspb
28.10.2016 15:29> Реализация своего списка является плохим вкусом в 100 процентах ситуаций
Для тех языков, в которых всё есть из коробки — да, но не для C.daiver19
28.10.2016 15:33-8Программисты на С настолько суровы, что не используют библиотеки? Ну и в любом случае, связный список — очень плохая структура данных. Особенно если ты стеснен в ресурсах (если нет, зачем вообще писать на С?)
OYTIS
28.10.2016 16:08+1Что значит «плохая структура данных»? У нее есть своя область применения, в т.ч. и в системном программировании. Linux-сообшество — достаточно открытое на самом деле, если вы предложите (и реализуете) более эффективную альтернативу, к вам наверняка прислушаются.
daiver19
28.10.2016 16:14-3Конечно, есть, поэтому и 99 процентов вместо 100. Но в целом нужно очень хорошо понимать, зачем тебе здесь список. В посте же речь идет о хорошем вкусе в целом (просто от Линуса). И вот использование списков и велосипедная реализация стандартных структур данных — весьма плохой вкус.
OYTIS
28.10.2016 16:33+1Вкус еще имеет отношение к языку и предметной области. Dependency hell в C совершенно не приветствуется, тем более ядру желательно не иметь никаких зависимостей и адаптировать все под свои задачи.
kloppspb
28.10.2016 16:19+6Назовите хоть одну стандартную C-библиотеку для списков? Хэшей? Деревьев? Очередей?
Ну хорошо, для линуксовой kernel-моды есть kfifo и прочее. Но на уровень чуть выше — уже пустота.
И почему вы считаете, что все поголовно C-программисты настолько криворуки, что не в состоянии реализовать эти вещи самостоятельно, с учётом конкретной задачи, и не хуже каких-то якобы существующих стандартных библиотек?daiver19
28.10.2016 16:32+1Статья называется «Правила хорошего вкуса», а не «Правила хорошего вкуса языка С». Я не пишу на С, но если там нет общепризнанных библиотек для таких простых вещей, то все, по-видимому, плохо.
Я вообще ничего не имею против С программистов, но реализовывать одни и те же вещи раз за разом это НЕ хороший вкус. И дело даже не в криворукости, а в потраченном времени. Посмотрите на какую-нибудь реализацию std::sort в stl и подумайте, сколько времени понадобилось бы «не криворукому» программисту на аналогичную по эффективности и гибкости реализацию, учитывая дебаг, оптимизацию, тестирование и бенчмаркинг.
Tujh
28.10.2016 16:36Вы чуть путаете. std::sort() это всё же С++, а «чистый си» используется порой в областях, где применение этой библиотеки невозможно, например на микроконтроллерах без «кучи».
daiver19
28.10.2016 16:46Я в курсе, что это С++. Это просто пример стандартного и общеизвестного алгоритма, который, тем не менее, долго и сложно реализовывать на должном уровне.
Я не знаком с миром микроконтроллеров, но это слишком узкая специфика, давайте может вообще о программировании для картриджей NES поговорим? Если какая-то область разработки полна велосипедов и костылей и при этом работает, это не значит, что у них все в порядке со вкусом/качеством итд.Tujh
28.10.2016 16:50ОК, linux kernel устроит? Там тоже нет стандартной «кучи». И да, область не «слишком узкая» на самом деле, и именно в ней наиболее активно, сейчас, живётся «pure C», но это уже ИМХО.
lorc
28.10.2016 16:51Зачем сейчас писать на C? Только ради эфективности. Использовать стандартные библиотеки — далеко не всегда эфективно. Они зачастую слишком общие, там есть много лишних проверок и т.д. и т.п.
Вот тот пример от Линуса — он не только сделал код короче. Он ещё и убрал один условный переход чем сильно облегчил жизнь процессору. Теперь процессору не надо будет сбрасывать конвеер, если предсказатель переходов ошибся.daiver19
28.10.2016 16:59+2> Зачем сейчас писать на C?
Наверное потому, что компилятор простой и потому удобно писать вещи вроде ОС? В плане производительности некоторое подмножество С++ не хуже будет.
> Он ещё и убрал один условный переход чем сильно облегчил жизнь процессору. Теперь процессору не надо будет сбрасывать конвеер, если предсказатель переходов ошибся
Один условный переход — это сильно, конечно. Вот только скачки по указателям, которые мажут мимо кэша практически полностью нивелирует эту оптимизацию. Я не говорю, что рефакторинг плох, просто изначально пример выбран странный.JIghtuse
28.10.2016 19:40+1list довольно широко используется в ядре. Во-первых, удобно добавлять/удалять элементы в начало (+ в конец в double linked-list), а индексация не так часто нужна. Во-вторых, объекты бывают довольно тяжёлыми, поэтому (пере-)выделять и копировать память лишний раз не станут (что в случае динамического массива происходит периодически). Думаю, немаловажен и детерминизм списка: мы точно не начнём возиться с памятью, когда нам нужно найти кандидата из процессов на квант времени. Хоть hard real-time и не поддерживается, в ядре важна детерминированность.
Насчёт промахов по кэшу согласен, список плох. В пространстве пользователя почти нет смысла использовать (кроме, опять же, больших объектов). Но, по-видимому, в ядре достоинства перевешивают.
daiver19
28.10.2016 20:01+1Скорее всего так и есть, я же и говорю «99 процентов». Меня просто зацепила ассоциация хорошего вкуса и связного списка. Всё-таки не так много людей работает на уровне ядра, так что для большинства месадж выходит несколько странный.
По поводу объектов, кстати, ничто не мешает хранить указатели в массиве, сами объекты двигать не нужно тогда. Конечно, это лишний переход по указателю, но в списке их гораздо больше. Для добавления в конец и начало есть дек (хотя никогда не тестировал его производительность). Но если для ядра амортизация не подходит, то да, прийдется использовать список.
Siemargl
29.10.2016 23:54-2«Я не пишу на С», «Я не знаком с миром микроконтроллеров», " скачки по указателям, которые мажут мимо кэша" может тебе не стоит пытаться обсуждать вещи, в которых ты не разбираешься?
daiver19
30.10.2016 00:07+1Пост о правилах хорошего вкуса, а не о программировании на С или программировании микроконтроллеров. Не я свернул общение на эту тему. Общие принципы программирования и хороший вкус в общих чертах языконезависимы (в рамках парадигмы, по крайней мере).
OYTIS
28.10.2016 16:52Не то, чтобы очень узкая, особенно если прибавить всякие системные штуки вроде ядра Linux с похожими требованиями. Вы же не ожидали, что Линус будет рассказывать о веб-программировании, правда?
daiver19
28.10.2016 17:05Ядро Линукса — «вещь в себе», и да, это везьма узкоспецифчная вещь. Не приходилось читать его код раньше, но быстрая проверка показала, что они знают о повторном использовании кода. Так что не знаю, о чем тут спорить.
OYTIS
28.10.2016 17:08Ну, собственно, да, там есть своя реализация связного списка, и все ее используют. Кстати, ту же реализацию Линус вставил в git, по-видимому, просто чтобы не плодить зависимостей.
kloppspb
28.10.2016 17:13-3Область примерения C далеко не ограничивается ядерным кодом и мелкими железяками.
И то, что вам кажется нормальным, у меня может вызвать недоумение. Например, зачем тащить какую-то неповоротливую, громоздкую, тормознутую универсальную библиотеку, когда можно написать своё? Которое будет куда лучше приспособлено к конкретной задаче и конкретным данным.
Пример с std::sort, кстати, очень в тему. Как раз то самое громоздкое и пр. Конечно же, под определённые нужды я напишу что-то лучше и эффективней (точней, даже не напишу, а воспользуюсь уже давно готовыми и отлаженными наработками, немного подкрутив их исходя из задачи).daiver19
28.10.2016 18:32+1> Пример с std::sort, кстати, очень в тему. Как раз то самое громоздкое и пр.
Меня очень радует ваша самоуверенность и пренебрежение к работе других людей. Вы ведь никогда не тестировали производительность std::sort, правда? И, кстати, привести пример «приспособления к данным»? А вообще не вижу смысла что-то объяснять, у вас явно есть очень четкая позиция.kloppspb
28.10.2016 18:45Почему же не тестировал? Всё, что я делаю, обязательно проходит кучу разных тестов. Из последнего, например, приходилось гонять C-реализацию хэш-таблицы vs std::map и std::set.
Но такие тесты не всегда имеют смысл. Зачем тестировать плюсовую библиотеку, если её в сишный проект всё равно не приклеишь? Так что STL гоняется чаще любопытства ради, больше приходится сравнивать с другими чисто сишными реализациями.
А где вы тут углядели пренебрежение совсем непонятно. Скорей наоборот, это вы отказываете в здравомыслии всем, кроме разработчиков каких-то отдельных библиотек. Причём совсем с другой областью применения.daiver19
28.10.2016 18:57+3C-реализацию хэш-таблицы vs std::map и std::set.
Я могу не глядя в реализации сказать, что O(1) обычно быстрее O(log n), не говоря уже об ужасной аллокации памяти в деревьях (как в списках, только хуже). Вы, кстати, хэш-таблицу не на списках писали, я надеюсь?
А где вы тут углядели пренебрежение совсем непонятно. Скорей наоборот, это вы отказываете в здравомыслии всем, кроме разработчиков каких-то отдельных библиотек.
Повторюсь, дело не в здравомыслии, а во времени. Я просто не считаю себя умнее группы других людей, работавших над данной конкретной задачей достаточно долгое время. Конечно, если вы пишете на С, то вы не можете пользоваться той же STL, но нужно понимать, что отсутствие хорошей стандартной библиотеки — это недостаток, а не достоинство.avost
28.10.2016 21:02+4>Повторюсь, дело не в здравомыслии, а во времени
При написании уеб-говнокода (херак, херак и в продакшн), да, дело во времени. При написании ядра операционки — в здравомыслии. Линус специалист по второму. Об этом и рассказывает и учит. Зачем ему учить первому? «специалистов» по первому учить не надо, они сами плодятся.
>нужно понимать, что отсутствие хорошей стандартной библиотеки — это недостаток, а не достоинство.
На уровне ядра «стандартная библиотека» — это только то, что они написали сами. Это не достоинство и не недостаток, это реальность. Да и в любом другом случае, стандартная библиотека не появляется ниоткуда божественным провидением. И её, сурпрайз, приходится кому-то писать. И даже херак-херак код далеко не всегда, оу, ещё один сурпрайз, состоит из последовательного применения функций стандартной библиотеки.daiver19
28.10.2016 21:15Ох, еще раз объясню: о времени речь идет когда есть готовая библиотека. Т.е. кто-то утверждает, что «зачем тянуть эту громоздкую библиотеку, лучше сам навелосипедю, т.к. я умный и здравомыслящий», я же с этим не согласен, т.к. какой бы ты ни был умный, вряд ли у тебя найдется достаточно времени для реализации вроде бы базовых вещей на достаточном уровне (если ты, конечно, не занимаешься разработкой соотвественной библиотеки).
Еще короче: велосипедить — плохо.
Если решения нет, то его, естественно, придется создать, я этого ни в коем случае не отрицаю. Просто заметьте, что в наше время львиная доля базовых, не очень базовых и совсем не базовых вещей уже реализована. Хоть свой Bolgenos пилите, ядро Linux вот прям по ссылке доступно.avost
29.10.2016 05:42+2>Т.е. кто-то утверждает, что «зачем тянуть эту громоздкую библиотеку, лучше сам навелосипедю, т.к. я умный и здравомыслящий»,
Кто утверждает? Линус?? Вы серьёзно? Кто этот «кто-то»?
По-моему вы выдумали какую-то глупость и пытаетесь «кого-то» убедить, что это глупость. А о том, что мир не заканчивается и даже не начинается на херак-херак коде даже услышать не в состоянии. Тем не менее, это так. А статья вообще не об этом.
kloppspb
28.10.2016 21:29+1> Вы, кстати, хэш-таблицу не на списках писали, я надеюсь?
Уж не знаю, огорчу или обрадую. Но пишущие на C не обязательно или школьники, только вчера увидевшие компилятор, или олдфаги, впавшие в окончательный маразм :)
selgjos
03.11.2016 09:35что O(1)
Вы, кстати, хэш-таблицу не на списках писали, я надеюсь?
Такие взаимоисключающие параграфы.
Я могу не глядя в реализации сказать,
А ничего, что O(1) стоит 4кб на елемент минимум? А уж про время ресайза я даже не говорю.
не говоря уже об ужасной аллокации памяти в деревьях (как в списках, только хуже).
Ужасные аллокации( что это?) проблемы stl в который не завезли вменяемый аллокатор.
Я просто не считаю себя умнее группы других людей, работавших над данной конкретной задачей достаточно долгое время.
А над какой задачей работали эти люди? И какое-такое «долгое время»?
Конечно, если вы пишете на С, то вы не можете пользоваться той же STL, но нужно понимать, что отсутствие хорошей стандартной библиотеки — это недостаток, а не достоинство.
Это достоинство. При осмысленном использование си — это не язык — это подход.
Ну и кто вообще сказал, что stl — это «хорошая библиотека»/«хороший подход» с т.з. производительности? Это хорошая обобщенная библиотека и продукт ограниченный рамками заранее определённого интерфейса и интеграции.
mikhanoid
28.10.2016 17:08+1А что мешает реализовать std::sort() для массивов без кучи?
khim
29.10.2016 00:35+1Ничто не мешает. Но тот факто что «if the algorithm fails to allocate memory, std::bad_alloc is thrown» толсто намекает на тот факт, что куча — таки нужна.
И вообще — этот один std::sort может породить столько кода, что сожрёт половину места под программу на контроллере — и всё равно будет тормозить потому что обтимизирован под объёмы которые в микроконтроллер просто не влезут.
Стандартные библиотеки почти всегда работают не так уж хорошо, на самом деле. Их используют не потому, что нельзя сделать быстрее, а потому, что сделать быстрее и «правильнее» с точки зрения конкретной задачи банально дольше и сложнее.mikhanoid
29.10.2016 11:01+1Мне кажется, что эволюция средств программирования подошла к такому этапу в своём развитии, на котором мы хорошо представляем тот небольшой оптимальный набор структур данных для коллекций, который покрывает 0.999 потребностей приложений. И мы знаем, как оптимально этот набор реализовывать для тех или иных условий исполнения: микроконтроллеры или многоядерные процессоры, много памяти или мало, и т.д.
Представляется, что проблема культуры Си-программирования именно в том, что люди почти всегда сами реализуют структуры данных для программ, поэтому редко выходят за определённый уровень сложности, за которым начинается совсем другая жизнь и по эффективности, и вообще по возможностям более оптимально выстроить программу.
Как пример: тема юниядер (unikernels) в ML. Ребята умудряются загружать виртуальную машину с полноценным web-сервером за время dns-ответа клиенту.khim
31.10.2016 13:22+1И мы знаем, как оптимально этот набор реализовывать для тех или иных условий исполнения: микроконтроллеры или многоядерные процессоры, много памяти или мало, и т.д.
Знаем, да. Чего мы не знаем — так это способа сделать нечто что будет работать хорошо везде. Можно сделать библиотеку, которая будет отлично работать на микроконтроллерах, но тогда на NUMA-системах она будет «сливать», можно сделать что-то, что будет отлично работать на серверах с 128 процессорами — но тогда на одном она будет тормозить и т.д. и т.п.
Стандартная библиотека же делается так, чтобы везде вести себя «прилично» — в результате максимальной скорости они не достигает нигде. И памяти они тоже использует «немного» — что может быть неприемлемо для микроконтроллеров, и медленно на серверах с сотнями гигабайт памяти.
То, что ML умеет загрузить виртуальную машину за время dns-ответа — это круто, конечно, но говорит скорее о том, что dns-ответ — штука медленная. И, потом, они явно не на микроконтроллере это делают. А сервер на микроконтроллере вполне может понадобится — и что вы будете делать если уже заложились на использование отдельной виртуальной машины для каждого запроса?
longclaps
29.10.2016 08:07Для чистого С есть qsort из stdlib.h
Без «кучи».khim
31.10.2016 13:24Он без кучи, но с, потенциально, очень глубокой рекурсией. А стек на микроконтроллерах ограничен.
kloppspb
31.10.2016 14:11А вы в его потроха загляните. Мало того что рекурсивный, так ещё и жутко пререгруженый всякими ненужностями. Запросто находятся простые примеры, на которых он будет пролетать по сравнению, скажем, со вставками, или его же нерекурсивной реализацией.
mikhanoid
28.10.2016 17:03+1Не все поголовно, конечно, настолько криворуки. Но большинство, действительно, именно настолько криворуки. Нередко на практике сталкиваешься с тем, что какой-нибудь «оптимизированный» Си-код работает медленней, чем его аналог на Lisp или даже на Python. Причина либо в том, что авторы не до конца понимают особенности работы процессоров или памяти, либо в том, что у них не хватает ресурсов написать всё хорошо.
kloppspb
29.10.2016 14:08Не могу понять, какое отношение аргументы уровня «некоторые не могут сделать хорошо» имеют отношение к утверждению «хорошо сделать можно» :-)
Siemargl
30.10.2016 00:01Это настолько фантастическое предположение, что хотелось бы увидеть примеры.
avost
30.10.2016 09:38-3Примеры? Виндовс? :)
Когда ещё были в ходу компакт диски (или ещё раньше, когда флопы), при попытке обращения к дефектному диску колом вставала вся операционка.
А когда у меня на работе была вин2000, я по приходу включал компьютер и шёл к коллегам пить кофе. Как раз к возвращению она успевала загрузиться (не всегда). Вот что она делала? ;) лучше бы она была написана на лиспе. :)MacIn
30.10.2016 18:30+1Код Виндовс — вполне себе неплох. И оформлен хорошо, читется легко. Лично мне он кажется эталоном оформления голого Си кода.
Когда ещё были в ходу компакт диски (или ещё раньше, когда флопы), при попытке обращения к дефектному диску колом вставала вся операционка.
Вы, веротяно, имеете в виду врмена 9х, когда Ос использовала драйвера ДОС, которые действительно могли встать колом.
А когда у меня на работе была вин2000, я по приходу включал компьютер и шёл к коллегам пить кофе.
Когда у меня на работе была В2000, она была эталоном и скорости и стабильности в мире Вин. ХР на том же железе загружалась медленнее. Не представляю, что с ней надо сделать, чтобы загрузка так растянулась.avost
01.11.2016 15:45-2>Код Виндовс — вполне себе неплох. И оформлен хорошо, читется легко. Лично мне он кажется эталоном оформления голого Си кода.
И даже не снятся по ночам переменные вида lpctszStr = «blabla»?
Счастливый вы человек!
>Вы, веротяно, имеете в виду врмена 9х
Ноусэр! Тёмные времена 9х я объехал на варпе (os/2 warp). Это были nt4 и xp.
>Когда у меня на работе была В2000, она была эталоном и скорости и стабильности в мире Вин.
Как вы, наверное, понимаете, мне от этого ничуть не легче.
>Не представляю, что с ней надо сделать, чтобы загрузка так растянулась.
Ничего сверх того, что она сама позволяла. Там вообще мало что было — JDK, эклипс, фотошоп, ну, и вездесущий офис. Ума не приложу что она всё это время делала, но, подозреваю, что на лиспе она сделала бы это быстрее :).
Ещё у 2к любимым развлечением было залочить файло, присланное по самбе так, что и с админскими правами их нельзя было удалить (это не моя делала — соседняя).MacIn
02.11.2016 22:39+1И даже не снятся по ночам переменные вида lpctszStr = «blabla»?
Счастливый вы человек!
А вы не путайте код интерфейса Win32 для юзерспейса и код ядра.
Ноусэр! Тёмные времена 9х я объехал на варпе (os/2 warp). Это были nt4 и xp.
Тогда не верю про «вставала колом вся операционка». Или вы очень вольно используете слова «вся операционка».
Как вы, наверное, понимаете, мне от этого ничуть не легче.
Как вы, наверно, понимаете, это значит, что вы что-то делаете не так.
Ничего сверх того, что она сама позволяла. Там вообще мало что было — JDK, эклипс, фотошоп, ну, и вездесущий офис.
Да хоть 100 прикладных программ. При чем тут загрузка системы?avost
03.11.2016 06:20-1>А вы не путайте код интерфейса Win32 для юзерспейса и код ядра
А код интерфейса Win32 не является виндосом? Как интересно! А чем он является? Может линуксом? Или макосью?
>Тогда не верю про «вставала колом вся операционка»
Пожимая плечами — не может быть потому что не может быть никогда? А, ну-ну. Разумеется.
> Или вы очень вольно используете слова «вся операционка».
Ну, поскольку с вашей точки зиения, как выяснилось, отдельные части виндоса виндосом не являются, то, таки да. Например, таймер, скорее всего, продолжал тикать. «вся операционка, кроме таймера» — так устроит? Только вот это ничего не меняет.
>Как вы, наверно, понимаете, это значит, что вы что-то делаете не так.
Стандартный приём демагогии микрософта. Разумеется, что-то не так. Посмел вставить в сидюк сбоящий диск. Вот я подлец-то какой! На какой страничке eula, говорите, запрещено вставлять в сидюк сбоящий диск?
>Да хоть 100 прикладных программ. При чем тут загрузка системы?
Вот и мне интересно. Впрочем, нет. Не было интересно ни тогда — вызывало только раздражение, не интересно и теперь — проще проголосовать ногами. Всего лишь отметил этот печальный факт.
Siemargl
30.10.2016 19:13+1Какое отношение имеет Windows к скорости Lisp или Python .vs. С? Прошу озаботиться чтением вопроса
avost
31.10.2016 05:45-2Виндовс написана (была) на си. Если бы была написана на лиспе, думаю и то быстрее бы работала. :) вы же просили примеров — это пример.
Siemargl
31.10.2016 09:48Если не теоретизировать, то стандартный pystone (python) работает в 100 раз медленнее, чем drystone, написанный на С.
avost
31.10.2016 12:54Вы часто работаете в тестах? Я — никогда. :)
В конце-концов, даже если вы действительно работаете в тестах, это всего лишь означает, что drystone написан хорошо. А вы просили обратные примеры :).Siemargl
31.10.2016 13:04+1Он написан одинаково. Простой порт с С на Питон.
Я не работаю в тестах, но если у меня есть подозрение, то я предпочитаю проверять, чем выдвигать голословные утверждения.
Так вот, ни один интерпретатор, никогда не сможет получить компилируемую производительность. Обратные утверждения — профанация.
Разумеется, сравнивать можно только одинаковые алгоритмы.avost
31.10.2016 14:02-2>Я не работаю в тестах, но если у меня есть подозрение, то я предпочитаю проверять, чем выдвигать голословные утверждения.
Что проверяете? Вы сомневаетесь, что код может быть написан плохо? Уверяю вас, вы сомневаетесь совершенно напрасно. Можете, хотя бы, посмотреть код автора из этой статьи. Что начальный, что, в общем-то, и конечный.
>Так вот, ни один интерпретатор, никогда не сможет получить компилируемую производительность. Обратные утверждения — профанация.
А я этого и не утверждал. Я утверждал совершенно другое.
>Разумеется, сравнивать можно только одинаковые алгоритмы.
Ну-у-у! Менять правила в ходе игры некрасиво.
BlackRaven86
29.10.2016 23:09Для списков и очередей я бы назвал стандартной queue.h. Но оно такое, полностью на макросах.
stranger777
30.10.2016 13:14Не то, чтобы это прямо стандартная библиотека в полном смысле слова, т.е. включённая в стандарт, да и библиотекой это не назвать, но всё-таки «оно» есть: https://linux.die.net/man/3/queue
kloppspb
30.10.2016 13:56Нет, это не «оно», а одно из многих решений, к тому же для ограниченого круга и, к обсуждаемому вопросу не имеющее ни малейшего отношения.
MacIn
28.10.2016 18:30+1Программисты на С настолько суровы, что не используют библиотеки?
Так вот приведен пример кода такой библиотеки, что не так? Почему вы думаете, что это велосипед?
Ну и в любом случае, связный список — очень плохая структура данных
Серьезно? Вот в NT двусвязный список применяется, например, для связки структур типа EPROCESS в кольцо. Очень удобно и затрат накладных — ноль целых, мал-мала десятых.
Предложите альтернативу, учитывая, что элементы в памяти расположены произвольно, добавление/удаление происходит редко. Отдельный вектор с постоянным ресайзом?daiver19
28.10.2016 18:39Так вот приведен пример кода такой библиотеки, что не так? Почему вы думаете, что это велосипед?
Да, я был не прав, когда писал про 100 процентов. В библиотеке, безусловно, список придется реализовать. Но в реальности всё это давно написано и переписано десятки раз. Поэтому с большой вероятностью можно сказать, что что-то пошло не так, если вам пришлось писать свой список.
Вот в NT двусвязный список применяется, например, для связки структур типа EPROCESS в кольцо. Очень удобно и затрат накладных — ноль целых, мал-мала десятых.
Не знаком с этим, к сожалению. Возможно, это тот случай из 1 процента. А, вероятно, отдельный вектор был бы оптимальнее, с учетом того, что добавление/удаление происходит редко, как вы сами сказали.
SannX
28.10.2016 15:32+2Последний вариант автора, который он считает красивым, подходит только для квадратных массивов. Его решение не универсальное, не подойдет для случая, если row_size != col_size. Потому, как уже отмечалось выше, верх и низ обрабатываем memset, а право/лево в одном цикле. Так будет универсальнее.
poxu
28.10.2016 15:50Да даже не важно, квадратные массивы, или нет.
Код понятным должен быть.
Как нормальные люди рисуют рамку?
Рисуют верхнюю линию, потом нижнюю, потом левую, потом правую.
Или верхнюю, потом правую, потом нижнюю, потом левую. Короче линию за линией рисуют. А тут предлагается написать непонятный код, который к тому же будет медленнее, чем понятный.
Про первоначальный вариант я вообще молчу.
paulstrong
28.10.2016 21:49так чисто для размятия мозга
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
Antervis
28.10.2016 15:41+1второй вариант разыменует нулевой указатель, если его передать.
lorc
28.10.2016 16:43+2Первый тоже. Там везде есть entry->next.
Просто Линус в основном пишет код для ядра. А там немного другой подход к некоторым вещам. Например — не надо передавать нулевые указатели в функции, которые их не ожидают.
Tujh
28.10.2016 15:45-1Мне одному показалось, что решение Линуса не оптимально в случае удаления не последнего элемента из конца списка?
В случае «некрасивого» решения это просто сращивание указателей, не очень красиво, но эффективно, а в случае «красивого» — это проход по всему списку от начала до конца — множество обращений к памяти, практически исключение процессорного кеша из применения, так как элементы списка не обязаны лежать линейно и т.п.? Или я что-то не понял из статьи?
LifeKILLED
28.10.2016 16:24+1Посыл у статьи отличный. Устранение условных операторов особенно полезно в шейдерах. Когда я начал их писать, нашёл для себя много способов избежать их применения.
Shamov
28.10.2016 18:15Честно говоря, после такого введения об указателях на указатели, я не ожидал, что автор остановится на том решении, с которого я бы начал. Я думал, что в итоге он запузырит что-нибудь вроде:
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;
А потом будет рассказывать о хорошем вкусе :)
Но нет… Он вовремя остановился… Видимо, у него и правда есть хороший вкус.
jcmvbkbc
29.10.2016 01:13*(p + (GRID_SIZE-1) * i++) и *(p + (GRID_SIZE-1) * i) — это одно и то же значение, а p++ в конце ломает логику, потому что левая и правая границы должны быть вертикальными, а будут диагональными.
Shamov
29.10.2016 08:42Думаю, обе проблемы имеют общую причину. Я решил избавиться от фигурных скобок, записав все присваивания одной строкой, но совсем забыл про точки следования. Похоже без фигурных скобок не обойтись. Нужно как минимум три строки.
Sixshaman
28.10.2016 23:01+1По той же причине, что и описал автор статьи, мне ужасно не нравится классическая реализация синглтона. Где инициализация происходит только один раз, а дальше if висит бесполезным грузом:
static Singleton getInstance() { if(mInstance == null) { mInstance = new Singleton(); } return mInstance; }
Поэтому я в какой-то момент перешёл на ручную иницализацию при запуске приложения:
static void initInstance() { mInstance = new Singleton(); } static Singleton getInstance() { return mInstance; }Antervis
29.10.2016 11:40синглтон на то и синглтон, чтобы его не приходилось вручную инициализировать и деинициализировать. Пользуйся синглтоном Майерса (в байткоде будет проверка флага на инициализированность) или не пользуйся синглтоном вообще. В современных процах есть branch prediction на худой конец.
Barafu
29.10.2016 12:29static const Singleton& getInstance() { static Singleton instance; return instance; }
И никаких висячих if.
Antervis
31.10.2016 06:13там внутри будет if. Это и есть синглтон Майерса
Barafu
31.10.2016 10:30Нууу да. Там выходит что-то типа такого:
Скрытый текст`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`
NoRegrets
28.10.2016 23:14+4Скажу крамольную вещь — лучше писать код который парсится человеком быстрее, нежели тот что быстрее выполняется, имхо. Это, конечно, не касается тех мест, где скорость выполнения имеет значение. Да, чем короче и лаконичнее код, тем лучше. Однако читабельность и понимабельность кода, по-моему, гораздо важнее. В первом примере, немало людей споткнулись на улучшенном варианте, что говорит о том, что он сложен для восприятия.
insensible
28.10.2016 23:48+1Придерживаюсь такого же подхода. Программа должна быть читаемой и объяснять _что_ требуется выполнить, а не _как_. Оптимизировать нужно только те места, где реально необходима оптимизация. На С сам давно не писал, но могу предположить, что в приведенных выше примерах компилятор вполне может выполнить оптимизацию так, чтобы эти примеры выполнялись абсолютно одинаково как по скорости, так и по результату. А если не видно разницы — зачем усложнять понимание?
Error1024
29.10.2016 01:08«Инициализация краёв сетки со вкусом» — серьезно?
Я бы такой говнокод как в первом и во втором варианте не написал бы никогда в принципе, даже в детстве, на моем спектруме это бы просто год работало бы.
Как вообще полное решение могло в голову автору прийти?
DarkGenius
29.10.2016 07:49В последнем примере кода с сеткой можно сократить число итераций на 1, воспользовавшись тем, что есть пересечения краев. Но придется учесть частный случай, когда сетка состоит из одного элемента.
Alex_info
29.10.2016 08:08Пример конечно интересный, но попробуйте обойтись без условия если матрица не квадратная, т.е. если
GRID_SIZE_X != GRID_SIZE_Y, что обычно встречается на практике.
Как тут было замечено строки (или столбцы, в зависимости от последовательности выделения памяти) лучше обнулять с помощью memset(...), а потом столбцы (или строки) в цикле. Нет условий и максимальная скорость работы.akzhan
29.10.2016 08:44де факто там получится оптимально первая строка кроме последней ячейки, потом цикл по правому краю, кроме последней строки (+ левый край через адрес+1), потом нижняя строка, кроме первого элемента )
а вот использовать цикл или memset — не так уж и важно. современные компиляторы очень хорошо оптимизируют такой код, и for может оказаться быстрее за счет использования векторных инструкций. библиотека может оказаться не оптимизированной под ваш target.
Shamov
29.10.2016 17:42+1Цикл по-любому лучше. Из моего примера, приведённого ниже, оптимизатор вообще убирает первый цикл для матриц шириной 100 и менее элементов. Без всяких там векторных инструкций. Просто тупо забивает строку в матрице 8-байтой константой, сдвигаясь на 8 байт в каждой следующей инструкции. Чуть больше десяти инструкций для матрицы размером 100.
Shamov
29.10.2016 09:49Если вообще без условий, то нужно два цикла:
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; }
teemour
29.10.2016 13:20недурновкусный код, конечно, красиво выглядит, но, может быть, удобнее явно видеть обработаны ли «особые случаи»
mav5555
30.10.2016 20:40>А как вы можете применить концепцию «хорошего вкуса» в своих проектах?
К примеру, на CMS Drupal функционал каталога можно реализовать (1) кастомным кодом, (2) используя контриб модули Ubercart или Commerce, (3) используя встроенные штатные модули Taxonomy + Views.
Третий вариант, на мой взгляд, это и есть концепция «хорошего вкуса». Позволяет сделать именно то, что нужно. Не тянет лишних зависимостей или лишнего функционала, как у второго варианта. Безопаснее и легче в поддержке по сравнению с первым.
NIKOSV
31.10.2016 07:45«Написать код понятный машине это фигня, а вот написать код понятный человеку — это исскуство» (с) не помню кто
ИМХО, если нет супер критических требований по производительности, можно забить на все эти оптимизации по уменьшению количеству проходов по циклам, условий и т.д… На первом месте должна стоять простота, читабельность и понятность кода, даже в ущерб производительности и меньшему объему кода (понятное дело что совсем маргиналить с трема влоежными циклами или еще чем-то — не надо). В 90% задачах разницы в скорости все-равно не будет видно а более короткий код далеко не всегда более читабельный код.
Scf
31.10.2016 22:22-1И правда, очень красивое решение, и лучше не сделаешь, как ни крути.
- находим в памяти указатель на удаляемый элемент
- перезаписываем этот указатель следующим
claygod
Побольше бы примеров — реально интересная тема.