Пример использования шаблонов для оптимизации - C/C++

Здравствуйте, chaotic-good, Вы писали:

CG>Ну так рекурсия же. ... Может если бы там был императивный цикл а не рекурсия, то все бы у компилятора получилось.

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

	Скрытый текст
	Посмотрел внимательнее, там в рекурсивном варианте icc сумел сделать несколько шагов, но не сумел довести до логичного конца вычисления, всё равно оставив исполняющийся всегда код с умножениями и переходами. Изменяя размер типа данных, наглядно видно, что для uint16_t этих шагов хватает для вычисления в compile-time, для uint64_t — нет, для uint32_t тоже не хватает, но ответ почти получен. В итеративном варианте этого уже нет — в compile-time не вычисляется ничего.

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

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

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

Ну, это по сути слегка изменённый пример оптимизации двоичного поиска из книги Бентли "Жемчужины программирования", тут, например, шаблоны немного помогают избавиться от ветвления — то, что jazzer упоминал здесь. Если нужен пример задачи, где шаблоны жгут, то это здесь.

Дисклеймер, однако:
Имеющий уши, да услышит.

Здравствуйте, chaotic-good, Вы писали:

CG>Я хочу придумать задачу, в которой шаблонный параметр целочисленного типа использовался бы для оптимизации.

умножение на константу. x*y выполняется медленнее чем x*constant.

Пример где это применяется привести не могу. Где-то хабре один чувак изголялся — делал многоуровневое вложение шаблонов и местами по тексту юзал шаблон умножения на константу.

CG>Я хочу придумать задачу, в которой шаблонный параметр целочисленного типа использовался бы для оптимизации. Что-то вроде:

Ну вот недавно делал, раскручивание цикла.
При желании можно еще немного дописать макросы, добавить возвращаемое значение, сделать возможность групировки вложености и т.д.

Здравствуйте, jazzer, Вы писали:

J>Так он же превратил хвостовую рекурсию в императивный цикл, в асме же видно. Казалось бы, в чем проблема сделать следующий шаг?

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

Здравствуйте, chaotic-good, Вы писали:

CG>Я хочу придумать задачу, в которой шаблонный параметр целочисленного типа использовался бы для оптимизации. Что-то вроде:

Использовал для оптимизации функции рассчета бита четности N младших бит числа.

код

//counter of significant bits in number
template <unsigned int x>
struct SignificantBits {
    static const unsigned int n = SignificantBits<x/2>::n + 1;
};

template <>
struct SignificantBits<0> {
    static const unsigned int n = 0;
};    

namespace parity_details{
    //structure implementing levels of parity computations
    template<int Level, typename T> struct Parity
    {
        static const int shifts = 1<<(Level-1);
        static T result(T x)
        {
            T tmp = Parity<Level - 1,T>::result(x);
            return tmp ^ (tmp >> shifts);    
        }

    };
    //recursion terminators
    template<typename T> struct Parity<1,T>
    {
        static T result(T x){return x ^ (x >> 1);}
    };
    //single-bit case
    template<typename T> struct Parity<0,T>
    {
        static T result(T x){return x;}
    };
}

//compute parity of N LSBs of x 
template<int N, typename T> 
inline 
typename std::enable_if<(std::numeric_limits<T>::digits > N) && (N > 0), T>::type 
compute_parity(T x)
{
    //mask bits involved
    x &=  (T(1)<<N) - 1;
    return ::parity_details::Parity<SignificantBits<N-1>::n,T>::result(x) & 1;
}
 
template<int N, typename T> 
inline 
typename std::enable_if<(std::numeric_limits<T>::digits == N), T>::type 
compute_parity(T x)
{
    return ::parity_details::Parity<SignificantBits<N-1>::n,T>::result(x) & 1;
}

template<int N, typename T> 
inline 
typename std::enable_if< (N > std::numeric_limits<T>::digits) || (N < 1), T>::type 
compute_parity(T x)
{
    static_assert(false,"compute_parity:invalid template parameters.");
    return x;
}

#endif

Здравствуйте, andyp, Вы писали:

A>Использовал для оптимизации функции рассчета бита четности N младших бит числа.

гоаздо быстрее это сделать, разделив число на куски по 10-11 бит и взяв для каждого из них чётность из таблицы. для int32 это будет всего 7 тактов

