Hello,

Where can one find information on types like dynamic array? Also, on funcs or procs that apply on them, like setLength & copy. If the answers to the following questions are somewhere, just tell me...

* Can one rely on the fact that setLength keeps existing data (in the range of the new size), both when up- and down-sizing? Or do my trials work only because the pointed memory has not yet been overwritten?

* How is resizing actually performed (is the data moved to a newly allocated area)?

* Does copy onto a dynamic array automatically resize (setLength), even if the target is greater than needed? (I would like no.)

* Can one set the first index where to copy on the target array? (eg to join 2 arrays into a greater one, or to extend an existing one that has free space at tail)

* Can one use copy from/to a *static* array? (If no, why not?)

* What other differences with static array, if any? (Aside the fact that one does not need to explicitely reallocate and copy on resizing.)

For Christmas:

* Can one add or remove an element --at the end? (And have the array behave accordingly.)

* Can one add or remove an element --anywhere? (And have the array behave accordingly.)

If the answers to last 2 questions is "only every 29th of februar", how can one have a "flexible" array? Is there something like that in stock? Would you implement it on top of dynamic array, or rather from scratch on top of static array (since the "dynamicity" does not seem very helpful)?

Denis
________________________________

vit esse estrany ☣

spir.wikidot.com

spir ☣ wrote

Where can one find information on types like dynamic array? Also, on funcs or procs that apply on them, like setLength & copy.

In the documentation: http://www.freepascal.org/docs-html/ref/refsu14.html

* Can one rely on the fact that setLength keeps existing data (in the range of the new size), both when up- and down-sizing?

Yes.

* How is resizing actually performed (is the data moved to a newly allocated area)?

That's implementation-defined.

* Does copy onto a dynamic array automatically resize (setLength), even if the target is greater than needed? (I would like no.)

Copy() creates a copy of the original dynamic array. If you assign the result afterwards to another dynamic array, that other dynamic array is finalised. The copy() operation itself has no idea about what you will do with the result.

* Can one set the first index where to copy on the target array? (eg to join 2 arrays into a greater one, or to extend an existing one that has free space at tail)

See above.

* Can one use copy from/to a *static* array? (If no, why not?)

No, simply because copy() is only defined for dynamic arrays.

* What other differences with static array, if any? (Aside the fact that one does not need to explicitely reallocate and copy on resizing.)

Please read the monster thread that I just closed, rather than starting it all over again.

For Christmas: * Can one add or remove an element --at the end? (And have the array behave accordingly.)

Use setlength to increase/decrease the length by one and add/

* Can one add or remove an element --anywhere? (And have the array behave accordingly.)

Not trivially/efficiently. In general, if you want to do something like that you should use a linked list rather than an array. Arrays are notoriously inefficient (even if you use plain static arrays with move() and other low level operations) if you often have to insert/ delete elements in the middle.

Don't use a hammer to tighten screws.

Jonas

Yes, one can rely on this.

* How is resizing actually performed (is the data moved to a newly allocated area)?

This is an implementation detail which should be of no concern to the user.

What does 'copy onto' mean in these questions ?

* What other differences with static array, if any? (Aside the fact that one does not need to explicitely reallocate and copy on resizing.)

A dynamic array is reference counted.

Thus
   A:=B;

Does not actually copy the entire array, it just lets B point to the same memory area where the array data is stored and increases the reference count. With static arrays

   A:=B;

Will actually create a copy.

For Christmas: * Can one add or remove an element --at the end? (And have the array behave accordingly.)

No.

* Can one add or remove an element --anywhere? (And have the array behave accordingly.)

No.

If you want a flexible array, use TList or TFPList or TCollection from the classes unit.

Michael.

2010/5/6 spir ☣ :

If the answers to last 2 questions is "only every 29th of februar", how can one have a "flexible" array? Is there something like that in stock? Would you implement it on top of dynamic array, or rather from scratch on top of static array (since the "dynamicity" does not seem very helpful)?

Use a list class instead. Descend from TList or embed TList in a class as a field variable. I hardly ever use arrays, simply because list classes can do everything you mention and works as expected.

