Speeding up algorithm

General
21

Couple of years ago I created a project that used an in-memory sqlite database instead of an array to hold the sprites. You can have a look at it here.

22

Thx all. By-the-way, the difference in speed between a compile on Windows (Core I7) and a compile on Mac (M1) is enormous.

23

Can we have the numbers ? Please ?

24

Coming up

25

At least tell us which one was faster.

1 Like
26

That code is pretty fast. I added some logging to it and Iā€™m getting CheckCollisions() running in about 8-10 milliseconds for 501 circles on a 5K screen (macOS, Intel core i9, 2.4GHz). Aggressive optimization.

I did some further cleanup:

  • moved some of the temporary variables into the method (you had them as window properties which is probably slower)
  • did a trick where instead of calculating distance as the square Root, just calculate distanceSquared - only doing the actual sqrt() call if there is a collision.
  • added #pragmas to some of the other functions that are being called.

This did seem to help, and now am getting about 5-6 milliseconds, so about 50% faster.

My modifications attached. Note that you can open Console.app and search for ā€œcheckCollisionā€ and youā€™ll see the speed being logged:

XojoFramework 82731 16:29:13.487493-0700 default MainWindow.CheckCollision took 0 msec for 0 objects BouncingBalls
XojoFramework 82731 16:29:15.836035-0700 default MainWindow.CheckCollision took 0 msec for 51 objects BouncingBalls
XojoFramework 82731 16:29:17.838963-0700 default MainWindow.CheckCollision took 3 msec for 501 objects BouncingBalls
XojoFramework 82731 16:29:19.838444-0700 default MainWindow.CheckCollision took 3 msec for 501 objects BouncingBalls

Updated project:
BouncingBallsWithMassVelocityOptimized2.xojo_binary_project.zip (16.2 KB)

1 Like
27

You donā€™t need to compute distance. You can drop the Sqrt() by comparing distance-squared to distance-squared.

28

You can also compare the Manhattan distance as a pre-screen which doesnā€™t require any multiplications, and then do the multiplications only if the Manhattan distance falls below the collision distance. Thatā€™s essentially what my earlier post was about.

29

The execution of a compiled (not built) app is way slower on a Core I7 Windows 11 machine than on a Mac M1 with circles <50. Iā€™ve used Mikeā€™s optimized code. - thanks Mike!

Screenshot Win
Screenshot Win1030Ɨ313 30.3 KB

Screenshot Mac
Screenshot Mac1516Ɨ402 160 KB

1.4340 for Win (I7 32 Gb) vs. 1.0093 for Mac (M1 8 Gb)

30

On a MacBook Pro M1 with attached Retina screen in full screen mode, with a few code changes I got frame rates around 200 FPS to up about 950 circles in the build. Which is quite impressive compared to former times. So yes, you can reduce the timer period, with some hints:

In animations, itā€™s better to go for a certain fixed screen refresh period and consider the circleā€™s impulses as speed vectors, so that first you check the exact passed time since last update and draw the circles relative to this time. This avoids stuttering animations.

If you donā€™t change the timer period when the speed slider is moved but rather take a fraction of its value as a multiplication factor, screen refresh stays persistent and slowed down phases are very smooth.

EDIT: With Mikeā€™s simplified check, 60 FPS limit is now at around 1500 circles on a 4K screen. I changed some sliders and added a FPS label:
BouncingBallsWithMassVelocityOptimizedUB.xojo_binary_project.zip (17.1 KB)

1 Like
31

Before calculate distanceSquared you can check if dx > (ci.radius + cj.radius) or dy > (ci.radius + cj.radius) like this :

dx = cj.x - ci.x
dy = cj.y - ci.y

var l2radius As Double
l2radius = ci.radius + cj.radius

if (dx > l2radius) or (dy > l2radius) then
else
  //distance = Sqrt(dx * dx + dy * dy)
  distanceSquared = dx * dx + dy * dy
32

Nice! To really get crazy speeds, the next step would be to figure out a way to use Preemptive Threading and break the problem up so that it can be completed on multiple cores. Coming Soon (probably)

1 Like
33

my rework (just for fun) with a thread, use the circle slider to max in compiled exe.
Bouncing Balls MR.zip (15.0 KB)

grafik
grafik1920Ɨ1080 198 KB

3 Likes
34

Thanks for sharing :slight_smile:

35

Thanks for sharing, but this is just the co-operative thread right? Not the pre-emptive. I do not see much improvement as the algorithm must loop balls^2 times whether this happens in a separate thread or the main thread makes IMHO not much difference?

36

i read xojo create something to replace the worker class.
i not have latest xojo. but i see Preemptive Threading feature in latest news letter yesterday.

37

By storing the value of UBound(Circles) in a variable before the For loops will mean the call to UBound(Circles) will not have to be done each time round each loop, saving time.

Var MaxCircles As Integer = UBound(Circles)

For i As Integer = 0 to MaxCircles

For j As Integer = i+1 to MaxCircles
1 Like
38

There are more advanced approaches, such as where you maintain a tree like structure of where each circle is on the screen. You might have areas such as

Top Left
Top Right
Bottom Left
Bottom Right
Top
Bottom
All

You determine which area your circle is in and then you only need to compare it to the circles in the same area.