Skip to main content

Profiling + Vector Math = Performance

So there was a student who implemented a flocking simulation for a virtual fishtank using Croquet. Worked fine with 20 fishes. With 50 fishes it became rather sluggish. Putting in more than 100 fishes the framerate could be measured in seconds per frame. So the rendering in Croquet is too slow, right?

Not quite. There are two things you have to keep in mind when it comes to performance:
  1. When in doubt, measure.
  2. You are in doubt.
So we fired up a message tally (world menu - debug - start MessageTally). Turns out only 12 percent of the time were spent in rendering. So it's not the rendering at all. A whopping 80 percent was taken by the flock's step methods. The leaves of the message tally showed that 15 percent of the time went into each of the methods #x, #y, and #z!

So we looked at the code. Every fish was told to swim in the main direction of its neighbors, that is the fishes within a certain radius. Processing continued only for those fishes in range.

Sounds quite reasonable, doesn't it? The only problem was that to find the neighbors for a fish, the distance to each other fish was compared to the radius. Not only does this result in a quadratic complexity (every fish was tested against every other) but the distance check was this:
(((thisFish position x - otherFish position x) *
(thisFish position x - otherFish position x))+
((thisFish position y - otherFish position y) *
(thisFish position y - otherFish position y))+
((thisFish position z - otherFish position z) *
(thisFish position z - otherFish position z))) sqrt
This guy knows how to take the distance of two points in 3D, and he knows that the square is the product of a number with itself. Very well, but very slow, too.

Vectors in Croquet are represented as FloatArrays, and for a good reason. The reason is that you can compute sums, products, etc. of a zillion numbers very rapidly, just by invoking a single method. This is way faster than doing a component-wise computation on your own. There's a drawback too, which is that because the internal representation of a float in a FloatArray and the one in a normal Float object differs, it is rather expensive to read or write individual elements from such an array.

So to make your math go fast, use vectors instead of home-brew arithmetic. The whole mess above can be replaced by this:
(thisFish position - otherFish position) length
which is way faster.

Of course, one can further improve this by omitting the square root inside #length, by using #squaredLength and comparing to the squared radius, but that would be nit-picking. And of course one should reduce the overall algorithmic complexity from O(n²) to O(n log n), but that's just common sense.

The point I want to drive home is this: Use the class library wisely. If something is too slow, chances are you're doing it the wrong way. Look for examples in the image, there almost always is one. For a nice example of vector math look at the particle system (TParticle).

Comments

Vanessa said…
Bounding boxes are second-class citizens in Croquet. The primary bounding volume is the sphere, indeed a hierarchy of spheres organized as sphere tree. So depending on what you need the avatar's extent for you might be better off using its bounding sphere.

Popular posts from this blog

Frontend-only Multi-Player. Unlimited Bandwidth. Or: What is Croquet.io, really?

A multi-player web app needs a backend, right? What if I told you, it doesn’t? Read on for how Croquet gets rid of servers running your multiplayer code. No, really . Instantaneous Shared Experiences  is how we describe Croquet on our website. And while that excellently describes What Croquet does, as Croquet's Chief Architect, I wanted to share a bit about How we do that. So I wrote a Twitter thread . Here it is in blog form, slightly extended. Click the animation above if it does not play automatically Croquet lets you build completely client-side multi-user web apps. Read that again. Client-side. Multi-user. No I’m not kidding. I built it, I know it works. 😁  Croquet apps run completely client-side: are hosted as a static web site no server-side code needed no networking code needed  Croquet is literally virtualizing the server: Instead of running code on a server (or in a serverless function) we run it as a virtual machine (VM) on each client.  Croquet carefully control

Deconstructing Floats: frexp() and ldexp() in JavaScript

While working on my  SqueakJS VM, it became necessary to deconstruct floating point numbers into their mantissa and exponent parts, and assembling them again. Peeking into the C sources of the regular VM, I saw they use the  frexp ()   and ldexp () functions found in the standard C math library. Unfortunately, JavaScript does not provide these two functions. But surely there must have been someone who needed these before me, right? Sure enough, a Google search came up with a few implementations. However, an hour later I was convinced none of them actually are fully equivalent to the C functions. They were imprecise, that is, deconstructing a float using frexp() and reconstructing it with ldexp() did not result in the original value. But that is the basic use case: for all float values, if [ mantissa , exponent ] = frexp (value) then value = ldexp ( mantissa , exponent ) even if the value is subnormal . None of the implementations (even the complex ones) really worked. I

Smalltalk Bindings for Minecraft Pi

The Raspberry Pi is a cute little computer. Quite cheap at $35, you plug in USB keyboard+mouse and a TV as monitor. And it is surprisingly capable, even for running 3D games. One particularly interesting game is Minecraft: Pi Edition . As in other Minecraft versions, the main goal is to create a world. But unlike other versions, you can not only use the tools provided by the game, you can make your own tools! That's because it comes with a programming interface. The Minecaft world is made of little cubes, and you normally place or remove these blocks by hand, one after another. This is fun, but for larger structures also quite cumbersome. For example, this rainbow here might take a long time to construct manually: But I did not make the rainbow by hand. I programmed it, using the Smalltalk programming language. It's just these dozen lines of code in the Squeak programming environment: Squeak is already installed on the Raspberry Pi, because Scratch was made in Squeak