Linked Lists Memory Management

Just starting out? Need help? Post your questions and find answers here.
HannesH
User
User
Posts: 14
Joined: Fri Dec 09, 2011 5:54 pm

Linked Lists Memory Management

Post by HannesH »

I came across a memory management problem with linked lists.

It took me some effort to create a minimum example.

Some snippets first (a minimum working example follows further down):

Code: Select all

Structure CP_TYPE
  dDummy1.d
  dDummy2.d
EndStructure  

Structure Arg_TYPE
  dummy1.l
  List CP.CP_TYPE()
EndStructure  

w1.Arg_TYPE
w2.Arg_TYPE

For i = 1 To #Elements
  AddElement(w1\CP())  
  AddElement(w2\CP())  
Next

; this seems just fine:  
;   For i = 1 To #Elements
;     AddElement(w1\CP())  
;   Next
;   For i = 1 To #Elements
;     AddElement(w2\CP())  
;   Next

ClearList(w1\CP())

ClearList clears the w1 list. However, it does not free the associated memory. Only when also
the w2 list is cleared, the memory is completely freed (and vice versa).
I my original code, elements are added at various places to the w1 and w2 lists.
Of course, I don't want to clear both list to get the memory back. I do not get any errors. ClearList
does not have a return value to tell that freeing did not occur.
It seem the two lists are somehow connected in terms of memory management.

Am I doing something wrong or is this a bug? A workaround to clear just one list with freed memory is deeply appreciated.

This problem also occurs when using DeleteElement on either w1 or w2, the memory only gets freed
dependent on the other list. I expect the lists to be independent.

Minimum Example

Code: Select all


Enumeration
  #PSAPI_DLL_LIB
EndEnumeration  

#Elements = 2000000

Structure CP_TYPE
  dDummy1.d
  dDummy2.d
EndStructure  

Structure Arg_TYPE
  dummy1.l
  List CP.CP_TYPE()
EndStructure  

w1.Arg_TYPE
w2.Arg_TYPE

