计算多个内存块的最快方法

Question

我有一个内存区域，它被划分为预定义 BLOCKSIZE 大小的块。给定一个内存块，由其偏移量 OFFSET 以字节为单位和 SIZE 以字节为单位定义，如何有效地计算包含该内存块的块数？

例如，假设 BLOCKSIZE=8。那么 OFFSET=0 和 SIZE=16 的内存块将占用 2 个块，而 OFFSET=4 和 SIZE=16 的内存块将占用 3 个块。

我可以写出这样的公式（使用 C 中的整数运算）：

numberOfBlocks = (OFFSET + SIZE - 1) / BLOCKSIZE - (OFFSET / BLOCKSIZE) + 1;

这个计算需要 2 个除法和 4 个加法。如果 BLOCKSIZE 是 2 和 OFFSET >= 0 和 SIZE > 0 的 次方，我们可以做得更好吗？

更新：我知道在这种情况下可以用移位代替除法。

Answer 1

Can we do better, provided that the BLOCKSIZE is a power of 2?

我不这么认为。您的（更正后的）公式基本上是（块后第一个块的索引）-（包含块的任何部分的第一个块的索引）。你可以用不同的方式来表述它——比如，作为基本块数的总和加上对需要一个额外块的某些布局的调整——但这实际上增加了一对夫妇所需的操作数：

numberOfBlocks = (SIZE + BLOCKSIZE - 1) / BLOCKSIZE
        + ((SIZE % BLOCKSIZE) + (OFFSET % BLOCKSIZE)) / BLOCKSIZE;

我看不到执行（至少）两个整数除法（或等效位移）的任何方法，因为任何计算方法都需要计算 two 块计数。这两个计算不能合并，因为每个计算都需要单独的余数截断。

BLOCKSIZE 是 2 的幂可能有助于您选择更高效的运算，但无助于减少所需运算的数量。但是，如果您可以依靠 SIZE 是 BLOCKSIZE 的倍数，您可以稍微减少操作次数。在这种情况下，您可以这样做：

numberOfBlocks = SIZE / BLOCKSIZE + (OFFSET % BLOCKSIZE) ? 1 : 0;

或者，如果计算覆盖块数的上限就足够了，那么您可以这样做：

numberOfBlocksBound = SIZE / BLOCKSIZE + 2;

或在许多情况下稍微更严格，但计算成本更高：

numberOfBlocksBound = (SIZE + BLOCKSIZE - 1) / BLOCKSIZE + 1;

Fastest way to calculate a number of memory blocks