Оптимизация составного std::functions

Можно ли оптимизировать серию «склеенных» std::function и/или есть ли какая-либо реализация, которая пытается это сделать?

То, что я имею в виду, проще всего выразить математически: скажем, я хочу создать std::function, являющееся функцией функции:

f(x,y,z) = x^2 * y^3 * z^4
g(x,y,z) = f(x,y,z) / (x*y^2)

Есть ли способ для разработчика STL/компилятора оптимизировать части арифметики, вызывающей объект функции g, созданный из объекта функции f?

Это было бы своего рода символическим упрощением функций, но поскольку это std::function, его нужно было бы определить на машинном уровне.

Из-за того, что это оптимизация, которая требует времени и, вероятно, не бесплатна (в тактовых циклах и/или памяти), она, вероятно, не разрешена стандартом? Он очень близок к языку, который обычно запускается через виртуальную машину. (Я думаю, что LLVM больше, чем Java, с оптимизацией времени выполнения).

РЕДАКТИРОВАТЬ: Чтобы сделать обсуждение «более полезным», вот короткий фрагмент кода (я понимаю, что лямбда не является std::function, но лямбда может быть сохранена в std::function, поэтому, предполагая, что auto ниже означает, что std::function<T> с соответствующим T будет выражать именно то, что я имел в виду выше):

auto f = [](const double x, const double y, const double z){ return x*x*y*y*y*z*z*z*z; };
auto g = [](const double c, const double y, const double z){ return f(x,y,z)/(x*y*y); };

«Тривиальный» компилятор сделал бы g эквивалентным

double g(const double x, const double y, const double z){ return x*x*y*y*y*z*z*z*z/(x*y*y); }

В то время как оптимизированный std::function мог бы это сделать (математически и во всех других смыслах правильно!):

double g( const double x, const double y, const double z){ return x*y*z*z*z*z; }

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

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


person rubenvb    schedule 21.07.2011    source источник
comment
Оптимизация разрешена стандартом. В стандарте ничего не говорится о том, что вы не должны оптимизировать. (Ну, есть некоторые предостережения в отношении volatile, в частности, но не для кода, о котором вы спрашиваете.) Возможно, это больше вопрос о том, может ли компилятор безопасно выполнить оптимизацию, и стоит ли разработчикам компилятора тратить время на это. искать оптимизацию.   -  person Jonathan Leffler    schedule 21.07.2011
comment
Я не думаю, что это запрещено стандартом, потому что это требует времени. Но это, вероятно, запрещено, потому что это меняет семантику. Для x == 0 или y == 0 неоптимизированная версия дает NaN, оптимизированная просто возвращает 0.   -  person Henrik    schedule 21.07.2011
comment
Я предполагаю, что такая оптимизация возможна с функциями constexpr.   -  person Richard    schedule 21.07.2011
comment
@ Хенрик, так ты говоришь, что g (x, y, z) = 0 с x = 0 не является решением в неоптимизированной версии? :)   -  person duedl0r    schedule 21.07.2011
comment
@duedl0r: да, если x, y и z имеют тип float или double, я ожидаю, что g(0,0,0) вычислит 0/0 и, таким образом, вернет NaN.   -  person Henrik    schedule 21.07.2011
comment
Ну, чисто математически говоря, g(0,y,z) = 0, потому что вы больше не делите на 0 (!). Это было своего рода моей точкой зрения с этими оптимизациями, своего рода математическим упрощением, если хотите...   -  person rubenvb    schedule 21.07.2011
comment
Я не понимаю, какое это имеет отношение к std::function (и c++0x). Вам нужно показать код, чтобы сделать обсуждение полезным.   -  person Gene Bushuyev    schedule 21.07.2011
comment
@rubenvb: Педантично говоря, вам разрешено отменять x/x = 1 только тогда, когда x не равно нулю. Что верно, так это то, что функция x -> x/x имеет устранимую сингулярность в 0 с пределом 1.   -  person Kerrek SB    schedule 21.07.2011
comment
@Kerrek SB: на самом деле педантично говоря, вы можете написать 1/x только в том случае, если x не равно 0, но x/x так же хорош, как и все, даже когда x = 0, потому что предел x/x для x-›0 равен все еще четко определена, и функция непрерывна и гладка, как вы можете найти...   -  person rubenvb    schedule 22.07.2011
comment
Я предлагаю вам удалить ссылку на std::function из вашего вопроса не только потому, что лямбда не std::function, но и потому, что сложности для компилятора, использующего std::function, делают ответ определенным НЕТ. И даже использование лямбда-выражений является ненужным усложнением. Самый простой способ — написать две встроенные функции.   -  person Gene Bushuyev    schedule 22.07.2011
comment
@Gene: хотя пример кода содержит лямбда, использование std::function для передачи лямбда почти неизбежно, под чем я подразумеваю, что алгебраическая система не будет использовать одно без другого и должна иметь возможность оптимизировать оба. Нигде в стандарте не говорится, что лямбда не может быть std::function, просто в некоторых случаях это сложно (захват переменных), но никогда не запрещается. Я бы даже сказал, воодушевлен, видя, что лямбда должна быть преобразована в std::function.   -  person rubenvb    schedule 22.07.2011
comment
@rubenvb: вопрос на самом деле не имеет ничего общего с лямбда-выражениями или std::function. Лямбды реализованы как замыкания, это стандарт. И хотя лямбда-выражения могут быть назначены std::function, это не их обычное использование.   -  person Gene Bushuyev    schedule 22.07.2011
comment
@rubenvb Тот факт, что std::function будет неизбежен, является полным отвлекающим маневром: использование функции main также неизбежно, но последнее место, где следует искать оптимизацию в вашем сценарии, находится в main. Алгебраическая система определенно не хотела бы использовать std::function, поскольку стирание типов избавляет от важной информации (как следует из названия, типов); client-code будет использовать его, но не library-code.   -  person Luc Danton    schedule 22.07.2011


Ответы (2)


Вот почему вы оставляете оптимизацию компилятору. Они алгебраически эквивалентны, но не эквивалентны из-за неточности FP. Ваши две версии g дадут немного разные ответы, что может быть очень важно, если вызываться во внутреннем цикле, не говоря уже о разнице в поведении, если x, y, z равны 0.

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

person Puppy    schedule 21.07.2011

Компилятору разрешено оптимизировать в определенных разрешенных случаях или если оптимизированный код ведет себя «как если бы» это был неоптимизированный код.

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

person Mark B    schedule 21.07.2011
comment
Обратите внимание, что, по крайней мере, в C, если происходит неопределенное поведение, такое как переполнение или деление на ноль, тогда программе разрешено делать что угодно — и, как следствие, оптимизации могут игнорировать такие случаи, такие как как (не то, чтобы любой компилятор обязательно делал это, и это не обязательно оптимизация), оптимизирующий x*x + x*y + y*y до (x+y)*(x+y). - person Antal Spector-Zabusky; 21.07.2011
comment
поведение undefined не является побочным эффектом для предотвращения оптимизации, это лицензия для компилятора делать (почти) что угодно :-) - person Gene Bushuyev; 21.07.2011
comment
@Antal: За исключением того, что эти два не эквивалентны ;-) ((x+y)*(x+y) эквивалентно x*x + 2*x*y + y*y). Кроме того, только фактическое переполнение приводит к неопределенному поведению, а не потенциальное переполнение: если компилятор выполняет какое-то арифметическое преобразование, он должен гарантировать, что для любых входных данных в исходное выражение дает правильные результаты, преобразованное выражение дает такие же правильные результаты. - person James McNellis; 22.07.2011