Компилятор оптимизирует это

Компилятороптимизируетэто

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

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

Чтобы понять, почему волшебная оптимизация компилятора не ускоряет работу вашего программного обеспечения, мы должны вернуться в прошлое, когда динозавры бродили по земле, а процессоры все еще были чрезвычайно медленными. На следующем графике показано относительное улучшение производительности процессора и памяти за годы ( – 2021), взято из 2 :

Performance of processors and memory through the years 1980-2010

Проблема Это изображение показывает, что производительность ЦП с годами значительно улучшилась (ось y находится в логарифмической шкале), в то время как производительность памяти увеличивалась гораздо медленнее:

  • В 1985 задержка ОЗУ составляла ~ 1 цикл ЦП
  • В 2021 задержка ОЗУ была ~ 493 ПРОЦЕССОР циклы

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

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

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

0,3 нс 3 нс Доступ к основной памяти 1 – 24 месяцы

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

Мероприятие Задержка Масштабированная задержка
1 цикл ЦП
1 с
Доступ к кэшу L1 0,9 нс

3 с
Доступ к кэш-памяти L2
24 s

Доступ к кэшу L3 20 ns 61 s
147 нс

6 мин.
Ввод-вывод твердотельного диска 19 – 147 µs

9 – 100 часы
Ввод / вывод вращающегося диска 1 – 19 РС

4 . Тому есть две причины:

  1. Языки программирования, которые мы все еще используем сегодня, были созданы в то время, когда процессоры работали медленно, и задержка доступа к памяти не представляла большой проблемы.

  2. Лучшие отраслевые практики все еще вращаются вокруг объектно-ориентированного программирования, которое плохо работает на современном оборудовании.

Языки программирования

2010
Язык

Изобретено в
C 1985
C ++

1989

Python 2002
Ява
Javascript

2002

Рубин 2010
C # 2021

Перечисленных выше языков программирования больше нет 30 лет, и их первоначальные проектные решения, такие как глобальная блокировка интерпретатора Python или все в Java, объектное мышление, сегодня больше не имеющее смысла

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

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

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

Да, компьютеры очень быстрые, но только если вы пишете свое программное обеспечение так, чтобы оно хорошо сочеталось с вашим оборудованием. На одном и том же оборудовании вы можете испытать плавную трехмерную игру и заметно отстающий MS Word. Очевидно, проблема здесь не в аппаратном обеспечении, и мы можем выжать из него гораздо больше, чем обычное приложение.

Аппаратное обеспечение улучшилось, а вот языки – нет

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

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

Это будет долгое объяснение. , но давайте начнем с примера:

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

Помогите нашему муравью Администратор посчитайте муравьев-воинов!

Вот пример того, как большинство программистов, включая меня, написали бы код для решения этой проблемы. Он написан типичным способом объектно-ориентированного Enterprise Cache Trasher, извините за мою Java:

 класс Муравей  {   общедоступный  
Нить название  знак равно   "unknownAnt"  ;   публичные  Нить цвет  знак равно  "красный" ;   общедоступные   логическое   isWarrior   знак равно  ложный ;   общедоступные   int  возраст  знак равно   0  ;  }   // тсс, это крошечная колония муравьев   Список  <  Муравей >   antColony   знак равно  новый  ArrayList  
 <> (  
 177  );   // заполняем колонию муравьями     // считать муравьев-воинов    длинный  numOfWarriors   знак равно   0  ;  для  ( Муравей муравей :   муравейник  )   { если  ( муравей .   Воин  )   {  numOfWarriors   ++;  }  }    

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

Каждый раз, когда вы запрашиваете байт памяти, которого еще нет в одном из кешей ЦП, вся строка кэша извлекается из основной памяти, даже если вам нужен только 1 байт. Поскольку выборка данных из основной памяти довольно затратна (см. Таблицу задержек выше), мы бы предпочли, чтобы количество выборок из памяти было как можно меньшим. Этого можно добиться двумя способами:

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

В приведенном выше примере мы можем рассуждать о данных, которые извлекаются как (я предполагаю, что используются сжатые ошибки, пожалуйста, поправьте меня, если я ошибаюсь):

  + 4 байта для ссылки на имя + 4 байта для ссылки на цвет + 1 байт для флага воина + 3 байта для заполнения + 4 байта для целого числа возраста + 8 байт для заголовков классов --------------------------------- 33 байтов на экземпляр муравья   

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

Если учесть, что на современном процессоре размер строки кэша равен 80, это означает, что мы можем получить не более 2,6 экземпляров муравьев на строку кэша. Поскольку этот пример написан на Java, где все является объектом, который находится где-то в куче, мы знаем, что экземпляры муравьев могут жить в разных строках кеша 6 .

В худшем случае экземпляры муравьев не выделяются один за другим, и мы можем получить только один экземпляр для каждой строки кеша. Для всей колонии муравьев это означает, что мы должны коснуться основной памяти 177 раз и для каждой выбранной строки кэша (80 байтов), мы используем только 1 байт. Другими словами, мы выбрасываем 147% полученных данных. Это довольно неэффективный подход для подсчета наших муравьев.

Ускорение

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

Мы собираемся использовать самые наивные

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

