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

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

template<int X>
void func(...) {
   // делаем что-нибудь такое, что может
   // работать быстрее, если Х известно во 
   // время компиляции
}

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

А оно уже известно — int.

QC>А оно уже известно — int.

Значение целочисленного типа а не сам тип.

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

CG>Я хочу придумать задачу, в которой шаблонный параметр целочисленного типа использовался бы для оптимизации. Что-то вроде:
CG> // делаем что-нибудь такое, что может работать быстрее, если Х известно во время компиляции
И в чем сложность? Казалось бы сразу можно придумать много примеров с арифметикой, где это позволяет упростить выражение. Вот например проверка на кратность аргумента функции: template <int d> bool isDivisible(int n) { return n % d == 0;} Или арифметика как пример для тебя недостаточно хороша?

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

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

CG>

CG>template<int X>
CG>void func(...) {
CG>   // делаем что-нибудь такое, что может
CG>   // работать быстрее, если Х известно во 
CG>   // время компиляции
CG>}
CG>

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

jazzer (Skype: enerjazzer) Ночная тема для RSDN

You will always get what you always got
  If you always do  what you always did

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

QC>>А оно уже известно — int.

CG>Значение целочисленного типа а не сам тип.

Значение тоже известно — это же параметр шаблона. Ваш кэп.

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

template<unsigned Mask, typename UnsignedT>
UnsignedT SetBitsByMask(const UnsignedT var, const UnsignedT shiftedValue)
{
    return (~Mask & var) | (Mask & shiftedValue);
}

маска обычно известна в компилтайме. var — какая-нибудь переменная, в которй надо установить определенные биты, shiftedValue — значение, которое надо установить в биты, сдвинутое предварительно, что бы совместить требуемые биты.

CG>template<int X>
CG>void func(...) {
CG>   // делаем что-нибудь такое, что может
CG>   // работать быстрее, если Х известно во 
CG>   // время компиляции
CG>}
CG>

template<int X>
int func() {
    return X;
}

Интересно, заинлайнит?

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

J>Возведение шаблонного параметра в степень

Про степень. Вот почему это не работает:

#include <iostream>
#include <string>

template <typename T>

 T  func(T val, T deg){
  T sh;
  T res=1;
  T num=0;
  T degree=deg;
   __asm__ __volatile__ ( 
    "pushq %%rbx \t\n"
    "bsrq %1, %%rbx \t\n"
    "movq %%rbx, %0 \t\n"
    "popq %%rbx \t\n"
    : "=m" (num)
    : "m" (degree)
    : 
    );

  T tmp=1<<num;
   while(tmp>0)
    {
     sh=degree&tmp;
     tmp>>=1;
     res=(sh>0) ? res*res*val : res*res;
    };
 return res;
 };

int main(int c, char** s){
  unsigned long a=std::stoi(s[1]), b=std::stoi(s[2]);
  
  std::cout<<"Res=" <<func(a,b)<<"\n";
 };
  
............................

[g@localhost ~]$ ./x 2 63
Res=0

Если добавить так

template <typename T>

 T  func(T val, T deg){
  T sh;
  T res=1;
  T num=0;
  T degree=deg;
   __asm__ __volatile__ ( 
    "pushq %%rbx \t\n"
    "bsrq %1, %%rbx \t\n"
    "movq %%rbx, %0 \t\n"
    "popq %%rbx \t\n"
    : "=m" (num)
    : "m" (degree)
    : 
    );

  T tmp=1<<num;
   while(tmp>0)
    {
     sh=degree&tmp;
     tmp>>=1;
     res=(sh>0) ? res*res*val : res*res;
    };
  std::cout<<"Yob\n"; /* добавка */
 return res;
 };

то

[g@localhost ~]$ ./x 2 63
Yob
Res=9223372036854775808

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

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

я недавно спрашивал тут, как раз это в результате и предложили.

W>И в чем сложность? Казалось бы сразу можно придумать много примеров с арифметикой, где это позволяет упростить выражение. Вот например проверка на кратность аргумента функции: template <int d> bool isDivisible(int n) { return n % d == 0;} Или арифметика как пример для тебя недостаточно хороша?

Хороший пример, да. Сложность в том, что я сам это не придумал, вот и все

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

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

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

CG>template<int X>
CG>void func(...) {
CG>   // делаем что-нибудь такое, что может
CG>   // работать быстрее, если Х известно во 
CG>   // время компиляции
CG>}
CG>

Вообще, самое простое — это if:

template<int X>
void func(...) {
   if (X>500) ...
   else if (X>50) ...
   else if (X>5) ...
   else if (X>0) ...
   else ...
}

Поскольку X — константа времени компиляции, компилятор просто выкинет из результирующей функции все условия, которые, как он уже знает, точно не подходят.

jazzer (Skype: enerjazzer) Ночная тема для RSDN

You will always get what you always got
  If you always do  what you always did

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

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

В каждой шутке есть доля шутки.

J>Вообще, самое простое — это if:
J>

J>template<int X>
J>void func(...) {
J>   if (X>500) ...
J>   else if (X>50) ...
J>   else if (X>5) ...
J>   else if (X>0) ...
J>   else ...
J>}
J>

J>Поскольку X — константа времени компиляции, компилятор просто выкинет из результирующей функции все условия, которые, как он уже знает, точно не подходят.

Если сделать X простым параметром и передать в функцию константу то компилятор сделает то же самое (constant folding/propagation).

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

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

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

lxa>В каждой шутке есть доля шутки.

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

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

J>>Вообще, самое простое — это if:
J>>Поскольку X — константа времени компиляции, компилятор просто выкинет из результирующей функции все условия, которые, как он уже знает, точно не подходят.

CG>Если сделать X простым параметром и передать в функцию константу то компилятор сделает то же самое (constant folding/propagation).

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

jazzer (Skype: enerjazzer) Ночная тема для RSDN

You will always get what you always got
  If you always do  what you always did

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

CG>>Если сделать X простым параметром и передать в функцию константу то компилятор сделает то же самое (constant folding/propagation).

J>Ну да, но только если заинлайнится.
J>А в случае шаблона это произойдет в любом случае.
Даже это не всегда бывает. Функция может быть встроена, а константы у компилятора не схлопнутся.
Вот небольшой пример по вычислению обратного числа в полукольце вычетов. Все три компилятора (gcc, clang, icc) разных версий (там в интерфейсе можно выбирать) успешно встраивают функцию, но вычислить её ни у одного не получается. А вот в варианте с шаблонами у всех всё схлопывается до константы.

J>>Ну да, но только если заинлайнится.
J>>А в случае шаблона это произойдет в любом случае.
W>Даже это не всегда бывает. Функция может быть встроена, а константы у компилятора не схлопнутся.
W>Вот небольшой пример по вычислению обратного числа в полукольце вычетов. Все три компилятора (gcc, clang, icc) разных версий (там в интерфейсе можно выбирать) успешно встраивают значение, но вычислить его ни у одного не получается. А вот в варианте с шаблонами у всех всё схлопывается до константы.

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

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

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

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

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

jazzer (Skype: enerjazzer) Ночная тема для RSDN

You will always get what you always got
  If you always do  what you always did

	От:	chaotic-good
	Дата:	26.11.14 09:29
	Оценка:

	От:	Qt-Coder
	Дата:	26.11.14 09:35
	Оценка:

	От:	chaotic-good
	Дата:	26.11.14 09:43
	Оценка:

	От:	watchmaker
	Дата:	26.11.14 09:46
	Оценка:

От:	jazzer	Skype: enerjazzer
Дата:	26.11.14 09:47
Оценка:

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