company_banner

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

Original author: Bian Barto
  • Translation
«Вкус — это способность судить о прекрасном»
И. Кант

Дирк Хондел, один из тех, кто стоял у истоков Linux, однажды сказал о создателе Linux Линусе Торвальдсе: «Линус не только блестящий программист: у него хороший вкус. Торвальдс находит простые и разумные пути решения проблем, умеет всё «разложить по полочкам». Сложные вещи он делает простыми. По-моему, это и есть главное отличие превосходного программиста от просто хорошего».

image

В недавнем интервью, примерно на 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;
	}
}

Хотя всё работало как надо, было понятно, что код далеко не идеален. А именно, вот основные проблемы этого фрагмента:

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

  2. Код неэффективен. При условии, что переменная 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;
}

В этом коде в каждой итерации цикла инициализируется четыре разных граничных элемента. Код просто устроен и весьма эффективен в плане производительности. Его легко читать. Этот вариант не идёт ни в какое сравнение с первым и даже со вторым.

В итоге результатами я остался абсолютно доволен.

Есть ли у меня вкус к программированию?


И что же, теперь я программист, код которого отвечает правилам хорошего вкуса?

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

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

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

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

А как вы можете применить концепцию «хорошего вкуса» в своих проектах?
RUVDS.com
RUVDS – хостинг VDS/VPS серверов

