C++ шаблоны для производительности?

Question

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

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

Я действительно заинтригован этим с точки зрения с наименьшей задержкой!

Answer 1

Обычный пример сортировки.

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

В C++ std::sort является шаблоном, и он может принимать объект-функтор в качестве компаратора. Существует другая копия std::sort для каждого другого типа, используемого в качестве компаратора. Предполагая, что вы используете класс функтора с перегруженным operator(), тогда вызов компаратора может легко вставить в эту копию std::sort.

Итак, шаблоны дают вам больше инкрустировки, потому что есть больше копий кода sort, каждый из которых может встроить другой компаратор. Вложение - довольно хорошая оптимизация, а процедуры сортировки выполняют множество сравнений, поэтому вы можете часто измерять std::sort, работая быстрее, чем эквивалент qsort. Стоимость этого - шанс намного большего кода - если ваша программа использует множество разных компараторов, тогда вы получаете много разных копий подпрограммы сортировки, каждая из которых использует другой компаратор, запеченный в нем.

В принципе нет причин, по которым реализация C не может встроить qsort в то место, которое оно вызывается. Затем, если он был вызван с именем функции, оптимизатор мог теоретически заметить, что в точке, которую он использует, указатель функции должен по-прежнему указывать на эту же функцию. Затем он может встроить вызов функции, и результат будет похож на результат с std::sort. Но на практике компиляторы, как правило, не делают первого шага, встраивая qsort. Это потому, что (а) оно велико и (б) оно находится в другой единицы перевода, обычно скомпилированной в какую-то библиотеку, с которой связана ваша программа, и (в) сделать это таким образом, у вас будет встроенная копия qsort для каждого обращения к нему, а не только для каждого другого компаратора. Таким образом, это было бы еще более раздутым, чем C++, если бы реализация не могла найти способ распространять код в случаях, когда qsort вызывается в разных местах с тем же компаратором.

Таким образом, функции общего назначения, такие как qsort в C, имеют некоторые накладные расходы в связи с вызовами через указатели функций или другие косвенные [*]. Шаблоны на C++ - это общий способ хранения исходного кода, но обеспечение его компиляции специальной функцией (или несколькими такими функциями). Надеемся, что код специального назначения будет быстрее.

Стоит отметить, что шаблоны никоим образом не связаны с производительностью. std::sort сам по себе более общий, чем qsort в некотором роде. Например, qsort сортирует только массивы, тогда как std::sort может сортировать все, что обеспечивает итератор с произвольным доступом. Он может, например, сортировать deque, который под крышками представляет собой несколько непересекающихся массивов, выделенных отдельно. Поэтому использование шаблонов не обязательно дает какую-либо выгоду от производительности, это может быть сделано по другим причинам. Просто случается, что шаблоны влияют на производительность.

[*] еще один пример с сортировкой - qsort принимает целочисленный параметр, указывающий, насколько велик каждый элемент массива, и когда он перемещает элементы, он поэтому должен вызывать memcpy или аналогично значению этой переменной. std::sort знает во время компиляции точный тип элементов и, следовательно, точный размер. Он может встроить вызов конструктора копии, который, в свою очередь, может перевести на команды для копирования этого количества байтов. Как и в случае встроенного компаратора, часто бывает возможно скопировать ровно 4 (или 8, или 16 или любые) байты быстрее, чем вы могли бы получить, вызывая процедуру, которая копирует переменное количество байтов, передавая ему значение 4 (или 8 , или 16, или что-то еще). Как и раньше, если вы вызывали qsort с литеральным значением для размера, и этот вызов в qsort был встроен, тогда компилятор мог выполнить ту же оптимизацию в C. Но на практике вы этого не видите.

Answer 2

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

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

template <int N> 
struct Factorial 
{ 
    enum { value = N * Factorial<N - 1>::value }; 
}; 

template <> 
struct Factorial<0> 
{ 
    enum { value = 1 }; 
}; 

// Factorial<4>::value == 24 
// Factorial<0>::value == 1 
void foo() 
{ 
    int x = Factorial<4>::value; // == 24 
    int y = Factorial<0>::value; // == 1 
} 

Вот немного больше читать http://en.wikipedia.org/wiki/Template_metaprogramming

Answer 3

скорее всего они говорят о шаблонном метапрограммировании, который является торговлей между скоростью компиляции для скорости выполнения. Основная идея заключается в том, что вы можете написать программу, которая будет выполняться в компиляторе C++. Например (украденного из Википедии):

template <int N> 
struct Factorial 
{ 
    enum { value = N * Factorial<N - 1>::value }; 
}; 

template <> 
struct Factorial<0> 
{ 
    enum { value = 1 }; 
}; 

// Factorial<4>::value == 24 
// Factorial<0>::value == 1 
void foo() 
{ 
    int x = Factorial<4>::value; // == 24 
    int y = Factorial<0>::value; // == 1 
} 

Таким образом, для вычисления Factorial<4>::value, компилятор должен «раскатать» шаблон и рассчитать Factorial<3>::value и так далее. Все это делается во время компиляции, что, очевидно, увеличивает время для компиляции, но эффективно заменяет его постоянным значением во время выполнения.

Answer 4

«быстрее» зависит от того, к чему вы его сравниваете.

Шаблоны полностью оцениваются компилятором, и поэтому они имеют нулевые служебные данные во время выполнения. Вызов Foo<int>() так же эффективен, как и вызов FooInt().

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

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

Answer 5

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

Таким образом, хотя это обычный алгоритм сортировки будет выглядеть следующим образом:

void qsort (void * base, size_t num, size_t size, 
      int (* comparator) (const void *, const void *)); 

Принимая указатель на функцию, чтобы сделать сравнение и, таким образом, inuring вызов функции на каждом сравнении версия C++ будет выглядеть следующим образом:

template <class RandomAccessIterator, class StrictWeakOrdering> 
void sort(RandomAccessIterator first, RandomAccessIterator last, 
       StrictWeakOrdering comp); 

Таким образом, comp является аргументом шаблона, и если это класс с operator(), то он может встроить реализацию функции в цикл и избежать многих вызовов функций.

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

Answer 6

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

vector<1000> a = foo(), b = bar(), c = baz(), result; 
result = a + b + c; 

Наивный подход будет добавить каждый elemnt из a и b вместе, сохранить результат в виде временного вектора, а затем сделать то же самое с c, и, наконец, скопировать результат в result , Использование шаблона выражение магии, полученный код вместо этого будет эквивалентно следующему:

for(int i = 0; i < 1000; ++i) { 
    result[i] = a[i] + b[i] + c[i]; 
} 

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

Answer 7

шаблоны являются краеугольным камнем развития C++, который ввел в язык третью парадигму.

I.e. C++ родился как объектно-ориентированное расширение до C, в основном обратно совместимое, а затем общее программирование (aka templates) было добавлено «ортогонально» для преодоления (относительной) медленности и многословия ООП, вызванного необходимостью «виртуализации» каждого низкого чтобы разработать код многократного использования (например, контейнеры).

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