c - 优化嵌套循环上的 ac 代码

Question

我有以下代码

for(i=0;i<16;i++)
  for(j=0;j<16;j++)
  {
     in=(i+u*j+rl+rc)&15;
     jn=(v*i+(u*v+1)*j+rc)&15;
     x1[i*16+j]=x2[in*16+jn];
   }

一些注意事项：

1. rl, rc, u, 和v是随机值，范围从 0 到 15
2. x1并且x2是 256 个值的数组，每个数组值的范围在 0 到 255 之间
3. 如果我想使用查找表来实现这个代码需要 16MB 和这个大内存

Answer 1

这是一个想法：

尝试提取至少在内部循环之外不会改变的部分计算。例如，i + rl + rc计算in不需要在循环内。一旦你有了它，你就会意识到每次迭代的值都会in增加u，当然是模 16。因此，您可以进行加法，而不是乘法。

该jn计算还引用了一些您可以提取的内容。

当然，这是假设您实际上知道这是一个性能瓶颈（分析它！）并且编译器不够聪明，无法为您进行这样的优化。如有疑问，请检查组件。

Answer 2

您可以尝试一些想法：

u您可以为和的所有组合构建一个查找表v，这将只需要 64k 内存。rl并rc作为水平和垂直的恒定偏移量（它们可以移动到最后一个语句，并且不必参与inand的计算jn）。这会减少你必须做的数学运算。

与任何其他性能优化一样，您首先需要查看这是否真的是瓶颈。可能是内存要慢得多，引入大型查找表只会减慢速度。