Re: [fpc-devel] Aligned dynamic arrays

[Anthony Walter]

Inside the type I have:

  TAlignedArray = record
  public
type
  TReference = ^T;
  TValue = T;
...
procedure Push(const Item: TValue);
function Pop: TValue;
property Length: Integer read FLength write SetLength;
property Reference[Index: Integer]: TReference read GetReference;
default;
property Item[Index: Integer]: TValue read GetItem write SetItem;
...
  end;

So the default property indexer returns references and not values. If you
want values specifically you can use the Item property indexer.

This way we can either access fields directly on the items withing the
array like so:

A[0].X := SomeValue;

Or if you need fast access to quickly populate the values, support we want
to write 3 component vertex data, you could write:

type
  TVertexBuffer = type TAlignedArray;
var
  Buffer: TVertexBuffer;
  V: TVertexBuffer.TReference;
begin
  Buffer.Length := VertexCount(ModelStream);
  V := Buffer[0];
  for I := 1 to Buffer.Length do
  begin
V.X := ReadX(ModelStream);
V.Y := ReadY(ModelStream);
V.Z := ReadZ(ModelStream);
Inc(V);
  end;
  ...
end;

Which probably ends up being faster than continually accessing array
dynamic values by index.
___
fpc-devel maillist  -  fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Re: [fpc-devel] Aligned dynamic arrays

[Ryan Joseph]

> On Mar 29, 2019, at 9:15 PM, Anthony Walter  wrote:
> 
> Ryan, actually ...
> 
> A.Length := 1;
> A[0].X := 100;
> 
> ... does work in my implementation.

Really, how? [] property uses a getter which copies the array right? I’mm not 
aware of how to do this in Pascal without pointers.

Regards,
Ryan Joseph

___
fpc-devel maillist  -  fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Re: [fpc-devel] Aligned dynamic arrays

[Anthony Walter]

Ryan, actually ...

A.Length := 1;
A[0].X := 100;

... does work in my implementation.
___
fpc-devel maillist  -  fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Re: [fpc-devel] Aligned dynamic arrays

[Ryan Joseph]

> On Mar 29, 2019, at 5:25 PM, Sven Barth via fpc-devel 
>  wrote:
> 
> Ignoring something is not an answer. At least there'd need to be a runtime 
> error.
> 
> Thinking about it maybe it would be better to follow Anthony's idea with the 
> record and not try to adjust/extend a language mechanism that wasn't geared 
> for that.

Biggest problems with records is that we can’t make arrays of records because 
the [] property copies the record with the getter (my other email on this never 
got posted). If there was a feasible way to fix that problem then dynamic 
arrays would be nearly obsolete anyways (probably still faster though).

var
 A: TAlignedArray;
begin
 A.Length := 1;
 A[0].x := 100; // Doesn’t work, writes to a copy and never mutates the 
underlying structure.

Is there no other way to specify alignment? It would be ugly but a compiler 
directive could be used.

var
 {$push}
 {$dynamic-array-align 4096}
 a: array of integer;
 {$pop}
begin
  SetLength(a,10); // just use normal SetLength now

Regards,
Ryan Joseph

___
fpc-devel maillist  -  fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Re: [fpc-devel] Aligned dynamic arrays

[Marco van de Voort]

Op 3/28/2019 om 11:40 PM schreef Anthony Walter:
Here is a brief follow up. I am working on other projects at the 
moment, but I am confident this a simple solution. Please tell me if 
this somehow will not fit you needs.

My needs are simple:

- auto clean like dynamic arrays.
- preferably transparent with all existing mechanisms.
- performance is important so no getters and setters (the units are 
pixels, and getters and setters in such cases slow down too much).
- I mostly align for SSE/AVX not DMA, so my alignment is typically 
64byte, I'd rather not use special functions that don't allocate via the 
pascal suballocator, that would only

increase fragmentation

However currently I have stowed the alignment requirement away in a few 
classes which are manually specialized versions of a generic one for 
different pixel size derive/specialize (*), so while I'm an alignment user,

I'm not the best motivation to pull it in language.


(*) 8-bit grayscale and  24-bit RGB have manually specialized classes, 
the rest uses an generic, which optimizes not as well in Delphi, but 
good enough for all but the most extreme speed.  The 24-bit RGB case is 
also due to bugs in older (<=XE6) Delphis that

