Spent a fair bit of time yesterday, and then this morning, looking at the speed of some of our most core alternate-math work. Floating-point math is too slow as well as being inaccurate between various computer architectures.
So back around 2009, I switched to fixed-int math in AI War on the advice of my friend Lars Bull. There weren’t any C# implementations at the time, so I wound up porting some professor’s Java implementation over for my purposes.
Over the years, Keith LaMothe (Arcen’s other programmer) and I have made a variety of improvements to it. We also had to re-implement a lot of trigonometry functions and things like square root, but that’s okay because performance stinks on those anyway in general. So we took a middle-ground between performance and precision.
Our versions give 100% reliable results, but they only give a certain number of significant digits – which is perfect for fixed-int math anyhow, because that inherently has a digit limit of (in our case) three places after the decimal.
Anyway, we haven’t really touched that code for years; we squeezed all the performance we could out of it long ago, and so we’ve been focused on multithreading, algorithm optimization, and a variety of other things.
Turns out that now things are SO efficient that some of the conversions and implicit-operators that we created for FInt (our fixed-int class) are now actually the bigger enemies again. There’s always a bottleneck somewhere, and these still aren’t the biggest one, but I managed to shave 2ms per frame off of a 12ms process just by working on the fixed-int math and then also a new random number generator, too.
That’s very worth it! The only reason it was that high is that we’re talking about a lot of math calls in these particular frames: tens or hundreds of thousands, depending on what is happening.
Regarding random number generation, there’s always a war there between accuracy (how random is it, really) and speed. I’ve never been all that happy with System.Random in .NET, and in Mono the performance is even worse. Though benchmarks suggest that the Unity 3D version of it is actually more performant than either the basic .NET or Mono versions. So… way to go, guys!
Still – we’ve been using Mersenne Twister (algorithm by Takuji Nishimura, with some credit to Topher Cooper and Marc Rieffel, and with a C# implementation by Akihilo Kramot) since around 2009, and that’s both slightly faster as well as a lot more random. In the intervening years we made a few small tweaks to make it run even faster, but it’s incredibly minor and mostly doesn’t help much in the grand scheme. Still, every little bit, right?
The problem is, sometimes you need quality randomness, and sometimes you need ultrafast randomness. There are certain things (like delays on special effects appearing, or shots emitting) that really don’t need all that much quality. We’re talking about a delay that is on the order of a hundred or thousand ms that we’re calculating randomly, and there’s just only so much randomness that you can see there. It’s not like AI decisions, which need to be quality.
So today I ported in a version of Xorshift (discovered by George Marsaglia) based on an implementation by Colin Green. I implemented that as an alternative for places where we want superspeed and don’t care if we’re getting super-duper high quality randomness as an output.
Well – it delivers! As noted, between that and the FInt shifts that was 2ms off a 12ms process, which is huge in terms of percentages.
