Dynamic arrays using management operators

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Dynamic arrays using management operators

Ryan Joseph
Since we were talking about dynamic arrays I was curious to see if they could be implemented using the new management operators so I made a little proof of concept by cobbling together old code. It’s not complete or very good by any means but I think it’s a pretty interesting alternative to using dynamic arrays. Being able to add operators and methods is nice, especially since type helpers (that we could use on dynamic arrays) are so limited by single scopes currently. Specifically it’s nice to just declare an array and say “a += 1” without anything else. Having the implementation in a unit is good also in case you need to mess with something for specific performant reasons.

Not sure if this is useful or not but it’s certainly a milestone for Pascal to be able to make complex data types that integrate so well into the language and are so easy to use and manage.

https://github.com/genericptr/Managed-Arrays-Dictionaries

TIntArray = specialize TDynArray<integer>;

var
  a: TIntArray;
begin
  d.AddValues([1, 2, 3]); // := assignment operator for implicit arrays [] are broken currently
  a += 4;
  for i in a do
    writeln(i);
end;

TIntDict = specialize TDynDictionary<integer>;

var
  dict: TIntDict;
  entry: TIntDict.TEntryPtr;
begin
  dict.SetValues([
    'a', 1,
    'b', 2
   ]);
  dict.SetValue('c', 3);

  if dict['a'] = 1 then
    writeln('a = 1');

  for entry in dict do
  if entry^.IsValid then
    writeln(entry^.key, ' => ', entry^.value);
end;


Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Michael Van Canneyt


On Mon, 4 Jun 2018, Ryan Joseph wrote:

> Since we were talking about dynamic arrays I was curious to see if they could be implemented using the new management operators so I made a little proof of concept by cobbling together old code. It’s not complete or very good by any means but I think it’s a pretty interesting alternative to using dynamic arrays. Being able to add operators and methods is nice, especially since type helpers (that we could use on dynamic arrays) are so limited by single scopes currently. Specifically it’s nice to just declare an array and say “a += 1” without anything else. Having the implementation in a unit is good also in case you need to mess with something for specific performant reasons.
>
> Not sure if this is useful or not but it’s certainly a milestone for Pascal to be able to make complex data types that integrate so well into the language and are so easy to use and manage.
>
> https://github.com/genericptr/Managed-Arrays-Dictionaries

I fail to see why you need management operators for this.

If you declare your array in the record as a dynamic array, everything
will be done for you.

The array is private. This means that the reference count will be 0 or 1.
When the record goes out of scope, the compiler code will free it.

Unless I missed something which is always a possibility.

Michael.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Ryan Joseph


> On Jun 4, 2018, at 4:39 PM, Michael Van Canneyt <[hidden email]> wrote:
>
> I fail to see why you need management operators for this.

just because I wanted the array implementation available and to get automatic cleanup. I don’t know all the stuff dynamic arrays do behind the scenes and that worries me (see below).

>
> If you declare your array in the record as a dynamic array, everything
> will be done for you.
>
> The array is private. This means that the reference count will be 0 or 1.
> When the record goes out of scope, the compiler code will free it.
>
> Unless I missed something which is always a possibility.

The ref counting is basically useless right now because the record needs to be passed by reference. All the internals like the ref count need to be stored as a pointer I think but I wanted this to be bare-bones and fast. Anyways it’s really just for single functions or globals, otherwise I’d use a class.

Mainly I just thought it was cool FPC can finally do this and if you wanted to you could make a robust implementation that did real ref counting. I had the problem with thread locking code getting called and killing performance so I won’t use dynamic arrays anymore because I don’t trust them. Using management operators with manual memory allocation gives you access to the implementation also in case you need to change something or need performance tuning (distrust of dynamic arrays really drives this idea for me). If I want to change something about dynamic arrays implementation it’s probably impossible for me personally to figure it out.

Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Ryan Joseph
In reply to this post by Michael Van Canneyt


> On Jun 4, 2018, at 4:39 PM, Michael Van Canneyt <[hidden email]> wrote:
>
> The array is private. This means that the reference count will be 0 or 1.

I looked at the examples on the wiki and think by private you mean that the ref count does indeed need to be a pointer so it gets updated for all references. I didn’t get that until just now. Since there’s already an array for the elements I guess just allocate all members of the record into a single block of the memory with the elements on the end. Thanks for pointing that out, I’ll fix it later.

Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Michael Van Canneyt
In reply to this post by Ryan Joseph


