Регистрация

[Ненормальное программирование, Программирование, Совершенный код, C++] Совершенный цикл

Ответить на тему
Автор Сообщение
news_bot ®

Стаж: 6 лет 3 месяца
Сообщений: 27286

Создавать темы news_bot ® написал(а)
26-Авг-2020 19:32
Цитировать

Сегодня необычный для меня формат статьи: я скорее задаю вопрос залу, нежели делюсь готовым рецептом. Впрочем, для инициации дискуссии рецепт тоже предлагаю. Итак, сегодня мы поговорим о чувстве прекрасного :)
Я довольно давно пишу код, и так вышло, что практически всегда на C++. Даже и не могу прикинуть, сколько раз я написал подобную конструкцию:
for (int i=0; i<size; i++) {
    [...]
}

Хотя почему не могу, очень даже могу:
find . \( -name \*.h -o -name \*.cpp \) -exec grep -H "for (" {} \; | wc -l
43641

Наш текущий проект содержит 43 тысячи циклов. Проект пилю не я один, но команда маленькая и проект у меня не первый (и, надеюсь, не последний), так что в качестве грубой оценки пойдёт. А насколько такая запись цикла for хороша? Ведь на самом деле, важно даже не то количество раз, когда я цикл написал, а то количество раз, когда я цикл прочитал (см. отладка и code review). А тут речь очевидно идёт уже о миллионах.
На КПДВ узел под названием «совершенная петля» (perfection loop).

Так каков он, совершенный цикл?
А в чём проблема?
Мы пишем много кода для математического моделирования; код довольно плотный, с огромным количеством целых чисел, которые являются индексами ячеек, функций и прочей лабуды. Чтобы был понятен масштаб проблемы, давайте я просто приведу крохотный кусочек кода из нашего проекта:
for (int iter=0; iter<nb_iter; iter++) {          // some iterative computation
    for (int c=0; c<mesh.cells.nb(); c++)         // loop through all tetrahedra
        for (int lv=0; lv<4; lv++)                // for every vertex of the tet
            for (int lv1 = lv0+1; lv1<4; lv1++)   // do stuff for subsequent vertices
                for (int d=0; d<3; d++) {         // for each of 3 dimensions
                    nlRowScaling(weight);
                    nlBegin(NL_ROW);
                    nlCoefficient(mesh.cells.vertex(c, lv0)*3 + d,  1);
                    nlCoefficient(mesh.cells.vertex(c, lv1)*3 + d, -1);
                    nlEnd(NL_ROW);
                }
    [...]
}

У нас есть некая область, разбитая на тетраэдры, и мы на ней моделируем некий процесс. Для каждой итерации процесса мы проходимся по всем тетраэдрам сетки, затем по всем вершинам каждого тетраэдра, бла-бла-бла, и всё венчает цикл по всем трём измерениям нашего окружающего мира.
Мы обязаны иметь дело с кучей вложенных циклов; вышеприведённые пять вложенных далеко не предел. Мы уже довольно давно (лет пятнадцать как) пришли к выводу, что стандартный for (int i=0; i<size; i++) — это очень громоздкая конструкция: те самые пять вложенных заголовков for превращаются в совершенно нечитаемую кашу, и даже подсветка синтаксиса не спасает.
Когда мы читаем стандартный for(;;), мы должны на каждой строчке обратить внимание на три вещи: на инициализацию, на условие выхода и собственно на инкремент. Но ведь это совершеннейший оверкилл для тех случаев, когда нам нужно пройтись от 0 до size-1, а это подавляющее большинство всех циклов. Скажите, как часто вам приходится писать обратный цикл или итерацию с другими границами? Как мне кажется, один раз из десяти — это ещё щедрая оценка.
До появления c++11 мы в итоге пришли к страшной вещи, а именно ввели в самый верхний заголовок вот такой дефайн:
#define FOR(I,UPPERBND) for(int I = 0; I<int(UPPERBND); ++I)

