User:Pancakes/SimpleHeapImplementation: Difference between revisions
m (fixed missing landmark to break the reader for a new section) |
m (added new implementation link for linked list bucket) |
||
| Line 26: | Line 26: | ||
|- |
|- |
||
| [[User:Pancakes/BitmapHeapImplementation|Bitmap Based]] |
| [[User:Pancakes/BitmapHeapImplementation|Bitmap Based]] |
||
| A very simple and decently performing implementation. |
|||
| ''(Simple, Good Performance, More Tolerant To Buffer Overflows, Aligned Data, Good For Lots Of Small Allocations)'' A bitmap based heap implementation. |
|||
|- |
|- |
||
| [[User:Pancakes/EntryBasedHeapImplementation|Entry Based]] |
| [[User:Pancakes/EntryBasedHeapImplementation|Entry Based]] |
||
| Not very good but shows an alternative way. |
|||
| ''(More Complex, Easier To Corrupt, Unaligned Data, Good For Very Large Allocations, Could Be More Space Efficient In Certain Situations)'' A entry based heap implementation. |
|||
|- |
|- |
||
| [[User:Pancakes/StackBasedHeapImplementation|Stack Based]] |
| [[User:Pancakes/StackBasedHeapImplementation|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. |
|||
| ''(Simple, Aligned Data, Fast, Static Allocation Size)'' A stack based heap implementation. |
|||
|- |
|- |
||
| [[User:Pancakes/BitmapHeapImplementationEnhanced|Bitmap Based With Enhanced Functionality]] |
| [[User:Pancakes/BitmapHeapImplementationEnhanced|Bitmap Based With Enhanced Functionality]] |
||
| |
| The bitmap implementation but supports managing physical memory and provides data aligned on arbitrary boundaries. |
||
|- |
|||
| [[User:mrvn/LinkedListBucketHeapImplementation|Linked List Bucket Heap]] |
|||
| A very fast general purpose allocator. It can work well with large or small allocations. |
|||
|} |
|} |
||
==== Performance ==== |
==== Performance ==== |
||
I am having to retest all the implementations and will update this section soon. |
|||
I have run some performance numbers. Keep in mind these can vary from system to system and could be wrong. These were just the best I could make of the them. There are a lot of factors that can influence the outcome of the numbers during the tests. But, these numbers I hope are close to what you can expect. |
|||
This is the code for each implementation: |
|||
<pre> |
|||
bm - bitmap based |
|||
sc - standard C |
|||
eb - entry based |
|||
sb - stack based |
|||
</pre> |
|||
''The ratios compare each implementation to the baseline standard C malloc and free calls. By taking the average time and dividing the implementation time into it resulting in a higher number if the average time was lower. So 1.57 means it was 157% faster than the standard C library. The left number is the alloc and the right number is the free.'' |
|||
This run was done randomly allocating and deallocating 1 to 16 bytes each time. This seemed fair since it includes the stack based implementation which has a fixed allocation size for the test set at 16 bytes. |
|||
<pre> |
|||
-----average times (lower better)------ |
|||
bm: 1055.7440821 1061.90860596 |
|||
sc: 1652.65433041 1869.73612079 |
|||
eb: 3797.06639644 2290.6665103 |
|||
sb: 973.836174458 719.019672573 |
|||
------ratio (higher is faster)------ |
|||
bm: 1.57 1.76 |
|||
eb: 0.44 0.82 |
|||
sb: 1.70 2.60 |
|||
</pre> |
|||
This run was done randomly allocating and deallocating 1 to 1024 bytes each time. The stack based |
|||
implementation is not included because it supports only a fixed allocation size. |
|||
<pre> |
|||
-----average times (lower better)------ |
|||
bm: 4057 3237 |
|||
sc: 5957 3793 |
|||
eb: 8675 7544 |
|||
------ratio (higher is faster)------ |
|||
bm: 1.47 1.17 |
|||
eb: 0.69 0.50 |
|||
</pre> |
|||
<strike>I honestly find the numbers odd. I think the stack based should have been a lot faster and I find that the bitmap being slower for freeing allocations is also odd, but it could be correct. I will continue to work on trying different testing methods and update as I can.</strike> |
|||
I found that GCC was not to optimize a loop in the bitmap ''free' method. Once this was corrected it was then faster than the standard run-time. |
|||
Revision as of 20:05, 6 May 2014
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 kmcg3413@gmail.com.
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
I am having to retest all the implementations and will update this section soon.