разворачивание циклов в функции особого случая

Поэтому я пытаюсь оптимизировать некоторый код. У меня есть функция с циклом переменного размера. Однако для эффективности я хочу сделать чехлы с петлями 1, 2 и 3 размера, специальные случаи, которые полностью развернуты. Мой подход до сих пор заключается в том, чтобы объявить размер цикла как константный параметр, а затем определить функции-оболочки, которые вызывают основную функцию, передавая ей литерал для константного значения. Я включил фрагмент кода, иллюстрирующий то, что я имею в виду.

inline void someFunction (const int a)
{
    for (int i=0; i<a; i++)
    {
        // do something with i.
    }
}

void specialCase()
{
    someFunction (3);
}

void generalCase(int a)
{
    someFunction (a);
}

Итак, мой вопрос: разумно ли ожидать, что мой компилятор (GCC) развернет цикл for внутри specialCase. Я имею в виду, что, очевидно, я могу скопировать и вставить содержимое someFunction в specialCase и заменить a на 3, но я бы предпочел иметь дело только с одним определением someFunction в моем коде для ясности.


person p clark    schedule 18.09.2017    source источник
comment
Для этого есть Godbolt, проверьте сами.   -  person Hatted Rooster    schedule 18.09.2017
comment
Вы действительно выиграете от развертывания коротких циклов размером 1, 2, 3 вместо того, чтобы пытаться оптимизировать длинные циклы?   -  person user7860670    schedule 18.09.2017
comment
Если вы не хотите копировать pase, почему бы не сделать do_something_with(i) отдельной (встроенной) функцией и позволить компилятору выполнить копирование для do_something_with(1); do_something_with(2);.   -  person Bo Persson    schedule 18.09.2017
comment
да, потому что в моем примере из реального мира это не просто один цикл в функции, а несколько, некоторые из них вложены в 3 или 4 цикла в глубину. и эта функция будет вызываться снова и снова, это главное узкое место программы. Предыдущая версия программы вручную разворачивала все циклы и была нечитаемой (и поддерживала только 3 прохода через этот один класс цикла, я хочу поддерживать как минимум 1, 2 или 3)   -  person p clark    schedule 18.09.2017
comment
к сожалению, Godbolt предполагает, что петли не будут развернуты.   -  person p clark    schedule 18.09.2017


Ответы (3)


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

Вы измерили, что это на самом деле быстрее? Я сомневаюсь, что это будет (или что компилятор не развернет цикл автоматически).


Мой подход до сих пор заключается в том, чтобы объявить размер цикла как константный параметр, а затем определить функции-оболочки, которые вызывают основную функцию, передавая ей литерал для константного значения.

const здесь ничего не значит. Это не повлияет на способность компилятора разворачивать цикл. Это просто означает, что a нельзя изменить внутри тела функции, но он по-прежнему является аргументом времени выполнения.


Если вы хотите обеспечить развертывание, то сделайте это принудительно. Это довольно просто с С++ 17.

template <typename F, std::size_t... Is>
void repeat_unrolled_impl(F&& f, std::index_sequence<Is...>)
{
    (f(std::integral_constant<std::size_t, Is>{}), ...);
}

template <std::size_t Iterations, typename F>
void repeat_unrolled(F&& f)
{
    repeat_unrolled_impl(std::forward<F>(f), 
                         std::make_index_sequence<Iterations>{});
}

живой пример на godbolt

person Vittorio Romeo    schedule 18.09.2017
comment
простой ответ: я не понимаю шаблоны, кроме самых основ. - person p clark; 18.09.2017

Если вы не любите шаблоны и не доверяете своему компилятору, всегда есть этот метод, вдохновленный устаревшим методом ручного развертывания циклов, который называется «устройство даффа»:

void do_something(int i);

void do_something_n_times(int n)
{
    int i = 0;
    switch(n)
    {
        default:
            while(n > 3) {
                do_something(i++);
                --n;
            }
        case 3: do_something(i++);
        case 2: do_something(i++);
        case 1: do_something(i++);
    }
}

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

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

Он был изобретен Томом Даффом в 1983 году.

https://en.wikipedia.org/wiki/Duff%27s_device

Его использование с современными компиляторами сомнительно.

person Richard Hodges    schedule 18.09.2017
comment
размещение битов тела основного цикла во встроенных функциях - мое последнее средство. В частности, встроенный, потому что в противном случае было бы слишком много параметров для передачи. - person p clark; 18.09.2017
comment
@pclark Я не знаю вашего точного варианта использования, но не бойтесь делегировать части вашей функции лямбда-выражениям с захватом переменных, аргументами или и тем, и другим. Оптимизатор компилятора должен со всем этим быстро справиться. - person Richard Hodges; 18.09.2017
comment
лямбда-исчисление - это не то, что я слишком хорошо знаю, а тем более его реализация на С++. Мои знания С++ 11 и выше очень шаткие. Поэтому я подумал, что лучше спросить здесь совета. Мое приложение представляет собой системный решатель ОДУ для класса ОДУ, из которых 1-й, 2-й и 3-й случаи будут наиболее распространенными. - person p clark; 18.09.2017
comment
Делегирование @pclark функции или лямбе, если они определены в одном файле, будет оптимальным, поскольку компилятор может видеть все пути кода. Структурирование вашего кода на более мелкие функции, конечно, может упростить код. Но вы это уже знали :) Стоит повторить, что компиляторы C++ стали очень хорошо различать ваши намерения. В окончательном коде будут сокращения, которые могут вас удивить, так что не беспокойтесь о ручной оптимизации. Часто это мешает компилятору. - person Richard Hodges; 18.09.2017
comment
Я удалил свои комментарии сейчас, так как они больше не актуальны :-) - person cmaster - reinstate monica; 19.09.2017

Я бы предпочел пойти по этому пути, если вы хотите использовать встроенную (нестандартную) функцию всех популярных компиляторов:

__attribute__((always_inline))
void bodyOfLoop(int i) {
  // put code here
}

void specialCase() {
    bodyOfLoop(0);
    bodyOfLoop(1);
    bodyOfLoop(2);
}

void generalCase(int a) {
    for (int i=0; i<a; i++) {
        bodyOfLoop(i);
    }
}

Примечание: это решение GCC/Clang. Используйте __forceinline для MSVC.

person geza    schedule 18.09.2017