Dynamic Storage Allocation
|
URI: |
http://herbert.gandraxa.com/herbert/dsa.asp |
|
HTML template: |
<a href="http://herbert.gandraxa.com/herbert/dsa.asp">Dynamic Storage Allocation</a> |
|
Link symbols: |
|
On current page |
On external site |
ZIP archive |
PDF |
E-Mail
Article
Organization
Home »
Linoleum Source Code » Dynamic Storage Allocation
- Source Code Library: The implementation in the cross-platform Assembler Linoleum.
- Source Code Test Program: Test program using the library.
Download as a WinZip file see below.
Scope
This DSA library presents a novel approach in Dynamic Storage Allocation, implemented in the 
Linoleum Programming Language.
The approach is best described as being a Quadruply-linked Dynamic Storage Allocator with AVL tree size-controller.
The main focusses were:
- steady performance, i.e. no sudden long-lasting delays as happen frequently with garbage collectors (this is especially important in game environments, where such delays are not acceptable)
- fragmentation reduction (keeping the dedicated memory area as compact as possible)
Memory chunks are allocated best fit, splits are done only when meaningful. Deallocation includes immediate coalescing and fastest possible return to the memory pool.
An AVL tree acts as a size controller for free chunks. Each AVL node maintains the start and end points of an individual chain linking together free memory chunks of same size. The size itself is a node's key.
Author
External Pages
- Dynamic storage allocation on Wikipedia
- AVL Tree on Wikipedia, by far more detailled on the German Wikipedia though
Outline
From the memory area dedicated to dynamic storage management, the AVL tree acting as the Size-Controller expands and shrinks from one end towards the other [1], maintaining an absolutely fragmentation-free internal organization.
Memory Chunks are memory fragments of any arbitrary size, prefixed by a fix-length header. They use the dedicated space from the other direction. There are two types of chunks: Allocated Chunks, which currently are in use, and Free Chunks, which interrupt a series of allocated chunks.
Free chunks are managed for further re-use. They never can be neighbours: if such a situation arose, the chunks would be coalesced into a single one.
The area between the size-controller and the memory chunks is called the Memory Pool: It exists as long as the size-controller and the chunks do not meet, and it is from there, that memory requests are served, when no free memory chunks can be re-used. When the Memory Pool would become a negative size, i.e. when the size-controller and a new pool allocation would overlap, then the 'out of memory' condition is met.
To reduce management of the size-controller's nodes, deallocated memory chunks bordering the Memory Pool are immediately returned to the latter, along with removing them from their respective size chain, possibly leading to a removal of the managing size node. From this follows, that a free chunk always must be bordered by at least one allocated chunk, namely the one in the direction of the Memory Pool.
[1] In my implementation, published in the DSA Library, the AVL tree grows top-down, the memory chunks bottom-up. If the whole dedicated memory area was designed to be dynamic itself, it would be a better idea to reverse these directions, because the additional memory is always added on top anyway and thus the whole lot of it simply could be declared to be a new free memory chunk. This is likely to be faster, than to move the whole size-controller up to the new top, which requires a loop over its whole current size to maintain its management information.
Download
The following ZIP file contains both the library's source (DSA.txt) as well as a test program (DSA Test.txt).
The other used libraries RNG.txt (Pseudo Random Number Generator) and AVL.txt (AVL Tree) are also included in the ZIP file.
A ready-to-run DSA.exe for Windows comes with the download. Before you run that exe, make sure you know how to operate it. Any key will stop the program, but only if you give it the focus. To give it the focus, set the mouse pointer on its display. You won't see the mouse pointer when doing so. Then click on it. Now any key will end the program. For the interpretation of the registers in the appearing window please read the documentation in the source code. And here the standard disclaimer: there is no liability for any damage possibly being caused by this program.
While you run the exe, the memory is mapped onto the screen. On how to interpret the color codes, read the header of the file DSA Test.txt.
Speed
On an Intel Celeron D 346 wth 3,066 MHz, running Windows 2000 Professional, the library DSA 1.2 provided the following times for large-volume data:
| Run | Number of Alloc/sec | Number of Free/sec |
| 1 | 2,029,608 | 1,554,038 |
| 2 | 1,997,770 | 1,541,060 |
| 3 | 1,981,293 | 1,531,316 |
Test
The library was thoroughly tested in a long-time test with more than 20 billion random allocations and deallocations. No errors occured during that test, all chains were coherently linked and no data corruption was manifest.
Fig. 1: The DSA test visualization in action, after running for 2 hours on a 2.8 GHz Pentium 4. Fragmentation is in blue, with the exception of the bottommost area, which together with the black area below it forms the memory pool. Allocated memory chunks are in yellow, preceded by a chunk header (headers shown as red dots).