On Mon, 4 Jun 2018, Ryan Joseph wrote:

>
>
>> On Jun 4, 2018, at 4:39 PM, Michael Van Canneyt <[hidden email]> wrote:
>>
>> I fail to see why you need management operators for this.
>
> just because I wanted the array implementation available and to get automatic cleanup. I don’t know all the stuff dynamic arrays do behind the scenes and that worries me (see below).

Well, as far as I can see, you are repeating what the compiler already does for you out of the box.

Michael.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Ryan Joseph


> On Jun 4, 2018, at 5:46 PM, Michael Van Canneyt <[hidden email]> wrote:
>
> Well, as far as I can see, you are repeating what the compiler already does for you out of the box.

But it’s customizable, that’s the point. What happens when you remove an element from a dynamic array? I don’t even know where to look in the source code to find out and if I want to change something I can’t. Do dynamic arrays resize memory when you remove elements? Maybe I don’t want that. Maybe I want to grow the array at different intervals, can’t do that either.

I know this is very fringe but I personally needed to customize dynamic arrays to escape that thread safety thing and when I couldn’t I had to make my own array wrapper class which I would have preferred to be a record in many instances, which I can do now. If nothing else it saves me lots of Create/Free calls in countless functions. Pretty good news.

If I actually made a competent implementation (which I’ll do later) dynamic arrays are possibly made redundant even, or close to it (providing the FPC RTL had something like them included).

Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Michael Van Canneyt


On Mon, 4 Jun 2018, Ryan Joseph wrote:

>
>
>> On Jun 4, 2018, at 5:46 PM, Michael Van Canneyt <[hidden email]> wrote:
>>
>> Well, as far as I can see, you are repeating what the compiler already does for you out of the box.
>
> But it’s customizable, that’s the point. What happens when you remove an element from a dynamic array? I don’t even know where to look in the source code to find out and if I want to change something I can’t. Do dynamic arrays resize memory when you remove elements? Maybe I don’t want that. Maybe I want to grow the array at different intervals, can’t do that either.
>
> I know this is very fringe but I personally needed to customize dynamic arrays to escape that thread safety thing and when I couldn’t I had to make my own array wrapper class which I would have preferred to be a record in many instances, which I can do now. If nothing else it saves me lots of Create/Free calls in countless functions. Pretty good news.
>
> If I actually made a competent implementation (which I’ll do later) dynamic arrays are possibly made redundant even, or close to it (providing the FPC RTL had something like them included).
I do not advocate that you drop your custom record.

I'm just saying that *the management operators* are not needed for your
use-case, based on what I see, if you would use dynamic arrays instead of
manually managing the memory. It will simplify your code.

All the rest of what you do remains exactly the same.
Dynamic arrays do far less than what you seem to assume.

All in all, it seems to me that you do not actually know what dynamic
arrays are really about, so instead of spending a lot of time
re-implementing what is there, maybe better learn what they do
(and don't do).

They make life easier by reducing the need for manual memory
management. No more, no less. Other than that they behave like normal
arrays on the heap.

Michael.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Martin Schreiber-2
On Monday 04 June 2018 16:12:27 Michael Van Canneyt wrote:
>
> They make life easier by reducing the need for manual memory
> management. No more, no less. Other than that they behave like normal
> arrays on the heap.
>
It seems that the inclocked()/declocked() operations completely destroy the
performance of the OP's application (which I find strange) so he never want
to touch dynamic arrays anymore as he wrote.

Martin
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Ryan Joseph
In reply to this post by Michael Van Canneyt

> On Jun 4, 2018, at 9:12 PM, Michael Van Canneyt <[hidden email]> wrote:
>
> All the rest of what you do remains exactly the same. Dynamic arrays do far less than what you seem to assume.

As noted the inclocked()/declocked() calls destroyed some performance sensitive parts of my code while testing and I had a choice to try to figure out the FPC or sources or just replace the dynamic arrays with my own memory management (totally trivial anyways). The dynamic arrays where inside of a class which I had to make anyways so I could extend the dynamic arrays to have append operations and optionally not resize memory when removing elements (I don’t know if dynamic arrays do that or not, who knows). I wish I kept the old performance profiles so we could look at them again.

It’s so trivial to make a class wrapper around simple memory management like arrays I felt like it was strange to use a hidden implementation that I couldn’t control 100%. It feels like RTL kind of stuff.

Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Ryan Joseph
In reply to this post by Martin Schreiber-2


> On Jun 4, 2018, at 9:21 PM, Martin Schreiber <[hidden email]> wrote:
>
> It seems that the inclocked()/declocked() operations completely destroy the
> performance of the OP's application (which I find strange) so he never want
> to touch dynamic arrays anymore as he wrote.

It was one hyper sensitive part of a sorting algorithm and it may have been a bug for all I know but it was less work to replace dynamic arrays with GetMem/FreeMem and get on with the day.

Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Ryan Joseph
In reply to this post by Ryan Joseph

I fixed up my code on GitHub so the records members including the ref count are actually on the heap so the ref count is actually used now. :) There’s still 2 problems though that make dynamic arrays better:

