[SOLVED] What is the name of the default memory allocator in Free Pascal?

[flowCRANE]

Free Pascal has a default memory allocator (or memory manager if you prefer) and its implementation is in the heaph.inc file. What kind of allocator is this? Any known algorithm, and if so, what is it called? I checked the documentation and even the sources, but unfortunately I did not find such information.

[jamie]

GetmemoryManager ?

It populates a TmemoryManager record you supply.

[flowCRANE]

No, that's not the point. The heaph.inc file contains the following functions:

Code: Pascal  [Select][+][-]

1. Function  SysGetmem(Size:ptruint):Pointer;
2. Function  SysFreemem(p:pointer):ptruint;
3. Function  SysFreememSize(p:pointer;Size:ptruint):ptruint;
4. Function  SysMemSize(p:pointer):ptruint;
5. Function  SysAllocMem(size:ptruint):Pointer;
6. function  SysTryResizeMem(var p:pointer;size:ptruint):Boolean;
7. Function  SysReAllocMem(var p:pointer;size:ptruint):Pointer;
8. function  SysGetHeapStatus:THeapStatus;
9. function  SysGetFPCHeapStatus:TFPCHeapStatus;

They are set as default in the memory manager:

Code: Pascal  [Select][+][-]

1. const
2.   MemoryManager: TMemoryManager = (
3.     NeedLock: false;  // Obsolete
4.     GetMem: {$ifndef FPC_NO_DEFAULT_HEAP}@SysGetMem{$else}nil{$endif};
5.     FreeMem: {$ifndef FPC_NO_DEFAULT_HEAP}@SysFreeMem{$else}nil{$endif};
6.     FreeMemSize: {$ifndef FPC_NO_DEFAULT_HEAP}@SysFreeMemSize{$else}nil{$endif};
7.     AllocMem: {$ifndef FPC_NO_DEFAULT_HEAP}@SysAllocMem{$else}nil{$endif};
8.     ReAllocMem: {$ifndef FPC_NO_DEFAULT_HEAP}@SysReAllocMem{$else}nil{$endif};
9.     MemSize: {$ifndef FPC_NO_DEFAULT_HEAP}@SysMemSize{$else}nil{$endif};
10.     InitThread: nil;
11.     DoneThread: nil;
12.     RelocateHeap: nil;
13.     GetHeapStatus: {$ifndef FPC_NO_DEFAULT_HEAP}@SysGetHeapStatus{$else}nil{$endif};
14.     GetFPCHeapStatus: {$ifndef FPC_NO_DEFAULT_HEAP}@SysGetFPCHeapStatus{$else}nil{$endif};
15.   );

They bodies are in the heap.inc file and contain application-side memory management code to minimize the use of the Windows HeapAlloc and HeapFree functions to increase allocation and deallocation efficiency. Is the code of these functions a port of some well-known allocator that has its own name and is described somewhere (such as mimalloc), or was it invented entirely by Free Pascal developers?

[Thaddy]

It was written from scratch by the FPC developers, but to a known, common pattern: bucketlist based allocators. The same pattern is e.g. used in Delphi too, with a completely different implementation based on FastMM. I have also seen implementations for C and C++, but in these languages the default is a simple heap based allocator. we can use that too: the implementation is in cmem.pas.
Bucket based allocators are less prone to heap memory fragmentation in the average use case.

In compiler shoot-outs, languages that have bucket based allocators usually have more efficient use of memory sizes, whereas heap based memory allocators favor speed over memory size.
a note of warning, though: the choice of a memory manager may depend on a specific use case.

[marcov]

Afaik the default FPC allocator also has per thread allocation/deallocation to avoid unnecessary locks.  That also has advantages and disadvantages, the positive is that allocating small amounts in a thread requires less locks, But it uses a bit more memory , and cross thread (allocate in one, deallocate in another) becomes more expensive.

[MarkMLl]

Afaik the default FPC allocator also has per thread allocation/deallocation to avoid unnecessary locks.  That also has advantages and disadvantages, the positive is that allocating small amounts in a thread requires less locks, But it uses a bit more memory , and cross thread (allocate in one, deallocate in another) becomes more expensive.

I believe you are correct, I remember discussing this with Jonas.

MarkMLl

[flowCRANE]

Ok, thanks for the answers. Is it described somewhere so that I can learn how exactly this implementation works?

[PascalDragon]

Is it described somewhere so that I can learn how exactly this implementation works?

If you want to learn how it works, look at the source code.

[flowCRANE]

What else is left if there is no documentation. Thanks.

[Thaddy]

Well, the internals, read the sourcecode, the design pattern and theory: google on bucket based memory allocation.
What else is not documented? Bloody irritating since I already explained it.

[n7800]

If anyone is still interested (I'm sure many are), there is some documentation about the memory manager. Is also a description of the "cmem" manager, which is in a separate compiler package.


By the way, in the compiler folder "<fpc-scr-dir>\packages\libgc\src\gcmem.pp" there is another one : "Boehm garbage collector memory manager".


In the source code of "heap.inc" I see a very detailed comment (one of many):

Code: [Select]

  Fixed os chunks can be converted to variable os chunks and back
  (if not too big). To prevent repeated conversion overhead in case
  of user freeing/allocing same or a small set of sizes, we only do
  the conversion to the new fixed os chunk size format after we
  reuse the os chunk for another fixed size, or variable. Note that
  while the fixed size os chunk is on the freelists.oslist, it is also
  still present in a freelists.fixedlists, therefore we can easily remove
  the os chunk from the freelists.oslist if this size is needed again; we
  don't need to search freelists.oslist in alloc_oschunk, since it won't
  be present anymore if alloc_oschunk is reached. Note that removing
  from the freelists.oslist is not really done, only the recycleflag is
  set, allowing to reset the flag easily. alloc_oschunk will clean up
  the list while passing over it, that was a slow function anyway.


But the repository history will show the maximum amount of information. For example, running [git log "*heap.inc"] shows many interesting commits (it is curious to see them with dates: --format="%cs %s"). You can see how improvements for multithreading were added, block sizes were changed, bugs were fixed... There are even recent commits.

[marcov]

Did you check the wiki? I'm not sure if there is anything in it, but afaik Micha who did the thread stuff wrote in the wiki often too.

[n7800]

There is no wiki user named "Micha". Searching by keywords I found only good articles about efficient memory usage, not its structure (there are only small notes). But this is expected, considering that the wiki is mainly aimed at end users.

[marcov]

His alias was "Neli" afaik.

[n7800]

Nothing on this topic.