Dynamic ArrayList (with circular doubly linked list under the hood)

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
Post Reply
fxm
Moderator
Posts: 12362
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Doubly linked list (optimized) [under the hood to build a Dynamic ArrayList]

Post by fxm »

About the eventual new member method:
.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)


fxm wrote: Sep 05, 2024 19:39 Using this new destruction member method, compared to a user destruction loop (user data destruction + element destruction in a same loop), allows to gain a factor of about 30% on the destruction time.
Should we then validate this idea?

Test code with the file to include modified accordingly:

Code: Select all

' DynamicArrayList.bi modified

#if __FB_VERSION__ < "1.10"
Type DoublyLinkedNode
    Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
    Dim As Any Ptr userPtr                   '' user pointer
    Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
End Type
#endif

Type DynamicArrayList
    Public:
        Declare Function InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
        Declare Function ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
        Declare Function ReverseOrderOfPosition() As Integer
        Declare Function ReturnArrayFromPosition(array() As Any Ptr) As Integer
        Declare Function LoadArrayIntoPosition(array() As Any Ptr) As Integer
        Declare Function SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
        Declare Sub DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
        Declare Function ReturnNumberOfPosition() As Integer
        Declare Constructor()
        Declare Destructor()
    Private:
        #if __FB_VERSION__ >= "1.10"
        Type DoublyLinkedNode
            Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
            Dim As Any Ptr userPtr                   '' user pointer
            Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
        End Type
        #endif
        Declare Function SearchNthPositionNode(ByVal n1 As Integer) As DoublyLinkedNode Ptr
        Dim As DoublyLinkedNode dummyNode           '' dummy node
        Dim As Integer nbrUserNode                  '' number of user node
        Dim As Integer recent1NodeIndex             '' recent #1 node index (position)
        Dim As DoublyLinkedNode Ptr recent1NodePtr  '' recent #1 node pointer
        Dim As Integer recent2NodeIndex             '' recent #2 node index (position)
        Dim As DoublyLinkedNode Ptr recent2NodePtr  '' recent #2 node pointer
End Type

Function DynamicArrayList.InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode + 1) Then Return 0
    ' Allocates memory for new node
    Dim As DoublyLinkedNode Ptr newNodePtr = CAllocate(1, SizeOf(DoublyLinkedNode))
    If newNodePtr = 0 Then Return 0
    ' Copies user pointer value in new node
    newNodePtr->userPtr = p
    ' Searches for node below insertion
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates pointers of previous, inserted, and next nodes
    newNodePtr->nextNodePtr = searchNodePtr
    newNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    searchNodePtr->prevNodePtr = newNodePtr
    newNodePtr->prevNodePtr->nextNodePtr = newNodePtr
    ' Increments the number of user nodes
    This.nbrUserNode +=1
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = newNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = newNodePtr
        This.recent2NodeIndex += 1  ' recent #2 node position shifted by the insertion
    End If
    Return p
End Function

Function DynamicArrayList.SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for node to suppress
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates of previous and next nodes
    searchNodePtr->prevNodePtr->nextNodePtr = searchNodePtr->nextNodePtr
    searchNodePtr->nextNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    ' Updates the recent visited node data
    If (posNodeIndex < This.nbrUserNode) And (posNodeIndex <> This.recent2NodeIndex) Then
        If posNodeIndex > This.recent1NodeIndex Then
            This.recent2NodeIndex = posNodeIndex
            This.recent2NodePtr = searchNodePtr->nextNodePtr
        Else
            This.recent1NodeIndex = posNodeIndex
            This.recent1NodePtr = searchNodePtr->nextNodePtr
            This.recent2NodeIndex -= 1  ' recent #2 node position shifted by the suppression
        End If
    Else
        ' Resets the recent visited node data
        This.recent1NodePtr = @This.dummyNode
        This.recent1NodeIndex = 0
        This.recent2NodePtr = @This.dummyNode
        This.recent2NodeIndex = 0
    End If
    ' Saves user pointer of the node
    Dim As Any Ptr searchUserPtr = searchNodePtr->userPtr
    ' Deallocates memory for the node
    Deallocate(searchNodePtr)
    ' Decrements the number of user nodes
    This.nbrUserNode -= 1
    Return searchUserPtr
End Function

Function DynamicArrayList.ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return searchNodePtr->userPtr
End Function

Function DynamicArrayList.UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates user pointer of the node
    searchNodePtr->userPtr = p
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return p
End Function

Function DynamicArrayList.SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts indexes into positive indexes
    Dim As Integer posNodeIndex1 = IIf(n1 <= 0, This.nbrUserNode + n1 + 1, n1)
    Dim As Integer posNodeIndex2 = IIf(n2 <= 0, This.nbrUserNode + n2 + 1, n2)
    ' Tests index validity
    If (posNodeIndex1 < 1) Or (posNodeIndex1 > This.nbrUserNode) Or (posNodeIndex2 < 1) Or (posNodeIndex2 > This.nbrUserNode) Then Return 0
    ' search for the 2 user nodes
    Dim As DoublyLinkedNode Ptr searchNodePtr1 = This.SearchNthPositionNode(posNodeIndex1)
    Dim As DoublyLinkedNode Ptr searchNodePtr2 = This.SearchNthPositionNode(posNodeIndex2)
    ' swaps the 2 user pointers
    Swap searchNodePtr1->userPtr, searchNodePtr2->userPtr
    ' Updates the recent visited node data
    If posNodeIndex2 > posNodeIndex1 Then
        This.recent1NodeIndex = posNodeIndex1
        This.recent1NodePtr = searchNodePtr1
        This.recent2NodeIndex = posNodeIndex2
        This.recent2NodePtr = searchNodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex2
        This.recent1NodePtr = searchNodePtr2
        This.recent2NodeIndex = posNodeIndex1
        This.recent2NodePtr = searchNodePtr1
    End If
    Return -1
End Function

Function DynamicArrayList.ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index and offset validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Or (posNodeIndex + offset < 1) Or (posNodeIndex + offset > This.nbrUserNode) Then Return 0
    ' search for the user node
    Dim As DoublyLinkedNode Ptr nodePtr2 = This.SearchNthPositionNode(posNodeIndex)
    Dim As DoublyLinkedNode Ptr nodePtr1
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = nodePtr2
    Else
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = nodePtr2
    End If
    ' Shifts the user pointer by using a repeated swapping process
    If offset > 0 Then
        For I As Integer = 1 To Offset
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->nextNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    Else
        For I As Integer = -1 To Offset Step -1
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->prevNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    End If
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent2NodeIndex = posNodeIndex + offset
        This.recent2NodePtr = nodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex + offset
        This.recent1NodePtr = nodePtr2
    End If
    Return -1
End Function

Function DynamicArrayList.ReverseOrderOfPosition() As Integer
    ' Returns 0 on empty list, otherwise -1
   
    ' Tests empty list
    If This.nbrUserNode = 0 Then Return 0
    ' Swaps user pointers from the ends up to the middle
    Dim As DoublyLinkedNode Ptr leftNodePtr = @This.dummyNode, rightNodePtr = @This.dummyNode
    For I As Integer = 1 To This.nbrUserNode \ 2
        leftNodePtr = leftNodePtr->nextNodePtr
        rightNodePtr = rightNodePtr->prevNodePtr
        Swap rightNodePtr->userPtr, leftNodePtr->userPtr
    Next I
    Return -1
End Function

Function DynamicArrayList.ReturnArrayFromPosition(array() As Any Ptr) As Integer
    ' Returns the number of elements
    
    If This.nbrUserNode = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    ' sizes the passed array
    Redim array(1 To This.nbrUserNode)
    ' fills in the array with the user pointers
    For I As Integer = 1 To This.nbrUserNode
        nodePtr = nodePtr->nextNodePtr
        array(I) = nodePtr->userPtr
    Next I
    Return This.nbrUserNode
End Function

