The Old Joel on Software Forum: Part 3 (of 5)

Lego intuition?

I was rereading Joel's "Back to Basics" post, and got stuck fixating on this statement:

"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."

Despite having played with Legos in my youth and following the rest of the article, I couldn't figure out why allocating in powers of two would minimize fragmentation, or what the connection to Legos might be. Any clues?

Sam Livingston-Gray
Tuesday, December 9, 2003

If you build a wall with legos of different lengths you get more holes if you are using bricks of length 6 and 3 than if you have bricks of lengths 2 4 8.

Dennis Atkins
Tuesday, December 9, 2003

Er, 6 and 3 in addition to the common 2 and 4s and rarer 8s.

Dennis Atkins
Tuesday, December 9, 2003

I'm still not quite sure I follow. If you build a wall with bricks of different lengths, you can make one end of the wall line up perfectly because you start over again when you "wrap" the line of Legos, and all the "holes" will be on the other end.

However, isn't memory effectively one-dimensional?

(rereads article) Oh, I see. malloc's free chain is a "linked list of available blocks," hence the wall of Legos. Thanks!

Sam Livingston-Gray
Wednesday, December 10, 2003

The plural of Lego is Lego.

Play Well
Wednesday, December 10, 2003

Should hairsplitting be hyphenated?

John Ridout
Wednesday, December 10, 2003

Yes. Should accuracy and attention to detail be mandatory for programmers?

Play Well
Wednesday, December 10, 2003

Must a surgeon cut the crusts off his sandwiches using a scalpal?

Ged Byrne
Wednesday, December 10, 2003

Practice makes perfect.

Play Well
Wednesday, December 10, 2003

Tut tut, how imprecisie.

Practices tends towards perfection.

Perfection itself cannot be obtained.

Ged Byrne
Wednesday, December 10, 2003

"Practices tends"...?

Play Well
Wednesday, December 10, 2003

That's more pedantry than hairsplitting.

John Ridout
Wednesday, December 10, 2003

Let me get this straight. I don't take any flak for failing to understand how malloc works, but my ignorance of the correct plural form of a trademark means I'm a bad programmer? (=

Sam Livingston-Gray
Wednesday, December 10, 2003

Hey - Leggo my Lego !

Kentasy
Wednesday, December 10, 2003

Sam, how can you possibly expect to understand how malloc works if you can't even master the plural of Lego?

<g, d & r>

Play Well
Wednesday, December 10, 2003

I think you will find that LEGO is a brand name and should be written capitals. LEGO (the company) does not refer to LEGOs only to LEGO bricks and LEGO elements. ;-)

John Ridout
Wednesday, December 10, 2003

Joel seems to be making some assumptions about
the way the heap is managed that may be far from the truth on some platforms. For instance, suppose your platform's malloc uses one extra word on the end[1] of each allocated block for bookkeeping. Then always requesting blocks of power-of-2 sizes will be equivalent to requesting power-of-2-plus-1 sizes using a malloc that doesn't need that overhead. That's not going to be so good for the fragmentation.

[1] Well, actually, before the beginning would make more sense.

The point about powers of 2 is, I assume, that if you have two adjacent blocks whose size is the same power of 2 then you can merge them to get a new power-of-2 block.

If you care enough about how memory allocation works for you to go rounding your blocks up to the next power of 2 (or something like that) then you should also care enough to *measure* and only do it if it helps. Which it may do, on some platforms and for some programs -- but it is unlikely to do so on all. Rounding up to the next power of 2 means, on average, something like 50% *internal* fragmentation from that source alone, on top of anything else imposed by the implementation. A good malloc implementation might have between 1% and 25% *total* (internal and external) fragmentation on typical workloads. That tradeoff doesn't look so good.

(See http://citeseer.nj.nec.com/wilson95dynamic.html and
http://citeseer.nj.nec.com/johnstone97memory.html for more about achievable levels of fragmentation.)

Gareth McCaughan
Wednesday, December 10, 2003

Like Gareth said, an extra block is added, so Joel's recommendation isn't perfect if the free list is a linked list. Typically blocks are allocated in multiples of 8 bytes. So it might make more sense to do something like this:

if(N*sizeof(datatype)%8 > 0)
datatype *dt = malloc(N*sizeof(datatype);
else
datatype *dt = malloc((N+1)*sizeof(datatype));

Another popular implementation is segmented storage. With segmented storage, a number of free lists are keep, with the blocks in each allocated in powers of 2. So if you malloc(1000) it will search the 1024 list for a free range of memory.

Memory allocation / deallocation gets fairly complicated, so I don't even try to match allocation size to what I think the allocator will do. However, when using an array that will grow, I agree with his advice to always double the size when reallocating.

Nick
Wednesday, December 10, 2003

Joel really should stop giving that sort of advice. This makes at least three times where he gives patently wrong information in one of his feature articles. His true strength is in project management, not the low level technical nuts and bolts stuff. The fact that he is an excellent writer doesn't make his writings accurate.

Memory managment and allocators is a much researched and written about problem domain. There are many different style allocators, some are optimized for speed, some for minimal memory overhead. Unless you know exactly what its optimized for, its foolish to try make it more efficient by allocating more memory than needed. Even then I don't recommend it, as I explain later.

Always allocate the amount of memory you need, don't pad it with any arbitrary amount because you think you are doing the Memory Manager a favor. Typically MMs are very good about allocating any padding as needed to avoid fragmentation, and padding it yourself is simply a waste of time (both yours and the machine's) and memory (just the machine's).

Frequently what can happen is that a stock MM will be optimized for the general case (allocations of varying sizes, held for varying amounts of time), but start to fall down if the allocations are more extreme (i.e. many small short lived allocations, many large but long lived allocations). If you ever find yourself in this situation, its often easier to replace the whole MM with one that is optimized for your constraints rather than change around all your code. If you've made the mistake of allocating extra padding because you think the MM likes it, then when you switch MMs you may have to go and find all those places and change them back to benefit the new MM.

DKatz
Wednesday, December 10, 2003

Source code for the MSVC run time library (malloc.c) seems to include this statement ...

/* round requested size */
size = _ROUND2(size, _GRANULARITY);

Similarly, the std::vector<>::insert method is willing to double the vector's buffer when it needs to grow.

Given that library writers implement the kind of thing that Joel mentioned, I wouldn't recommend that you write it into application-level code.

Christopher Wells
Thursday, December 11, 2003