* * *

Author Topic: Dynamic arrays  (Read 1934 times)

tverweij

  • Guest
Dynamic arrays
« on: April 12, 2018, 04:24:28 pm »
Are dynamic arrays allocated in one continuous memory segment?
Or can a dynamic array be fragmented?
« Last Edit: April 12, 2018, 05:43:38 pm by tverweij »

Handoko

  • Hero Member
  • *****
  • Posts: 2438
  • My goal: build my own game engine using Lazarus
Re: Dynamic arrays
« Reply #1 on: April 12, 2018, 04:46:20 pm »
Because you can use FillChar to initial dynamic arrays' content:

FillChar(MyVariable,sizeof(MyVariable), #0);

Quote
Fillchar fills the memory starting at X with Count bytes or characters with value equal to Value. 
Source: https://www.freepascal.org/docs-html/rtl/system/fillchar.html

it means dynamic array occupies one continuous memory segment.

tverweij

  • Guest
Re: Dynamic arrays
« Reply #2 on: April 12, 2018, 05:00:42 pm »
I read http://wiki.freepascal.org/Dynamic_array again, and you are right.
Dynamic arrays must be in a continuous memory segment.

This means that I can use copyMemory to copy the contents of one dynamic array to another.

But this also raises another question:
What if the heap is so fragmented that there is no large enough continuous free memory segment is available?
Will I get an exception or will the heap be defragmented?  Or can I defragment the heap myself in such a case?

ASerge

  • Hero Member
  • *****
  • Posts: 859
Re: Dynamic arrays
« Reply #3 on: April 12, 2018, 05:21:07 pm »
What if the heap is so fragmented that there is no large enough continuous free memory segment is available?
Will I get an exception or will the heap be defragmented?  Or can I defragment the heap myself in such a case?
Yes, EOutOfMemory. Write your own memory manager.

tverweij

  • Guest
Re: Dynamic arrays
« Reply #4 on: April 12, 2018, 05:35:58 pm »
@ASerge: I am just trying to find out how it works, so I will know what to expect.

Thaddy

  • Hero Member
  • *****
  • Posts: 6525
Re: Dynamic arrays
« Reply #5 on: April 12, 2018, 06:03:50 pm »
@ASerge: I am just trying to find out how it works, so I will know what to expect.
In the case of a dynamic array this should not be a problem unless you call setlength() for every added item.
And that would be bad programming. (And VERY slow!). Better to grow the array capacity with - let's say - the golden ratio if you need to add something beyond its capacity? (~1.5). Basics.
That will limit fragmentation but eventually... not enough space will lead to a EOutOfMemory.
The FPC memory manager is efficient in most cases but not really suited to the above scenario.
It is also very low-level, so not even for intermediate programmers. Although I invite everyone to experiment with writing a memory manager....Good! O:-)

The code requirements are simple, but the effects are frighteningly complex... :D
« Last Edit: April 12, 2018, 06:13:42 pm by Thaddy »
Ada's daddy wrote this:"Fools are my theme, let satire be my song."

Handoko

  • Hero Member
  • *****
  • Posts: 2438
  • My goal: build my own game engine using Lazarus
Re: Dynamic arrays
« Reply #6 on: April 12, 2018, 06:21:15 pm »
@tverweij

Or maybe you can consider TList, TFPList, TFPObjectList or something similar.
http://wiki.freepascal.org/Data_Structures,_Containers,_Collections

They do not use one single continuous memory segment.

Dynamic array should always be faster but my test on a simple game I wrote, the performance different dynamic array vs TFPList was insignificant.
« Last Edit: April 12, 2018, 06:22:49 pm by Handoko »

Thaddy

  • Hero Member
  • *****
  • Posts: 6525
Re: Dynamic arrays
« Reply #7 on: April 12, 2018, 06:28:44 pm »
These are basically dynamic arrays that behave like I described.
Ada's daddy wrote this:"Fools are my theme, let satire be my song."

Handoko

  • Hero Member
  • *****
  • Posts: 2438
  • My goal: build my own game engine using Lazarus
Re: Dynamic arrays
« Reply #8 on: April 12, 2018, 06:34:50 pm »
Quote
TList is a class that can be used to manage collections of pointers.
Source: https://www.freepascal.org/docs-html/rtl/classes/tlist.html

Yes, you're right. But because the 'real' data are in the locations pointed by those pointers, they're not in a continuous memory segment. That's what I meant.
« Last Edit: April 12, 2018, 06:36:23 pm by Handoko »

tverweij

  • Guest
Re: Dynamic arrays
« Reply #9 on: April 12, 2018, 07:21:28 pm »
Quote
This means that I can use copyMemory to copy the contents of one dynamic array to another.

Before Someone tries to do this: I just realized this will copy the values/references without increasing the reference count.
As soon as the original array is destroyed, the content will also be destroyed, causing the copies to be invalid.

@Thaddy: I am a beginner with FPC, but not with programming. I have 28 years experience in different languages  - only 2 years with Delphi, but that was Delphi 1 and 2, a very long time ago. So I won't set SetLength for each and every item  :o

