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

orion said…
neat!

i just discovered that about 55% of my code's time is being used in TAvatar >> extent, (which boils down to 30% in TGroup >> boundingBox and another 20% tacked on by TMesh >> boundingBox).

I call TAvatar extent once per frame per avatar per collision object.

.. A quick change to Latch the value of extent just knocked that 55% down to 0%, and it's visibly quite faster when connected.
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. 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: can be 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 controls the inputs to these identi

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

Emulating Smalltalk-76

If you got as excited as me about Dan Ingalls' live Smalltalk-76 demo on an actual 1970's Xerox Alto, you may have wanted to try it yourself.  For one, you could try my Smalltalk-78 VM. Smalltalk-78 is a leaner version of Smalltalk-76 but very much identical in syntax semantics.  It is also possible to run the full Smalltalk-76 environment, and here is how: First, you need an emulator for the Alto computer. Ken Shiriff posted a nice piece on how to run ContrAlto on Windows . It is written in C# and I got it to work on my Mac using Mono. So here's a step-by-step: Install Mono from  http://www.mono-project.com/download/ Download ContrAlto-mono.zip from https://github.com/livingcomputermuseum/ContrAlto/releases Download this Smalltalk-76 disk image: http://www.bitsavers.org/bits/Xerox/Alto/disk_images/chm/xmsmall.zip Unzip both  ContrAlto-mono.zip  and  xmsmall.zip  in the same folder. In a terminal, change to the ContrAlto directory and run mono Contralto.exe .