Inaccurate FPS capping + two solutions to fix it

[JasonS05]

First of all, I want to acknowledge that this is an extremely minor issue, but at the same time the code change(s) to fix it are also fairly trivial, so I think it's worthwhile to bring up. So, the issue is that when the FPS cap is set to 60, it runs at something like 57.5 FPS, and for other FPS caps it similarly runs just a tiny bit slower. The reason for that is because the way the FPS cap is implemented. The current implementation is as follows (in pseudocode):

loop {
	int frameStart = GetMilliseconds()
	
	// do work
	
	int now = GetMilliseconds()
	int frameDuration = now - frameStart
	float targetDuration = 1000.0 / maxFPS
	SleepMilliseconds(floor(targetDuration - frameDuration + 0.5))
}

This has two issues. The first and more obvious one is rounding error. Every time it tries to sleep for 10.49 milliseconds, it'll always call SleepMilliseconds(10), and every time it tries to sleep for 10.51 milliseconds, it'll always call SleepMilliseconds(11). If, on average, it rounds down more than up (or vice-versa), the rounding error will accumulate and the net FPS will consequently be affected. The other, less obvious, issue is that SleepMilliseconds (void SDL_Delay(Uint32)) doesn't actually sleep for the specified amount of time. Instead, it sleeps for at least the specified amount of time, and possibly longer. For example, if the OS scheduler uses a 400 Hz timer, then SleepMilliseconds could overshoot by up to 2.5 milliseconds, and on average 1.25 milliseconds. This most likely contributes to the observed FPS sag much more than the rounding error. To fix this, I propose two solutions. The first one is simpler, but I personally prefer the second one. The pseudocode for the first one is as follows:

int frameStart = GetMilliseconds()

loop {
	// do work
	
	int now = GetMilliseconds()
	int frameDuration = now - frameStart
	float targetDuration = 1000.0 / maxFPS
	int sleepTime = floor(targetDuration - frameDuration + Random())
	frameStart = now + max(sleepTime, 0.0)
	SleepMilliseconds(sleepTime)
}

This employs two changes. The first is the change of + 0.5 to + Random(), where Random() returns a random number in the range 0.0 to 1.0 which removes the possibility of rounding error accumulation. The second change is to set the start time of the next frame before we sleep, calculating where it should start at, so if the sleep function overshoots then that overshoot gets registered as part of the time taken during the next frame, not before it. This will affix the average FPS to exactly maxFPS, but there will still be statistical noise from the random rounding. To fix this, I propose the second solution.

The second solution divides time into blocks the duration of an ideal frame, and tries to sync up to the beginning of the next block. In order to prevent frames that take slightly longer than targetDuration from suddenly dropping the FPS to half of maxFPS, I decide the next time block to sleep for to be the time block after the time block the frame started at, not the current time block. This also has the beneficial effect of making it play "catch-up" if one frame spuriously takes extra long and ends up longer than targetDuration but shorter than targetDuration * 2.0, so even with the spuriously slow frame it will still complete maxFPS frames in that second. The pseudocode is as follows:

int frameStart = GetMilliseconds()

loop {
	// do work
	
	int now = GetMilliseconds()
	float timeBlockDuration = 1000.0 / maxFPS
	int frameStartTimeBlock = floor(frameStart / timeBlockDuration)
	int currentTimeBlock = floor(now / timeBlockDuration)
	int nextTimeBlock = frameStartTimeBlock + 1
	frameStart = max(now, ceil(nextTimeBlock * timeBlockDuration))
	SleepMilliseconds(frameStart - now)
}

Note:

• floor(x) is the mathematical floor function, i.e. rounding down
• ceil(x) is the mathematical ceiling function, i.e. rounding up
• max(x, y) returns x if it is greater than y, and otherwise returns y

[LBPHacker]

Does this look good? 2cb6b96

[JasonS05]

Does this look good? 2cb6b96

Looks right, except for two mistakes I noticed. On line 515 you put frameStart = std::max(frameStart, ...); but it needs to be frameStart = std::max(now, ...);, and on line 520 you forgot a * 0.95 in the computation of correctedFrameTimeAverage.

The first error means that if you do something laggy and drop to 10 FPS for a while, then clear the current save it’ll shoot up to 300 FPS or whatever according to your computer’s capabilities until it’s caught up on all the missing frames and then it’ll drop to 60 FPS again. By maxing with now instead of frameStart you keep it from holding a backlog of more than 1 frame.

The second error means that even if the FPS is stable and correct, it’ll display a completely incorrect FPS estimate that never rises, only falls, and keeps falling indefinitely, approaching zero.

Also, I like the change to use nanoseconds instead of milliseconds. Makes things a little nicer than dealing with casts/rounding between float and int.

[JasonS05]

Oh gosh, I accidentally hit the “close” button. Oops! Reopening now.

[LBPHacker]

Neither of your observations is correct. frameStart is equal to now by the time the max-ing takes place, and the 0.95 is not needed because I converted the b * f - a * (1 - f)-type b * f + a * (1 - f)-type expression to a a + (b - a) * f-type one.

[LBPHacker]

Might be a good idea to explain that with comments.

[JasonS05]

Oh, good point! In that case, both issues I mentioned are resolved, but if I’m not still misunderstanding things, then that raises a different issue. The computation of frameStartTimeBlock relies on frameStart equaling the time the frame started at, not now. Computing frameStartTimeBlock with now means that if every frame takes about 20 ms, which should result in 50 or so FPS, it’ll actually drop to exactly 30 FPS.

[LBPHacker]

That is correct. I shot myself in the foot by reshuffling code to make way for the fpsLimit <= 2 (no limit) case. Will fix in a bit.

[LBPHacker]

That said, somehow, it caps to 60, not 30.

[JasonS05]

That said, somehow, it caps to 60, not 30.

It’ll only cap to 30 if frames don’t fit in the 16 millisecond window. If they do fit, it’ll cap to 60 instead.

[JasonS05]

Just changing line 513 to use oldFrameStart instead of frameStart should do the trick, I believe.

[LBPHacker]

Yeah that's what I'm doing, among other things.

[LBPHacker]

Okay yeah I won't overcomplicate it. master...LBPHacker:The-Powder-Toy:better-fps-cap

[LBPHacker]

I guess I should add that we don't care nearly as much about the "draw cap" (RPS cap? no idea) as the FPS cap. It's fine for it to be imprecise, it's only meant to give an FPS boost when you really need it.

[JasonS05]

yeah the draw cap's not so important. Still, it looks like it should work correctly. Since this appears to be done (unless playtesting proves otherwise, I guess), I'm closing this now.

[LBPHacker]

Yeah github's issue-closing mechanics are not exactly intuitive.

[LBPHacker]

Fixed by c6d6a7d.