时间戳

首页 > 解决方案 > 为什么函数式代码比 C 中的命令式代码快得多？

c - 为什么函数式代码比 C 中的命令式代码快得多？

问题描述

我一直在研究一种算法，用于计算各种语言中表达式的最大深度（即有多少嵌套括号），只是为了好玩/练习。

我注意到函数式 C 代码和命令式 C 代码的性能存在巨大的性能差异，我想知道为什么会这样。

给定字符串“(1+(2*3)+((8)/4))+1”，命令式代码在大约 10-13us 内始终如一地完成，但功能性代码需要 2-3us，快两倍多。这两种算法都是用-O2和 gcc 编译的，所以我发现这非常令人惊讶，但我对编译器的实现知之甚少，无法理解为什么。

那么谁能告诉我为什么功能代码的速度如此之快？

功能代码（注意 _ERR 的东西只是带有整数的#define）：

const int max_depth_functional(
        const char *expr, const int sum, const int max) {
    switch(*expr) {
        case '\0':
            return sum == 0 ? max : UNTERM_PARENTH_ERR;
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
        case '+': case '-': case '*': case '/': case '^':
            return max_depth_functional(expr + 1, sum, max);
        case '(':
            return max_depth_functional(
                expr + 1, sum + 1, sum + 1 > max ? sum + 1 : max
            );
        case ')':
            return max_depth_functional(expr + 1, sum - 1, max);
        default:
            return INVALID_EXPR_ERR;
    }
}

命令式代码：

const int max_depth_imperative(const char *expr) {
    int curr_sum = 0, curr_max = 0;
    while(*expr != '\0') {
        switch(*expr++) {
            case '0': case '1': case '2': case '3': case '4':
            case '5': case '6': case '7': case '8': case '9':
            case '+': case '-': case '*': case '/': case '^':
                break;
            case '(':
                curr_sum++;
                curr_max = curr_sum > curr_max ? curr_sum : curr_max;
                break;
            case ')':
                curr_sum--;
                break;
            default:
                return INVALID_EXPR_ERR;
        }
    }
    return curr_sum == 0 ? curr_max : UNTERM_PARENTH_ERR;
}

两者都被称为：

const clock_t start = clock();
const int func_result = max_depth_func(args[1]);
const clock_t end = clock();

另外，我正在使用 Linux x86_64 来构建和运行

标签： cperformancefunctional-programmingimperative-programming

解决方案

根据评论，我使用以下方法运行代码：

double imperative_time_sum = 0, functional_sum_time = 0;
for(int i = 0; i < 100000; i++) {
    const clock_t start_imp = clock();
    max_depth(args[1]);
    const clock_t end_imp = clock();
    max_depth_functional_fast(args[1], 0, 0);
    const clock_t end_func = clock();

    imperative_time_sum +=
        1000 * (double) (end_imp - start_imp) / CLOCKS_PER_SEC;
    functional_sum_time +=
        1000 * (double) (end_func - end_imp) / CLOCKS_PER_SEC;
}
printf("Average imperative: %fms\n", imperative_time_sum / 100000);
printf("Average functional: %fms\n", functional_sum_time / 100000);

产生的结果：

Average imperative: 0.002412ms
Average functional: 0.002421ms

尽管我之前重新运行了该程序超过 100 次，但我没有运行接近 100000 次。在那之后，时代非常接近。

推荐阅读