User:Pancakes/SimpleHeapImplementation: Difference between revisions
m added new times and note about fix the bitmap free routine |
added correct graph |
||
| (8 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== Simple Heap Implementation == |
== Simple Heap Implementation == |
||
There are |
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. |
write a little tutorial on each page to kind of walk the reader through how they work. |
||
| Line 12: | Line 12: | ||
''If you find any bugs, problems, or have success using them just let me know at [mailto:kmcg3413@gmail.com kmcg3413@gmail.com].'' |
''If you find any bugs, problems, or have success using them just let me know at [mailto:kmcg3413@gmail.com 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 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. |
|||
{| class="wikitable" |
{| class="wikitable" |
||
| Line 19: | 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]] |
|||
| 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 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. |
|||
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. |
|||
This is the code for each implementation: |
|||
<pre> |
|||
bm - bitmap based |
|||
sc - standard C |
|||
eb - entry based |
|||
sb - stack based |
|||
</pre> |
|||
<html><body><svg height="300" width="700"> |
|||
''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.'' |
|||
<text style="font-size: 8pt;" x="0" y="271.4770860505417" fill="rgb(0,0,0)">eb</text> |
|||
<text style="font-size: 8pt;" x="0" y="260.5681727301949" fill="rgb(0,0,0)">bm</text> |
|||
<text style="font-size: 8pt;" x="0" y="201.04345987460465" fill="rgb(0,0,0)">sb</text> |
|||
<text style="font-size: 8pt;" x="0" y="238.8811744121518" fill="rgb(0,0,0)">mrvn</text> |
|||
<line x1="40" y1="271.4770860505417" x2="39.0" y2="271.4770860505417" style="stroke:rgb(153,0,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="40" y="271.4770860505417" fill="rgb(153,0,255)">0.3</text> |
|||
<line x1="40" y1="260.5681727301949" x2="39.0" y2="260.5681727301949" style="stroke:rgb(153,255,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="40" y="260.5681727301949" fill="rgb(153,255,153)">0.4</text> |
|||
<line x1="40" y1="201.04345987460465" x2="39.0" y2="201.04345987460465" style="stroke:rgb(0,255,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="40" y="201.04345987460465" fill="rgb(0,255,255)">1.1</text> |
|||
<line x1="40" y1="238.8811744121518" x2="39.0" y2="238.8811744121518" style="stroke:rgb(255,153,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="40" y="238.8811744121518" fill="rgb(255,153,153)">0.7</text> |
|||
<text style="font-size: 8pt;" x="40" y="300" fill="rgb(0,0,0)">16</text> |
|||
<line x1="80" y1="271.59097505774" x2="40" y2="271.4770860505417" style="stroke:rgb(153,0,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="80" y="271.59097505774" fill="rgb(153,0,255)">0.3</text> |
|||
<line x1="80" y1="266.1457872407004" x2="40" y2="260.5681727301949" style="stroke:rgb(153,255,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="80" y="266.1457872407004" fill="rgb(153,255,153)">0.3</text> |
|||
<line x1="80" y1="197.9335788586706" x2="40" y2="201.04345987460465" style="stroke:rgb(0,255,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="80" y="197.9335788586706" fill="rgb(0,255,255)">1.1</text> |
|||
<line x1="80" y1="243.85223645946513" x2="40" y2="238.8811744121518" style="stroke:rgb(255,153,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="80" y="243.85223645946513" fill="rgb(255,153,153)">0.6</text> |
|||
<text style="font-size: 8pt;" x="80" y="300" fill="rgb(0,0,0)">32</text> |
|||
<line x1="120" y1="273.3687218988938" x2="80" y2="271.59097505774" style="stroke:rgb(153,0,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="120" y="273.3687218988938" fill="rgb(153,0,255)">0.3</text> |
|||
<line x1="120" y1="273.2187003317216" x2="80" y2="266.1457872407004" style="stroke:rgb(153,255,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="120" y="273.2187003317216" fill="rgb(153,255,153)">0.3</text> |
|||
<line x1="120" y1="184.0375802848887" x2="80" y2="197.9335788586706" style="stroke:rgb(0,255,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="120" y="184.0375802848887" fill="rgb(0,255,255)">1.3</text> |
|||
<line x1="120" y1="247.36927461158245" x2="80" y2="243.85223645946513" style="stroke:rgb(255,153,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="120" y="247.36927461158245" fill="rgb(255,153,153)">0.6</text> |
|||
<text style="font-size: 8pt;" x="120" y="300" fill="rgb(0,0,0)">64</text> |
|||
<line x1="160" y1="280.0267366728067" x2="120" y2="273.3687218988938" style="stroke:rgb(153,0,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="160" y="280.0267366728067" fill="rgb(153,0,255)">0.2</text> |
|||
<line x1="160" y1="278.3306191945452" x2="120" y2="273.2187003317216" style="stroke:rgb(153,255,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="160" y="278.3306191945452" fill="rgb(153,255,153)">0.2</text> |
|||
<line x1="160" y1="193.80312762756847" x2="120" y2="184.0375802848887" style="stroke:rgb(0,255,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="160" y="193.80312762756847" fill="rgb(0,255,255)">1.2</text> |
|||
<line x1="160" y1="250.4264809169783" x2="120" y2="247.36927461158245" style="stroke:rgb(255,153,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="160" y="250.4264809169783" fill="rgb(255,153,153)">0.5</text> |
|||
<text style="font-size: 8pt;" x="160" y="300" fill="rgb(0,0,0)">128</text> |
|||
<line x1="200" y1="283.2616949646197" x2="160" y2="280.0267366728067" style="stroke:rgb(153,0,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="200" y="283.2616949646197" fill="rgb(153,0,255)">0.1</text> |
|||
<line x1="200" y1="283.15126703525505" x2="160" y2="278.3306191945452" style="stroke:rgb(153,255,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="200" y="283.15126703525505" fill="rgb(153,255,153)">0.1</text> |
|||
<line x1="200" y1="179.8772379141531" x2="160" y2="193.80312762756847" style="stroke:rgb(0,255,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="200" y="179.8772379141531" fill="rgb(0,255,255)">1.3</text> |
|||
<line x1="200" y1="247.57494334396884" x2="160" y2="250.4264809169783" style="stroke:rgb(255,153,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="200" y="247.57494334396884" fill="rgb(255,153,153)">0.6</text> |
|||
<text style="font-size: 8pt;" x="200" y="300" fill="rgb(0,0,0)">256</text> |
|||
<line x1="240" y1="284.98919175692185" x2="200" y2="283.2616949646197" style="stroke:rgb(153,0,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="240" y="284.98919175692185" fill="rgb(153,0,255)">0.1</text> |
|||
<line x1="240" y1="288.2320350909907" x2="200" y2="283.15126703525505" style="stroke:rgb(153,255,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="240" y="288.2320350909907" fill="rgb(153,255,153)">0.1</text> |
|||
<line x1="240" y1="115.37561513335092" x2="200" y2="179.8772379141531" style="stroke:rgb(0,255,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="240" y="115.37561513335092" fill="rgb(0,255,255)">2.1</text> |
|||
<line x1="240" y1="241.2029598079109" x2="200" y2="247.57494334396884" style="stroke:rgb(255,153,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="240" y="241.2029598079109" fill="rgb(255,153,153)">0.6</text> |
|||
<text style="font-size: 8pt;" x="240" y="300" fill="rgb(0,0,0)">512</text> |
|||
<line x1="280" y1="287.3975513306974" x2="240" y2="284.98919175692185" style="stroke:rgb(153,0,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="280" y="287.3975513306974" fill="rgb(153,0,255)">0.1</text> |
|||
<line x1="280" y1="293.3565931075834" x2="240" y2="288.2320350909907" style="stroke:rgb(153,255,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="280" y="293.3565931075834" fill="rgb(153,255,153)">0.0</text> |
|||
<line x1="280" y1="93.56361255075586" x2="240" y2="115.37561513335092" style="stroke:rgb(0,255,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="280" y="93.56361255075586" fill="rgb(0,255,255)">2.4</text> |
|||
<line x1="280" y1="243.0694390692868" x2="240" y2="241.2029598079109" style="stroke:rgb(255,153,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="280" y="243.0694390692868" fill="rgb(255,153,153)">0.6</text> |
|||
<text style="font-size: 8pt;" x="280" y="300" fill="rgb(0,0,0)">1024</text> |
|||
<line x1="320" y1="289.8395296655668" x2="280" y2="287.3975513306974" style="stroke:rgb(153,0,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="320" y="289.8395296655668" fill="rgb(153,0,255)">0.1</text> |
|||
<line x1="320" y1="291.4247206595326" x2="280" y2="293.3565931075834" style="stroke:rgb(153,255,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="320" y="291.4247206595326" fill="rgb(153,255,153)">0.0</text> |
|||
<line x1="320" y1="91.37795492547124" x2="280" y2="93.56361255075586" style="stroke:rgb(0,255,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="320" y="91.37795492547124" fill="rgb(0,255,255)">2.4</text> |
|||
<line x1="320" y1="240.37311671765553" x2="280" y2="243.0694390692868" style="stroke:rgb(255,153,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="320" y="240.37311671765553" fill="rgb(255,153,153)">0.6</text> |
|||
<text style="font-size: 8pt;" x="320" y="300" fill="rgb(0,0,0)">2048</text> |
|||
<line x1="360" y1="291.82936406358374" x2="320" y2="289.8395296655668" style="stroke:rgb(153,0,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="360" y="291.82936406358374" fill="rgb(153,0,255)">0.0</text> |
|||
<line x1="360" y1="291.685536015328" x2="320" y2="291.4247206595326" style="stroke:rgb(153,255,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="360" y="291.685536015328" fill="rgb(153,255,153)">0.0</text> |
|||
<line x1="360" y1="84.43282646493722" x2="320" y2="91.37795492547124" style="stroke:rgb(0,255,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="360" y="84.43282646493722" fill="rgb(0,255,255)">2.5</text> |
|||
<line x1="360" y1="242.36747130138255" x2="320" y2="240.37311671765553" style="stroke:rgb(255,153,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="360" y="242.36747130138255" fill="rgb(255,153,153)">0.6</text> |
|||
<text style="font-size: 8pt;" x="360" y="300" fill="rgb(0,0,0)">4096</text> |
|||
<line x1="400" y1="293.64362664521053" x2="360" y2="291.82936406358374" style="stroke:rgb(153,0,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="400" y="293.64362664521053" fill="rgb(153,0,255)">0.0</text> |
|||
<line x1="400" y1="291.0443879550437" x2="360" y2="291.685536015328" style="stroke:rgb(153,255,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="400" y="291.0443879550437" fill="rgb(153,255,153)">0.1</text> |
|||
<line x1="400" y1="75.78456882308708" x2="360" y2="84.43282646493722" style="stroke:rgb(0,255,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="400" y="75.78456882308708" fill="rgb(0,255,255)">2.6</text> |
|||
<line x1="400" y1="244.82608599404003" x2="360" y2="242.36747130138255" style="stroke:rgb(255,153,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="400" y="244.82608599404003" fill="rgb(255,153,153)">0.6</text> |
|||
<text style="font-size: 8pt;" x="400" y="300" fill="rgb(0,0,0)">8192</text> |
|||
<line x1="440" y1="292.83027753490535" x2="400" y2="293.64362664521053" style="stroke:rgb(153,0,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="440" y="292.83027753490535" fill="rgb(153,0,255)">0.0</text> |
|||
<line x1="440" y1="289.20005644117305" x2="400" y2="291.0443879550437" style="stroke:rgb(153,255,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="440" y="289.20005644117305" fill="rgb(153,255,153)">0.1</text> |
|||
<line x1="440" y1="0.0" x2="400" y2="75.78456882308708" style="stroke:rgb(0,255,255);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="440" y="0.0" fill="rgb(0,255,255)">3.4</text> |
|||
<line x1="440" y1="240.93068766785797" x2="400" y2="244.82608599404003" style="stroke:rgb(255,153,153);stroke-width:2"/> |
|||
<text style="font-size: 8pt;" x="440" y="240.93068766785797" fill="rgb(255,153,153)">0.6</text> |
|||
<text style="font-size: 8pt;" x="440" y="300" fill="rgb(0,0,0)">16384</text> |
|||
</svg></body></html> |
|||
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> |
|||
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. |
|||
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> |
|||
''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.'' |
|||
<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 properly optimizing a loop in the bitmap ''free' method. Once this was corrected it was then faster than the standard run-time. |
|||
Latest revision as of 18:54, 7 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
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.
<html><body><svg height="300" width="700"> <text style="font-size: 8pt;" x="0" y="271.4770860505417" fill="rgb(0,0,0)">eb</text> <text style="font-size: 8pt;" x="0" y="260.5681727301949" fill="rgb(0,0,0)">bm</text> <text style="font-size: 8pt;" x="0" y="201.04345987460465" fill="rgb(0,0,0)">sb</text> <text style="font-size: 8pt;" x="0" y="238.8811744121518" fill="rgb(0,0,0)">mrvn</text> <line x1="40" y1="271.4770860505417" x2="39.0" y2="271.4770860505417" style="stroke:rgb(153,0,255);stroke-width:2"/> <text style="font-size: 8pt;" x="40" y="271.4770860505417" fill="rgb(153,0,255)">0.3</text> <line x1="40" y1="260.5681727301949" x2="39.0" y2="260.5681727301949" style="stroke:rgb(153,255,153);stroke-width:2"/> <text style="font-size: 8pt;" x="40" y="260.5681727301949" fill="rgb(153,255,153)">0.4</text> <line x1="40" y1="201.04345987460465" x2="39.0" y2="201.04345987460465" style="stroke:rgb(0,255,255);stroke-width:2"/> <text style="font-size: 8pt;" x="40" y="201.04345987460465" fill="rgb(0,255,255)">1.1</text> <line x1="40" y1="238.8811744121518" x2="39.0" y2="238.8811744121518" style="stroke:rgb(255,153,153);stroke-width:2"/> <text style="font-size: 8pt;" x="40" y="238.8811744121518" fill="rgb(255,153,153)">0.7</text> <text style="font-size: 8pt;" x="40" y="300" fill="rgb(0,0,0)">16</text> <line x1="80" y1="271.59097505774" x2="40" y2="271.4770860505417" style="stroke:rgb(153,0,255);stroke-width:2"/> <text style="font-size: 8pt;" x="80" y="271.59097505774" fill="rgb(153,0,255)">0.3</text> <line x1="80" y1="266.1457872407004" x2="40" y2="260.5681727301949" style="stroke:rgb(153,255,153);stroke-width:2"/> <text style="font-size: 8pt;" x="80" y="266.1457872407004" fill="rgb(153,255,153)">0.3</text> <line x1="80" y1="197.9335788586706" x2="40" y2="201.04345987460465" style="stroke:rgb(0,255,255);stroke-width:2"/> <text style="font-size: 8pt;" x="80" y="197.9335788586706" fill="rgb(0,255,255)">1.1</text> <line x1="80" y1="243.85223645946513" x2="40" y2="238.8811744121518" style="stroke:rgb(255,153,153);stroke-width:2"/> <text style="font-size: 8pt;" x="80" y="243.85223645946513" fill="rgb(255,153,153)">0.6</text> <text style="font-size: 8pt;" x="80" y="300" fill="rgb(0,0,0)">32</text> <line x1="120" y1="273.3687218988938" x2="80" y2="271.59097505774" style="stroke:rgb(153,0,255);stroke-width:2"/> <text style="font-size: 8pt;" x="120" y="273.3687218988938" fill="rgb(153,0,255)">0.3</text> <line x1="120" y1="273.2187003317216" x2="80" y2="266.1457872407004" style="stroke:rgb(153,255,153);stroke-width:2"/> <text style="font-size: 8pt;" x="120" y="273.2187003317216" fill="rgb(153,255,153)">0.3</text> <line x1="120" y1="184.0375802848887" x2="80" y2="197.9335788586706" style="stroke:rgb(0,255,255);stroke-width:2"/> <text style="font-size: 8pt;" x="120" y="184.0375802848887" fill="rgb(0,255,255)">1.3</text> <line x1="120" y1="247.36927461158245" x2="80" y2="243.85223645946513" style="stroke:rgb(255,153,153);stroke-width:2"/> <text style="font-size: 8pt;" x="120" y="247.36927461158245" fill="rgb(255,153,153)">0.6</text> <text style="font-size: 8pt;" x="120" y="300" fill="rgb(0,0,0)">64</text> <line x1="160" y1="280.0267366728067" x2="120" y2="273.3687218988938" style="stroke:rgb(153,0,255);stroke-width:2"/> <text style="font-size: 8pt;" x="160" y="280.0267366728067" fill="rgb(153,0,255)">0.2</text> <line x1="160" y1="278.3306191945452" x2="120" y2="273.2187003317216" style="stroke:rgb(153,255,153);stroke-width:2"/> <text style="font-size: 8pt;" x="160" y="278.3306191945452" fill="rgb(153,255,153)">0.2</text> <line x1="160" y1="193.80312762756847" x2="120" y2="184.0375802848887" style="stroke:rgb(0,255,255);stroke-width:2"/> <text style="font-size: 8pt;" x="160" y="193.80312762756847" fill="rgb(0,255,255)">1.2</text> <line x1="160" y1="250.4264809169783" x2="120" y2="247.36927461158245" style="stroke:rgb(255,153,153);stroke-width:2"/> <text style="font-size: 8pt;" x="160" y="250.4264809169783" fill="rgb(255,153,153)">0.5</text> <text style="font-size: 8pt;" x="160" y="300" fill="rgb(0,0,0)">128</text> <line x1="200" y1="283.2616949646197" x2="160" y2="280.0267366728067" style="stroke:rgb(153,0,255);stroke-width:2"/> <text style="font-size: 8pt;" x="200" y="283.2616949646197" fill="rgb(153,0,255)">0.1</text> <line x1="200" y1="283.15126703525505" x2="160" y2="278.3306191945452" style="stroke:rgb(153,255,153);stroke-width:2"/> <text style="font-size: 8pt;" x="200" y="283.15126703525505" fill="rgb(153,255,153)">0.1</text> <line x1="200" y1="179.8772379141531" x2="160" y2="193.80312762756847" style="stroke:rgb(0,255,255);stroke-width:2"/> <text style="font-size: 8pt;" x="200" y="179.8772379141531" fill="rgb(0,255,255)">1.3</text> <line x1="200" y1="247.57494334396884" x2="160" y2="250.4264809169783" style="stroke:rgb(255,153,153);stroke-width:2"/> <text style="font-size: 8pt;" x="200" y="247.57494334396884" fill="rgb(255,153,153)">0.6</text> <text style="font-size: 8pt;" x="200" y="300" fill="rgb(0,0,0)">256</text> <line x1="240" y1="284.98919175692185" x2="200" y2="283.2616949646197" style="stroke:rgb(153,0,255);stroke-width:2"/> <text style="font-size: 8pt;" x="240" y="284.98919175692185" fill="rgb(153,0,255)">0.1</text> <line x1="240" y1="288.2320350909907" x2="200" y2="283.15126703525505" style="stroke:rgb(153,255,153);stroke-width:2"/> <text style="font-size: 8pt;" x="240" y="288.2320350909907" fill="rgb(153,255,153)">0.1</text> <line x1="240" y1="115.37561513335092" x2="200" y2="179.8772379141531" style="stroke:rgb(0,255,255);stroke-width:2"/> <text style="font-size: 8pt;" x="240" y="115.37561513335092" fill="rgb(0,255,255)">2.1</text> <line x1="240" y1="241.2029598079109" x2="200" y2="247.57494334396884" style="stroke:rgb(255,153,153);stroke-width:2"/> <text style="font-size: 8pt;" x="240" y="241.2029598079109" fill="rgb(255,153,153)">0.6</text> <text style="font-size: 8pt;" x="240" y="300" fill="rgb(0,0,0)">512</text> <line x1="280" y1="287.3975513306974" x2="240" y2="284.98919175692185" style="stroke:rgb(153,0,255);stroke-width:2"/> <text style="font-size: 8pt;" x="280" y="287.3975513306974" fill="rgb(153,0,255)">0.1</text> <line x1="280" y1="293.3565931075834" x2="240" y2="288.2320350909907" style="stroke:rgb(153,255,153);stroke-width:2"/> <text style="font-size: 8pt;" x="280" y="293.3565931075834" fill="rgb(153,255,153)">0.0</text> <line x1="280" y1="93.56361255075586" x2="240" y2="115.37561513335092" style="stroke:rgb(0,255,255);stroke-width:2"/> <text style="font-size: 8pt;" x="280" y="93.56361255075586" fill="rgb(0,255,255)">2.4</text> <line x1="280" y1="243.0694390692868" x2="240" y2="241.2029598079109" style="stroke:rgb(255,153,153);stroke-width:2"/> <text style="font-size: 8pt;" x="280" y="243.0694390692868" fill="rgb(255,153,153)">0.6</text> <text style="font-size: 8pt;" x="280" y="300" fill="rgb(0,0,0)">1024</text> <line x1="320" y1="289.8395296655668" x2="280" y2="287.3975513306974" style="stroke:rgb(153,0,255);stroke-width:2"/> <text style="font-size: 8pt;" x="320" y="289.8395296655668" fill="rgb(153,0,255)">0.1</text> <line x1="320" y1="291.4247206595326" x2="280" y2="293.3565931075834" style="stroke:rgb(153,255,153);stroke-width:2"/> <text style="font-size: 8pt;" x="320" y="291.4247206595326" fill="rgb(153,255,153)">0.0</text> <line x1="320" y1="91.37795492547124" x2="280" y2="93.56361255075586" style="stroke:rgb(0,255,255);stroke-width:2"/> <text style="font-size: 8pt;" x="320" y="91.37795492547124" fill="rgb(0,255,255)">2.4</text> <line x1="320" y1="240.37311671765553" x2="280" y2="243.0694390692868" style="stroke:rgb(255,153,153);stroke-width:2"/> <text style="font-size: 8pt;" x="320" y="240.37311671765553" fill="rgb(255,153,153)">0.6</text> <text style="font-size: 8pt;" x="320" y="300" fill="rgb(0,0,0)">2048</text> <line x1="360" y1="291.82936406358374" x2="320" y2="289.8395296655668" style="stroke:rgb(153,0,255);stroke-width:2"/> <text style="font-size: 8pt;" x="360" y="291.82936406358374" fill="rgb(153,0,255)">0.0</text> <line x1="360" y1="291.685536015328" x2="320" y2="291.4247206595326" style="stroke:rgb(153,255,153);stroke-width:2"/> <text style="font-size: 8pt;" x="360" y="291.685536015328" fill="rgb(153,255,153)">0.0</text> <line x1="360" y1="84.43282646493722" x2="320" y2="91.37795492547124" style="stroke:rgb(0,255,255);stroke-width:2"/> <text style="font-size: 8pt;" x="360" y="84.43282646493722" fill="rgb(0,255,255)">2.5</text> <line x1="360" y1="242.36747130138255" x2="320" y2="240.37311671765553" style="stroke:rgb(255,153,153);stroke-width:2"/> <text style="font-size: 8pt;" x="360" y="242.36747130138255" fill="rgb(255,153,153)">0.6</text> <text style="font-size: 8pt;" x="360" y="300" fill="rgb(0,0,0)">4096</text> <line x1="400" y1="293.64362664521053" x2="360" y2="291.82936406358374" style="stroke:rgb(153,0,255);stroke-width:2"/> <text style="font-size: 8pt;" x="400" y="293.64362664521053" fill="rgb(153,0,255)">0.0</text> <line x1="400" y1="291.0443879550437" x2="360" y2="291.685536015328" style="stroke:rgb(153,255,153);stroke-width:2"/> <text style="font-size: 8pt;" x="400" y="291.0443879550437" fill="rgb(153,255,153)">0.1</text> <line x1="400" y1="75.78456882308708" x2="360" y2="84.43282646493722" style="stroke:rgb(0,255,255);stroke-width:2"/> <text style="font-size: 8pt;" x="400" y="75.78456882308708" fill="rgb(0,255,255)">2.6</text> <line x1="400" y1="244.82608599404003" x2="360" y2="242.36747130138255" style="stroke:rgb(255,153,153);stroke-width:2"/> <text style="font-size: 8pt;" x="400" y="244.82608599404003" fill="rgb(255,153,153)">0.6</text> <text style="font-size: 8pt;" x="400" y="300" fill="rgb(0,0,0)">8192</text> <line x1="440" y1="292.83027753490535" x2="400" y2="293.64362664521053" style="stroke:rgb(153,0,255);stroke-width:2"/> <text style="font-size: 8pt;" x="440" y="292.83027753490535" fill="rgb(153,0,255)">0.0</text> <line x1="440" y1="289.20005644117305" x2="400" y2="291.0443879550437" style="stroke:rgb(153,255,153);stroke-width:2"/> <text style="font-size: 8pt;" x="440" y="289.20005644117305" fill="rgb(153,255,153)">0.1</text> <line x1="440" y1="0.0" x2="400" y2="75.78456882308708" style="stroke:rgb(0,255,255);stroke-width:2"/> <text style="font-size: 8pt;" x="440" y="0.0" fill="rgb(0,255,255)">3.4</text> <line x1="440" y1="240.93068766785797" x2="400" y2="244.82608599404003" style="stroke:rgb(255,153,153);stroke-width:2"/> <text style="font-size: 8pt;" x="440" y="240.93068766785797" fill="rgb(255,153,153)">0.6</text> <text style="font-size: 8pt;" x="440" y="300" fill="rgb(0,0,0)">16384</text> </svg></body></html>
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.