User:Pancakes/SimpleHeapImplementation
Simple Heap Implementation
There are a few simple heap implementations for you to examine. I want to come back and write a little tutorial on each page to kind of walk the reader through how they work.
If you want to copy them straight out and use them in your kernel then that is fine. I put these up here so someone who might not be that interested in implementing a heap can get it done and move on to better things.
The bitmap implementation has been fairly well optimized. I can not find any major performance improvements to make. It still needs some optimization for multiple blocks such as moving full blocks to the end of the linked list maybe. Also, the entry could perhaps use a double chain where one chain links free entries and the other links used entries therefore making allocation quicker. At the moment it just jumps through all of them. Also, deallocation could be faster on the entry implementation.
I have tested both implementations quite well for corruption internally, and checked a 32-bit block at the beginning and end of the blocks for under or over runs and so far have found no corruption even after a long period of running.
If you find any bugs, problems, or have success using them just let me know at [email protected].
Simulation
I wrote a page that lets you simulate a bitmap heap with a view of memory and play back of memory accesses. It relates directly to the bitmap algorithm except it uses only 16-bit fields. You can find it at http://kmcg3413.net/jsbmheap.htm. It also contains a link back to the bitmap implementation page so you can reference the actual code and structures.
Implementations
These are the implementations. I recommend the bitmap because of it's reliability, decent performance, simplicity, and small code size make it a very attractive choice for a beginning heap.
| Page | Brief Description |
|---|---|
| Bitmap Based | A very simple and decently performing implementation. |
| Entry Based | Not very good but shows an alternative way. |
| Stack Based | Very fast but only supports one block size, and if data is smaller it wastes memory depending on stack entry size. Could be chained together to provide different sizes like a SLAB allocator. |
| Bitmap Based With Enhanced Functionality | The bitmap implementation but supports managing physical memory and provides data aligned on arbitrary boundaries. |
| Linked List Bucket Heap | A very fast general purpose allocator. It can work well with large or small allocations. |
Performance
The Enhanced Bitmap is noted as bm in green, and was initialized with 16-byte blocks. The Linked List Bucket Heap is noted as mrvn and is shown in light red. As you can see the performance of the bitmap implementation decreases as allocation size increases. The darkish purple is the entry based. The numbers across the bottom denote maximum allocation size. For example 256 means allocations were between 1 and 256 while 4096 means allocations where between 1 byte and 4096 bytes. Each implementation was run for a lengthy period of time and had allocations and frees made randomly. Each implementation was allowed to use more memory if it ran out.
The Linked List Bucket Heap is a great generic heap, but it is slightly more complicated and a little harder to follow code wise. The bitmap heap also consumes significant memory by meta-data of it's bitmap tables, but code wise is fairly straight forward and simple.
The numbers represent the speed gain compared with the standard malloc and free provided by my C library on the machine I produced these numbers on. It represents how many times faster, and it combines the speed of both malloc and free for an overall speed. Some implements have ultra fast free like entry based and bitmap which beat all others, but their initial allocation speed is just too slow to make them fast.