Функция оптимизирована для постоянной времени компиляции

Предположим, у меня есть функция вычисления длины вектора, у которой есть дополнительный параметр inc (он сообщает расстояние между соседними элементами). Простая реализация:

float calcLength(const float *v, int size, int inc) {
    float l = 0;

    for (int i=0; i<size*inc; i += inc) {
        l += v[i]*v[i];
    }
    return sqrt(l);
}

Теперь calcLength можно вызывать с двумя типами inc параметров: когда inc известен во время компиляции, и когда нет. Я хотел бы иметь оптимизированную версию calcLength для общих значений времени компиляции inc (например, 1).

Итак, у меня было бы что-то вроде этого:

template <int C>
struct Constant {
    static constexpr int value() {
        return C;
    }
};

struct Var {
    int v;

    constexpr Var(int p_v) : v(p_v) { }

    constexpr int value() const {
        return v;
    }
};

template <typename INC>
float calcLength(const float *v, int size, INC inc) {
        float l = 0;

        for (int i=0; i<size*inc.value(); i += inc.value()) {
            l += v[i]*v[i];
        }
        return sqrt(l);
    }
}

Итак, это можно использовать:

calcLength(v, size, Constant<1>()); // inc is a compile-time constant 1 here, calcLength can be vectorized

or

int inc = <some_value>;
calcLength(v, size, Var(inc)); // inc is a non-compile-time constant here, less possibilities of compiler optimization

Мой вопрос: можно ли каким-то образом сохранить исходный интерфейс и автоматически вставить _11 _ / _ 12_, в зависимости от типа (константа времени компиляции или нет) inc?

calcLength(v, size, 1); // this should end up calcLength(v, size, Constant<1>());
calcLength(v, size, inc); // this should end up calcLength(v, size, Var(int));

Примечание: это простой пример. В моей реальной проблеме у меня есть несколько функций, таких как calcLength, и они большие, я не хочу, чтобы компилятор встраивал их.


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

  • алгоритм указывается один раз (скорее всего, в шаблонной функции)
  • если я укажу 1 как inc, будет создана специальная функция, и код, скорее всего, будет векторизован
  • если inc не является константой времени компиляции, вызывается общая функция
  • в противном случае (константа времени компиляции, отличная от 1): не имеет значения, какая функция вызывается

person geza    schedule 19.03.2019    source источник
comment
AFAIK, если вся функция constexpr, передача константы времени компиляции ничего вам не даст. Однако вы можете сделать константу параметром шаблона, не являющимся типом. Тогда значение будет известно во время компиляции, и компилятор сможет соответствующим образом оптимизировать.   -  person NathanOliver    schedule 19.03.2019
comment
@NathanOliver: насколько я понимаю, это то, что я делаю в вопросе. С одним отличием: чтобы разрешить оба вида inc, у него есть параметр шаблона типа. Но результат тот же.   -  person geza    schedule 19.03.2019
comment
Вы ищете if constexpr?   -  person Jesper Juhl    schedule 19.03.2019
comment
Я имею в виду такую ​​функцию, как template <std::size_t inc> float calcLength(const float *v, int size) { use inc here as a compile time value }.   -  person NathanOliver    schedule 19.03.2019
comment
@NathanOliver: ваше предложение имеет тот же результат, что и мое решение, если Constant<X> используется как inc.   -  person geza    schedule 19.03.2019
comment
Есть ли у вас какие-либо тесты, соответствующие вашему мнению о лучшей оптимизации? Я могу представить себе гипотетические случаи, если inc% 8 == 0 или inc% 16 == 0, но не уверен, что это может быть векторизовано намного лучше.   -  person Dmitry    schedule 19.03.2019
comment
@Dmitry: в моем случае, если inc известен во время компиляции, это будет 1 99% времени. И, конечно, его можно оптимизировать намного лучше. У него огромная разница в скорости.   -  person geza    schedule 19.03.2019
comment
@geza Я думаю, у вас есть тесты, значит опубликуйте тест, чтобы я мог убедиться, что мое решение работает.   -  person anatolyg    schedule 20.03.2019
comment
@anatolyg: У меня есть тесты, но не для этого простого случая. Но на самом деле этот вопрос не нуждается в тесте. Это скорее языковой вопрос. По сути, я хотел бы иметь функцию, которая может быть автоматически скомпилирована для постоянной времени компиляции. Мой код работает, но мне не нравится инструкция _1 _ / _ 2_. Я бы хотел, чтобы это происходило автоматически.   -  person geza    schedule 20.03.2019
comment
Итак, у вас есть доказательства того, что этот подход лучше подходит для вашей архитектуры, чем просто встроить функцию и позволить оптимизатору беспокоиться об этом? Это было бы хорошо объяснить или хотя бы упомянуть в вопросе.   -  person aschepler    schedule 20.03.2019
comment
@aschepler: Я упомянул в своем вопросе, что у меня есть несколько функций, и они огромны. Я абсолютно уверен, что компилятор не будет их встраивать из-за их размера. Мне нужно использовать какую-нибудь forceinline функцию. Но я не хочу, потому что размер скомпилированного кода будет намного больше. Было бы ошибкой встроить эти функции в любую текущую архитектуру.   -  person geza    schedule 20.03.2019
comment
@JesperJuhl: Я не знаю, как использовать if constexpr в своей проблеме, так что, наверное, нет.   -  person geza    schedule 20.03.2019
comment
Но если inc не константа времени компиляции, а значение 1, какую функцию следует вызвать? Ничего страшного, если это называется Constant<1> версией?   -  person max66    schedule 20.03.2019
comment
@ max66: в принципе, это не так. Но я думаю, что понимаю, почему вы спрашиваете об этом: я мог бы добавить небольшую встроенную функцию-оболочку, которая проверяет 1. Мне не очень нравится это решение, потому что оно добавляет ненужное if для случая константы, не связанной с временем компиляции. Если это единственное решение, я буду продолжать использовать _1 _ / _ 2_.   -  person geza    schedule 20.03.2019
comment
std :: integration_constant, но, похоже, это не сработало: godbolt.org/z/YuSK0L   -  person Mooing Duck    schedule 12.04.2019
comment
Теперь, когда я включил оптимизацию, обе версии рассчитывались во время компиляции: godbolt.org/z/-s1xNS   -  person Mooing Duck    schedule 12.04.2019
comment
Если вы не слишком возражаете против переносимости, __builtin_constant_p - отличный инструмент для такого рода оптимизации.   -  person Marc Glisse    schedule 12.04.2019
comment
Если вы используете GCC, как предложил @MarcGlisse, __builtin_constant_p будет работать, но если условия по-прежнему выполняются один в этот пример ...   -  person Hiroki    schedule 12.04.2019


