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

Question

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

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

我可以写出这样的公式(使用 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?

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

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

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

BLOCKSIZE 是 2 的幂可能有助于您选择更高效的操作，但它无助于减少所需操作的数量。但是，如果您可以将 SIZE 设为 BLOCKSIZE 的倍数，则可以稍微减少操作数。在这种情况下，您可以这样做:

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

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

numberOfBlocksBound = SIZE / BLOCKSIZE + 2;

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

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