The cost of empty lists

So now we have the ability to embed lists, maps and arrays inside structures. Its a very useful feature and we can already see people building crazy data structures with all sorts of nesting in them, even tree like structures. I want to talk a little bit about the costs associated with these objects. The fact is, even empty lists or maps take up memory and if you create a lot of them, you should be aware of that. The sizes i give below are all for the x86 versions (so 4 bytes per pointer). For x64, you can usually double that. Not all fields are actually pointer sized, so it is less than that in reality, but it is a good approximation.  My base scenario is an array of a structure type with an embedded list. However, this applies to all other combinations as well.

Structure MyStruct
  Something.i
  List Elements.s()
EndStructure

Dim Table.MyStruct(99)
Automatic initialization on creation

First of all, its important to realize that structure content is automatically initialized on creation. This means that if you create a structured variable with an embedded list, you don’t have to call NewList in order to use the embedded list. However, this also means that simply by the process of creating the structured variable, you also created a (still empty) list which takes up some memory. The same thing applies to my example array: By creating the array with 100 elements (0-99), i also created 100 empty lists.

You could say this is a waste of memory, and you would not be entirely wrong. After all, if not all elements of this array are actually used to store data, that is a lot of unused memory. We discussed this at length when implementing the feature. An alternative approach would have been to leave all such dynamic elements uninitialized on creation and require the user to explicitly call NewList before using them in each element. This would conserve memory when not all array elements are intended to have items in their lists, but it puts the burden to ensure that all dynamic elements are initialized before they are accessed on the user and introduces a whole new source for bugs. Its also extra work for the user considering that if people define such a structure they intend to put things into it, and forcing them to do an extra initialization step each time when PB can easily do it for them is just wasting the programmer’s energy.

So in the interest of having a really easy to use feature we decided to go with automatic initialization. After all, if you really need the full control and do not shy away from some extra work then building your own linked data structures in memory is not that hard. If you want something simple that just works, then this feature is for you. Of course its never wrong to know about the costs so you know what happens when your data set gets large.

Memory usage

How much memory does an empty list take? Aside from the actual space it takes up inside the structure which is 2 pointers for a list (1 pointer for array and map), there is a header structure which is allocated as well. It stores information about the list such as its type (for sorting and cleanup), the pointers to the first and last element in the list as well as cached index information for a fast SelectElement() if possible. The list header is currently 48 bytes on x86. As described in another entry, we also have custom memory allocation for list elements for faster allocation/freeing of memory. These allocation routines also take up 24 bytes of header data per list.

So in my list in array example above i have created 100*12 bytes of actual element data in the array plus another 100*72 bytes for empty lists. While this extra data is still not very much, it is considerably more than the array element data itself, so it will become an issue if you make your array very large. If you knew for example that you will never have more than 18 elements in the embedded list, then you could replace the thing with a static array inside the structure with 18 elements and still have the same memory usage.

Empty maps have a much larger impact. They also come with a header and an allocator header, but an empty map also reserves space for its hash table even if there are no elements in it. The default table size is 512 entries, so that is another 2048 bytes for an empty map on x86.

Arrays are a little different as you can declare inside the structure how many elements it should have on creation. Arrays also come with a header, but nothing else. Here its more important to keep in mind that if the elements of the embedded array in turn contain embedded lists, maps or arrays that you have to take their costs into account as well as they will be initialized too when the embedded array is created.

One final thing to keep in mind is that lists and maps actually allocate the memory for their elements in blocks of 16 elements minimum (for speed and to reduce fragmentation), if you create many lists with just a few elements in them (say 2 per list for a binary tree structure), you end up with used memory of 16 elements per list instead. Note though that this is just allocation, not initialization. The used memory will be only for the 16 elements themselves, not for any contained dynamic list, map or array they may contain.

Bottom line

This post should be seen in the right context. The cost of the embedded object may seem large compared to the size of the structure they are put in, but that doesn’t change the fact that they are still very cheap objects. Lists, maps and arrays are all memory-only objects. This means that all they need is memory, no handles, no system objects, nothing else. Memory is not much of a concern these days, so you can create many of them and even create/destroy them frequently. This really isn’t a problem. Take my above array example: Even if we Dim the array to 10000 elements, we still only used up 820Kb of memory which is not much by today’s standards.

The only place where you really need to concern yourself with this is if your data sets get really large and memory does become an issue. In this case the advice is simple: Avoid “sparse” data structures where a large part of the dynamic elements are allocated but not used. You can also call FreeList(), FreeMap(), FreeArray() or ClearStructure() on any element you do not need. You then have to re-initialize it if you want to use it later with NewList, NewMap, Dim or InitializeStructure() respectively.

Always keep in mind the quote from Donald Knuth on optimization:

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified.

In this context, this means not to worry about this issue when designing your data structures. Do not get tempted to optimize away a few bytes of extra memory with funny tricks. A clear and simple layout of the data in your program is worth much more than that (and will save you many headaches from chasing bugs). Only if you see that your program really has a memory problem is it time to start thinking of ways to cut down on overhead like this.

In this spirit, have fun designing crazy nested data structures with the new dynamic elements! 🙂

Leave a Reply