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

CG>Погугли constant folding и constant propagation. Функция возводящая в степень будет оптимизирована компилятором. Что-то такое:
CG>

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

CG>компилятор соптимизирует в две инструкции mul. Цикл будет развернут, так как значение y известно на этапе компиляции (без всяких шаблонов).
Ну я же про рекурсивный алгоритм, а не алгоритм с циклом (у тебя описка и что-то типа x^(2^y), если не путаю). Конкретно студийный компилятор когда я пробовал пример со степеньюЮ пару лет назад, не умел сворачивать рекурсию сам, хотя конечно ничего не мешает компилятору частично вычислять что угодно по константным данным. Вообщем если не нравится пример со степенью, то можно взять любой другой рекурсивный алгоритм. Функция Аккермана? Еще можно умножать матрицы на константные разряженные матрицы?

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

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

CG>>Погугли constant folding и constant propagation. Функция возводящая в степень будет оптимизирована компилятором. Что-то такое:
CG>>

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

CG>>компилятор соптимизирует в две инструкции mul. Цикл будет развернут, так как значение y известно на этапе компиляции (без всяких шаблонов).
Z>Ну я же про рекурсивный алгоритм, а не алгоритм с циклом (у тебя описка и что-то типа x^(2^y), если не путаю). Конкретно студийный компилятор когда я пробовал пример со степеньюЮ пару лет назад, не умел сворачивать рекурсию сам, хотя конечно ничего не мешает компилятору частично вычислять что угодно по константным данным. Вообщем если не нравится пример со степенью, то можно взять любой другой рекурсивный алгоритм. Функция Аккермана? Еще можно умножать матрицы на константные разряженные матрицы?

Кстати если возводиться в степень будут не int-ы, а какие-нибудь сложные объекты и компилятор не сможет пользоваться мат-преобразованиями, то возведение в 17-ю степень останется 17-ю умножениями, против 5-ти в рекурсивном алгоритме.

EP>Тем не менее это дополнительный барьер.
Отрицать не буду.

EP>При создании applications естественным образом получаются новые библиотеки. Причём процент того что называется "application code" мал, да и в основном это клей соединяющий библиотеки (свои и third-party).
Тут бывают разные методики, если code reuse не предполагается, то нет смысла выносить все в библиотеки. Это overkill и лишняя трата времени. Избавиться от такого кода потом будет сложнее.

EP>1. Precompiled headers.
Ага, особенно с GCC и для своих собственных заголовочных файлов. Это не панацея и хорошо работает только со студией. С gcc можно запросто получить более долгий билд, с чем я сталкивался не однократно.

EP>2. Декомпозируйте заголовки на независимые части. Включайте только то, что требуется.
Я уж лучше последую совету дедушки Лейкоса и не буду писать код в хедерах почти никогда.

EP>3. При изменении нешаблонной функции, которая встроена в N мест, LTCG также будет выполнять переборку этих N мест. Хотя возможно масштаб и поменьше чем с заголовками.
Несравнимо меньше, я бы сказал

EP>>>Чем по твоей классификации отличаются простые алгоритмы от сложных? И почему по-твоему простые на шаблонах получается проще, а сложные — нет?
EP>Всё же не понятно почему простые алгоритмы на шаблонах проще, а сложные нет.
Ну скажем если основной код находится в срр, а шаблонный код просто склеивает то что живет в срр и делает более удобный интерфейс. Ну или всякие алгоритмы a-la STL, их довольно бессмысленно выносить в срр, ибо все равно они никогда не меняются и должны быть максимально обобщенными.

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

Если нужна полностью обобщенная реализация то да, будут касты. Если же обобщенная реализация не нужна (а это часто бывает в application specific коде) — то все становится проще.

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

EP>В общем случае (без soo, и прочего) std::function это дорогая аллокация которую очень непросто соптимизировать компилятору.
Не обязательно использовать std::funcition, там действительно внутри динамический объект сидит и поэтому компилятору сложно, если вообще возможно, избавиться от вирт. вызова. Но вот такой пример отлично оптимизируется (девиртуализация + векторизация в обоих случаях). Конечно это java style и не очень выразительно, но зато позволяет обойтись без кода в хедерах.

