Stack Classes: New Attempt lazarus / 21-General ---------------------------------------------------------------------- Warfley · 2023-07-12 17:00 After some discussions in some of the other threads here I was a bit intrigued with the idea of how to build Stack based classes. It is generally possible through overriding NewInstance and FreeInstance for a class. But this has three major drawbacks. First you need to pre-allocate the memory on the stack to then feed into NewInstance, as it has it's own stack frame you can't allocate stack memory in there. And the second problem is that you need to still call the Destructor, so while the class is on the stack, you still need to do manual memory management, making it little better than already existing objects. Aside from that the third problem is that the stack locality would be bound to the class type, and you can only do this with custom classes that have been specifically built for that. So I had an idea of solving these Problems in a slightly different attempt, including a Managed Record as Stack Allocator, which will allocate memory on the stack frame it is called from, and will automatically free all allocations in it's finalization. The code is actually quite simple: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i unit StackAllocator; {$mode ObjFPC}{$H+}{$AsmMode intel}{$ModeSwitch advancedrecords} interface type   { TStackAllocator }   TStackAllocator = record  private type    PAllocMem = ^TAllocMem;    TAllocMem = record      PreviousAlloc: PAllocMem; // Allocations form linked list to allow freeing them      ClassData: record end; // Empty Data (Size -> 0) because we just grab a pointer from here    end;  private    FLastAlloc: PAllocMem;   public     class operator Initialize(var Allocator: TStackAllocator);    class operator Finalize(var Allocator: TStackAllocator);      function AllocateClass(cls: TClass): TObject;    generic function Allocate: T; inline; // If not inlined this creates a stack frame at it won't work  end; implementation threadvar  TempStack: Array[0..1023] of Byte; // Global variable where we will temporary move to { TStackAllocator } class operator TStackAllocator.Initialize(var Allocator: TStackAllocator);begin  Allocator.FLastAlloc := nil;end; class operator TStackAllocator.Finalize(var Allocator: TStackAllocator);begin  while Assigned(Allocator.FLastAlloc) do  begin    // FIXME: Memory Manager trying to free on stack causes exception    // Only usable with custom class overloading FreeInstance    TObject(@Allocator.FLastAlloc^.ClassData).Destroy;    Allocator.FLastAlloc := Allocator.FLastAlloc^.PreviousAlloc;  end;end; function TStackAllocator.AllocateClass(cls: TClass): TObject;var  StackPtr: Pointer = Nil;  BasePtr: Pointer;  NewStackPtr, NewBasePtr: Pointer;  FrameSize, AllocaSize: SizeInt;  InsertionPoint: PAllocMem;begin  (*  Stack Memory Layout  Low      -> +-----------------+              |       ...       |              +-----------------+  RSP      -> |  Lo(LastLocal)  |\              +     ...       + \              |  Hi(LastLocal)  |  \              +-----------------+   \              |   Locals [...]  |    )            +-----------------+    )  / Stack part of the current function  RBP      -> |   Lo(PrevRBP)   |    ) <  Move up to make room for allocation              +       ...       +    )  \ Then allocate on previous stack frame              |   Hi(PrevRBP)   |    )            +-----------------+   /  RBP + 8  -> |   Lo(RetAddr)   |  /            +       ...       + /              |   Hi(RetAddr)   |/              +-----------------+  <- Insertion point for allocation  RBP + 16 -> | Locals(LastFrm) |                |       ...       |  High     -> +-----------------+  *)   // Allocate Structure of TAllocMem + Class Data  AllocaSize := SizeOf(TAllocMem) + cls.InstanceSize;   // In order to being able to call functions and use local variables  // while changing the stack, we will operate on a copy of the stack  // This should be doable also registers only in ASM, but I am very lazy  asm  MOV StackPtr, RSP  MOV BasePtr, RBP  end;  // This framesize does not contain the previous RBP nor the return address  // But this is enough as we never intend to return from the temp stack  FrameSize := BasePtr - StackPtr;  NewBasePtr := @TempStack[High(TempStack)];  NewStackPtr := NewBasePtr - FrameSize;  Move(PByte(StackPtr)^, PByte(NewStackPtr)^, FrameSize);  // Move to the temp stack  asm  MOV RSP, NewStackPtr  MOV RBP, NewBasePtr  end;   // Move everything before insertion point up the stack to make room for allocation  // Framesize does not include prevRBP nor RetAddr, so add 2*Ptr  Move(PByte(StackPtr)^, PByte(StackPtr - AllocaSize)^, FrameSize + SizeOf(Pointer) * 2);  // And update the references  StackPtr -= AllocaSize;  BasePtr -= AllocaSize;   // We insert after the base pointer and the return address, both have SizeOf(Pointer)  InsertionPoint := PAllocMem(BasePtr + 2 * SizeOf(Pointer));  InsertionPoint^.PreviousAlloc := FLastAlloc;  FLastAlloc := InsertionPoint;   // Move back to old stack  asm  MOV RSP, StackPtr  MOV RBP, BasePtr  end;  // Note all the computations in the local variables above are on the temp stack  // As we are now on the original stack, we don't have access to them anymore  // So we will just use the Self Reference to create the result  Result := cls.InitInstance(@FLastAlloc^.ClassData);  (************************** **************************************************)  (*                                 FIXME                                  *)  (*         When the Destructor is Called FreeInstance is called           *)  (*      This usually frees the memory before cleaning up managed fields     *)  (*          We want to skip the Free and only call CleanupInstance          *)  (*       But somehow overriding it directly in ther VMT does not work       *)  (*                          TODO: Find out why                            *)  (*************** *************************************************************)  // PVMT(Result)^.vFreeInstance := @TObject.CleanupInstance;end; generic function TStackAllocator.Allocate: T;begin  Result := T(AllocateClass(T));end; end.  And it can be used like this: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program project1; {$mode Delphi} uses  Classes, StackAllocator; type  // Because the runtime overriding using the VMT does not work  // We need to override FreeInstance manually here  TStackStringList = class(TStringList)  public    procedure FreeInstance; override;  end; procedure TStackStringList.FreeInstance;begin  CleanupInstance;end; procedure Smack;var  arr: array[0..1023] of Byte;begin  FillChar(arr, SizeOf(arr), $FF);end; procedure TestStack;var  alloc: TStackAllocator;  sl: TStringList;begin  // Only works because it is inlined, if message "marked as inline is not inlined", it will fail  sl := alloc.Allocate.Create;  sl.Add('Foo');   Smack;  sl.Add('Bar');  WriteLn(sl.Text);end; begin  TestStack;  ReadLn;end. How it works is quite simple, it extends the stack from the function that calls the allocator, by simply moving the current stackframe up the stack, and this newly created gap between the moved stack frame and the old stack frame will be the new stack frame for the class. To free the class, the allocator actually also allocates a bit more space for a pointer to the last allocated structure. This way all stack allocations form a linked list which can be traversed to call their destructor when the managed record is finalized. But, this only solves problems one and two, as seen in the example I still need to define my own TStackStringList to override FreeInstance to not free the memory, but only call CleanupInstance to clear all managed data fields of the class. My Idea for that was to change the function in the VMT of the stack allocated object, as can be seen in the end of the AllocateClass method: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   // PVMT(Result)^.vFreeInstance := @TObject.CleanupInstance;But this seems to not work so far. Generally speaking, I haven't tested this that much. When I use heaptrc in this code, it starts throwing errors, but they are not due to the allocation of the classes, but due to the internal allocations of TStringList and I don't know why (maybe non aligned pointers?). With creating a custom class that does not allocations in the background (as TStringList does for it's strings), not a single byte of heap memory will be allocated. So I don't know whats about that. Also due to the fact that I'm currently on Windows I haven't tested it on anything else, let alone with some testing tools like valgrind. And lastly, as written before I have no idea why the runtime change of the VMT for the FreeInstance function is not working. If someone has an idea about that, please let me know ---------------------------------------------------------------------- Ryan J · 2023-07-15 03:46 This is interesting but of course a big hack and probably extremely slow due to all the required boilerplate. Isn't what we really want here a deferred free? That seems like the simplest thing FPC could give  us to make memory management of classes less manual and cover a large number of the cases that plague us (freeing a class when the function terminate). Otherwise I think if the object model in FPC was unified we could simply declare a class on the stack or heap and the compiler would do the right thing for us. I don't have the experience to know but does that work well for C++? It seems very reasonable to me and when I have done C++ it worked very well, albeit in tiny programs. ---------------------------------------------------------------------- Red_prig · 2023-07-15 18:13 Not so long ago I tested the allocation of data on the stack, but in the end I partially abandoned this, it turned out that when optimizing -O3, the compiler starts using registers for stack frames differently and the code breaks))) In the end, the best and easiest option was allocation method on the stack but on the other sides))) ---------------------------------------------------------------------- Warfley · 2023-07-15 21:27 Quote from: Ryan J on July 15, 2023, 05:46:59 amThis is interesting but of course a big hack and probably extremely slow due to all the required boilerplate. Isn't what we really want here a deferred free? That seems like the simplest thing FPC could give  us to make memory management of classes less manual and cover a large number of the cases that plague us (freeing a class when the function terminate).You should not underestimate how slow heap allocations are. This code is extremly unoptimized, as I have written in a comment, this code moves to a temporary stack in order to change the current stack. I did this because I really like using variables and calling functions, but you could rewrite this completely in assembly only using registers, and therefore avoid most of the overhead. Even though when putting it to a benchmark: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i uses  StackAllocator, SysUtils; type  TBaseClass = class  private    FX: Double;    FY: Double;   public    constructor Create(AX, AY: Double);  end;   TStackClass = class(TBaseClass)  public    procedure FreeInstance; override;  end; constructor TBaseClass.Create(AX, AY: Double);begin  FX := AX;  FY := AY;end; procedure TStackClass.FreeInstance;begin  CleanupInstance;end; procedure TestStackClass;var  alloc: TStackAllocator;  arr: array[0..99] of TBaseClass;  i: Integer;begin  for i:=Low(Arr) to High(Arr) do    arr[i] := alloc.Allocate.Create(Random, Random);end; procedure TestHeapClass;var  arr: array[0..99] of TBaseClass;  i: Integer;begin  for i:=Low(Arr) to High(Arr) do    arr[i] := TBaseClass.Create(Random, Random);  for i:=Low(Arr) to High(Arr) do    arr[i].Free;end; var  start: QWord;  i: Integer;begin  start := GetTickCount64;  for i:=0 to 100000 do    TestStackClass;  WriteLn('Stack: ', GetTickCount64 - start, 'ms');   start := GetTickCount64;  for i:=0 to 100000 do    TestHeapClass;  WriteLn('Heap: ', GetTickCount64 - start, 'ms');end. The stack allocation is nearly 20% faster: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Stack: 640msHeap: 766msWith an respective optimization using assembler code instead of moving to a parallel stack, this difference will probably become much greater. Quote from: Ryan J on July 15, 2023, 05:46:59 amOtherwise I think if the object model in FPC was unified we could simply declare a class on the stack or heap and the compiler would do the right thing for us. I don't have the experience to know but does that work well for C++? It seems very reasonable to me and when I have done C++ it worked very well, albeit in tiny programs. I mean such a "unified" system isn't actually new, records and base types are using this for ages, and we also have oldschool objects which do this. Basically the whole classical pointer system with new and dispose is exactly this. I've worked on C++ programs of all sizes, and it does indeed work. The problem is, we now have in Pascal these "heap only" classes, and this was an attempt on how to bring them on the stack without having to change the original class definition, e.g. such that you can simply use TStringList and all the other already existing classes without any changes on the stack. Quote from: Red_prig on July 15, 2023, 08:13:33 pmNot so long ago I tested the allocation of data on the stack, but in the end I partially abandoned this, it turned out that when optimizing -O3, the compiler starts using registers for stack frames differently and the code breaks))) In the end, the best and easiest option was allocation method on the stack but on the other sides))) This is just a bit of lets call it "academic curiosity" it is a hack and will probably never be really usable without real compiler support for stack allocations. Note that a similiar idea of the Allocator record can be used for more robust allocation methods: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i unit BufferAllocator; {$mode ObjFPC}{$H+}{$ModeSwitch advancedrecords} interface type  TBufferAllocator = record  private type    PAllocMem = ^TAllocMem;    TAllocMem = record      PreviousAlloc: PAllocMem; // Allocations form linked list to allow freeing them      ClassData: record end; // Empty Data (Size -> 0) because we just grab a pointer from here    end;  private    FBuffer: Pointer;    FBuffLen: SizeInt;    FHead: SizeInt;    FLastAlloc: PAllocMem;   public    constructor Create(ABuffer: Pointer; ASize: SizeInt);     class operator Initialize(var Allocator: TBufferAllocator);    class operator Finalize(var Allocator: TBufferAllocator);     generic function Allocate: T;  end; implementation { TBufferAllocator } constructor TBufferAllocator.Create(ABuffer: Pointer; ASize: SizeInt);begin  FBuffer := ABuffer;  FBuffLen := ASize;     FHead := 0;end; class operator TBufferAllocator.Initialize(var Allocator: TBufferAllocator);begin  Allocator.FLastAlloc := nil;  Allocator.FBuffer := Nil;  Allocator.FBuffLen := 0;  Allocator.FHead := 0;end; class operator TBufferAllocator.Finalize(var Allocator: TBufferAllocator);begin  while Assigned(Allocator.FLastAlloc) do  begin    // FIXME: Memory Manager trying to free on stack causes exception    // Only usable with custom class overloading FreeInstance    TObject(@Allocator.FLastAlloc^.ClassData).Destroy;    Allocator.FLastAlloc := Allocator.FLastAlloc^.PreviousAlloc;  end;end; generic function TBufferAllocator.Allocate: T;var  AllocaSize: SizeInt;  Allocation: PAllocMem;begin  AllocaSize := SizeOf(TAllocMem) + T.InstanceSize;   if FHead + AllocaSize > FBuffLen then    Exit(nil); // Not enough space in buffer left   Allocation := PAllocMem(FBuffer + FHead);  Allocation^.PreviousAlloc := FLastAlloc;  FLastAlloc := Allocation;   Inc(FHead, AllocaSize);   Result := T(T.InitInstance(@FLastAlloc^.ClassData));  (************************* ***************************************************)  (*                                 FIXME                                  *)  (*         When the Destructor is Called FreeInstance is called           *)  (*      This usually frees the memory before cleaning up managed fields     *)  (*          We want to skip the Free and only call CleanupInstance          *)  (*       But somehow overriding it directly in ther VMT does not work       *)  (*                          TODO: Find out why                            *)  (*************** *************************************************************)  // PVMT(Result)^.vFreeInstance := @TObject.CleanupInstance;end; end. This uses a pre-defined buffer for a FIFO style allocation, e.g. using a local array: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure TestStack;var  buff: Array[0..2047] of Byte;  alloc: TBufferAllocator;  sl: TStringList;begin  alloc := TBufferAllocator.Create(@buff, SizeOf(Buff));  // Only works because it is inlined, if message "marked as inline is not inlined", it will fail  sl := alloc.Allocate.Create;  sl.Add('Foo');  Smack;  sl.Add('Bar');  WriteLn(sl.Text);end; This would be a stack allocation without any assumptions about stack frames etc. But it has the disadvantage that it is not really dynamic, because it is limited by the size of the Buffer which is a compiletime constant. ---------------------------------------------------------------------- Red_prig · 2023-07-15 21:46 By the way, there is also "object", they have some of the advantages of classes and at the same time, memory for them needs to be allocated independently, in addition, they even support virtual methods, but to initialize them, you need to explicitly call the added "Constructor" ---------------------------------------------------------------------- Warfley · 2023-07-16 10:14 Yes I know, and I have already looked into how one could automate their destructor calls in https://forum.lazarus.freepascal.org/index.php/topic,63657.0.html This was more about on how to use the existing vast RTL, FCL or LCL class libraries, because using objects is fine and all, but this means I would have to rewrite all the already existing functionality in those classes for objects ---------------------------------------------------------------------- Warfley · 2023-07-16 19:02 Quote from: Warfley on July 15, 2023, 11:27:23 pmThe stack allocation is nearly 20% faster: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Stack: 640msHeap: 766msWith an respective optimization using assembler code instead of moving to a parallel stack, this difference will probably become much greater. I've just implemented a very simple ASM move: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   // Allocate Structure of TAllocMem + Class Data  AllocaSize := SizeOf(TAllocMem) + cls.InstanceSize;   asm    MOV R9, AllocaSize    // Target (RDX) := RSP - AllocaSize    MOV RDX, RSP    SUB RDX, R9    // Size (R8) = RBP + 2*SizeOf(Pointer) - Start (RSP)    MOV R8, RBP  ADD R8, 2*SizeOf(Pointer)    SUB R8, RSP    // i (RCX) := 0    MOV RCX, 0    // While i < Size  MoveLoop:    CMP RCX, R8    JNL MoveEnd  // Target[i] := Start[i]    MOV RAX, [RSP+RCX]    MOV [RDX+RCX], RAX    // i += 8    ADD RCX, 8    // End While    JMP MoveLoop  MoveEnd:  // RSP, RBP -= AllocaSize    SUB RSP, R9    SUB RBP, R9    // InsertionPoint := RBP + 2*SizeOf(Pointer)    MOV RAX, RBP    ADD RAX, 2*SizeOf(Pointer)    MOV InsertionPoint, RAX  end;   InsertionPoint^.PreviousAlloc := FLastAlloc;  FLastAlloc := InsertionPoint;  Result := cls.InitInstance(@FLastAlloc^.ClassData);Now the results are: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Stack: 391msHeap: 750msSo stack allocation, even with all this boilerplate is nearly twice as fast as heap allocation. ---------------------------------------------------------------------- Ryan J · 2023-07-17 03:39 Quote from: Warfley on July 15, 2023, 11:27:23 pmThe problem is, we now have in Pascal these "heap only" classes, and this was an attempt on how to bring them on the stack without having to change the original class definition, e.g. such that you can simply use TStringList and all the other already existing classes without any changes on the stack. Some years ago I tried to get the compiler people to accept some idea of stack allocated backings for classes but it didn't go anywhere because of "safety" concerns. Read about it here https://www.mail- archive.com/fpc-pascal@lists.freepascal.org/msg48491.html. I don't get it. Pascal is not a memory safe language. Only C is less safe than Pascal I would argue so I don't see the harm in adding compiler features to make memory management faster in terms of performance.