1) the := operator for implicit arrays like [1,2,3] is bugged currently so requires a really long and ugly type cast (a := TIntArray.ValueArray([1,2,3]);) . Sven just got a := [] syntax working for dynamic arrays so record wrappers are harder to use in that regard. Hopefully that can be fixed.

2) dynamic arrays can index directly into records and write to fields but the [] operator overload can’t do this. That’s really annoying because you need to use calls like a.GetValuePtr(0)^.x := 1 to assign to an array of Vec2’s. Dynamic arrays could just do a[0].x := 1;


#2 is maybe not fixable for FPC without serious intervention. Basically it requires something like C++’s  & alias which makes a pointer but assumes the pointer -> syntax. FPC can’t overload functions by result type so you’d have to choose one or the other and be stuck with always using ^ to dereference  , even for read operations.

        property ArrayValues[index:TArrayIndex]: T read GetValue; default;
        property ArrayValuesPtr[index:TArrayIndex]: TArrayValuePtr read GetValuePtr;

So yeah dynamic arrays for records are still a better choice unless you don’t need to “index and write”.


Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Nitorami
>2) dynamic arrays can index directly into records and write to fields but
the [] operator overload can’t do this.

I don't understand this, can you provide an example ?



--
Sent from: http://free-pascal-general.1045716.n5.nabble.com/
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Free Pascal - General mailing list
Nitorami <[hidden email]> schrieb am Mi., 6. Juni 2018, 22:39:
>2) dynamic arrays can index directly into records and write to fields but
the [] operator overload can’t do this.

I don't understand this, can you provide an example ?

With dynamic arrays that contain records you can do this:

=== code begin ===

var 
  parr: array of TPoint;
begin
  // init parr 
  // ... 
  parr[0].x := 42;
end. 

=== code end ===

However you can't do that with indexed properties (which is the feature that Ryan meant) as the value returned by the property getter is merely a copy and not a reference. 
For completeness sake: for primitive types (except ShortString) and implicit pointer types (classes, interfaces, dynamic arrays, string types except ShortString) this behavior is not relevant.

Regards, 
Sven

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Ryan Joseph


> On Jun 7, 2018, at 4:25 AM, Sven Barth via fpc-pascal <[hidden email]> wrote:
>
> However you can't do that with indexed properties (which is the feature that Ryan meant) as the value returned by the property getter is merely a copy and not a reference.
>

Is there anyway to fix this btw or can I make a feature request? Pascal doesn’t have any concept of a “var result” so we kind of locked ourselves out of references for return result types, unlike C++’s & which can be used for function return results or parameters.

Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Dynamic arrays using management operators

Free Pascal - General mailing list
Ryan Joseph <[hidden email]> schrieb am Do., 7. Juni 2018, 03:32:


> On Jun 7, 2018, at 4:25 AM, Sven Barth via fpc-pascal <[hidden email]> wrote:
>
> However you can't do that with indexed properties (which is the feature that Ryan meant) as the value returned by the property getter is merely a copy and not a reference.
>

Is there anyway to fix this btw or can I make a feature request? Pascal doesn’t have any concept of a “var result” so we kind of locked ourselves out of references for return result types, unlike C++’s & which can be used for function return results or parameters.

From what I know no one of the team is interested in this (me included) so even if you'd do a feature request it would sit there forever. So no, there is no way to fix it. 

Regards, 
Sven 

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal