Как выбрать функции, вызываемые внутри вложенных циклов, прежде чем попасть в циклы?

Question

Как показано в следующем коде, одна из нескольких атомарных процедур вызывается в функции messagePassing. Какой из них использовать, определяется перед погружением во вложенные циклы. В текущей реализации несколько циклов while используются для повышения производительности во время выполнения. Я хочу избежать повторения себя (повторения общих операций во вложенных циклах) для удобства чтения и поддержки и достижения чего-то вроде messagePassingCleanButSlower.

Существует ли подход, который не жертвует производительностью во время выполнения?

Мне нужно разобраться с двумя сценариями.

1. В первом из них атомарные процедуры малы и включают в себя только 3 операции плюс / минус, поэтому я предполагаю, что они будут встроенными.
2. Во втором элементарные процедуры большие (около 200 строк) и, следовательно, вряд ли будут встроены.

#include <vector>

template<typename Uint, typename Real>
class Graph {
public:
  void messagePassing(Uint nit, Uint type);
  void messagePassingCleanButSlower(Uint nit, Uint type);

private:
  struct Vertex {}; // Details are hidden since they are distracting.
  std::vector< Vertex > vertices;

  void atomicMessagePassingType1(Vertex &v);
  void atomicMessagePassingType2(Vertex &v);
  void atomicMessagePassingType3(Vertex &v);
  // ...
  // may have other types
};

template<typename Uint, typename Real>
void
Graph<Uint, Real>::
messagePassing(Uint nit, Uint type)
{
  Uint count = 0;   // round counter
  if (type == 1) {
    while (count < nit) {
      ++count;
      // many operations
      for (auto &v : vertices) {
        // many other operations
        atomicMessagePassingType1(v);
      }
    }
  }
  else if (type == 2) {
    while (count < nit) {
      ++count;
      // many operations
      for (auto &v : vertices) {
        // many other operations
        atomicMessagePassingType2(v);
      }
    }
  }
  else {
    while (count < nit) {
      ++count;
      // many operations
      for (auto &v : vertices) {
        // many other operations
        atomicMessagePassingType3(v);
      }
    }
  }
}

template<typename Uint, typename Real>
void
Graph<Uint, Real>::
messagePassingCleanButSlower(Uint nit, Uint type)
{
  Uint count = 0;   // round counter
  while (count < nit) {
    ++count;
    // many operations
    for (auto &v : vertices) {
      // many other operations
      if (type == 1) {
        atomicMessagePassingType1(v);
      }
      else if (type == 2) {
        atomicMessagePassingType2(v);
      }
      else {
        atomicMessagePassingType3(v);
      }
    }
  }
}

Answer 1

См. Тесты здесь:

1. http://quick -bench.com / rMsSb0Fg4I0WNFX8QbKugCe3hkc

Для 1. Я настроил тестовый сценарийгде операции в atomicMessagePassingTypeX действительно короткие (только барьер оптимизации). Я выбрал примерно 100 элементов для vertices и 100 итераций внешнего while. Эти условия будут отличаться для вашего фактического кода, поэтому примените ли результаты моего теста к вашему случаю, вы должны проверить, сравнив свой собственный код.

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

template<typename Uint, typename Real>
void
Graph<Uint, Real>::
messagePassingLambda(Uint nit, Uint type)
{
  using ftype = decltype(&Graph::atomicMessagePassingType1);
  auto lambda = [&](ftype what_to_call) {
    Uint count = 0;   // round counter
    while (count < nit) {
      ++count;
      // many operations
      for (auto &v : vertices) {
        // many other operations
        (this->*what_to_call)(v);
      }
    }
  };
  if(type == 1) lambda(&Graph::atomicMessagePassingType1);
  else if(type == 2) lambda(&Graph::atomicMessagePassingType2);
  else lambda(&Graph::atomicMessagePassingType3);
}

Попробуйте все комбинации GCC 9.1 / Clang 8.0 и O2 / O3. Вы увидите, что в O3 оба компилятора дают примерно одинаковую производительность для вашего «медленного» варианта, в случае GCC он на самом деле лучший. Компилятор выводит операторы if / else как минимум из внутренних циклов, а затем, по какой-то причине, которая мне не совсем понятна, GCC меняет порядок команд во внутреннем цикле иначе, чем для первоговариант, в результате чего он будет даже чуть-чуть быстрее.

Вариант указателя функции неизменно самый медленный.

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

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

С C ++ 14 или более поздней версии вы можете сделать общую лямбду:

 auto lambda = [&](auto what_to_call) {

измените форму вызова (this->*what_to_call)(v); на what_to_call(); и вызовите ее с помощью другой лямбды:

lambda([&](){ atomicMessagePassingType1(v); });

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

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

Answer 2

Есть несколько способов.

1) Bool param. Это действительно просто перемещает if / else в функцию ... но это хорошо, когда вы используете функцию [s] в разных местах, и плохо, если вы пытаетесь вывести тест из цикла. OTOH, умозрительное выполнение должно смягчить это.

2) Указатели на функции-члены. Неприятный синтаксис в необработанном виде, но «auto» может похоронить все это для нас.

#include <functional>
#include <iostream>


class Foo
{
public:
  void bar() { std::cout << "bar\n"; }
  void baz() { std::cout << "baz\n"; }
};

void callOneABunch(Foo& foo, bool callBar)
{
    auto whichToCall = callBar ? &Foo::bar : &Foo::baz;
    // without the auto, this would be "void(Foo::*)()"
    // typedef void(Foo::*TypedefNameGoesHereWeirdRight)();
    for (int i = 0; i < 4; ++i)
    {
      std::invoke(whichToCall, foo); // C++17
      (foo.*whichToCall)(); // ugly, several have recommended wrapping it in a macro
      Foo* foop = &foo;
      (foop->*whichToCall)(); // yep, still ugly
    }
}

int main() {
    Foo myFoo;
    callOneABunch(myFoo, true);
}

Вы также можете сделать это с std::function или std::bind, но поспорив с fuctionна некоторое время я вернулся к голому синтаксису.

Answer 3

Вы можете использовать указатель функции для принятия решения перед входом в цикл, например:

template<typename Uint, typename Real>
void
Graph<Uint, Real>::
messagePassingV2(Uint nit, bool isType1)
{
    void (Graph::* aMPT_Ptr)(Vertex &); // Thanks to @uneven_mark for the corerct
    if (isType1)
        aMPT_Ptr = &Graph<Uint, Real>::atomicMessagePassingType1;  // syntax here
    else
        aMPT_Ptr = &Graph<Uint, Real>::atomicMessagePassingType2;
    Uint count = 0;   // round counter
    while (count < nit) {
        ++count;
        for (auto& v : vertices) {
            (this->*aMPT_Ptr)(v); // Again, thanks to @uneven_mark for the syntax!
        }
    }
}

Единственное, что остается потенциальной проблемой, это то, что происходит, если любая из функций «назначена»к указателю встраивается. Я думаю, что, поскольку есть код, принимающий адрес этих функций, компилятор, вероятно, предотвратит любое встраивание.