1

标题可能听起来很复杂，但只要几行代码就很容易理解了。

假设您有一个指针数组，它可能是 NULL 或可能指向实际结构。我们的任务是将所有指针设置为 NULL（删除无关紧要）。

我们可以通过以下方式做到这一点：

 // first way
 array[i] = NULL;

 // second way
 if (array[i] != NULL)
      array[i] = NULL;

我想知道，如果我们采用第二种方式，我们会在已经为 NULL 的值上节省一些速度吗？假设数组已经 50% 为 NULL。我的大学讲师曾经提到“比较不花钱，而改变价值”。这是真的吗？如果我们采用第二种方式，我们会对速度产生积极影响吗？或者额外的比较只会浪费时间？

4

4 回答 4

5

第一种方式总是更快。您必须读取指针以检查它是否为空，然后写入它，这比写入它需要更长的时间。虽然进行比较本身可能不会花费太多时间，但采用条件分支的后果肯定不好。[好的，所以编译器可以消除它，但完全不能保证]。

但与性能一样，“在互联网上询问并不能代替测量！”。

于 2013-02-02T11:43:31.863 回答
2

如果我们总是可以保存一些东西，那么编译器会在很多情况下进行这种机械转换。从来没有听说过。

我至少可以想到一种可能会节省一些东西的情况：如果你有一个巨大的数组，你在随机位置分配了一个数组，并且值通常是相同的。在这种情况下，您可能希望延长分支的周期，以防止 CPU 弄脏高速缓存行并被迫将其写回。

于 2013-02-02T11:43:30.893 回答
1

像往常一样，答案是“视情况而定”。关于您的问题集有多大，以及您的特定机器的特性。没有什么比对实际经验证据的剖析更好了。

您实际上是在将其中一个换成另一个：

  • 条件分支的成本。
  • 内存访问的成本。

对于每个数组元素，您的第一个解决方案只需要一次内存写入。第二种解决方案需要读取、比较，然后是条件写入。如果读取比写入便宜，并且比较相对便宜，那么如果有很多 NULL 条目，它可能会更快。

我的头上的回答是第一种方法，相当于 a memcpy，在现代处理器上可能更快，特别是如果使用非临时写入进行优化，因为它不会分支（昂贵！）并且不需要浪费你的带有元素的 CPU 缓存只读取一次。

于 2013-02-02T11:45:25.180 回答
0

让我们从基本原则开始：你的导师告诉你的往往是完全倒退的。写入通常比读取快。具体来说（至少对于大多数现代 CPU），写入只是意味着将地址和值存入队列。然后 CPU 的其他部分可以处理将该值写入内存，而执行单元可以继续执行更多指令。但是，如果在写入队列已满时/如果您尝试写入更多数据，指令流可能会停止。

相比之下，要进行比较，如果数据尚未在缓存中，则必须将地址写入内存，然后停止直到数据从内存到达才能正确使用它进行比较。

比较还使用标志寄存器，它有很大的“寄存器压力”，因为大多数指令都会修改它们。这可以防止原本可用的指令级并行性。

现在，确实，您通常宁愿避免使用相关数据污染缓存，除非您很快会将其用于其他目的。一些缓存通过不在写入时分配缓存空间而完全避免了这种情况——即，除非您最近读取了数据，因此它已经在缓存中，否则写入它不会将其移动到缓存中；它只会将数据直接写入主存储器。

许多（大多数？）最近的处理器还具有始终直接写入内存的指令，而不管缓存策略如何。英特尔（例如）调用这些非临时存储（例如，MOVNTQ 和 MOVNTPS）。但是，正确使用这些可能有点棘手。与普通的内存写入不同，默认情况下它们不保证缓存一致性。您需要在写入后执行 SFENCE 指令，以确保其他处理器将看到写入的结果。

另一次值得进行比较的时候是单个比较可以让您避免大量写入。例如，假设您的数组非常稀疏，因此几百个条目中只有大约一个是非空的。在这种情况下，您可以（例如）使用位图，其中位图中的一位表示指针是否为空。在这种情况下，单个 64 位比较可以让您避免（例如）写入每个 64 位的 64 个不同指针中的任何一个。

不过，单独查看指针不会带来任何好处——具体而言，您需要先将每个指针加载到缓存中，然后才能进行比较，因此尝试逐个比较以避免污染缓存是一种弄巧成拙的主张。

于 2013-02-02T13:57:12.407 回答