Эффективность алгоритмов: ресурсы и оптимизация

Введение

Свойство алгоритма

В информатике алгоритмическая эффективность — это свойство алгоритма, характеризующее количество используемых им вычислительных ресурсов. Алгоритмическую эффективность можно рассматривать как аналог инженерной производительности для повторяющегося или непрерывного процесса. Для достижения максимальной эффективности желательно минимизировать потребление ресурсов. Однако различные ресурсы, такие как временная и пространственная сложность, нельзя сравнивать напрямую, поэтому оценка эффективности двух алгоритмов часто зависит от того, какая мера эффективности считается наиболее важной. Например, сортировка пузырьком и сортировка TimSort — это оба алгоритма для сортировки списка элементов от наименьшего к наибольшему. Сортировка пузырьком выполняется за время, пропорциональное квадрату количества элементов (см. нотацию «Большое О»), но требует лишь небольшого объема дополнительной памяти, который постоянен относительно длины списка. TimSort сортирует список за время, линейно-логарифмическое по длине списка (пропорциональное величине, умноженной на логарифм этой величины), но требует объема памяти, линейного относительно длины списка. Если для конкретного приложения необходимо быстро сортировать большие списки, TimSort будет лучшим выбором; однако, если важнее минимизировать объем используемой памяти, сортировка пузырьком будет предпочтительнее.

Обзор

Алгоритм считается эффективным, если его потребление ресурсов, также известное как вычислительная стоимость, находится на приемлемом уровне или ниже. Грубо говоря, "приемлемый" означает, что он выполнится за разумное время и с использованием разумного объема памяти на доступном компьютере, как правило, в зависимости от размера входных данных. С 1950-х годов компьютеры значительно увеличили как вычислительную мощность, так и объем доступной памяти, поэтому современные приемлемые уровни были бы неприемлемы даже десять лет назад. Фактически, благодаря приблизительному удвоению вычислительной мощности каждые два года, задачи, которые являются приемлемо эффективными на современных смартфонах и встраиваемых системах, могли быть неприемлемо неэффективными для промышленных серверов десять лет назад. Производители компьютеров часто выпускают новые модели, зачастую с более высокой производительностью. Стоимость программного обеспечения может быть значительной, поэтому в некоторых случаях самым простым и дешевым способом повышения производительности может быть просто покупка более быстрого компьютера, при условии его совместимости с существующим оборудованием. Существует множество способов измерения ресурсов, используемых алгоритмом: наиболее распространенными являются скорость и использование памяти; другие показатели могут включать скорость передачи данных, временное использование диска, долгосрочное использование диска, энергопотребление, общую стоимость владения, время отклика на внешние воздействия и т. д. Многие из этих показателей зависят от размера входных данных, то есть от объема обрабатываемой информации. Они также могут зависеть от организации данных; например, некоторые алгоритмы сортировки показывают плохие результаты на уже отсортированных или отсортированных в обратном порядке данных. На практике на эффективность алгоритма могут влиять и другие факторы, такие как требования к точности и/или надежности. Как подробно описано ниже, способ реализации алгоритма также может существенно влиять на фактическую эффективность, хотя многие аспекты этого связаны с вопросами оптимизации.

Проблемы с реализацией

Проблемы реализации также могут влиять на эффективность, например, выбор языка программирования, способ фактической реализации алгоритма в коде, выбор компилятора для конкретного языка, используемые опции компиляции или даже используемая операционная система. Во многих случаях язык, реализованный интерпретатором, может быть значительно медленнее, чем язык, реализованный компилятором. См. статьи о JIT-компиляции и интерпретируемых языках. Существуют и другие факторы, которые могут влиять на производительность по времени или объему памяти, но которые могут быть вне контроля программиста: выравнивание данных, гранулярность данных, локальность кэша, когерентность кэша, сборка мусора, параллелизм на уровне инструкций, многопоточность (на аппаратном или программном уровне), одновременная многозадачность и вызовы подпрограмм. Некоторые процессоры поддерживают векторную обработку, позволяющую одной инструкции оперировать несколькими операндами; использование этих возможностей может быть как простым, так и сложным для программиста или компилятора. Алгоритмы, разработанные для последовательной обработки, могут потребовать полной переработки для использования параллельной обработки, либо их можно легко переконфигурировать. По мере роста важности параллельных и распределенных вычислений в конце 2010-х годов увеличиваются инвестиции в эффективные высокоуровневые API для параллельных и распределенных вычислительных систем, такие как CUDA, TensorFlow, Hadoop, OpenMP и MPI. Другая проблема, возникающая при программировании, заключается в том, что процессоры, совместимые с одним и тем же набором инструкций (например, x86-64 или ARM), могут реализовывать одну и ту же инструкцию по-разному, в результате чего инструкции, относительно быстрые на одних моделях, могут быть относительно медленными на других. Это часто создает трудности для оптимизирующих компиляторов, которым необходимо обладать обширными знаниями о конкретном процессоре и другом доступном оборудовании на целевой платформе компиляции, чтобы наилучшим образом оптимизировать программу для достижения максимальной производительности. В крайнем случае компилятор может быть вынужден эмулировать инструкции, не поддерживаемые на целевой платформе компиляции, что заставит его генерировать код или подключать вызов внешней библиотеки для получения результата, который иначе невозможно вычислить на этой платформе, даже если он поддерживается аппаратно и более эффективен на других платформах. Это часто встречается во встраиваемых системах в отношении арифметики с плавающей точкой, где малогабаритные и маломощные микроконтроллеры часто не имеют аппаратной поддержки для арифметики с плавающей точкой и, следовательно, требуют ресурсоемких программных подпрограмм для выполнения вычислений с плавающей точкой.

