26. Yet more building a simulation

Where Are We?

In the last lecture, we fleshed out the stub of a road, where the simulation of the activity on the road involved vehicle entry to the road and exit from the road:

        void entryEvent( float t ) {
                // A vehicle arrives at the road entrance at time t
                Simulator.schedule(
                        t+travelTime,
                        (float time)->Road.this.exitEvent( time )
                );
        }

void exitEvent( float t ) {
        // A vehicle arrives at the road exit at time t
        // Bug:  What happens next?
        // if the intersection is open, the vehicle goes on
        // if the intersection is blocked (stoplight?) the vehicle wait
}

The problem we face in fleshing out the details of how a vehicle exits a road is that the details depend on whether the intersection at the end of the road permits vehicle entry.

At the very least, the road might lead to a stop light that is red at the time the vehicle reaches the end. In that case, the vehicle must wait until the light changes. In a more general simulation model, we could add additional behaviors: For example, we could model intersections where it takes a finite nonzero time for a car to pass through the intersection, and where we forbid two cars in the intersection at the same time. In that case, if a car arrives at an intersection that is currently occupied, it must wait (perhaps briefly) for the intersection to clear.

For now, we won't do anything with these details, but we will, at the very least, simulate the behavior of stoplights.

The Stoplight as a Process

Just as source intersections are processes that periodically generate vehicles, stoplights are processes that periodically allow traffic to flow through an intersection from one road or another. If we ignore the possibility of traffic sensors that control the stoplight, and if we ignore the the possibility that the stoplight might give longer green lights to one road than another, the process for each stoplight is quite simple: The stoplight initializer schedule the first light-change event, and each light-change event schedule the next.

class StopLight extends Intersection {
        float interval = 99.99f; // how long the light stays green in each dir
        int direction = 0;       // the direction that is currently green

        // initializer
        public StopLight( Scanner sc, String name ) throws IllegalName {
                
                ...  // previous code of the initializer

                interval = ScanSupport.scanFloat(
                        sc,
                        () -> StopLight.this.toString()
                )
                direction = 0;

                ScanSupport.lineEnd( ... );

If stop lights have behavior, we need to add variables to the light to support this. Each light could have a different timing, so we add this, and we add a variable to describe which direction the green light currently points.

The code given above extends the simulation language by making the stop light interval a parameter that is set by the model. We could, of course, make the initial light direction a parameter as well. Here is the specification of a stoplight that stays green in each direciton for 2.5 time units:

intersection X stoplight 2.5

Given this, the basic process at each stoplight can be coded something like this:

class StopLight extends Intersection {
        float interval = 99.99f; // how long the light stays green in each dir
        int direction = 0;       // the direciton that is currently green

        // initializer
        public StopLight( Scanner sc, String name ) throws IllegalName {

                ... // previously discussed code

                // start this stoplight cycling through its incoming roads
                Simulator.schedule(
                        0.0f,
                        (float time)->Source.this.lightChanges( time )
                );
        }

        // simulation methods

        /** Process cycling through incoming roads at this stoplight
         */
        private void lightChanges( float t ) {
                direction = direction + 1;
                if (direction >= incoming.size()) direction = 0;
                // Bug:  incoming.size() is expensive and constant for each

                Simulator.schedule(
                        t + interval,
                        (float time)->Source.this.lightChanges( time )
                );
        }

Efficiency Questions

Note above the use of the following code framework to update the direction:

                direction = direction + 1;
                if (direction >= incoming.size()) direction = 0;

We could just as easily have written this:

                direction = (direction + 1) % incoming.size();

Why pick one or the other of these? The first one is long winded, but it uses intellectually trivial code, just assignment, increment and comparison. Any beginning programmer understands these.

The second is considerably shorter, using just the % operator instead of an if statement. The problem is, this operator that is understood by a smaller fraction of the population. In fact, one way to divide computer scientists from mere "coders" is that a computer scientist should understand the mod operator.

But run-time efficiency also matters. The mod operator is typically computed by division, although if the dividend is a constant power of two, faster operations can be used. Division, on a typical CPU, is 10 to 20 times slower than simple operations such as addition and comparison. The net result is that the version of the code with the if statement is typically significantly faster than the version of the code using division.

There is a second issue hiding here: The call to incoming.size(). For linked lists, the typical code to compute the size iterates down the list counting list elements. This can be painfully slow. The official Java documentation for class LinkedList does not indicate whether the linked list implementation keeps a running count of the number of list items. but even if it does, it would likely be faster for each stoplight to keep a field that counts the incoming roads. This count is a constant once the simulation begins because roads are not dynamically created and destroyed. We've dealt with this issue with a bug notice above.

But the big problem we uncovered in writing this code lies in the reference to the incoming field of the intersection. A quick inspection of the code shows that neither incoming nor outgoint are initialized. We defined these fields but we never initialized them! So, we have added this bug notice in class Intersection:

        private LinkedList  outgoing = new LinkedList  ();
        private LinkedList  incoming = new LinkedList  ();
        // stop lights need to know incoming to release waiting cars
        // Bug:  Incoming and outgoing are never updated!