Какова стоимость использования указателя на функцию-член вместо переключателя? - PullRequest
12 голосов
/ 22 сентября 2008

У меня следующая ситуация:


class A
{
public:
    A(int whichFoo);
    int foo1();
    int foo2();
    int foo3();
    int callFoo(); // cals one of the foo's depending on the value of whichFoo
};

В моей текущей реализации я сохраняю значение whichFoo в элементе данных в конструкторе и использую switch в callFoo(), чтобы решить, какой из foo вызывать. Кроме того, я могу использовать switch в конструкторе, чтобы сохранить указатель вправо fooN() для вызова в callFoo().

У меня вопрос, какой путь более эффективен, если объект класса A создается только один раз, тогда как callFoo() вызывается очень большое количество раз. Таким образом, в первом случае мы имеем несколько выполнений оператора switch, тогда как во втором случае есть только один переключатель и несколько вызовов функции-члена с использованием указателя на него. Я знаю, что вызов функции-члена с использованием указателя происходит медленнее, чем простой вызов. Кто-нибудь знает, если эти издержки больше или меньше, чем стоимость switch?

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

О, и мне также больше нравится подход 2 по эстетическим соображениям. Я думаю, я ищу оправдание для его реализации. :)

Ответы [ 12 ]

11 голосов
/ 22 сентября 2008

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

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

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

8 голосов
/ 22 сентября 2008

Вы можете написать это:

class Foo {
public:
  Foo() {
    calls[0] = &Foo::call0;
    calls[1] = &Foo::call1;
    calls[2] = &Foo::call2;
    calls[3] = &Foo::call3;
  }
  void call(int number, int arg) {
    assert(number < 4);
    (this->*(calls[number]))(arg);
  }
  void call0(int arg) {
    cout<<"call0("<<arg<<")\n";
  }
  void call1(int arg) {
    cout<<"call1("<<arg<<")\n";
  }
  void call2(int arg) {
    cout<<"call2("<<arg<<")\n";
  }
  void call3(int arg) {
    cout<<"call3("<<arg<<")\n";
  }
private:
  FooCall calls[4];
};

Вычисление фактического указателя функции является линейным и быстрым:

  (this->*(calls[number]))(arg);
004142E7  mov         esi,esp 
004142E9  mov         eax,dword ptr [arg] 
004142EC  push        eax  
004142ED  mov         edx,dword ptr [number] 
004142F0  mov         eax,dword ptr [this] 
004142F3  mov         ecx,dword ptr [this] 
004142F6  mov         edx,dword ptr [eax+edx*4] 
004142F9  call        edx 

Обратите внимание, что вам даже не нужно фиксировать фактический номер функции в конструкторе.

Я сравнил этот код с asm, сгенерированным switch. Версия switch не обеспечивает увеличения производительности.

2 голосов
/ 22 сентября 2008

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

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

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

2 голосов
/ 22 сентября 2008

Если вы собираетесь продолжать использовать переключатель, что вполне нормально, тогда вам, вероятно, следует поместить логику в вспомогательный метод и вызвать if из конструктора. Кроме того, это классический случай паттерна стратегии . Вы можете создать интерфейс (или абстрактный класс) с именем IFoo, который имеет один метод с подписью Foo. Вы бы попросили конструктор взять экземпляр IFoo (конструктор Dependancy Injection , который реализовал нужный вам метод foo. У вас был бы частный IFoo, который будет установлен с этим конструктором, и каждый раз, когда вы захотите позвоните Foo, вы бы назвали версию вашего IFoo.

Примечание: я не работал с C ++ с тех пор, как поступил в колледж, поэтому мой язык может быть здесь, но общие идеи верны для большинства ОО-языков.

2 голосов
/ 22 сентября 2008

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

Чтобы ответить на незаданный вопрос: что здесь означает «лучше»? В большинстве случаев я ожидаю, что разница будет незначительной. Однако в зависимости от того, чем занимается этот класс, разница может быть значительной. Тестирование производительности, прежде чем беспокоиться о разнице, очевидно, является правильным первым шагом.

1 голос
/ 22 сентября 2008

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

пс. Чтобы усилить ответ Грега, если вам небезразлична скорость - измерьте. Просмотр ассемблера не помогает, когда у ЦП есть ветвление предварительной выборки / прогнозирования, а также задержки конвейера и т. Д.

1 голос
/ 22 сентября 2008

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

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

1 голос
/ 22 сентября 2008

Используйте таймеры, чтобы увидеть, что быстрее. Хотя, если этот код не будет повторяться, маловероятно, что вы заметите какую-либо разницу.

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

Эта техника интенсивно используется в ОС Symbian: http://www.titu.jyu.fi/modpa/Patterns/pattern-TwoPhaseConstruction.html

1 голос
/ 22 сентября 2008

Оптимизация только при необходимости

Первое: в большинстве случаев вам, скорее всего, все равно, разница будет очень мала. Убедитесь, что оптимизация этого вызова действительно имеет смысл в первую очередь. Только если ваши измерения показывают, что затраты времени на вызовы действительно затрачены, переходите к его оптимизации (бесстыдный плагин - см. Как оптимизировать приложение, чтобы оно было быстрее? ). Если оптимизация незначительна, предпочитаю более читаемый код.

Стоимость косвенного звонка зависит от целевой платформы

Как только вы определили, что стоит применить низкоуровневую оптимизацию, настало время понять вашу целевую платформу. Стоимость, которую вы можете избежать здесь, является штрафом за неправильное прогнозирование ветки. На современном процессоре x86 / x64 это неправильное прогнозирование, вероятно, будет очень небольшим (они могут предсказывать косвенные вызовы в большинстве случаев достаточно хорошо), но при нацеливании на PowerPC или другие платформы RISC косвенные вызовы / переходы часто вообще не прогнозируются и избегают они могут привести к значительному увеличению производительности. См. Также Стоимость виртуального звонка зависит от платформы .

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

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

1 голос
/ 22 сентября 2008

Я должен думать, что указатель будет быстрее.

Современные инструкции по предварительной загрузке процессоров; неправильно предсказанные ветви очищают кэш, что означает, что он останавливается, пока заполняет кэш. Указатель этого не делает.

Конечно, вы должны измерить оба.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...