В информатике разделение циклов (или распределение циклов ) — это оптимизация компилятора , при которой цикл разбивается на несколько циклов в одном и том же диапазоне индексов, каждый из которых занимает только часть тела исходного цикла. [1] [2] Цель состоит в том, чтобы разбить большое тело цикла на более мелкие, чтобы добиться лучшего использования локальности ссылки . Эта оптимизация наиболее эффективна в многоядерных процессорах , которые могут разбивать задачу на несколько задач для каждого процессора .
И наоборот, слияние циклов (или застревание циклов ) — это оптимизация компилятора и преобразование циклов , при которых несколько циклов заменяются одним. [3] [2] Слияние циклов не всегда улучшает скорость выполнения. В некоторых архитектурах два цикла могут работать лучше, чем один, потому что, например, внутри каждого цикла увеличивается локальность данных . Одним из основных преимуществ объединения циклов является то, что оно позволяет избежать временного выделения памяти, что может привести к огромному увеличению производительности в языках числовых вычислений, таких как Julia, при выполнении поэлементных операций с массивами (однако объединение циклов Julia технически не является оптимизацией компилятора). , а синтаксическая гарантия языка). [4]
Другие преимущества слияния циклов заключаются в том, что оно позволяет избежать накладных расходов на структуры управления циклом, а также позволяет распараллеливать тело цикла процессором [5] , используя преимущества параллелизма на уровне команд . Это возможно, когда между телами двух циклов нет зависимостей по данным (это резко контрастирует с другим основным преимуществом объединения циклов, описанным выше, которое проявляется только тогда, когда существуют зависимости по данным, которые требуют промежуточного выделения для хранения Результаты). Если слияние циклов позволяет удалить избыточные выделения, повышение производительности может быть значительным. [4] В противном случае существует более сложный компромисс между локальностью данных, параллелизмом на уровне инструкций и накладными расходами цикла (ветвление, приращение и т. д.), что может сделать слияние циклов, разделение циклов или ни то, ни другое предпочтительным вариантом оптимизации.
int я , а [ 100 ], б [ 100 ]; для ( я знак равно 0 ; я < 100 ; я ++ ) { а [ я ] знак равно 1 ; б [ я ] знак равно 2 ; } эквивалентно:
int я , а [ 100 ], б [ 100 ]; для ( я знак равно 0 ; я < 100 ; я ++ ) { а [ я ] знак равно 1 ; } for ( я знак равно 0 ; я < 100 ; я ++ ) { б [ я ] знак равно 2 ; } Рассмотрим следующий код MATLAB:
х = 0 : 999 ; % Создать массив чисел от 0 до 999 (диапазон включительно) y = sin ( x ) + 4 ; % Возьмите синус x (поэлементно) и прибавьте 4 к каждому элементу Вы можете добиться того же синтаксиса в C++, используя перегрузку функций и операторов:
#include <cmath> #include <cassert> #include <memory> #include <iostream> класс Array { size_t длина ; std :: unique_ptr < float [] > data ; // Внутренний конструктор, создающий неинициализированный массив Array ( size_t n ) : length ( n ), data ( new float [ n ]) { } public : // Фабричный метод для создания массива в целочисленном диапазоне (верхняя граница // является эксклюзивным, в отличие от диапазонов MATLAB). диапазон статического массива ( size_t start , size_t end ) { assert ( end > start ); size_t длина = конец - начало ; Массив a ( длина ); for ( size_t я знак равно 0 ; я < длина ; ++ я ) { а [ я ] = начало + я ; } Вернуть ; } // Основные операции с массивами size_t size () const { return length ; } float & оператор []( size_t i ) { возвращаем данные [ i ]; } const float & оператор []( size_t i ) const { возвращаем данные [ i ]; } // Объявляем перегруженный оператор сложения как свободную дружественную функцию (этот // синтаксис определяет оператор+ как свободную функцию, которая является дружественной этому // классу, несмотря на то, что она отображается как объявление функции-члена). друг Оператор массива + ( const Array & a , float b ) { Array c ( a . size ()); для ( size_t я знак равно 0 ; я < a . size (); ++ я ) { c [ я ] знак равно а [ я ] + б ; } Вернуть С ; } // Аналогичным образом мы можем определить перегрузку для функции sin(). На практике // было бы громоздко определять все возможные перегруженные математические операции как // друзей внутри класса, но это всего лишь пример. друг Массив sin ( const Array & a ) { Array b ( a . size ()); for ( size_t i = 0 ; i < a . size (); ++ i ) { b [ i ] = std :: sin ( a [ i ]); } Вернуть б ; } }; int main ( int argc , char * argv []) { // Здесь мы выполняем те же вычисления, что и в примере MATLAB auto x = Array :: Range ( 0 , 1000 ); авто y = грех ( x ) + 4 ; // Распечатываем результат - просто чтобы убедиться, что оптимизатор не удалит // все (если он достаточно умен, чтобы это сделать). std :: cout << "Результат: " << std :: endl ; for ( size_t i = 0 ; i < y . size (); ++ i ) { std :: cout << y [ i ] << std :: endl ; } вернуть 0 ; } Однако в приведенном выше примере излишне выделяется временный массив для результата sin(x). Более эффективная реализация могла бы выделить один массив для yи выполнять вычисления yв одном цикле. Чтобы оптимизировать это, компилятору C++ необходимо:
sinи operator+.Все эти шаги возможны индивидуально. Даже четвертый шаг возможен, несмотря на то, что функции типа mallocи freeимеют глобальные побочные эффекты, поскольку некоторые компиляторы жестко закодируют символы, такие как mallocи free, чтобы они могли удалять неиспользуемые выделения из кода. [6] Однако, начиная с clang 12.0.0 и gcc 11.1, такого слияния циклов и удаления избыточных выделений не происходит - даже на самом высоком уровне оптимизации. [7] [8]
В некоторых языках, специально предназначенных для числовых вычислений, таких как Julia, может быть встроена концепция объединения циклов на высоком уровне, когда компилятор распознает соседние поэлементные операции и объединяет их в один цикл. [9] В настоящее время для достижения того же синтаксиса в языках общего назначения, таких как C++, функции sinи operator+должны пессимистично выделять массивы для хранения своих результатов, поскольку они не знают, из какого контекста они будут вызываться. Этой проблемы можно избежать в C++, используя другой синтаксис, который не требует от компилятора удаления ненужных временных выделений (например, с помощью функций и перегрузок для операций на месте, таких как operator+=или std::transform).
слияние петель.