Z>Ну я же про рекурсивный алгоритм, а не алгоритм с циклом (у тебя описка и что-то типа x^(2^y), если не путаю). Конкретно студийный компилятор когда я пробовал пример со степеньюЮ пару лет назад, не умел сворачивать рекурсию сам, хотя конечно ничего не мешает компилятору частично вычислять что угодно по константным данным. Вообщем если не нравится пример со степенью, то можно взять любой другой рекурсивный алгоритм. Функция Аккермана? Еще можно умножать матрицы на константные разряженные матрицы?

^ это XOR, но у меня там ошибка есть, должно быть как-то так:

int pow(int val, int y) {
    int res = 1;
    for (int i = 0; i < y; i++) {
        res *= val;
    }
    return res;
}

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

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

Необязательно делать реализацию супер обобщённой, но code reuse возможен даже внутри самого проекта.
Например, неужели никогда не приходилось делать свою структуры данных, алгоритмы и т.п.? Им место как раз в обособленной библиотеке (пусть не сильно обобщённой, но всё же обособленной).
В конце концов отдельные обособленные части проще тестировать.

CG>Избавиться от такого кода потом будет сложнее.

А зачем от него избавляться?

EP>>1. Precompiled headers.
CG>Ага, особенно с GCC и для своих собственных заголовочных файлов. Это не панацея и хорошо работает только со студией. С gcc можно запросто получить более долгий билд, с чем я сталкивался не однократно.

А какая у GCC проблема с PCH?

EP>>В общем случае (без soo, и прочего) std::function это дорогая аллокация которую очень непросто соптимизировать компилятору.
CG>Не обязательно использовать std::funcition, там действительно внутри динамический объект сидит и поэтому компилятору сложно, если вообще возможно, избавиться от вирт. вызова.

AFAIK, для небольших объектов в популярных реализациях делается small object optimization — объект не аллоцируется в куче, а делается placement new внутри самой std::function.
Тем не менее — это пример того, что у компилятора есть вся необходимая информация, причём случай не такой уж и тяжёлый — а оптимизацию он сделать не может.

CG>Но вот такой пример отлично оптимизируется (девиртуализация + векторизация в обоих случаях).

Да, потому что это простой пример.

CG>Конечно это java style и не очень выразительно, но зато позволяет обойтись без кода в хедерах.

Для таких случаев можно сделать не владеющий аналог function (либо аналог/дополнение к Boost.TypeErasure в более общем случае) — то есть использование будет очень близко по форме (думаю можно сделать даже одинаковым) к std::function, с тем отличием что время жизни исходного функционального объекта должен обеспечивать пользователь. Думаю оптимизировать компилятору это будет намного проще.
Если руки дойдут, то набросаю пример.

EP>Необязательно делать реализацию супер обобщённой, но code reuse возможен даже внутри самого проекта.
EP>Например, неужели никогда не приходилось делать свою структуры данных, алгоритмы и т.п.? Им место как раз в обособленной библиотеке (пусть не сильно обобщённой, но всё же обособленной).
EP>В конце концов отдельные обособленные части проще тестировать.

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

CG>>Избавиться от такого кода потом будет сложнее.
EP>А зачем от него избавляться?

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

EP>А какая у GCC проблема с PCH?
Он не очень то от них выигрывает. Я как-то раз на SO спрашивал — http://stackoverflow.com/questions/13309228/gcc-build-time-doesnt-benefit-much-from-precompiled-headers Часть проекта размером в 150К строк собиралась примерно 15 минут после всевозможных оптимизаций билда (оптимизации физической структуры, зависимостей и тд), в том числе и после включения PCH. Вот от PCH толку было очень мало, 5-10%.