Ответы (3)


Если цель здесь просто оптимизировать, а не разрешить использование в контексте времени компиляции, вы можете дать компилятору подсказки о своем намерении:

static float calcLength_inner(const float *v, int size, int inc) {
    float l = 0;

    for (int i=0; i<size*inc; i += inc) {
        l += v[i]*v[i];
    }
    return sqrt(l);
}

float calcLength(const float *v, int size, int inc) {
    if (inc == 1) {
        return calcLength_inner(v, size, inc);  // compiler knows inc == 1 here, and will optimize
    }
    else {
        return calcLength_inner(v, size, inc);
    }
}

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

Это трюк C (и широко используется внутри numpy), но вы можете написать простую оболочку, чтобы упростить использование в C ++:

// give the compiler a hint that it can optimize `f` with knowledge of `cond`
template<typename Func>
auto optimize_for(bool cond, Func&& f) {
    if (cond) {
        return std::forward<Func>(f)();
    }
    else {
        return std::forward<Func>(f)();
    }
}

float calcLength(const float *v, int size, int inc) {
    return optimize_for(inc == 1, [&]{
        float l = 0;
        for (int i=0; i<size*inc; i += inc) {
            l += v[i]*v[i];
        }
        return sqrt(l);
    });
}
person Eric    schedule 21.09.2019
comment
Хороший улов по пропавшей отдаче, исправлено - person Eric; 21.09.2019
comment
Ссылка Godbolt добавлена - person Eric; 21.09.2019

C ++ не предоставляет способа определить, является ли предоставленный параметр функции константным выражением или нет, поэтому вы не можете автоматически различать предоставленные литералы и значения времени выполнения.

Если параметр должен быть параметром функции, и вы не желаете изменять способ его вызова в двух случаях, то единственный рычаг, который у вас есть, - это тип параметра: ваши предложения for Constant<1>() vs Var(inc) довольно хороши в этом отношении.

person Anthony Williams    schedule 26.03.2019

Вариант 1. Доверьтесь компилятору (или ничего не делайте)

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

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

Компилятор может полностью встроить эту функцию, потенциально делая вашу проблему не проблемой (вы можете помочь ей, указав ее встроенным в заголовок, используя lto и / или используя специфические атрибуты компилятора, такие как __attribute__((always_inline)))

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

Вариант 2: две перегрузки

float calcLength(const float *v, int size, int inc) {
    float l = 0;

    for (int i=0; i<size*inc; i += inc) {
        l += v[i]*v[i];
    }
    return sqrt(l);
}

template <int Inc>
float calcLength(const float *v, int size) {
    float l = 0;

    for (int i=0; i<size*inc; i += inc) {
        l += v[i]*v[i];
    }
    return sqrt(l);
}

Недостатком здесь является дублирование кода, ofc. Также необходимо проявлять небольшую осторожность на месте звонка:

calcLength(v, size, inc); // ok
calcLength<1>(v, size);   // ok
calcLength(v, size, 1);   // nope

Вариант 3: Ваша версия

Ваша версия в порядке.

person bolov    schedule 21.09.2019
comment
@geza отличное предложение, но похоже, что оно все еще требует значительного объема работы. - person bolov; 21.09.2019