Stack allocated dynamic arrays (AKA VLA) in Free Pascal

[maugli]

Dear community,

Today I had to explain to someone the concept of VLA and that why is it not suppoerted in C90 (and back), and why could it be problematic (extracting down the whole process to alloca calls, and the undefined behaviour with stack overflow, etc.).

And I wanted to convince him about how Free Pascal is better, because either you have arrays with size given at compilation time (and thus allocated on the stack frame if I'm not mistaken), or dynamic what is allocated on heap, but still very convenient, and safe, not leaking memory, etc.

And before I started to tell him anything about FP+arrays I've become concerned:
Are static size arrays always stored on stack in FP? (I guess yes, because I can easily cause stackoverflow with too big static arrays, but would like to be sure)
Are dynamic arrays stored on the heap?
Is there any way in FP to force stack allocation like alloca in C?

And after I've read through the available documentation (or at least the pieces I've found), I've started to realise I don't know enough about FP array handling.

SO!

Could anyone explain me how the things around arrays are implemented in FP?
What is allocated on the stack, what is on the heap? Is there any method to force each behaviour? Are there platform specific details?

Thanks in advance!

[440bx]

Are static size arrays always stored on stack in FP? (I guess yes, because I can easily cause stackoverflow with too big static arrays, but would like to be sure)

Answer: no.  the type of memory allocated depends on "where" the static array is declared.  if the static array is declared as a local variable in a function or procedure then it will always be allocated on the stack.  if the static array is declared as a "program" variable (that is, a global variable) then it will be allocated in the executable's data segment. 

Are dynamic arrays stored on the heap?

Answer: Yes.  this is what allows dynamic array related functions such as SetLength to dynamically modify the size of the dynamic array. 

Is there any way in FP to force stack allocation like alloca in C?

Answer: yes but, with some considerations.  FPC does not have an alloca function (at least not to my knowledge) but you can accomplish the same thing for a _static_ array (not a dynamic one) by declaring the array as a local variable.

Could anyone explain me how the things around arrays are implemented in FP?

Answer: it depends on the type of array.  All arrays, whether dynamic or static, have one thing in common, they are always consecutive collections of elements one after the other.  For a dynamic array, that collection of elements is always allocated on the heap, this is what allows a function like SetLength to perform expansion or contraction of the array (by manipulating the heap block as needed.) For static arrays, what you need to know is in the previous answers.

What is allocated on the stack, what is on the heap? Is there any method to force each behaviour? Are there platform specific details?

I cannot answer platform specific details other than for Windows.  Therefore, in Windows, static arrays declared as local variables in a function or procedure are allocated on the stack.  Dynamic arrays are allocated in the heap.  As far as forcing a particular behavior, the answer is yes but, with limits.  For instance, there is no way to force a dynamic array to be allocated on the stack simply because the stack frame is established upon function/procedure entry, this forces the array to be static.  In FPC, it is very easy to choose where an array is located, simply declare a pointer to the array element's data type, use any memory allocation function you desire and, because FPC allows pointer arithmetic (just as in C) any element of the array can be accessed by using (pointer + element_index)^.  Because of this, it is easy to create a custom "dynamic" array (dynamic in quotes because this custom array cannot  be modified by using SetLength for instance).  As an example, using O/S functions such as VirtualAllocEx in Windows, it is possible to reserve a large amount of address space, initially commit only a few pages and, grow the array by committing additional pages as needed, essentially implementing a custom version of SetLength.

Thanks in advance!

You're welcome.

HTH.

[rforcen]

this snippet briefly explain memory usage of different fpc items: dynamic arrays, record, objects, classes and dynamic memory allocation with new & getmem

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

