Array size 64bits

[Heremik 0]

Hello,

I work with Delphi from the begining (even begun with turbo pascal).

I have to make calculation with very big array. if I use dynamic array no problem for the size.

But dynamic array are very slow vs static array (about at least 2X).

So my intention was to use static array to perform my objective.

But, i have a problem.

 

When I try a clean VCL projet and I declare that :

        Table : array[0..536870473] of integer; => Ok
        Table : array[0..536870474] of integer; => Access violation (74 to 76)
        Table : array[0..536870477] of integer; => Compilation error, data too big > 2Go...

 

I have tried with boolean  :

            Table: array [0 ..  2147481895] of Boolean; => Ok
            Table: array [0 ..  2147481896] of Boolean; => Access violation (896 to 911)
            Table: array [0 ..  2147481911] of Boolean => Compilation error, data too big > 2Go...

 

Ok, Access violation is just an error to the limitation. But in 64 bits why limitation to 2 Go ???????

I have 80 Go of RAM on my computer, and I don't understand why my static array are limited.

 

Is there a solution ? (with performance, because I always need speed).

[Heremik 0]

Thank's for the advice if it is possible.

[Clément 148]

Hi,

 

How did you measure the performance of static arrays vs dynamic arrays?
IME I found dynamic array to be faster than static arrays for large data. I almost always use static arrays for smallish data types.
Be sure to allocate your dynamic array only once, and use it as you please.

 

My $0.02

 

type
  THugeArray = TArray<Integer>;


  TForm90 = class(TForm)
    procedure FormCreate(Sender: TObject);
  private
    { Private declarations }
     Table2 : THugeArray;
  public
    { Public declarations }
  end;

var
  Form90: TForm90;

implementation

{$R *.dfm}

procedure TForm90.FormCreate(Sender: TObject);
begin
   SetLength( Table2, MaxInt ); // Will take some time to allocate the memory.
end;

 

[David Heffernan 2345]

In terms of accessing the memory, then there's basically no difference in performance between heap allocated and stack allocated arrays. The performance difference comes in allocation. If you are going to allocate such large arrays then the time spent working on them surely dwarfs the allocation cost. 

 

The other thing to note is that your stack is typically going to have a size much lower than the arrays you want to work with. So even if you could declare such huge arrays as fixed size, they won't fit I. The stack. In other words heap allocated dynamic arrays are the only option. 

 

Probably your next move is to revisit your benchmark and understand how you ended up with the erroneous view that heap allocated memory is slower. 

[Heremik 0]

Here is a small example. Just a form with a button.
The array is not a local variable and the allocation is done before measuring time.
On my PC :

- 24 seconds with static array

- 27 seconds with dynamic array.

 

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;

Const
  NbPrime = 10000000;

Type
  TForm1 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Déclarations privées }
  public
    { Déclarations publiques }

    // Table: Array [0 .. NbPremier] of Dword;
    Table: Array of Dword;
  end;

var
  Form1: TForm1;

implementation

uses math;
{$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject);
var
  current, first, last: Dword;
  IsPrime: Boolean;
  index: Dword;
  sqcompteur: Dword;
  StartTime, EndTime: TTime;
  i, j: Dword;
BEGIN
  SetLength(Table, NbPrime);
  StartTime := Time();

  Table[0] := 2;
  Table[1] := 3;
  last := 1;
  index := 5;
  while last < NbPrime do
  begin
    sqcompteur := trunc(sqrt(index)) + 1;
    IsPrime := True;
    current := 1;
    while IsPrime and (Table[current] < sqcompteur) do
    begin
      IsPrime := (index mod Table[current]) <> 0;
      current := current + 1
    end;
    if IsPrime then
    begin
      last := last + 1;
      Table[last] := index;
    end;
    index := index + 2;
  end;

  EndTime := Time();
  StartTime := EndTime - StartTime;
  showMessage(TimeToStr(StartTime));
end;

end.

 

Edited November 13, 2022 by Heremik

[PeterBelow 238]

10 hours ago, Heremik said:

Hello,

I work with Delphi from the begining (even begun with turbo pascal).

I have to make calculation with very big array. if I use dynamic array no problem for the size.

But dynamic array are very slow vs static array (about at least 2X).

So my intention was to use static array to perform my objective.

But, i have a problem.

 

When I try a clean VCL projet and I declare that :

        Table : array[0..536870473] of integer; => Ok
        Table : array[0..536870474] of integer; => Access violation (74 to 76)
        Table : array[0..536870477] of integer; => Compilation error, data too big > 2Go...

 

I have tried with boolean  :

            Table: array [0 ..  2147481895] of Boolean; => Ok
            Table: array [0 ..  2147481896] of Boolean; => Access violation (896 to 911)
            Table: array [0 ..  2147481911] of Boolean => Compilation error, data too big > 2Go...

 

Ok, Access violation is just an error to the limitation. But in 64 bits why limitation to 2 Go ???????

I have 80 Go of RAM on my computer, and I don't understand why my static array are limited.

 

Is there a solution ? (with performance, because I always need speed).

This seems to be a limitation of the compiler, System.GetMem does use NativeInt for the size parameter, so can allocate more than 2GB for a 64 bit target.

This works:

procedure TForm2.Test;
var
  p: pinteger;
begin
  GetMem(p, NativeInt(High(Integer)) * Sizeof(Integer));
  try
    Caption := Format('p= %p',[p]);
  finally
    FreeMem(p);
  end;
end;

The only problem is that you cannot declare a proper static array type for this memory block, so would have to do all the index calculations in code.

However, you  can size a dynamic array to more than 2GB:

procedure TForm2.Test2;
var
  a: array of integer;
begin
  SetLength(a, High(Integer));
  try
    Caption := Format('p= %p',[pointer(a)]);
  finally
    setlength(a, 0);
  end;
end;

 

[David Heffernan 2345]

3 hours ago, Heremik said:

Here is a small example. Just a form with a button.
The array is not a local variable and the allocation is done before measuring time.
On my PC :

- 24 seconds with static array

- 27 seconds with dynamic array.

Same time for both versions for me, using 64 bit release build with XE7. I'm quite confident that your diagnosis is not correct.

[Heremik 0]

I have made the test multiple times, with exactly the code I have posted and I have always the same result.

I use Delphi 10.4, perhaps, there is a difference in the code generated.

[Der schöne Günther 316]

Are you using range checking in your debug build? Maybe the compiler does different range checking for static and dynamic arrays.

[David Heffernan 2345]

42 minutes ago, Der schöne Günther said:

Maybe the compiler does different range checking for static and dynamic arrays.

It will do because it knows the size of the fixed length array at compile time. 

[Stefan Glienke 2002]

The difference in performance is clear - accessing a dynamic array which is a field inside the class is two indirections while accessing a static array which is a field inside the class is only one indirection. If you inspect the generated assembly code you will see that every access to the dynamic array has more instructions. This is the case every time you have repeated access to a field inside a method because the compiler does not store it away as if it was a local variable and then directly reads it but basically does Self.Table every time. For this exact reason I have explicitly written code that first reads the dynamic array into a local pointer variable (to avoid the extra reference counting) and then operate on that one via hardcast back to dynamic array (or via pointermath). That way the compiler could keep that in a register and directly index into it rather than dereferencing Self every time to read that dynamic array.

 

To try out, add this code to your Button1Click:

 

  {$POINTERMATH ON}
  Table: ^DWord;
  {$POINTERMATH OFF}
begin
  SetLength(Self.Table, NbPrime);
  Table := @Self.Table[0];

Now the code accesses the local Table variable which most likely is stored in a register.

Edited November 14, 2022 by Stefan Glienke