don't deal well with pointer math of 3-byte types.
___
fpc-devel maillist  -  fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Re: [fpc-devel] Aligned dynamic arrays

[Sven Barth via fpc-devel]

Am 29.03.2019 um 17:53 schrieb Ryan Joseph:

First minor snag, fpc_dynarray_insert, fpc_dynarray_concat can allocate new 
arrays like SetLength can. Do we need to make aligned variants for these also? 
Using array + operators there is no possibility to set alignment.

var
   a, b: array of integer;
begin
   a += [1]; // no way to set alignment for a

   insert(1, b, 0); // no way to set alignment for b
end.

Some options:

1) ignore the problem
2) make extra syntax like:

a: array of integer; alignment = 64;

3) make another function to allocate an empty array that sets alignment

SetAlignment(a, 64);
An empty array is Nil, changing that would lead to a whole different can 
of worms.

4) for insert/concat make variants like InsertAligned() and ignore + operators 
for aligned arrays
Ignoring something is not an answer. At least there'd need to be a 
runtime error.


Thinking about it maybe it would be better to follow Anthony's idea with 
the record and not try to adjust/extend a language mechanism that wasn't 
geared for that.


Regards,
Sven
___
fpc-devel maillist  -  fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Re: [fpc-devel] Aligned dynamic arrays / Maybe implement in mem-mgr?

[Ryan Joseph]

> On Mar 29, 2019, at 1:21 PM, Martin Frb  wrote:
> 
> Question: Should the alignment be "user data" or "type info".
> Does it need to be determined at runtime, and set to different values (for 
> the same type/variable) at runtime?

I’m just doing what Sven said I could do, which is store the info in the 
dynamic array header and add a “SetLengthAligned” intrinsic. Maybe the new 
problem changes things though.

As for the memory manager I’m not sure that helps because of how the dynamic 
arrays are already implemented. It would have to be extended to return an 
aligned block that had x number of bytes directly before it. No idea if that’s 
feasible for memory managers.

Regards,
Ryan Joseph

___
fpc-devel maillist  -  fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Re: [fpc-devel] Aligned dynamic arrays / Maybe implement in mem-mgr?

[Martin Frb]

On 29/03/2019 17:53, Ryan Joseph wrote:

First minor snag, fpc_dynarray_insert, fpc_dynarray_concat can allocate new 
arrays like SetLength can. Do we need to make aligned variants for these also? 
Using array + operators there is no possibility to set alignment.

1) ignore the problem
2) make extra syntax like:

a: array of integer; alignment = 64;

3) make another function to allocate an empty array that sets alignment

SetAlignment(a, 64);
4) for insert/concat make variants like InsertAligned() and ignore + operators 
for aligned arrays



Question: Should the alignment be "user data" or "type info".
Does it need to be determined at runtime, and set to different values 
(for the same type/variable) at runtime?


If not, i.e. if a specific variable always needs 4k alignment, would it 
not be more logical to make it part of the type?

   type TFoo = array [x..y] of byte aligned 4096;

Of course that does not change the above problem.
The (current or fixed) alignment needs to be stored, so concat can 
retrieve it and honour it.

Stored either in the header or the RTTI type info



Question 2:
Would it not be more efficient, if the alignment would happen in the 
memory manager?
Then no over-allocation would be needed. And the memory that is skipped 
in front of the array could be used for other data.


The memory manager would need 2 new methods:
AllocMemAtAllignment
FreeMemWithAllignment

So the array still needs to know, it was allocated with Allignment and 
call the correct  FreeMemWithAllignment.
As a default for all memory manager AllocMemAtAllignment could do the 
over-allocate, and return the correct pointer, with the mem-managers 
align header.

Individual MemManagers can then be optimized.

pseudo code for AllocMemAtAllignment
  mem := alloc(size+align+sizeof(MemMgrAlignHeader))
  result := getNextAlignedAddr(mem+sizeof(MemMgrAlignHeader))
  (result-sizeof(MemMgrAlignHeader)) ^.RealAllocAddr := mem;

The result looks then like
  mem
 // padding
  result - header:
 RealAllocAddr
  result
    // At least size bytes

So pretty much what would have happened in the array code. But moved to 
the mem-manager.

