Совершенный цикл for
Сегодня необычный для меня формат статьи: я скорее задаю вопрос залу, нежели делюсь готовым рецептом. Впрочем, для инициирования дискуссии рецепт тоже предлагаю. Итак, сегодня мы поговорим о чувстве прекрасного.
Я довольно давно пишу код, и так вышло, что практически всегда на C++. Даже и не могу прикинуть, сколько раз я написал подобную конструкцию:
Хотя почему не могу, очень даже могу:
find . \( -name \*.h -o -name \*.cpp \) -exec grep -H "for (" <> \; | wc -l 43641Наш текущий проект содержит 43 тысячи циклов. Проект пилю не я один, но команда маленькая и проект у меня не первый (и, надеюсь, не последний), так что в качестве грубой оценки пойдёт. А насколько такая запись цикла for хороша? Ведь на самом деле, важно даже не то количество раз, когда я цикл написал, а то количество раз, когда я цикл прочитал (см. отладка и code review). А тут речь очевидно идёт уже о миллионах.
На КПДВ узел под названием «совершенная петля» (perfection loop).
Так каков он, совершенный цикл?
А в чём проблема?
Мы пишем много кода для математического моделирования; код довольно плотный, с огромным количеством целых чисел, которые являются индексами ячеек, функций и прочей лабуды. Чтобы был понятен масштаб проблемы, давайте я просто приведу крохотный кусочек кода из нашего проекта:
У нас есть некая область, разбитая на тетраэдры, и мы на ней моделируем некий процесс. Для каждой итерации процесса мы проходимся по всем тетраэдрам сетки, затем по всем вершинам каждого тетраэдра, бла-бла-бла, и всё венчает цикл по всем трём измерениям нашего окружающего мира.
Мы обязаны иметь дело с кучей вложенных циклов; вышеприведённые пять вложенных далеко не предел. Мы уже довольно давно (лет пятнадцать как) пришли к выводу, что стандартный for (int i=0; i
Когда мы читаем стандартный for(;;) , мы должны на каждой строчке обратить внимание на три вещи: на инициализацию, на условие выхода и собственно на инкремент. Но ведь это совершеннейший оверкилл для тех случаев, когда нам нужно пройтись от 0 до size-1 , а это подавляющее большинство всех циклов. Скажите, как часто вам приходится писать обратный цикл или итерацию с другими границами? Как мне кажется, один раз из десяти — это ещё щедрая оценка.
До появления c++11 мы в итоге пришли к страшной вещи, а именно ввели в самый верхний заголовок вот такой дефайн:
#define FOR(I,UPPERBND) for(int I = 0; IИ тогда вышеприведённый кусок кода превращается из тыквы в кабачок:
Польза такой трансформации в том, что когда я встречаю for (;;) , я знаю, что мне нужно насторожиться и внимательно смотреть на все три места (инициализацию, условие, инкремент). В то время как если я вижу FOR(,) то это совершенно стандартный пробег от 0 до n-1 без каких-либо тонкостей. Я совершенно не предлагаю пользоваться вышеприведённым дефайном, но точно знаю, что для нашей команды он сберёг много ресурсов мозга, поскольку мы кода гораздо больше читаем (см. отладка), нежели пишем (как, наверное, и все программисты).
То есть, вопрос, которым я задаюсь, звучит так: "Как выглядит цикл, имеющий минимальную когнитивную нагрузку при чтении кода?"
Жизнь после 11го года, или range for
А как дела обстоят у соседей? Вы знаете, местами довольно недурно. Например, в лагере питонистов стандартный цикл выглядит следующим образом:
Что любопытно, до третьего питона range() создавал в памяти массив индексов, и проходился по нему. И со времён c++11 мы вполне можем делать точно так же!
#include int main() < int range[] = ; for (int i : range) < std::cerr >Разумеется, явно создавать в памяти массив индексов это несерьёзно, и с третьей версии в питоне это тоже поняли. Но и в C++ мы можем сделать не хуже!
Давайте посмотрим на следующую функцию range(int n) :
#include constexpr auto range(int n) < struct iterator < int i; void operator++() < ++i; >bool operator!=(const iterator& rhs) const < return i != rhs.i; >const int &operator*() const < return i; >>; struct wrapper < int n; auto begin() < return iterator; > auto end() < return iterator; > >; return wrapper; > int main() < for (int i: range(13)) < std::cerr return 0; >Пожалуйста, не начинайте int vs size_t , разговор не об этом. Если скомпилировать этот код при помощи gcc 10.2 с флагами компиляции -std=c++17 -Wall -Wextra -pedantic -O1 , то мы получим следующий ассемблерный код (проверьте тут):
[. ] .L2: mov esi, ebx mov edi, OFFSET FLAT:_ZSt4cerr call std::basic_ostream >::operatorТо есть, компилятор начисто убрал все эти обёртки и оставил голый инкремент, ровно как если бы мы написали обычный for (int i=0; i
Лично мне кажется, что for (int i: range(n)) справляется с подчёркиванием обычности цикла чуть хуже, нежели FOR(,) , но тоже вполне достойно, и за это не нужно платить дополнительными тактами процессора.
Продолжаем подглядывать в замочную скважину: enumerate
Range for в c++11 нанёс большую пользу. Давайте скажем, что у меня есть массив трёхмерных точек, и мне нужно распечатать икс координаты каждой точки, это можно сделать следующим образом:
#include #include struct vec3 < double x,y,z; >; int main() < std::vectorpoints = ,,>; for (vec3 &p: points) < std::cerr return 0; >for (vec3 &p: points) это прекрасная конструкция, никаких костылей, сразу из стандарта языка. Но что если у меня каждая точка из массива имеет цвет, вес или вкус? Это можно представить ещё одним массивом того же размера, что и массив точек. И тогда для доступа к атрибуту мне всё же понадобится индекс, который мы можем сгенерировать, например, вот таким образом:
std::vector points = ,,>; std::vector weights = ; int i = 0; for (vec3 &p: points)
Для этого кода компилятор генерирует следующий ассемблер:
.L2: movsd xmm0, QWORD PTR [r13+0] mov edi, OFFSET FLAT:_ZSt4cerr call std::basic_ostream >& std::basic_ostream >::_M_insert(double) movsd xmm0, QWORD PTR [rbp+0] mov rdi, rax call std::basic_ostream >& std::basic_ostream >::_M_insert(double) add rbp, 8 add r13, 24 cmp r14, rbp jne .L2В принципе, имеет право на жизнь, но гулять так гулять, давайте снимем с программиста заботу о создании параллельного индекса, ровно как сделали в питоне, благо стандарт c++17 имеет structural binding!
Итак, можно сделать следующим образом:
#include #include #include "range.h" struct vec3 < double x,y,z; >; int main() < std::vectorpoints = ,,>; std::vector weights = ; for (auto [i, p]: enumerate(points)) < std::cerr return 0; >Функция enumerate() определена в следующем заголовочном файле:
#ifndef __RANGE_H__ #define __RANGE_H__ #include #include #include constexpr auto range(int n) < struct iterator < int i; void operator++() < ++i; >bool operator!=(const iterator& rhs) const < return i != rhs.i; >const int &operator*() const < return i; >>; struct wrapper < int n; auto begin() < return iterator; > auto end() < return iterator; > >; return wrapper; > template constexpr auto enumerate(T && iterable) < struct iterator < int i; typedef decltype(std::begin(std::declval())) iterator_type; iterator_type iter; bool operator!=(const iterator& rhs) const < return iter != rhs.iter; >void operator++() < ++i; ++iter; >auto operator*() const < return std::tie(i, *iter); >>; struct wrapper < T iterable; auto begin() < return iterator; > auto end() < return iterator; > >; return wrapper; > #endif // __RANGE_H__ При компиляции с флагами -std=c++17 -Wall -Wextra -pedantic -O2 мы получим следующий ассемблерный код (проверьте тут):
.L14: movsd xmm0, QWORD PTR [rbx] mov edi, OFFSET FLAT:_ZSt4cerr call std::basic_ostream >& std::basic_ostream >::_M_insert(double) mov rdi, rax mov rax, QWORD PTR [rsp+32] movsd xmm0, QWORD PTR [rax+rbp] call std::basic_ostream >& std::basic_ostream >::_M_insert(double) add rbx, 24 add rbp, 8 cmp r12, rbx jne .L14И снова компилятор начисто убрал обёртку (правда, для этого пришлось поднять уровень оптимизации с -O1 на -O2 ).
Кстати, в c++20 появился std::ranges , что ещё больше упрощает написание такой функции, но я пока не готов переходить на этот стандарт.
Вопрос залу
На ваш взгляд, каким должен быть совершенный цикл в 2020м году? Научите меня!
Если вы ещё не задавались этим вопросом, то скопируйте к себе в пет-проект заголовочный файл range.h и попробуйте его поиспользовать хотя бы несколько дней.
Основанное на диапазоне выражение for (C++)
Циклически и последовательно выполняет оператор ( statement ) каждого элемента в выражении ( expression ).
Синтаксис
for ( for-range-declaration : Выражение )
инструкция
Комментарии
Используйте оператор на основе for диапазона для создания циклов, которые должны выполняться через диапазон, который определяется как все, что можно выполнить, например , или любая другая последовательность стандартной библиотеки C++, std::vector диапазон которой определен begin() в и end() . Имя, объявленное в for-range-declaration части , является локальным for для оператора и не может быть повторно объявлено в expression или statement . Обратите внимание, что auto ключевое слово является предпочтительным в for-range-declaration части инструкции .
Новые возможности Visual Studio 2017: Циклы на основе for диапазонов больше не требуют, чтобы begin() и end() возвращали объекты одного типа. Это позволяет end() возвращать объект sentinel, например используемый диапазонами, как определено в предложении Ranges-V3. Дополнительные сведения см. в статье Обобщение цикла Range-Based For и библиотеки range-v3 на сайте GitHub.
В этом коде показано, как использовать циклы на основе for диапазона для итерации массива и вектора:
// range-based-for.cpp // compile by using: cl /EHsc /nologo /W4 #include #include using namespace std; int main() < // Basic 10-element integer array. int x[10] = < 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 >; // Range-based for loop to iterate through the array. for( int y : x ) < // Access by value using a copy declared as a specific type. // Not preferred. cout cout << endl; // The auto keyword causes type inference to be used. Preferred. for( auto y : x ) < // Copy of 'x', almost always undesirable cout cout << endl; for( auto &y : x ) < // Type inference by reference. // Observes and/or modifies in-place. Preferred when modify is needed. cout cout << endl; for( const auto &y : x ) < // Type inference by const reference. // Observes in-place. Preferred when no modify is needed. cout cout v; for (int i = 0; i < 10; ++i) < v.push_back(i + 0.14159); >// Range-based for loop to iterate through the vector, observing in-place. for( const auto &j : v ) < cout cout
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 end of integer array test 0.14159 1.14159 2.14159 3.14159 4.14159 5.14159 6.14159 7.14159 8.14159 9.14159 end of vector test Цикл на основе for диапазона завершается, когда выполняется одна из этих инструкций break в statement : , return или goto оператор с меткой за пределами цикла на основе for диапазона. Оператор continue в цикле на основе for диапазона завершает только текущую итерацию.
Имейте в виду следующие факты о диапазоне: for
- Такие циклы автоматически распознают массивы.
- Такие циклы автоматически распознают контейнеры с методами .begin() и .end() .
- Для всех остальных итераторов в них используются поиск, зависящий от аргументов ( begin() и end() ).
Range-based for Statement (C++)
Executes statement repeatedly and sequentially for each element in expression .
Syntax
for ( for-range-declaration : expression )
statement
Remarks
Use the range-based for statement to construct loops that must execute through a range, which is defined as anything that you can iterate through—for example, std::vector , or any other C++ Standard Library sequence whose range is defined by a begin() and end() . The name that is declared in the for-range-declaration portion is local to the for statement and cannot be re-declared in expression or statement . Note that the auto keyword is preferred in the for-range-declaration portion of the statement.
New in Visual Studio 2017: Range-based for loops no longer require that begin() and end() return objects of the same type. This enables end() to return a sentinel object such as used by ranges as defined in the Ranges-V3 proposal. For more information, see Generalizing the Range-Based For Loop and the range-v3 library on GitHub.
This code shows how to use range-based for loops to iterate through an array and a vector:
// range-based-for.cpp // compile by using: cl /EHsc /nologo /W4 #include #include using namespace std; int main() < // Basic 10-element integer array. int x[10] = < 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 >; // Range-based for loop to iterate through the array. for( int y : x ) < // Access by value using a copy declared as a specific type. // Not preferred. cout cout << endl; // The auto keyword causes type inference to be used. Preferred. for( auto y : x ) < // Copy of 'x', almost always undesirable cout cout << endl; for( auto &y : x ) < // Type inference by reference. // Observes and/or modifies in-place. Preferred when modify is needed. cout cout << endl; for( const auto &y : x ) < // Type inference by const reference. // Observes in-place. Preferred when no modify is needed. cout cout v; for (int i = 0; i < 10; ++i) < v.push_back(i + 0.14159); >// Range-based for loop to iterate through the vector, observing in-place. for( const auto &j : v ) < cout cout
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 end of integer array test 0.14159 1.14159 2.14159 3.14159 4.14159 5.14159 6.14159 7.14159 8.14159 9.14159 end of vector test A range-based for loop terminates when one of these in statement is executed: a break , return , or goto to a labeled statement outside the range-based for loop. A continue statement in a range-based for loop terminates only the current iteration.
Keep in mind these facts about range-based for :
- Automatically recognizes arrays.
- Recognizes containers that have .begin() and .end() .
- Uses argument-dependent lookup begin() and end() for anything else.