User:Pancakes/SimpleHeapImplementation: Difference between revisions

From OSDev.wiki
Jump to navigation Jump to search
← Older edit
Content deleted Content added
VisualWikitext
Pancakes (talk | contribs)
294 edits
m added more info about each implementation
Pancakes (talk | contribs)
294 edits
added correct graph
 
(14 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Simple Heap Implementation ==
== Simple Heap Implementation ==
There are two simple heap implementations for you to examine. I want to come back and
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. They
write a little tutorial on each page to kind of walk the reader through how they work.
are not meant to be the greatest in the world. Just enough to get you to see how it can be
done. There is plenty of room for optimization though. If your looking for something high
performance and cutting edge then you might be a little disappointed.


If you want to copy them straight out and use them in your kernel then that is fine. I put these
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
up here so someone who might not be that interested in implementing a heap can get it done and
move on to better things.
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 [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 18: 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)'' A entry based heap implementation.
|-
| [[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.
|-
| [[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 ====

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.''

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.

Retrieved from "https://osdev.wiki/wiki/User:Pancakes/SimpleHeapImplementation?oldid=13230"