Здравствуйте, BulatZiganshin, Вы писали:

BZ>гоаздо быстрее это сделать, разделив число на куски по 10-11 бит и взяв для каждого из них чётность из таблицы. для int32 это будет всего 7 тактов

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

Здравствуйте, chaotic-good, Вы писали:

CG>Я хочу придумать задачу, в которой шаблонный параметр целочисленного типа использовался бы для оптимизации. Что-то вроде:
CG>

CG>template<int X>
CG>void func(...) {
CG>

Погугли про partial evaluation. Собственно hello world для partial evaluation — это обычно рекурсивный алгоритм возведения в константную степень. Степень константа, так что все ветвления и рекурсия раскрываются и это дает ускорение в несколько раз.
Если брать константные выражения не только примитивных типов, то следующий пример: алгоритмы какой-нить интерпретации по константной программе для интерпретатора. Например интерпретация символьного арифметического выражения по константному выражению.
Ну а дальше алгоритм интерпретации интерпретаторов по константному интерпретарору, получаем компилятор.
Ну а дальше еще никто не доходил )

Z>Погугли про partial evaluation. Собственно hello world для partial evaluation — это обычно рекурсивный алгоритм возведения в константную степень. Степень константа, так что все ветвления и рекурсия раскрываются и это дает ускорение в несколько раз.
Погугли constant folding и constant propagation. Функция возводящая в степень будет оптимизирована компилятором. Что-то такое:

int pow(int x, int y) {
    for (int i = 0; i < y; i++) {
        x *= x;
    }
}
pow(var, 3);

компилятор соптимизирует в две инструкции mul. Цикл будет развернут, так как значение y известно на этапе компиляции (без всяких шаблонов).

Z>Если брать константные выражения не только примитивных типов, то следующий пример: алгоритмы какой-нить интерпретации по константной программе для интерпретатора. Например интерпретация символьного арифметического выражения по константному выражению.

Рабочий пример? Это очень сложно сделать на шаблонах, я думаю не очень и нужно.

Мой поинт в том, что многие программисты просто недооценивают возможности компилятора и переусложняют код из-за этого, пытаясь оптимизировать раньше времени то, что компилятор может соптимизировать без них. Хороший пример это т.н. статический полиморфизм. "Эксперты" любят писать сложный код с CRTP, хотя если конкретный тип объекта может быть выведен статически, компилятор может девиртуализировать вызовы и получится тот же самый результат — статический вызов, но только без использования сложных шаблонов (a-la CRTP) и кучи кода в хедерах. Я просто поспорил кое с кем о том, что использование шаблонов "для скорости" это в 99% случаев ошибка (если это не класс-контейнер). Пока что местные программисты не смогли меня убедить в обратном

Здравствуйте, chaotic-good, Вы писали:

CG>Я хочу придумать задачу, в которой шаблонный параметр целочисленного типа использовался бы для оптимизации. Что-то вроде:

Например передача размерности конечномерного пространства через шаблонный параметр позволяет выводить размер значений типов представляющих вектора, матрицы и т.п. в compile-time, и соответственно избавляет от целого класса аллокаций и индерекций.

Здравствуйте, chaotic-good, Вы писали:

CG>Мой поинт в том, что многие программисты просто недооценивают возможности компилятора и переусложняют код из-за этого, пытаясь оптимизировать раньше времени то, что компилятор может соптимизировать без них. Хороший пример это т.н. статический полиморфизм. "Эксперты" любят писать сложный код с CRTP, хотя если конкретный тип объекта может быть выведен статически, компилятор может девиртуализировать вызовы и получится тот же самый результат — статический вызов, но только без использования сложных шаблонов (a-la CRTP) и кучи кода в хедерах.

Код со статическим/параметрическим полиморфизмом зачастую получается не только быстрее, но и проще. Несколько раз упомянутый тобой CRTP используется только в некоторых специфических случаях, в то время как для статического полиморфизма зачастую достаточно обыкновенной перегрузки, которая очевидно проще чем виртуальные вызовы и прочие индерекции, плюс value-semantic автоматически сохраняется (её можно получить и для динамического полиморфизма, но для этого требуется много движений).
Например попробуй переписать partition_point через динамический полиморфизм, и мы сравним:

