A New Timer Algorithm

Shared Code
#1

(This was also posted on forums.java.sun.com)

Since the beginning of time, people have been trying to come up with a timer in pure Java. The problem has been that System.currentTimeMillis() is not accurate across systems. On Windows 2000 for example, it’s 10 ms. Of course, 10ms is still enough to time up to 100 frames per second. The problem of course, is that you never know where you are in that 10 ms resulting in inconsistant drawing rates of 22 ms, 18 ms, 27 mx, etc. This makes the animation appear to “jump” around on the screen. This has meant that System.currentTimeMillis() has been useless for timing framerates. That is, until now.

As I was thinking about the problem, I realized that there’s no need to increase the resolution, just sync based on the resolution. Older DOS based games used to latch onto every other screen refresh for timing. Serial ports wait for the control signal to change. These methods weren’t to make something faster, they were to synchronize timing. Then I realized, what I really needed was to latch onto the leading edge of the digital wave that the timer produced. i.e. If I always waited until exactly after the timer was updated, I should have exactly the resolution of the timer until the next tick.

Well, the idea was great in theory. In practice, it was about as successful as mixing coordinate systems. You see, this method would allow me to write code that would hit 50 fps right on the dot (no small acheivement for such a low-res timer). It seems that should work great, right? Wrong. The problem was that the VSync was running at 60Hz. This gave me a remainder (10 fps) that couldn’t be evenly split between frames. Had I chosen 30 fps, I would have better success due to the nice even split (2 VSyncs per frame). The problem (again) is that the resolution of the Windows 2000 timer (10ms) doesn’t leave much room for distribution of the extra timing (100/30 = 10/3 = 3.333333).

The best solution for this I’ve managed to produce is to seperate the timing of the frame from the logic. If the logic runs on it’s own timer, it should appear to be smooth since every frame of drawing is being taken advantage of. And indeed, this does appear to be much smoother. However, there is still a slight jerkiness visible. In a real game this would probably disappear, but it’s always best to try for perfection.

The entire package with source, javadocs, a JAR lib and an example file is available here:

http://java.dnsalias.com/timer/timer-1.0.zip

Let me know what you think. Enjoy!

#2

My display is running at 85Hz. Is 60Hz really the standard for everyone else or have people blurred the baseline in to a universal constant?

Anyway, sounds like a good implementation.

#3

It’s not so much a standard but a least common denominator… for instance, my laptop’s LCD display cannot refresh at anything BUT 60Hz… (60hz on CRTs gives me a headache in minutes, but this doesnt)

Some people have monitors that refresh >100Hz. EVERYONE can do 60hz…

#4

[quote]Some people have monitors that refresh >100Hz. EVERYONE can do 60hz…
[/quote]
Most people I’ll give you, everyone I disagree with! :wink: I’ve still got one machine in my house that I think is sub-60Hz.

#5

[quote]I’ve still got one machine in my house that I think is sub-60Hz.
[/quote]
Really??? :o
Let’s make it ‘everyone except cfmdobbie’ then ;D

#6

Sure, works for me! ;D

#7

How is this different from TheLorax’s timer hack? Probably a question best filed under “stupid” but I’m not with it totally today.

#8

[quote]How is this different from TheLorax’s timer hack?
[/quote]
That depends on if you’ve got a link to TheLorax’s timer hack. (i.e. I haven’t heard of it before.) :slight_smile:

#9

Ok, I tracked TheLorax’s original post down. His code is designed to use Thread.sleep(1) as a timer (a practice that’s been going on for quite awhile now). The problem is that this is a hack and it’s only psuedo-effective. Since you’re relying on the Thread scheduler for a heartbeat and the thread scheduler does not guarantee a return, your one millisecond could be anything from 1.5 ms to 100 ms. TheLorax’s code mitigates this problem by occasionally resyncing with the (highly inacurrate) system clock.

The timer I created here works on completly different principles. It still uses System.currentTimeMillis(), but detects the resolution of the timer and uses this to do timeslicing. Basically, by synchronizing with the clock exactly, my code can guarantee that your code has X number of milliseconds until the next “beat” of the clock. It doesn’t completely solve the problem, but it helps bring the problem back into the Real-Time system domain where gaming lives. (By “real-time” I am referring to predictable behavior like that of Real-Time Operating Systems.)

The good news is that it works. The bad news is, not entirely. The problem is that the 60Hz signal of a monitor leaves 40 timer beats extra per second to do something with. In order to use this timer for game timing, the beats have to be evenly distributed (i.e. So that you have 2 beats per frame for example). 100/60 works out to 1.6 beats per frame. 100/30 works out to 3. 3 beats per frame. Eventually, these partial beats are going to accumulate and result in either a lost frame or an extra frame. When that happens, your animation is going to appear to “jump”.

Does that explain it better?

#10