Comments 145

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

      Главное при этом не забывать высвободить память.
        +3

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

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

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

              +2
              Хм… А если элемента entry нет в списке?
              Все свалится.
                +1

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

                      0

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


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

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

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

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

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

                          –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;
                          	}
                          }
                          
                            +19

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

                              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;
                              	}
                              }
                              


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

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

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

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

                                Второй пример — отличный контраргумент в споре о том, нужны ли алгоритмы. Никакой вменяемый программист, который понимает работу алгоритмов, не будет реализовывать n^2 решение для задачи, явно требующей линейного времени. Да и вообще, подозреваю что большинство бы реализовало сразу же последний вариант, т.к. он очевиден. Так что здесь скорее не о вкусе, а вообще о понимании, что ты делаешь.
                                  0
                                  > Реализация своего списка является плохим вкусом в 100 процентах ситуаций

                                  Для тех языков, в которых всё есть из коробки — да, но не для C.
                                    –8
                                    Программисты на С настолько суровы, что не используют библиотеки? Ну и в любом случае, связный список — очень плохая структура данных. Особенно если ты стеснен в ресурсах (если нет, зачем вообще писать на С?)
                                      +1
                                      Что значит «плохая структура данных»? У нее есть своя область применения, в т.ч. и в системном программировании. Linux-сообшество — достаточно открытое на самом деле, если вы предложите (и реализуете) более эффективную альтернативу, к вам наверняка прислушаются.
                                        –3
                                        Конечно, есть, поэтому и 99 процентов вместо 100. Но в целом нужно очень хорошо понимать, зачем тебе здесь список. В посте же речь идет о хорошем вкусе в целом (просто от Линуса). И вот использование списков и велосипедная реализация стандартных структур данных — весьма плохой вкус.
                                          +1
                                          Вкус еще имеет отношение к языку и предметной области. Dependency hell в C совершенно не приветствуется, тем более ядру желательно не иметь никаких зависимостей и адаптировать все под свои задачи.
                                        +6
                                        Назовите хоть одну стандартную C-библиотеку для списков? Хэшей? Деревьев? Очередей?
                                        Ну хорошо, для линуксовой kernel-моды есть kfifo и прочее. Но на уровень чуть выше — уже пустота.

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

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

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

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

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


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

                                                        +1
                                                        Скорее всего так и есть, я же и говорю «99 процентов». Меня просто зацепила ассоциация хорошего вкуса и связного списка. Всё-таки не так много людей работает на уровне ядра, так что для большинства месадж выходит несколько странный.
                                                        По поводу объектов, кстати, ничто не мешает хранить указатели в массиве, сами объекты двигать не нужно тогда. Конечно, это лишний переход по указателю, но в списке их гораздо больше. Для добавления в конец и начало есть дек (хотя никогда не тестировал его производительность). Но если для ядра амортизация не подходит, то да, прийдется использовать список.
                                                          –2
                                                          «Я не пишу на С», «Я не знаком с миром микроконтроллеров», " скачки по указателям, которые мажут мимо кэша" может тебе не стоит пытаться обсуждать вещи, в которых ты не разбираешься?
                                                            +1
                                                            Пост о правилах хорошего вкуса, а не о программировании на С или программировании микроконтроллеров. Не я свернул общение на эту тему. Общие принципы программирования и хороший вкус в общих чертах языконезависимы (в рамках парадигмы, по крайней мере).
                                                    0
                                                    Не то, чтобы очень узкая, особенно если прибавить всякие системные штуки вроде ядра Linux с похожими требованиями. Вы же не ожидали, что Линус будет рассказывать о веб-программировании, правда?
                                                      0
                                                      Ядро Линукса — «вещь в себе», и да, это везьма узкоспецифчная вещь. Не приходилось читать его код раньше, но быстрая проверка показала, что они знают о повторном использовании кода. Так что не знаю, о чем тут спорить.
                                                        0
                                                        Ну, собственно, да, там есть своя реализация связного списка, и все ее используют. Кстати, ту же реализацию Линус вставил в git, по-видимому, просто чтобы не плодить зависимостей.
                                                      –3
                                                      Область примерения C далеко не ограничивается ядерным кодом и мелкими железяками.

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

                                                      Пример с std::sort, кстати, очень в тему. Как раз то самое громоздкое и пр. Конечно же, под определённые нужды я напишу что-то лучше и эффективней (точней, даже не напишу, а воспользуюсь уже давно готовыми и отлаженными наработками, немного подкрутив их исходя из задачи).
                                                        +1
                                                        > Пример с std::sort, кстати, очень в тему. Как раз то самое громоздкое и пр.
                                                        Меня очень радует ваша самоуверенность и пренебрежение к работе других людей. Вы ведь никогда не тестировали производительность std::sort, правда? И, кстати, привести пример «приспособления к данным»? А вообще не вижу смысла что-то объяснять, у вас явно есть очень четкая позиция.
                                                          0
                                                          Почему же не тестировал? Всё, что я делаю, обязательно проходит кучу разных тестов. Из последнего, например, приходилось гонять C-реализацию хэш-таблицы vs std::map и std::set.
                                                          Но такие тесты не всегда имеют смысл. Зачем тестировать плюсовую библиотеку, если её в сишный проект всё равно не приклеишь? Так что STL гоняется чаще любопытства ради, больше приходится сравнивать с другими чисто сишными реализациями.

                                                          А где вы тут углядели пренебрежение совсем непонятно. Скорей наоборот, это вы отказываете в здравомыслии всем, кроме разработчиков каких-то отдельных библиотек. Причём совсем с другой областью применения.
                                                            +3
                                                            C-реализацию хэш-таблицы vs std::map и std::set.

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

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

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

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

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

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

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

                                                                Уж не знаю, огорчу или обрадую. Но пишущие на C не обязательно или школьники, только вчера увидевшие компилятор, или олдфаги, впавшие в окончательный маразм :)
                                                                  0
                                                                  что O(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

                                                                                        Какая экспрессия. Человек спросил «Спольски врет?» — это не я предложил такую форму общения. Замечу, слово «врет» не обязательно означает намеренную ложь. Я всего лишь сказал, что такое-то и такое-то утверждение не соответствует действительности, остальное — ваше воображение дорисовывает. Будьте спокойнее.
                                                                                          0
                                                                                          Так еще, на всякий случай. Вот цитата из 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.
                                                                          +1
                                                                          Какое отношение имеет Windows к скорости Lisp или Python .vs. С? Прошу озаботиться чтением вопроса
                                                                            –2
                                                                            Виндовс написана (была) на си. Если бы была написана на лиспе, думаю и то быстрее бы работала. :) вы же просили примеров — это пример.
                                                                              +1
                                                                              давайте на секунду вспомним, что на уровне ядра лисп попросту не заработает
                                                                                –1
                                                                                Неочевидно. Даже если железные лисп-машины в расчёт не принимать.
                                                                                0
                                                                                Если не теоретизировать, то стандартный pystone (python) работает в 100 раз медленнее, чем drystone, написанный на С.
                                                                                  0
                                                                                  Вы часто работаете в тестах? Я — никогда. :)
                                                                                  В конце-концов, даже если вы действительно работаете в тестах, это всего лишь означает, что drystone написан хорошо. А вы просили обратные примеры :).
                                                                                    +1
                                                                                    Он написан одинаково. Простой порт с С на Питон.

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

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

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

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

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

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

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

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

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

                                                                          0
                                                                          Оно же только в GNU/BSD, насколько помню.
                                                                            0

                                                                            Да, эта штука, в основном, в никсах встречается.

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

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

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

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

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

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

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

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


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


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


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

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

                                                                          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
                                                                          
                                                                          +1
                                                                          второй вариант разыменует нулевой указатель, если его передать.
                                                                            0
                                                                            Это псевдокод.
                                                                              +2
                                                                              Первый тоже. Там везде есть entry->next.

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

                                                                                  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;
                                                                                  

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

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

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

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

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

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

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

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


                                                                                            Скрытый текст
                                                                                            `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 мешает, то, наверное, можно, презрев приличия, сохранить в этом месте локальную копию указателя на объект. Только с потоками не налажать.
                                                                                        +4
                                                                                        Скажу крамольную вещь — лучше писать код который парсится человеком быстрее, нежели тот что быстрее выполняется, имхо. Это, конечно, не касается тех мест, где скорость выполнения имеет значение. Да, чем короче и лаконичнее код, тем лучше. Однако читабельность и понимабельность кода, по-моему, гораздо важнее. В первом примере, немало людей споткнулись на улучшенном варианте, что говорит о том, что он сложен для восприятия.
                                                                                          +1
                                                                                          Придерживаюсь такого же подхода. Программа должна быть читаемой и объяснять _что_ требуется выполнить, а не _как_. Оптимизировать нужно только те места, где реально необходима оптимизация. На С сам давно не писал, но могу предположить, что в приведенных выше примерах компилятор вполне может выполнить оптимизацию так, чтобы эти примеры выполнялись абсолютно одинаково как по скорости, так и по результату. А если не видно разницы — зачем усложнять понимание?
                                                                                            0
                                                                                            компилятору сложновато даются оптимизации при работе с указателями
                                                                                          0
                                                                                          «Инициализация краёв сетки со вкусом» — серьезно?
                                                                                          Я бы такой говнокод как в первом и во втором варианте не написал бы никогда в принципе, даже в детстве, на моем спектруме это бы просто год работало бы.
                                                                                          Как вообще полное решение могло в голову автору прийти?
                                                                                            0
                                                                                            В последнем примере кода с сеткой можно сократить число итераций на 1, воспользовавшись тем, что есть пересечения краев. Но придется учесть частный случай, когда сетка состоит из одного элемента.
                                                                                              0
                                                                                              Пример конечно интересный, но попробуйте обойтись без условия если матрица не квадратная, т.е. если
                                                                                              GRID_SIZE_X != GRID_SIZE_Y, что обычно встречается на практике.
                                                                                              Как тут было замечено строки (или столбцы, в зависимости от последовательности выделения памяти) лучше обнулять с помощью memset(...), а потом столбцы (или строки) в цикле. Нет условий и максимальная скорость работы.
                                                                                                0

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


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

                                                                                                  +1
                                                                                                  Цикл по-любому лучше. Из моего примера, приведённого ниже, оптимизатор вообще убирает первый цикл для матриц шириной 100 и менее элементов. Без всяких там векторных инструкций. Просто тупо забивает строку в матрице 8-байтой константой, сдвигаясь на 8 байт в каждой следующей инструкции. Чуть больше десяти инструкций для матрицы размером 100.
                                                                                                  0
                                                                                                  Если вообще без условий, то нужно два цикла:
                                                                                                  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;
                                                                                                  }
                                                                                                  
                                                                                                  0
                                                                                                  недурновкусный код, конечно, красиво выглядит, но, может быть, удобнее явно видеть обработаны ли «особые случаи»
                                                                                                    0
                                                                                                    чем больше ветвлений if тем медленнее код! меньше ifov быстрее код!
                                                                                                      0
                                                                                                      Первый код как манная каша — все понятно, в горле не застрянет. А второй дает возможность подумать, распробовать… Именно этот «вкус» я думаю и имел в виду Торвальдс. Согласен, вкуснее.
                                                                                                        0
                                                                                                        Зато первый читается легче.
                                                                                                        0
                                                                                                        >А как вы можете применить концепцию «хорошего вкуса» в своих проектах?

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

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

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

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

                                                                                                              –1

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


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

                                                                                                              Only users with full accounts can post comments. Log in, please.