Right, Michael gives the same advice. What I need is actually a general-purpose sequence type. The point is that insertion/deletion is indeed required, but the most common operations are the ones efficient with arrays, esp. plain item access via index. This is the reason why sequences in dynamic languages (eg python lists) are in fact implemented as flexible arrays, that simply happen to also behave like lists from the point of view of client code. So, if TList is a type of linked list, it can probably not do the job for me. Anyway, I'm not a production programmer & would be pleased to explore this topic as an occasion to learn Pascal and fp further. Tips/pointers welcome. (I'm currently stuck with how to have a [pointer] variable/field refer to a static array which size may change ;-)

denis
________________________________

vit esse estrany ☣

spir.wikidot.com

2010/5/6 spir ☣ :

So, if TList is a type of linked list, it can probably not do the job for me. Anyway, I'm not a production programmer & would be pleased to explore this topic as an occasion to learn Pascal and fp further.

TList wraps TFPList, which is based internally on an array. So access is fast; insertion, deletion not.

Hello FPC-Pascal,

Thursday, May 6, 2010, 3:53:59 PM, you wrote:

c> TList wraps TFPList, which is based internally on an array. So access c> is fast; insertion, deletion not.

But it is faster than inserting elements in a dynamic array (unless reference counted ones) because it usually moves less amount of data (4/8 bytes per element).

Thank you very much, José & Henry, have the information I needed. I'll use TList for all kinds of flexible & ordered sequences.

Denis
________________________________

vit esse estrany ☣

spir.wikidot.com

Why do you think so? You can also create dyn. arrays of pointers.

I guess José is well aware of it, but isn't it a good thing to suggest the use of TFPList to "newbies"?

-Flávio

Hello FPC-Pascal,

FK> Why do you think so? You can also create dyn. arrays of pointers.

I know, but I think this user is looking for a general purpose ordered list accesible by index and TList more or less matches the request and keep a more user friendly interface. Is quote "unless referenced counted ones" because as referenced counted are pointers, a dyn array of strings would be more or less as fast as a TList, well, a bit faster in fact. If the user plans to use a record (which is my suspect) with TList he must "new" and "dispose" the elements and he will end up with a dyn array of pointers after all, which is a TList.

I know that sometimes I over simplify some things, but I think that you'll agree with me that a deeper explain sometimes add fog to a clear concept.

A dyn. array of records requires no new/dispose as well as no type casts as TList does.

Hello FPC-Pascal,

you wrote

> faster in fact. If the user plans to use a record (which is my > suspect) with TList he must "new" and "dispose" the elements and he > will end up with a dyn array of pointers after all, which is a TList.

FK> A dyn. array of records requires no new/dispose as well as no type casts FK> as TList does.

OK, I see :) Do you remember how this veryyyy long thread starts ?

A: array of MyArray;
SetLength(A,x);
A[0]:=MyArrayElement;
Move(A,B,sizeof..);

Entering the doom again... Next question could be why:

p1: TObject;
p2: TObject;
p1:=TObject.Create();
p2:=p1;
P1.free;
p1:=nil;

Why I get an AV if accesing p2 ? Because the object has been freed... So why is not p2 = nil as p1 ?

This kind of messages will end up or in a master class of pointers for dummies or a lot of developers dropping the list for days.

