c - 使用 -O2 减少冒泡排序 C 程序的时间

Question

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void sort();

int main() {
    int i;
    for (i = 0; i < 100000; i++) {
        sort();
    }
}

void sort() {
    int i, j, k, array[100], l = 99, m;
    for (i = 0; i < 100; i++) {
        array[i] = rand() % 1000 + 1;
    }
    for (k = 0; k < 99; k++) {
        for (j = 0; j < l; j++) {
            if (array[j + 1] > array[j]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
        l--;
    }
    for (m = 0; m < 100; m++) {
        printf("%d ", array[m]);
    }
}

在 linux shell 上，gcc sort -o sort.c 然后是 time ./sort >> out。 在这里，如果我执行 gcc -o2 sort -o sort.c 和类似的 o3 和 o4 那么时间会继续减少。优化选项如何工作？请说明所有实时时间、用户时间和系统时间。

PS:代码可能有点低效。请忽略这一点。

Answer 1

优化选项在读取源代码和将二进制指令写入 CPU 之间起作用。

GCC 是一个多阶段编译器，其中阶段大致包括:

1. 从输入文本创建“标记”。
2. 将这些标记排列成抽象语法树结构。
3. 修剪抽象语法树。
4. 创建基于寄存器的指令，假设 CPU 寄存器的数量是无限的。
5. 将寄存器映射到可用的实际寄存器。
6. 以加载器预期的格式写出二进制信息。

优化会影响许多位置，通常它们会在上述第 3 步到第 5 步中变得活跃。有许多优化，包括:

• 常量折叠——提前计算常量子表达式。
• 强度降低 – 用更快的等价物代替慢速操作。
• 空序列——删除无用的操作。
• 合并操作——用一个等价的操作替换多个操作。
• 代数定律 – 使用代数定律来简化或重新排序指令。
• 特殊情况说明 – 使用为特殊操作数情况设计的说明。
• 地址模式操作——使用地址模式来简化代码。
• 循环展开 - 用等效指令替换循环
• 部分循环展开 - 减少评估循环的次数，同时保留整体功能。

请注意，这些并不是可能执行的所有优化，但它开始给你一个想法。

例如，如果编译器看到

int s = 3;
while (s < 6) {
   printf("%d\n", s);
   s++;
}

并且标志被设置为展开循环，那么它可能会编写等同于

的CPU指令

printf("%d\n", 3);
printf("%d\n", 4);
printf("%d\n", 5);

这些指令对我们人类来说可能看起来更冗长，但 CPU 命令可能更小，因为不需要“查找”现在已删除的 s 值，也不需要向其添加一个，或将新的更新值存储回 RAM。

GCC 将优化分为几类，从“安全”到“有风险”。 -O2 是速度和安全之间的良好折衷。 -O 值越高风险越大。