Я видел онлайн несколько раз, как уже упоминалось, что С++ может быть быстрее с использованием шаблонов.
Может ли кто-нибудь объяснить, в том числе на низком уровне, почему это точно? Я всегда предполагал, что такая "приятная" функция будет иметь накладные расходы, как и большинство полезных концепций.
Я действительно заинтригован этим с точки зрения с наименьшей задержкой!
Обычный пример сортировки.
В C, qsort берет указатель на функцию сравнения. Вообще говоря, будет одна копия кода qsort, которая не является встроенной. Он совершит вызов через указатель на процедуру сравнения - это, конечно же, также не указано.
В С++ std::sort является шаблоном, и он может принимать объект-функтор в качестве компаратора. Для каждого другого типа, используемого в качестве компаратора, существует другая копия std::sort. Предполагая, что вы используете класс функтора с перегруженным operator(), тогда вызов компаратора может быть легко встроен в эту копию std::sort.
Итак, шаблоны дают вам больше инкрустировки, потому что есть больше копий кода sort, каждый из которых может встроить другой компаратор. Вложение - довольно хорошая оптимизация, а процедуры сортировки выполняют множество сравнений, поэтому вы можете часто измерять std::sort, работая быстрее, чем эквивалент qsort. Стоимость этого - шанс намного большего кода - если ваша программа использует множество разных компараторов, тогда вы получаете много разных копий подпрограммы сортировки, каждая из которых использует другой компаратор, запеченный в нем.
В принципе нет причин, по которым реализация C не может встроить qsort в то место, которое она вызывается. Затем, если он был вызван с именем функции, оптимизатор мог теоретически заметить, что в той точке, в которой он используется, указатель функции должен все же указывать на ту же функцию. Затем он может включить вызов функции, и результат будет похож на результат с std::sort. Но на практике компиляторы, как правило, не делают первого шага, вставляя qsort. Это потому, что (а) оно большое и (б) оно в другой единицы перевода, обычно скомпилированной в какую-то библиотеку, с которой связана ваша программа, и (в) сделать это таким образом, у вас будет встроенная копия qsort для каждого вызова, а не только для каждого другого компаратора. Таким образом, это будет еще более раздутым, чем С++, если только реализация не сможет найти способ распространять код в случаях, когда qsort вызывается в разных местах с тем же компаратором.
Таким образом, функции общего назначения, такие как qsort в C, имеют некоторые накладные расходы из-за вызовов с помощью указателей функций или других косвенных [*]. Шаблоны на С++ - это общий способ хранения исходного кода, но обеспечение его компиляции специальной функцией (или несколькими такими функциями). Надеемся, что код специального назначения будет быстрее.
Стоит отметить, что шаблоны никоим образом не связаны с производительностью. std::sort сам по себе более универсальный, чем qsort. Например, qsort сортирует только массивы, тогда как std::sort может сортировать все, что предоставляет итератор с произвольным доступом. Он может, например, сортировать a deque, который под обложками представляет собой несколько непересекающихся массивов, выделенных отдельно. Поэтому использование шаблонов не обязательно дает какую-либо выгоду от производительности, это может быть сделано по другим причинам. Просто случается, что шаблоны влияют на производительность.
[*] другой пример с сортировкой - qsort принимает целочисленный параметр, указывающий, насколько велик каждый элемент массива, и когда он перемещает элементы, он поэтому должен вызывать memcpy или аналогичный со значением этой переменной. std::sort знает во время компиляции точный тип элементов и, следовательно, точный размер. Он может встроить вызов конструктора копии, который, в свою очередь, может перевести на команды для копирования этого количества байтов. Как и в случае встроенного компаратора, часто можно скопировать ровно 4 (или 8, или 16 или любые) байты быстрее, чем вы получили, вызывая процедуру, которая копирует переменное количество байтов, передавая ему значение 4 (или 8, или 16, или что-то еще). Как и раньше, если вы вызвали qsort с литеральным значением для размера, и этот вызов в qsort был встроен, тогда компилятор мог выполнить ту же самую оптимизацию в C. Но на практике вы этого не видите.
"быстрее" зависит от того, с чем вы сравниваете.
Шаблоны полностью оцениваются компилятором, и поэтому они имеют нулевые служебные данные во время выполнения. Вызов Foo<int>() точно так же эффективен, как вызов FooInt().
Таким образом, по сравнению с подходами, которые полагаются на большую работу, выполняемую во время выполнения, например, путем вызова виртуальных функций, шаблоны действительно могут быть быстрее. По сравнению с рукописным кодом, написанным именно для этого сценария, существует нулевая разница.
Итак, приятная вещь о шаблонах - это не то, что они "быстрее", чем то, что вы могли бы сделать в противном случае, но что они "так же быстро", как рукописный код, а также являются универсальными и многоразовыми.
Другим замечательным примером использования шаблонов для повышения производительности во время выполнения является библиотека шаблоны выражений, используя логику компиляции, чтобы преобразовать арифметические выражения с большими векторами и матрицами в эквивалентные, которые много проще компилировать в эффективный машинный код. Например, с учетом следующего псевдокода:
vector<1000> a = foo(), b = bar(), c = baz(), result;
result = a + b + c;
Наивный подход добавит каждый элемент a и b вместе, сохранит результат во временном векторе, затем сделает то же самое с c и, наконец, скопирует результат в result. Используя магию шаблона выражения, полученный в результате код будет эквивалентен этому:
for(int i = 0; i < 1000; ++i) {
result[i] = a[i] + b[i] + c[i];
}
Это намного быстрее, что позволяет лучше использовать локальность кэш-памяти и избегать ненужных временных рядов. Он также избегает проблем с псевдонимом, когда компилятор не может доказать, что два указателя указывают на различные области памяти, заставляя его создавать неоптимальный код. Шаблоны экспрессии теперь широко используются в высокопроизводительных численных моделях, а также в других целях, не связанных с производительностью, таких как библиотека Boost.Spirit.
Я не уверен, что вы говорите о метапрограммировании шаблонов С++: выполняйте некоторые вычисления во время компиляции, чтобы получить результат во время выполнения почти мгновенно. Если да, вот пример.
Используя метапрограммирование шаблонов и специализированную специализацию шаблона для обеспечения конечного условия рекурсии, факториалы, используемые в программе, игнорируя любые факториалы, которые не используются, могут быть рассчитаны во время компиляции этим кодом
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
Скорее всего, они говорят о метапрограммировании шаблонов, что является сделкой между скоростью компиляции для скорости выполнения. Основная идея заключается в том, что вы можете написать программу, которая будет выполняться в компиляторе С++. Например (украденный из википедии):
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 и так далее. Все это делается во время компиляции, что, очевидно, увеличивает время компиляции, но эффективно заменяет его постоянным значением во время выполнения.
являются краеугольным камнем развития С++, который ввел в язык третья парадигма.
т.е. С++ родился как объектно-ориентированное расширение до C, в основном обратно совместимое, а затем универсальное программирование (aka templates) было добавлено "ортогонально" для преодоления (относительной) медлительности и многословия ООП, вызванного необходимостью "виртуализации" каждого низкого чтобы создать код многократного использования (например, контейнеры).
Контейнеры, действительно, показывают, что легче понять ускорение, полученное с помощью дженериков: при доступе к элементу это значение доступно непосредственно компилятору.
Шаблоны причин считаются более быстрыми, так как они видны компилятору.
Итак, в то время как простой алгоритм сортировки C будет выглядеть следующим образом:
void qsort ( void * base, size_t num, size_t size,
int ( * comparator ) ( const void *, const void * ) );
Принимая указатель на функции для сравнения и тем самым вызывая вызов функции при каждом сравнении, версия С++ будет выглядеть так:
template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
Таким образом, comp является аргументом шаблона, и если он определяет класс с operator(), то компилятор может встроить реализацию функции в цикл и избежать многих вызовов функций.
Я не думаю, что точка, которая была сделана, заключается в том, что мета-программирование шаблона выполняется быстрее, поскольку это редко используется в большинстве баз кода.