无分支溢出处理

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

Is what I have really branchless? Because if the C compiler decides to use short-circuiting on &&, the code might get branched.

也许吧。在这些情况下，编译器可能足够聪明以生成无分支机器代码，但您不能依赖它。

If && causes branching, is there an alternative that has the same behavior in this case that does not involve branching?

你的问题有点乱。编译器可能会发出分支代码来实现 && 操作这一事实源于该操作的定义行为。具有相同行为的任何替代方案都必须提供相同的分支可能性。

另一方面，如果你想问是否有替代方案在所有情况下计算相同的结果，那么是的，你可以重写这些表达式来做到这一点没有分支的可能性。例如，您可以像这样使用 & 或 * 运算符：

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

或者，您可以实现您真正想要的行为：

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

没有理由认为编译器会为这些计算中的任何一个发出分支指令；如果确实如此，那可能是因为它认为这会在目标架构上提供性能改进。

Can this be faster than a basic overflow check? Or could the C compiler somehow give a branchless version of if(index < 256) buffer[index] = elem?

无分支版本当然可以更快。在大量执行（非）分支的工作负载上，它们最有可能明显更快，并且没有易于识别的模式可供选择。但是，如果（非）分支主要遵循规则模式，特别是如果它几乎总是单向运行，那么 CPU 的分支预测单元可以进行普通的有效性检查，至少与无分支分配一样快.

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

无分支溢出处理

Branchless Overflow Handling

c

assembly

branch-prediction