So it can be:
a) re-used for other types or even called by usercode
b) a mem-manager that can get the aligned address without padding, can 
be optimized, and return a normal block of memory

  (does not even need the MemMgrAlignHeader)











___
fpc-devel maillist  -  fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Re: [fpc-devel] Aligned dynamic arrays

[Ryan Joseph]

First minor snag, fpc_dynarray_insert, fpc_dynarray_concat can allocate new 
arrays like SetLength can. Do we need to make aligned variants for these also? 
Using array + operators there is no possibility to set alignment.

var
  a, b: array of integer;
begin
  a += [1]; // no way to set alignment for a

  insert(1, b, 0); // no way to set alignment for b
end.

Some options:

1) ignore the problem
2) make extra syntax like: 

a: array of integer; alignment = 64;

3) make another function to allocate an empty array that sets alignment

SetAlignment(a, 64);
4) for insert/concat make variants like InsertAligned() and ignore + operators 
for aligned arrays

Regards,
Ryan Joseph

___
fpc-devel maillist  -  fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Re: [fpc-devel] Aligned dynamic arrays

[Anthony Walter]

Gareth,

There is a bounty for this? I wonder if my solution is acceptable.

Also, my solution, or any for that matter, could be enhanced to make the
alignment size configurable per each array aligned array. That is, memory
alignment starting position and page size could be defined by each array.
This would allow for more flexibility and would be trivial enough to adapt
to what I've provided.

Finally, these methods could be added to the type, making it like a super
array or list:

{ Returns the lower bounds of the list }
function Lo: Integer;
{ Returns the upper bounds of the list }
function Hi: Integer;
{ Reverses the items in the list }
procedure Reverse;
{ Swap two items by index in the list }
procedure Exchange(A, B: Integer);
{ Adds and item to the end of the list }
procedure PushRange(const Collection: array of T);
{ Remove an item randomly from the list }
function PopRandom: T;
{ Return a copy of the list with items passing through a filter }
function Filter(Func: TFilterFunc): TArrayList;
{ Return the first item matching a condition }
function FirstOf(Func: TFilterFunc): T;
{ Removes an item by index from the list and decreases the count by one
}
procedure Delete(Index: Integer);
{ Sort the items using a comparer }
procedure Sort(Order: TSortingOrder = soAscend; Comparer: TCompare =
nil);
{ Attempt to find the item using DefaultCompare }
function IndexOf(const Item: T): Integer;
{ Join a the array into a string using a separator }
function Join(const Separator: string; Convert: TConvertString =
nil): string;
{ Returns true if ther are no items in the list }
property IsEmpty: Boolean read GetIsEmpty;
{ First item in the list }
property First: T read GetFirst write SetFirst;
{ Last item in the list }
property Last: T read GetLast write SetLast;
___
fpc-devel maillist  -  fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Re: [fpc-devel] Aligned dynamic arrays

[J. Gareth Moreton]

 I wonder if there's any incentive to have such a feature in-built in the
compiler.  The bounty on #34031 has probably expired by now.  If not,
then your unit would be a great addition.
 Page-aligned memory is probably something that warrants further discussion
with the core team.

 Gareth aka. Kit

 On Fri 29/03/19 05:01 , "Anthony Walter" sys...@gmail.com sent:
 Here is the full implementation of aligned arrays, let me know if it works
for you.
 https://www.getlazarus.org/arrays/ [1]

 Here is another example:
 uses  AlignArrays;
  procedure Test;var
   VertexData: TAlignedArray;  V: PVec3;  I: Integer;begin 
VertexData.Length := 100; // page sized and aligned memory allocated here
  V := VertexData[0]; // get a reference to the first item  for I := 0 to
V.Length - 1 do  begin    V^ := ComputeVertex(I); // write to vertex
data faster via a pointer
     Inc(V);  end;   for V in VertexData do // array like enumerators
are supported    PrintVertex(V);  V.Item[6] :=
ComputeVertex(Random(100)); // you can write directly using this syntax 
V[7]^ := ComputeVertex(Random(100)); // or write by dereferencing  the
default indexer end; // there is no need to free the memory, it is taken
care of for you by finalize
  

Links:
--
[1] https://www.getlazarus.org/arrays/
___
fpc-devel maillist  -  fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel