AI-приложения в C ++: Насколько дороги виртуальные функции? Каковы возможные оптимизации?

Question

В приложении AI я пишу на C ++,

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

Есть ли в такой ситуации какие-либо методы оптимизации? Хотя сейчас я не буду заботиться об оптимизации приложения, одним из аспектов выбора C ++ вместо Java для проекта было предоставление большего рычага для оптимизации и возможность использования не объектно-ориентированных методов (шаблоны, процедуры, перегрузка).

В частности, какие методы оптимизации связаны с виртуальными функциями? Виртуальные функции реализуются через виртуальные таблицы в памяти. Есть ли какой-нибудь способ предварительно извлечь эти виртуальные таблицы в кэш L2 (стоимость выборки из памяти / кэш L2 увеличивается)?

Помимо этого, есть ли хорошие ссылки на методы локальности данных в C ++? Эти методы позволят сократить время ожидания выборки данных в кэш L2, необходимое для вычислений.

Обновление : Также см. Следующие связанные форумы: Штраф за производительность интерфейса , Несколько уровней базовых классов

Answer 1

Виртуальные функции очень эффективны. Предполагая 32-битные указатели, объем памяти составляет примерно:

classptr -> [vtable:4][classdata:x]
vtable -> [first:4][second:4][third:4][fourth:4][...]
first -> [code:x]
second -> [code:x]
...

classptr указывает на память, которая обычно находится в куче, иногда в стеке, и начинается с четырехбайтового указателя на виртуальную таблицу для этого класса. Но важно помнить, что сама таблица не выделяет память. Это статический ресурс, и все объекты одного и того же типа класса будут указывать на одно и то же место в памяти для своего массива vtable. Вызов разных экземпляров не приведет к извлечению разных областей памяти в кэш L2.

Этот пример из msdn показывает виртуальную таблицу для класса A с виртуальными func1, func2 и func3. Ничего больше, чем 12 байтов. Существует большая вероятность того, что таблицы с различными классами также будут физически смежными в скомпилированной библиотеке (вы должны убедиться, что это вас особенно беспокоит), что может микроскопически повысить эффективность кэша.

CONST SEGMENT
??_7A@@6B@
   DD  FLAT:?func1@A@@UAEXXZ
   DD  FLAT:?func2@A@@UAEXXZ
   DD  FLAT:?func3@A@@UAEXXZ
CONST ENDS

Другая проблема производительности - накладные расходы при вызове через функцию vtable. Это тоже очень эффективно. Почти идентичен вызову не виртуальной функции. Снова из примера из MSDN :

; A* pa;
; pa->func3();
mov eax, DWORD PTR _pa$[ebp]
mov edx, DWORD PTR [eax]
mov ecx, DWORD PTR _pa$[ebp]
call  DWORD PTR [edx+8]

В этом примере ebp, базовый указатель кадра стека, имеет переменную A* pa со смещением нуля. Регистр eax загружается со значением в location [ebp], поэтому он имеет A *, а edx загружается со значением в location [eax], поэтому он имеет класс A vtable. Затем ecx загружается с помощью [ebp], поскольку ecx представляет «this», теперь он содержит A *, и, наконец, выполняется вызов значения в местоположении [edx + 8], которое является третьим адресом функции в vtable. *

Если бы этот вызов функции не был виртуальным, mov eax и mov edx не были бы необходимы, но разница в производительности была бы неизмеримо мала.

Answer 2

Раздел 5.3.3 проекта технического отчета о производительности C ++ полностью посвящен накладным расходам виртуальных функций.

Answer 3

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

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

Answer 4

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

Мне неизвестен какой-либо компилятор / среда выполнения C ++, использующая эту технику.

Answer 5

Вы действительно профилировали и нашли, где и что нуждается в оптимизации?

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

Answer 6

Статический полиморфизм, как некоторые пользователи ответили здесь. Например, WTL использует этот метод. Четкое объяснение реализации WTL можно найти по адресу http://www.codeproject.com/KB/wtl/wtl4mfc1.aspx#atltemplates

Answer 7

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

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

И, конечно, это также зависит от архитектуры процессора. На некоторых это может стать довольно дорогим.

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

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

Но сначала убедитесь, что у вас проблема. Код на самом деле слишком медленный, чтобы быть приемлемым? Во-вторых, выясните, что замедляет работу профилировщика. И в-третьих, исправить это.

Answer 8

Я подтверждаю все ответы, которые говорят в действительности:

• Если вы на самом деле не знаете, что это проблема, то любая забота о ее устранении, вероятно, неуместна.

То, что вы хотите знать, это:

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

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

Моя любимая техника - просто несколько раз приостановить ее под отладчиком.

Если время, затрачиваемое на вызовы виртуальных функций, является значительным, например, 20%, то в среднем 1 из 5 примеров в нижней части стека вызовов покажет в окне разборки инструкции после указателя виртуальной функции.

Если вы на самом деле этого не видите, это не проблема.

В процессе вы, вероятно, увидите другие вещи выше стека вызовов, которые на самом деле не нужны и могут сэкономить вам много времени.

Answer 9

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

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

Class A {
   inline virtual int foo() {...}
};

И когда вы находитесь в точке кода, вы УВЕРЕНЫ в типе вызываемого объекта, вы можете сделать встроенный вызов, чтобы избежать полиморфной системы и включить компиляцию.

class B : public A {
     inline virtual int foo() 
     {
         //...do something different
     }

     void bar()
     {
      //logic...
      B::foo();
      // more  logic
     }
};

В этом примере вызов foo() будет сделан неполиморфным и привязан к реализации B foo(). Но делайте это только тогда, когда вы точно знаете, какой это тип экземпляра, потому что функция автоматического полиморфизма исчезнет, ​​и это не очень очевидно для более поздних читателей кода.

Answer 10

Решением динамического полиморфизма может быть статический полиморфизм, который можно использовать, если ваши типы известны при типе компиляции: CRTP (Любопытно повторяющийся шаблон).

http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern

Объяснение Википедии достаточно ясное, и, возможно, оно могло бы помочь вам , если вы действительно определили, что вызовы виртуальных методов были источником узких мест производительности.