*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

суббота, 25 июля 2009 г.

Кто быстрее: функтор или указатель на функцию

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

functor.cpp:
#include "gtest/gtest.h"

#include <algorithm>

typedef double Type;

Type* array;
const int N = 100000000;

inline bool less(Type a1, Type a2) {
return a1 < a2;
}

class Less {
public:
inline bool operator()(Type a1, Type a2) {
return a1 < a2;
}
};

// Использование встроенной функции сравнения.
TEST(Callback, BuiltIn) {
std::sort(array, array + N);
}

// Использование свободной функции сравнения по указателю.
TEST(Callback, Function) {
std::sort(array, array + N, less);
}

// Использование функтора.
TEST(Callback, Functor) {
std::sort(array, array + N, Less());
}

int main(int argc, char* argv[]) {
// Создаем отсортированный массив.
array = new Type[N];
Type* p = array;
for (int i = 0; i < N; ++i) *p++ = i;

testing::InitGoogleTest(&argc, argv);
// Принудительно печатаем время работы тестов.
testing::GTEST_FLAG(print_time) = true;
return RUN_ALL_TESTS();
}
Компилируем и запускаем (Visual Studio 2008):
cl /O2 /arch:SSE2 /EHsc /I. functor.cpp gtest\gtest-all.cc && functor
Результат:
[==========] Running 3 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 3 tests from Callback
[ RUN ] Callback.BuiltIn
[ OK ] Callback.BuiltIn (9547 ms)
[ RUN ] Callback.Function
[ OK ] Callback.Function (24391 ms)
[ RUN ] Callback.Functor
[ OK ] Callback.Functor (9578 ms)
[----------] 3 tests from Callback (43547 ms total)

[----------] Global test environment tear-down
[==========] 3 tests from 1 test case ran. (43547 ms total)
[ PASSED ] 3 tests.
Видно, что скорость функтора (9578 мс) практически равна встроенной функции (9547 мс) сравнения. А вот вызов свободной функции конкретно отстает (24391 мс), приблизительно в 2.5 раза.

Такое поведение можно объяснить тем, что в данном случае при вызове обычной функции компилятор не может оптимизировать такой вызов встраиванием (inlining). Вне зависимости от того, что функция объявлена выстраиваемой, так как ее вызов производится по указателю, компилятор не может сделать предположений о значении этого указателя на стадии исполнения, а значит провести оптимизацию.

При использовании же функтора компилятору доступна информация о семантике вызываемого кода, поэтому все типы оптимизации возможны. Отсюда и скорость, близкая к встроенной функции сравнения.
Как вариант, при замене типа с double на int и при условии, что опция /arch:SSE2 включена, тест с функтором работал даже быстрее встроенной функции.
Вывод

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


Данный пост является экспериментом по использованию Google Code в качестве хостинга для размещения исходных текстов примеров и самих статей.

Головная страница проекта - http://code.google.com/p/easy-coding/.

Каждый пост будет по необходимости размещаться в отдельном каталоге и отдельной страницей Wiki.