I had proposed the "solution" that I think is easy to understand what happends behind the scenes or maybe I wrongly choose the moment of hit reply :(

The short answer is because you have not set p2 to nil as you did to p1.

Pointer operations (and the disguised ones that are references to class instances and dynamic data structures) are NOT managed for you. You still have to be careful in handling them. That is why the FreeAndNil procedure was created. To help you manage object instance references.

Consider this: The runtime system does not keep track of how many variables you set pointing to a given location. To do so would be VERY inefficient. Therefore, it cannot go out and find all those variables and set them for you. As the programmer you have to do this yourself. That's part of what programming is all about.

Hello FPC-Pascal,

Thursday, May 6, 2010, 9:50:34 PM, you wrote:

DC> The short answer is because you have not set p2 to nil as you did to p1.

I do not want to be rude but, do you read all the message ? I was trying to be ironic, but seems that I was unable maybe due my very limited english, sorry.

Both are good to me. I first implemented my needs as a dynamic array of pointers, precisely. (By the way, started playing with TFPList already, and could not find how to get data back! I mean the symtric of add(). Even tried indexing (who knows, with the syntactic magic of modern language? ;-).)

Denis
________________________________

vit esse estrany ☣

spir.wikidot.com

2010/5/6 spir ☣ :

(By the way, started playing with TFPList already, and could not find how to get data back! I mean the symtric of add(). Even tried indexing (who knows, with the syntactic magic of modern language? ;-).)

It is indexing.

var
  l: TFPList;
  p: Pointer;
  index: Integer;
begin
  l := TFPList.Create;
  index := l.Add(p);
  p := l[index];
end;

You can use it like an array too:

var
  l: TFPList;
begin
  l := TFPList.Create;
  l.Count := 20;
  // now you have l[0]..l[19] elements for read/write
end;

Thank you, I must have written a typo or messed up indices, since now it works fine. Still, remains a mystery about untyped pointers, illustrated by the code below:

var
	l : TFPList;
	i : Integer;
	p : ^Integer;
begin
	l := TFPList.Create;
	i := 1 ; new(p) ; p^ := i; l.Add(p);
	p := l[0] ; writeln(p^);
	writeln(l[0]^);			// error
end.

I cannot directly "fish" and use the pointer's target. Seems I always need to pass _via_ the pointer, then all is fine. It's not really annoying. But I don't understand the difference: in code, both versions are indeed strictly equivalent. I guess there's an implicit (pointer?) conversion somewhere? Are there cases where the pointer's mediation is not needed?

Denis
________________________________

vit esse estrany ☣

spir.wikidot.com

L[0] is an untyped pointer. Dereferencing it gives you a memory address, but not a type. So the compiler doesn't know what to do with it.

p is a pointer to an integer. When dereferencing it, the compiler knows that at the address an integer is waiting, and it knows how to deal with integers.

Adding a typed pointer (p) to an untyped pointer list does not store the type information in the list, any type information available is lost: the compiler or the list do not remember that you stored a pointer to an integer. They just remember the address, not the type.

Michael.

On Fri, 7 May 2010 06:10:30 +0200
cobines wrote:

PS : I also need the pointer's mediation when a func/proc expects a (typed) element. Must rewrite the code to use an element pointer as parameter (and pass a pointer from the list). This is more annoying since it obscures the func/proc's signature.

Is the source of this issue really that these pointers are untyped? If yes, maybe a way to get rid of such noise would be to subtype TFPList into a list of typed pointers?

(I don't know yet how to use fpc's type system. So new in this domain I have no idea what the difference between type & class may be ;-) But this will come soon, I guess...)

Denis
________________________________

vit esse estrany ☣

spir.wikidot.com

Type
   ptInteger = ^Integer;

         writeln(ptInteger(l[0])^);

end.

i.e. cast the untyped pointer into a pointer to integer, so the compiler knows what type of writeln to throw it at.

(untested)

2010/5/7 spir ☣ :

I cannot directly "fish" and use the pointer's target. Seems I always need to pass _via_ the pointer, then all is fine. It's not really annoying. But I don't understand the difference: in code, both versions are indeed strictly equivalent. I guess there's an implicit (pointer?) conversion somewhere? Are there cases where the pointer's mediation is not needed?

There is an implicit conversion when you assign p := l[0], which is
PInteger := Pointer.

TFPList uses untyped Pointer for storage. You would need to make a descendant class of TFPList and change methods to use PInteger (at least for Items property and Get, Put methods). Then use this new class specialized for storing PIntegers instead of TFPList.

Or take a look at generics in FPC. There is a generic class TFPGList defined in unit "fgl". Use it like this:

uses
   fgl;
type
   TPIntegerList = specialize TFPGList<PInteger>;
var
       l : TPIntegerList;
       i : Integer;
       p : ^Integer;
begin
       l := TPIntegerList.Create;
       i := 1 ; new(p) ; p^ := i; l.Add(p);
       p := l[0] ; writeln(p^);
       writeln(l[0]^);                 // no error
end.

Denis,

you need to get up to speed on <types>, since this is one of the fundamental (and better) differences of pascal. You'll find the typing system actually helps you a lot.

FYI, class is one of the possible types. Basically in Pascal, some types are basic: integer, real, some types are structured: records array, some types are objects (coming from TP/BP), some types are classes and interfaces. There are also some special types like variants. You've also seen the difference between static and dynamic types. Please look up the reference manual for that here:
ftp://ftp.freepascal.org/pub/*fpc*/docs-pdf/ref.pdf