Implementation issues can also have an effect on efficiency, such as the choice of programming language, or the way in which the algorithm is actually coded, or the choice of a compiler for a particular language, or the compilation options used, or even the operating system being used. In many cases a language implemented by an interpreter may be much slower than a language implemented by a compiler. See the articles on just in time compilation and interpreted languages. There are other factors which may affect time or space issues, but which may be outside of a programmer's control; these include data alignment, data granularity, cache locality, cache coherency, garbage collection, instruction level parallelism, multi threading (at either a hardware or software level), simultaneous multitasking, and subroutine calls. Some processors have capabilities for vector processing, which allow a single instruction to operate on multiple operands; it may or may not be easy for a programmer or compiler to use these capabilities. Algorithms designed for sequential processing may need to be completely redesigned to make use of parallel processing, or they could be easily reconfigured. As parallel and distributed computing grow in importance in the late 2010s, more investments are being made into efficient high level APIs for parallel and distributed computing systems such as CUDA, TensorFlow, Hadoop, OpenMP and MPI. Another problem which can arise in programming is that processors compatible with the same instruction set (such as x86 64 or ARM) may implement an instruction in different ways, so that instructions which are relatively fast on some models may be relatively slow on other models. This often presents challenges to optimizing compilers, which must have a great amount of knowledge of the specific CPU and other hardware available on the compilation target to best optimize a program for performance. In the extreme case, a compiler may be forced to emulate instructions not supported on a compilation target platform, forcing it to generate code or link an external library call to produce a result that is otherwise incomputable on that platform, even if it is natively supported and more efficient in hardware on other platforms. This is often the case in embedded systems with respect to floating point arithmetic, where small and low power microcontrollers often lack hardware support for floating point arithmetic and thus require computationally expensive software routines to produce floating point calculations.

Теория

Анализируйте алгоритм, как правило, с помощью анализа временной сложности, чтобы получить оценку времени выполнения как функции от размера входных данных. Результат обычно представляется в нотации «Большое О». Это полезно для сравнения алгоритмов, особенно при обработке больших объемов данных. Для сравнения производительности алгоритмов требуются более детальные оценки, когда объем данных невелик, хотя это, вероятно, менее важно. Алгоритмы, включающие параллельную обработку, могут быть сложнее анализировать.

Практика

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

Хранилище иерархия памяти

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