I am going to look at the internals of the lists mentioned, to see what best suits my scenario, involving very large arrays of pointers and an almost impossible performance is needed on them - meaning I have to look on NUMA optimization also.

Handoko

  • Hero Member
  • *****
  • Posts: 2438
  • My goal: build my own game engine using Lazarus
Re: Dynamic arrays
« Reply #10 on: April 12, 2018, 08:56:25 pm »
Before Someone tries to do this: I just realized this will copy the values/references without increasing the reference count.
As soon as the original array is destroyed, the content will also be destroyed, causing the copies to be invalid.

My test show the Storage2 still has valid content after Storage1 destroyed:

Code: Pascal  [Select]
  1. unit Unit1;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. interface
  6.  
  7. uses
  8.   Classes, SysUtils, Forms, Controls, Dialogs, StdCtrls;
  9.  
  10. type
  11.  
  12.   { TForm1 }
  13.  
  14.   TForm1 = class(TForm)
  15.     Button1: TButton;
  16.     procedure Button1Click(Sender: TObject);
  17.   end;
  18.  
  19. var
  20.   Form1: TForm1;
  21.  
  22. implementation
  23.  
  24. {$R *.lfm}
  25.  
  26. { TForm1 }
  27.  
  28. procedure TForm1.Button1Click(Sender: TObject);
  29. var
  30.   Storage1, Storage2: array of Integer;
  31.   Total1, Total2, i: Integer;
  32. begin
  33.  
  34.   SetLength(Storage1, 100);
  35.   for i := Low(Storage1) to High(Storage1) do
  36.     Storage1[i] := Random(999);
  37.   Storage2 := Copy(Storage1, Low(Storage1), Length(Storage1));
  38.  
  39.   Total1 := 0;
  40.   for i := Low(Storage1) to High(Storage1) do
  41.     Inc(Total1, Storage1[i]);
  42.   SetLength(Storage1, 0);
  43.  
  44.   Total2 := 0;
  45.   for i := Low(Storage2) to High(Storage2) do
  46.     Inc(Total2, Storage2[i]);
  47.   SetLength(Storage2, 0);
  48.  
  49.   ShowMessage('Total sum of Storage1 = ' + Total1.ToString + LineEnding +
  50.               'Total sum of Storage2 = ' + Total2.ToString);
  51.  
  52. end;
  53.  
  54. end.

Line #42: SetLength(Storage1, 0); is used to destroy the Storage1's content.

Read more:
https://www.freepascal.org/docs-html/rtl/system/copy.html

jamie

  • Hero Member
  • *****
  • Posts: 785
Re: Dynamic arrays
« Reply #11 on: April 12, 2018, 11:56:44 pm »
I didn't see the Target OS you are shooting for but if you are on Windows you can use the API memory functions which can
allocate a chuck of memory outside of the heap memory used in your app...

 The only draw back with this is that you'll need to use the old style of Pointer memory functionality which isn't really
a big deal...

 You can create a Record that represents your layout for the memory and then assign a pointer to it, from there on, its
smooth sailing..

 Just remember to release that memory !

Leledumbo

  • Hero Member
  • *****
  • Posts: 7936
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: Dynamic arrays
« Reply #12 on: April 13, 2018, 06:07:30 am »
But this also raises another question:
What if the heap is so fragmented that there is no large enough continuous free memory segment is available?
Will I get an exception or will the heap be defragmented?  Or can I defragment the heap myself in such a case?
Two things to read:
https://www.freepascal.org/docs-html/prog/progsu172.html
https://www.freepascal.org/docs-html/prog/progsu173.html

Note that it's applicable to memory management in general, not dynamic array specific whatsoever.

tverweij

  • Guest
Re: Dynamic arrays
« Reply #13 on: April 13, 2018, 09:06:49 am »
@Handoko: you are using the Pascal function Copy instead of the Windows function CopyMemory in line 37, and you are using a value type instead of a reference type.
That's why your copy is still valid.

@jamie: Target is Windows 64 bit. And yes, I will use the API memory functions if needed to get a stable and fast result. But I will first try to use the standard functions (maybe with some hacks) and see if it fits my needs.

@Leledumbo: Thanks for the links! ReturnNilIfGrowHeapFails is a very interesting option.


tverweij

  • Guest
Re: Dynamic arrays
« Reply #14 on: April 13, 2018, 09:27:09 am »
Thanks for all replies.

I am going for my own memory management; a thread per Numa-Node with each it's own heap in Local Memory (to prevent performance degradation because of the use of Remote Memory). If you don't know about this subject, read http://frankdenneman.nl/2015/02/18/memory-configuration-scalability-blog-series/

If anyone has hints or tips in this area, they are welcome!
« Last Edit: April 13, 2018, 09:49:11 am by tverweij »

 

Recent

Get Lazarus at SourceForge.net. Fast, secure and Free Open Source software downloads Open Hub project report for Lazarus