[fpc-pascal] about dynamic array

["Vinzent Höfler"]

> 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.

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. ;)

> 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).

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

> 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

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.

-- 
GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT!
Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01