Function DynamicArrayList.LoadArrayIntoPosition(array() As Any Ptr) As Integer
    ' Return 0 if the list is not empty, otherwise returns the number of loaded elements
    
    If This.nbrUserNode > 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    For I As Integer = Lbound(array) To Ubound(array)
        ' Allocates memory for new node
        Dim As DoublyLinkedNode Ptr newNodePtr = CAllocate(1, SizeOf(DoublyLinkedNode))
        If newNodePtr = 0 Then Return This.nbrUserNode
        ' Copies user pointer value in new node
        newNodePtr->userPtr = array(I)
        ' Updates pointers of previous and inserted nodes
        nodePtr->nextNodePtr = newNodePtr
        newNodePtr->prevNodePtr = nodePtr
        ' Inserted node becomes previous node
        nodePtr = newNodePtr
        ' Increments the number of user nodes
        This.nbrUserNode += 1
    Next I
    ' Updates pointer of last node and dummy node
    nodePtr->nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = nodePtr
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
    ' Return 0 if the search failed, otherwise returns the position index of the first occurence found
    ' If startPosition > 0 (set of positive index used), the search begins at the startPosition index then continues in the increasing index order
    ' If startPosition < 0 (set of negative index used), the search begins at the startPosition index then continues in the decreasing index order (reverse order)
    ' The returned index uses the same set (positive or negative) of index than the one used for startPosition
    
    If compare = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr
    ' set of positive index used
    If (startPosition >= 1) And (startPosition <= This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(startPosition)
        For I As Integer = startPosition To This.nbrUserNode
            If compare(nodePtr->userPtr) = True Then Return I
            ' next node
            nodePtr = nodePtr->nextNodePtr
        Next I
    ' set of negative index used
    ElseIf (startPosition <= -1) And (startPosition >= -This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(This.nbrUserNode + startPosition + 1)
        For I As Integer = startPosition To -This.nbrUserNode Step -1
            If compare(nodePtr->userPtr) = True Then Return I
            ' previous node
            nodePtr = nodePtr->prevNodePtr
        Next I
    End If
    Return 0
End Function

Sub DynamicArrayList.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
    ' Deallocates memory used by user nodes one by one by transverse access, including user data in the loop if destroy <> 0 is passed
    
    Dim As DoublyLinkedNode Ptr nodePtr = This.dummyNode.nextNodePtr
    If destroy <> 0 Then
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            destroy(nodePtr->prevNodePtr->userPtr)
            Deallocate(nodePtr->prevNodePtr)
        Next I
    Else
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            Deallocate(nodePtr->prevNodePtr)
        Next I
    End If
    ' Clears the number of user nodes
    This.nbrUserNode = 0
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodeIndex = 0
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodeIndex = 0
    This.recent2NodePtr = @This.dummyNode
End Sub

Function DynamicArrayList.ReturnNumberOfPosition() As Integer
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchNthPositionNode(ByVal posNodeIndex As Integer) As DoublyLinkedNode Ptr
    Dim As DoublyLinkedNode Ptr nodePtr
    ' The node (among these 3) memorized closest to the targeted position
    ' is chosen as starting point of the iteration (forward or backward) through the nodes
    ' (3 * 2 = 6 cases)
    If posNodeIndex < This.recent1NodeIndex Then
        If posNodeIndex <= This.recent1NodeIndex - posNodeIndex Then
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    ElseIf posNodeIndex < This.recent2NodeIndex Then
        If posNodeIndex - This.recent1NodeIndex <= This.recent2NodeIndex - posNodeIndex Then
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    Else
        If posNodeIndex - This.recent2NodeIndex <= This.nbrUserNode + 1 - posNodeIndex Then
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = This.nbrUserNode To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    End If
    Return nodePtr
End Function

Constructor DynamicArrayList()
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodePtr = @This.dummyNode
End Constructor

Destructor DynamicArrayList()
    ' Deallocates memory used by user nodes one by one  by transverse access
    This.DestroyAllNthPosition()
End Destructor



Sub PrintList(Byref dal As DynamicArrayList)
    Print "   ";
    For I As Integer = 1 To 5
        Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
    Next I
    Print " .....";
    For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
        Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
    Next I
    Print
End Sub

Sub destroy(ByVal p As Any Ptr)
    Delete Cptr(Long Ptr, p)
End Sub

Sub test(Byval N As Integer)
    Dim As Double t
    Dim As Integer position
    
    Dim As DynamicArrayList dal1
    Dim As DynamicArrayList dal2
    Print "Two Dynamic ArrayLists pointing to """ & N & """ dynamic integers :"
    For I As Integer = 1 To N
        dal1.InsertInNthPosition(New Long(I), 0)
    Next I
    PrintList(dal1)
    For I As Integer = 1 To N
        dal2.InsertInNthPosition(New Long(I), 0)
    Next I
    PrintList(dal2)
    Print
    Print "   Time to destroy all elements + the dynamic user data :"
    Print "      - by using a user loop for the first Dynamic ArrayList :"
    t = Timer
    For I As Integer = 1 To N
        Delete Cptr(Long Ptr, dal1.SuppressTheNthPosition(1))
    Next i
    Print "         " & Timer - t & " s"
    Print "      - by using the member method for the second Dynamic ArrayList :"
    t = Timer
    dal2.DestroyAllNthPosition(@destroy)
    Print "         " & Timer - t & " s"
End Sub

Test(1000000)
Print "--------------------------------------------------------------------"
Test(3000000)
Print "--------------------------------------------------------------------"
Test(5000000)
Print "--------------------------------------------------------------------"
Test(7000000)
Print "--------------------------------------------------------------------"
Test(9000000)

Sleep
  • Output example:

    Code: Select all

    Two Dynamic ArrayLists pointing to "1000000" dynamic integers :
        1 2 3 4 5 ..... 999996 999997 999998 999999 1000000
        1 2 3 4 5 ..... 999996 999997 999998 999999 1000000
    
       Time to destroy all elements + the dynamic user data :
          - by using a user loop for the first Dynamic ArrayList :
             0.1290565999519799 s
          - by using the member method for the second Dynamic ArrayList :
             0.08200879994598154 s
    --------------------------------------------------------------------
    Two Dynamic ArrayLists pointing to "3000000" dynamic integers :
        1 2 3 4 5 ..... 2999996 2999997 2999998 2999999 3000000
        1 2 3 4 5 ..... 2999996 2999997 2999998 2999999 3000000
    
       Time to destroy all elements + the dynamic user data :
          - by using a user loop for the first Dynamic ArrayList :
             0.3774869000394574 s
          - by using the member method for the second Dynamic ArrayList :
             0.2655347000473967 s
    --------------------------------------------------------------------
    Two Dynamic ArrayLists pointing to "5000000" dynamic integers :
        1 2 3 4 5 ..... 4999996 4999997 4999998 4999999 5000000
        1 2 3 4 5 ..... 4999996 4999997 4999998 4999999 5000000
    
       Time to destroy all elements + the dynamic user data :
          - by using a user loop for the first Dynamic ArrayList :
             0.6417374999850267 s
          - by using the member method for the second Dynamic ArrayList :
             0.4314474999961249 s
    --------------------------------------------------------------------
    Two Dynamic ArrayLists pointing to "7000000" dynamic integers :
        1 2 3 4 5 ..... 6999996 6999997 6999998 6999999 7000000
        1 2 3 4 5 ..... 6999996 6999997 6999998 6999999 7000000
    
       Time to destroy all elements + the dynamic user data :
          - by using a user loop for the first Dynamic ArrayList :
             0.8864024000415611 s
          - by using the member method for the second Dynamic ArrayList :
             0.6022076999993828 s
    --------------------------------------------------------------------
    Two Dynamic ArrayLists pointing to "9000000" dynamic integers :
        1 2 3 4 5 ..... 8999996 8999997 8999998 8999999 9000000
        1 2 3 4 5 ..... 8999996 8999997 8999998 8999999 9000000
    
       Time to destroy all elements + the dynamic user data :
          - by using a user loop for the first Dynamic ArrayList :
             1.11212479997738 s
          - by using the member method for the second Dynamic ArrayList :
             0.7666473000202814 s
    

I would prefer to add this member method to the DynamicArrayList structure, which makes it easier for the user to manually destroy the list elements and its associated data if necessary.
fxm
Moderator
Posts: 12362
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Doubly linked list (optimized) [under the hood to build a Dynamic ArrayList]

Post by fxm »

fxm wrote: Sep 06, 2024 8:53 About the eventual new member method:
.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)

Added the member method 'Sub DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)' in the 'DynamicArrayList' type:
- To destroy in one shoot all elements of the list, the user can call this member procedure, passing as optional argument a user procedure (callback) to also destroy (if necessary) from the member procedure internal loop his own dynamic data at the same time than the list elements.

These 3 posts have been updated.
fxm
Moderator
Posts: 12362
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Post by fxm »

fxm wrote: Aug 29, 2024 16:25 - For a preserved dynamic array, inserting (or deleting) an element at the end of the array is the best case in terms of execution time, otherwise it can be much worse when the insertion (or deletion) position is far from the end because all elements from the insertion position (or after the deletion position) have additionally to be shifted.
- For the Dynamic ArrayList, the insertion (or deletion) position has almost no effect on the execution time.

Test code:

Code: Select all

#include "DynamicArrayList.bi"

Sub PrintArray(array() As Integer)
    Print "            array:";
    If (Ubound(array) + 1) = 0 Then
        Print " empty";
    Elseif (Ubound(array) + 1) <= 10 Then
        For I As Integer = 0 To Ubound(array)
            Print array(I);
        Next I
    Else
        For I As Integer = 1 To 5
            Print array(I - 1);
        Next I
        Print " .....";
        For I As Integer = Ubound(array) - 4 To Ubound(array)
            Print array(I);
        Next I
    End If
    Print
End Sub

Sub PrintList(Byref dal As DynamicArrayList)
    Print "            list:";
    If dal.ReturnNumberOfPosition() = 0 Then
        Print " empty";
    Elseif dal.ReturnNumberOfPosition() <= 10 Then
        For I As Integer = 1 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    Else
        For I As Integer = 1 To 5
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
        Print " .....";
        For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    End If
    Print
End Sub

Sub test(Byval N As Integer)
    Dim As Double t
    Dim As Long array()
    Dim As DynamicArrayList dal
    
    Print
    Print "Preserved dynamic array of integers:"
    Print "   By acting only from the end of the array:"
    Print "      Time to increase the array step by step up to " & N & " elements:"
    t = Timer
    For I As Integer = 1 To N
        Redim Preserve array(Ubound(array) + 1)
        array(Ubound(array)) = I
    Next I
    Print "         " & Timer - t & " s"
    PrintArray(array())
    Print "      Time to decrease the array step by step up to 0 element:"
    t = Timer
    For I As Integer = 1 To N - 1
        Redim Preserve array(Ubound(array) - 1)
    Next I
    Erase array
    Print "         " & Timer - t & " s"
    PrintArray(array())
    Print "   By acting only from the beginning of the array:"
    Print "      Time to increase the array step by step up to " & N & " elements:"
    t = Timer
    Redim Preserve array(Ubound(array) + 1)
    array(Lbound(array)) = 1
    For I As Integer = 2 To N
        Redim Preserve array(Ubound(array) + 1)
        FB_Memmove(array(Lbound(array) + 1), array(Lbound(array)), (Ubound(array) - Lbound(array)) * Sizeof(Long))
        array(Lbound(array)) = I
    Next I
    Print "         " & Timer - t & " s"
    PrintArray(array())
    Print "      Time to decrease the array step by step up to 0 element:"
    t = Timer
    For I As Integer = 1 To N - 1
        FB_Memmove(array(Lbound(array)), array(Lbound(array) + 1), (Ubound(array) - Lbound(array)) * Sizeof(Long))
        Redim Preserve array(Ubound(array) - 1)
    Next I
    Erase array
    Print "         " & Timer - t & " s"
    PrintArray(array())
    Print
    
    Print "Dynamic ArrayList pointing to dynamic integers:"
    Print "   By acting only from the end of the list:"
    Print "      Time to increase the list step by step, up to " & N & " elements:"
    t = Timer
    For I As Integer = 1 To N
        dal.InsertInNthPosition(New Long(I), 0)
    Next I
    Print "         " & Timer - t & " s"
    PrintList(dal)
    Print "      Time to decrease the list step by step, up to 0 element:"
    t = Timer
    For I As Integer = 1 To N
        Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(-1))
    Next I
    Print "         " & Timer - t & " s"
    PrintList(dal)
    Print "   By acting only from the beginning of the list:"
    Print "      Time to increase the list step by step, up to " & N & " elements:"
    t = Timer
    For I As Integer = 1 To N
        dal.InsertInNthPosition(New Long(I), 1)
    Next I
    Print "         " & Timer - t & " s"
    PrintList(dal)
    Print "      Time to decrease the list step by step, up to 0 element:"
    t = Timer
    For I As Integer = 1 To N
        Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(1))
    Next I
    Print "         " & Timer - t & " s"
    PrintList(dal)
    Print
End Sub

Test(5000)
Print "--------------------------------------------------------------------"
Test(10000)
Print "--------------------------------------------------------------------"
Test(30000)
Print "--------------------------------------------------------------------"
Test(60000)

Sleep
  • Output example:

    Code: Select all

    Preserved dynamic array of integers:
       By acting only from the end of the array:
          Time to increase the array step by step up to 5000 elements:
             0.0006975000759439354 s
                array: 1 2 3 4 5 ..... 4996 4997 4998 4999 5000
          Time to decrease the array step by step up to 0 element:
             0.0004722000704759921 s
                array: empty
       By acting only from the beginning of the array:
          Time to increase the array step by step up to 5000 elements:
             0.006149299884668835 s
                array: 5000 4999 4998 4997 4996 ..... 5 4 3 2 1
          Time to decrease the array step by step up to 0 element:
             0.005664100097419578 s
                array: empty
    
    Dynamic ArrayList pointing to dynamic integers:
       By acting only from the end of the list:
          Time to increase the list step by step, up to 5000 elements:
             0.001034800063621333 s
                list: 1 2 3 4 5 ..... 4996 4997 4998 4999 5000
          Time to decrease the list step by step, up to 0 element:
             0.000546199929544855 s
                list: empty
       By acting only from the beginning of the list:
          Time to increase the list step by step, up to 5000 elements:
             0.001758899901801669 s
                list: 5000 4999 4998 4997 4996 ..... 5 4 3 2 1
          Time to decrease the list step by step, up to 0 element:
             0.0006361998839565786 s
                list: empty
    
    --------------------------------------------------------------------
    
    Preserved dynamic array of integers:
       By acting only from the end of the array:
          Time to increase the array step by step up to 10000 elements:
             0.001257399970768347 s
                array: 1 2 3 4 5 ..... 9996 9997 9998 9999 10000
          Time to decrease the array step by step up to 0 element:
             0.001068000088025656 s
                array: empty
       By acting only from the beginning of the array:
          Time to increase the array step by step up to 10000 elements:
             0.0219928001037033 s
                array: 10000 9999 9998 9997 9996 ..... 5 4 3 2 1
          Time to decrease the array step by step up to 0 element:
             0.02092620003111278 s
                array: empty
    
    Dynamic ArrayList pointing to dynamic integers:
       By acting only from the end of the list:
          Time to increase the list step by step, up to 10000 elements:
             0.002987899914046466 s
                list: 1 2 3 4 5 ..... 9996 9997 9998 9999 10000
          Time to decrease the list step by step, up to 0 element:
             0.001579099906393822 s
                list: empty
       By acting only from the beginning of the list:
          Time to increase the list step by step, up to 10000 elements:
             0.00231859990446992 s
                list: 10000 9999 9998 9997 9996 ..... 5 4 3 2 1
          Time to decrease the list step by step, up to 0 element:
             0.001407299953825714 s
                list: empty
    
    --------------------------------------------------------------------
    
    Preserved dynamic array of integers:
       By acting only from the end of the array:
          Time to increase the array step by step up to 30000 elements:
             0.003644799999847237 s
                array: 1 2 3 4 5 ..... 29996 29997 29998 29999 30000
          Time to decrease the array step by step up to 0 element:
             0.002756000055342156 s
                array: empty
       By acting only from the beginning of the array:
          Time to increase the array step by step up to 30000 elements:
             0.2054611000864952 s
                array: 30000 29999 29998 29997 29996 ..... 5 4 3 2 1
          Time to decrease the array step by step up to 0 element:
             0.2067085000668385 s
                array: empty
    
    Dynamic ArrayList pointing to dynamic integers:
       By acting only from the end of the list:
          Time to increase the list step by step, up to 30000 elements:
             0.007203299971251909 s
                list: 1 2 3 4 5 ..... 29996 29997 29998 29999 30000
          Time to decrease the list step by step, up to 0 element:
             0.006684799898835081 s
                list: empty
       By acting only from the beginning of the list:
          Time to increase the list step by step, up to 30000 elements:
             0.00683309997282322 s
                list: 30000 29999 29998 29997 29996 ..... 5 4 3 2 1
          Time to decrease the list step by step, up to 0 element:
             0.005087799908778834 s
                list: empty
    
    --------------------------------------------------------------------
    
    Preserved dynamic array of integers:
       By acting only from the end of the array:
          Time to increase the array step by step up to 60000 elements:
             0.009835400026190655 s
                array: 1 2 3 4 5 ..... 59996 59997 59998 59999 60000
          Time to decrease the array step by step up to 0 element:
             0.007979600000567189 s
                array: empty
       By acting only from the beginning of the array:
          Time to increase the array step by step up to 60000 elements:
             0.7594995999510274 s
                array: 60000 59999 59998 59997 59996 ..... 5 4 3 2 1
          Time to decrease the array step by step up to 0 element:
             0.7474576999555893 s
                array: empty
    
    Dynamic ArrayList pointing to dynamic integers:
       By acting only from the end of the list:
          Time to increase the list step by step, up to 60000 elements:
             0.01554709993968117 s
                list: 1 2 3 4 5 ..... 59996 59997 59998 59999 60000
          Time to decrease the list step by step, up to 0 element:
             0.01119940009459697 s
                list: empty
       By acting only from the beginning of the list:
          Time to increase the list step by step, up to 60000 elements:
             0.01170210008638151 s
                list: 60000 59999 59998 59997 59996 ..... 5 4 3 2 1
          Time to decrease the list step by step, up to 0 element:
             0.008671499908473379 s
                list: empty
    
    In the above results, for inserting/suppressing elements:
    - When using a preserve array, acting from the array beginning compared to acting from the array end increases the exécution time by a factor 10 to 100 depending on array size.
    - When using the Dynamic ArrayList, there is not notable difference in execution time between acting from the list beginning and acting from the list end, and this whatever the list size.
fxm
Moderator
Posts: 12362
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Post by fxm »

Small optimization in 'DynamicArrayList.bi' (about 10% speedup when inserting) by replacing 'CAllocate' (clearing unnecessary memory) with 'Allocate'.

Only this post has been updated.
shadow008
Posts: 117
Joined: Nov 26, 2013 2:43

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Post by shadow008 »

fxm wrote: Oct 03, 2024 14:57 Small optimization in 'DynamicArrayList.bi' (about 10% speedup when inserting) by replacing 'CAllocate' (clearing unnecessary memory) with 'Allocate'.
I had done this test myself in the past on personal projects, but this was on allocations of 100s to 10,000s of items only. The resulting segment allocations were usually <10KB in size, and I had seen barely measurable performance difference. I had came to the conclusion:

1. Callocate effectively loaded the entire memory segment into cache as part of zeroing out the segment
2. The segments usually fit into L1 cache
3. Therefore, the only difference between Allocate + fill and Callocate + fill was the additional iteration over the callocated segment, which was entirely in low level cache, and thus did not make any considerable performance difference.

At what scale (size in bytes of memory segments) were you seeing this 10% performance increase?
fxm
Moderator
Posts: 12362
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Post by fxm »

shadow008 wrote: Oct 03, 2024 16:12 At what scale (size in bytes of memory segments) were you seeing this 10% performance increase?
Inserting 10000000 consecutive elements (inducing a node-by-node allocation of 3 pointers each).
fxm
Moderator
Posts: 12362
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Post by fxm »

fxm wrote: Oct 03, 2024 16:43
shadow008 wrote: Oct 03, 2024 16:12 At what scale (size in bytes of memory segments) were you seeing this 10% performance increase?
Inserting 10000000 consecutive elements (inducing a node-by-node allocation of 3 pointers each).

Simple example with only the 'CAllocate' / 'Allocate' time taken into account:

Code: Select all

#define allocNbr 10000000

Dim As Double t
Redim As Any Ptr parray(1 To allocNbr)

For N As Integer = 1 To 5
    Print "Time for " & allocNbr & " 'Callocate' of 3 pointers each : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = Callocate(1, 3 * Sizeof(Any Ptr))
    Next I
    t = Timer - t
    Print t & " s"
    For I As Integer = 1 To allocNbr
        Deallocate(parray(I))
    Next I

    Print "Time for " & allocNbr & " 'Allocate' of 3 pointers each  : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = Allocate(3 * Sizeof(Any Ptr))
    Next I
    t = Timer - t
    Print t & " s"
    For I As Integer = 1 To allocNbr
        Deallocate(parray(I))
    Next I
    Print
Next N

Erase parray
Sleep
  • Output example:

    Code: Select all

    Time for 10000000 'Callocate' of 3 pointers each : 0.7727757000153872 s
    Time for 10000000 'Allocate' of 3 pointers each  : 0.5569001999748195 s
    
    Time for 10000000 'Callocate' of 3 pointers each : 0.7536964999775364 s
    Time for 10000000 'Allocate' of 3 pointers each  : 0.5533465999784255 s
    
    Time for 10000000 'Callocate' of 3 pointers each : 0.7513144000059526 s
    Time for 10000000 'Allocate' of 3 pointers each  : 0.560658500011499 s
    
    Time for 10000000 'Callocate' of 3 pointers each : 0.7622070999868811 s
    Time for 10000000 'Allocate' of 3 pointers each  : 0.5542497999804255 s
    
    Time for 10000000 'Callocate' of 3 pointers each : 0.7434600999982592 s
    Time for 10000000 'Allocate' of 3 pointers each  : 0.5390733000285479 s
    
    Speedup of about 25% here.

Note: it is surprising when using 'New', we find an execution time comparable to that of 'Allocate' (better than 'CAllocate'), while the memory is set to 0.
Example with an UDT of 3 pointers to be compatible with 'New':

Code: Select all

#define allocNbr 10000000

Type DoublyLinkedNode
    Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
    Dim As Any Ptr userPtr                   '' user pointer
    Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
End Type

Dim As Double t
Redim As DoublyLinkedNode Ptr parray(1 To allocNbr)

For N As Integer = 1 To 3
    Print "Time for " & allocNbr & " 'Callocate' of UDT (3 pointers) : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = Callocate(1, Sizeof(DoublyLinkedNode))
    Next I
    t = Timer - t
    Print t & " s"
    Print "   Time for " & allocNbr & " 'Deallocate' : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        Deallocate(parray(I))
    Next I
    t = Timer - t
    Print t & " s"

    Print "Time for " & allocNbr & " 'Allocate' of UDT (3 pointers)  : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = Allocate(Sizeof(DoublyLinkedNode))
    Next I
    t = Timer - t
    Print t & " s"
    Print "   Time for " & allocNbr & " 'Deallocate' : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        Deallocate(parray(I))
    Next I
    t = Timer - t
    Print t & " s"

    Print "Time for " & allocNbr & " 'New' of UDT (3 pointers)       : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        parray(I) = New DoublyLinkedNode
    Next I
    t = Timer - t
    Print t & " s"
    Print "   Time for " & allocNbr & " 'Delete'     : ";
    t = Timer
    For I As Integer = 1 To allocNbr
        Delete(parray(I))
    Next I
    t = Timer - t
    Print t & " s"
    Print
Next N

Erase parray
Sleep
  • Output example:

    Code: Select all

    Time for 10000000 'Callocate' of UDT (3 pointers) : 0.9042052000002663 s
       Time for 10000000 'Deallocate' : 0.3417718000007319 s
    Time for 10000000 'Allocate' of UDT (3 pointers)  : 0.6365616000034109 s
       Time for 10000000 'Deallocate' : 0.3315588000019929 s
    Time for 10000000 'New' of UDT (3 pointers)       : 0.6527570999982508 s
       Time for 10000000 'Delete'     : 0.4361705000013423 s
    
    Time for 10000000 'Callocate' of UDT (3 pointers) : 0.7977705999997653 s
       Time for 10000000 'Deallocate' : 0.3519302000023714 s
    Time for 10000000 'Allocate' of UDT (3 pointers)  : 0.6200587000020903 s
       Time for 10000000 'Deallocate' : 0.341211499998618 s
    Time for 10000000 'New' of UDT (3 pointers)       : 0.6394830000023006 s
       Time for 10000000 'Delete'     : 0.4483076000033428 s
    
    Time for 10000000 'Callocate' of UDT (3 pointers) : 0.7915781999985043 s
       Time for 10000000 'Deallocate' : 0.3403417999994574 s
    Time for 10000000 'Allocate' of UDT (3 pointers)  : 0.6272025000029693 s
       Time for 10000000 'Deallocate' : 0.3491629999966825 s
    Time for 10000000 'New' of UDT (3 pointers)       : 0.6726065999964668 s
       Time for 10000000 'Delete'     : 0.4498922999965451 s
    
Last edited by fxm on Oct 05, 2024 14:06, edited 2 times in total.
Reason: Added test with 'New' also.
fxm
Moderator
Posts: 12362
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Post by fxm »

Dynamic ArrayList: Pre-allocating memory for nodes ('DynamicArrayListWithPreAlloc.bi')

I tested the possibility of using pre-allocated memory for the nodes, in order to improve the execution time for inserting and suppressing positions in the list.
The user can set the number of pre-allocated nodes using an optional parameter at construction time.

Only a rudimentary pre-allocation of nodes can be used to obtain speed up of performance:
- individual freed nodes in pre-allocated memory cannot generally be re-used, except the last used pre-allocated (no time to scan the allocated memory to find a free node),
- if all pre-allocated nodes are freed, the full pre-allocation memory becomes back available,
- pre-allocated memory block cannot be resized (no time to readjust the pointers of all used nodes in allocated memory block),
- once that the end of the pre-allocated memory for nodes is reached, the next nodes are allocated individually.

Improvement: about 30% at maximum (when only pre-allocated nodes are used) of speed up for insertion and suppression.

- DynamicArrayListWithPreAlloc.bi:

Code: Select all

' DynamicArrayListWithPreAlloc.bi

#if __FB_VERSION__ < "1.10"
Type DoublyLinkedNode
    Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
    Dim As Any Ptr userPtr                   '' user pointer
    Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
End Type
#endif

Type DynamicArrayList
    Public:
        Declare Function InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
        Declare Function UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
        Declare Function SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
        Declare Function ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
        Declare Function ReverseOrderOfPosition() As Integer
        Declare Function ReturnArrayFromPosition(array() As Any Ptr) As Integer
        Declare Function LoadArrayIntoPosition(array() As Any Ptr) As Integer
        Declare Function SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
        Declare Sub DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
        Declare Function ReturnNumberOfPosition() As Integer
        Declare Constructor()
        Declare Constructor(ByVal nbrPreAlloc As Integer)
        Declare Destructor()
    Private:
        #if __FB_VERSION__ >= "1.10"
        Type DoublyLinkedNode
            Dim As DoublyLinkedNode Ptr prevNodePtr  '' previous node pointer
            Dim As Any Ptr userPtr                   '' user pointer
            Dim As DoublyLinkedNode Ptr nextNodePtr  '' next node pointer
        End Type
        #endif
        Declare Function SearchNthPositionNode(ByVal n1 As Integer) As DoublyLinkedNode Ptr
        Dim As DoublyLinkedNode dummyNode           '' dummy node
        Dim As Integer nbrUserNode                  '' number of user node
        Dim As Integer recent1NodeIndex             '' recent #1 node index (position)
        Dim As DoublyLinkedNode Ptr recent1NodePtr  '' recent #1 node pointer
        Dim As Integer recent2NodeIndex             '' recent #2 node index (position)
        Dim As DoublyLinkedNode Ptr recent2NodePtr  '' recent #2 node pointer
        Dim As DoublyLinkedNode Ptr preAllocPtr     '' pre-allocation pointer
        Dim As Integer nbrPreAllocDone              '' number of pre-allocation done
        Dim As Integer preAllocNbr                  '' pre-allocation number
        Dim As Integer nbrPreAllocUsed              '' number of pre-allocation used
End Type

Function DynamicArrayList.InsertInNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode + 1) Then Return 0
    Dim As DoublyLinkedNode Ptr newNodePtr
    If This.preAllocNbr = This.nbrPreAllocDone Then
        ' Allocates memory for new node
        newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
        If newNodePtr = 0 Then Return 0
    Else
        ' Uses pre-allocated memory
        newNodePtr = @This.preAllocPtr[This.preAllocNbr]
        This.nbrPreAllocUsed += 1
        This.preAllocNbr += 1
    End If
    ' Copies user pointer value in new node
    newNodePtr->userPtr = p
    ' Searches for node below insertion
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates pointers of previous, inserted, and next nodes
    newNodePtr->nextNodePtr = searchNodePtr
    newNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    searchNodePtr->prevNodePtr = newNodePtr
    newNodePtr->prevNodePtr->nextNodePtr = newNodePtr
    ' Increments the number of user nodes
    This.nbrUserNode +=1
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = newNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = newNodePtr
        This.recent2NodeIndex += 1  ' recent #2 node position shifted by the insertion
    End If
    Return p
End Function

Function DynamicArrayList.SuppressTheNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for node to suppress
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates of previous and next nodes
    searchNodePtr->prevNodePtr->nextNodePtr = searchNodePtr->nextNodePtr
    searchNodePtr->nextNodePtr->prevNodePtr = searchNodePtr->prevNodePtr
    ' Updates the recent visited node data
    If (posNodeIndex < This.nbrUserNode) And (posNodeIndex <> This.recent2NodeIndex) Then
        If posNodeIndex > This.recent1NodeIndex Then
            This.recent2NodeIndex = posNodeIndex
            This.recent2NodePtr = searchNodePtr->nextNodePtr
        Else
            This.recent1NodeIndex = posNodeIndex
            This.recent1NodePtr = searchNodePtr->nextNodePtr
            This.recent2NodeIndex -= 1  ' recent #2 node position shifted by the suppression
        End If
    Else
        ' Resets the recent visited node data
        This.recent1NodePtr = @This.dummyNode
        This.recent1NodeIndex = 0
        This.recent2NodePtr = @This.dummyNode
        This.recent2NodeIndex = 0
    End If
    ' Saves user pointer of the node
    Dim As Any Ptr searchUserPtr = searchNodePtr->userPtr
    If (This.nbrPreallocDone = 0) Orelse ((searchNodePtr < @This.preAllocPtr[0]) Or (searchNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
        ' Deallocates memory for the node
        Deallocate(searchNodePtr)
    Else
        ' Frees the node from the preallocated memeory
        This.nbrPreAllocUsed -= 1
        If This.nbrPreAllocUsed = 0 Then
            This.preAllocNbr = 0
        Else
            If searchNodePtr = @This.preAllocPtr[This.preAllocNbr - 1] Then This.preAllocNbr -= 1
        End If
    End If
    ' Decrements the number of user nodes
    This.nbrUserNode -= 1
    Return searchUserPtr
End Function

Function DynamicArrayList.ReturnFromNthPosition(ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return searchNodePtr->userPtr
End Function

Function DynamicArrayList.UpdateTheNthPosition(ByVal p As Any Ptr, ByVal n As Integer) As Any Ptr
    ' Returns 0 on error, otherwise the value of the provided user pointer
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Then Return 0
    ' Searches for user node
    Dim As DoublyLinkedNode Ptr searchNodePtr = This.SearchNthPositionNode(posNodeIndex)
    ' Updates user pointer of the node
    searchNodePtr->userPtr = p
    ' Updates the recent visited node data
    If posNodeIndex > This.recent1NodeIndex Then
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = searchNodePtr
    Else
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = searchNodePtr
    End If
    Return p
End Function

Function DynamicArrayList.SwapNthPthPosition(ByVal n1 As Integer, ByVal n2 As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts indexes into positive indexes
    Dim As Integer posNodeIndex1 = IIf(n1 <= 0, This.nbrUserNode + n1 + 1, n1)
    Dim As Integer posNodeIndex2 = IIf(n2 <= 0, This.nbrUserNode + n2 + 1, n2)
    ' Tests index validity
    If (posNodeIndex1 < 1) Or (posNodeIndex1 > This.nbrUserNode) Or (posNodeIndex2 < 1) Or (posNodeIndex2 > This.nbrUserNode) Or (posNodeIndex1 = posNodeIndex2) Then Return 0
    ' search for the 2 user nodes
    Dim As DoublyLinkedNode Ptr searchNodePtr1 = This.SearchNthPositionNode(posNodeIndex1)
    Dim As DoublyLinkedNode Ptr searchNodePtr2 = This.SearchNthPositionNode(posNodeIndex2)
    ' swaps the 2 user pointers
    Swap searchNodePtr1->userPtr, searchNodePtr2->userPtr
    ' Updates the recent visited node data
    If posNodeIndex2 > posNodeIndex1 Then
        This.recent1NodeIndex = posNodeIndex1
        This.recent1NodePtr = searchNodePtr1
        This.recent2NodeIndex = posNodeIndex2
        This.recent2NodePtr = searchNodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex2
        This.recent1NodePtr = searchNodePtr2
        This.recent2NodeIndex = posNodeIndex1
        This.recent2NodePtr = searchNodePtr1
    End If
    Return -1
End Function

Function DynamicArrayList.ShiftTheNthPosition(ByVal n As Integer, ByVal offset As Integer) As Integer
    ' Returns 0 on error, otherwise -1
   
    ' Converts index into positive index
    Dim As Integer posNodeIndex = IIf(n <= 0, This.nbrUserNode + n + 1, n)
    ' Tests index and offset validity
    If (posNodeIndex < 1) Or (posNodeIndex > This.nbrUserNode) Or (posNodeIndex + offset < 1) Or (posNodeIndex + offset > This.nbrUserNode) Or (offset = 0) Then Return 0
    ' search for the user node
    Dim As DoublyLinkedNode Ptr nodePtr2 = This.SearchNthPositionNode(posNodeIndex)
    Dim As DoublyLinkedNode Ptr nodePtr1
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent1NodeIndex = posNodeIndex
        This.recent1NodePtr = nodePtr2
    Else
        This.recent2NodeIndex = posNodeIndex
        This.recent2NodePtr = nodePtr2
    End If
    ' Shifts the user pointer by using a repeated swapping process
    If offset > 0 Then
        For I As Integer = 1 To Offset
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->nextNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    Else
        For I As Integer = -1 To Offset Step -1
            nodePtr1 = nodePtr2
            nodePtr2 = nodePtr2->prevNodePtr
            Swap nodePtr1->userPtr, nodePtr2->userPtr
        Next I
    End If
    ' Updates the recent visited node data
    If offset > 0 Then
        This.recent2NodeIndex = posNodeIndex + offset
        This.recent2NodePtr = nodePtr2
    Else
        This.recent1NodeIndex = posNodeIndex + offset
        This.recent1NodePtr = nodePtr2
    End If
    Return -1
End Function

Function DynamicArrayList.ReverseOrderOfPosition() As Integer
    ' Returns 0 on empty list, otherwise -1
   
    ' Tests empty list
    If This.nbrUserNode = 0 Then Return 0
    ' Swaps user pointers from the ends up to the middle
    Dim As DoublyLinkedNode Ptr leftNodePtr = @This.dummyNode, rightNodePtr = @This.dummyNode
    For I As Integer = 1 To This.nbrUserNode \ 2
        leftNodePtr = leftNodePtr->nextNodePtr
        rightNodePtr = rightNodePtr->prevNodePtr
        Swap rightNodePtr->userPtr, leftNodePtr->userPtr
    Next I
    Return -1
End Function

Function DynamicArrayList.ReturnArrayFromPosition(array() As Any Ptr) As Integer
    ' Returns the number of elements
    
    If This.nbrUserNode = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    ' sizes the passed array
    Redim array(1 To This.nbrUserNode)
    ' fills in the array with the user pointers
    For I As Integer = 1 To This.nbrUserNode
        nodePtr = nodePtr->nextNodePtr
        array(I) = nodePtr->userPtr
    Next I
    Return This.nbrUserNode
End Function

Function DynamicArrayList.LoadArrayIntoPosition(array() As Any Ptr) As Integer
    ' Return 0 if the list is not empty, otherwise returns the number of loaded elements
    
    If This.nbrUserNode > 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr = @This.dummyNode
    For I As Integer = Lbound(array) To Ubound(array)
        Dim As DoublyLinkedNode Ptr newNodePtr
        If This.preAllocNbr = This.nbrPreAllocDone Then
            ' Allocates memory for new node
            newNodePtr = Allocate(SizeOf(DoublyLinkedNode))
            If newNodePtr = 0 Then Return 0
        Else
            ' Uses pre-allocated memory
            newNodePtr = @This.preAllocPtr[This.preAllocNbr]
            This.nbrPreAllocUsed += 1
            This.preAllocNbr += 1
        End If
        ' Copies user pointer value in new node
        newNodePtr->userPtr = array(I)
        ' Updates pointers of previous and inserted nodes
        nodePtr->nextNodePtr = newNodePtr
        newNodePtr->prevNodePtr = nodePtr
        ' Inserted node becomes previous node
        nodePtr = newNodePtr
        ' Increments the number of user nodes
        This.nbrUserNode += 1
    Next I
    ' Updates pointer of last node and dummy node
    nodePtr->nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = nodePtr
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchForNthPosition(ByVal compare As Function(ByVal p As Any Ptr) As Boolean, ByVal startPosition As Integer = 1) As Integer
    ' Return 0 if the search failed, otherwise returns the position index of the first occurence found
    ' If startPosition > 0 (set of positive index used), the search begins at the startPosition index then continues in the increasing index order
    ' If startPosition < 0 (set of negative index used), the search begins at the startPosition index then continues in the decreasing index order (reverse order)
    ' The returned index uses the same set (positive or negative) of index than the one used for startPosition
    
    If compare = 0 Then Return 0
    Dim As DoublyLinkedNode Ptr nodePtr
    ' set of positive index used
    If (startPosition >= 1) And (startPosition <= This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(startPosition)
        For I As Integer = startPosition To This.nbrUserNode
            If compare(nodePtr->userPtr) = True Then Return I
            ' next node
            nodePtr = nodePtr->nextNodePtr
        Next I
    ' set of negative index used
    ElseIf (startPosition <= -1) And (startPosition >= -This.nbrUserNode) Then
        ' search start node
        nodePtr = This.SearchNthPositionNode(This.nbrUserNode + startPosition + 1)
        For I As Integer = startPosition To -This.nbrUserNode Step -1
            If compare(nodePtr->userPtr) = True Then Return I
            ' previous node
            nodePtr = nodePtr->prevNodePtr
        Next I
    End If
    Return 0
End Function

Sub DynamicArrayList.DestroyAllNthPosition(ByVal destroy As Sub(ByVal p As Any Ptr) = 0)
    ' Deallocates memory used by user nodes one by one by transverse access, including user data in the loop if destroy <> 0 is passed
    
    Dim As DoublyLinkedNode Ptr nodePtr = This.dummyNode.nextNodePtr
    If destroy <> 0 Then
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            destroy(nodePtr->prevNodePtr->userPtr)
            If (This.nbrPreAllocDone = 0) Orelse ((nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            End If
        Next I
    Else
        For I As Integer = 1 To This.nbrUserNode
            nodePtr = nodePtr->nextNodePtr
            If (This.nbrPreAllocDone = 0) Orelse ((nodePtr->prevNodePtr < @This.preAllocPtr[0]) Or (nodePtr->prevNodePtr > @This.preAllocPtr[This.nbrPreAllocDone - 1])) Then
                ' Deallocates memory for the node
                Deallocate(nodePtr->prevNodePtr)
            End If
        Next I
    End If
    ' Clears the number of user nodes
    This.nbrUserNode = 0
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodeIndex = 0
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodeIndex = 0
    This.recent2NodePtr = @This.dummyNode
    ' Initializes the preallocated memory use
    This.nbrPreAllocUsed = 0
    This.preAllocNbr = 0
End Sub

Function DynamicArrayList.ReturnNumberOfPosition() As Integer
    Return This.nbrUserNode
End Function

Function DynamicArrayList.SearchNthPositionNode(ByVal posNodeIndex As Integer) As DoublyLinkedNode Ptr
    Dim As DoublyLinkedNode Ptr nodePtr
    ' The node (among these 3) memorized closest to the targeted position
    ' is chosen as starting point of the iteration (forward or backward) through the nodes
    ' (3 * 2 = 6 cases)
    If posNodeIndex < This.recent1NodeIndex Then
        If posNodeIndex <= This.recent1NodeIndex - posNodeIndex Then
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    ElseIf posNodeIndex < This.recent2NodeIndex Then
        If posNodeIndex - This.recent1NodeIndex <= This.recent2NodeIndex - posNodeIndex Then
            ' recent #1 visited node closest to targeted position
            nodePtr = This.recent1NodePtr
            For I As Integer = This.recent1NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex - 1 To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    Else
        If posNodeIndex - This.recent2NodeIndex <= This.nbrUserNode + 1 - posNodeIndex Then
            ' recent #2 visited node closest to targeted position
            nodePtr = This.recent2NodePtr
            For I As Integer = This.recent2NodeIndex + 1 To posNodeIndex  ' forward iteration
                nodePtr = nodePtr->nextNodePtr
            Next I
        Else
            ' dummy node closest to targeted position
            nodePtr = @This.dummyNode
            For I As Integer = This.nbrUserNode To posNodeIndex Step -1 ' backward iteration
                nodePtr = nodePtr->prevNodePtr
            Next I
        End If
    End If
    Return nodePtr
End Function

Constructor DynamicArrayList()
    ' Loops the dummy node on itself
    This.dummyNode.nextNodePtr = @This.dummyNode
    This.dummyNode.prevNodePtr = @This.dummyNode
    ' Initializes the two recent visited nodes memory with the dummy node
    This.recent1NodePtr = @This.dummyNode
    This.recent2NodePtr = @This.dummyNode
End Constructor

Constructor DynamicArrayList(ByVal nbrPreAlloc As Integer)
    Constructor()
    If nbrPreAlloc > 0 Then
        ' Pre-allocates memory for nbrPreAlloc nodes
        This.preAllocPtr = Allocate(nbrPreAlloc * Sizeof(DoublyLinkedNode))
        If This.preAllocPtr > 0 Then This.nbrPreAllocDone = nbrPreAlloc
    End If
End Constructor

Destructor DynamicArrayList()
    ' Deallocates memory used by user nodes one by one by transverse access
    This.DestroyAllNthPosition()
    If This.nbrPreAllocDone > 0 Then
        ' Deallocates the pre-allocated memory
        Deallocate(This.preAllocPtr)
        This.nbrPreAllocDone = 0
    End If
End Destructor

- Test code:

Code: Select all

#include "DynamicArrayListWithPreAlloc.bi"

Sub PrintList(Byref dal As DynamicArrayList)
    Print "            list:";
    If dal.ReturnNumberOfPosition() = 0 Then
        Print " empty";
    Elseif dal.ReturnNumberOfPosition() <= 10 Then
        For I As Integer = 1 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    Else
        For I As Integer = 1 To 5
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
        Print " .....";
        For I As Integer = dal.ReturnNumberOfPosition() - 4 To dal.ReturnNumberOfPosition()
            Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
        Next I
    End If
    Print
End Sub

Sub destroy(Byval p As Any Ptr)
    Delete Cptr(Long Ptr, p)
End Sub

Sub test(Byval N As Integer)
    Dim As Double t
    
    Scope
        Print "Dynamic ArrayList (without pre-allocation) pointing to dynamic integers:"
        Print "   By acting only from the end of the list:"
        Print "      Time to increase the list step by step, up to " & N & " elements:"
        t = Timer
        Dim As DynamicArrayList dal
        For I As Integer = 1 To N
        dal.InsertInNthPosition(New Long(I), 0)
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "      Time to decrease the list step by step, up to 0 element:"
        t = Timer
        For I As Integer = 1 To N
            Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(-1))
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "   By acting only from the beginning of the list:"
        Print "      Time to increase the list step by step, up to " & N & " elements:"
        t = Timer
        For I As Integer = 1 To N
            dal.InsertInNthPosition(New Long(I), 1)
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "      Time to destroy the list in one shoot:"
        t = Timer
        dal.DestroyAllNthPosition(@destroy)
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print
    End Scope

    Scope
        Print "Dynamic ArrayList (with full pre-allocation) pointing to dynamic integers:"
        Print "   By acting only from the end of the list:"
        Print "      Time to increase the list step by step, up to " & N & " elements:"
        t = Timer
        Dim As DynamicArrayList dal = DynamicArrayList(N)
        For I As Integer = 1 To N
            dal.InsertInNthPosition(New Long(I), 0)
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "      Time to decrease the list step by step, up to 0 element:"
        t = Timer
        For I As Integer = 1 To N
            Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(-1))
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "   By acting only from the beginning of the list:"
        Print "      Time to increase the list step by step, up to " & N & " elements:"
        t = Timer
        For I As Integer = 1 To N
            dal.InsertInNthPosition(New Long(I), 1)
        Next I
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print "      Time to destroy the list in one shoot:"
        t = Timer
        dal.DestroyAllNthPosition(@destroy)
        t = Timer - t
        Print "         " & t & " s"
        PrintList(dal)
        Print
    End Scope
End Sub

Test(9000000)

Sleep
  • Output example:

    Code: Select all

    Dynamic ArrayList (without pre-allocation) pointing to dynamic integers:
       By acting only from the end of the list:
          Time to increase the list step by step, up to 9000000 elements:
             1.498154600001138 s
                list: 1 2 3 4 5 ..... 8999996 8999997 8999998 8999999 9000000
          Time to decrease the list step by step, up to 0 element:
             1.025472899999013 s
                list: empty
       By acting only from the beginning of the list:
          Time to increase the list step by step, up to 9000000 elements:
             1.406190900000343 s
                list: 9000000 8999999 8999998 8999997 8999996 ..... 5 4 3 2 1
          Time to destroy the list in one shoot:
             0.7894261999986991 s
                list: empty
    
    Dynamic ArrayList (with full pre-allocation) pointing to dynamic integers:
       By acting only from the end of the list:
          Time to increase the list step by step, up to 9000000 elements:
             0.9478515000013648 s
                list: 1 2 3 4 5 ..... 8999996 8999997 8999998 8999999 9000000
          Time to decrease the list step by step, up to 0 element:
             0.7321279999994452 s
                list: empty
       By acting only from the beginning of the list:
          Time to increase the list step by step, up to 9000000 elements:
             0.9181955000000759 s
                list: 9000000 8999999 8999998 8999997 8999996 ..... 5 4 3 2 1
          Time to destroy the list in one shoot:
             0.5359600999990555 s
                list: empty
    
fxm
Moderator
Posts: 12362
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Post by fxm »

fxm wrote: Oct 05, 2024 11:56 Dynamic ArrayList: Pre-allocating memory for nodes
.....
The user can set the number of pre-allocated nodes using an optional parameter at construction time.
.....
Improvement: about 30% at maximum (when only pre-allocated nodes are used) of speed up for insertion and suppression.

The reference posts 1/4 and 3/4 have been updated with this improved version of the 'DynamicArrayList' type:
added memory pre-allocating for nodes, set (or not) by the user at instance construction time.
fxm
Moderator
Posts: 12362
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Post by fxm »

File to include "DynamicArrayList.bi" : Added the 'NumberOfPreAllocAvailable' public property.

Tunning the pre-allocated memory size for nodes:
  • The number of pre-allocated nodes available throughout the execution is difficult to predict because it mainly depends on the configuration of the different suppressing sequences (in pre-allocated memory or not) compared to the inserting sequences:
    - Individual freed nodes in pre-allocated memory cannot generally be re-used, except the last used pre-allocated.
    - If all pre-allocated nodes are freed, the full pre-allocation memory becomes back available.

    As a result, this public property has been added.
The reference post 1/4 has been updated with this improved version of the 'DynamicArrayList' type:
added the 'NumberOfPreAllocAvailable' public property.
fxm
Moderator
Posts: 12362
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Dynamic ArrayList (with circular doubly linked list under the hood)

Post by fxm »

fxm wrote: Oct 19, 2024 16:10 File to include "DynamicArrayList.bi" : Added the 'NumberOfPreAllocAvailable' public property.

Tunning the pre-allocated memory size for nodes:
  • The number of pre-allocated nodes available throughout the execution is difficult to predict because it mainly depends on the configuration of the different suppressing sequences (in pre-allocated memory or not) compared to the inserting sequences:
    - Individual freed nodes in pre-allocated memory cannot generally be re-used, except the last used pre-allocated.
    - If all pre-allocated nodes are freed, the full pre-allocation memory becomes back available.

    As a result, this public property has been added.

- Very simple inserting/suppressing sequences to already understand the difficulty of predicting at any runtime the number of available pre-allocated nodes:

Code: Select all

#include "DynamicArrayList.bi"

Sub PrintList(Byref dal As DynamicArrayList)
    Print "   '";
    For I As Integer = 1 To dal.ReturnNumberOfPosition()
        Print *Cptr(Long Ptr, dal.ReturnFromNthPosition(I));
    Next I
    Print " '     => number of pre-allocated nodes now available : " & dal.NumberOfPreAllocAvailable
End Sub

Print "Creating an empty list with 4 pre-allocated nodes:"
Dim As DynamicArrayList dal = DynamicArrayList(4)
PrintList(dal)
Print
Print "----------------------------------------------------------------------"
Print
Print "Inserting 8 elements 1 by 1 from the end of the list:"
For I As Integer = 1 To 8
    dal.InsertInNthPosition(New Long(I), 0)
    PrintList(dal)
Next I
Print
Print "Suppressing all elements 1 by 1 from the end of the list:"
While dal.ReturnNumberOfPosition() > 0
    Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(-1))
    PrintList(dal)
Wend
Print
Print "----------------------------------------------------------------------"
Print
Print "Inserting 8 elements 1 by 1 from the beginning of the list:"
For I As Integer = 1 To 8
    dal.InsertInNthPosition(New Long(I), 1)
    PrintList(dal)
Next I
Print
Print "Suppressing all elements 1 by 1 from the beginning of the list:"
While dal.ReturnNumberOfPosition() > 0
    Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(1))
    PrintList(dal)
Wend
Print
Print "----------------------------------------------------------------------"
Print
Print "Inserting 8 elements 1 by 1 from the end of the list:"
For I As Integer = 1 To 8
    dal.InsertInNthPosition(New Long(I), 0)
    PrintList(dal)
Next I
Print
Print "Suppressing all elements 1 by 1 from the beginning of the list:"
While dal.ReturnNumberOfPosition() > 0
    Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(1))
    PrintList(dal)
Wend
Print
Print "----------------------------------------------------------------------"
Print
Print "Inserting 8 elements 1 by 1 from the beginning of the list:"
For I As Integer = 1 To 8
    dal.InsertInNthPosition(New Long(I), 1)
    PrintList(dal)
Next I
Print
Print "Suppressing all elements 1 by 1 from the end of the list:"
While dal.ReturnNumberOfPosition() > 0
    Delete Cptr(Long Ptr, dal.SuppressTheNthPosition(-1))
    PrintList(dal)
Wend
Print

Sleep
  • Output:

    Code: Select all

    Creating an empty list with 4 pre-allocated nodes:
       ' '     => number of pre-allocated nodes now available : 4
    
    ----------------------------------------------------------------------
    
    Inserting 8 elements 1 by 1 from the end of the list:
       ' 1 '     => number of pre-allocated nodes now available : 3
       ' 1 2 '     => number of pre-allocated nodes now available : 2
       ' 1 2 3 '     => number of pre-allocated nodes now available : 1
       ' 1 2 3 4 '     => number of pre-allocated nodes now available : 0
       ' 1 2 3 4 5 '     => number of pre-allocated nodes now available : 0
       ' 1 2 3 4 5 6 '     => number of pre-allocated nodes now available : 0
       ' 1 2 3 4 5 6 7 '     => number of pre-allocated nodes now available : 0
       ' 1 2 3 4 5 6 7 8 '     => number of pre-allocated nodes now available : 0
    
    Suppressing all elements 1 by 1 from the end of the list:
       ' 1 2 3 4 5 6 7 '     => number of pre-allocated nodes now available : 0
       ' 1 2 3 4 5 6 '     => number of pre-allocated nodes now available : 0
       ' 1 2 3 4 5 '     => number of pre-allocated nodes now available : 0
       ' 1 2 3 4 '     => number of pre-allocated nodes now available : 0
       ' 1 2 3 '     => number of pre-allocated nodes now available : 1
       ' 1 2 '     => number of pre-allocated nodes now available : 2
       ' 1 '     => number of pre-allocated nodes now available : 3
       ' '     => number of pre-allocated nodes now available : 4
    
    ----------------------------------------------------------------------
    
    Inserting 8 elements 1 by 1 from the beginning of the list:
       ' 1 '     => number of pre-allocated nodes now available : 3
       ' 2 1 '     => number of pre-allocated nodes now available : 2
       ' 3 2 1 '     => number of pre-allocated nodes now available : 1
       ' 4 3 2 1 '     => number of pre-allocated nodes now available : 0
       ' 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
       ' 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
       ' 7 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
       ' 8 7 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
    
    Suppressing all elements 1 by 1 from the beginning of the list:
       ' 7 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
       ' 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
       ' 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
       ' 4 3 2 1 '     => number of pre-allocated nodes now available : 0
       ' 3 2 1 '     => number of pre-allocated nodes now available : 1
       ' 2 1 '     => number of pre-allocated nodes now available : 2
       ' 1 '     => number of pre-allocated nodes now available : 3
       ' '     => number of pre-allocated nodes now available : 4
    
    ----------------------------------------------------------------------
    
    Inserting 8 elements 1 by 1 from the end of the list:
       ' 1 '     => number of pre-allocated nodes now available : 3
       ' 1 2 '     => number of pre-allocated nodes now available : 2
       ' 1 2 3 '     => number of pre-allocated nodes now available : 1
       ' 1 2 3 4 '     => number of pre-allocated nodes now available : 0
       ' 1 2 3 4 5 '     => number of pre-allocated nodes now available : 0
       ' 1 2 3 4 5 6 '     => number of pre-allocated nodes now available : 0
       ' 1 2 3 4 5 6 7 '     => number of pre-allocated nodes now available : 0
       ' 1 2 3 4 5 6 7 8 '     => number of pre-allocated nodes now available : 0
    
    Suppressing all elements 1 by 1 from the beginning of the list:
       ' 2 3 4 5 6 7 8 '     => number of pre-allocated nodes now available : 0
       ' 3 4 5 6 7 8 '     => number of pre-allocated nodes now available : 0
       ' 4 5 6 7 8 '     => number of pre-allocated nodes now available : 0
       ' 5 6 7 8 '     => number of pre-allocated nodes now available : 4
       ' 6 7 8 '     => number of pre-allocated nodes now available : 4
       ' 7 8 '     => number of pre-allocated nodes now available : 4
       ' 8 '     => number of pre-allocated nodes now available : 4
       ' '     => number of pre-allocated nodes now available : 4
    
    ----------------------------------------------------------------------
    
    Inserting 8 elements 1 by 1 from the beginning of the list:
       ' 1 '     => number of pre-allocated nodes now available : 3
       ' 2 1 '     => number of pre-allocated nodes now available : 2
       ' 3 2 1 '     => number of pre-allocated nodes now available : 1
       ' 4 3 2 1 '     => number of pre-allocated nodes now available : 0
       ' 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
       ' 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
       ' 7 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
       ' 8 7 6 5 4 3 2 1 '     => number of pre-allocated nodes now available : 0
    
    Suppressing all elements 1 by 1 from the end of the list:
       ' 8 7 6 5 4 3 2 '     => number of pre-allocated nodes now available : 0
       ' 8 7 6 5 4 3 '     => number of pre-allocated nodes now available : 0
       ' 8 7 6 5 4 '     => number of pre-allocated nodes now available : 0
       ' 8 7 6 5 '     => number of pre-allocated nodes now available : 4
       ' 8 7 6 '     => number of pre-allocated nodes now available : 4
       ' 8 7 '     => number of pre-allocated nodes now available : 4
       ' 8 '     => number of pre-allocated nodes now available : 4
       ' '     => number of pre-allocated nodes now available : 4
    

- More turbulent example with a reproducible pseudo-random sequence for the inserting then suppressing positions (list of 26 elements with 26 pre-allocated nodes):

Code: Select all

#include "DynamicArrayList.bi"

Sub PrintList(Byref dal As DynamicArrayList)
    Print "   '";
    For I As Integer = 1 To dal.ReturnNumberOfPosition()
        Print *Cptr(String Ptr, dal.ReturnFromNthPosition(I));
    Next I
    Print "'   => nbr of pre-alloc nodes now available : " & dal.NumberOfPreAllocAvailable
End Sub

Print "Creating an empty list with 26 pre-allocated nodes:"
Dim As DynamicArrayList dal = DynamicArrayList(26)
PrintList(dal)
Print
Print "Inserting 26 elements 1 by 1 at randomly position:"
For I As Integer = 1 To 26
    Dim As Integer N = Int(Rnd() * (dal.ReturnNumberOfPosition() + 1) + 1)
    dal.InsertInNthPosition(New String(Chr(64 + I)), N)
    PrintList(dal)
Next I
Print
Print "Suppressing all elements 1 by 1 at randomly position:"
While dal.ReturnNumberOfPosition() > 0
    Dim As Integer N = Int(Rnd() * dal.ReturnNumberOfPosition() + 1)
    Delete Cptr(String Ptr, dal.SuppressTheNthPosition(N))
    PrintList(dal)
Wend
Print

Sleep
  • Output:

    Code: Select all

    Creating an empty list with 26 pre-allocated nodes:
       ''   => nbr of pre-alloc nodes now available : 26
    
    Inserting 26 elements 1 by 1 at randomly position:
       'A'   => nbr of pre-alloc nodes now available : 25
       'BA'   => nbr of pre-alloc nodes now available : 24
       'BCA'   => nbr of pre-alloc nodes now available : 23
       'BCAD'   => nbr of pre-alloc nodes now available : 22
       'BCAED'   => nbr of pre-alloc nodes now available : 21
       'BCAFED'   => nbr of pre-alloc nodes now available : 20
       'BCGAFED'   => nbr of pre-alloc nodes now available : 19
       'BCGAFEDH'   => nbr of pre-alloc nodes now available : 18
       'BCGAFEDHI'   => nbr of pre-alloc nodes now available : 17
       'BCGAFEDHIJ'   => nbr of pre-alloc nodes now available : 16
       'BCGAFKEDHIJ'   => nbr of pre-alloc nodes now available : 15
       'BCGAFKEDLHIJ'   => nbr of pre-alloc nodes now available : 14
       'MBCGAFKEDLHIJ'   => nbr of pre-alloc nodes now available : 13
       'MBCGAFKEDNLHIJ'   => nbr of pre-alloc nodes now available : 12
       'OMBCGAFKEDNLHIJ'   => nbr of pre-alloc nodes now available : 11
       'OMBCGAFPKEDNLHIJ'   => nbr of pre-alloc nodes now available : 10
       'QOMBCGAFPKEDNLHIJ'   => nbr of pre-alloc nodes now available : 9
       'QOMBCGAFRPKEDNLHIJ'   => nbr of pre-alloc nodes now available : 8
       'QOMBCGAFRPKEDNLSHIJ'   => nbr of pre-alloc nodes now available : 7
       'QOMBCGAFRPKEDNLSTHIJ'   => nbr of pre-alloc nodes now available : 6
       'QOMBCGAFRPKEDNLSTHUIJ'   => nbr of pre-alloc nodes now available : 5
       'QOMBCVGAFRPKEDNLSTHUIJ'   => nbr of pre-alloc nodes now available : 4
       'QOMBCVGWAFRPKEDNLSTHUIJ'   => nbr of pre-alloc nodes now available : 3
       'QOMBCVGWAFRXPKEDNLSTHUIJ'   => nbr of pre-alloc nodes now available : 2
       'QOMBCVGWAFYRXPKEDNLSTHUIJ'   => nbr of pre-alloc nodes now available : 1
       'QOMBCVGWAFYRXPZKEDNLSTHUIJ'   => nbr of pre-alloc nodes now available : 0
    
    Suppressing all elements 1 by 1 at randomly position:
       'QOMBCVGWAFYRXPZKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 0
       'QOMBCVWAFYRXPZKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 0
       'QOMBVWAFYRXPZKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 0
       'QOMBVWAFYRXPKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 1
       'QOMBVWAFRXPKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 2
       'QOMBVWFRXPKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 2
       'QOMBVWFRPKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 3
       'QOMBVFRPKEDNLSTUIJ'   => nbr of pre-alloc nodes now available : 4
       'QOMBVFRPKEDNLSTIJ'   => nbr of pre-alloc nodes now available : 4
       'QOMBVFRPEDNLSTIJ'   => nbr of pre-alloc nodes now available : 4
       'QOMBFRPEDNLSTIJ'   => nbr of pre-alloc nodes now available : 5
       'QOMBFRPEDNSTIJ'   => nbr of pre-alloc nodes now available : 5
       'QOMBFRPEDNTIJ'   => nbr of pre-alloc nodes now available : 5
       'QOMBFREDNTIJ'   => nbr of pre-alloc nodes now available : 5
       'QOMBREDNTIJ'   => nbr of pre-alloc nodes now available : 5
       'QOMBRENTIJ'   => nbr of pre-alloc nodes now available : 5
       'QOMBRENTI'   => nbr of pre-alloc nodes now available : 5
       'QOMRENTI'   => nbr of pre-alloc nodes now available : 5
       'QOMRNTI'   => nbr of pre-alloc nodes now available : 5
       'QOMRTI'   => nbr of pre-alloc nodes now available : 5
       'QOMRI'   => nbr of pre-alloc nodes now available : 5
       'QORI'   => nbr of pre-alloc nodes now available : 5
       'QOR'   => nbr of pre-alloc nodes now available : 5
       'QO'   => nbr of pre-alloc nodes now available : 5
       'Q'   => nbr of pre-alloc nodes now available : 5
       ''   => nbr of pre-alloc nodes now available : 26
    
Last edited by fxm on Oct 20, 2024 18:24, edited 3 times in total.
Reason: Added more turbulent example with a reproducible pseudo-random sequence for the inserting then suppressing positions.
Post Reply