Dear all,
as a reminder, the result of the original code was:
LinkedList wrote:Single Main Thread: 32 ms
1 Thread(s): 32 ms
2 Thread(s): 148 ms
3 Thread(s): 406 ms
4 Thread(s): 982 ms
The result with just allocating and freeing memory:
AllocateMemory wrote:Single Main Thread: 38 ms
1 Thread(s): 39 ms
2 Thread(s): 45 ms
3 Thread(s): 42 ms
4 Thread(s): 68 ms
And now the result with my Slab-Module:
Slab-Allocator wrote:Single Main Thread: 19 ms
1 Thread(s): 19 ms
2 Thread(s): 25 ms
3 Thread(s): 29 ms
4 Thread(s): 36 ms
I'm very happy about the performance.
At the moment I do some more performance test with usual cases and extreme cases when allocating and releasing random elements.
However, here are the code for you and an example:
Code: Select all
CompilerIf Not #PB_Compiler_Thread
CompilerError "Enable Thread-Safe"
CompilerEndIf
XIncludeFile "Slab.pbm"
Procedure Test(Void.i=0)
Protected I.i
Protected *Slab = Slab::NewAllocator(SizeOf(Integer))
For I = 1 To 1000000
Slab::AllocateElement(*Slab)
Next
Slab::FreeAllocator(*Slab)
EndProcedure
Define Time.i, Threads.i
Define NewList Thread.i()
OpenConsole()
Time = ElapsedMilliseconds()
Test()
Time = ElapsedMilliseconds() - Time
PrintN("Single Main Thread: "+Str(Time)+" ms")
For Threads = 1 To 4
Time = ElapsedMilliseconds()
For I = 1 To Threads
AddElement(Thread()) : Thread() = CreateThread(@Test(), 0)
Next
ForEach Thread()
WaitThread(Thread())
Next
ClearList(Thread())
Time = ElapsedMilliseconds() - Time
PrintN(Str(Threads)+" Thread(s): "+Str(Time)+" ms")
Next
Input()
________
Slab Module:
Code: Select all
DeclareModule Slab
Prototype Callback(*Element)
Declare.i NewAllocator(ElementSize.i, SlabLength.i=128) ; Creates a new slab-allocator with the specified element size and slab length.
Declare.i AllocateElement(*Allocator, AllocationCallback.Callback=#Null) ; Allocates a new element within the slab-allocator with an optional callback for i.e. InitializeStructure()
Declare.i ReleaseElement(*Element, ReleaseCallback.Callback=#Null) ; Releases an element from the slab-allocator with an optional callback for i.e. ClearStructure()
Declare.i FreeAllocator(*Allocator, ReleaseCallback.Callback=#Null) ; Frees the whole slab-allocator and all its elements with an optional callback for i.e. ClearStructure()
Declare.i ExamineElements(*Allocator, ExaminationCallback.Callback) ; Examines all elements within the slab-allocator and calls the callback on each element.
Declare.i Report(*Allocator) ; Gives a debug report about the slab-allocator properties.
EndDeclareModule
Module Slab
EnableExplicit
Structure Allocator
SlabLength.i
SlabSize.i
Slabs.i
*LatestSlab.Slab
ElementSize.i
Elements.i
*NextUsableElement.Element
EndStructure
Structure Slab
*Allocator.Allocator
*PreviousSlab.Slab
*NextSlab.Slab
Elements.i
Voids.i
DataArea.i[0]
EndStructure
Structure Element
*Slab.Slab
*NextUsableElement.Element
DataArea.i[0]
EndStructure
Procedure ReleaseSlab(*Slab.Slab)
Protected *Allocator.Allocator = *Slab\Allocator
Protected *NextUsableElement.Element
If *Slab\PreviousSlab
*Slab\PreviousSlab\NextSlab = *Slab\NextSlab
EndIf
If *Slab\NextSlab
*Slab\NextSlab\PreviousSlab = *Slab\PreviousSlab
EndIf
While *Allocator\NextUsableElement And *Allocator\NextUsableElement > *Slab And *Allocator\NextUsableElement < *Slab + *Allocator\SlabSize
*Allocator\NextUsableElement = *Allocator\NextUsableElement\NextUsableElement
*Slab\Voids - 1
Wend
*NextUsableElement = *Allocator\NextUsableElement
While *NextUsableElement\NextUsableElement And *Slab\Voids > 0
If *NextUsableElement\NextUsableElement > *Slab And *NextUsableElement\NextUsableElement < *Slab + *Allocator\SlabSize
*NextUsableElement\NextUsableElement = *NextUsableElement\NextUsableElement\NextUsableElement
*Slab\Voids - 1
Else
*NextUsableElement = *NextUsableElement\NextUsableElement
EndIf
Wend
*Allocator\Slabs - 1
FreeMemory(*Slab)
EndProcedure
Procedure.i AllocateSlab(*Allocator.Allocator)
Protected *Slab.Slab = AllocateMemory(*Allocator\SlabSize)
With *Slab
\Allocator = *Allocator
\NextSlab = *Allocator\LatestSlab
If *Allocator\LatestSlab
*Allocator\LatestSlab\PreviousSlab = *Slab
EndIf
EndWith
*Allocator\Slabs + 1
*Allocator\LatestSlab = *Slab
ProcedureReturn *Slab
EndProcedure
Procedure.i NewAllocator(ElementSize.i, SlabLength.i=128)
Protected *Allocator.Allocator = AllocateMemory( SizeOf(Allocator) )
With *Allocator
\SlabLength = SlabLength
\SlabSize = SizeOf(Slab) + ( SizeOf(Element) + ElementSize ) * SlabLength
\LatestSlab = AllocateSlab(*Allocator)
\ElementSize = ElementSize
\NextUsableElement = \LatestSlab + SizeOf(Slab)
EndWith
ProcedureReturn *Allocator
EndProcedure
Procedure.i AllocateElement(*Allocator.Allocator, AllocationCallback.Callback=#Null)
Protected *Element.Element
*Allocator\Elements + 1
*Element = *Allocator\NextUsableElement
If *Element\NextUsableElement
; Allocate a void
*Element\Slab\Elements + 1
*Element\Slab\Voids - 1
*Allocator\NextUsableElement = *Element\NextUsableElement
*Element\NextUsableElement = #Null
Else
; Allocate from latest slab
*Element\Slab = *Allocator\LatestSlab
*Element\Slab\Elements + 1
If *Element\Slab\Elements < *Allocator\SlabLength
*Allocator\NextUsableElement = *Allocator\NextUsableElement + ( SizeOf(Element) + *Allocator\ElementSize )
Else
*Allocator\LatestSlab = AllocateSlab(*Allocator)
*Allocator\NextUsableElement = *Allocator\LatestSlab + SizeOf(Slab)
EndIf
EndIf
If AllocationCallback
ProcedureReturn AllocationCallback( *Element + SizeOf(Element) ) ; Shift the Pointer to the element's data.
Else
ProcedureReturn *Element + SizeOf(Element) ; Shift the Pointer to the element's data.
EndIf
EndProcedure
Procedure ReleaseElement(*Element.Element, ReleaseCallback.Callback=#Null)
Protected *Slab.Slab, *Allocator.Allocator
*Element - SizeOf(Element) ; Shift the Pointer to the element's head.
*Slab = *Element\Slab
*Allocator = *Slab\Allocator
If ReleaseCallback
ReleaseCallback(*Element + SizeOf(Element))
Else
FillMemory(*Element + SizeOf(Element), *Allocator\ElementSize)
EndIf
*Slab\Elements - 1
*Slab\Voids + 1
*Allocator\Elements - 1
*Element\NextUsableElement = *Allocator\NextUsableElement
*Allocator\NextUsableElement = *Element
If *Slab\Voids = *Allocator\SlabLength And *Allocator\Elements <= (*Allocator\Slabs-2) * *Allocator\SlabLength
ReleaseSlab(*Slab)
EndIf
EndProcedure
Procedure FreeAllocator(*Allocator.Allocator, ReleaseCallback.Callback=#Null)
Protected *Slab.Slab = *Allocator\LatestSlab
Protected *NextSlab.Slab
Protected Index.i, *Element.Element
If ReleaseCallback
While *Slab
Index = 0
While Index < *Slab\Elements + *Slab\Voids
*Element = *Slab + SizeOf(Slab) + Index * (SizeOf(Element) + *Allocator\ElementSize)
If *Element\NextUsableElement = #Null
ReleaseCallback(*Element + SizeOf(Element))
EndIf
Index + 1
Wend
*NextSlab = *Slab\NextSlab
FreeMemory(*Slab)
*Slab = *NextSlab
Wend
Else
While *Slab
*NextSlab = *Slab\NextSlab
FreeMemory(*Slab)
*Slab = *NextSlab
Wend
EndIf
FreeMemory(*Allocator)
EndProcedure
Procedure.i ExamineElements(*Allocator.Allocator, ExaminationCallback.Callback)
Protected *Slab.Slab = *Allocator\LatestSlab
Protected *NextSlab.Slab
Protected Index.i, *Element.Element
While *Slab
Index = 0
While Index < *Slab\Elements + *Slab\Voids
*Element = *Slab + SizeOf(Slab) + Index * (SizeOf(Element) + *Allocator\ElementSize)
If *Element\NextUsableElement = #Null
ExaminationCallback(*Element + SizeOf(Element))
EndIf
Index + 1
Wend
*Slab = *Slab\NextSlab
Wend
ProcedureReturn *Allocator\Elements
EndProcedure
Procedure Report(*Allocator.Allocator)
Protected *Slab.Slab = *Allocator\LatestSlab
Protected Index.i, String.s
Protected *Element.Element
Debug "SlabAllocator {"
Debug " Element size = " + *Allocator\ElementSize + " Byte"
Debug " Slab length = " + *Allocator\SlabLength
Debug " Slabs = " + *Allocator\Slabs
Debug " Elements = " + *Allocator\Elements
Debug " Total size = " + Str( SizeOf(Allocator) + *Allocator\Slabs * *Allocator\SlabSize ) + " Byte"
Debug " Fill ratio = " + Str(100 * *Allocator\Elements / (*Allocator\Slabs * *Allocator\SlabLength))+" %"
Debug " Slabs {"
While *Slab
Index = 0
String = ""
While Index < *Slab\Elements + *Slab\Voids
*Element = *Slab + SizeOf(Slab) + Index * (SizeOf(Element) + *Allocator\ElementSize)
If *Element\NextUsableElement = #Null
String + "#"
Else
String + "o"
EndIf
Index + 1
Wend
Debug " "+LSet(String, *Allocator\SlabLength, ".")
*Slab = *Slab\NextSlab
Wend
Debug "}"
EndProcedure
EndModule
;- Example
CompilerIf #PB_Compiler_IsMainFile
Procedure ExaminationCallback(*Integer.Integer) ; A callback for the Slab::ExamineElements() procedure
Debug "Element: " + Str(*Integer\i)
EndProcedure
Define *Slab = Slab::NewAllocator(8, 3) ; New slab-allocator with 8 byte for each element and just 3 elements per slab for demonstration.
Define Dim *Element.Integer(100)
*Element(1) = Slab::AllocateElement(*Slab) : *Element(1)\i = 1 ; Allocate some elements and fill them. The array ist just for easier access.
*Element(2) = Slab::AllocateElement(*Slab) : *Element(2)\i = 2
*Element(3) = Slab::AllocateElement(*Slab) : *Element(3)\i = 3
*Element(4) = Slab::AllocateElement(*Slab) : *Element(4)\i = 4
*Element(5) = Slab::AllocateElement(*Slab) : *Element(5)\i = 5
*Element(6) = Slab::AllocateElement(*Slab) : *Element(6)\i = 6
*Element(7) = Slab::AllocateElement(*Slab) : *Element(7)\i = 7
*Element(8) = Slab::AllocateElement(*Slab) : *Element(8)\i = 8
Slab::ReleaseElement(*Element(3)) ; Release some of this elements.
Slab::ReleaseElement(*Element(1))
Slab::ReleaseElement(*Element(7))
Slab::Report(*Slab) ; Give a short report about the slab-allocator
*Element(9) = Slab::AllocateElement(*Slab ) : *Element(9)\i = 9 ; Allocate some more elements, using the free places.
*Element(10) = Slab::AllocateElement(*Slab) : *Element(10)\i = 10
Slab::Report(*Slab)
Slab::ReleaseElement(*Element(9)) ; Release some more elements, resulting in a release of a slab.
Slab::ReleaseElement(*Element(8))
Slab::ReleaseElement(*Element(10))
Slab::ReleaseElement(*Element(2))
Slab::Report(*Slab)
Slab::ExamineElements(*Slab, @ExaminationCallback())
CompilerEndIf