无分支溢出处理

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] = elem？

无分支版本肯定可以会更快。在非（非）分支执行很多的工作负载上，它们最有可能显着加快，并且没有容易辨别的替代方式。但是，如果（非）分支大多遵循规则模式，特别是如果它几乎总是以单向的方式进行，那么CPU的分支预测单元可以进行普通有效性检查，至少与无分配分配一样快。

最终，没有充分的理由担心这个问题，而没有在实际数据或者其良好的传真基础上对代码的实际性能进行基准测试。结果很可能取决于数据，它的重要程度取决于程序的运行时间花费在您询问的功能上的多少。除非你有一个好的基准，否则你应该为清晰度和可维护性编码。