#AltDevBlog

I promised in my last post to show an example of the importance of knowing how much precision a float has at a particular value. Here goes.

As a general rule this type of data that should never be stored in a float:

Elapsed game time should never be stored in a float. Use a double instead. I’ll explain why below.

As an extra bonus, because switching to double is not always the best solution, this post demonstrates the dangers of unstable algorithms, and how to use the guarantees of floating-point math to improve them.

How long has this been going on?

A lot of games have some sort of GetTime() function that returns how long the game has been running. Often these return a floating-point number because it allows for convenient use of seconds as the units, while allowing sub-second precision.

GetTime() is typically implemented with some sort of high frequency timer such as QueryPerformanceCounter. This allows time resolution of a microsecond or better. However it’s worth looking at what happens to this resolution if the time is returned as a float, or stored in a float. We can do that using one of the TestFloatPrecision functions from the last post – just call them from the watch window of the debugger. In the screen shot below I tested the precision available at one minute, one hour, one day, and one week:

It’s important to understand what this data means. The number ‘60’, like all integers up to 16777216, can be exactly represented in a float. The watch window shows that the next value after 60 that can be represented by a float is about 60.0000038. Therefore, if we use a float to store “60 seconds” then the next time that we can represent is 3.8 microseconds past 60 seconds. If we try to store a value in-between then it will be rounded up or down.

How long did it take?

One of the most common things to do with time values is to subtract them. For instance, we might have code like this:

double GetTime();
 
   
 
  float TimeSomethingBadly()
 
  {
 
      float fStart = GetTime();
 
      DoSomething();
 
      float elapsed = GetTime() - fStart;
 
      return elapsed;
 
  }

The implication of the precision calculations above is that if ‘fStart’ is around 60, then ‘elapsed’ will be a multiple of 3.8 microseconds (two to the negative eighteenth seconds). That is the most precision you can get. If less than 3.8 microseconds has elapsed then ‘elapsed’ will either be rounded down to zero, or rounded up to 3.8 microseconds.

Therefore, if our game timer starts at zero and we store time in a float then after a minute the best precision we can get from our timer is 3.8 microseconds. After our game has been running for an hour our best precision drops to 0.24 milliseconds. After our game has been running for a day our precision drops to 7.8 milliseconds, and after a week our precision drops to 62.5 milliseconds.

This is why storing time in a float is dangerous. If you use float-time to try calculating your frame rate after running for a day then the only answers above 30 fps that are possible are infinity, 128, 64, 42.6, or 32 (since the possible frame lengths are 0, 7.8, 15.6, 23.4, or 31.2 milliseconds). And it only gets worse if you run longer.

As another example consider this code:

double GetTime();
 
   
 
  void ThinkBadly()
 
  {
 
      float startTime = (float)GetTime();
 
      // Do AI stuff here
 
      float elapsedTime = GetTime() - startTime;
 
      assert(elapsedTime < 0.005); // 
 
  }

The purpose of this code is to warn the developers whenever the AI code takes inordinately long. However when the game has been running for a day (actually the problem reaches this level after 65,536 seconds) GetTime() will always be returning a multiple of 0.0078 s, and ‘elapsedTime’ will always be a multiple of that duration. In most cases ‘elapsedTime’ will be equal to zero, but every now and then, no matter how fast the AI code executes, the time will tick over to the next representation during the AI calculations and ‘elapsedTime’ will be 0.0078 s instead of zero. The assert will then trigger even though the AI code is actually still under budget.

It’s a catastrophe for base-ten also

The general term for what is happening with these time calculations is catastrophic cancellation. In all of these examples above there are two time values that are accurate to about seven digits. However they are so close to each other that when they are subtracted the result has, in the worst case, zero significant digits.

We can see the same thing happening with decimal numbers. A float has roughly seven decimal digits of precision so the decimal equivalent would be getting a time value of 60.00000 and having the next possible time value be 60.00001. Given a seven-digit decimal float we can’t get more than a tenth of a microsecond precision when dealing with time around 60 seconds. When we subtract 60.00000 from 60.00001 then six of the seven digits cancel out and we end up with just one accurate digit. For times less than a tenth of a microsecond we have a complete catastrophe – all seven digits cancel out and we get zero digits of precision, just like with a binary float.