И тогда вышеприведённый кусок кода превращается из тыквы в кабачок:
FOR(iter, nb_iter) {
    FOR(c, mesh.cells.nb())
        FOR(lv0, 4)
            for (int lv1 = lv0+1; lv1<4; lv1++)
                FOR(d, 3) {
                    nlRowScaling(weight);
                    nlBegin(NL_ROW);
                    nlCoefficient(mesh.cells.vertex(c, lv0)*3 + d,  1);
                    nlCoefficient(mesh.cells.vertex(c, lv1)*3 + d, -1);
                    nlEnd(NL_ROW);
                }
    [...]
}

Польза такой трансформации в том, что когда я встречаю for (;;), я знаю, что мне нужно насторожиться и внимательно смотреть на все три места (инициализацию, условие, инкремент). В то время как если я вижу FOR(,) то это совершенно стандартный пробег от 0 до n-1 без каких-либо тонкостей. Я совершенно не предлагаю пользоваться вышеприведённым дефайном, но точно знаю, что для нашей команды он сберёг много ресурсов мозга, поскольку мы кода гораздо больше читаем (см. отладка), нежели пишем (как, наверное, и все программисты).
То есть, вопрос, которым я задаюсь, звучит так: "Как выглядит цикл, имеющий минимальную когнитивную нагрузку при чтении кода?"
Жизнь после 11го года, или range for
А как дела обстоят у соседей? Вы знаете, местами довольно недурно. Например, в лагере питонистов стандартный цикл выглядит следующим образом:
for i in range(n):
    print(i)

Что любопытно, до третьего питона range() создавал в памяти массив индексов, и проходился по нему. И со времён c++11 мы вполне можем делать точно так же!
#include <iostream>
int main() {
    int range[] = {0,1,2,3,4,5};
    for (int i : range) {
        std::cerr << i;
    }
}

Разумеется, явно создавать в памяти массив индексов это несерьёзно, и с третьей версии в питоне это тоже поняли. Но и в C++ мы можем сделать не хуже!
Давайте посмотрим на следующую функцию range(int n):
#include <iostream>
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{0}; }
        auto end()   { return iterator{n}; }
    };
    return wrapper{n};
}
int main() {
    for (int i: range(13)) {
        std::cerr << i;
    }
    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<char, std::char_traits<char> >::operator<<(int)
        add     ebx, 1
        cmp     ebx, 13
        jne     .L2
[...]

То есть, компилятор начисто убрал все эти обёртки и оставил голый инкремент, ровно как если бы мы написали обычный for (int i=0; i<13; i++).
Лично мне кажется, что for (int i: range(n)) справляется с подчёркиванием обычности цикла чуть хуже, нежели FOR(,), но тоже вполне достойно, и за это не нужно платить дополнительными тактами процессора.
Продолжаем подглядывать в замочную скважину: enumerate
Range for в c++11 нанёс большую пользу. Давайте скажем, что у меня есть массив трёхмерных точек, и мне нужно распечатать икс координаты каждой точки, это можно сделать следующим образом:
#include <vector>
#include <iostream>
struct vec3 {  double x,y,z;  };
int main() {
    std::vector<vec3> points = {{6,5,8},{1,2,3},{7,3,7}};
    for (vec3 &p: points) {
        std::cerr << p.x;
    }
    return 0;
}

for (vec3 &p: points) это прекрасная конструкция, никаких костылей, сразу из стандарта языка. Но что если у меня каждая точка из массива имеет цвет, вес или вкус? Это можно представить ещё одним массивом того же размера, что и массив точек. И тогда для доступа к атрибуту мне всё же понадобится индекс, который мы можем сгенерировать, например, вот таким образом:
std::vector<vec3> points = {{6,5,8},{1,2,3},{7,3,7}};
    std::vector<double> weights = {4,6,9};
    int i = 0;
    for (vec3 &p: points) {
        std::cerr << p.x << weights[i++];
    }

Для этого кода компилятор генерирует следующий ассемблер:

asm

SPL
.L2:
        movsd   xmm0, QWORD PTR [r13+0]
        mov     edi, OFFSET FLAT:_ZSt4cerr
        call    std::basic_ostream<char, std::char_traits<char> >& std::basic_ostream<char, std::char_traits<char> >::_M_insert<double>(double)
        movsd   xmm0, QWORD PTR [rbp+0]
        mov     rdi, rax
        call    std::basic_ostream<char, std::char_traits<char> >& std::basic_ostream<char, std::char_traits<char> >::_M_insert<double>(double)
        add     rbp, 8
        add     r13, 24
        cmp     r14, rbp
        jne     .L2

В принципе, имеет право на жизнь, но гулять так гулять, давайте снимем с программиста заботу о создании параллельного индекса, ровно как сделали в питоне, благо стандарт c++17 имеет structural binding!
Итак, можно сделать следующую функцию enumerate():
#include <vector>
#include <iostream>
#include <tuple>
#include <utility>
#include <iterator>
template <typename T> constexpr auto enumerate(T && iterable) {
    struct iterator {
        int i;
        typedef decltype(std::begin(std::declval<T>())) 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{0, std::begin(iterable)}; }
        auto end()   { return iterator{0, std::end  (iterable)}; }
    };
    return wrapper{std::forward<T>(iterable)};
}
struct vec3 {
    double x,y,z;
};
int main() {
    std::vector<vec3> points = {{6,5,8},{1,2,3},{7,3,7}};
    std::vector<double> weights = {4,6,9};
    for (auto [i, p]: enumerate(points)) {
        std::cerr << p.x << weights[i];
    }
    return 0;
}

