Почему эта виртуальная функция так дорого стоит?

Question

Недавно я модифицировал программу для использования виртуальных функций (вместо последовательности, если if-else условия со статическими вызовами.) Измененная программа работает на 8% медленнее оригинала. Это похоже на слишком высокую стоимость использования виртуальных функций, поэтому я должен делать что-то неэффективное в том, как я устанавливаю иерархию классов и виртуальные функции; но я не понимаю, как отследить проблему. (Я вижу подобное ухудшение производительности, используя как clang на моем Mac, так и gcc на Linux.)

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

Вот грубый набросок исходного кода

int main(int argc, char* argv[]) { 
    bool use_m1; 
    bool use_m2; 
    ... 
    bool use_m10; 

    // set the various "use" flags based on argv 

    for (Graph& g : graphsToStudy()) { 
     for (Partition& p : allPartitions()) { 
      if (use_m1) { 
       M1::evaluate(g, p); 
      } 
      if (use_m2) { 
       M2::evaluate(g,p); 
      } 
      // and so on 
     } 
    } 

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

class ObjectiveFunction { 
public: 
    virtual double eval(Graph& g, Partition& p) = 0; 
} 

class ObjFn1 : public ObjectiveFunction { 
public: 
    virtual double eval(Graph& g, Partition& p) { 
     return M1::evaluate(g,p); 
    } 
} 

class ObjFn2 : public ObjectiveFunction { 
public: 
    virtual double eval(Graph& g, Partition& p) { 
     return M2::evaluate(g,p); 
    } 
} 


int main(int argc, char* argv[]) { 
    vector<ObjectiveFunction*> funcs; 
    fill_funcs_based_on_opts(funcs, argc, argv); 

    for (Graph& g : graphsToStudy()) { 
     for (Partition& p : allPartitions()) { 
      // funcs contains one object for each function selected by user. 
      for (ObjectiveFunction* fp : funcs) { 
       fp->evaluate(g, p); 
      } 
     } 
    } 

Учитывая, что генерация графов и разделов, а также самих объектных функций являются умеренно вычислительно интенсивными, добавление вызова виртуальной функции должно быть почти незаметным. Любые идеи, что я, возможно, сделал неправильно; или как его отслеживать? Я пробовал использовать callgrind, но я не вижу никаких прозрений.

Возможно, я просто неправильно интерпретирую вывод callgrind_annotate. В приведенном ниже примере Neo::Context::evaluatePartition аналогичен ObjFn1::evaluate в приведенном выше примере.

1. Почему эта функция перечислен четыре раза с различными исходными файлами? Этот метод вызван только из функции main в timeMetrics.cpp.

2. Что такое src/lib/PartitionIterator.h:main обратитесь к? В PartitionIterator.h нет основной функции .

3. Почему 414,219,420 дважды появляется в списке исходных кодов для evaluatePartition? Разве это не первое число, которое должно представлять служебные данные вызова функции?

---

35,139,513,913 PROGRAM TOTALS 
17,029,020,600 src/lib/metrics/Neo.h:gvcd::metrics::Neo::Context<unsigned int, unsigned char, unsigned int>::evaluatePartition(gvcd::Partition<unsigned int, unsigned int> const&, bool) [bin/timeMetrics_v] 
7,168,741,865 /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/vector:gvcd::Partition<unsigned int, unsigned int>::buildMembersh ipList() 
4,418,473,884 src/lib/Partition.h:gvcd::Partition<unsigned int, unsigned int>::buildMembershipList() [bin/timeMetrics_v] 
1,459,239,657 src/lib/PartitionIterator.h:main 
1,288,682,640 /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/vector:gvcd::metrics::Neo::Context<unsigned int, unsigned char, u nsigned int>::evaluatePartition(gvcd::Partition<unsigned int, unsigned int> const&, bool) 
1,058,560,740 src/lib/Partition.h:gvcd::metrics::Neo::Context<unsigned int, unsigned char, unsigned int>::evaluatePartition(gvcd::Partition<unsigned int, unsigned int> const&, bool) 
1,012,736,608 src/perfEval/timeMetrics.cpp:main [bin/timeMetrics_v] 443,847,782 /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/vector:main 
368,372,912 /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:gvcd::Partition<unsigned int, unsigned int>::buildMembersh ipList()  
322,170,738 /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/ostream:main 
    92,048,760 src/lib/SmallGraph.h:gvcd::metrics::Neo::Context<unsigned int, unsigned char, unsigned int>::evaluatePartition(gvcd::Partition<unsigned int, unsigned int> const&, bool) 
    84,549,144 ???:szone_free_definite_size [/usr/lib/system/libsystem_malloc.dylib] 
    54,212,938 ???:tiny_free_list_add_ptr [/usr/lib/system/libsystem_malloc.dylib] 



      .   virtual double 
    414,219,420   evaluatePartition(const Partition <VertexID, SetBitmap> &p, bool raw = false) { 
    414,219,420   uint_wn_t raw_answer = Neo::evaluatePartition(*(this->g), p); 
      .   return (double) (raw ? raw_answer : max_neo - raw_answer); 
      .   } 
      .  }; // end Context 

Answer 1

Позволяет зафиксировать очевидный первый:

В обоих вариантах вы делаете это:

foreach (Graph g : graphsToStudy()) { 
    foreach (Partition p : allPartitions()) { 

Если Graph/Partition не легко и мало, чтобы скопировать то большинство ваша работа будет здесь.

foreach (Graph& g : graphsToStudy()) { 
      //^
    foreach (Partition& p : allPartitions()) { 
        //^

Второй вопрос у меня есть. Это не похоже на правильное использование виртуальных функций. Исходный код выглядит полностью в этом случае, когда на каждую пару (g, p) вызывается несколько версий evaluate().

Теперь, если вы только называется каждый из evaluate() функций, то это может быть лучше использовать случай, но тогда вам больше не нужно, что внутренняя петля:

foreach (ObjectiveFunction* fp : funcs) { 

Answer 2

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

Это может помочь филиальную предсказатель, если заменить коллекцию итерацию с внутренней связного списка:

class ObjectiveFunction 
{ 
    ObjectiveFunction* m_next; 
    virtual double evaluate(Graph& g, Partition& p) = 0; 

    protected: 
    ObjectiveFunction(ObjectiveFunction* next = nullptr) : m_next(next) {} 

    // for gcc use __attribute__((always_inline)) 
    // for MSVC use __forceinline 
    void call_next(Graph& g, Partition& p) 
    { 
     if (m_next) m_next->eval(g, p); 
    } 
    public: 
    virtual void eval(Graph& g, Partition& p) = 0; 
}; 

Теперь, вместо одной строки кода внутри цикла, достигающего множество различных функций, функция call_next() (которая должна быть последним шагом каждого отдельного eval перегрузки) должны быть включены в каждую из этих перегрузок, и во время выполнения каждая встроенная копия этой команды косвенного вызова будет повторно вызывать только одну функцию, что приведет к 100% -ному прогнозу ветвления.

Answer 3

Где я могу, я предпочитаю статическую динамическую диспетчеризацию - динамическая отправка может стоить вам, предотвращая такие оптимизации, как функция inlining, а с двойным разрывом, связанным с vtables, вы можете страдать от плохой локальности (пропуски кэша команд).

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