Где накладные расходы на вызов виртуальной функции?

Question

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

Вот код:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

long long timespecDiff(struct timespec *timeA_p, struct timespec *timeB_p)
{
return ((timeA_p->tv_sec * 1000000000) + timeA_p->tv_nsec) -
    ((timeB_p->tv_sec * 1000000000) + timeB_p->tv_nsec);
}

void function_not( double *d ) {
*d = sin(*d);
}

void function_and( double *d ) {
*d = cos(*d);
}

void function_or( double *d ) {
*d = tan(*d);
}

void function_xor( double *d ) {
*d = sqrt(*d);
}

void ( * const function_table[4] )( double* ) = { &function_not, &function_and, &function_or, &function_xor };

int main(void)
{
srand(time(0));
void ( * index_array[100000] )( double * );
double array[100000];
for ( long int i = 0; i < 100000; ++i ) {
    index_array[i] = function_table[ rand() % 4 ];
    array[i] = ( double )( rand() / 1000 );
}

struct timespec start, end;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
for ( long int i = 0; i < 100000; ++i ) {
    index_array[i]( &array[i] );
}
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

unsigned long long time_elapsed = timespecDiff(&end, &start);
cout << time_elapsed / 1000000000.0 << endl;
}

и вот вариант виртуальной функции:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

long long timespecDiff(struct timespec *timeA_p, struct timespec *timeB_p)
{
return ((timeA_p->tv_sec * 1000000000) + timeA_p->tv_nsec) -
    ((timeB_p->tv_sec * 1000000000) + timeB_p->tv_nsec);
}

class A {
public:
    virtual void calculate( double *i ) = 0;
};

class A1 : public A {
public:
    void calculate( double *i ) {
    *i = sin(*i);
    }
};

class A2 : public A {
public:
    void calculate( double *i ) {
        *i = cos(*i);
    }
};

class A3 : public A {
public:
    void calculate( double *i ) {
        *i = tan(*i);
    }
};

class A4 : public A {
public:
    void calculate( double *i ) {
        *i = sqrt(*i);
    }
};

int main(void)
{
srand(time(0));
A *base[100000];
double array[100000];
for ( long int i = 0; i < 100000; ++i ) {
    array[i] = ( double )( rand() / 1000 );
    switch ( rand() % 4 ) {
    case 0:
    base[i] = new A1();
    break;
    case 1:
    base[i] = new A2();
    break;
    case 2:
    base[i] = new A3();
    break;
    case 3:
    base[i] = new A4();
    break;
    }
}

struct timespec start, end;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
for ( int i = 0; i < 100000; ++i ) {
    base[i]->calculate( &array[i] );
}
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

unsigned long long time_elapsed = timespecDiff(&end, &start);
cout << time_elapsed / 1000000000.0 << endl;
}

Моя система - LInux, Fedora 13, gcc 4.4.2. Код скомпилирован с помощью g ++ -O3. Первый - test1, второй - test2.

Теперь я вижу это в консоли:

[Ignat@localhost circuit_testing]$ ./test2 && ./test2 
0.0153142
0.0153166

Ну, более или менее, я думаю. И затем, это:

[Ignat@localhost circuit_testing]$ ./test2 && ./test2 
0.01531
0.0152476

Где 25%, которые должны быть видны? Как первый исполняемый файл может быть даже медленнее, чем второй?

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

Answer 1

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

Answer 2

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

Answer 3

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

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

void function_not( double *d ) {
    *d = 1.0;
}

void function_and( double *d ) {
    *d = 2.0;
}

И т. Д., И аналогично для виртуальных функций.

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

С этими изменениями результаты немного отличаются. Лучший из 4 трасс в каждом случае. (Не очень научно, но цифры в целом схожи для большего количества прогонов.) Все таймеры работают на моем ноутбуке циклично. Код был скомпилирован с использованием VC ++ (только изменил время), но gcc реализует вызовы виртуальных функций таким же образом, поэтому относительные временные параметры должны быть примерно одинаковыми даже с различными процессорами / компиляторами OS / x86.

Функциональные указатели: 2,052,770

Виртуалы: 3 598 039

Эта разница кажется немного чрезмерной! Конечно же, два бита кода не совсем одинаковы с точки зрения поведения доступа к памяти. Второй должен иметь таблицу 4 A * s, используемую для заполнения базы, а не для создания новой для каждой записи. В этом случае оба примера будут иметь одинаковое поведение (1 промах кэша / N записей) при получении указателя для перехода. Например:

A *tbl[4] = { new A1, new A2, new A3, new A4 };
for ( long int i = 0; i < 100000; ++i ) {
    array[i] = ( double )( rand() / 1000 );
    base[i] = tbl[ rand() % 4 ];
}

Имея это, все еще используя упрощенные функции:

Виртуалы (как предлагается здесь): 2 487 699

Так что 20%, лучший случай. Достаточно близко?

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

Answer 4

Многие люди привыкли делать что-то просто потому, что их считают «быстрее». Это все относительно.

Если я собираюсь проехать 100 миль от моего дома, я должен начать с обхода квартала. Я могу объехать квартал направо или налево. Один из них будет «быстрее». Но будет ли это иметь значение? Конечно нет.

В этом случае вызываемые вами функции, в свою очередь, вызывают математические функции.

Если вы ставите программу на паузу в среде IDE или GDB, я подозреваю, что вы обнаружите, что почти каждый раз, когда вы приостанавливаете ее, она будет в этих подпрограммах математической библиотеки (или должна быть!) И разыменовывает дополнительный указатель, чтобы попасть туда. (при условии, что он не разрушает кэш) должен быть потерян в шуме.

Добавлено: вот любимое видео: ретранслятор Гарри Портера . Поскольку эта штука кропотливо отбирает добавление чисел и добавление счетчика программ, я считаю полезным помнить, что это то, что делают все компьютеры, просто в разном масштабе времени и сложности. В вашем случае подумайте об алгоритме sin, cos, tan или sqrt. Внутри он таращится, делая эти вещи, и лишь случайно следуя адресам или работая с очень медленной памятью, добирается туда.

Answer 5

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

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

Answer 6

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