Lazarus

Free Pascal => General => Topic started by: tverweij on April 12, 2018, 04:24:28 pm

Title: Dynamic arrays
Post by: tverweij on April 12, 2018, 04:24:28 pm
Are dynamic arrays allocated in one continuous memory segment?
Or can a dynamic array be fragmented?
Title: Re: Dynamic arrays
Post by: Handoko 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.
Title: Re: Dynamic arrays
Post by: tverweij on April 12, 2018, 05:00:42 pm
I read http://wiki.freepascal.org/Dynamic_array (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?
Title: Re: Dynamic arrays
Post by: ASerge 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.
Title: Re: Dynamic arrays
Post by: tverweij 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.
Title: Re: Dynamic arrays
Post by: Thaddy 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
Title: Re: Dynamic arrays
Post by: Handoko 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.
Title: Re: Dynamic arrays
Post by: Thaddy on April 12, 2018, 06:28:44 pm
These are basically dynamic arrays that behave like I described.
Title: Re: Dynamic arrays
Post by: Handoko 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.
Title: Re: Dynamic arrays
Post by: tverweij 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.
Title: Re: Dynamic arrays
Post by: Handoko 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
Title: Re: Dynamic arrays
Post by: jamie 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 !
Title: Re: Dynamic arrays
Post by: Leledumbo 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.
Title: Re: Dynamic arrays
Post by: tverweij 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.

Title: Re: Dynamic arrays
Post by: tverweij 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/ (http://frankdenneman.nl/2015/02/18/memory-configuration-scalability-blog-series/)

If anyone has hints or tips in this area, they are welcome!
TinyPortal © 2005-2018