Prototype GetProcessMemoryInfo( hProcess, *address, size )
If Not OpenLibrary(#PSAPI_DLL_LIB, "psapi.dll")
  MessageBox_(0,"Failed to open library psapi.dll","Error",#MB_OK | #MB_ICONERROR | #MB_SETFOREGROUND | #MB_TOPMOST)
  End
EndIf  
;  Debug "  psapi.dll open"
Global GetProcessMemoryInfo_.GetProcessMemoryInfo = GetFunction(#PSAPI_DLL_LIB, "GetProcessMemoryInfo")

Procedure.d GetWorkingSetSize_MB()
   pmc.PROCESS_MEMORY_COUNTERS
   If GetProcessMemoryInfo_(GetCurrentProcess_(), pmc, SizeOf(PROCESS_MEMORY_COUNTERS))
     ProcedureReturn pmc\WorkingSetSize / (1024 * 1024)
   Else   
     ProcedureReturn 0
   EndIf  
 EndProcedure
 
  
If OpenConsole()
  
  initial_size.d = GetWorkingSetSize_MB()
  PrintN("Initial Size: " + StrD(initial_size,2) + " MB")
    
  ; creating the lists
  ; the trouble version: (this causes the memory management to be somewhat interlaced, freeing the memory becomes unreliable)
  For i = 1 To #Elements
    AddElement(w1\CP())  
    AddElement(w2\CP())  
  Next
    
  
  ; this seems just fine:  
;   For i = 1 To #Elements
;     AddElement(w1\CP())  
;   Next
;   For i = 1 To #Elements
;     AddElement(w2\CP())  
;   Next
  
  
;   For each element the size shall increase by
;     - the size of CP_TYPE
;     - 2 pointers For *next And *previous
;     - some additional overhead For memory management: 4 bytes on x86 (LinkedList memory management on Team Blog) And 8 bytes on x64 measured here
  
;   expected_element_size.l = SizeOf(CP_TYPE) + 2 * SizeOf(integer)
;   PrintN("expected element size: " + Str(expected_element_size))
;   consumed_bytes_per_element.l = 1024*1024*(GetWorkingSetSize_MB() - initial_size) / ( 2 * #Elements)
;   PrintN("consumed bytes per element: " + Str(consumed_bytes_per_element))
;   PrintN("management overhead: " + Str(consumed_bytes_per_element - expected_element_size) + " bytes per element")
  
  PrintN("Size with " + Str(ListSize(w1\CP())) + " w1 elements and " + Str(ListSize(w2\CP())) + " w2 elements: " + StrD(GetWorkingSetSize_MB(),2) + " MB")
  
  ; clearing the w1 list
  ClearList(w1\CP())
  ;  alternatively:
  ;  While DeleteElement(w1\CP())
  ;  Wend  
  PrintN("Size with " + Str(ListSize(w1\CP())) + " w1 elements and " + Str(ListSize(w2\CP())) + " w2 elements: " + StrD(GetWorkingSetSize_MB(),2) + " MB")
  ; the w1 list appears to be cleared but the associated memory is not freed. Using DeleteElement isn't freeing the memory either
    
  ; now clear the w2 list
  ClearList(w2\CP())
  PrintN("Size with " + Str(ListSize(w1\CP())) + " w1 elements and " + Str(ListSize(w2\CP())) + " w2 elements: " + StrD(GetWorkingSetSize_MB(),2) + " MB")
  ; add suddenly all of the memory gets freed!
  
  PrintN("Any key to end.")
  String$ = Input()

  CloseConsole()
EndIf
End

User avatar
Demivec
Addict
Addict
Posts: 4086
Joined: Mon Jul 25, 2005 3:51 pm
Location: Utah, USA

Re: Linked Lists Memory Management

Post by Demivec »

The entry in the PureBasic Blog entitled 'LinkedList memory management' covers a description of your problem and the cause.

http://www.purebasic.fr/blog/?p=8

The entry in the blog seems to indicate that if all the elements were freed you shouldn't have a problem. There may be another element to the memory management that needs to be tweaked to fix this.
HannesH
User
User
Posts: 14
Joined: Fri Dec 09, 2011 5:54 pm

Re: Linked Lists Memory Management

Post by HannesH »

I've read that blog entry (and the paper to some extent). I also do understand the concept of
array lists, which this is basically all about.

"The bigger problem arises when freeing part of the list. A block can only be freed when all its elements are unused. Consider the (highly unlikely) case that i use the list above, then free all elements but 2000 of them and unlucky as i am, there is exactly one element remaining on every single memory block. This means no memory is freed at all."

But we're talking about two (or more) separate lists. Are they sharing such blocks?
Or - and that's what I strongly hope/suggest - do separate lists have their own blocks?

Unfortunately the given link to the paper isn't valid anymore but Jeff Bonwicks article "The Slab Allocator: An Object-Caching Kernel Memory Allocator" can be found here: https://www.usenix.org/legacy/publicati ... /bonwick.a
freak
PureBasic Team
PureBasic Team
Posts: 5929
Joined: Fri Apr 25, 2003 5:21 pm
Location: Germany

Re: Linked Lists Memory Management

Post by freak »

In our original implementation every list had its own allocator and ClearList() could just free all memory managed by the allocator. But the addition of the SplitList() and MergeLists() commands made that impossible since you can now move elements between lists.

This is why lists with equal element sizes now share an allocator.
quidquid Latine dictum sit altum videtur
HannesH
User
User
Posts: 14
Joined: Fri Dec 09, 2011 5:54 pm

Re: Linked Lists Memory Management

Post by HannesH »

Thanks for the short and precise answer; it explains all my oberservations! Not a bug but a price paid for other features.

Conclusion:

Code: Select all

  For i = 1 To #Elements
    AddElement(w1\CP())  
    AddElement(w2\CP())  
  Next
creates list elements managed by the same allocator since both CP lists have the same structure size. In this
example the elements are simply interleaved.

Therefore,

Code: Select all

ClearList(w1\CP())
will only delete every second entry. Hence, no (or almost no) memory blocks are released.

However, the following scheme allows to rearange the memory and therefore, free the unused memory:

Code: Select all

; and w2 can be "compressed" like this:
*mem = AllocateMemory(SizeOf(CP_TYPE))
ForEach w2\CP()
  CopyMemory(w2\CP(),*mem,SizeOf(CP_TYPE))
  DeleteElement(w2\CP())
  AddElement(w2\CP())
  CopyMemory(*mem,w2\CP(),SizeOf(CP_TYPE))
Next
FreeMemory(*mem)
The following assumptions guide to the above rearrange scheme:
  • - New elements are positioned at the first available free position in memory.
  • - The ForEach does not change the index while Add/Delete occurr within the loop.

...
Post Reply