В информатике нормализованный цикл (иногда называемый хорошо себя ведущим циклом) — это цикл, в котором переменная цикла начинается с 0 (или любой константы) и увеличивается на единицу на каждой итерации до тех пор, пока не будет выполнено условие выхода. Нормализованные циклы очень важны для теории компиляторов , анализа зависимости циклов , поскольку они упрощают анализ зависимости данных . [ необходима цитата ] [1]
Правильно организованный цикл обычно имеет вид:
для ( i = 0 ; i < МАКС ; i ++ ) a [ i ] = b [ i ] + 5 ; Поскольку приращение является единичным и постоянным, очень легко увидеть, что если и a, и b больше MAX, этот цикл никогда не обратится к памяти за пределами выделенного диапазона.
Ненормализованный цикл может начинаться с разных индексов, увеличиваться на неунитарные величины и иметь сложные для определения условия выхода. Такие циклы трудно оптимизировать, векторизовать и даже обходить, особенно если функции выполняются в любой части условий цикла.
Простой пример, где он не начинается с начала и увеличивается более чем на единицу:
// Пример 1 для ( i = 7 ; i < MAX ; i += 3 ) a [ i ] = b [ i ] + 5 ; Более сложный пример с дополнительным условием выхода:
// Пример 2 для ( i = 7 ; i < MAX || i > MIN ; i += 3 ) a [ i ] = b [ i ] + 5 ; Циклы также могут иметь непредсказуемое поведение во время компиляции, когда условие выхода зависит от содержимого изменяемых данных:
// Пример 3 для ( i = 7 ; i < MAX && a [ i ]; i += 3 ) a [ i ] = b [ i ] + 5 ; Или даже динамические вычисления посредством вызовов функций:
// Пример 4 для ( i = start (); i < max (); i += increment () ) a [ i ] = b [ i ] + 5 ; Обратные циклы также очень просты и могут быть легко нормализованы:
// Пример 5 для ( i = MAX ; i > 0 ; i -- ) a [ i ] = b [ i ] + 5 ; Если ненормализованное не имеет динамического поведения, его обычно очень легко преобразовать в нормализованное. Например, первый пример (Пример 1) выше можно легко преобразовать в:
// Пример 1 -> нормализовано для ( i = 0 ; i < ( MAX -7 ) / 3 ; i ++ ) a [ i * 3 + 7 ] = b [ i * 3 + 7 ] + 5 ; Хотя третий пример можно частично нормализовать, чтобы обеспечить некоторую распараллеливание, но в нем все еще нет возможности узнать длительность цикла (сколько будет итераций), что затрудняет векторизацию с использованием мультимедийного оборудования.
Начинать с 7 не так уж и сложно, если приращение регулярное, желательно одно. Когда несколько операторов внутри цикла используют индекс, могут быть созданы некоторые частные временные переменные, чтобы справиться с различными темпами итераций.
Обратный цикл (пример 5) также легко нормализовать:
// Пример 5 -> нормализовано для ( i = 0 ; i < MAX ; i ++ ) a [ MAX - i ] = b [ MAX - i ] + 5 ; Обратите внимание, что доступ все еще обратный. В этом случае нет смысла оставлять его обратным (поскольку нет зависимости по данным ), но там, где существуют зависимости, необходимо соблюдать осторожность, чтобы также вернуть доступ, поскольку это может нарушить порядок назначений.
Пример 4 выше делает невозможным предсказание чего-либо из этого цикла. Если только сами функции не являются тривиальными (константными), нет способа узнать, где цикл начнется, остановится и насколько он увеличится на каждой итерации. Эти циклы не только трудно распараллелить, но они еще и ужасно работают.
На каждой итерации цикл будет оценивать две функции ( max() и increment() ). Даже если функции встроены, условие становится слишком сложным, чтобы его стоило оптимизировать. Программист должен быть особенно осторожен, чтобы не создавать эти циклы, если только это не является строго необходимым (если вообще когда-либо).
Другая опасность таких циклов возникает, если оценка зависит от изменяемых данных. Например, обычной ошибкой при использовании итераторов является удаление элементов из списка при его изменении или опора на размеры (для условия выхода), которые больше не являются истинными.