10

15 years ago, while programming with Pascal, I understood why to use power of two's for memory allocation. But this still seems to be state-of-the-art.

C# Examples:

new StringBuilder(256);
new byte[1024];
int bufferSize = 1 << 12;

I still see this thousands of times, I use this myself and I'm still questioning:

Do we need this in modern programming languages and modern hardware?
I guess its good practice, but what's the reason?

EDIT
For example a byte[] array, as stated by answers here, a power of 2 will make no sense: the array itself will use 16 bytes (?), so does it make sense to use 240 (=256-16) for the size to fit a total of 256 bytes?

joe
  • 8,344
  • 9
  • 54
  • 80
  • Because the CPU work binary, memory blocks (pages) are 2^n size (why waste half memblocks) and those are easy to index. See more here: http://en.wikipedia.org/wiki/Computer_number_format and here: https://en.wikipedia.org/wiki/Page_(computer_memory) – Jeroen van Langen Aug 13 '13 at 06:13
  • 1
    I think most is to show off... You can't really know what exact buffer size is allocated for complex class (`Dictionary` or even `List` or `StringBuilder`), for byte arrays it somewhat makes sense as Jack explained. – Alexei Levenkov Aug 13 '13 at 06:26

5 Answers5

4

Do we need this in modern programming languages and modern hardware? I guess its good practice, but what's the reason?

It depends. There are two things to consider here:

  1. For sizes less than the memory page size, there's no appreciable difference between a power-of-two and an arbitrary number to allocate space;
  2. You mostly use managed data structures with C#, so you won't even know how many bytes are really allocated underneath.

Assuming you're doing low-level allocation with malloc(), using multiples of the page size would be considered a good idea, i.e. 4096 or 8192; this is because it allows for more efficient memory management.

My advice would be to just allocate what you need and let C# handle the memory management and allocation for you.

Ja͢ck
  • 170,779
  • 38
  • 263
  • 309
  • 1
    Page size is irrelevant. You are neglecting to account for sub-allocation and memory block meta data. – David Heffernan Aug 13 '13 at 07:56
  • @DavidHeffernan All the more reason to not bother using 2^n sizes at all, is that what you're saying? – Ja͢ck Aug 13 '13 at 07:58
  • @DavidHeffernan I've reworded it a little to talk specifically about lower-level allocation. – Ja͢ck Aug 13 '13 at 08:10
  • @Jack: Many good point here, thanks! When thinking about memory defragmentation by the GC, this makes even more sense. – joe Aug 16 '13 at 19:23
2

Sadly, it's quite stupid if you want to keep a block of memory in a single memory page of 4k... And persons don't even know it :-) (I didn't until 10 minutes ago... I only had an hunch)... An example... It's unsafe code and implementation dependant (using .NET 4.5 at 32/64 bits)

byte[] arr = new byte[4096];

fixed (byte* p = arr)
{
    int size = ((int*)p)[IntPtr.Size == 4 ? -1 : -2];
}

So the CLR has allocated at least 4096 + (1 or 2) sizeof(int)... So it has gone over one 4k memory page. This is logical... It has to keep the size of the array somewhere, and keeping it together with the array is the most intelligent thing (for those that know what Pascal Strings and BSTR are, yes, it's the same principle)

I'll add that all the objects in .NET have a syncblck number and a RuntimeType... They are at least int if not IntPtr, so a total of between 8 and 16 bytes/object (This is explained in various places... try looking for .net object header if you are interested)

xanatos
  • 109,618
  • 12
  • 197
  • 280
1

It still makes sense in certain cases, but I would prefer to analyze case-by-case whether I need that kind of specification or not, rather than blindly use it as good practice.

For example, there might be cases where you want to use exactly 8 bits of information (1 byte) to address a table.

In that case, I would let the table have the size of 2^8.

Object table = new Object[256];

By this, you will be able to address any object of the table using only one byte.

Even if the table is actually smaller and doesn't use all 256 places, you still have the guarantee of bidirectional mapping from table to index and from index to table, which could prevent errors that would appear, for example, if you had:

Object table = new Object[100];

And then someone (probably someone else) accesses it with a byte value out of table's range.

Maybe this kind of bijective behavior could be good, maybe you could have other ways to guarantee your constraints.

Probably, given the increase in smartness of current compilers, it is not the only good practice anymore.

Lake
  • 4,072
  • 26
  • 36
0

IMHO, anything ending in exact power of two's arithmeric operation is like a fast track. low level arithmeric operation for power of two takes less number of turns and bit manipulations than any other numbers need extra work for cpu.

And found this possible duplicate:Is it better to allocate memory in the power of two?

Community
  • 1
  • 1
swcraft
  • 2,014
  • 3
  • 22
  • 43
  • 1. Power of two usually evaluated at compile time. 2. Compilers can optimise to shift if it is indeed faster. 3. Memory allocation orders of magnitude more expensive than arithmetic, so this so called efficiency could never be measured. – David Heffernan Aug 13 '13 at 07:59
  • based on what you saying, it could be little overhead to compiler but never to runtime.. I think that's true for specific language but only for that sophisticated compilers. I guess your answer is precise this case since this thread is for C# – swcraft Aug 13 '13 at 17:59
0

Yes, it's good practice, and it has at least one reason. The modern processors have L1 cache-line size 64 bytes, and if you will use buffer size as 2^n (for example 1024, 4096,..), you will take fully cache-line, without wasted space. In some cases, this will help prevent false sharing problem (http://en.wikipedia.org/wiki/False_sharing).

oakio
  • 1,868
  • 1
  • 14
  • 21