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?
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).
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.
This is to minimize the number of tiny blocks of memory that are too small to use for anything but need to be walked when the program allocates or deallocates memory. A classic explanation from Joel Spolsky’s blog, all the way back in 2001:
Smart programmers minimize the potential distruption of malloc by always allocating blocks of memory that are powers of 2 in size. You know, 4 bytes, 8 bytes, 16 bytes, 18446744073709551616 bytes, etc. For reasons that should be intuitive to anyone who plays with Lego, this minimizes the amount of weird fragmentation that goes on in the free chain. Although it may seem like this wastes space, it is also easy to see how it never wastes more than 50% of the space. So your program uses no more than twice as much memory as it needs to, which is not that big a deal.
There were plenty of other discussions of memory-heap implementations before then, including by Donald Knuth in The Art of Computer Programming. Not everyone will necessarily agree with that advice, but that is why people do it.
The system itself uses powers of 2 to set various limits. For example maximum allocation for the length of file name can be 256, or 32768. Disk page size is powers of 2, etc.
We often have to keep these system restrictions in mind, and use the same powers of 2.
But if you only need 257 bytes, don't over allocate 512 bytes. Some programmers use powers of 2 to set limits for user input. This can be confusing to the user. It had some benefits in older computers, but not now.
Other times we use allocations which are randomly large. For example we might use 1000 or 1024 to read one line of text, because we don't know how long the input is. This is bad programming either way. It really doesn't matter if allocation is 1000 or 1024 in this case.
I doubt there is much reason to do this on desktop-class computers any more. For embedded devices where there are more extreme memory and performance limitations then powers of two can allow some extra optimisations.
Often operations such as multiplication are expensive on these devices, so replacing multiplication with bit shifts is an easy way to gain extra performance. Bounds checking can also be ignored in some cases, such as when an 8 bit index is used on an array of size 256.