Aha! Much better. Thank you.

#11

Quick update. The AdvancedTimer code has been merged into the GAGE project at http://java.dnsalias.com and now includes a hi-res timer for Windows. Check out the thread on GAGE in the Java2D directory.

#12

Has anyone else noticed that this timer class (as opposed to TheLorax’s one) causes your CPU usage to jump to 100%?

I did a pretty direct apples-to-apples replacement of SleepTimer with AdvancedTimer, and suddenly my CPU usage was off the scale (though, to be fair, my machine was still as responsive as usual, so maybe it’s doing something very low priority).

Possibly it’s because SleepTimer uses ‘Thread.sleep’ whereas this implementation uses ‘Thread.yield’ in a tight loop which might mean, if there’s no other thread to yield to (i.e. they’re all waiting on this timer!) that loop would just go nuts waiting for the clock to tick round?

Is this just me?

#13

Has anyone else noticed that this timer class (as opposed to TheLorax’s one) causes your CPU usage to jump to 100%?

Flames start pouring out all across the forum pages. Aiiee!!! Walk away slowly. Pretend you never made this statement. Forget the person named JBanes ever existed.

On another note, why do people work so hard just to avoid getting a good hi-res timer. Every system has one. Just write the freaking ten lines of code to get to it until Sun does. Sheez.

God bless,
-Toby Reyelts

#14

Kenrod,

You’ll forgive me for putting it this way, but it’s a feature, not a bug. :slight_smile: Using Thread.sleep() is a highly inaccurate way to sleep. For example, you need to sleep for about one millisecond, but Thread.sleep() may not return for 3 milliseconds. Using Thread.yield() allows the game to play nicely with other processes while getting the timing advantages of a hard loop. If any other processes need it, they can grab as many CPU cycles as they need.

That being said, this feature is not a requirement. The GAGETimer simply provides a resolution of 1ms or better. It makes use of the Window’s Hi-Res timer to produce a tick rate that’s in the range of a small fraction of a millisecond instead of the 10-50ms per tick that Windows normally produces. You can quite happily use this timer combined with Thread.sleep() to prevent your game from using 100% CPU. This may be desirable in situations where a high frame rate is unnecessary (i.e. A turn based strategy game.) Just be warned that you cannot properly frame-lock with Thread.sleep() under most gaming OSes.

#15

Using Thread.sleep() is a highly inaccurate way to sleep.

I constantly see this dichotomy between Thread.yield() and Thread.sleep() espoused, but I don’t know why. A call to Thread.sleep( 0 ) is going to have the same effect as a call to Thread.yield(). In fact, if you look at the source code for Sun’s JVM (for Win32), you’ll see that that is exactly what Thread.yield() does - call Sleep( 0 ).

So, Thread.yield() is no more inherently unsafe then Thread.sleep(). In both cases, you’re giving up the time slice for your thread and asking the thread scheduler to reschedule it. You can only hope that the thread scheduler isn’t so stupid as to not return to your thread in an equitable period of time.

As an aside, here’s some documentation for pthread_yield() that I thought you might find interesting JBanes:

Use this routine carefully and sparingly, because misuse can cause unnecessary context switching which will increase overhead and actually degrade performance.

God bless,
-Toby Reyelts

#16

[quote]Using Thread.sleep() is a highly inaccurate way to sleep.

I constantly see this dichotomy between Thread.yield() and Thread.sleep() espoused, but I don’t know why. A call to Thread.sleep( 0 ) is going to have the same effect as a call to Thread.yield(). In fact, if you look at the source code for Sun’s JVM (for Win32), you’ll see that that is exactly what Thread.yield() does - call Sleep( 0 ).

So, Thread.yield() is no more inherently unsafe then Thread.sleep(). In both cases, you’re giving up the time slice for your thread and asking the thread scheduler to reschedule it. You can only hope that the thread scheduler isn’t so stupid as to not return to your thread in an equitable period of time.

As an aside, here’s some documentation for pthread_yield() that I thought you might find interesting JBanes:

Use this routine carefully and sparingly, because misuse can cause unnecessary context switching which will increase overhead and actually degrade performance.
[/quote]
Sorry to weigh in here with a (probably) stupid question, but I’m going round the bend with a problem that only shows up on windows (XP mainly). Is this “inaccurate timer” the root cause of the godawful scheduling of threads on windows XP? It behaves as though XP has the butt-sucking, non-pre-emptive scheduler from windows 3.1 (which I well rememeber and hate to the end of time!).

I’m only using one thread of my own (for my game) and siphoning off mouseevents from the awt thread, via a mouselistener on a JComponent - but I do NO calculation in that siphoning off - and yet still if you move the mouse too much, my main only game thread gets zero processor time.

I’ve been scouring the JGO forums for anyone with similar problems, but having trouble finding anything. Sigh.