template<typename I, typename P>
I partition_point(I first, I last, P p)
{
    while(first != last)
    {
        I middle = next(first, distance(first, last)/2);
        if( p(*middle) )
            last = middle;
        else
            first = next(middle);
    }
    return first;
}

CG>Я просто поспорил кое с кем о том, что использование шаблонов "для скорости" это в 99% случаев ошибка (если это не класс-контейнер).

Ошибка какого рода? Не добавляет скорости или "производительность в базу упирается"?

CG>Пока что местные программисты не смогли меня убедить в обратном

А что тебя сможет убедить? Какой-то пример или что?

EP>Код со статическим/параметрическим полиморфизмом зачастую получается не только быстрее, но и проще. Несколько раз упомянутый тобой CRTP используется только в некоторых специфических случаях, в то время как для статического полиморфизма зачастую достаточно обыкновенной перегрузки, которая очевидно проще чем виртуальные вызовы и прочие индерекции, плюс value-semantic автоматически сохраняется (её можно получить и для динамического полиморфизма, но для этого требуется много движений).
EP>Например попробуй переписать partition_point через динамический полиморфизм, и мы сравним:
EP>

EP>template<typename I, typename P>
EP>I partition_point(I first, I last, P p)
EP>{
EP>    while(first != last)
EP>    {
EP>        I middle = next(first, distance(first, last)/2);
EP>        if( p(*middle) )
EP>            last = middle;
EP>        else
EP>            first = next(middle);
EP>    }
EP>    return first;
EP>}
EP>

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

EP>Ошибка какого рода? Не добавляет скорости или "производительность в базу упирается"?

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

EP>Например передача размерности конечномерного пространства через шаблонный параметр позволяет выводить размер значений типов представляющих вектора, матрицы и т.п. в compile-time, и соответственно избавляет от целого класса аллокаций и индерекций.

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

template<int N>
void calcuate_things(array<N> const& m)

void calculate_things(Value* m, size_t sz);

const size_t sz = ...;
calculate_things(pvalue, sz);

ну может в первом случае он это сделает гарантированно, во втором — нет

Здравствуйте, chaotic-good, Вы писали:

EP>>Например передача размерности конечномерного пространства через шаблонный параметр позволяет выводить размер значений типов представляющих вектора, матрицы и т.п. в compile-time, и соответственно избавляет от целого класса аллокаций и индерекций.
CG>Без конкретного кода сложно это обсуждать. Подозреваю, что современный компилятор справится одинаково хорошо в обоих случаях:
CG>

CG>template<int N>
CG>void calcuate_things(array<N> const& m)
CG>

Скорее так:

template<int N>
Things calcuate(const Sequence<Vector<N>> &)
{
    // ...
    Vector<N> x = ... ;
    unordered_map<int, Vector<N>> y;
    // ...
}

Причём это N может и не использоваться во входных параметрах, а будет задавать размерность какого-либо внутреннего пространства. Например при использовании метода главных компонент или ортонормализации Грама—Шмидта.

Здравствуйте, chaotic-good, Вы писали:

CG>Я не утверждал что кругом нужно лепить динамический полиморфизм.

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

EP>>Ошибка какого рода? Не добавляет скорости или "производительность в базу упирается"?
CG>Ложное целеполагание. Некоторые считают что с помощью шаблонов можно получить более быстрый код, но по факту, никто ведь не сравнивает обычно

Выше привели сравнение — даже в простом случае код на шаблонах оказался быстрее чем constexpr функция (без форсирования compile-time контекста).
Сравнивать же каждый подобный случай, где очевидно что код на шаблонах будет не медленнее, а код без шаблонов не быстрее, при том что код на шаблонах зачастую более простой — необязательно.

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

Ты как-то слишком ловко от частного "для non-type template parameters, в некоторых частных случаях, аналог без шаблонов даст иногда даст такой же результат, а в общем случае не лучше" переходишь к общему "очень часто компилятор может оптимизировать код без шаблонов не хуже"

CG>>Я не утверждал что кругом нужно лепить динамический полиморфизм.
EP>Ты говорил что статический полиморфизм ведёт к сложному коду. По факту же, код зачастую получается намного проще.

