Investigation of optimal sleep time calculation in game loop

Question

When programming animations and little games I've come to know the incredible importance of Thread.sleep(n); I rely on this method to tell the operating system when my application won't need any CPU, and using this making my program progress in a predictable speed.

My problem is that the JRE uses different methods of implementation of this functionality on different operating systems. On UNIX-based (or influenced) OS:es such as Ubuntu and OS X, the underlying JRE implementation uses a well-functioning and precise system for distributing CPU-time to different applications, and so making my 2D game smooth and lag-free. However, on Windows 7 and older Microsoft systems, the CPU-time distribution seems to work differently, and you usually get back your CPU-time after the given amount of sleep, varying with about 1-2 ms from target sleep. However, you get occasional bursts of extra 10-20 ms of sleep time. This causes my game to lag once every few seconds when this happens. I've noticed this problem exists on most Java games I've tried on Windows, Minecraft being a noticeable example.

Now, I've been looking around on the Internet to find a solution to this problem. I've seen a lot of people using only Thread.yield(); instead of Thread.sleep(n);, which works flawlessly at the cost of the currently used CPU core getting full load, no matter how much CPU your game actually needs. This is not ideal for playing your game on laptops or high energy consumption workstations, and it's an unnecessary trade-off on Macs and Linux systems.

Looking around further I found a commonly used method of correcting sleep time inconsistencies called "spin-sleep", where you only order sleep for 1 ms at a time and check for consistency using the System.nanoTime(); method, which is very accurate even on Microsoft systems. This helps for the normal 1-2 ms of sleep inconsistency, but it won't help against the occasional bursts of +10-20 ms of sleep inconsistency, since this often results in more time spent than one cycle of my loop should take all together.

After tons of looking I found this cryptic article of Andy Malakov, which was very helpful in improving my loop: http://andy-malakov.blogspot.com/2010/06/alternative-to-threadsleep.html

Based on his article I wrote this sleep method:

// Variables for calculating optimal sleep time. In nanoseconds (1s = 10^-9ms).
private long timeBefore = 0L;
private long timeSleepEnd, timeLeft;

// The estimated game update rate.
private double timeUpdateRate;

// The time one game loop cycle should take in order to reach the max FPS.
private long timeLoop;

private void sleep() throws InterruptedException {

    // Skip first game loop cycle.
    if (timeBefore != 0L) {

        // Calculate optimal game loop sleep time.
        timeLeft = timeLoop - (System.nanoTime() - timeBefore);

        // If all necessary calculations took LESS time than given by the sleepTimeBuffer. Max update rate was reached.
        if (timeLeft > 0 && isUpdateRateLimited) {

            // Determine when to stop sleeping.
            timeSleepEnd = System.nanoTime() + timeLeft;

            // Sleep, yield or keep the thread busy until there is not time left to sleep.
            do {
                if (timeLeft > SLEEP_PRECISION) {
                    Thread.sleep(1); // Sleep for approximately 1 millisecond.
                }
                else if (timeLeft > SPIN_YIELD_PRECISION) {
                    Thread.yield(); // Yield the thread.
                }
                if (Thread.interrupted()) {
                    throw new InterruptedException();
            }
                timeLeft = timeSleepEnd - System.nanoTime();
            }
            while (timeLeft > 0);
        }
        // Save the calculated update rate.
        timeUpdateRate =  1000000000D / (double) (System.nanoTime() - timeBefore);
    }
    // Starting point for time measurement.
    timeBefore = System.nanoTime();
}

SLEEP_PRECISION I usually put to about 2 ms, and SPIN_YIELD_PRECISION to about 10 000 ns for best performance on my Windows 7 machine.

After tons of hard work, this is the absolute best I can come up with. So, since I still care about improving the accuracy of this sleep method, and I'm still not satisfied with the performance, I would like to appeal to all of you java game hackers and animators out there for suggestions on a better solution for the Windows platform. Could I use a platform-specific way on Windows to make it better? I don't care about having a little platform specific code in my applications, as long as the majority of the code is OS independent.

I would also like to know if there is anyone who knows about Microsoft and Oracle working out a better implementation of the Thread.sleep(n); method, or what's Oracle's future plans are on improving their environment as the basis of applications requiring high timing accuracy, such as music software and games?

Thank you all for reading my lengthy question/article. I hope some people might find my research helpful!

Answer 1

You could use a cyclic timer associated with a mutex. This is IHMO the most efficient way of doing what you want. But then you should think about skipping frames in case the computer lags (You can do it with another nonblocking mutex in the timer code.)

Edit: Some pseudo-code to clarify

Timer code:

While(true):
  if acquireIfPossible(mutexSkipRender):
    release(mutexSkipRender)
    release(mutexRender)

Sleep code:

acquire(mutexSkipRender)
acquire(mutexRender)
release(mutexSkipRender)

Starting values:

mutexSkipRender = 1
mutexRender = 0

Edit: corrected initialization values.

The following code work pretty well on windows (loops at exactly 50fps with a precision to the millisecond)

import java.util.Date;
import java.util.Timer;
import java.util.TimerTask;
import java.util.concurrent.Semaphore;


public class Main {
    public static void main(String[] args) throws InterruptedException {
        final Semaphore mutexRefresh = new Semaphore(0);
        final Semaphore mutexRefreshing = new Semaphore(1);
        int refresh = 0;

        Timer timRefresh = new Timer();
        timRefresh.scheduleAtFixedRate(new TimerTask() {
            @Override
            public void run() {
                if(mutexRefreshing.tryAcquire()) {
                    mutexRefreshing.release();
                    mutexRefresh.release();
                }
            }
        }, 0, 1000/50);

        // The timer is started and configured for 50fps
        Date startDate = new Date();
        while(true) { // Refreshing loop
            mutexRefresh.acquire();
            mutexRefreshing.acquire();

            // Refresh 
            refresh += 1;

            if(refresh % 50 == 0) {
                Date endDate = new Date();
                System.out.println(String.valueOf(50.0*1000/(endDate.getTime() - startDate.getTime())) + " fps.");
                startDate = new Date();
            }

            mutexRefreshing.release();
        }
    }
}