About the RTL: you'll find a good manual here:
ftp://ftp.freepascal.org/pub/*fpc*/docs-pdf/rtl.pdf

About TList: it's item type is a untyped pointer, so you can't do anything with the results unless you type it first as mentioned. TObjectList, TComponentList, etc all derive from TList and provide a typed item.

It's a good idea for you, if you need it often, to derive your own TIntegerList from TList (or any other container in Cntnrs or elsewhere). You'll find many tutorials on the web, where TIntegerList is provided.

With the generics now available in FPC, it's also easy to have a whole hierarchy of TGenericLists which could be easily instanciated to TIntegerList as needed.

Out of FPC/Lazarus, there are excellent container libraries, that can reduce your workload. Most of what you need is already there. Decal is one.

Best regards,
Thierry

Implementing a dynamic array via a list implementation which is based on a dynamic array. Sure, that's faster.

Hello FPC-Pascal,

you wrote

> But it is faster than inserting elements in a dynamic array (unless > reference counted ones) because it usually moves less amount of data > (4/8 bytes per element).

VH> Implementing a dynamic array via a list implementation which VH> is based on a dynamic array. Sure, that's faster.

Ok, let me known which operation is faster:

type ItemOfArray=record
  TheData: array [0..4095] of BYTE;
end;
1)
 TheArray: array of ItemArray;
 AnyItem: ItemOfArray;
 [...]
 for j:=0 to 1000 do begin
   SetLength(TheArray,j+1);
   TheArray[j]:=AnyItem;
 end;
 [...]
 Now here add the code to remove element zero from the array and move
 down the upper elements.
2)
  TheList: TList;
  AnyItem: ItemOfArray;
  p: Pointer;
  [...]
  for j:=0 to 1000 do begin
    GetMem(p,Sizeof(AnyItem));
    TheList.Add(p);
  end;
  [...]
  p:=TheList[0];
  FreeMem(p);
  TheList.Remove(0);

----------------------
Remember that the user wants to have an array which could be extended and that allow fast insertion and remove. Of course it would be faster using an array of pointers, but TList will force the user to use an array of pointer, while a dynamic array will not as it can be used with the record type directly.

IMHO the discussion was about how help the user to reach an objetive, not how to reach the objetive in the most efficient way but forcing the user to learn the inners of dynamic array. Remember the begins, "move (dynarray,...,...)" do not work "as expected".

If you think that have a better proposal, write it...

I can have some basic skills at some points in the pascal world, but I'm not stupid at such level to not known that a dynamic array (or similar) is being used in the background of TFPList.

About 1000 GetMem operations (and 1000 assignments which aren't there in the code below, so I won't count them).

Now here add the code to remove element zero from the array and move down the upper elements.

One GetMem, one FreeMem and a (hopefully) fast memory move.

About 1000 GetMems, and potentially another 1000 for extending the list (yes, the internals are more optimized, yet there /will/ be additional calls to GetMem).

[...] p:=TheList[0]; FreeMem(p); TheList.Remove(0);

One explicit FreeMem, one potential FreeMem for resizing the list and a (hopefully) fast memory move.

IMHO the discussion was about how help the user to reach an objetive, not how to reach the objetive in the most efficient way but forcing the user to learn the inners of dynamic array.

And the statement was that using TList would be faster.

I can have some basic skills at some points in the pascal world, but I'm not stupid at such level to not known that a dynamic array (or similar) is being used in the background of TFPList.

So, apart from a possibly more optimized implementation (like not changing the allocated memory size on each single insertion/deletion) how do you come up with the idea that adding another layer would make it faster?

Vinzent.

And quite a few memory moves (depending on how unlucky you are regarding memory fragmentation and how the heap manager handles things).

Yes, about 20.

Which happens quite rarely, since it's only done if the list is half empty.

And depending on the usage patterns and the size of the elements stored in the array, it probably can be. That's all he was saying, and only as a side remark in the context of the discussion (which was meanly to steer away a new programmer from dynamic arrays to tfplist, which I think is a good idea).

Jonas

Hello FPC-Pascal,

Saturday, May 8, 2010, 5:07:12 PM, you wrote:

