Are FP dynamic arrays really that slow, or did I miss something?

[Rochus]

My FP implementation of the Storage benchmark runs extremely slow. On x86 the FP version runs half as fast as the LuaJIT version, and on x86_64 LuaJIT (i.e. the Lua version just using dynamic Lua tables) is even three times as fast as the FP implementation.

Here is the FP code: https://github.com/rochus-keller/Are-we-fast-yet/blob/main/FreePascal/Storage.pas. I first had the newly created array as a return value of buildTreeDepth but then switched to a var parameter in hope that it might become faster. Didn't help. I assume I did something wrong since I cannot believe it is so slow by design. But keep in mind, the goal of the benchmark is to compare ideomatic code, i.e. as it would be written by someone with no knowledge about compiler internals and with no C style trickery.

Here are the C++ and Lua implementations for comparison:

https://github.com/rochus-keller/Are-we-fast-yet/blob/main/Cpp/Storage.cpp

https://github.com/rochus-keller/Are-we-fast-yet/blob/main/Lua/storage.lua

In Oberon a dynamic array is realized as a pointer to an array, and the array is allocated with new(ptr, size). I didn't understand what it actually is in FP. Is it automatically initialized? What initial size does it have? What actually happens when I pass it by var to a procedure?

[jamie]

They are managed, and yes, depending on you are doing the managed arrays may not be a speed demon.

Use unmanaged arrays instead.


How about showing us some code on how you are using them?

[Rochus]

Use unmanaged arrays instead.

My reference is the "FreePascal Language Reference Guide 3.2.2". It only defines "static" and "dynamic" arrays. The length is determined at runtime, so I use "dynamic" arrays as recommended in the spec. What is an "unmanaged array"? Didn't find it in the spec.

How about showing us some code on how you are using them?

I posted the link to the source file in my question.

[jamie]

When you change the size of a dynamic array, it normally has to recreate the table in new memory and then copy over the existing.

 Now, I didn't really look that deep there, but I noticed you aren't showing the benchmark code which obviously can play a part in it. Also, you are using virtual methods in the objects which slow things down.

[runewalsh]

Creating many arrays and objects might be slow because they are filled with zeros. (Objects are zeroed by their constructors.)

Instead of ar: array of SomeType, try C-style par: PSomeType allocated with par := GetMem(count * sizeof(SomeType)). Instead of objects, try managed records (or just objects without constructors, destructors, and virtual methods; use ordinary methods instead, i.e. new(obj); obj^.init_method). (Classes are even slower btw: their creation involves the same zeroing, but then does even more stuff.)

If it does not help, the reason might be the memory manager... but first make sure you don’t have heaptrc enabled and run outside of the debugger (I don’t know how, but it sometimes affects my allocation-heavy cases even without heaptrc).

[Rochus]

When you change the size of a dynamic array, it normally has to recreate the table in new memory and then copy over the existing.

I call setLength() exactly once per created dynamic array; I apparently have to call this procedure at least once, otherwise the dynamic array has an indefinite size.

... but I noticed you aren't showing the benchmark code which obviously can play a part in it. Also, you are using virtual methods in the objects which slow things down.

The link in my question pionts to the benchmark code.

I don't think virtual methods are an issue in FP compared to e.g. C++, otherwise the other benchmarks would show low performance as well.

[Rochus]

Instead of ar: array of SomeType, try C-style par: PSomeType allocated with par := GetMem(count * sizeof(SomeType)).

Thanks for the hint. But isn't it actually that we use Pascal instead of C to avoid exactly things like pointer arithmetics and untyped memory? Do I really have to avoid the official language support for dynamic arrays for performance reasons?

but first make sure you don’t have heaptrc enabled and run outside of the debugger

I only call fpc Main and then run Main, nothing else.

[runewalsh]

...Also, C-style array will allow you to do fewer allocations, as you do in non-vector C++ version.

The potential issue (probably very minor) with constructors, destructors, and virtual methods (in Tree, not TBenchmark, of course) is that they add a VMT pointer.

Do I really have to avoid the official language support for dynamic arrays for performance reasons?

Remind me why you avoided vectors in C++. C:

[Rochus]

Remind me why you avoided vectors in C++. C:

T* t = new T[n] and delete[] t is perfectly legal in C++ and also type safe; why shouldn't I use it? The approach you recommend looks rather like T* t = malloc(n * sizeof(T)) in C, where this kind of trickery is the usual way to go. But this is Pascal, not C.

EDIT: and since you asked: I avoided all STL collections because that's the rule of the benchmark; the rule is to only use the data structures built into the language or the ones provided with the benchmark (which I haven't implemented yet); if every language implementation does so, we have the chance to make fair comparisons. But besides that there is nothing wrong with std::vector per se and usually it's not slower than manual memory management, but of course it can be used in inefficient ways by people with little experience. That's why I'm asking here whether I correctly applied FP dynamic arrays.

[alpine]

I can't compile it. TBenchmark.verifyResult has a parameter named 'result'. Unit Run uses unix, etc.

@Rochus
What FPC version you're using and why 'objects' instead of 'classes'?

Mine is: Lazarus 2.2.2 (rev lazarus_2_2_2) FPC 3.2.2 i386-win32-win32/win64

[runewalsh]

T* t = new T[n] and delete[] t is perfectly legal in C++ and also type safe.

They might be more type safe than malloc but aren’t quite safe in general: delete[] vs. delete, no RAII. Yes “Pascal is not C” but you don’t have one-line equivalent to new T[n], and GetMem is closer to your C++ solution, while array of would be closer to vectors (still slower, but not as much).

Btw, what if the reason of slow dynamic arrays in this example is exactly the absence of https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/383. 😱

[marcov]

Free Pascal also has a slower random generator. Try filling a block of memory with random values before entering the benchmarked loop and see if that matters.

[Rochus]

What FPC version you're using and why 'objects' instead of 'classes'?

It's FPC 3.2.2 in standard mode. Just compile with "fpc Main" and then run "Main".

[Rochus]

Free Pascal also has a slower random generator. Try filling a block of memory with random values before entering the benchmarked loop and see if that matters.

Thanks for the hint. I don't use the FP random generator, but generate my own "random" numbers, as requested by the benchmark guidelines.

But I still didn't get a confirmation that my code in Storage.pas looks decently, or that there are misconceptions which I should fix.

[marcov]

But I still didn't get a confirmation that my code in Storage.pas looks decently, or that there are misconceptions which I should fix.

As far as my limited C++ goes, you allocate an array of objects in C++ but an array of references to objects (with individual getmem) for Freepascal.

Simply see if you can get further by changing Treelist to 

Code: Pascal  [Select][+][-]

1.                 TreeList = array of Tree;  

below the Tree definition to satisfy define before use (pointers are the exception to that )

The setlength allocates the memory, and the constructor call initializes.

Code: [Select]

setLength(t,len);   /
for i := 0 to len-1 do
  t[i].init;

Probably you need to make sub ttreelist also. (since dynamic arrays are already references).

But it is hard for me to guess because of low familiarity of C++, and I also have little experience in performance optimization for the TP object that I never use.