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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 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]; } 

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

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

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

 template  struct Factorial { enum { value = N * Factorial::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

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

 template  struct Factorial { enum { value = N * Factorial::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 ++, который ввел в язык третью парадигму.

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

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

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

Поэтому, когда простой алгоритм сортировки по C будет выглядеть так:

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

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

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

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

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

  • Обходное решение для вывода аргумента шаблона в невыводимом контексте
  • HTML5: Почему мой атрибут oninvalid позволяет шаблону выйти из строя?
  • перегрузка оператора друга << для шаблона classа
  • недопустимое использование неполного типа
  • Препроцессор C ++: избегать повторения кода списка переменных-членов
  • Razor рассматривает как шаблоны электронной почты
  • Проблема GCC: использование члена базового classа, который зависит от аргумента шаблона
  • Расшифровка сообщений об ошибках шаблона C ++
  • Каков правильный способ представления classов шаблонов с помощью UML?
  • Что именно «нарушено» с помощью двухфазного экземпляра шаблона Microsoft Visual C ++?
  • Делают ли c ++ шаблоны медленными?
  • Interesting Posts

    Почему статическое поле должно быть доступно статическим способом?

    как экземпляр List ?

    Ошибка компилятора C ++ C2280 «попытка ссылки на удаленную функцию» в Visual Studio 2013 и 2015

    Удалить заголовок сервера IIS7

    Отключение обновлений окон для Windows 10

    Разница между e.target и e.currentTarget

    Как я могу настроить трафик для маршрутизации Windows VPN (по сети назначения)?

    Настройка кнопок быстрого доступа в левой части File-> Open dialog в большинстве программ Windows

    Apache Tomcat не отображается в среде Runtime сервера Eclipse

    Как программно запускать разрешение на запуск программного обеспечения MIUI Security?

    Iphone: как отобразить изображения в каталоге документов в режиме просмотра изображений?

    «Sdclt.exe / config» завершается с неуказанной ошибкой

    Отключите громкость сразу после ее вставки, если ее имя «XYZ»

    Android Geocoder getFromLocationName всегда возвращает null

    Заменить вектор, используя вектор индексов

    Давайте будем гением компьютера.