CG>>Конечно это java style и не очень выразительно, но зато позволяет обойтись без кода в хедерах.
EP>Для таких случаев можно сделать не владеющий аналог function (либо аналог/дополнение к Boost.TypeErasure в более общем случае) — то есть использование будет очень близко по форме (думаю можно сделать даже одинаковым) к std::function, с тем отличием что время жизни исходного функционального объекта должен обеспечивать пользователь. Думаю оптимизировать компилятору это будет намного проще.
EP>Если руки дойдут, то набросаю пример.

Вот пример:
LIVE DEMO

template<typename F, typename Result, typename ...Params>
Result concrete_wrapper(const void *f, Params... params)
{
    return (*static_cast<const F*>(f))(params...);
}

template<typename Signature>
class function_non_owning;

template<typename Result, typename ...Params>
class function_non_owning<Result(Params...)>
{
    const void *f = nullptr;
    Result (*wrapper)(const void *, Params...) = nullptr;
public:
    function_non_owning() = default;

    template<typename F>
    function_non_owning(const F &f)
        : f(&f), wrapper(&concrete_wrapper<F, Result, Params...>)
    {}

    Result operator()(Params... params) const
    {
        return wrapper(f, params...);
    }
};

// Example of usage:

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

void test_baz()
{
    baz([](int x, int y){ return x+y; });
}

Результат:

_Z8test_bazv:
.LFB4:
    .cfi_startproc
    movl    $888, -4(%rsp)
    movl    -4(%rsp), %eax
    ret
    .cfi_endproc

И GCC и Clang оптимизируют этот вариант до кода идентичного шаблонной версии.

EP>>Для таких случаев можно сделать не владеющий аналог function (либо аналог/дополнение к Boost.TypeErasure в более общем случае) — то есть использование будет очень близко по форме (думаю можно сделать даже одинаковым) к std::function, с тем отличием что время жизни исходного функционального объекта должен обеспечивать пользователь. Думаю оптимизировать компилятору это будет намного проще.
EP>>Если руки дойдут, то набросаю пример.

EP>Вот пример:
EP>LIVE DEMO
EP>

EP>...
EP>

Результат:
EP>

EP>_Z8test_bazv:
EP>.LFB4:
EP>    .cfi_startproc
EP>    movl    $888, -4(%rsp)
EP>    movl    -4(%rsp), %eax
EP>    ret
EP>    .cfi_endproc
EP>

EP>И GCC и Clang оптимизируют этот вариант до кода идентичного шаблонной версии.

Пожалуй это можно признать примером действительно практичной оптимизации с использованием шаблонов, исключением из правила

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

CG>Пожалуй это можно признать примером действительно практичной оптимизации с использованием шаблонов, исключением из правила

Другие примеры ты почему-то проигнорировал — например

Автор: Evgeny.Panasyuk
Дата: 24.02.15

. Это же огромный класс задач в которых sizeof создаваемых внутри функции объектов зависит от шаблонных параметров (не важно каких — type или non-type template parameters).
Если же отказываться от шаблонов — то в общем случае вылезут лишние динамические аллокации (так как объект создавать надо, а его размер неизвестен в compile-time), с которыми у оптимизаторов всё плохо. GCC не может даже оптимизировать простейший случай:

int main()
{
    delete [] new char[0x555];
}

0000000000400510 <main>:
  400510:    48 83 ec 08              sub    $0x8,%rsp
  400514:    bf 55 05 00 00           mov    $0x555,%edi
  400519:    e8 c2 ff ff ff           callq  4004e0 <_Znam@plt>
  40051e:    48 89 c7                 mov    %rax,%rdi
  400521:    e8 da ff ff ff           callq  400500 <_ZdaPv@plt>
  400526:    31 c0                    xor    %eax,%eax
  400528:    48 83 c4 08              add    $0x8,%rsp
  40052c:    c3                       retq

EP>Другие примеры ты почему-то проигнорировал — например

Автор: Evgeny.Panasyuk
Дата: 24.02.15

. Это же огромный класс задач в которых sizeof создаваемых внутри функции объектов зависит от шаблонных параметров (не важно каких — type или non-type template parameters).

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