使用 -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]);
    }
}

上linuxshell，gcc sort -o sort.c然后time ./sort >> out。在这里，如果我做 gcc -o2 sort -o sort.c 并且类似地 o3 和 o4 那么时间会继续减少。优化选项如何工作？请解释所有实时时间、用户时间和系统时间。

PS：代码可能有点低效。请无视。

Answer 1

-O 代表 optimize，其中 gcc 将自动采取必要的步骤来优化您的程序。您可以在此处阅读有关 GCC 优化程序的具体步骤的更多信息：https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

但本质上，-O2 比 -O1 更优化，-O3 比 -O2 更优化。这可能会带来编译二进制文件大小方面的缺点，其中生成的二进制文件可以使用更多 space，但运行更快，反之亦然。您实际上可以将您的代码粘贴到 https://godbolt.org/ 中，然后在 -O1 或下拉列表旁边的任何优化选项中写入以选择编译器，然后 godbolt 将显示结果代码的样子.您将能够看到 O1 和 O2 之间的区别，即 O2 生成的代码可能更短，并且会使用很多快捷方式来执行您的算法。

Answer 2

-O 编译器标志控制您希望编译器执行的编译器优化量。简而言之，构建项目将花费更长的时间，但生成的可执行文件应该更快。有关详细信息，请在命令提示符中键入 man gcc 或 gcc -c -Q -O3 --help=optimizers 以获取有关针对特定标志执行的优化的特定信息。

Answer 3

gcc 提供了许多优化标志。你可以在这里看到每个人的具体作用：

https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

通过增加编译时间、增加内存使用等，总是需要权衡优化...

-o2 标志启用了数十项优化，因此可能无法立即清楚哪些具体优化会影响排序。除了 -o2，您可以单独尝试每个优化，例如使用 -falign-loops 标志，看看它是否是提供性能提升的那个。

Answer 4

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

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

正在根据输入文本创建 "tokens"。
将这些标记排列成抽象语法树结构。
修剪抽象语法树。
创建基于寄存器的指令，假设有无限数量的 CPU 个寄存器。
将寄存器映射到可用的实际寄存器。
正在以加载程序的预期格式写出二进制信息。

优化会影响多个位置，通常它们在上述第 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 命令可能更小，因为不需要 "lookup" s 现在已删除的值，也不需要对其加一，或将新的更新值存储回 RAM。

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

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

using -O2 decreases time of bubble sort C program

c

sorting

gcc

bubble-sort