C: Why allocate string length in powers of 2?

Question

Why do C programmers often allocate strings (char arrays) in powers of two?

You often see...

char str[128]
char str[512]
char str[2048]

Less often, you see...

char str[100]
char str[500]
char str[2000]

Why is that?

I understand the answer will involve memory being addressed in binary... But why don't we often see char str[384], which is 128+256 (multiple of two).

Why are multiples of two not used? Why do C programmers use powers of two?

Answer 1

There is no good reason for it anymore except for some very rare cases.

To debunk the most common argument: It helps the memory allocator to avoid fragmentation.

Most often it will not. If you allocate - lets say - 256 bytes the memory allocator will add some additional space for it's internal management and house-keeping. So your allocation is internally larger. Two 256 buffers have the same size as a 512 byte buffer? Not true.

For peformance it is may even doing harm because how the CPU caches work.

Lets say you need N buffers of some size you may declare them this way:

char buffer[N][256];

Now each buffer[0] to buffer[N-1] have identical least significant bits in their address, and these bits are used to allocate cache-lines. The first bytes of your buffers all occupy the same place in your CPU cache.

If you do calculations of the first few bytes of each buffer over and over again you won't see much acceleration from your first level cache.

If on the other hand you would declare them like this:

char buffer[N][300];

The individual buffers don't have identical least significant bits in the address and the first level cache can fully use it.

Lots of people have already run into this issue, for example see this question here: Matrix multiplication: Small difference in matrix size, large difference in timings

There are a few legitimate use-cases for power-of-two buffer sizes. If you write your own memory allocator for example you want to manage your raw memory in sizes equal to the operation system page size. Or you may have hardware constraints that force you to use power-of-two numbers (GPU textures etc).

Answer 2

An interesting question. Blocks of sizes 2^k fits better when OS memory management uses Buddy memory allocation technique. This technique deals with fragmentation of allocations. https://en.wikipedia.org/wiki/Buddy_memory_allocation

This allocation system does alignment of block to size power of 2. But this is used for heap allocation.

int * array = (int*) malloc(sizeof(int)*512); // OS manages heap memory allocation

When buffer is allocated on stack, there is no needs to make block alignment.

int buffer[512]; // stack allocation

I think no reason to make sizes of powers of 2.