Процессорные регистры – самая быстрая из технологий компьютерной памяти с наименьшим объемом хранения. Большинство прямых вычислений на современных компьютерах выполняются с исходными и целевыми операндами в регистрах, прежде чем они будут обновлены в кэше, основной памяти и виртуальной памяти, если это необходимо. На ядре процессора обычно доступно порядка сотен байт или меньше регистров, хотя файл регистров может содержать больше физических регистров, чем архитектурные регистры, определенные в архитектуре набора команд. Кэш-память – вторая по скорости и вторая по объему память в иерархии памяти. Кэши присутствуют в процессорах, графических процессорах, жестких дисках и внешних периферийных устройствах и обычно реализованы на статической оперативной памяти (SRAM). Кэши памяти многоуровневые: более низкие уровни больше, медленнее и обычно совместно используются ядрами процессора в многоядерных процессорах. Для обработки операндов в кэш-памяти процессор должен извлечь данные из кэша, выполнить операцию в регистрах и записать данные обратно в кэш. Это происходит со скоростью, сопоставимой (примерно в 2-10 раз медленнее) со скоростью арифметико-логического устройства (ALU) или блока операций с плавающей запятой (FPU) процессора или графического процессора, если данные находятся в кэше L1. Скорость снижается примерно в 10 раз при промахе кэша L1, когда данные необходимо извлечь из кэша L2 и записать в него, и еще в 10 раз при промахе кэша L2, когда данные необходимо извлечь из кэша L3 (если он присутствует). Основная физическая память чаще всего реализована на динамической оперативной памяти (DRAM). Основная память значительно больше (обычно гигабайты по сравнению с ≈8 мегабайтами), чем кэш L3 процессора, а задержки чтения и записи обычно в 10-100 раз выше. По состоянию на 2018 год оперативная память все чаще интегрируется в чип процессора в виде памяти процессора или графического процессора. Виртуальная память чаще всего реализована на основе вторичной памяти, такой как жесткий диск, и является расширением иерархии памяти, которое обеспечивает гораздо больший объем хранения, но значительно большую задержку, обычно в 1000 раз больше, чем промах кэша для значения в оперативной памяти. Хотя изначально виртуальная память была создана для создания иллюзии большего объема памяти, чем было доступно на самом деле, в современном использовании она более важна благодаря компромиссу между временем и пространством и возможности использования виртуальных машин. Промахи кэша из основной памяти называются ошибками страниц и приводят к значительным потерям производительности программ. Алгоритм, чьи потребности в памяти помещаются в кэш-память, будет работать намного быстрее, чем алгоритм, который помещается в основную память, который, в свою очередь, будет намного быстрее, чем алгоритм, которому приходится обращаться к виртуальной памяти. Поэтому политики замены кэша чрезвычайно важны для высокопроизводительных вычислений, как и программирование с учетом кэша и выравнивание данных. Чтобы еще больше усложнить ситуацию, некоторые системы имеют до трех уровней кэш-памяти с различными эффективными скоростями. Различные системы будут иметь разный объем этих различных типов памяти, поэтому влияние потребностей алгоритма в памяти может сильно варьироваться от одной системы к другой. В первые дни электронных вычислений, если алгоритм и его данные не помещались в основную память, алгоритм не мог быть использован. Сегодня использование виртуальной памяти, по-видимому, обеспечивает большой объем памяти, но ценой производительности. Если алгоритм и его данные помещаются в кэш-память, можно достичь очень высокой скорости; в этом случае минимизация объема памяти также поможет минимизировать время. Это называется принципом локальности, который можно разделить на локальность ссылок, пространственную локальность и временную локальность. Алгоритм, который не полностью помещается в кэш-память, но демонстрирует локальность ссылок, может работать достаточно хорошо.

Processor registers, the fastest of computer memory technologies with the least amount of storage space. Most direct computation on modern computers occurs with source and destination operands in registers before being updated to the cache, main memory and virtual memory if needed. On a processor core, there are typically on the order of hundreds of bytes or fewer of register availability, although a register file may contain more physical registers than architectural registers defined in the instruction set architecture. Cache memory is the second fastest and second smallest memory available in the memory hierarchy. Caches are present in CPUs, GPUs, hard disk drives and external peripherals, and are typically implemented in static RAM. Memory caches are multi leveled; lower levels are larger, slower and typically shared between processor cores in multi core processors. In order to process operands in cache memory, a processing unit must fetch the data from the cache, perform the operation in registers and write the data back to the cache. This operates at speeds comparable (about 2 10 times slower) with the CPU or GPU's arithmetic logic unit or floating point unit if in the L1 cache. It is about 10 times slower if there is an L1 cache miss and it must be retrieved from and written to the L2 cache, and a further 10 times slower if there is an L2 cache miss and it must be retrieved from an L3 cache, if present. Main physical memory is most often implemented in dynamic RAM (DRAM). The main memory is much larger (typically gigabytes compared to ≈8 megabytes) than an L3 CPU cache, with read and write latencies typically 10 100 times slower. as of 2018, RAM is increasingly implemented on chip of processors, as CPU or GPU memory. Virtual memory is most often implemented in terms of secondary storage such as a hard disk, and is an extension to the memory hierarchy that has much larger storage space but much larger latency, typically around 1000 times slower than a cache miss for a value in RAM. While originally motivated to create the impression of higher amounts of memory being available than were truly available, virtual memory is more important in contemporary usage for its time space tradeoff and enabling the usage of virtual machines. Cache misses from main memory are called page faults, and incur huge performance penalties on programs. An algorithm whose memory needs will fit in cache memory will be much faster than an algorithm which fits in main memory, which in turn will be very much faster than an algorithm which has to resort to virtual memory. Because of this, cache replacement policies are extremely important to high performance computing, as are cache aware programming and data alignment. To further complicate the issue, some systems have up to three levels of cache memory, with varying effective speeds. Different systems will have different amounts of these various types of memory, so the effect of algorithm memory needs can vary greatly from one system to another. In the early days of electronic computing, if an algorithm and its data would not fit in main memory then the algorithm could not be used. Nowadays the use of virtual memory appears to provide much memory, but at the cost of performance. If an algorithm and its data will fit in cache memory, then very high speed can be obtained; in this case minimizing space will also help minimize time. This is called the principle of locality, and can be subdivided into locality of reference, spatial locality and temporal locality. An algorithm which will not fit completely in cache memory but which exhibits locality of reference may perform reasonably well.