Static versus dynamic arrays in DBPro?

Author

Message

void

13

Years of Service

User Offline

Joined: 4th Aug 2011

Location:

Posted: 4th Aug 2011 11:45

Link

I'm doing some prototyping with DBP to see how I might want to approach some elements, but I'm noticing that even with dimensions specified in the 'dim' statement, arrays appear to be getting generated as dynamic objects.

I put together some basic logic making use of vectors for positioning and steering, and noticed that as I increased the count of the entities, framerate dropped at a rate much steeper than I would have expected.

I tried setting all of the sprites to hidden, but this had absolutely no effect on framerate, so it's not a rendering issue.

Tweaking the math portions of it had less effect than I would have expected. Given the following table..

50, 750 to 800 fps.
100, 475 to 500 fps
200, 160 to 180 fps
300, 55 to 70 fps
400, 27 to 32 fps
500, 16 to 18 fps

... the behavior seems to be bound to array entry lookup. Are all arrays actually linked lists? Is there no way to have a properly static array?

I attempted to look through the documentation and the forums, but I couldn't find much on this topic. For my current purposes, the additional functionality provided by linked lists/dynamic arrays is unnecessary, as I'm simply iterating over hundreds of objects in sequential order every time.

The array is of a UDT with 7 fields (5 integers, two floats). Admittedly, I don't actually expect to need 500 entities of this type in action at once, but I will need to iterate over the array repeatedly in the rest of the algorithm, and if simple index based lookups require seeking instead of direct access I'm not really sure how to proceed.

In case it matters, I'm currently using the free version of DBPro.

Back to top

Profile PM

BatVink

Moderator

21

Years of Service

User Offline

Joined: 4th Apr 2003

Location: Gods own County, UK

Posted: 4th Aug 2011 13:37 Edited at: 4th Aug 2011 13:45

Link

All arrays are dynamic in DBP, but they are not linked lists. If you add a new element dynamically then the memory used by that array will be reassigned - the newly sized array will find a new home in memory whilst the old is deleted.

If you need 500 elements, create them at the start and code to manage the fact that some of them may be empty (maybe a variable that gives you the last element is use)

You can take this much further, as I wrote about in the newsletter editorial in issue 72. I actually had the same problem here, and the solution to the issue is finally found in that thread here where my code finally speeds up 500% over the original unoptimised method of tracking objects.

Back to top

Profile PM Email

void

13

Years of Service

User Offline

Joined: 4th Aug 2011

Location:

Posted: 4th Aug 2011 21:08

Link

I am, in fact, pre-allocating my array, initializing all of its entities and sprites ahead of time.

I can make an array of 900 entities (complete with set-up for each).. Then if my game loop iterates over 0 to 200, I get the 160 to 180 fps mentioned above.

If I iterate over 700 to 900, I get 7-10 FPS.

There is no creation here, only math, including vector assignments, and sprite commands. That's all.

Like I said. It's behaving as though I'm searching through a linked list instead of directly accessing an array.

A further data point:

If I iterate over 0 to 300 three times per loop, performing all math and rendering steps for each set of iterations, I only drop to 20 FPS. Which is a linear framerate drop with work done, as I would have expected.

What exactly is happening here?

Back to top

Profile PM

void

13

Years of Service

User Offline

Joined: 4th Aug 2011

Location:

Posted: 5th Aug 2011 05:53

Link

Okay, spent some more time on the problem, and I've isolated the issue.

It's not the array I'm using for my data, but the provided vector functions, which appear to demonstrate O(N) behavior, where N is the number of vectors in the system.

I rolled my own vector3 functions, and with identical logic as before I can have 2000 entities before I start to dip below 60 FPS. Around 3000 entities gets me to the ~30-40 FPS range, and I'm still around 20 FPS with 4k entities. This is certainly well within tolerances for my goals.

I'm just surprised that the built-in vector functions are so much slower.

Back to top

Profile PM

Neuro Fuzzy

17

Years of Service

User Offline

Joined: 11th Jun 2007

Location:

Posted: 7th Aug 2011 12:43

Link

hmm... which ones were you using specifically?

Why does blue text appear every time you are near?

Back to top

Profile PM Email

void

13

Years of Service

User Offline

Joined: 4th Aug 2011

Location:

Posted: 7th Aug 2011 12:48

Link

Is there more than one set of built-in vector functions? The DarkBASIC Pro provided vector functions (I tried 2d and 3d) were what was problematic.

Add, subtract, multiply and length were all I used to that point. I didn't investigate further, because once I determined that the vector routines were most definitely O(N), I made my own.

If it's of any use to someone, it'd be trivial to put together a demonstration case.

Back to top

Profile PM

Neuro Fuzzy

17

Years of Service

User Offline

Joined: 11th Jun 2007

Location:

Posted: 7th Aug 2011 23:06

Link

Would you please? I've never heard of a problem like this with the vector commands.

it would also be useful to know how you are iterating over the functions.

Maybe in your custom code you write (x*x+y*y+z*z), but in your vector code you write length vector3(a)*length vector3(a)? that calculates sqrt(x*x+y*y+z*z)*sqrt(x*x+y*y+z*z), so instead of three multiplications and two adds, there are seven multiplications, four adds, and two square roots.

Why does blue text appear every time you are near?

Back to top

Profile PM Email

void

13

Years of Service

User Offline

Joined: 4th Aug 2011

Location:

Posted: 7th Aug 2011 23:42

Link

The problem here is not a math performance issue at all. It's a data access issue.

The more vectors you have in DBP, the longer it takes to access the later added vectors. There's clearly some kind of linked list style structure behind the scenes, which makes the time to access a vector nonlinear based on its key, and since you can add keys in any order, the delay cannot be predicted short of ensuring keys are made in a certain order.

The attached program creates 5000 vector3s, sets them to 0, 0, 0.
Then it iterates over them, performing an add vector3 i, i, i one hundred times.

As i increases, the time it takes to perform this task steadily increases. For the early entries, it's clearly effectively instant, but after a while, it steadily starts taking multiple ms just to do 100 vector adds. On my machine, at entry 5000 it takes 13ms to do 100 vector adds.

To show this isn't related to the actual index number itself, I then delete all the vectors, and recreate them in reverse order, from 5000 to 1.

When I perform the same test of 100 adds from i = 1, it starts at the other end, and steadily decreases as I reach 5000.

You can hit a non-escape key to abort either test in progress (if you abort the first, it goes on to the second), and it pauses to wait for a key between the tests. Obviously, escape at any point will end the program.

Again, the problem here is the cost of accessing any vector is based on when it was added.

I've done other tests with nonsequential entries, and it's consistently been the same. The vector added last is the slowest.

Attachments

Login to view attachments

Back to top

Profile PM

Neuro Fuzzy

17

Years of Service

User Offline

Joined: 11th Jun 2007

Location:

Posted: 8th Aug 2011 05:10

Link

Huh, I see what you mean! I'd guess the same is true for all other math DBPro datatypes (VectorN and matrix4)

Why does blue text appear every time you are near?

Back to top

Profile PM Email

Sorry your browser is not supported!

Newcomers DBPro Corner / Static versus dynamic arrays in DBPro?

Attachments