1. { test bench of fpc memory management}
2. program memMgr;
3.  
4. type
5.   TRec = record { memory area of sizeof(TRec) }
6.     a, b: integer;
7.   end;
8.  
9.   TObj = object { memory area of sizeof(TObj) }
10.     a, b: integer;
11.   end;
12.  
13.   { TClass }
14.  
15.   TClass = class { pointer }
16.     constructor Create; overload;
17.     constructor Create(const c: TClass); overload; {deep copy version}
18.   public
19.     a, b: integer;
20.     v: array of integer;
21.   end;
22.  
23.   PTRec = ^TRec;
24.  
25. var
26.   a, b: array of integer; { dynamic arrays -> pointer }
27.   ra, rb: TRec;
28.   oa, ob: TObj;
29.   ca, cb: TClass;
30.   pa, pb: PTrec;
31.  
32.   { TClass }
33.  
34.   constructor TClass.Create;
35.   begin
36.     a := 0;
37.     b := 0;
38.     v := nil;
39.     inherited Create;
40.   end;
41.  
42.   constructor TClass.Create(const c: TClass);
43.   begin
44.     inherited Create;
45.  
46.     a := c.a; {deep copy assign all c properties to self}
47.     b := c.b;
48.     v := copy(c.v); {for dynamic arrays properties use copy func: v:=copy(c.v); }
49.   end;
50.  
51. begin
52.   { dynamic array are pointers so assignment does a shallow copy }
53.   writeln('----------- dynamic arrays');
54.   a := nil;
55.   setLength(a, 10);
56.   a[0] := 1;
57.   b := a; // pointer copy
58.   writeln('@a[0]=0x', hexStr(@a[0]), ' @b[0]=0x', hexStr(@b[0]), ' pointers are equal');
59.   b[0] := 2; // also changes a[0] as a and b point to the same place
60.  
61.   writeln('a[0]=', a[0], ' b[0]=', b[0]);
62.   if a[0] = b[0] then writeln(
63.       'dymanic arrays assignment copies a pointer (shallow copy)');
64.  
65.   { deep copy using copy func. }
66.   b := copy(a); // now a & b point to different addresses
67.   b[0] := 3;
68.  
69.   if a[0] <> b[0] then writeln('after copy func b has a different address');
70.   writeln('a[0]=', a[0], ' b[0]=', b[0]);
71.  
72.  
73.   { records fixed address deep copy assignment (non recursive)}
74.   writeln('----------- records');
75.   ra.a := 1;
76.   rb := ra;
77.   rb.a := 2;
78.   writeln('ra.a=', ra.a, ' rb.a=', rb.a);
79.   if ra.a <> rb.a then writeln('records use fixed independant storage');
80.  
81.   { objects -> fixed address deep copy assign }
82.   writeln('----------- objects');
83.   oa.a := 1;
84.   ob := oa;
85.   ob.a := 2;
86.   writeln('oa.a=', ra.a, ' ob.a=', ob.a);
87.   if oa.a <> ob.a then writeln('objects use fixed independant storage');
88.  
89.   { class -> pointers }
90.   writeln('----------- class');
91.   ca := TClass.Create;
92.   cb := ca;   {copy pointer -> shallow copy }
93.   ca.a := 1;
94.   cb.a := 2;  { now both ca.a and cb.a are equal as ca and cb point to the same place }
95.  
96.   writeln('ca=0x', hexStr(ca), ' cb=0x', hexStr(cb), ' they point to the same address');
97.   writeln('ca.a=', ca.a, ' cb.a=', cb.a);
98.   if ca.a <> cb.a then writeln('class use fixed independant storage')
99.   else
100.     writeln('class use pointer based shallow copy');
101.  
102.   cb := TClass.Create;
103.   cb.a := 3;
104.  
105.   if ca.a <> cb.a then writeln(
106.       'after creating a new instance of cb it points to a different place than ca');
107.   writeln('ca.a=', ca.a, ' cb.a=', cb.a);
108.  
109.   cb := TClass.Create(ca);
110.   { now the contain the same data in different spaces -> deep copy }
111.   writeln('after a deep copy ca.a=', ca.a, ' cb.a=', cb.a);
112.  
113.   cb.a := 3;
114.   writeln('modified cb -> cb.a=', cb.a, ' cb.b=', cb.b);
115.  
116.   { pointers: new dispose }
117.   writeln('----------- pointers to records new/dispose');
118.   new(pa);
119.   pa^.a := 1;
120.   pb := pa;
121.   pb^.a := 2;
122.  
123.   if pa^.a <> pb^.a then writeln('pointers use fixed independant storage')
124.   else
125.     writeln('pointers use shallow copy');
126.   writeln('pa.a=', pa^.a, ' pb.a=', pb^.a);
127.  
128.   writeln('new pb instance');
129.   new(pb);
130.   pb^.a := 3;
131.   writeln('pa.a=', pa^.a, ' pb.a=', pb^.a);
132.   writeln('pa=0x', hexStr(pa), ' pb=0x', hexStr(pb), ' point to different places');
133.  
134.   dispose(pa);
135.   dispose(pb);
136.  
137.   { getmem }
138.   writeln('----------- pointers to records getmem/freemem');
139.   getmem(pa, sizeof(pa^));
140.  
141.   pa^.a := 1;
142.   pb := pa;
143.   pb^.a := 2;
144.  
145.   if pa^.a <> pb^.a then writeln('pointers use fixed independant storage')
146.   else
147.     writeln('pointers use shallow copy');
148.   writeln('pa.a=', pa^.a, ' pb.a=', pb^.a);
149.  
150.   writeln('new pb instance');
151.   getmem(pb, sizeof(pb^));
152.  
153.   pb^.a := 3;
154.   writeln('pa.a=', pa^.a, ' pb.a=', pb^.a);
155.   writeln('pa=0x', hexStr(pa), ' pb=0x', hexStr(pb), ' point to different places');
156.  
157.   pb^ := pa^; { record deep copy }
158.   writeln('pa.a=', pa^.a, ' pb.a=', pb^.a);
159.   writeln('pa=0x', hexStr(pa), ' pb=0x', hexStr(pb), ' point to different places');
160.  
161.   freemem(pa);
162.   freemem(pb);
163.  
164.   {---------------------}
165.   readln;
166. end.
167.  

[jamie]

I wanted to add something to this

Writeable constants :

  You can declare a writeable constant anywhere, however, those that are declared inside a function or procedure are locale to that block of code and retains the last state when that block of code was executed.

Writeable constants are like Static constants and require a type, otherwise they become only read only constants that are fluid to the type you are using them with.

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

1. Procedure Test;
2. Constant MyLocalByte:Byte = 1; // They must be assigned a value at compile time.
3.  
4. Begin
5.    ....
6.   Writeln('The last time here had a value of ', MyLocalByte);
7.   Inc(MyLocalByte);
8. end;
9.  
10.  

This is niffy code because you can use the same name of the writeable constant in many functions or procedures and they are each unique to that code block.

[Чебурашка]

What happens if, under reasonable concurrence protection, such a dynamic structure on the stack, is made bigger by another thread, while stack owning thread is in pause? Who should manage that?

[440bx]

made bigger by another thread, while stack owning thread is in pause? Who should manage that?

A thread _cannot_ give itself the luxury of making structural changes to the stack of another thread.

Even a debugger should not do that.  A debugger commonly changes the values of variables on the stack but, changes to the values of variables does not in any way change the structure of the stack.  Allocating memory on the stack is a stack structural change.

[jamie]

The stack is at a different location when a secondary thread calls it if the primary thread is already in there.

Dynamic items will have a different home along with fixed sized items on the stack.