Слияние кода завершено, страница обновится автоматически
Написание и оптимизация кода Go
Этот документ описывает лучшие практики для написания высокопроизводительного кода Go.
Хотя существуют дискуссии, направленные на то, чтобы сделать отдельные сервисы более быстрыми (кэш и т. д.), проектирование высокопроизводительных распределённых систем выходит за рамки этой работы. Уже есть хорошие тексты о мониторинге и проектировании распределённых систем. Они охватывают совершенно другой набор решений в области исследований и проектирования.
Весь контент будет лицензирован под CC-BY-SA.
Эта книга разделена на разные секции:
Мы можем резюмировать эти три секции как:
Я ставлю это на первое место, потому что это действительно самый важный шаг. Вы должны это делать?
Любая оптимизация имеет свою цену. Обычно эта цена выражается в терминах сложности кода или когнитивной нагрузки — оптимизированный код редко проще, чем версия без оптимизаций.
Но есть и другая сторона, которую я назову экономией оптимизации. Как программист, ваше время ценно. Существует стоимость упущенной возможности работать над другими вещами в проекте, например, исправлять ошибки или добавлять функции. Оптимизировать вещи весело, но это не всегда правильная задача. Производительность — это функция (feature), но также важны доставка и корректность.
Выберите наиболее важную задачу для работы. Иногда это не оптимизация процессора, а пользовательский опыт. Что-то такое простое, как добавление индикатора выполнения или повышение отзывчивости страницы после выполнения вычислений в фоновом режиме после рендеринга страницы.
Иногда это будет очевидно: отчёт, который занимает три часа, вероятно, менее полезен, чем тот, который завершается менее чем за час.
То, что что-то легко оптимизировать, не означает, что это стоит оптимизировать. Игнорировать более простые случаи — это эффективная стратегия разработки.
Думайте об этом как об оптимизации вашего времени.
Вы можете выбирать, что оптимизировать и когда. Вы можете перемещать ползунок между «Быстрым ПО» и «Быстрой реализацией».
Люди слышат и повторяют «Преждевременная оптимизация — корень всех зол», но они теряют полный контекст цитаты.
«Программисты тратят много времени, думая или беспокоясь о скорости некритических частей своих программ. Эти попытки добиться эффективности имеют сильный негативный эффект, когда учитываются отладка и обслуживание. Мы должны забыть о мелких улучшениях, скажем, примерно о 97% времени: преждевременная оптимизация — корень всего зла. Однако мы не должны упускать наши возможности в этих критических 3%». — Кнут (вольный перевод).
Добавьте: https://www.youtube.com/watch?time_continue=429&v=RT46MpK39rQ
«Должны ли вы оптимизировать? Да, но только если проблема важна, программа действительно очень медленная и есть некоторые ожидания, что она может быть сделана быстрее, сохраняя при этом правильность, надёжность и ясность». — Практика программирования, Керниган и Пайк (вольный перевод).
[Оценка производительности BitFunnel] (http://bitfunnel.org/strangeloop) имеет некоторые цифры, которые делают это решение более явным. Представьте себе гипотетическую поисковую машину, которой требуется 30 000 машин в нескольких датацентрах. Эти машины стоят примерно 1 000 долларов США в год. Если вы сможете удвоить скорость программного обеспечения, это может сэкономить 15 миллионов долларов США в год. Даже один разработчик, потративший целый год на улучшение производительности всего на 1%, будет… Оптимизация
В большинстве случаев размер и скорость программы не являются проблемой. Самая простая оптимизация — это отсутствие необходимости в ней. Вторая по простоте оптимизация заключается лишь в покупке более быстрого оборудования.
Если вы решили изменить свою программу, продолжайте читать.
Прежде чем вдаваться в подробности, поговорим об общем процессе оптимизации.
Оптимизация — это форма рефакторинга. Однако вместо улучшения какого-либо аспекта исходного кода (дублирование кода, ясность и т. д.) она улучшает какой-либо аспект производительности, например, снижает использование ЦП, уменьшает занятость памяти, сокращает задержку и т.д. Эти улучшения обычно реализуются за счёт некоторой потери читаемости кода. Это означает, что помимо набора модульных тестов (чтобы гарантировать, что ваши изменения ничего не сломают), вам также потребуется хороший набор benchmarks, чтобы убедиться, что ваши изменения действительно обеспечивают желаемый прирост производительности. Вы должны быть в состоянии проверить, действительно ли изменение снижает использование процессора. Иногда изменение, которое, как вы думали, улучшит производительность, на самом деле не оказывает никакого влияния или даже вызывает негативное воздействие. В таких случаях всегда отменяйте свои изменения.
Какой самый лучший комментарий, который вы когда-либо встречали в коде? — Stack Overflow:
// // Дорогой сопровождающий: // // Как только вы откажетесь от попыток «оптимизировать» этот код и поймёте, какую ужасную ошибку вы совершили, // пожалуйста, увеличьте счётчик ниже в качестве предупреждения // следующему человеку: // // total_hours_wasted_here = 42 //
Benchmarks, которые вы решите использовать, должны быть точными и предлагать воспроизводимые числа при соответствующих нагрузках. Если отдельные выполнения имеют слишком большую дисперсию, это затруднит обнаружение небольших улучшений. Поэтому вам нужно будет использовать benchstat или эквивалентное решение для проведения статистических тестов, поскольку вы не сможете проверить улучшения только путём наблюдения. (Обратите внимание, что использование статистических тестов является хорошей идеей в любом сценарии). Шаги для запуска benchmarks должны быть задокументированы, а любые дополнительные скрипты и/или инструменты должны быть включены в репозиторий с инструкциями по их использованию. Будьте осторожны с большими наборами benchmark, требующими много времени для выполнения: это замедлит процесс разработки.
Также помните, что всё, что можно измерить, можно оптимизировать. Убедитесь, что вы измеряете правильную вещь.
Следующий шаг — решить, какова ваша цель оптимизации. Если цель состоит в том, чтобы улучшить использование ЦП, какая скорость приемлема? Вы хотите улучшить производительность в 2 раза или в 10 раз? Вы можете определить это как «большую проблему N, которую необходимо решить за время меньше T»? Вы пытаетесь уменьшить использование памяти? Насколько? Для определённого сокращения использования памяти насколько допустимо замедление? От чего вы готовы отказаться ради меньшего требования к пространству?
Оптимизация с акцентом на задержку обслуживания — более сложная задача. Целые книги были написаны о том, как тестировать производительность веб-серверов. Основная проблема заключается в том, что для одной функции производительность достаточно стабильна для проблемы определённого размера. Для web services у вас нет одного числа. Хороший набор benchmark для web services предоставит распределение задержки для заданного уровня запросов в секунду. Эта лекция даёт хорошее общее представление о некоторых проблемах: «Как НЕ измерять задержку» Гила Тене.
TODO: Посмотрите следующий раздел об оптимизации web services.
Цели производительности должны быть конкретными. Почти всегда вы сможете сделать что-то быстрее. Оптимизация — это... Часто это игра с убывающей отдачей. Нужно знать, когда остановиться. Сколько усилий ещё вы готовы приложить, чтобы получить это небольшое улучшение? Насколько вы готовы сделать код более уродливым и сложным в поддержке?
В упомянутой ранее лекции Дэна Луу «Оценка производительности BitFunnel» приводится пример использования приближённых вычислений для определения того, являются ли предполагаемые цели по производительности разумными.
TODO: В «Programming Pearls» есть «Проблемы Ферми». Полезно ознакомиться со слайдами Джеффа Дина.
При разработке новых проектов не следует оставлять оценку производительности на потом. Легко сказать «потом сделаю», но если производительность действительно важна, об этом нужно думать с самого начала проекта. Любые существенные изменения в архитектуре для решения проблем с производительностью будут ещё более рискованными, если их придётся вносить ближе к крайнему сроку. Обратите внимание, что во время разработки основное внимание должно уделяться согласованному дизайну, алгоритмам и структуре данных. Оптимизация на более низких уровнях структуры должна быть отложена до более поздней стадии цикла разработки, когда будет более полное представление о производительности системы. Любой полный системный профиль, который вы создаёте, пока система неполна, даст искажённое представление о том, где на самом деле будут узкие места в готовой системе.
TODO: Как избежать/обнаружить «смерть от тысячи порезов (линчи)» из-за плохо написанного software.
Benchmarking как часть CI сложен из-за помех, вызванных совместным использованием ресурсов. Также сложно его активировать в метриках производительности. Хороший компромисс — это выполнение benchmarks разработчиком (на подходящем оборудовании) и включение их в commits, которые специально касаются производительности. Для тех, кто просто вносит общие исправления, попробуйте определить потенциальные ухудшения производительности «на глаз» при просмотре кода.
TODO: Как отслеживать производительность с течением времени?
Напишите код, который можно сравнить. Вы можете профилировать большие системы, но в benchmarking вы хотите тестировать отдельные части. Вам нужно уметь извлекать и настраивать контекст, необходимый для того, чтобы benchmarks выполняли репрезентативные и достаточные тесты.
Разрыв между вашей целью и текущей производительностью также даст вам направление, с чего начать. Если вам нужна лишь 10–20% -ная оптимизация производительности, вы, вероятно, сможете достичь этого с помощью небольших корректировок. Если вам нужно улучшить производительность в 10 раз или больше, это потребует более значительных изменений в вашей структуре.
Хорошая работа по улучшению производительности требует знаний на самых разных уровнях, от системного проектирования, сети, hardware (ЦП, кэши, хранилище), алгоритмов, настроек и debugging. Имея ограниченное время и ресурсы, рассмотрите то, что даст вам наибольшую отдачу: это не всегда будет алгоритм или тонкая настройка программы.
Как правило, оптимизации должны идти сверху вниз. Системные оптимизации окажут большее влияние, чем оптимизации на уровне кода. Убедитесь, что вы решаете проблему на соответствующем уровне.
Эта книга в основном будет посвящена снижению использования ЦП, снижению использования памяти и снижению задержки. Интересно отметить, что редко удаётся добиться всех трёх целей одновременно. Возможно, время работы ЦП стало быстрее, но теперь ваша программа использует больше памяти. Может быть, вам нужно уменьшить объём памяти, но теперь программа будет работать дольше.
[Закон Амдала] говорит нам сосредоточиться на узких местах. Если вы удвоите скорость подпрограммы, которая занимает 5% времени выполнения, вы получите прирост всего в 2,5% общего времени. С другой стороны, увеличение скорости подпрограммы, занимающей 80% времени, всего на 10%, даёт реальное увеличение на 8%. Профилирование поможет определить, где действительно тратится время.
Когда вы оптимизируете, вы хотите уменьшить работу, которую должен выполнять ЦП. Quicksort — это... Дополнительные исследования
Большинство структур данных предназначено для одного типа запросов. Если вам нужны два разных типа запросов, то может быть полезно добавить дополнительную «визуализацию» к вашим данным. Например, набор структур может иметь первичный целочисленный идентификатор (ID), который вы используете для поиска в срезе, но иногда вам нужно искать с помощью вторичного строкового идентификатора (ID). Вместо того чтобы перебирать срез, вы можете расширить свою структуру данных с помощью карты от строки к ID или непосредственно к собственной структуре.
Дополнительная информация об элементах
Например, поддержание bloom-фильтра всех вставленных элементов может позволить вам быстро возвращать запросы без результатов. Они должны быть небольшими и быстрыми, чтобы не перегружать остальную часть структуры данных. (Если основной поиск в ваших данных дёшев, стоимость bloom-фильтра превысит любую экономию.)
Если запросы дорогие, добавьте кэш.
На более высоком уровне внутренний или внешний кэш (например, memcache) может помочь. Это может показаться чрезмерным только для одной структуры данных. Мы поговорим о кэше ниже.
Эти типы изменений полезны, когда необходимые данные дёшевы для организации и просты в обновлении.
Это явные примеры принципа «меньше работы» при рассмотрении уровня структуры данных. Все они занимают место. В большинстве случаев, если вы оптимизируете использование процессора, ваша программа будет использовать больше памяти — это классическая компенсация пространства-времени.
Важно подумать, как эта компенсация может повлиять на ваши решения — косвенно. Иногда небольшое количество памяти может привести к значительному увеличению скорости, в других ситуациях этот компромисс линейный (2x использование памяти == 2x улучшение производительности), в других случаях он значительно хуже: огромное количество памяти даёт лишь небольшое улучшение производительности. То, где вам нужно находиться на этой кривой памяти/производительности, может повлиять на то, какие варианты алгоритмов являются разумными. Не всегда можно просто настроить параметр алгоритма. Различные способы использования памяти могут иметь совершенно разные алгоритмические подходы.
Таблицы поиска также вписываются в эту компенсацию пространства-времени. Простая таблица поиска может быть просто кешем вычислений, которые были запрошены ранее.
Если домен достаточно мал, весь набор результатов может быть предварительно вычислен и сохранён в таблице.
В качестве примера, это может быть подход, принятый для быстрой реализации popcount, где количество активных битов в байте хранится в таблице из 256 записей. Большая таблица может хранить биты, необходимые для всех 16-битных слов. В этом случае они хранят точные результаты.
Многие алгоритмы для тригонометрических функций используют таблицы поиска в качестве отправной точки для выполнения вычислений.
Если ваша программа использует много памяти, есть и другой путь. Уменьшите использование пространства в обмен на увеличение вычислений. Вместо хранения вещей всегда рассчитывайте их. Вы также можете сжимать данные в памяти и быстро распаковывать их, когда это необходимо.
Если данные, которые вы обрабатываете, находятся на диске, вместо того, чтобы загружать всё в оперативную память, вы можете создать индекс для необходимых частей и сохранить их в памяти или предварительно обработать файл небольшими доступными фрагментами.
Small Memory Software — это книга, доступная онлайн, которая охватывает методы, используемые для уменьшения пространства, используемого вашими программами. Хотя она была первоначально написана для разработчиков встроенного программного обеспечения, идеи применимы к программам, работающим на современном оборудовании, которое имеет дело с большими объёмами данных.
Реорганизуйте свои данные
Удалите заполнение структуры. Удалите лишние поля. Используйте меньший тип данных.
Переключитесь на структуру Точный перевод текста на русский язык:
Необходимо всегда сокращать циклы, но это предотвращает глупые проблемы с производительностью, которые могут быть не замечены намного позже.
Основные классы сложности:
Ссылка: http://bigocheatsheet.com
Допустим, вам нужно искать неупорядоченный набор данных. «Я должен использовать двоичный поиск», — думаете вы, зная, что двоичный поиск — это O (log n) быстрее, чем линейный поиск O (n). Однако двоичный поиск требует, чтобы данные были упорядочены, а это означает, что вам сначала придётся их упорядочить, что займёт время O (n log n).
Если вы выполняете много поисков, первоначальные затраты на классификацию будут оправданы. С другой стороны, если вы ищете преимущественно в картах, возможно, матрица будет неправильным выбором, и лучше заплатить стоимость поиска O (1) для карты.
Способность анализировать свою проблему в терминах нотации «O» также означает, что вы можете определить, достигли ли вы предела того, что возможно для вашей задачи, и нужно ли изменить подход, чтобы ускорить процесс. Например, найти минимум неупорядоченного списка — это O(n), потому что вам нужно проверить каждый элемент. Нет способа сделать это быстрее.
Если ваша структура данных статична, обычно вы можете добиться гораздо большего, чем в динамическом случае. Становится проще создать идеальную структуру данных, адаптированную именно под ваши шаблоны поиска. Решения, такие как идеальный минимальный хэш, могут иметь здесь смысл, или предварительно вычисленные фильтры Блума. Это также имеет смысл, если ваша структура данных достаточно статична в течение длительного времени, и вы сможете амортизировать первоначальную стоимость построения при множественных поисках.
Выберите наиболее разумную и простую структуру данных и двигайтесь дальше. Это CS 101 для написания «немедленного программного обеспечения». Это должно быть вашим стандартным методом разработки. Если вы знаете, что вам нужен произвольный доступ, не выбирайте связанный список. Если вам нужна сортировка по порядку, не используйте карту. Требования меняются, и вы не всегда можете предсказать будущее. Сделайте обоснованное предположение о рабочей нагрузке.
http://daslab.seas.harvard.edu/rum-conjecture/
Структуры данных для подобных задач различаются по своей работе. Двоичное дерево классифицируется понемногу по мере выполнения вставок. Неупорядоченная матрица быстрее вставляется, но не упорядочена: в конце концов, для «завершения» вам нужно выполнить сортировку за один раз.
При написании пакета для использования другими людьми избегайте соблазна заранее оптимизировать все случаи использования. Это приведёт к нечитаемому коду. По замыслу структуры данных фактически уникальны. Вы не можете читать мысли или предсказывать будущее. Если пользователь скажет: «Ваш пакет слишком медленный для этого случая использования», разумный ответ может быть: «Тогда используйте этот другой пакет здесь». Пакет должен «хорошо делать одну вещь».
Иногда гибридные структуры данных обеспечивают необходимое улучшение производительности. Например, при объединении ваших данных вы можете ограничить свой поиск одним интервалом. Это всё равно оплачивает теоретическую стоимость O(n), но константа будет меньше. Мы рассмотрим эти типы корректировок, когда дойдём до оптимизации.
Две вещи, о которых люди забывают, когда обсуждают нотацию «O»: Во-первых, существует постоянный фактор. Два алгоритма, имеющие одинаковую алгоритмическую сложность, могут иметь разные постоянные коэффициенты. Представьте себе повторение списка 100 раз или только один раз. Хотя оба они являются O(n), один из них имеет постоянный коэффициент в 100 раз больше.
Эти постоянные коэффициенты являются причиной того, почему, хотя merge sort, quick sort и heap sort являются O (n log n), все используют quick sort, потому что он самый быстрый. Этот метод сортировки имеет наименьший постоянный коэффициент.
Во-вторых, Big-O говорит только «по мере того, как n растёт до бесконечности». Он говорит о тенденции роста: «По мере увеличения чисел этот будет доминирующим фактором роста времени выполнения». Он ничего не говорит о реальной производительности или о том, как он ведёт себя с небольшим значением n.
Часто существует точка отсечения, ниже которой более простой алгоритм работает быстрее. Хороший пример — пакет sort стандартной библиотеки Go. В большинстве случаев он использует quicksort, но проходит через сортировку по Шелла, а затем через вставку, когда размер раздела падает ниже 12 элементов.
Для некоторых алгоритмов постоянный коэффициент может быть настолько большим, что эта точка отсечки может быть больше, чем все разумные входные данные. То есть алгоритм O(n^2) быстрее, чем алгоритм O(n) для всех входных данных, с которыми вы, вероятно, работаете.
Это также означает, что вам нужно знать репрезентативные размеры входных данных как для выбора наиболее подходящего алгоритма, так и для написания хороших оценок. 10 элементов? 1000 элементов? 1 000 000 элементов?
Также это происходит другим способом: например, выбор использования более сложной структуры данных для обеспечения масштабирования O(n) вместо O(n^2), даже если параметры для небольших входных данных стали медленнее. Это также относится к большинству структур данных без содержания. Они обычно медленнее в случае одной нити, но более масштабируемы при использовании многими нитями.
Иерархия памяти в современных компьютерах немного запутывает проблему здесь, поскольку кэши предпочитают предсказуемый доступ сканирования случайному доступу, который мы имеем при преследовании указателя. Тем не менее лучше начать с хорошего алгоритма. Мы поговорим об этом в разделе, посвящённом аппаратному обеспечению.
TODO: расширяя последний абзац, упомяните, что нотация O() — это модель, в которой каждая операция имеет фиксированную стоимость. Это ошибочное предположение в современном оборудовании.
Борьба не всегда выигрывается самым сильным, или гонка самым быстрым, но это способ сделать ставку. -- Редьярд Киплинг
Иногда лучший алгоритм для конкретной задачи — это не один алгоритм, а набор алгоритмов, специализированных для слегка разных классов входных данных. Этот «полиалгоритм» быстро определяет, с каким типом ввода ему нужно работать, и отправляет его на соответствующий путь кода. Это то, что делает упомянутый выше пакет классификации: определяет размер проблемы и выбирает другой алгоритм. Помимо объединения quicksort, сортировки по Шеллу и сортировки вставками, он также отслеживает глубину рекурсии quicksort и вызывает heapsort, если это необходимо. Пакеты string и bytes делают нечто подобное, обнаруживая и специализируясь на различных случаях. Как и при сжатии данных, чем больше вы знаете о внешнем виде ваших входных данных, тем лучше может быть ваше индивидуальное решение. Даже если оптимизация не всегда применима, стоит усложнить свой код, определив, что безопасно использовать и выполнять различные логики.
Это также относится к подпроблемам, которые должен решить ваш алгоритм. Например, наличие radix sort в вашем распоряжении может значительно повлиять на производительность или использование быстрой сортировки, если вам нужна только частичная классификация.
Иногда, вместо специализации для вашей конкретной задачи, лучшим подходом является абстрагирование её до более общего пространства проблем, которое было хорошо изучено исследователями. Затем вы можете применить... Решение общей проблемы: выбор подходящего алгоритма
Перенос проблемы в область, где уже есть хорошо изученные реализации, может быть значительным преимуществом.
Аналогично, использование более простого алгоритма означает, что детали обменов, анализов и реализации имеют больше шансов быть изученными и понятыми, чем более экзотические или сложные.
Более простые алгоритмы также могут быть быстрее. Эти два примера не являются изолированными случаями.
TODO: заметки о выборе алгоритма
TODO:
Хотя большинство алгоритмов детерминировано, существует класс алгоритмов, которые используют случайность как способ упростить сложные этапы принятия решений. Вместо того чтобы иметь код, который делает правильные вещи, вы используете случайность для выбора чего-то, вероятно, не плохого. Например, treap — это вероятностно сбалансированное бинарное дерево. Каждый узел имеет ключ, но также получает случайное значение. При вставке в дерево следует обычный путь вставки бинарного дерева, но узлы также подчиняются свойству кучи на основе веса, назначенного случайным образом каждому узлу. Этот более простой подход заменяет сложные решения для вращения деревьев (например, AVL и красно-чёрные деревья), но всё ещё сохраняет сбалансированное дерево с O(log n) вставкой/поиском с высокой вероятностью. Skip lists — ещё одна простая структура данных, которая использует случайность для получения O(log n) вероятной вставки и поиска.
Точно так же выбор случайного опорного элемента для quicksort может быть проще, чем сложный подход медианы медиан для нахождения хорошего опорного элемента, и вероятность того, что плохие опорные элементы будут постоянно выбираться (случайно) и ухудшать производительность quicksort до O(n^2), очень мала.
Случайные алгоритмы классифицируются как алгоритмы «Монте-Карло» или «Лас-Вегас», по двум известным игровым местам. Алгоритм Монте-Карло играет точно: он может дать неправильный ответ (или, в данном случае, несбалансированное двоичное дерево). Алгоритм Лас-Вегаса всегда даёт правильный ответ, но может занять много времени для завершения.
Ещё один известный пример случайного алгоритма — алгоритм теста на простоту Миллера-Рабина. Каждая итерация будет давать «не простое число» или «возможно простое». В то время как «непростое число» верно, «возможно простое» верно с вероятностью не менее 1/2. То есть существуют непростые числа, для которых всё равно будет выдано «возможно простое число». Выполнив много итераций Миллера-Рабина, мы можем сделать вероятность ошибки (выдача «возможно простого числа» для составного числа) настолько малой, насколько захотим. Если выполнить 200 итераций, можно сказать, что число составное с вероятностью максимум 1/(2^200).
Другая область, в которой случайность играет роль, называется «Сила двух случайных выборов». Хотя изначально исследование было применено к балансировке нагрузки, оно оказалось широко применимым к различным проблемам выбора. Идея заключается в том, что вместо того, чтобы пытаться найти лучший выбор среди группы элементов, выберите два случайно и выберите лучший. Возвращаясь к балансировке нагрузки (или цепочкам хеш-таблиц), сила двух случайных вариантов уменьшает ожидаемую нагрузку (или длину цепочки хеширования) элементов O(log n) до O(log log n). Для получения дополнительной информации см. «The Power of Two Random Choices: A Survey of Techniques and Results».
Случайные алгоритмы:
TODO: пакет для уменьшения перегрузки. Вступление для оценки производительности
Вклад реального мира редко соответствует «худшему случаю» в теории. Бенчмаркинг жизненно важен для понимания того, как система ведёт себя в производстве.
Вам нужно знать, какой класс входных данных будет видеть ваш система после внедрения, и ваши бенчмарки должны использовать экземпляры, извлечённые из той же самой дистрибуции. Как мы видели, разные алгоритмы имеют смысл при разных размерах входных данных. Если ожидаемый диапазон входных данных меньше 100, ваши бенчмарки должны отражать это. В противном случае выбор идеального алгоритма для n = 10^6 может быть не самым быстрым.
Способность генерировать репрезентативные тестовые данные. Разные распределения данных могут вызывать разное поведение в вашем алгоритме: подумайте о классическом примере «quicksort — это O (n^2), когда данные отсортированы». Точно так же поиск интерполяции — это O (log log n) для случайных однородных данных, но O (n) в худшем случае. Знание того, каковы ваши входные данные, является ключом к репрезентативным бенчмаркам и выбору лучшего алгоритма. Если данные, которые вы используете для тестирования, не являются репрезентативными для реальных рабочих нагрузок, вы можете легко оптимизировать определённый набор данных, «слишком сильно подстраивая» свой код для работы с определённым набором входных данных.
Это также означает, что ваши эталонные данные должны быть репрезентативны для реального мира. Использование чисто случайных входных данных может исказить поведение вашего алгоритма. Алгоритмы кэширования и сжатия используют искажённые распределения, отсутствующие в случайных данных, и поэтому будут иметь худшую производительность, в то время как бинарное дерево будет работать лучше со случайными значениями, поскольку они, как правило, поддерживают сбалансированное дерево. (Это идея, лежащая в основе treap, кстати.)
С другой стороны, рассмотрим случай тестирования системы с кешем. Если ваша входная контрольная точка состоит только из одной консультации, то каждая заявка попадёт в кеш, обеспечивая потенциально очень нереалистичное представление о том, как система будет вести себя в реальном мире с более разнообразным шаблоном запросов.
Кроме того, обратите внимание, что некоторые проблемы, которые не очевидны на вашем ноутбуке, могут стать видимыми после развёртывания в рабочей среде и достижения 250 тыс. запросов в секунду на 40-ядерном сервере. Аналогично, поведение сборщика мусора во время бенчмаркинга может искажать влияние на реальный мир. Существуют случаи (редкие), когда микробенчмарк покажет замедление, но производительность в реальном мире улучшится. Микробенчмарки могут помочь направить вас в правильном направлении, но способность полностью протестировать влияние изменения на всю систему лучше.
Написание хороших эталонных тестов может быть сложным.
Используйте среднее геометрическое для сравнения групп бенчмарков.
Оценка точности бенчмарка:
Улучшение программы
Улучшение программы раньше было формой искусства, но компиляторы стали лучше. Поэтому теперь компиляторы могут оптимизировать код лучше, чем усложнять его. Компилятор Go всё ещё имеет долгий путь, чтобы соответствовать gcc и clang, но это означает, что вам нужно быть осторожным при настройке и особенно при обновлении версий Go, чтобы ваш код не стал «хуже».
Определённо, есть случаи, когда настройки для решения отсутствия конкретной оптимизации компилятора делают код медленнее после улучшения компилятора. Реоло и логика его кэша позволяют просто искать или пересчитывать данные.
Более сложные алгоритмы, которые предлагают более высокие показатели точности, обычно недёшевы. Случайное удаление кэша — это простой и быстрый способ, который может быть эффективным во многих случаях. Аналогично случайная вставка кэша может ограничить его только популярными элементами с минимальной логикой. Хотя они могут быть не так эффективны, как более сложные алгоритмы, значительное улучшение будет достигнуто добавлением кэша в первую очередь: выбрать именно тот алгоритм кэширования, который предлагает лишь небольшие улучшения.
Важно оценить выбор алгоритма удаления кэша на основе реальных данных. Если в реальном мире повторные запросы достаточно редки, то может оказаться дороже поддерживать ответы в кэше, чем просто пересчитывать их при необходимости. У меня были сервисы, где тестирование с данными из рабочей среды показало, что даже идеальный кэш не стоил усилий. Просто у нас не было достаточного количества повторных запросов, чтобы оправдать дополнительную сложность кэша.
Ожидаемая точность кэша важна. Вы хотите экспортировать пропорцию для своей системы мониторинга. Изменение показателей покажет изменение трафика. Пришло время пересмотреть размер кэша или политику истечения срока действия.
Большой кэш может увеличить нагрузку на сборщик мусора. В крайнем случае (мало или совсем нет удаления, кэш всех запросов к дорогостоящей функции) это может превратиться в [запоминание] (https://ru.wikipedia.org/wiki/Мемоизация).
Улучшение программы:
Улучшение программы — это искусство постепенного улучшения программы. Эгон Элбре представляет свой процесс:
Оптимизация может принимать различные формы.
a <b / c => a * c <b
Для большинства случаев быстрой оптимизации будет достаточно. Если же вам нужны более высокие показатели производительности, вероятно, потребуется специализированная реализация. Регулярно создавайте профиль, чтобы отслеживать характеристики производительности вашей системы и быть готовым к повторной оптимизации по мере изменения трафика.
Знайте пределы своей системы и имейте хорошие метрики, которые позволят предсказать, когда вы достигнете этих пределов. Когда использование приложения меняется, разные части могут стать точками доступа. Пересмотрите предыдущие оптимизации и решите, всё ещё ли они актуальны. Вернитесь к более читаемому коду, если это возможно. У меня был случай, когда система оптимизировала время запуска процесса с помощью сложного набора mmap, reflect и unsafe. После того как мы изменили способ внедрения системы, этот код больше не требовался, и я заменил его на гораздо более читаемые операции с файлами.
Резюме процесса оптимизации (или улучшения производительности) Все оптимизации должны следовать этим этапам:
Также упоминается github.com/aclements/perflock как инструмент для снижения шума процессора. Первый шаг важен. Он сообщает, когда и где начать оптимизацию. Более важно, он также сообщает, когда остановиться. Практически все оптимизации добавляют сложность кода в обмен на скорость. И вы всегда можете создать более быстрый код. Это акт равновесия.
Вы платите за выделение памяти более одного раза. Первый раз, очевидно, когда вы выделяете память. Но вы также платите каждый раз, когда выполняется сборщик мусора.
Выделения стека против кучи.
Что вызывает выделения кучи?
Понимание анализа побега (и текущей ограниченности).
/ debug / pprof / heap и -base.
Дизайн API для ограничения выделений:
Уменьшение указателей для сокращения времени проверки GC.
GOGC.
Повторное использование буфера (sync.Pool vs или пользовательский через go-slab и т. д.).
Фрагментация против перемещения: записи указателя во время выполнения GC требуют барьера записи: https://github.com/golang/go/commit/b85433975aedc2be2971093b6bbb0a7dc264c8fd. Никаких барьеров записи, если запись находится в стеке: https://github.com/golang/go/commit/2140975ebde164ea1eaa70fc72775c03567f2bc9.
Используйте переменные ошибок вместо errors.New() / fmt.Errorf() на сайте вызова (производительность или стиль? Интерфейс требует указатель, так что он всё равно убежит в стек).
Используйте структурированные ошибки для уменьшения выделения (передайте значение структуры), создайте строку в момент печати ошибки.
Классы размера. Время выполнения и компилятор
Стоимость вызовов через интерфейсы (косвенные вызовы на уровне CPU).
runtime.convT2E / runtime.convT2I.
Утверждения типа vs. переключатели типа.
defer.
Реализации карт для особых случаев для int, строк. Карта для byte / uint16 не оптимизирована; используйте срез. Вы можете подделать оптимизированный float64 с помощью math.Float {32, 64} {from,}, но будьте осторожны с проблемами равенства float.
Unsafe
Общие советы с использованием стандартной библиотеки
Альтернативные реализации
Популярные замены стандартных библиотечных пакетов:
В запросе могут быть термины и понятия, специфичные для языка программирования Go. Если вам нужна дополнительная информация по этим темам, рекомендуется обратиться к документации или ресурсам, посвящённым языку Go. Реализация исследовательских работ
Советы по реализации документов: (для «алгоритма» также читайте «структура данных»)
Современные алгоритмы, как правило, имеют более низкие теоретические сложности, но высокие постоянные коэффициенты и большую сложность реализации. Одним из классических примеров этого являются кучи Фибоначчи. Они известны своей сложностью в реализации и имеют огромный постоянный коэффициент. Существует множество опубликованных статей, сравнивающих различные реализации кучи на разных рабочих нагрузках, и, как правило, неявные кучи размером 8 областей всегда оказываются на вершине. И даже в тех случаях, когда куча Фибоначчи должна быть быстрее (из-за O (1) «уменьшения ключа»), эксперименты с алгоритмом глубокого поиска Дийкстры показывают, что он работает быстрее при использовании прямого удаления и добавления кучи.
Аналогично, treaps или skiplists против более сложных красно-чёрных деревьев или AVL. На современном оборудовании самый медленный алгоритм может быть достаточно быстрым или даже быстрее.
Самый быстрый алгоритм часто можно заменить почти таким же быстрым и гораздо более простым для понимания.
— Дуглас У. Джонс, Университет Айовы
Дополнительная сложность должна оправдывать себя. Другим примером являются алгоритмы удаления кэша. Различные алгоритмы могут иметь гораздо более высокую сложность только для небольшого улучшения точности. Конечно, возможно, вы не сможете протестировать его, пока у вас не будет функциональной реализации и вы не интегрируете его в свою программу.
Иногда работа содержит графики, но это очень похоже на тенденцию публиковать только положительные результаты, они будут искажены в пользу демонстрации того, насколько хорош новый алгоритм.
Часто предыдущие статьи легче понять и они обязательно будут содержать более простые алгоритмы.
Не все роли хороши.
Посмотрите контекст, в котором была написана статья. Определите предположения о аппаратном обеспечении: дисковое пространство, использование памяти и т. д. Некоторые старые статьи содержат разные компромиссы, которые были разумны в 70-х или 80-х годах, но не обязательно применимы к вашему варианту использования. Например, то, что они определяют как «разумную» память по сравнению с обменом дисковым пространством. Размеры памяти сейчас на порядок больше, а SSD изменили штраф за задержку при использовании диска. Аналогичным образом некоторые потоковые алгоритмы предназначены для оборудования маршрутизатора, что может затруднить перевод в программное обеспечение.
Проверьте, сохраняются ли предположения, которые делает алгоритм относительно ваших данных.
Это займёт некоторое время. Вы, вероятно, не захотите реализовывать первый попавшийся вам документ.
https://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/07/paper-reading.pdf
Хорошее понимание может позволить вам извлечь ключевую идею документа и, возможно, применить её непосредственно к вашей проблеме, которая может быть проще, чем полная переделка.
Оригинальный документ структуры или алгоритма данных не всегда лучший. Последующие работы могут содержать лучшие объяснения.
Некоторые работы публикуют исходный код, с которым вы можете сравнить, но
Также ищите другие реализации на GitHub: они могут иметь те же (или разные!) ошибки, что и ваша.
Другие ресурсы по этой теме:
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Опубликовать ( 0 )