Условие теста с вызовом функции и простым тестом, выполняющим примерно то же самое

Question

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

Вот код:

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

struct list_t {
    int val;
    struct list_t *next;
};
typedef struct list_t list_t;

// Removes elements not matching the predicate.
// NOTE: This is not freeing the removed elements.

list_t *keep(int (*predfun)(int,int), int predarg, list_t *list) {
    list_t *this, *prev;

    for (this=list, prev=NULL; this; prev=this, this=this->next) {
        if (!predfun(this->val, predarg)) {
            if (!prev) {
                list = this->next;
            }
            else {
                prev->next = this->next;
            }
        }
    }

    return list;
}

int less(int a, int b) {
    return a<b;
}

// A "template" macro for the keep function.
// The idea is to embed the predicate into the function, so that we
// don't have to make a function call on each iteration.

#define build_keep(test) {                                           \
    list_t *this, *prev;                                             \
                                                                     \
    for (this=list, prev=NULL; this; prev=this, this=this->next) {   \
        if (!(test)) {                                               \
            if (!prev) {                                             \
                list = this->next;                                   \
            }                                                        \
            else {                                                   \
                prev->next = this->next;                             \
            }                                                        \
        }                                                            \
    }                                                                \
    return list;                                                     \
}


list_t *keep_less(int arg, list_t *list) {
    build_keep(this->val < arg);
}

#define LEN 1000000
#define MOD 1024

// Creates a new list.
list_t *buildlist() {
    int i;
    list_t *list, *last, *t;
    list=NULL, last=NULL;
    srand(0); // Using always the same seed for the benchmark.
    for (i=0; i<LEN; i++) {
        if (!last) {
            last = malloc(sizeof(list_t));
            list = last;
        }
        else {
            last->next = malloc(sizeof(list_t));
            last = last->next;
        }
        last->val = rand() % MOD;
    }
    last->next = NULL;
    return list;
}    

int main() {
    struct timeval t0, t1;
    list_t *list, *t;

    // With macro.
    list = buildlist();
    //for (t=list; t; t=t->next) printf("%d ", t->val); printf("\n");
    gettimeofday(&t0, NULL);
    keep_less(500, list);
    gettimeofday(&t1, NULL);
    printf("keep_less: %lf\n", (1000000 * (t1.tv_sec - t0.tv_sec) + (t1.tv_usec - t0.tv_usec))/1000000.0);
    //for (t=list; t; t=t->next) printf("%d ", t->val); printf("\n");

    printf("\n");

    // Without macro.
    list = buildlist();
    //for (t=list; t; t=t->next) printf("%d ", t->val); printf("\n");
    gettimeofday(&t0, NULL);
    keep(less, 500, list);
    gettimeofday(&t1, NULL);
    printf("keep: %lf\n", (1000000 * (t1.tv_sec - t0.tv_sec) + (t1.tv_usec - t0.tv_usec))/1000000.0);
    //for (t=list; t; t=t->next) printf("%d ", t->val); printf("\n");

    return 0;
}

Вывод здесь:

keep_less: 0.181019

keep: 0.185590

Answer 1

Поскольку Офек на самом деле не ответил на вопрос ;-) что такое , почему это происходит? . Очевидно, что компилятор делает довольно хорошую работу, здесь.

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

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

Answer 2

Я бы не сказал, что результаты примерно одинаковы - вы видите разницу в 4 милисекунды (~ 2%) в пользу немедленной версии.

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