При компиляции с флагами -std=c++17 -Wall -Wextra -pedantic -O2 мы получим следующий ассемблерный код (проверьте тут):

ASM

SPL
.L14:
        movsd   xmm0, QWORD PTR [rbx]
        mov     edi, OFFSET FLAT:_ZSt4cerr
        call    std::basic_ostream<char, std::char_traits<char> >& std::basic_ostream<char, std::char_traits<char> >::_M_insert<double>(double)
        mov     rdi, rax
        mov     rax, QWORD PTR [rsp+32]
        movsd   xmm0, QWORD PTR [rax+rbp]
        call    std::basic_ostream<char, std::char_traits<char> >& std::basic_ostream<char, std::char_traits<char> >::_M_insert<double>(double)
        add     rbx, 24
        add     rbp, 8
        cmp     r12, rbx
        jne     .L14

И снова компилятор начисто убрал обёртку (правда, для этого пришлось поднять уровень оптимизации с -O1 на -O2).
Кстати, в c++20 появился std::ranges, что ещё больше упрощает написание такой функции, но я пока не готов переходить на этот стандарт.
Вопрос залу
На ваш взгляд, каким должен быть совершенный цикл в 2020м году? Научите меня!
Если вы ещё не задавались этим вопросом, то вот ещё раз целиком заголовочный файл, попробуйте его поиспользовать хотя бы несколько дней в вашем пет-проекте:

range.h

SPL
#ifndef __RANGE_H__
#define __RANGE_H__
#include <tuple>
#include <utility>
#include <iterator>
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{0}; }
        auto end()   { return iterator{n}; }
    };
    return wrapper{n};
}
template <typename T> constexpr auto enumerate(T && iterable) {
    struct iterator {
        int i;
        typedef decltype(std::begin(std::declval<T>())) 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{0, std::begin(iterable)}; }
        auto end()   { return iterator{0, std::end  (iterable)}; }
    };
    return wrapper{std::forward<T>(iterable)};
}
#endif // __RANGE_H__

 ===========
 Источник:
habr.com
===========
Похожие новости: Теги для поиска: #_nenormalnoe_programmirovanie (Ненормальное программирование), #_programmirovanie (Программирование), #_sovershennyj_kod (Совершенный код), #_c++, #_vopros_zalu (вопрос залу), #_nenormalnoe_programmirovanie (
Ненормальное программирование
), #_programmirovanie (
Программирование
), #_sovershennyj_kod (
Совершенный код
), #_c++
Профиль  ЛС 
Показать сообщения:     
Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 16-Май 17:48
Часовой пояс: UTC + 5