CODEWITHSUNDEEP
cmemory-management
HEKTO
HEKTO

Reputation: 4191

Fastest way to calculate a number of memory blocks

I have a memory region, which is divided in blocks of predefined BLOCKSIZE size. Given a memory chunk, defined by its offset OFFSET in bytes and SIZE in bytes, how to efficiently calculate a number of blocks, containing this memory chunk?

For example, let's say the BLOCKSIZE=8. Then a memory chunk with OFFSET=0 and SIZE=16 will take 2 blocks, but a chunk with OFFSET=4 and SIZE=16 will take 3 blocks.

I can write a formula like this (using integer arithmetics in C):

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

This calculation will take 2 divisions and 4 additions. Can we do better, provided that the BLOCKSIZE is a power of 2 and OFFSET >= 0 and SIZE > 0?

UPDATE: I uderstand that division can be replaced by shifting in this case.

Upvotes: 0

Views: 2441

Answers (1)

John Bollinger
John Bollinger

Reputation: 180430

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

I don't think so. Your (corrected) formula is basically (index of the first block after the chunk) - (index of the first containing any part of the chunk). You could formulate it differently -- say, as the sum of a base number of blocks plus an adjustment for certain layouts that require one extra block -- but that actually increases the number of operations needed by a couple:

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

I don't see any way around performing (at least) two integer divisions (or equivalent bit shifts), because any approach to the calculation requires computing two block counts. These two computations cannot be combined, because each one requires a separate remainder truncation.

That BLOCKSIZE is a power of two may help you choose more efficient operations, but it does not help reduce the number of operations required. However, you could reduce the number of operations slightly if you could rely on SIZE to be a multiple of BLOCKSIZE. In that case, you could do this:

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

Alternatively, if it would be sufficient to compute an upper bound on the number of blocks covered, then you could do this:

numberOfBlocksBound = SIZE / BLOCKSIZE + 2;

or slightly tighter in many cases, but more costly to compute:

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

Upvotes: 2

Related Questions