5

比如我想用数组SQRT[i]创建一个平方根表来优化一个游戏，但是不知道下面的初始化在访问SQRT[i]的值时会不会有性能差异：

  1. 硬编码数组

    int SQRT[]={0,1,1,1,2,2,2,2,2,3,3,.......255,255,255}

  2. 在运行时产生价值

    int SQRT[65536];
int main(){
    for(int i=0;i<65536;i++){
        SQRT[i]=sqrt(i);
    }
    //other code
    return 0;
}

访问它们的一些示例：

    if(SQRT[a*a+b*b]>something)
    ...

我不清楚程序是否以不同的方式存储或访问硬代码数组，也不知道编译器是否会优化硬代码数组以加快访问时间，它们之间是否存在性能差异访问数组时？

4

3 回答 3

4

首先，您应该正确执行硬编码数组：

static const int SQRT[]={0,1,1,1,2,2,2,2,2,3,3,.......255,255,255};

（也使用uint8_t代替int可能更好，以减少数组的大小并使其对缓存更友好）

这样做比替代方案有一个很大的优势：编译器可以轻松检查数组的内容是否无法更改。

没有这个，编译器必须是偏执的——每个函数调用都可能改变 的内容SQRT，每个指针都可能指向SQRT，因此任何通过int*或char*可能正在修改数组的写入。如果编译器不能证明这不会发生，那么就会限制它可以做的优化类型，在某些情况下可能会影响性能。

另一个潜在的优势是能够在编译时解决涉及常量的事情。

如果需要，您可以通过巧妙地使用__restrict__.

在现代 C++ 中，您可以两全其美；应该有可能（并且以合理的方式）编写将在编译时运行的代码以初始化SQRT为constexpr. 不过，最好问一个新问题。

于 2015-08-13T06:03:40.843 回答
1

正如人们在评论中所说：

if(SQRT[a*a+b*b]>something)

是一个可怕的示例用例。如果这就是您需要 SQRT 的全部，只需 square something。

只要您可以告诉编译器SQRT没有任何别名，那么运行时循环将使您的可执行文件更小，并且在启动期间只会增加少量的 CPU 开销。肯定用uint8_t，不行int。从 8 位内存位置加载 32 位临时文件并不比从零填充的 32b 内存位置加载慢。（x86 上的额外movsx指令，而不是使用内存操作数，将在减少缓存污染方面付出更多的代价。RISC 机器通常不允许内存操作数，因此您总是需要一条指令将值加载到寄存器中。 )

此外，sqrt在 Sandybridge 上是 10-21 周期延迟。如果你不经常需要它，int->double、sqrt、double->int 链并不比 L2 缓存命中差多少。而且比去 L3 或主内存要好。如果你需要很多sqrt，那么当然，做一个LUT。即使您在桌子上弹跳并导致 L1 未命中，吞吐量也会好得多。

您可以通过平方而不是 sqrting 来优化初始化，例如

uint8_t sqrt_lookup[65536];
void init_sqrt (void)
{
    int idx = 0;
    for (int i=0 ; i < 256 ; i++) {
        // TODO: check that there isn't an off-by-one here
        int iplus1_sqr = (i+1)*(i+1);
        memset(sqrt_lookup+idx, i, iplus1_sqr-idx);
        idx = iplus1_sqr;
    }
}

您仍然可以获得存在的好处sqrt_lookup（const编译器知道它不能别名）。要么使用restrict，要么对编译器撒谎，所以表的用户看到一个const数组，但你实际上是写给它的。

这可能涉及对编译器撒谎，extern const在大多数地方声明它，而不是在初始化它的文件中。您必须确保这确实有效，并且不会创建引用两个不同符号的代码。如果您只是丢弃了const初始化它的函数，如果编译器将它放入rodata（或者如果它未初始化，则可能是只读bss内存，如果在某些平台上可能的话？）

也许我们可以避免对编译器撒谎，方法是：

uint8_t restrict private_sqrt_table[65536];  // not sure about this use of restrict, maybe that will do it?
const uint8_t *const sqrt_lookup = private_sqrt_table;

实际上，这只是一个const指向const数据的指针，并不能保证它所指向的内容不能被另一个引用更改。

于 2015-08-14T00:59:03.200 回答
0

访问时间将相同。当您对数组进行硬编码时，在 main 之前调用的 C 库例程将对其进行初始化（在嵌入式系统中，启动代码将读写数据复制，即从 ROM 硬编码到数组所在的 RAM 地址，如果数组是常量，则直接从 ROM 访问）。

如果使用 for 循环进行初始化，那么调用 Sqrt 函数就会产生开销。

于 2015-08-13T05:43:41.253 回答