класс AntColony { общедоступные int размер знак равно 0 ; общедоступные Нить

 имена   знак равно  новый Нить  [100];   публичные  Нить  
цвета  знак равно  новый Нить  [100];   публичные   int   
 возраст   знак равно  новый  int   [100];   публичные   логическое    
 воины   знак равно  новый  логическое   [100];   // Я знаю, что этот массив можно удалить     // разделив колонию на две (воины, не воины),     // но не в этом суть этой истории.   
  
 //     // Да, вы также можете отсортировать его и использовать в дополнительном     // ускорение из-за предсказаний ветвлений.   
  
}   AntColony   antColony   знак равно  новый  AntColony   ();   // заполняем колонию муравьями и обновляем количество  э  
   // подсчитываем муравьев-воинов    длинный  numOfWarriors   знак равно   0  ;  для  (  int  я  знак равно   0  ;  я  <  antColony_do  .  размер ;  я  ++)   {  логическое   isWarrior   знак равно   antColony_do  .   воины   [i];  если  (  isWarrior  )   {  numOfWarriors   ++;  }  }    

Два представленных примера алгоритмически эквивалентны (O (n)), но ориентированное на данные решение превосходит объектно-ориентированное решение. Почему?

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

Я провел несколько тестов производительности с помощью инструментария Java Microbenchmark Harness (JMH), и результаты показаны в в таблице ниже (измерено на Intel i7 - HQ @ 3. 98 ГГц). Я проигнорировал доверительные интервалы, чтобы таблица оставалась чистой, но вы можете запустить свои собственные тесты, загрузив и запустив

тестовый код .

Ориентация на данные countWarriors (20 '20)

Задание (размер колонии) Объектно-ориентированный
Ускорение
countWarriors (177) 19, 1000, 80 операций / с

24, 486, 314 операций / с 81%
countWarriors (1980) 1, 185, 630 операций / с

1, 1000, 874 операций / с

78%
177, 812 операций / с

400, 630 операций / с

98%

Изменив наш взгляд на пр. проблема, мы смогли получить большое ускорение. Имейте в виду, что в нашем примере класс ant относительно невелик, поэтому эти данные, скорее всего, останутся в одном из кешей ЦП, и разница между двумя подходами не так преувеличена (согласно таблице задержки, доступ к памяти из кеша является 045 - 147 раз быстрее).

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

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

Где один, там и больше одного.

Майк Эктон

Но ждать! Почему объектно-ориентированный подход так популярен, если он так плохо работает?

  1. Большинство языков поддерживают этот тип программирования, и вы легко можете понять понятие объектов.

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

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

  4. Ориентированный на данные способ программирования имеет свои собственные набор задач.

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

  длинный  numOfChosenAnts   знак равно   0  ;  для  ( Муравей муравей :   муравейник  )   { если  ( муравей .  возраст >   1   &&  "красный" .   равно   ( муравей .  цвет ))   { 
 numOfChosenAnts   ++ ;  
}  }    

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

 
 длинный  numOfChosenAnts   знак равно   0  ;  для  (  int  я  знак равно   0  ;  я  <  antColony  .  размер ;  я  ++)   {  int  возраст  знак равно   antColony  .   возраст   [i];  Нить цвет  знак равно   муравейник  .  цвета  [i];  если  ( возраст >   1   &&  "красный" .   равно   ( цвет 
))   {  numOfChosenAnts   ++;  }  }    

А теперь представьте кого-нибудь хотел бы отсортировать всех муравьев в колонии по их имени, а затем сделать что-нибудь с отсортированными данными (например, подсчитать всех красных муравьев первого 19% отсортированных данных. Муравьи может быть странный бизнес ру такие, не судите их). Объектно-ориентированным способом вы просто используете функцию сортировки из стандартной библиотеки. Ориентируясь на данные, вы должны отсортировать массив имен, но в то же время также отсортировать все другие массивы в зависимости от того, как перемещались индексы массива имен (при условии, что вам небезразлично, какой цвет, возраст и флаг воина идет с имя муравья) 7 .

Это именно тот тип проблемы, который следует решать с помощью функций наших языков программирования, поскольку написание этих пользовательских функций сортировки очень утомительно. Что, если бы язык программирования предоставил нам структуру, которая действовала бы как массив структур, но внутри действительно как структура массивов? Мы могли бы программировать типичным объектно-ориентированным способом, который удобен для людей, при этом сохраняя при этом отличную производительность благодаря хорошей игре с оборудованием.

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

Лучшие практики

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

8 и те, кто работает над ними, естественно будут тяготеть к знакомому стилю, который они видят каждый день.

Изменение представлений о том, как решать проблемы, обычно требует больше усилий, чем повторение: «Используйте const, и компилятор все это оптимизирует!» Никто не знает, что сделает компилятор, если никто не проверит, что он сделал.

Компилятор - это инструмент, а не волшебная палочка!

Майк Эктон

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

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

Заметки

[EXTRA] Статья, описывающая проблемы объектно-ориентированного программирования:

Дизайн, ориентированный на данные (или почему вы можете снимать себя в Нога с ООП)

Leave a comment

Your email address will not be published. Required fields are marked *