Time slice vs. critical events

The most common way to simulate something is to build a representation of the system being simulated, update the entire representation, and repeat. For example, in a gravity simulation the positions and velocities of objects at t_n (time n) can be used to figure out their positions and velocities at t_n+1. This is called the time slice strategy. The size of a time slice is often constant, but more advanced simulations may vary the size of the time slice. For example, gravity simulations sometimes use narrower time slices when two objects are making a close approach, because the standard algorithm applies the high close approach acceleration to the objects for an entire time slice, when in reality the two objects would only have been that close for a very short time. Game programmers often vary the time slices in their simulation of the game world to match the frame rate of the display.

Taking this further, some simulations don't need to know anything at all about the situation between certain times, because the situation at any point between those times is trivial to calculate. The classic example of this is a queue for service in front of a bank teller. If you want to simulate the length of the queue, all you need to know are the times at which customers join the queue, and the times at which the teller finishes serving a customer. Between those times, the length of the queue doesn't change (which is certainly trivial to calculate). This is called the critical event strategy.

In fact, to simulate the queue, you only need 4 variables: the length of the queue, the current time, the time until the next customer arrival, and the time until the next customer departure (Q, C, TA, and TD, respectively). Suppose TA < TD (a customer will arrive before one leaves):

C += TA
TD -= TA
Q += 1
TA = -A*ln(1 - rand())

That last line deserves some explanation. The time between arrivals usually follows an exponential distribution, and -A*ln(1 - rand()) will generate a number from an exponential distribution with average value A.

This system saves you a lot of computing time. Unfortunately, beginning programmers sometimes use the constant time slice method for everything. In this case, the novice might repeatedly do the following:

C += 1
TA -= 1
TD -= 1
if TA <= 0 then
    Q += 1
    TA = -A*ln(1 - rand())

This is a bad idea. In one case, on a school assignment, I saw a student use this method to run a simulation of operating system file access so slowly that it took 20min because the loop went through so many iterations where nothing happened, while a critical event version took negligible time to generate the same results, and allowed fractional times on the clock too.

You can't use the critical event strategy to simulate everything, of course (gravity being the canonical counter-example). But when you can, it really speeds things up.