Monthly Archives: April 2010

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! 🙂

Purify it !

What a wierd title. Or may be not. Depending of your experience, you may or may not know these life-saver tools, when strange things happen to your program and you have absolutely no clue about what the hell is going on. No starting point to look at. It sometimes happens, sometimes not, as if the computer was an organic lifeform. Here enters purify like programs (‘valgrind’ on linux, ‘purify’ or ‘bound checker’ on Windows) , which adds realtime checks around almost every kind dynamically allocated memory block to detect the root of evils: buffer overflows.

You may think: “well that’s cool but i use PureBasic, and barely never dynamically allocated memory block, as all is managed by natives libraries”. You are right. But may be you use pointers, or even OS calls. And this is where things got a bit more complicated, as pointers is the ultimate power in programming. And as all power, it has to be used wisely. Are don’t get me wrong: you will use them wisely. Until something is changed in your code which impacts that and suddenly the pointer gets crazy, without any notification. On a big program, it could be very long to isolate the bug. I have some ‘souvenirs’ of very vicious cases which took me several days to fix. And as PureBasic executables uses a custom debugger format, it is not compatiable with any of the purifier tools. Too bad. Until now.

Before going further in the details, let’s try to really understand how a purifier works. Basically, it puts ‘cookies’ around every potientally dangerous code items: variables, arrays, strings, dynamically allocated memory block. What’s a cookie ? It’s just a predefined value (usually 32 bits), often something funny like $BADBEEF or $BADF00D. At every executed line, the purifier (which holds a list of all the installed cookies address) will check them, and if one is broken will stop. That means than something has erased this area which should never have been erased. Ever. That’s a bit like a code integrity check. As we could imagine, the bigger your program is, the slower the purifier will be. And it can be very very slow, that’s why it’s possible to tune it to check only some kind of data, and at which rate.

Consider this code:

Procedure a()

a.l = 10

*CrazyPointer.Long = @a
*CrazyPointer+1
*CrazyPointer\l = 152  ; stack corruption

EndProcedure
a()

This is an obvious error. But it does go unnoticed when running in standard release/debug mode. On some more retricrive OS, it could even crash. If you activate the purifier it catch it immediately and report a stack corruption. Let’s try another less obvious one:

*LocalDrive = AllocateMemory(#MAX_PATH)
GetModuleFileName_(0, *LocalDrive, #MAX_PATH)

This snippet uses Windows API, and get back the executable name. So far so good. Now what happen if you change the program mode from ASCII to Unicode ? You end up with a buffer which is twice smaller as requested, and chances are high than you will be hit with a nasty buffer overflow. Again the purifier will detect it as the ‘cookie’ put at the end of the allocated memory block will be overwritten.

And there is quite some cases where it can happen: a structure too small to recieve the expected data, wrong associated structure to a pointer, pointer manipulation error, wrong API call, etc. For most of them, the purifier will catch the error. There are some limitations tough: threaded program could report wrong line and  if a pointer is really filled with a random value, it won’t be noticed by it (but probably by the debugger as IMA – Invalid Memory Access).

The purifier is now available in PureBasic 4.50 !

PureBasic 4.50 Beta 1 released!

Hello everybody!

… this is not an april fools joke… or is it? 😛

We are proud to announce the first public beta of the upcoming PureBasic 4.50 release. As promised, the release cycle is much shorter than that of the 4.40 release which means that also the feature list is shorter. Nontheless, some long requested features have been implemented in this release which we hope you will enjoy very much.

The most notable are:

  • Support for Array, List and Map in structures:  These can be nested as much as you want, so you can have a Map-in-List-in-List if you want to. There is no need to call NewList, NewMap or Dim on these elements. They are created as soon as the outer structure is created. Dim can of course still be used to change the size of a dynamic array. Arrays inside structures can only have one dimension for the moment. The debugger has full support for this too. Embedded Arrays, Lists or Maps can be easily viewed by right-clicking on them in the Variable Viewer.
  • Image Library changes: We decided to abandon the support for images with depths below 24bit. Support for images with a palette was Windows-only anyway and had quite a number of bugs as well. The library now stores images internally only in 24bit or 32bit format which makes things a lot simpler. Images can still be loaded (and now also saved) at lower bit depth, so you can still work with them if you need to.
  • IDE Improvements:  The ability to select the used compiler in the compiler options allows to easily switch between different versions from the same IDE. It also allows to easily build and debug 32bit and 64bit applications from one IDE. Furthermore, some longer requested options like keyword sensitive indentation and indent guides have been added.
  • Debugger improvements: There is a brand new ‘Purifier’ tool in the debugger. It adds special ‘cookie’ values around variables, strings and allocated memory blocks to detect when the program accidentally writes past its intended target buffer. As this requires support from the compiler, it has to be activated in the compiler options to be available in the debugger. Furthermore, the already discussed network support and data breakpoints are now available.
  • Up to date documentation:  The english help file has already been updated with all documentation for these new features. The other languages will follow in the final release.

The feature list:

PureBasic 4.50 Beta 1
- Added support for Array, List, Map inside structures
- Added CopyList(), CopyMap(), CopyArray() commands
- Added FreeList(), FreeMap(), FreeArray() commands
- Added CopyStructure() and InitializeStructure() commands
- Added volume support to PlaySournd()
- Changed: The Image library now keeps images only in 24bit or 32bit (loading and saving works with other bit depths)
- Added Depth parameter to SaveImages()  (default is the original depth when the image was loaded)
- Added ImageDepth() flag to get the original or current image depth
- Added #PB_Image_Transparent flag for CreateImage()
- Added 32bit support to TGA image decoder
- Added 32bit support to BMP image encoder
- Added RoundRect() command to the 2DDrawing library
- Added #PB_2DDrawing_AllChannels mode for DrawingMode() (modifies all channels without blending)
- Added image support for the ComboBoxGadget command (not supported for editable ComboBox on Mac OSX)
- Added AbortFTPFile()
- Added graphical console functions to linux
- Added large file support to File lib on Linux/OSX
- Added RandomData() command
- Added CryptRandom(), CryptRandomData(), OpenCryptRandom(), CloseCryptRandom() commands
- Added many more Math functions: Exp(), ATan2(), Radian(), Degree(), [A]CosH(), [A]SinH(), [A]TanH(), IsNaN(), IsInfinity(), NaN(), Infinity()
- Added 'Debugger' Library to control some debugger actions from code

IDE/Debugger:
- Added Keyword underline for Break, Continue, ProcedureReturn
- Added StatusBar help for prototypes and interfaces
- Added Keyword sensitive indentation (block mode is still available)
- Added "Format indentation" option in the edit menu
- Added indentation guides and whitespace options
- Added the ability to select multiple compilers in the compiler options
- Added Purifier tool for the debugger
- Added full debugger compatibility between all OS and processors
- Added network debugging for the standalone debugger
- Added data breakpoints for the debugger
- Added maximize button to Variable-, Memory-, Library Viewer and Callstack
- Added support for structured items in the 'View Array/List/Map' tab of the Variable Viewer
- Changed: The Array, List or Map name in the Variable viewer should be entered with a "()" now to display their elements.
       (It is automatically corrected if the () is missing)

As always thank you to everyone who helps test these beta versions and reports bugs. Have fun with this new version and tell us any problems that you have. As usual, this version can be downloaded on your personal account on http://www.purebasic.com/

Oh, and Happy Birthday Fred!  :mrgreen:

The PureBasic Team