Allocation-Free Collections
[SHOWTOGROUPS=4,20]
January 25, 2019 by Erik van Bilsen
Say you have a method that creates a temporary list to gather some data. You calculate some statistics based on that data and then you destroy the list again. You call this method a lot, resulting in lots of memory allocations and deallocations and increased memory fragmentation. In addition, all this memory management takes time and may affect performance when used in time-critical sections of code.
For those situations, you may want to keep all your data on the stack instead and avoid memory allocations altogether. We show you a couple of ways you can achieve this.
Even if these use cases don’t apply to you, you may find this article useful since it uses some interesting concepts and Delphi language features.
Stack vs Heap, Value vs Reference Types
But first, lets get some terminology out of the way. You probably already know everything in this section, but let’s recap anyway.
There are two main types of internal memory: the stack and the heap. The stack is used to store local variables of methods and possibly other data (such as return addresses on many platforms). The heap stores dynamically allocated blocks of memory, including strings, dynamic arrays and objects.
When you learned about these types of memory, you probably read about value and reference types in the same paragraph or chapter, because the two are somewhat related. A value type stores some value directly at the memory location, while a reference type stores a pointer to a value that is located somewhere else (usually, but not necessarily on the heap). Examples of value types are integers, floating-point numbers, Booleans, enums, characters, records and static arrays. Examples of reference types are strings, objects, object interfaces, dynamic arrays and pointers.
This results in the following memory layout (with arbitrary memory locations for reference):
[/URL]
As you can see, creating a TList and adding some items results in at least two heap memory allocations: one to store the instance data of the list object (FItems, FCount and some other fields) and one to store a dynamic array of items. In this example, the dynamic array has room for 4 items, of which 2 are used. The dynamic array will grow as needed to accommodate new items.
Stack-Based Collections
You may run into situations where these heap memory allocations are not ideal. They can increase memory fragmentation which can result in increased memory usage. Also, allocating and freeing dynamic memory is not a cheap operation, and creating temporary lists many times per second may impact performance. On the other hand, “allocating” memory on the stack is usually a zero-cost operation. It just involves adjusting the stack pointer at the start of a method, which the compiler does most of the time anyway.
These issues could be addressed if you could create a collection entirely on the stack (that is, both the collection properties like FCount and the actual items should live on the stack). Actually, you probably already have used these kinds of collections before:
A local static array is essentially a stack-based collection, albeit not a user-friendly one. To make this array more list-like, we could wrap it inside a record with methods.
A Simple Stack-Based List
A simple implementation of that could look like this:
You can find a more documented version of this code (and all other code in this article) in our Для просмотра ссылки Войдиили Зарегистрируйся in the Для просмотра ссылки Войди или Зарегистрируйся directory.
It also checks if the type parameter T is a managed type and raises an exception if so. This may deserve some explanation. Even though the type parameter T has a record constraint, this doesn’t mean that T cannot contain a managed type. For example, the record constraint prevents Delphi from compiling this:
But not from compiling this:
When the type parameter T is a reference type or a managed type, we need some additional code to prevent memory leaks. We’ll get to this later and keep things simple for now by not allowing this.
Adding an item works like this:
Since the capacity of this list is fixed, we need to raise an exception when the list is full. We’ll look at an alternative later.
Because the FData field is just an array of bytes, we need a trick to put items of type T into this array. This is where the type P = ^T; declaration comes in handy. We calculate the offset into the FData array and assign its address to the Target variable of type P. Then, we can just dereference this variable to assign the value. Retrieving an item works in a similar way:
You can use this stack-based list as follows (see the E01SimpleStackList example in the repo):
[/SHOWTOGROUPS]
January 25, 2019 by Erik van Bilsen
Say you have a method that creates a temporary list to gather some data. You calculate some statistics based on that data and then you destroy the list again. You call this method a lot, resulting in lots of memory allocations and deallocations and increased memory fragmentation. In addition, all this memory management takes time and may affect performance when used in time-critical sections of code.
For those situations, you may want to keep all your data on the stack instead and avoid memory allocations altogether. We show you a couple of ways you can achieve this.
Even if these use cases don’t apply to you, you may find this article useful since it uses some interesting concepts and Delphi language features.
Stack vs Heap, Value vs Reference Types
But first, lets get some terminology out of the way. You probably already know everything in this section, but let’s recap anyway.
There are two main types of internal memory: the stack and the heap. The stack is used to store local variables of methods and possibly other data (such as return addresses on many platforms). The heap stores dynamically allocated blocks of memory, including strings, dynamic arrays and objects.
When you learned about these types of memory, you probably read about value and reference types in the same paragraph or chapter, because the two are somewhat related. A value type stores some value directly at the memory location, while a reference type stores a pointer to a value that is located somewhere else (usually, but not necessarily on the heap). Examples of value types are integers, floating-point numbers, Booleans, enums, characters, records and static arrays. Examples of reference types are strings, objects, object interfaces, dynamic arrays and pointers.
Only value types can be stored on the stack. When a reference type is declared on the stack, only its pointer value is stored on the stack; the actual value is allocated on the heap (if not nil). For example:
| 1 2 3 4 5 6 7 8 9 10 | procedure StackVsHeap; var A: Integer; B: TList<Integer>; begin A := 42; B := TList<Integer>.Create; B.Add(42); B.Add(100); end; |
As you can see, creating a TList and adding some items results in at least two heap memory allocations: one to store the instance data of the list object (FItems, FCount and some other fields) and one to store a dynamic array of items. In this example, the dynamic array has room for 4 items, of which 2 are used. The dynamic array will grow as needed to accommodate new items.
Stack-Based Collections
You may run into situations where these heap memory allocations are not ideal. They can increase memory fragmentation which can result in increased memory usage. Also, allocating and freeing dynamic memory is not a cheap operation, and creating temporary lists many times per second may impact performance. On the other hand, “allocating” memory on the stack is usually a zero-cost operation. It just involves adjusting the stack pointer at the start of a method, which the compiler does most of the time anyway.
These issues could be addressed if you could create a collection entirely on the stack (that is, both the collection properties like FCount and the actual items should live on the stack). Actually, you probably already have used these kinds of collections before:
| 1 2 3 4 5 6 7 | procedure StaticArray; var Items: array [0..9] of Integer; Count: Integer; begin ... end; |
A local static array is essentially a stack-based collection, albeit not a user-friendly one. To make this array more list-like, we could wrap it inside a record with methods.
A Simple Stack-Based List
A simple implementation of that could look like this:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | type TStackList<T: record> = record private type P = ^T; private FData: array [0..255] of Byte; FCapacity: Integer; FCount: Integer; function GetItem(const AIndex: Integer): T; public procedure Initialize; procedure Clear; procedure Add(const AItem: T); property Count: Integer read FCount; property Items[const AIndex: Integer]: T read GetItem; default; end; |
You can find a more documented version of this code (and all other code in this article) in our Для просмотра ссылки Войди
A couple of things to note here:
- I chose to create a generic list here. Nowadays there is little need for non-generic lists.
- The type parameter T has a record constraint. This means that the list can only hold value types (for now). This simplifies the implementation of this list somewhat.
- The nested type P = ^T; declaration may be new to you. It declares a typed pointer to the type of the items in the list. This is useful in the implementation to access list items.
- The list holds its items in a static array of 256 bytes, meaning it always consumes 256 bytes of (stack) memory, regardless of type T. So if used to create a list of integers, then the list can hold at most 64 items (since an integer is 4 bytes in size).
- You must call the Initialize method to initialize or create the list. This method acts like a constructor. Since records cannot have constructors without parameters (at least not in the current Delphi version), I chose to add an Initialize method. You could also opt for a static method that returns a list instead (as in class function Create: TStackList<T>; static
, but returning a large record from a function is not very efficient. - Although you can declare a TStackList as a field inside an object, this is not really the purpose of this list and just wastes memory. This type is designed to be declared as a local variable in a method only.
| 1 2 3 4 5 6 7 8 9 | procedure TStackList<T>.Initialize; begin if IsManagedType(T) then raise EInvalidOperation.Create( 'A stack based collection cannot contain managed types'); FCapacity := SizeOf(FData) div SizeOf(T); FCount := 0; end; |
| 1 2 | var List: TStackList<String>; |
But not from compiling this:
| 1 2 3 4 5 6 | type TStringWrapper = record Value: String; end; var List: TStackList<TStringWrapper>; |
When the type parameter T is a reference type or a managed type, we need some additional code to prevent memory leaks. We’ll get to this later and keep things simple for now by not allowing this.
Adding an item works like this:
| 1 2 3 4 5 6 7 8 9 10 11 | procedure TStackList<T>.Add(const AItem: T); var Target: P; begin if (FCount >= FCapacity) then raise EInvalidOperation.Create('List is full'); Target := @FData[FCount * SizeOf(T)]; Target^ := AItem; Inc(FCount); end; |
Since the capacity of this list is fixed, we need to raise an exception when the list is full. We’ll look at an alternative later.
Because the FData field is just an array of bytes, we need a trick to put items of type T into this array. This is where the type P = ^T; declaration comes in handy. We calculate the offset into the FData array and assign its address to the Target variable of type P. Then, we can just dereference this variable to assign the value. Retrieving an item works in a similar way:
| 1 2 3 4 5 6 7 8 9 10 | function TStackList<T>.GetItem(const AIndex: Integer): T; var Item: P; begin if (AIndex < 0) or (AIndex >= FCount) then raise EArgumentOutOfRangeException.Create('List index out of range'); Item := @FData[AIndex * SizeOf(T)]; Result := Item^; end; |
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | procedure SimpleStackListExample; var List: TStackList<Integer>; Error: Boolean; I: Integer; begin List.Initialize; { TStackList<Integer> can contain up to 256 bytes of data. An Integer is 4 bytes in size, meaning the list can contain up to 64 Integers. } for I := 0 to 63 do List.Add(I); { Adding 64'th item should raise an exception. } Error := False; try List.Add(0); except Error := True; end; Assert(Error); { Check contents } Assert(List.Count = 64); for I := 0 to List.Count - 1 do Assert(List = I); end; |
[/SHOWTOGROUPS]
