c—无支路溢出处理

Question

我正在尝试创建一种自动处理溢出而没有任何分支的安全缓冲区。缓冲区大小是2的幂，并且只能有有效的正(即不包括零)索引。它还允许检查删除，即如果存储在该索引上的元素等于搜索键，则在给定索引上删除。

我本来想写这样的

Element *buffer[256];
inline void buffer_insert(size_t index, Element *elem){
  buffer[index < 256 && index] = elem;
}
//Optional: checked insert to prevent overwrite. Will only insert
//if the buffer holds NULL at index.
inline void buffer_checkedInsert(size_t index, Element * elem){
  buffer[index && !buffer[index < 256 && index]] = elem;  
}
inline void buffer_checkedRemove(size_t index, Element *elem){
  buffer[0] = NULL; //Maybe useful if buffer[0] stores elem
  buffer[((elem == buffer[index < 256 && index)) && index] = NULL;
}

所以我基本上想访问索引0时，传入的索引是越界的，因为buffer[0]不是一个有效的缓冲区索引。当要移除的元素不等于传递给移除操作的元素时，我还想访问索引0，如果缓冲区中包含索引为

的内容，我也可能想访问索引0。

我的问题是:

• 我所拥有的真的是无枝的吗?因为如果C编译器决定在&&上使用短路，代码可能会被分支。
• 如果,,导致分支，在这种情况下是否存在具有相同行为但不涉及分支的替代方案?
• 这可以比基本溢出检查更快吗?或者C编译器可以以某种方式提供if(index < 256) buffer[index] = elem的无分支版本?

Answer 1

我所拥有的真的是无枝的吗?因为如果C编译器决定在&&上使用短路，代码可能会被分支。

也许。在这些情况下，编译器可能会聪明到发出无分支的机器码，但你不能依赖它。

如果,,导致分支，在这种情况下是否存在具有相同行为但不涉及分支的替代方案?

你的问题有点混乱。编译器可以发出分支代码来实现&&操作，这一事实遵循了该操作的定义行为。任何具有相同行为的选择必须提供相同的分支可能性。 另一方面，如果你想问是否有另一种方法在所有情况下都计算相同的结果，那么是的，你可以重写这些表达式来这样做而不需要分支的可能性。例如，可以使用&或*操作符，如下所示:

buffer[(index < 256) & (index != 0)] = elem;

或者，你可以实现你真正想要的行为:

buffer[(index < 256) * index] = elem;

没有理由认为编译器会为这两种计算发出分支指令;如果它这样做了，那可能是因为它认为这会在目标体系结构上提供性能改进。

这会比基本的溢出检查更快吗?或者C编译器可以以某种方式给出if(index <256) buffer[index] = elm ?

无分支的版本当然可以更快。在大量执行(非)分支的工作负载上，它们最有可能明显更快，并且没有容易识别的模式可以采用替代方案。但是，如果(非)分支大部分遵循规则模式，特别是如果它几乎总是单向的，那么CPU的分支预测单元可以进行普通的有效性检查，至少与无分支分配一样快。

最终，如果没有在真实数据上对代码的实际性能进行基准测试，或者对其进行良好的复制，就没有理由担心这个问题。结果很可能依赖于数据，它是否重要取决于您所询问的函数花费了多少程序运行时间。除非你有一个好的基准要求，否则你应该为清晰和可维护性编写代码。