Да, ведет к сложному коду. Как минимум к коду в хедерах, что уже усложняет сам код и процесс разработки. Простые алгоритмы — да, я согласен, становятся проще. Код всяких коллекций тоже выигрывает. Но вот остальное — едва ли. Просто мне часто доводилось видеть код, черезмерно злоупотребляющий шаблонами. Вот такой вот например:

template<class FwdIter>
class Foo {
....
void reset(FwdIter begin, FwdIter end) {
    std::vector<int> tmp(begin, end);
    std::swap(m_values, tmp);
    ...
}

я однаждый исправил на вот такое вот:

void Foo::reset(std::vector<int> newvals) {
    std::swap(newvals, m_values);
}

Ибо в проекте на 400К LOC он всегда использовался с вектором, за исключением одного случая в не критичном к производительности участке кода. Как ты наверное понимаешь, иметь подобные методы в хедерах ради перспективы использовать их с std::list или deque без лишнего копирования — очень сомнительна. Тупой код с конкретным типом стал проще, хочу заметить.

EP>>>Ошибка какого рода? Не добавляет скорости или "производительность в базу упирается"?
CG>>Ложное целеполагание. Некоторые считают что с помощью шаблонов можно получить более быстрый код, но по факту, никто ведь не сравнивает обычно
EP>Выше привели сравнение — даже в простом случае код на шаблонах оказался быстрее чем constexpr функция (без форсирования compile-time контекста).

Этот пример? Это все я могу и в матлабе посчитать, вставить в виде коснтанты в код и в комментарии описать алгоритм получения. В общем, не самый практичный пример.

EP>Ты как-то слишком ловко от частного "для non-type template parameters, в некоторых частных случаях, аналог без шаблонов даст иногда даст такой же результат, а в общем случае не лучше" переходишь к общему "очень часто компилятор может оптимизировать код без шаблонов не хуже"

В том то и дело что это не частные случаи. Ты можешь использовать шаблон для генерации более быстрого кода тогда, когда на этапе компиляции есть какая-нибудь информация и ты можешь развернуть какой-нибудь цикл или зафиксировать какой-нибудь параметр или избавиться от косвенного вызова через vtable, но то же самое компилятор делает постоянно и без твоей помощи, когда у него эта информация есть. Я когда на C# программировал — циклы вручную разворачивал иногда, так как там JIT компилятор тупой был, а для плюсов полно хороших оптимизирующих компиляторов, поэтому заниматься разворачиванием циклов (пусть и неявным) заниматься нет смысла практически никогда.

Здравствуйте, chaotic-good, Вы писали:

CG>>>Я не утверждал что кругом нужно лепить динамический полиморфизм.
EP>>Ты говорил что статический полиморфизм ведёт к сложному коду. По факту же, код зачастую получается намного проще.
CG>Да, ведет к сложному коду. Как минимум к коду в хедерах,

Встраивать код из другого translation unit это ещё сложнее, так как требует link-time code generation. Выше был пример фейла оптимизации на constexpr-функции, а если она будет ещё и в другом translation unit — то сфейлится и подавно.

CG>что уже усложняет сам код и процесс разработки.

Чем же код в headers сложнее? Чем усложняется процесс разработки?
Я наоборот предпочёл бы использовать header-only библиотеку, так это многое упрощает — и так будет до тех пор, пока не появятся модули

CG>Простые алгоритмы — да, я согласен, становятся проще. Код всяких коллекций тоже выигрывает. Но вот остальное — едва ли.

Чем по твоей классификации отличаются простые алгоритмы от сложных? И почему по-твоему простые на шаблонах получается проще, а сложные — нет?

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

CG>Просто мне часто доводилось видеть код, черезмерно злоупотребляющий шаблонами. Вот такой вот например:
CG> ...

А в этом коде вообще шаблон не нужен был. С vector<int> получается даже потенциально быстрее, например если передаётся rvalue.

CG>Ибо в проекте на 400К LOC он всегда использовался с вектором, за исключением одного случая в не критичном к производительности участке кода.
CG>Как ты наверное понимаешь, иметь подобные методы в хедерах ради перспективы использовать их с std::list или deque без лишнего копирования — очень сомнительна.

Не понимаю о каком лишнем копировании идёт речь — тут всегда создаётся временная копия.

CG>Тупой код с конкретным типом стал проще, хочу заметить.

В этом месте было неправильное использование шаблонов, которое не приносило никакой пользы, и даже вредило.
Если бы здесь была хоть какая-то польза от шаблонов, то был бы смысл обсуждать tradeoffs — а так, просто пример "так делать не надо", и такие примеры можно найти для любой технологии.

CG>Этот пример? Это все я могу и в матлабе посчитать, вставить в виде коснтанты в код и в комментарии описать алгоритм получения.

А если много разных аргументов? Причём которые вычисляются как промежуточные значения какого-то алгоритма? Будешь за каждым в матлаб бегать? Генерировать скриптом?

CG>В общем, не самый практичный пример.

Нормальный пример демонстрирующий то что шаблонный код оптимизируется даже лучше чем constexpr-функции

EP>>Ты как-то слишком ловко от частного "для non-type template parameters, в некоторых частных случаях, аналог без шаблонов даст иногда даст такой же результат, а в общем случае не лучше" переходишь к общему "очень часто компилятор может оптимизировать код без шаблонов не хуже"

CG>В том то и дело что это не частные случаи. Ты можешь использовать шаблон для генерации более быстрого кода тогда, когда на этапе компиляции есть какая-нибудь информация и ты можешь развернуть какой-нибудь цикл или зафиксировать какой-нибудь параметр или избавиться от косвенного вызова через vtable, но то же самое компилятор делает постоянно и без твоей помощи, когда у него эта информация есть.

Эти рассуждения теоретически верны, но на практике справедливы только для крайне малого класса случаев. Что уже успешно демонстрировалось примером выше. Тебе нужны ещё примеры?
Да, у компилятора+ликновщика (причём не только у C++) есть вся необходимая информация для крутых оптимизаций — но из этого никак не следует что в компиляторе все эти оптимизации реализованы. Из этого также не следует что подобные оптимизации будут выполнятся за какое-то вменяемое время.
Или, например, у компилятора есть необходимая информация для того чтобы автоматически переделать алгоритм на GPGPU, но он зараза этого не делает.
В общем из наличия возможности, никак не следует то что эта возможность была реализована

CG>Я когда на C# программировал — циклы вручную разворачивал иногда, так как там JIT компилятор тупой был, а для плюсов полно хороших оптимизирующих компиляторов, поэтому заниматься разворачиванием циклов (пусть и неявным) заниматься нет смысла практически никогда.

Разворачивать циклы вручную через рекурсивные шаблоны смысл есть, так как компиляторы далеко не всегда додумываются развернуть цикл с фиксированным числом итераций. Даже недавно подобная тема поднималась.
Шаблонный loop unroll используется во многих библиотеках, как раз потому что компиляторы не всегда способны его сделать

EP>Встраивать код из другого translation unit это ещё сложнее, так как требует link-time code generation. Выше был пример фейла оптимизации на constexpr-функции, а если она будет ещё и в другом translation unit — то сфейлится и подавно.

Ну это все сейчас умеют, даже студия

EP>Чем же код в headers сложнее? Чем усложняется процесс разработки?
EP>Я наоборот предпочёл бы использовать header-only библиотеку, так это многое упрощает — и так будет до тех пор, пока не появятся модули

Ключевое слово "библиотеку"

Если смотреть на это как application developer a не как library developer, то получается грусно. Вносить изменения в хедеры дороже, так как цикл разработки (edit -> compile -> run tests -> fix errors) замедляется. Изменил одну строчку и ждешь пока пересобирутся десять единиц трансляции, завязанных на этот хедер. У нас в конторе это крайне не приветствуется и в code style есть соотв. раздел про код в хедерах.

EP>Чем по твоей классификации отличаются простые алгоритмы от сложных? И почему по-твоему простые на шаблонах получается проще, а сложные — нет?

EP>Ты всё же попробуй переведи пример partition_point на динамический полиморфизм, хотя бы схематично.

Я немного во времени ограничен. Уверен что будет хуже чем с шаблонами, придется нагородить класс итератор с виртуальными ф-ями и использвать его. Получится полная хрень a-la java, но скорее всего работать будет не хуже. Если хочешь в code golf поиграть, могу потом как-нибудь наваять.

EP>А в этом коде вообще шаблон не нужен был. С vector<int> получается даже потенциально быстрее, например если передаётся rvalue.
EP>Не понимаю о каком лишнем копировании идёт речь — тут всегда создаётся временная копия.

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

EP>В этом месте было неправильное использование шаблонов, которое не приносило никакой пользы, и даже вредило.
EP>Если бы здесь была хоть какая-то польза от шаблонов, то был бы смысл обсуждать tradeoffs — а так, просто пример "так делать не надо", и такие примеры можно найти для любой технологии.

Угу. Вот только это оч. распространенная практика. Очень часто шаблоны появляются в коде там где они не нужны и половина таких случаев это begin end итераторы вместо конкретного типа либо параметр функтор — template<class Fn> void apply(Fn const& f); — который можно заменить std::function или чем-нибудь полиморфным.

EP>А если много разных аргументов? Причём которые вычисляются как промежуточные значения какого-то алгоритма? Будешь за каждым в матлаб бегать? Генерировать скриптом?

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

EP>Эти рассуждения теоретически верны, но на практике справедливы только для крайне малого класса случаев. Что уже успешно демонстрировалось примером выше. Тебе нужны ещё примеры?
EP>Да, у компилятора+ликновщика (причём не только у C++) есть вся необходимая информация для крутых оптимизаций — но из этого никак не следует что в компиляторе все эти оптимизации реализованы. Из этого также не следует что подобные оптимизации будут выполнятся за какое-то вменяемое время.
EP>Или, например, у компилятора есть необходимая информация для того чтобы автоматически переделать алгоритм на GPGPU, но он зараза этого не делает.
EP>В общем из наличия возможности, никак не следует то что эта возможность была реализована

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

EP>Разворачивать циклы вручную через рекурсивные шаблоны смысл есть, так как компиляторы далеко не всегда додумываются развернуть цикл с фиксированным числом итераций. Даже недавно подобная тема поднималась.
EP>Шаблонный loop unroll используется во многих библиотеках, как раз потому что компиляторы не всегда способны его сделать

Я там в той теме отписывался, честно попытался воспроизвести кейс с помощью клэнга 3.6 но ничего не получилось, он генерит здоровую ф-ю, которая проверяет нет ли алиасинга и потом если его нет — использует быстрый векторизованый цикл иначе — более сложную и медленную реализацию. В месте вызова оно вообще инлайнилось и векторизировалось. Я не смог заставить clang сгенирировать плохой код с включенными оптимизациями (-O2)

Здравствуйте, chaotic-good, Вы писали:

EP>>Встраивать код из другого translation unit это ещё сложнее, так как требует link-time code generation. Выше был пример фейла оптимизации на constexpr-функции, а если она будет ещё и в другом translation unit — то сфейлится и подавно.
CG>Ну это все сейчас умеют, даже студия

Тем не менее это дополнительный барьер.

EP>>Чем же код в headers сложнее? Чем усложняется процесс разработки?
EP>>Я наоборот предпочёл бы использовать header-only библиотеку, так это многое упрощает — и так будет до тех пор, пока не появятся модули

CG>Ключевое слово "библиотеку"

Если смотреть на это как application developer a не как library developer, то получается грусно.

При создании applications естественным образом получаются новые библиотеки. Причём процент того что называется "application code" мал, да и в основном это клей соединяющий библиотеки (свои и third-party).

CG>Вносить изменения в хедеры дороже, так как цикл разработки (edit -> compile -> run tests -> fix errors) замедляется. Изменил одну строчку и ждешь пока пересобирутся десять единиц трансляции, завязанных на этот хедер. У нас в конторе это крайне не приветствуется и в code style есть соотв. раздел про код в хедерах.

1. Precompiled headers.
2. Декомпозируйте заголовки на независимые части. Включайте только то, что требуется.
3. При изменении нешаблонной функции, которая встроена в N мест, LTCG также будет выполнять переборку этих N мест. Хотя возможно масштаб и поменьше чем с заголовками.

EP>>Чем по твоей классификации отличаются простые алгоритмы от сложных? И почему по-твоему простые на шаблонах получается проще, а сложные — нет?

Всё же не понятно почему простые алгоритмы на шаблонах проще, а сложные нет.

EP>>Ты всё же попробуй переведи пример partition_point на динамический полиморфизм, хотя бы схематично.
CG>Я немного во времени ограничен. Уверен что будет хуже чем с шаблонами, придется нагородить класс итератор с виртуальными ф-ями и использвать его. Получится полная хрень a-la java, но скорее всего работать будет не хуже. Если хочешь в code golf поиграть, могу потом как-нибудь наваять.

Полная реализация не нужна, попробуй только интерфейс. Даже в таком простейшем случае без шаблонов повылазят касты типов — так как тип параметра предиката должен быть совместим с value_type итератора, в "чистом ООП" это будет выражено через Object с последующими кастами. В сложных алгоритмах подобных проблем будет больше.
Другой пример это "динамические" мультметоды, которых как известно нет в C++. И если попадётся подобная задача, то их придётся эмулировать, например через visitor, в то время как "статические" мультиметоды элементарно выражаются через перегрузку.

CG>>Ибо в проекте на 400К LOC он всегда использовался с вектором, за исключением одного случая в не критичном к производительности участке кода.
CG>>Как ты наверное понимаешь, иметь подобные методы в хедерах ради перспективы использовать их с std::list или deque без лишнего копирования — очень сомнительна.
EP>>Не понимаю о каком лишнем копировании идёт речь — тут всегда создаётся временная копия.
CG>Ну стандарт не гарантирует использование copy elision тут, так что может быть и лишняя копия, по крайней мере те люди, которые пишут такой код, либо не знают про copy elision, либо не очень на это надеются.

Тут очень простой случай elision, это не какой-нибудь хитрый RVO — компиляторы умеют это делать очень давно. Да и если не будет elision, то это всего лишь move, а не copy.
Да и вообще я не об этом говорил — ты пишешь о какой-то перспективе использования "deque без лишнего копирования", мол там был шаблон из-за того что для deque он что-то улучшит — что ты имеешь ввиду? Для deque там всегда будет копия.

CG>Угу. Вот только это оч. распространенная практика. Очень часто шаблоны появляются в коде там где они не нужны

По моим наблюдениям не "очень часто", а "редко", и в основном это ошибки/перекосы новичков, которые делают ошибки везде, в том числе и в "чистом ООП".

CG>либо параметр функтор — template<class Fn> void apply(Fn const& f); — который можно заменить std::function или чем-нибудь полиморфным.

В общем случае (без soo, и прочего) std::function это дорогая аллокация которую очень непросто соптимизировать компилятору.

EP>>А если много разных аргументов? Причём которые вычисляются как промежуточные значения какого-то алгоритма? Будешь за каждым в матлаб бегать? Генерировать скриптом?
CG>Можно в рантайме сгенерировать перед стартом, если это очень долго, то можно сгенирировать на этапе компиляции скриптом и вставить в исходинк, можно фалйик сделать и в ресурсы запихать, много вариантов есть.

Это всё никак не сравнится по удобству, наглядности и краткости с шаблонами (либо constexpr функции в forced context)

CG>Считать факториалы шаблонами IMO самый кривой из вышеперечисленных вариантов.

Почему?
Кстати, мне как раз compile-time факториал пригодился для вычисления объёма симплекса в пространствах различной размерности — проще и лаконичней было сделать metaprogramming hello-world факториал, чем проверять что runtime факториал заинлайнится на семи компиляторах в 14 конфигурациях, или чем вставлять таблицу.

CG>Ну это передергивание уже с GPGPU.

Это всего лишь гротескная иллюстрация к твоему радикальному тезису о том, что компилятор будет делать все оптимизации без помощи программиста, главное чтобы у него была информация в compile-time:

CG>В том то и дело что это не частные случаи. Ты можешь использовать шаблон для генерации более быстрого кода тогда, когда на этапе компиляции есть какая-нибудь информация и ты можешь развернуть какой-нибудь цикл или зафиксировать какой-нибудь параметр или избавиться от косвенного вызова через vtable, но то же самое компилятор делает постоянно и без твоей помощи, когда у него эта информация есть.

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

Пожалуйста, вот gcc 4.9.2 -O3:

#include <functional>
using namespace std;

void foo(function<int(int, int)> x)
{
    volatile auto y = x(111, 222) + 555;
    (void)y;
}

void test_foo()
{
    foo([](int x, int y){ return x+y; });
}
/*********************************************/
template<typename F>
void bar(F x)
{
    volatile auto y = x(111, 222) + 555;
    (void)y;
}

void test_bar()
{
    bar([](int x, int y){ return x+y; });
}

CG>gcc это дело девиртуализирует очень запросто, даже в другой единице трансляции.

Ок, смотрим:

_Z8test_foov:
.LFB1245:
    .cfi_startproc
    .cfi_personality 0x3,__gxx_personality_v0
    .cfi_lsda 0x3,.LLSDA1245
    pushq    %rbx
    .cfi_def_cfa_offset 16
    .cfi_offset 3, -16
    movl    $1, %edi
    subq    $48, %rsp
    .cfi_def_cfa_offset 64
    movq    $0, 32(%rsp)
.LEHB0:
    call    _Znwm
.LEHE0:
    leaq    16(%rsp), %rdi
    movl    $222, %edx
    movl    $111, %esi
    movq    %rax, 16(%rsp)
    movq    $_ZNSt17_Function_handlerIFiiiEZ8test_foovEUliiE_E9_M_invokeERKSt9_Any_dataii, 40(%rsp)
    movq    $_ZNSt14_Function_base13_Base_managerIZ8test_foovEUliiE_E10_M_managerERSt9_Any_dataRKS3_St18_Manager_operation, 32(%rsp)
    call    _ZNSt17_Function_handlerIFiiiEZ8test_foovEUliiE_E9_M_invokeERKSt9_Any_dataii
    leaq    16(%rsp), %rsi
    addl    $555, %eax
    movl    $3, %edx
    movl    %eax, 12(%rsp)
    movl    12(%rsp), %eax
    movq    %rsi, %rdi
    call    _ZNSt14_Function_base13_Base_managerIZ8test_foovEUliiE_E10_M_managerERSt9_Any_dataRKS3_St18_Manager_operation
    addq    $48, %rsp
    .cfi_remember_state
    .cfi_def_cfa_offset 16
    popq    %rbx
    .cfi_def_cfa_offset 8
    ret
.L20:
    .cfi_restore_state
    movq    32(%rsp), %rcx
    movq    %rax, %rbx
    testq    %rcx, %rcx
    je    .L19
    leaq    16(%rsp), %rsi
    movl    $3, %edx
    movq    %rsi, %rdi
    call    *%rcx
.L19:
    movq    %rbx, %rdi
.LEHB1:
    call    _Unwind_Resume
.LEHE1:
    .cfi_endproc
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
_Z8test_barv:
.LFB1253:
    .cfi_startproc
    movl    $888, -4(%rsp)
    movl    -4(%rsp), %eax
    ret
    .cfi_endproc

Clang частично оптимизирует и встраивает, но только частично и с шаблоном функции никак не сравнится. Хотя пример элементарный — лямбда stateless, применимо SOO.

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

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

CG>Я там в той теме отписывался, честно попытался воспроизвести кейс с помощью клэнга 3.6 но ничего не получилось, он генерит здоровую ф-ю, которая проверяет нет ли алиасинга и потом если его нет — использует быстрый векторизованый цикл иначе — более сложную и медленную реализацию. В месте вызова оно вообще инлайнилось и векторизировалось. Я не смог заставить clang сгенирировать плохой код с включенными оптимизациями (-O2)

Clang несомненно радует, но к сожалению не везде. Я часто сравниваю его вывод с GCC — в каких-то местах лучше Clang, а в каких-то GCC. То есть грубо говоря нельзя сказать "мы пишем для Clang'а, поэтому получим все прелести компиляторной оптимизации".

	От:	watchmaker
	Дата:	27.11.14 16:18
	Оценка:

От:	lxa	http://aliakseis.livejournal.com
Дата:	27.11.14 16:54
Оценка:

	От:	sunheretic13
	Дата:	21.02.15 19:40
	Оценка:

	От:	nen777w
	Дата:	22.02.15 08:29
	Оценка:

	От:	andyp
	Дата:	22.02.15 11:03
	Оценка:

	От:	Evgeny.Panasyuk
	Дата:	23.02.15 17:23
	Оценка:

	От:	chaotic-good
	Дата:	24.02.15 07:41
	Оценка:

	От:	chaotic-good
	Дата:	24.02.15 07:45
	Оценка:

	От:	chaotic-good
	Дата:	24.02.15 11:07
	Оценка:

	От:	chaotic-good
	Дата:	24.02.15 14:03
	Оценка: