Слияние кода завершено, страница обновится автоматически
Этот документ описывает лучшие практики для написания высокопроизводительного кода на Go.
Хотя будут обсуждаться способы оптимизации отдельных сервисов (кэширование и т. д.), дизайн высокопроизводительных распределённых систем выходит за рамки этой работы. Уже существуют подробные тексты о мониторинге и дизайне распределённых систем. Эта тема охватывает совершенно другой набор исследований и уступок в дизайне.
Весь контент лицензирован под CC-BY-SA.
Эта книга разделена на разные разделы:
Мы можем резюмировать эти три раздела как:
Я пишу этот раздел первым, потому что это самый важный шаг. Должны ли вы это делать?
Любая оптимизация имеет свою стоимость. Обычно эта стоимость выражается в терминах сложности кода или когнитивной нагрузки — оптимизированный код редко бывает проще, чем неоптимизированная версия.
Но есть ещё один аспект, который я назову экономикой оптимизации. Как программист, ваше время ценно. Существует стоимость упущенной возможности других вещей, которые вы могли бы сделать в своём проекте, ошибок, которые вы могли бы исправить, улучшений, которые вы могли бы добавить. Оптимизировать вещи весело, но это не всегда правильная задача. Производительность программы — это характеристика, но также важно её завершение и правильность выполнения.
Выберите самое важное, над чем вам следует работать. Иногда это не оптимизация использования процессора, а оптимизация пользовательского опыта. Что-то такое простое, как добавление индикатора выполнения или изменение страницы, чтобы она работала быстрее, выполняя вычисления в фоновом режиме после её отображения.
Иногда это будет очевидно: отчёт, который генерируется каждый час и занимает 3 часа для завершения, менее полезен, чем тот, который завершается менее чем за час.
Только то, что что-то легко оптимизировать, не означает, что это стоит делать. Игнорирование простого — это действительная стратегия разработки.
Рассматривайте это как оптимизацию вашего времени.
Вы решаете, что оптимизировать и когда оптимизировать. Вы можете перемещать рычаг между «быстрым программным обеспечением» и «быстрой разработкой».
Люди слушают и повторяют, не думая, что «преждевременная оптимизация — корень всех зол», но они игнорируют полный контекст фразы.
«Программисты тратят огромное количество времени, думая или беспокоясь о скорости некритических частей своих программ, и эти попытки быть более эффективными на самом деле оказывают большое негативное влияние, когда учитываются обслуживание или отладка. Мы должны забыть о небольших улучшениях, скажем, 97% времени: преждевременная оптимизация — корень всего зла. Однако мы не должны упускать возможность оптимизации в этих критических 3%». — Кнут.
https://www.youtube.com/watch?time_continue=429&v=3WBaY61c9sE
— Не игнорируйте простые оптимизации. — Больше знаний об алгоритмах и структурах данных делают оптимизацию более «простой» или «очевидной».
«Должны ли вы оптимизировать свой код? Да, но только если проблема важна, программа действительно медленная, и есть надежда, что можно улучшить, сохраняя при этом точность, надёжность и ясность». — Практика программирования, Керниган и Пайк.
Преждевременная оптимизация также может повлиять на вас, заставляя принимать определённые решения. Окончательный код может быть сложнее изменить, если требования изменятся, и его будет сложнее отбросить (ошибка стоимости), если это необходимо.
Оценка производительности BitFunnel показывает данные, которые делают этот баланс. Решая проблему на соответствующем уровне.
Эта книга будет говорить в основном о том, как уменьшить использование процессора, использование памяти и задержку. Важно отметить, что редко можно достичь всех трёх целей одновременно. Возможно, время процессора будет быстрее, но теперь ваша программа использует больше памяти. Может быть, вам нужно уменьшить объём памяти, но тогда программа будет работать медленнее.
[Закон Амдала] говорит, что сосредоточьтесь на узких местах. Если вы удвоите скорость подпрограммы, которая занимает только 5% времени выполнения, это приведёт к общему улучшению всего на 2,5%. С другой стороны, ускорение подпрограммы, занимающей 80% времени, всего на 10%, улучшит время выполнения почти на 8%. Профилирование поможет вам определить, где действительно тратится время.
При оптимизации вы хотите уменьшить количество работы, которую должен выполнять процессор. Quick sort работает быстрее, чем Bubble sort, потому что решает ту же задачу (сортировку) за меньшее количество шагов. Это более эффективный алгоритм. Вы уменьшили работу, которую должен выполнить процессор, чтобы получить тот же результат.
Настройка программы, такая как оптимизация компилятора, обычно приводит лишь к небольшому сокращению общего времени выполнения. Большие выгоды почти всегда будут связаны с изменением алгоритма или изменением структуры данных, фундаментальным изменением в том, как организован ваш код. [Закон Проебстинга] гласит, что производительность компиляторов удваивается каждые 18 лет, что явно контрастирует с (слегка неверно истолкованным) Законом Мура, который гласит, что производительность процессоров удваивается каждые 18 месяцев. Улучшения алгоритмов работают в гораздо больших масштабах. Алгоритмы смешанного целочисленного программирования [улучшились в 30 000 раз между 1991 и 2008 годами]. В качестве конкретного примера рассмотрим [этот анализ] замены алгоритма геопространственной грубой силы, описанного в блоге Uber, на более подходящую специализацию для поставленной задачи. Нет изменения в компиляторе, которое привело бы к эквивалентному увеличению производительности.
TODO: Оптимизация различий в алгоритмах с плавающей запятой FFT и MMM в gttse07.pdf
Профилировщик может показать, что много времени тратится на определённую подпрограмму. Это может быть тяжёлая подпрограмма или лёгкая подпрограмма, которая вызывается очень часто. Вместо того чтобы сразу пытаться ускорить эту подпрограмму, посмотрите, можете ли вы уменьшить количество вызовов или полностью исключить её. Мы обсудим конкретные стратегии оптимизации в следующем разделе.
Три вопроса оптимизации:
Работа Джона Бентли 1982 года «Написание эффективных программ» рассматривала оптимизацию программ как инженерную проблему: Измерьте. Проанализируйте. Улучшите. Проверьте. Итерации. Некоторые из его советов автоматически применяются компиляторами. Работа программиста заключается в применении преобразований, которые компиляторы не могут сделать.
Есть резюме книги:
и правил настройки программ:
Когда вы думаете об изменениях, которые вы можете внести в свою программу, есть две основные возможности: вы можете изменить данные или вы можете изменить свой код.
Изменение данных означает добавление или изменение представления данных, которые вы обрабатываете. С точки зрения производительности некоторые из них приведут к... Изменение сложности O(), связанной с различными аспектами структуры данных
Идеи для улучшения структуры данных:
Классический пример этого — хранение длины связанного списка в поле в корневом узле. Поддерживать её в актуальном состоянии требует немного больше работы, но запрос длины становится простым доступом к полю вместо поиска по всему списку со сложностью O(n). Ваша структура данных может иметь аналогичное улучшение: немного дополнительной работы над некоторыми операциями в обмен на повышение производительности в распространённом случае использования.
Аналогично, можно хранить указатели на часто используемые узлы вместо выполнения дополнительных поисков. Это охватывает такие вещи, как «обратная» ссылка в двусвязном списке, чтобы удаление узлов имело сложность O(1). Некоторые списки переходов хранят «указатель поиска», где вы сохраняете указатель на то место, где вы недавно находились в вашей структуре данных, предполагая, что это хорошая отправная точка для следующей операции.
Большинство структур данных предназначены для одного типа запросов. Если вам нужны два типа запросов, наличие дополнительного «представления» ваших данных может быть большим улучшением. Например, набор structs может иметь первичный ID (integer), который вы используете для поиска в срезе, но иногда вам нужно искать по вторичному ID (string). Вместо перебора среза вы можете улучшить свою структуру данных с помощью карты от строки к ID или непосредственно к рассматриваемому struct.
Например, поддержание фильтра Блума для всех вставленных элементов может позволить вам быстро возвращать «нет совпадений» при поиске. Они должны быть маленькими и быстрыми, чтобы не перегружать остальную часть структуры данных. (Если поиск в основной структуре данных дёшев, стоимость фильтра Блума превысит любую экономию.)
На более крупном уровне внутренний или внешний кэш (например, memcache) может помочь. Он может быть излишним для одной структуры данных. Мы поговорим о кэшах позже.
Этот тип изменений полезен, когда данные, которые необходимо сохранить, дёшевы и просты в поддержании в актуальном состоянии.
Это все чёткие примеры «меньше работы» на уровне структуры данных. Все они занимают место. В большинстве случаев, если вы оптимизируете для процессора, ваша программа будет использовать больше памяти. Это классический компромисс между пространством и временем.
Если ваша программа использует слишком много памяти, также возможно пойти другим путём. Уменьшите использование пространства в обмен на большую вычислительную нагрузку. Вместо сохранения вещей рассчитывайте их каждый раз. Вы также можете сжимать данные в памяти и распаковывать их, когда они вам понадобятся.
Small Memory Software — это онлайн-книга, которая охватывает методы сокращения пространства, используемого вашими программами. Хотя она изначально была написана для разработчиков встраиваемых систем, её идеи применимы к программам на современном оборудовании, которое обрабатывает большие объёмы данных.
Удалите заполнение. Удалите лишние поля. Используйте меньшие типы данных.
Более простые структуры данных часто имеют меньшие требования к памяти. Например, переход от древовидной структуры с интенсивным использованием указателей к срезу и линейному поиску.
Алгоритмы сжатия сильно зависят от того, что сжимается. Лучше всего выбрать тот, который подходит вашим данным. Если у вас есть []byte, тогда что-то вроде snappy, gzip, lz4 работает хорошо. Для данных с плавающей запятой существует go-tsz для временных рядов и fpc для научных данных. Совет: не запускайте это на миллионе строк
O(b^n), O(n!): экспоненциальная и выше
Совет: вам понадобится удача, если у вас больше одной или двух дюжин данных
Ссылка: http://bigocheatsheet.com
Предположим, что вам нужно искать в неупорядоченном наборе данных. «Я должен использовать бинарный поиск», — думаете вы, зная, что бинарный поиск — это O(log n), что быстрее, чем O(n) линейного поиска. Однако бинарный поиск требует, чтобы данные были упорядочены, а это означает, что вам придётся их отсортировать, что занимает O(n log n). Если вы делаете много поисков, первоначальные затраты на сортировку окупятся. Но если вы в основном выполняете поиск, возможно, использование массива было ошибочным решением, и лучше использовать карту со стоимостью O(1).
Если ваша структура данных статична, то обычно вы сможете сделать это намного лучше, чем если бы она была динамической. Будет проще построить оптимальную структуру данных для ваших шаблонов поиска. Решения, такие как минимальное идеальное хеширование, могут иметь здесь больше смысла, или предварительно рассчитанные фильтры Блума. Это также имеет смысл, если ваша структура данных «статична» в течение длительного периода времени, так что вы можете амортизировать первоначальную стоимость её создания при многих поисках.
Выберите самую простую структуру данных, которая является разумной, и продолжайте. Это важно для написания «немедленного программного обеспечения». Это должно быть вашим способом разработки по умолчанию. Если вы знаете, что вам нужен произвольный доступ, не выбирайте связанный список. Если вы знаете, что вам нужно пройти через данные по порядку, не используйте карту. Требования меняются, и вы не всегда можете предсказать будущее. Сделайте разумное предположение о рабочей нагрузке.
http://daslab.seas.harvard.edu/rum-conjecture/
Структуры данных для подобных задач будут различаться в зависимости от того, какую часть работы они выполняют. Бинарное дерево упорядочивается по мере вставки элементов. Неупорядоченный массив быстрее при вставке, но не упорядочен: в конце концов, для «завершения» вам нужно выполнить сортировку.
Когда вы пишете пакет для использования другими, избегайте соблазна оптимизировать заранее для каждого отдельного случая использования. Это приведёт к нечитаемому коду. Структуры данных имеют одну цель. Вы не можете читать мысли или предсказывать будущее. Если пользователь говорит: «Ваш пакет слишком медленный для этого варианта использования», разумным ответом может быть: «Тогда используйте этот другой пакет». Пакет должен «делать одну вещь хорошо».
Иногда гибридные структуры данных обеспечивают необходимое повышение производительности. Например, группируя ваши данные, вы можете ограничить свой поиск одной группой. Теоретически это всё ещё будет стоить O(n), но константа будет меньше. Мы вернёмся к рассмотрению этих типов настроек, когда дойдём до части, посвящённой настройке программ.
Две вещи, которые люди забывают, когда обсуждают обозначения big-O:
Во-первых, существует постоянный коэффициент. Два алгоритма с одинаковой алгоритмической сложностью могут иметь разные постоянные коэффициенты. Представьте, что вы перебираете список 100 раз вместо одного раза. Хотя оба они равны O(n), один из них имеет постоянный коэффициент, который в 100 раз больше.
Эти постоянные коэффициенты объясняют, почему, хотя merge sort, quicksort и heapsort все равны O(n log n), все используют quicksort, потому что он самый быстрый. У него наименьший постоянный коэффициент.
Вторая вещь заключается в том, что big-O говорит только «по мере того, как n стремится к бесконечности». Он говорит о тенденции роста: «По мере увеличения чисел этот будет фактором роста, который будет доминировать во времени выполнения». Он ничего не говорит о реальной производительности или о том, как он ведёт себя, когда n мало.
Часто существует точка отсечения, ниже которой более глупый алгоритм работает быстрее. Хороший пример — пакет sort стандартной библиотеки Go. Большую часть времени он использует quicksort, но делает проход с shell sort, а затем с insertion sort, когда размер раздела меньше 12 элементов. Алгоритмы, постоянная константа может быть настолько большой, что эта точка отсечения может быть больше любого разумного ввода. То есть алгоритм O(n^2) быстрее алгоритма O(n) для любого ввода, с которым вы столкнётесь.
Это также означает, что вам нужно иметь репрезентативные выборки размера вашего ввода как для выбора наиболее подходящего алгоритма, так и для написания хороших тестов производительности. 10 элементов? 1000 элементов? 1 000 000 элементов?
Это работает и в обратном направлении: например, выбор более сложной структуры данных для получения роста O(n), а не O(n^2), хотя тесты производительности для меньших входных данных будут медленнее. Это также относится к большинству структур данных, которые являются lock-free. Они обычно работают медленнее при использовании в одном потоке, но более масштабируемы при наличии многих потоков, использующих их.
Иерархия памяти в современных компьютерах немного запутывает тему в том смысле, что кэши предпочитают предсказуемый линейный доступ при обходе среза, а не случайный доступ при следовании за указателем. Тем не менее лучше начать с хорошего алгоритма. Мы поговорим об этом подробнее в разделе о аппаратном обеспечении.
Иногда лучший алгоритм для конкретной задачи — это не один алгоритм, а набор алгоритмов, специализирующихся на слегка разных типах ввода. Этот «полиалгоритм» сначала определяет тип ввода, который он должен обработать, а затем следует соответствующему пути кода. Таким образом работает упомянутый ранее пакет sort: он определяет размер проблемы и выбирает другой алгоритм. Помимо объединения quicksort, shell sort и insertion sort, он также контролирует уровень рекурсивности quicksort и использует heapsort, если это необходимо. Пакеты string и bytes делают нечто подобное, определяя и специализируя для различных случаев. Как и при сжатии данных, чем больше вы знаете о характеристиках вашего ввода, тем лучше будет ваше конкретное решение. Даже если оптимизацию не всегда можно применить, усложнение вашего кода путём определения того, что безопасно использовать, и выполнения различной логики может стоить того.
Это также применимо к подпроблемам, которые должен решить ваш алгоритм. Например, использование radix sort может значительно повлиять на производительность или использование quicksort, если вам нужна только частичная сортировка.
Иногда вместо специализации для вашей задачи лучшим подходом является абстрагирование задачи до более общей категории проблем, которая уже была изучена. Так вы сможете применить наиболее общее решение к вашему конкретному случаю. Сопоставление вашей проблемы с областью с хорошо изученными реализациями может привести к значительной выгоде.
Аналогично, использование более простого алгоритма означает, что более вероятно, что уступки, анализ и детали реализации были изучены и лучше поняты, чем в других более эзотерических, экзотических и сложных алгоритмах.
Простые алгоритмы могут быть быстрее. Эти два примера не являются изолированными случаями: https://go-review.googlesource.com/c/crypto/+/169037 https://go-review.googlesource.com/c/go/+/170322/
TODO: заметки по выбору алгоритма
TODO: улучшить поведение в худшем случае за небольшую стоимость среднего времени выполнения; линейное сопоставление регулярных выражений; рандомизированные алгоритмы: MC против LV; улучшение времени работы в худшем случае; skip-list, treap, рандомизированная маркировка; тестирование простоты, рандомизированный стержень для быстрой сортировки; степень двойки случайных выборов; статистические приближения (часто зависят от размера выборки, а не от размера популяции).
TODO: пакетирование для снижения накладных расходов: https://lemire.me/blog/2018/04/17/iterating-in-batches-over-data-structures-can-be-much-faster/
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Опубликовать ( 0 )