Double down

The solution to all of this is simple. GetTime() must return a double, and its result must always be stored in a double. The cancellation still occurs, but it is no longer catastrophic. A double has enough bits in the mantissa that even if your game runs for several millennia your double-precision timers will still have sub-microsecond precision. You can verify this by using the double-precision variation of TestFloatPrecisionAwayFromZero():

union Double_t
 
  {
 
      int64_t i;
 
      double f;
 
      struct
 
      {
 
          uint64_t mantissa : 52;
 
          uint64_t exponent : 11;
 
          uint64_t sign : 1;
 
      } parts;
 
  };
 
   
 
  double TestDoublePrecisionAwayFromZero(double input)
 
  {
 
      union Double_t num;
 
      num.f = input;
 
      // Incrementing infinity or a NaN would be bad!
 
      assert(num.parts.exponent < 2047);
 
      // Increment the integer representation of our value
 
      num.i += 1;
 
      // Subtract the initial value find our precision
 
      double delta = num.f - input;
 
      return delta;
 
  }

You can see in the screenshot below that if you store time in doubles then after your game has been running for a week you will have sub-nanosecond precision, and after three millennia you will still have sub-millisecond precision.

Clearly a double is overkill for storing time, but since a float is underkill a double is the right choice.

Aside: my initial calculation of the precision remaining after three millennia was wrong because the calculation of the number of seconds was done with integer math, and it overflowed and gave a completely worthless answer. Which proves that integer math can be just as tricky as floating-point math.

Changing your units doesn’t help

All along I am assuming that you are storing your time in seconds. However your choice of units doesn’t significantly affect the results. If you decide that your time units are milliseconds, or days, then the precision available after your game has been running for a day will be about the same. It is the ratio between the elapsed time and the time being measured that matters.

Or use integers

Tom Forsyth OffendOMatic rule for all who use doubles, I still prefer doubles for game time because of the combination of convenient units (seconds) and more than sufficient precision.

While Tom and I appear to disagree over whether you should use double in situations like this, we agree that ‘float’ won’t work.

Note that while GetTickCount() and GetTickCount64() are millisecond precision they are often actually less accurate than you would expect. Unless you have changed the Windows timer frequency with timeBeginPeriod() the GetTickCount functions will only return a new value every 10-20 milliseconds (insert pithy comment about precision versus accuracy here).

Time deltas fit in a float

It is important to understand that the limited precision of a float is only a problem if you do an unstable calculation, such as catastrophic cancellation cancelling out most of the digits. The code below, on the other hand, is fine:

double GetTime();
 
   
 
  float TimeSomethingWell()
 
  {
 
      double dStart = GetTime(); // Store time in a double
 
      DoSomething();
 
      float elapsed = GetTime() - dStart; // Store *result* in a float
 
      return elapsed;
 
  }

In TimeSomethingWell() we store the result of the subtraction in a float – after the catastrophic cancellation. Therefore our elapsed time value will have tons of precision.

Similarly, if you are using floats in your animation system to represent short times, such as the location of key-frames in a 60 second animation, then floats are fine. However when you add these to the current time you need to store the result of the addition in a double.

Tables!

Forrest Smith made a pretty table showing how the precision of a float changes as the magnitude increases, and I mangled it to suit my needs. Here it is for time:

And here is the table showing how the precision of a float diminishes when you use it to measure large distances, with meters being the units in this case:

Stable algorithms also matter

Some time ago I investigated some asserts in a particle animation system. Values were going out of range after less than an hour of gameplay and I traced this back to an out-of-range ‘t’ value being passed to the Lerp function, which expected it to always be from 0.0 to 1.0. Clamping was one obvious solution but I first investigated why ’t’ was going out of range.

One problem with the code was that the three parameters were all floats, so over long periods of time it would inevitably have insufficient precision. However we were getting instability much earlier than expected and it felt like switching to double immediately might just mask an underlying problem.

