Долой циклы, или Неленивая композиция алгоритмов в C++

    "Кто ни разу не ошибался в индексировании цикла, пусть первый бросит в деструкторе исключение."

    — Древняя мудрость

    Циклы ужасны. Циклы сложно читать — вместо того, чтобы сразу понять намерение автора, приходится сначала вникать в код, чтобы понять, что именно он делает. В цикле легко ошибиться с индексированием и переопределить индекс цикла во вложенном цикле. Циклы сложно поддерживать, исправлять в случае ошибок, сложно вносить текущие изменения, и т.д. и т.п.


    В конце концов, это просто некрасиво.


    Человечество издревле пытается упростить написание циклов. Вначале программисты подметили часто повторяющиеся циклы и выделили их в отдельные функции. Затем они придумали ленивые итераторы, а потом и диапазоны. И каждая из этих идей была прорывом. Но, несмотря на это, идеал до сих пор не достигнут, и люди продолжают искать способы улучшить свой код.


    Данная работа ставит своей целью пролить свет на отнюдь не новую, но пока что не слишком распространённую идею, которая вполне способна произвести очередной прорыв в области написания программ на языке C++.


    Так как же писать красивый, понятный, эффективный код, а также иметь возможность параллелить большие вычисления лёгким движением пальцев по клавиатуре?



    Содержание


    1. Существующие модели
    2. Базовые понятия
      1. Определение №1: свёртка
      2. Определение №2: ядро свёртки
    3. Идеология
      1. Факт №1: каждый цикл можно представить в виде свёртки
      2. Факт №2: большинство циклов расладываются на простые составляющие
      3. Факт №3: каждую свёртку можно представить в виде автомата
      4. Факт №4: автоматы комбинируются
      5. Снова к свёртке
    4. Я птичка, мне такое сложно, можно я сразу код посмотрю?
      1. Простой пример
      2. constexpr
    5. Многопоточность
    6. Сравнительная таблица
    7. Ссылки


    Существующие модели


    Основные на текущий момент способы избавления от циклов — это алгоритмы из стандартной библиотеки и ленивые итераторы и диапазоны из библиотек Boost.Iterator, Boost.Range и range-v3.


    range-v3 частично попали в стандартную библиотеку C++20, но, во-первых, попали они туда в достаточно усечённом виде, а во-вторых, соответствующих реализаций на текущий момент пока нет.

    Стандартные алгоритмы прекрасны, и помогают избаваться от циклов, но, к сожалению, только в самых простых случаях, посколько несколько таких алгоритмов невозможно скомбинировать в единое вычисление. Для каждого шага придётся хранить промежуточный результат. А это и перерасход по памяти, и сложности с выводом типов для промежуточных результатов, то есть усложнение кода.


    Именно из-за этого появились ленивые итераторы и диапазоны в сторонних библиотеках, а в C++17 появились гибриды семейства std::transform_reduce.


    Ленивые итераторы и диапазоны решают многие проблемы. Но они сами не лишены своих собственных проблем. В частности, поскольку они отделены от схемы вычислений (они определяют только операции над отдельными элементами последовательности), их сложно параллелить. А стандартные алгоритмы уже с C++17 имеют параллельные версии, способные более эффективно использовать многоядерные архитектуры.


    Возникает вопрос: можно ли объединить преимущества обоих подходов одновременно? Оказывается, можно. Об этом и пойдёт речь далее.



    Базовые понятия


    Для того, чтобы двинуться далее, необходимо разобраться с тем, что такое свёртка.



    Определение №1: свёртка


    Свёртка — это вычислительный процесс, производимый над некоторой последовательностью значений по правилу, задаваемому ядром свёртки.


    Результат свёртки — значение, полученное последовательным применением ядра свёртки к текущему значению и очередному элементу последовательности.



    Определение №2: ядро свёртки


    Ядро свёртки — это действие, производимое на каждом шаге свёртки. Применяется к текущему значению свёртки и очередному элементу последовательности.


    Свёртка


    На этом рисунке изображена свёртка последовательности $\{x_0, x_1, x_2\}$ с ядром $f$ и начальным значением $v_0$. $v_3$ — результат свёртки.


    В стандартной библиотеке свёртка представлена алгоритмами std::accumulate и std::reduce.



    Идеология


    Итак, для того, чтобы понять основную идею данного подхода, нужно обратить внимание на несколько известных фактов.



    Факт №1: каждый цикл можно представить в виде свёртки


    И действительно:


    1. Контекст программы перед началом цикла — начальное значение;
    2. Набор индексов, контейнер, диапазон и т.п. — последовательность элементов;
    3. Итерация цикла — применение двуместной операции (ядра свёртки) к текущему значению и очередному элементу последовательности, в результате чего текущее значение изменяется.

    auto v = 0;                   // Начальное значение: v_0
    for (auto i = 0; i < 10; ++i) // Последовательность: [x_0, x_1, ...]
    {
        v = f(v, i);              // Двуместная операция, изменяющая
                                  // значение: v_{i + 1} = f(v_i, x_i)
    }

    Иначе говоря, для того, чтобы выразить любой цикл, достаточно базиса из одной единственной операции — свёртки. А все остальные операции — например, стандартные алгоритмы, — можно выразить через неё.


    Пример №1: отображение через свёртку


    template <ForwardIterator I, OutputIterator J, UnaryFunction F>
    J transform (I begin, I end, J result, F f)
    {
        // Начальное значение — это выходной итератор.
        auto initial_value = result;
        // Ядро свёртки.
        auto binary_op =
            [f] (auto iterator, auto next_element)
            {
                // Записываем в текущий итератор результат отображения...
                *iterator = f(next_element);
                // ... и возвращаем продвинутый итератор.
                return ++iterator;
            };
        // Свёртка.
        return accumulate(begin, end, initial_value, binary_op);
    }

    Пример №2: фильтрация через свёртку


    template <ForwardIterator I, OutputIterator J, UnaryPredicate P>
    J copy_if (I begin, I end, J result, P p)
    {
        // Начальное значение.
        auto initial_value = result;
        // Ядро свёртки.
        auto binary_op =
            [p] (auto iterator, auto next_element)
            {
                if (p(next_element))
                {
                    *iterator = next_element;
                    ++iterator;
                }
                return iterator;
            };
        // Свёртка.
        return accumulate(begin, end, initial_value, binary_op);
    }

    Аналогичным образом выражаются и все остальные последовательные алгоритмы. Любознательный читатель может проделать это в качестве упражнения.



    Факт №2: большинство циклов расладываются на простые составляющие


    Если присмотреться, то станет понятно, что большинство циклов — типовые. Они раскладываются на простые составляющие:


    • Преобразование;
    • Фильтрация;
    • Группировка;
    • Подсчёт;
    • Суммирование;
    • Запись в массив;
    • ...
    • и т.д.

    Это значит, что нужно подобрать достаточно выразительный базис операций, чтобы их комбинациями покрыть подавляющее большинство возможных циклов, а также научиться легко и удобно составлять эти комбинации с точки зрения программного кода.



    Факт №3: каждую свёртку можно представить в виде автомата


    По определению, автомат — это система, которая может пребывать в различных состояниях, а переход между этими состояниями происходит при произведении на систему определённого воздействия.


    Так, если рассматривать свёртку как автомат, то состояния этого автомата — это совокупность возможных значений переменной, а воздействие — это применение ядра свёртки к текущему значению переменной и очередному элементу последовательности.


    Важно:

    В данной модели рассматривается обобщение автоматов, когда есть не только входные символы, под действием которых происходит переход между состояниями, но и выходные символы, сопутствующие этому переходу.
    На диаграмме входной символ рисуется над стрелками переходов, а выходной — под стрелкой.

    Кроме того, наш автомат может обладать памятью.

    Автомат


    Пример №1: автомат для отображения


    Например, так будет выглядеть автомат для отображения (transform, или map в функциональном программировании).


    Автомат для отображения


    Здесь $a$ — входной символ, $f$ — функция преобразования.


    Данный автомат имеет одно состояние и один переход. Каждый входной символ $a$ он преобразует с помощью функции $f$, и результат этого преобразования подаёт на выход. После этого возвращается в исходное состояние.


    Пример №2: автомат для фильтрации


    Автомат для фильтрации


    Здесь $a$ — входной символ, $p$ — предикат, $\epsilon$ — обозначение пустого символа.


    Данный автомат имеет одно состояние и два перехода. Один переход реализуется тогда, когда входной символ $a$ удовлетворяет предикату $p$. В этом случае на выход подаётся сам символ $a$. В случае, если символ $a$ не удовлетворяет предикату, на выход подаётся пустой символ $\epsilon$ (то есть ничего не подаётся). В обоих случаях автомат возвращается в исходное состояние.



    Факт №4: автоматы комбинируются


    Если у автомата есть выход, то, очевидно, этот выход можно подать на вход другому автомату.


    Композиция автоматов


    Таким образом, имея набор из нескольких автоматов, каждый из которых задаёт одну операцию преобразования, можно составлять достаточно сложные преобразования.



    Снова к свёртке


    Чтобы получить нужную нам свёртку, в конец цепочки мы поставим автомат, который представляет собой ядро свёртки.


    Цепочка с ядром в конце


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


    Схлопнули


    Итак, мы разложили цикл на простые составляющие и представили с помощью свёртки. В теории всё прекрасно, но как же это будет выглядеть в коде?



    Код


    На основе изложенных выше идей разработана библиотека Проксима.



    Простой пример


    #include <proxima/compose.hpp>
    #include <proxima/kernel/sum.hpp>
    #include <proxima/reduce.hpp>
    #include <proxima/transducer/stride.hpp>
    #include <proxima/transducer/take_while.hpp>
    #include <proxima/transducer/transform.hpp>
    
    #include <cassert>
    
    int main ()
    {
        const int items[] = {1, 2, 3, 4, 5};
        const auto kernel =
            proxima::compose
            (
                proxima::transform([] (auto x) {return x * x;}),   // 1. Каждый элемент возведён в квадрат;
                proxima::stride(2),                                // 2. Берутся только элементы с номерами,
                                                                   //    кратными двойке (нумерация с нуля);
                proxima::take_while([] (auto x) {return x < 10;}), // 3. Элементы берутся до тех пор, пока
                                                                   //    они меньше десяти;
                proxima::sum                                       // 4. Результат суммируется.
            );
        const auto x = proxima::reduce(items, kernel);
        assert(x == 10); // 1 * 1 + 3 * 3
    }


    constexpr


    Можно отметить, что код из примера может быть выполнен на этапе компиляции:


    #include <proxima/compose.hpp>
    #include <proxima/kernel/sum.hpp>
    #include <proxima/reduce.hpp>
    #include <proxima/transducer/stride.hpp>
    #include <proxima/transducer/take_while.hpp>
    #include <proxima/transducer/transform.hpp>
    
    int main ()
    {
        constexpr int items[] = {1, 2, 3, 4, 5};
        constexpr auto kernel =
            proxima::compose
            (
                proxima::transform([] (auto x) {return x * x;}),   // 1. Каждый элемент возведён в квадрат;
                proxima::stride(2),                                // 2. Берутся только элементы с номерами,
                                                                   //    кратными двойке (нумерация с нуля);
                proxima::take_while([] (auto x) {return x < 10;}), // 3. Элементы берутся до тех пор, пока
                                                                   //    они меньше десяти;
                proxima::sum                                       // 4. Результат суммируется.
            );
        constexpr auto x = proxima::reduce(items, kernel);
        static_assert(x == 10); // 1 * 1 + 3 * 3
    }

    Большая часть Проксимы может быть выполнена на этапе компиляции.



    Многопоточность


    Одна из ключевых особенностей описываемой модели состоит в том, что она легко поддаётся параллелизации.


    В Проксиме существует механизм, с помощью которого очень легко распараллеливать вычисления. Это делается с помощью фиктивного преобразователя pipe, который выполняет роль "разделителя потоков":


    proxima::reduce(values,
        proxima::compose
        (
            proxima::for_each(hard_work), // | Поток №1
                                          // ----------
            proxima::pipe,                //            Разделитель потоков
                                          // ----------
            proxima::for_each(hard_work), // | Поток №2
                                          // ----------
            proxima::pipe,                //            Разделитель потоков
                                          // ----------
            proxima::for_each(hard_work), // | Поток №3
            proxima::sum                  // | Поток №3
        ));

    Запись выше означает, что будут созданы три потока, и в каждом из них будет выполняться только часть работы над очередным элементом последовательности.


    Чтобы показать эффективность такого разбиения, рассмотрим пример (полный код лежит на Гитлабе).


    В нём будем замерять разницу между распараллеленной в три потока свёрткой, обычной свёрткой и простым циклом. Для имитации "тяжёлых" вычислений сделаем функцию, которая просто засыпает на несколько микросекунд. И сгенерируем набор случайных чисел, которые и будут определять время засыпания.


    auto hard_work (std::int32_t time_to_sleep)
    {
        std::this_thread::sleep_for(std::chrono::microseconds(time_to_sleep));
    }
    
    const auto proxima_crunch_parallel =
        [] (auto b, auto e)
        {
            return
                proxima::reduce(b, e,
                    proxima::compose
                    (
                        proxima::for_each(hard_work),
                        proxima::pipe,
                        proxima::for_each(hard_work),
                        proxima::pipe,
                        proxima::for_each(hard_work),
                        proxima::sum
                    ));
        };
    
    const auto proxima_crunch =
        [] (auto b, auto e)
        {
            return
                proxima::reduce(b, e,
                    proxima::compose
                    (
                        proxima::for_each(hard_work),
                        proxima::for_each(hard_work),
                        proxima::for_each(hard_work),
                        proxima::sum
                    ));
        };
    
    const auto loop_crunch =
        [] (auto b, auto e)
        {
            auto sum = typename decltype(b)::value_type{0};
            while (b != e)
            {
                hard_work(*b);
                hard_work(*b);
                hard_work(*b);
    
                sum += *b;
                ++b;
            }
    
            return sum;
        };

    Если сгенерировать 1000 случайных засыпаний в диапазоне от 10 до 20 микросекунд, то получим следующую картину (показано время работы соответствующего обработчика — чем меньше, тем лучше):


    proxima_crunch_parallel | 0.0403945
    proxima_crunch          | 0.100419
    loop_crunch             | 0.103092

    И чем "жирнее" будут вычислительные функции, тем больше будет отрыв многопоточной версии. Например, если взять случайные засыпания в диапазоне от 100 до 200 микросекунд, то картина будет следующей:


    proxima_crunch_parallel | 0.213352
    proxima_crunch          | 0.624727
    loop_crunch             | 0.625393

    То есть почти в три раза быстрее, как было бы при идеальном разложении на три потока.



    Сравнительная таблица


    Библиотека STL (алгоритмы) Boost range-v3 Проксима
    Компонуемость Нет Да Да Да
    Вывод типов Плохо Средне Средне Хорошо
    Параллелизация Почти* Нет Нет Да
    Совместимость Boost STL STL Всё
    Расширяемость Сложно Нормально Сложно Легко
    Самостоятельность Да Да Да Не совсем
    constexpr Частично Нет Частично** Да***
    Модель Монолитная Ленивая Ленивая Неленивая

    *) Параллелизация в STL ещё не везде реализована.

    **) constexpr диапазонов, видимо, будет лучше, когда они попадут в STL.

    ***) constexpr Проксимы зависит от STL. Всё, что своё — уже constexpr. Всё, что зависит от STL, будет constexpr как только в STL оно будет таковым.


    Ссылки


    1. Проксима
    2. Алгоритмы STL
    3. atria::xform
    4. Boost.Iterator
    5. Boost.Range
    6. range-v3
    7. Абстрактный автомат
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 47

      +1
      Комментарии к коммитам на русском — это конечно сильно)
        +3
        Очень круто. Как будто какой-нибудь ФП-шный хаскелевский Data.List в C++ перетащили. Надо добавить в Boost. Правда от 90% до 99% программистов все-равно будут у себя писать циклы по-старинке, максимум — с использованием известных функций STL.
          0

          Спасибо :) .

          +4

          Скажите, а если ядро свёртки ассоциативно, я могу как-то распараллелить не промежуточные операции, а итоговую свёртку? Ну, чтобы разбить исходную последовательность на несколько кусков и каждый кусок обрабатывать на своём потоке.

            0

            Отмечу, что это позволит нормально использовать кэш процессора, что в отдельных случаях приводит к ускорению кода на 2 порядка.


            Было бы интересно посмотреть на замеры скорости cache-friendly цикла и этого решения.

              0

              Спасибо за вопрос. В текущей версии нет, но вообще, конечно, да. Просто пока не было времени реализовать. Если есть желание и возможность, с радостью приму помощь.

              +2
              Привлекли термины попавшие в заголовок статьи «циклы», «алгоритмы». Традиционно именно циклы используют в алгоритмах сортировки массивов. Можно пример «простой» сортировки (вставка, пузырек, выбор...), алгоритм которой должен состоять из двух циклов. Не хочу никого обижать, но действительно, очень желал бы увидеть, какой это будет «красивый, понятный, эффективный код». Только в рекурсивном выражении не нужно, в этой формулировке Эрланг уже получил приз за высокую «красивость и неэффективность», там вот одной строки хватает:
              q([])->[];q([H|T])->[q([X<-T,X=<H])]++[H|q([X<-T,X>H])].

              upd: даже раскраска исходного текста не выдержала, только первый символ смогла отделить, ха-ха, похоже, её реализовал тот, кто умеет красиво и эффективно одновременно.
              upd2: почему только первый идентификатор функции выделяет цветом, почему далее по тексту, три раза встречается «кюю» и почему оно не выделилось…, а если вводить с новой строки — то сработает, получается лексемы не верно выделяет, парсер какой-то «левый»:
              q([])->[];
              q([H|T])->[q([X<-T,X=<H])]++[H|q([X<-T,X>H])].

              upd3: как так, почему на профильном сайте такая ситуация, отмечаю текст необходимым языком, а это приводит к созданию картины неясности и недопонимания конструкций этого языка, а в дальнейшем это приводит к исключении его из списка языков, так уже Пролог «почил» уже более года назад, лично отмечено…
              upd4: ну и на последок, а что показывает «индустрия», как это будет выглядеть в другом стиле:
              q([])->[];q([H|T])->[q([X<-T,X=<H])]++[H|q([X<-T,X>H])].

                +6

                на профильном сайте страничка с тысячью комментариями жрёт ресурсов больше чем современные компьютерные игры, а вы тут про расскрасски :)

                  0
                  Не, думаю там виной вселенский заговор, это Хром занимает все ресурсы драйверами всех типов видеокамер, что бы следить за человечеством в пользу Гугла.
                    +1
                    Вот именно. Нормальный браузер весь целиком, вместе со страничкой,
                    потребляет порядка 23 Мб

                    И это с прогрузкой графики и форматированием. Чисто текстовые браузеры жрали бы ещё меньше.
                  +1
                  Я Нелениво выполнил вручную итерации цикла и получил такую композицию
                  уменьшая влияние проблем в раскраске синтаксиса на суть:
                  qsort( X ) when X = [] -> []; 
                  qsort( [H | T] ) - >
                           L = qsort([X || X <-T , X<H]),
                           R = qsort([X || X <-T , X>=H]),
                           L ++ [H] ++ R.

                  сверху все примеры с опечаткой были, тут устранено
                  +2

                  Прям Matlab, как-то написал в стиле без циклов прототип в матлабе, а потом понял что релиз то на си надо >.<

                    +1
                    Циклы ужасны. Циклы сложно читать — вместо того, чтобы сразу понять намерение автора, приходится сначала вникать в код, чтобы понять, что именно он делает. В цикле легко ошибиться с индексированием и переопределить индекс цикла во вложенном цикле. Циклы сложно поддерживать, исправлять в случае ошибок, сложно вносить текущие изменения, и т.д. и т.п.

                    С++ ужасны. С++ сложно читать — вместо того, чтобы сразу понять намерение автора, приходится сначала вникать в код, чтобы понять, что именно он делает. В С++ легко ошибиться. С++ сложно поддерживать, исправлять в случае ошибок, сложно вносить текущие изменения, и т.д. и т.п.

                    Можно подставить что угодно. Где доказательства? Чем обоснованы эти утверждения?
                    Если автор не умеет понятно писать, язык программирования тут не причем. А избавлять императивный язык от циклов затея бестолковая. Если у вас высокоуровневый код то там циклов почти нет. А в низкоуровневом они никому не мешают и таскать туда STL,Boost,range-v3 и другие велосипеды не всегда хорошая идея.

                    Если вы хотите строить вычислительный граф и потом его преобразовывать и объединять с другими графами и искать оптимальный, то это надо делать до компиляции. В C++ нет встроенных средств языка для преобразования вычислительных графов. А предложение использовать убогий препроцессор и новые марсианские фичи С++ для данной задачи и потом надеяться что он всё оптимизирует говоря не дальновидно. Не надо смешивать всё в кучу ибо сложность будет нарастать экспоненциально. И проблем будет создано больше чем решено. Лучше разбить на отдельные простые части и есть слона по частям.
                    Что мешает вызывать из высокоуровневого кода черный ящик, оптимизированный под конкретную железяку.

                    ps: «Человечество издревле пытается упростить написание циклов» — первый раз слышу что бы это было важнее свежей тротуарной плитки.
                      0
                      Если автор не умеет понятно писать

                      Это можно легко проверить, заглянув в репозиторий.


                      избавлять императивный язык от циклов затея бестолковая

                      C++ — мультипарадигменный язык.


                      это надо делать до компиляции

                      Где доказательства? Чем обоснованы эти утверждения?
                      ;)


                      ps

                      Я не могу к каждой шутливой фразе делать сноску "юмор".

                        +2
                        Вы совершенно правы! Я прямо умилился, читая статью — сразу видно, автор не знает что, например, почти все реальные вычислительные алгоритмы (а это именно то, что загружает процессоры) написаны на фортране — это я к тому, что в фортране кроме цикла и goto особо ничего и не используется (ну еще if тернарный :). То есть критерий истины — практика — говорит о том, что правильный софт — только циклы, только goto…
                          –1
                          почти все реальные вычислительные алгоритмы (а это именно то, что загружает процессоры) написаны на фортране

                          А какая доля этих программ написана в этом веке?

                            +2
                            Встречный вопрос — а какая доля программ написана на С++ до 1970 года и до сих пор используются?
                              –1
                              Встречный вопрос — а какая доля программ написана на ЯП, первая версия которого появилась в 1985 году, до 1970 года и до сих пор используются?

                              Уточнил вопрос.

                            0

                            Описанная Вами практика общепризнанно является порочной. Использование goto в Фортране не требуется и порицается еще с момента выхода стандарта 90 в 91-м году, то есть уже на протяжении 30-и лет. Актуальных программ, где "кроме цикла и goto особо ничего и не используется", почти не осталось — все переписано или переписываются на соврмененный стандарт Фортрана или C++ по очень многим причинам, в том числе сходным с отмеченными автором.
                            Кроме того, высокопроизводительное вычислительное ПО сейчас — это далеко не только, и даже, к моему сожалению, не столько Фортран, это еще C или C++, а иногда смесь Фортрана и C++.

                              0
                              За те же 30 лет практики программирования я ни разу не встречался с людьми, которые бы считали такую практику порочной — откуда берется это «общепризнанно»?
                              Ну это, конечно, может быть ошибка выжившего — но я пишу программы либо в стиле повествования (это хорошо на Аде делать или Прологе), либо в стиле работы с графами, и тогда циклы и особенно goto совершенно естественны. И к тому же в процессоре есть только одна основная команда управления ходом вычислений — переход (условный или безусловный) — вот и получается, что преобразование исходного текста в машинный код лучше делать (и результат будет эффективнее), если и там и там одни переходы и вычисления.
                              Я, конечно, видел иной стиль написания программ — вообще без переходов, ветвлений и циклов — только одни вычисления… Но это было сгенерировано автоматически и вселяло ужас своей невероятностью…
                              И хотя я знаю, откуда пошло это клеймение goto, ни я, ни многие другие программисты не понимают, чем плох goto, а теперь уже и циклы… Видимо, это связано с ослаблением умственных способностей программистов, не в обиду будь сказано. И надо сказать, что ни lapack, ни mkl, ни множество других высокоэффективных программ расчетов никогда, видимо (ну не в ближейшие 10-30 лет) не будут переписаны с фортрана (а уж там одни goto и циклы, поверьте!) — банально потому что работают, и там нет ошибок :)
                              Интересно ваше замечание о смеси с C++ — это что же, оболочки на нем, что ли пишут?
                                0

                                На Ваш первый вопрос мне трудно дать исчерпывающий ответ. Скажу, что никогда не встречал ни одной рекомендации в духе: "используйте goto вместо if-then-else". Управлаемый goto в последней редакции стандарта официально вынесен в список устаревших конструкций, подлежащих удалению из стандарта.


                                Использовать goto не нужно тогда, когда для этого нет причин.

                                Его активное использование плохо тем, что запутывает код для восприятия и программистом, что усложняет развитие кода, и компилятором, который в таких случаях избегает применения оптимизаций. С другой стороны, в подавляющем большинстве случаев явные конструкции if-then-else, do, do while с exit и cycle абсолютно ничем не уступают goto, но они гораздо более выразительны. Хотя я могу себе представить алгоритмы, где использование goto может принести выгоду, это, все-таки, скорее исключение, и почти всегда goto если используется, то именно вместо указанных выше стандартных конструкций.


                                И в целом, не видел я ни одной серьезной программы на Фортране с goto, common-областями, процедурами по 1000 строк с именами длиной 5 символов (это все составляющие одного и того же стиля), без сомнения написанной программистами с высокими представлениями о своих умственных способностях, в которой не нашлось бы банальных (и, вообще-то, серьезных) ошибок с памятью. Просто потому, что все программисты — люди, а люди ошибаются. Использование наделенных абстрактным смыслом избыточных, но выразительных, конструкций сродни такой культуре и позволяет обнаружить многие ошибки еще на этапе компиляции, а не через два года эксплуатации. А это особенно важно именно в численных методах.


                                Современный Фортран поддерживает ООП и допускает использование элементов функционального подхода, он хорошо оптимизируем и сравнительно безопасен, в чем является противоположностью старому Фортрану. При всем этом он остается высокопроизводительным ЯП. Но ассоциации с "фишками" Фортрана-77 приводят к неуклонному снижению его популярности.


                                Про MKL пишут, что она на писана на "C/C++, Fortran". Фортрановская часть кода MKL никак не обосновывает разработку новых программ теми же методами.


                                На C++ написана куча вычислительных программ. Тот же GEANT4, который переписан с Фортрана еще в 90-х для того, чтобы развиваться. Вообще, с Фортрана, к сожалению, уходят, на C++, текущий пример.
                                Писать интерфейсы вычислительных программ на C++ сейчас особого смысла нет — есть методы проще и эффективнее.

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

                                    Если получается решать задачи на Питоне, то Фортран там скорее всего не сильно и нужен, так как будет больше ограничений и меньше библиотек. Фортран ближе к железу: например, сечения массивов в Питоне — это скорее синтаксический сахар, а они же в Фортране — почти прямое указание компилятору использовать SIMD-инструкции для векторизации.
                                    Фортран лучше подходит для разработки сложных программ, жизненный цикл которых измеряется десятилетиями, а там основной выбор лежит между Фортраном и C/C++.

                                    0
                                    > Управлаемый goto в последней редакции стандарта официально вынесен в список устаревших конструкций, подлежащих удалению из стандарта.

                                    Простите, а при чём тут computed GOTO к общей теме поддержки GOTO? Или что-то после N2146 публично доступно и говорит про устаревание простого GOTO?
                                    (Я тоже за то, чтобы вместо GOTO использовать почти везде структурные конструкции, но именно этот момент смущает.)

                                    > Но ассоциации с «фишками» Фортрана-77 приводят к неуклонному снижению его популярности.

                                    77 уже был продвижением вперёд — как классика вспоминается IV или 66 :)
                                      0
                                      Простите, а при чём тут computed GOTO к общей теме поддержки GOTO? Или что-то после N2146 публично доступно и говорит про устаревание простого GOTO?

                                      Пишу про парадигму и стиль программирования. Речь шла о "кроме цикла и goto особо ничего и не используется". Управляемый goto, просто goto, имена подпрограмм по 4-6 символов, и даже размножение фрагмента кода с заменой имен переменных и одной строки — все это обычно идет в одном комплекте.
                                      Про вывод самого goto из стандарта не слышал, и думаю, что вряд ли это произойдет.


                                      77 уже был продвижением вперёд — как классика вспоминается IV или 66 :)

                                      Согласен. Уже в этом стандарте постоянное использование goto было не обязательно. Но, к сожалению, в моей среде многие его новшества были прогнорированы, кроме, разве что, оператора include.


                                      Возможно, в корне этого спора лежит различие подразумеваемых областей применения. Использование обсуждаемых приемов программирования в библиотеке для операций с двумя матрицами, реализованной "раз и навсегда", наверное, не так критично.

                                    –1
                                    > И хотя я знаю, откуда пошло это клеймение goto, ни я, ни многие другие программисты не понимают, чем плох goto, а теперь уже и циклы… Видимо, это связано с ослаблением умственных способностей программистов, не в обиду будь сказано.

                                    Когда считалось нормой задумчиво сидеть с ручкой над листингами и выдавать как результат 1 отлаженную строку кода за рабочий день… ну может тогда и можно было тратить умственные способности на плоскую плетёнку с GOTO, и даже допускать приёмчики типа прыжка из середины одного цикла в середину другого цикла (видел я как-то в юности такой код и впечатлён до сих пор).

                                    Но уже в начале-середине 80-х стали запрещать (в разумных пределах) эти фокусы — в середину цикла, например, вы так уже не перейдёте. Разумеется, сохраняется возможность эмулировать циклы, структурный IF и прочее на сплошных GOTO — но зачем?
                              +1
                              а куда стоит податься, если не до конца понимаешь потенциал всего описанного?
                                0

                                Ну, наверное, можно пройтись по ссылкам в конце статьи.
                                Или задать какой-нибудь конкретный вопрос, я постараюсь ответить.

                                  0
                                  Можете посоветовать книжку-учебник по плюсам 17/20 стандартов? Я учил по книжке Страуструпа и какому-то этюднику для 03, и даже тогда плюсы были очень рыхлыми. Я сейчас из всех «свежих» плюсов более-менее понимаю только шаблоны :) Понятно, что прочесть сниппет могу, но вот код писать не возьмусь.
                                    0
                                    C++17 — The Complete Guide
                                    по 20му едва ли уже успели написать что-то стоящее
                                      0

                                      Не думаю, что по 17-м плюсам необходим отдельный учебник.
                                      Если нужно просто понять суть современных плюсов, то вполне достаточно последней редакции Страуструпа (она включает 14-й стандарт).
                                      Также можно почитать Майерса — "Эффективный современный C++".


                                      Вот про 20-й было бы неплохо отдельную книжку иметь, но мне такие неизвестны.

                                        0
                                        так он только только вышел же
                                          0
                                          Jens Gustedt умудряется писать маны для ещё не вышедшего стандарта С. Правда, он в комитете.
                                            0
                                            по 20му стандарту тоже были маны по принятым преложениям или тому что еще рассматривается, там ведь не за одну встречу принимают весь стандарт, но книги из серии «стандарт еще вышел, и половина рассказаного еще не принята» у меня лично вызывает вопрос «зачем?», зачем было писать книгу о стандарте если он не закончен на момент выхода книги
                                        0

                                        Недавно вышел именно учебник, "Modern C++ for Absolute Beginners" (подзаголовок: "A Friendly Introduction to C++ Programming Language and C++11 to C++20 Standards"), Slobodan Dmitrović. Есть ещё пара недавних книг (не учебников), в которые я заглядывал: "Modern C++ Tutorial: C++11/14/17/20 On the Fly", Changkun Ou и "C++ Best Practices", Jason Turner. От комментариев, что в этих книгах хорошо / плохо воздержусь, заглядывал только поверхностно. Возможно, стоит обратить внимание на вышедшее летом 2018-го второе издание "A Tour of C++ (C++ In-Depth Series)", Bjarne Stroustrup.

                                          0
                                          Спасибо. Это было внезапно :)
                                            0

                                            Зашёл на эту запись по ассоциации, прочитав свежий пост izvolov -а.


                                            Да и книги вышли внезапно, относительно недавно. Я узнал о двух из них, слушая подкаст "CppCast", Jason Turner — его соведущий. С Слободаном у них был выпуск (Джейсон как раз свою книгу писал тогда, расспрашивал Слободана), а потом о выходе книги Джейсона упомянули между делом. Книга Чангкуна не такая новая; она в свободном доступе (на Гитхабе) и, вероятно, обновляется.


                                            Ожидаю, что в ближайшее время появится несколько новых редакций книг, в названии которых "C++17" будет заменено на "C++20": тот же эффект, как три года назад (когда в названии ставили C++17). Я тогда тоже поверхностно пролистал несколько книг, но не был впечатлён (попадалась откровенная халтура).

                                    0

                                    Спасибо, интересно! А как со длительностью компиляции обстоят дела у вашей библиотеки? Оригинальные ranges Ниблера компилируются прям ооочень долго (вроде бы в основном из-за самодельных концептов).

                                      +1

                                      Довольно шустро, хотя специальных замеров не делал. С Ниблером несопоставимо :) .

                                        0

                                        Здорово!

                                      +3

                                      Еще такой вопрос, не про библиотеку, а скорее про свертки.
                                      Может быть у меня мозги не обучены еще в таких понятиях думать, но мне все время кажется, что свертки хорошо смотрятся, если цикл:


                                      • по всей коллекции целиком
                                      • затрагивает либо каждый элемент по отдельности, либо только соседние элементы, либо элементы, подчиняющиеся какому-то паттерну
                                      • не удаляет элементы

                                      В то время как обычный цикл таких ограничений лишен — я могу спокойно удалить третий, пятый и 19-ый элемент, при этом начав проход со второго, а закончив на 3 элемента раньше конца.
                                      Понятное дело, что так писать нехорошо и это скорее всего симптом плохого дизайна, но все же?

                                        +1
                                        удалить третий, пятый и 19-ый элемент

                                        Никаких проблем. Можем сделать преобразователь, удаляющий n-й элемент по счёту, и собрать из них любую схему удалений.


                                        начав проход со второго, а закончив на 3 элемента раньше конца

                                        Границы удобнее задавать итераторами, но тоже можно, если хочется.


                                        const auto result =
                                            proxima::reduce(items.begin() + 2, items.end() - 3,
                                                proxima::compose
                                                (
                                                    drop_nth(3),
                                                    drop_nth(5),
                                                    drop_nth(19),
                                                    proxima::sum
                                                ));
                                          0

                                          А drop_nth не сбивает нумерацию?

                                            0

                                            Смотря как сделать :).
                                            Можно сделать сбивающим, но многопозиционным:


                                            const auto result =
                                                proxima::reduce(items.begin() + 2, items.end() - 3,
                                                    proxima::compose
                                                    (
                                                        drop_nth(3, 5, 19),
                                                        proxima::sum
                                                    ));
                                            0

                                            Уболтали :) Спасибо!

                                          0
                                          Ленивые итераторы и диапазоны решают многие проблемы. Но они сами не лишены своих собственных проблем. В частности, поскольку они отделены от схемы вычислений (они определяют только операции над отдельными элементами последовательности), их сложно параллелить.

                                          Можете пояснить про недостатки итераторов? И как понять "отделены от схемы вычислений"?

                                            0

                                            В данном случае речь идёт о том, что итератор определяет обход последовательности и выдачу элементов.
                                            При этом итератор не знает, что будут делать с выданными им элементами: умножать, складывать, что-то ещё.


                                            Из проблем, навскидку:


                                            • Неочевидные просадки по производительности в простых случаях (например, если поставить filter после transform, который читает из файла или делает что-то долгое). При этом код корректен, компилируется и работает.
                                            • Накладные расходы на хранение данных в сложных итераторах (например, чтобы решить предыдущую проблему, можно создать итератор, который будет кэшировать промежуточные вычисления. Но чтобы это засунуть в итератор, потребуется завернуть кэш во что-то типа shared_ptr, а это уже лишний уровень косвенности.

                                          Only users with full accounts can post comments. Log in, please.