JM> And depending on the usage patterns and the size of the JM> elements stored in the array, it probably can be. That's all he JM> was saying, and only as a side remark in the context of the JM> discussion (which was meanly to steer away a new programmer from JM> dynamic arrays to tfplist, which I think is a good idea).

Thank you, at least one catch my whole idea about when TList can be faster that dynamic array or a plain GetMem for the array.

Hello FPC-Pascal,

Saturday, May 8, 2010, 4:42:46 PM, you wrote:

VH> So, apart from a possibly more optimized implementation (like VH> not changing the allocated memory size on each single VH> insertion/deletion) how do you come up with the idea that adding VH> another layer would make it faster?

Because it is not "another layer", is a different implementation. You say that my implement was not fair play as I use "SetLength" inside the loop, but the user request fast insertion/deletion so he do not known in advance the amount of items in the array. The code to insert something in a Dyn array is more complex than a remove in TList.

Using dyn arrays and some helper functions to insert/delete elements would be faster and using a helper variable to get the amount of cached entries (not filled) and real entries will end in faster code for sure, but more complex from the end user point of view. TList version imposes more memory fragmentation (each element is in its own block) which could be convenient or not based in the amount of memory available and the current fragmentation (big blocks are not always the better solution).

I take the time to peform the test suggested in previous mail, allowing the dyn array to known the amount of elements available in advance, and here are the results:

Elements Record of bytes Dyn array TList
-------- --------------- --------- --------
1000000 64 187 ms 1328 ms
100000 4096 1032 ms 1046 ms
100000 4095 1469 ms 1031 ms
100000 16384 Crash 5954 ms
10000 65536 1656 ms 2188 ms
10000 65537 2312 ms 2219 ms

The "crash" was due there was not available 1.5 Gby available in one block.

I can post the code if you like.

Well, you didn't say "can" previously, you said "it is faster". That's quite a difference.

Vinzent.

Based on the same underlying data type.

You say that my implement was not fair play as I use "SetLength" inside the loop,

Did I, really?

but the user request fast insertion/deletion so he do not known in advance the amount of items in the array. The code to insert something in a Dyn array is more complex than a remove in TList.

Agreed.

Using dyn arrays and some helper functions to insert/delete elements would be faster and using a helper variable to get the amount of cached entries (not filled) and real entries will end in faster code for sure, but more complex from the end user point of view.

You seem to get my point now. ;)

In my line of work, dynamic memory allocation is not a solution at all. ;)

Well, according to this, the dynamic array performs slightly faster in many cases (which is supporting my previously expressed doubts, isn't it?). Of course, with the above-mentioned cost of keeping track of the data structure, I would not suggest using that unless the performance difference really matters (which it usually doesn't unless you're writing language benchmarks).

Vinzent.

Hello FPC-Pascal,

you wrote

> Thank you, at least one catch my whole idea about when TList can be > faster that dynamic array or a plain GetMem for the array.

VH> Well, you didn't say "can" previously, you said "it is VH> faster". That's quite a difference.

Ok, you are right, I said that.

Hello FPC-Pascal,

Sunday, May 9, 2010, 1:51:20 PM, you wrote:

VH> Well, according to this, the dynamic array performs slightly VH> faster in many cases (which is supporting my previously expressed VH> doubts, isn't it?). Of course, with the above-mentioned cost of VH> keeping track of the data structure, I would not suggest using VH> that unless the performance difference really matters (which it VH> usually doesn't unless you're writing language benchmarks).

So finally we get a common point of view :) Great. To be honest I must say that the dynamic array performs very good removing elements except if memory writes costs too much.

So finally we get a common point of view :)

Sorry to have launched such an argument by starting a new thread "about dynamic array". My purpose, as a newcomer discovering the world of fpc, was just to get information I could not find myself to help me and progress in the jungle ;-)

Denis
________________________________

vit esse estrany ☣

spir.wikidot.com

Hello FPC-Pascal,

Sunday, May 9, 2010, 8:04:24 PM, you wrote:

s> Sorry to have launched such an argument by starting a new s> thread "about dynamic array". My purpose, as a newcomer discovering s> the world of fpc, was just to get information I could not find s> myself to help me and progress in the jungle ;-)

From every discussion something new emerge :)