The parameters to the function, all time values in seconds, corresponded to the end of an animation segment, the length of that segment, and the current time, which was always between the start of the segment (segmentEnd-segmentLength) and ‘segmentEnd’. Because the start time of the segment was not passed in this code calculated it, and then did a straightforward calculation to get ‘t’:

float CalcTBad(float segmentEnd, float segmentLength, float time)
 
  {
 
      float segmentStart = segmentEnd - segmentLength;
 
      float t = (time - segmentStart) / segmentLength;
 
      return t;
 
  }

Straightforward, but unstable. Because ‘segmentLength’ is presumed to be quite small compared to ‘segmentEnd’, there is some rounding during the first subtraction and the difference between ‘segmentStart’ and ‘segmentEnd’ will be a bit larger or smaller than ‘segmentLength’. The resulting difference will always be a multiple of the current precision, so it will degrade over time, but even very early in the game the result will not be perfect. Because the value for ‘segmentStart’ is slightly wrong the value of “time – segmentStart” will be slightly wrong, and occasionally ‘t’ will be outside of the 0.0 to 1.0 range.

This will happen even if you use doubles. The errors will be smaller, but ‘t’ can still go slightly outside the 0.0 to 1.0 range. As the game goes on ‘t’ will range farther outside of the correct range, but from just a few minutes into the game the results will show signs of instability.

The natural tendency is to say “floating-point math is flaky, clamp the results and move on”, but we can do better, as shown here:

float CalcTGood(float segmentEnd, float segmentLength, float time)
 
  {
 
      float howLongAgo = segmentEnd - time;
 
      float t = (segmentLength - howLongAgo) / segmentLength;
 
      return t;
 
  }

Mathematically this calculation is identical to CalcTBad, but from a stability point of view it is greatly improved.

If we assume that ‘time’ and ‘segmentEnd’ are large compared to ‘segmentLength’, then we can reasonably assume that ‘segmentEnd’ is less than twice as large as time. And, it turns out that if two floats are that close then their difference will fit exactly into a float. Always. So the calculation of ‘howLongAgo’ is exact. Ponder that for a moment – given a few reasonable assumptions we have exact results for one of our floating-point math operations.

With ‘howLongAgo’ being exact, if ‘time’ is within its prescribed range then ‘howLongAgo’ will be between zero and ‘segmentLength’, and so will ‘segmentLength’ minus ‘howLongAgo’. IEEE floating-point math guarantees correct rounding so when we divide by ‘segmentLength’ we are guaranteed that ‘t’ will be from 0.0 to 1.0. No clamping needed, even with floats.

This real example demonstrates a few things:

• Any time you add or subtract floats of widely varying magnitudes you need to watch for loss of precision
• Sometimes using ‘double’ instead of ‘float’ is the correct solution, but often a more stable algorithm is more important
• CalcT should probably use double (to give sufficient precision after many hours of gameplay)

Your compiler is trying to tell you something…

With Visual C++ on the default warning level you will get warning C4244 when you assign a double to a float:

warning C4244: ‘initializing’ : conversion from ‘double’ to ‘float’, possible loss of data

Possible loss of data is not necessarily a problem, but it can be. Suppressing warnings, with #pragma warning or with a cast, is something that should be done thoughtfully, after understanding the issue. Otherwise the compiler might say “I told you so” when your game fails after a twenty-four hour soak test.

Does it matter?

For some game types this problem may be irrelevant. Many games finish in less than an hour and a float that holds 3,600 (seconds) still has sub-millisecond accuracy, which is enough for most purposes. This means that for those game types you should be fine storing time in a float, as long as you reset the zero-point of GetTime() at the beginning of each game, and as long as the clock stops running when the game is paused.

For other game types – probably the majority of games – you need to do your time calculations using a double or uint64_t. I’ve seen problems on multiple games who failed to follow this rule. The problems are particularly tedious to track down and fix because they may take many hours to show up.

Store your time values in a double, and then you don’t need to worry, at least not as much, as long as you avoid unstable algorithms.

Next time…

On the next post I think it might finally be time to start jumping into the delicate subject of how to compare floating-point numbers, with the many subtleties involved. Previous articles in this series, and other posts, can be found here.