c - 搜索最大平方算法中的优化函数

Question

我对优化有点陌生，我正在参加一场友好的比赛，以编写最快的算法来在有障碍物的领域中找到一个正方形。我认为我的算法非常快（在 10k * 10k 网格中 2.07 秒，密度为 70%），但我想让它更快。我最常用的功能是找到正方形中给定坐标的最大尺寸。这里是 ：

int     max_size(int i, int j, int **tab, int offset)
{
int a;

a = offset;
if (i > 0 && j > 0)
{
    while (i + a < g_ymax && j + a < g_xmax && tab[i + a][j + a] - tab[i + a][j - 1] - tab[i - 1][j + a] + tab[i - 1][j - 1] == 0)
        a++;
    return (a);
}
else if (i > 0 && j == 0)
{
    while (i + a < g_ymax && j + a < g_xmax && tab[i + a][j + a] - tab[i - 1][j + a] == 0)
        a++;
    return (a);
}
else if (i == 0 && j > 0)
{
    while (i + a < g_ymax && j + a < g_xmax && tab[i + a][j + a] - tab[i + a][j - 1] == 0)
        a++;
    return (a);
}
else
{
    while (i + a < g_ymax && j + a < g_xmax && tab[i + a][j + a] == 0)
        a++;
    return (a);
}
}

所以这很丑陋，我想对其进行优化。是否会使其成为内联函数的帮助？我试图运行一些测试，但我没有看到太大的差异。

标签： coptimization

Answer 1

首先，在没有考虑特定系统的情况下谈论性能或手动优化没有多大意义。通常，为了比该系统的编译器进行更好的优化，您必须是该特定系统的专家。

但是让我们假设这是一些主流的高端系统，如 x86、PowerPC 或 ARM。到目前为止，对性能最重要的是网格如何存储在内存中。

您拥有int **tab并将其视为二维数组，这是代码异味。这很可能意味着tab指向一些基于指针的查找表，可能在堆上分配。访问这样的查找表将在具有数据高速缓存存储器的系统上造成显着的性能损失，因为数据的分段将阻碍有效的数据高速缓存利用。有关如何从根本上提高这方面性能的建议，请参阅正确分配多维数组。

将网格移动到连续内存后，下一步是确保以这样的方式对其进行迭代，即最右边的维度是最频繁更改的维度。也就是说，given array[i][j]确保进行迭代，以便j成为最频繁更改的迭代器。这也与高速缓存内存的使用以及可能的对齐有关。

您可以通过减少比较次数来获得较小的性能提升，例如使用真值表。比较越少，分支预测越好。

内联函数确实可能会带来轻微的性能提升，尽管编译器应该能够在那里做出更好的决定，因为内联是以牺牲可执行文件大小和内存使用为代价的。

如果 10k*10k 是最大值，则可以通过交换 来获得较小的性能提升int，uint_fast16_t尽管这主要是针对 8 位和 16 位 CPU 的优化。