11 комментариев:

  1. Для интереса скомпилировал похожий бенчмарк в g++ 4.4.1 и icc 11.1:
    g++ functor.cc -O3
    > Standart: 6.29
    > Function: 6.26
    > Functor: 6.32

    icc functor.cc -fast
    > Standart: 5.19
    > Function: 5.23
    > Functor: 5.23

    Я к тому, что из подобных сравнений не стоит делать такие громкие выводы. Единственный вывод, который можно сделать, что, вероятно, cl (какой версии?) не умеет делать инлайнинг функций, переданных как указателей в std::sort.

    ОтветитьУдалить
  2. Собрал конкретно этот пример в GCC 4.3.2 20080827 (beta) 2 на чуть более быстрой машине.

    g++ -O3 -o functor -I. functor.cpp gtest-all.cc

    ./functor

    [==========] Running 3 tests from 1 test case.
    [----------] Global test environment set-up.
    [----------] 3 tests from Callback
    [ RUN ] Callback.BuiltIn
    [ OK ] Callback.BuiltIn (4392 ms)
    [ RUN ] Callback.Function
    [ OK ] Callback.Function (9719 ms)
    [ RUN ] Callback.Functor
    [ OK ] Callback.Functor (4391 ms)
    [----------] 3 tests from Callback (18542 ms total)

    [----------] Global test environment tear-down
    [==========] 3 tests from 1 test case ran. (18545 ms total)
    [ PASSED ] 3 tests.

    Опять указатель на функцию проигрывает.

    К сожалению на GCC 4.4.1 проверить не могу, но если оптимизатор в 4.4.1 так радикально шагнул вперед по сравнению с 4.3.2, то надо срочно обновляться. Хотя, как-то сомнительно.

    Кстати, компилятор cl из Visual Studio 2008, версия 15.00.21022.08 for 80x86.

    Просто интересно, как можно оптимизировать в inline вызов по указателю, если в runtime указатель может быть другой.

    Может мы компилируем разные примеры? Можете привести ваш тест?

    ОтветитьУдалить
  3. http://pastebin.com/f51bd326f

    Если скомпилируете в g++ с флагами -O3 -fdump-tree-optimized, то будет видно различие (точнее почти отсутствие различий) в генерируемых оптимизированных алгоритмах.

    В первом примере генерируется вызов подставленной __introsort_loop без компаратора.

    Во втором примере вызов генерированной функции, аналогичной __introsort_loop без компаратора. Функция по указателю снова инлайнится.

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

    ОтветитьУдалить
  4. Хм, скомпилил ваш пример на GCC 4.3.2.

    g++ -O3 -fdump-tree-optimized functor.cpp

    ./functor

    Standart: 0.562
    Function: 0.969
    Functor: 0.563

    Странно. Опять функтор быстрее.

    Может в платформе дело? Я компилю все на x86, а вы на какой?

    ОтветитьУдалить
  5. А вот прогон вашего примера через cl, правда на другой машине.

    cl /O2 functor.cpp

    functor.exe

    Standart: 0.047
    Function: 0.157
    Functor: 0.078

    Тенденция та же.

    ОтветитьУдалить
  6. x86, Intel E8500.

    Прогнал ещё раз 10, различия только в случайных погрешностях.

    Попробуйте http://www.mediafire.com/download.php?1jtjnzwwihm , может правда пора обновляться.

    ОтветитьУдалить
  7. Lockal: Я тут разыскал GCC 4.4.0 и вот что вышло с вашим примером:

    g++ -o func -O3 func.cpp

    Standart: 0.45
    Function: 0.38
    Functor: 0.41

    g++ -o func -O2 func.cpp

    Standart: 0.39
    Function: 0.38
    Functor: 0.38

    Получается, что -O2 в данном случае лучше чем -O3 (повторял много раз, тенденция одна и та же), а опция -fdump-tree-optimized роли не играет.

    ОтветитьУдалить
  8. Я не понятно объяснил =)
    -fdump-tree-optimized не влияет на компиляцию, а только генерирует промежуточный си-подобный листинг в файле с расширением optimized. Там и можно посмотреть, что подставилось, а что нет.

    Кстати, почему у вас так быстро отрабатывает? У меня после вызова srand в среднем по 5-7 секунд отрабатывает. Без srand что -O3, что -O2 отрабатывают за абсолютно одинаковое время.

    ОтветитьУдалить
  9. Да, про -fdump-tree-optimize я уж понял, обнаружив интересный файл объяснениями что куда соптимизировалось ;-).

    А быстро, потому, что я уменьшил N на один нолик ;-). На которых моих машинах я ограничен в плане ресурсов, и программа падала с std::bad_alloc из-за нехватки памяти. Пришлось уменьшить размерность. Но в целом, показательность осталась.

    ОтветитьУдалить
  10. Идиотские эксперименты.. вообще на ассемблере пишите и будет вам скорость...

    ОтветитьУдалить
  11. Некоторые вещи, связанные с тестированием эффективности в C++

    http://groups.google.co.il/group/perfo
    http://groups.google.co.il/group/sources
    http://groups.google.co.il/group/log-files

    ОтветитьУдалить