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:
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:
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:
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).
Not quite. There are two things you have to keep in mind when it comes to performance:
- When in doubt, measure.
- You are in doubt.
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) *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.
(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
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) lengthwhich 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