18. Miscellaney and Wasted Computation
Part of
CS:2820 Object Oriented Software Development Notes, Spring 2021
|
There's a problem with our class Error and RoadNetwork. As the code stands, you can write new Error(), at which point, Java will happily create a new object of class Error, despite the fact that this is a useless object. Similarly, you could write new RoadNetwork.
One way to prevent instantiation of a class that should never be instantiated is to add a private constructor that is never called. So, we could begin the class like this:
/**
* Error handling
*/
abstract class Error{
private Error(){}; // never call this!
Alternatively, we can declare the class to be abstract to prevent instantiation. It is still legal, however, to create (useless) subclasses of abstract classes. We can also define a class to be final to prevent anyone from ever creating a subclass of that class, but unfortunately, Java does not permit the combination of abstract and final. So we could write:
/**
* Error handling
* This would be tagged final to prevent any subclasses.
*/
abstract class Error{
private static int errorCount = 0;
private static final int maxErrors = 10;
public static void warn( String message ) {
System.err.println( message + "\n" );
errorCount = errorCount + 1;
if (errorCount > maxErrors) System.exit( 1 );
}
public static void fatal( String message ) {
warn( message );
System.exit( 1 );
}
}
In the above, we also made the error handler count the errors and limit the count to a reasonable value. We declared the limit on the error count to be a final int which makes it effectively constant.
Note that final does not make objects constant unless they are immutable. It finalizes the identity of the object referenced to a variable. Some objects are immutable. Class String is an example, because there are no methods to change the value of an object in that class, only methods that construct new objects to hold a new value. Class LinkedList is an example of a mutable class. A single list object may be manipulated in a wide variety of ways.
Now, let's return to class Intersection. We declared the name of an intersection to be final, like this:
abstract class Intersection {
public final String name; // textual name of intersection, never null!
We were forced to add a protected constructor to the class so that the constructors in the subclasses could initialize name. If a Final variable is not set on the line where it is declared, it must be set in the constructor for the class itself, not in any subclass.
It helps to understand the way subclasses are implemented. If class A has class B as a subclass, the actual implementation of an object of class B has all the fields of A followed by the fields of B. For example, consider this code:
class A {
int A1;
int A2 = 4;
}
class B extends A {
int B1;
int B2;
}
The objects actually created in memory for class B look like this:
class B {
int A1;
int A2 = 4;
int B1;
int B2;
}
If you pass an object of class B to a method that expects an object of class A, that method will work just fine. It expect an object with 2 fields, and never looks beyond those 2. The fact that the object you passed actually had 4 fields is irrelevant. The first 2 fields obey all the rules for objects of class A.
Now, when you call a constructor with, for example, new B(), what actually happens is, first, the compiler allocates a new uninitialized block of memory big enough to hold an object of class B. Then it executes all the in-line initializations from class A, and then all the in-line initializations from class B, and only then does it exeute the code for the explicit constructor that you called. Within a constructor for class B you have the option of calling any constructor of class A first, so long as you do this immediately at the start of the class B constructor.
This applies even to abstract classes! Constructors of an abstract class may not be used in the outside world, but they may be used in subclasses. As such, constructors in an abstract class should be declared to be protected. Note that constructors may also be declared to be private, in which case they may only be used within methods of the class.
In each subclass of Intersection, the constructor must begin with a call to the parent class's constructor. For example:
class Stoplight extends Intersection {
// fields unique to a Stoplight
...
Stoplight( String name ) {
super( name ); // call the superclass (Interesection) constructor
...
// finish constructing a Stoplight
}
It is legal to declare methods in an abstract class. We can do this two ways: First, we can declare abstract methods. These are commitments made in the abstract class forcing each concrete subclass to provide an implementation. When you declare an abstract method, you give just the heading, which includes the parameter list but not the method body. For example, every subclass of Stoplight must implement toString(), so we'd like to write this:
abstract class Intersection {
...
public abstract String toString();
}
This would force each subclass of interesection to define toString(). For example,
class Stoplight extends Intersection {
...
public String toString() {
return "Intersection " + name + " stoplight";
}
All of the different subclasses of Intersection would use very similar return statements in their toString methods, so it would be nice to provide a concrete toString method in the superclass so that we could write something like this:
class Stoplight extends Intersection {
...
public String toString() {
return super.toString() + " stoplight";
}
The problem is, we've already committed to an abstract method in the superclass. Furthermore, the signature of toString is strongly constrained, since we inherited it from class Object, the superclass of all classes. The definition of Object.toString() constrains the signature of all redefinitions of toString(). Because Object.toString() is public, we may not redefine it as private or protected. We must declare it to be public. If we want anything different, we'll have to rename it.
Look at the code we currently have to construct a new road:
public Road( MyScanner sc ) throws ConstructorFailure {
// keyword Road was already scanned
final String src; // where does it come from
final String dst; // where does it go
src = sc.getNext( "???", "road source missing" );
dst = sc.getNext( "???", "road " + src + " to missing destination" );
travelTime = sc.getNextFloat(
Float.NaN, "road " + src + " to missing destination"
);
if ((src == "???") || (dst == "???") || travelTime.isNaN()) {
// this takes care of the errors detected above
throw new ConstructorFailure();
}
destination = Intersection.lookup( dst );
if (destination == null) {
Error.warn( "road " + src + " " + dst + " undefined: " + dst );
throw new ConstructorFailure();
}
source = Intersection.lookup( src );
if (source == null) {
Error.warn( "road " + src + " " + dst + " undefined: " + src );
throw new ConstructorFailure();
}
if (travelTime < 0) {
Error.warn( this.toString() + ": negative travel time?" );
throw new ConstructorFailure();
}
allRoads.add( this ); // this is the only place items are added!
}
Specifically, look at these lines:
dst = sc.getNext( "???", "road " + src + " to missing destination" );
travelTime = sc.getNextFloat(
Float.NaN, "road " + src + " to missing destination"
);
new StringBuilder( "a" ).append( "b" ).append( "c" ).toString()
You can look up class StringBuilder and class String on the Oracle/Java web pages to see more complete documentation for these methods.
Remember, Java strings are not mutable, and Java string concatenation returns a new string object. Java objects of class StringBuilder are identical to strings, except that they are mutable and have a variety of append() and insert() methods for modifying the string. Things are worse than the above code suggests, because the code to initialize a new StringBuilder from a string has to copy the characters into place one at a time, and the append() method does the same.
The impact of this is considerable. Consider this method call:
dst = sc.getNext( "???", "road " + src + " to missing destination" );
This is really equivalent to
{
StringBuilder s = new StringBuilder( "road " );
s.append( src );
s.append( " to missing destination" );
dst = sc.getNext( "???", s.toString() );
}
Many of the methods on class StringBuilder end with return this. As a result, the above can be rewritten in a more compact form:
{
StringBuilder s = new StringBuilder( "road " )
.append( src )
.append( " to missing destination" );
dst = sc.getNext( "???", s.toString() );
}
We can even rewrite this as:
dst = sc.getNext(
"???",
new StringBuilder( "road " )
.append( src )
.append( " to missing destination" )
.toString()
);
None of the above rewrites reduce the number of method calls or the amount of string copying, where each string is represented internally as an array of characters, and string copying involves copying each of these characters.
The net result of all of this is that the total cost of this call to the getNext() method is likely to be dominated by the cost of computing the second parameter to the call. If the user does not make a syntax error (the normal case), the value of that parameter will simply be discarded, so the normal case involves considerable wasted computation.
Here is a code sample that shows a typical starting point for this. Notice that each error message in the sequence is a refinement of the previous one.
srcname = in.getNext( "???", "road: source missing" );
dstname = in.getNext( "???", "road: destination missing" );
travelTime = in.getNextFloat(
99999.9F,
"road " + srcname + " " + dstname + ": travel time missing"
);
in.getNextLiteral( ";",
"road " + srcname + " " + dstname + " " + travelTime +
": semicolon missing"
);
In this case, we can cut down on the wasted concatenations by accumulating the error message incrementally in a string variable:
String errMsg = "road" srcname = in.getNext( "???", errMsg + ": source missing" ); errMsg = errMsg + " " + srcname; dstname = in.getNext( "???", errMsg + ": destination missing" ); errMsg = errMsg + " " + dstname; travelTime = in.getNextFloat( 99999.9F, errMsg + ": travel time missing" ); errMsg = errMsg + " " + travelTime; in.getNextLiteral( ";", errMsg + ": semicolon missing" );
This solution takes advantage of the particular pattern of information used in this context, and it does cut the number of concatenations as well as tightening up the code significantly. The problem is that it still does a number of concatenations on speculation that there might be an error.
An interesting alternative solution that comes to mind is to change the getNext() methods so they take a number of strings as parameters. Thus, we replace
travelTime = in.getNextFloat(
99999.9F,
"road " + srcname + " " + dstname + ": travel time missing"
);
with this call:
travelTime = in.getNextFloat(
99999.9F, "road", srcname, dstname, ": travel time missing"
);
Here, we rely on the getNext method to do the concatenation, a job it will only do if there is an error. All the getNext methods have to take 4 string parameters, and they have to do the work of concatenating them, putting spaces between the strings.
If you need an error message that involves fewer strings, just pass empty strings. This could result in random extra spaces at the end of the message, but usually, nobody will notice this, and if it does matter, we can change the error output parts of the getNext methods to avoid sticking in spaces strings before empty strings.
It is a bit of a nuisance designing methods to use this solution because you need to anticipate the likely number of parameters that might be required. If you have a large program and then you discover some setting where more parameters are required, you either have to search the entire program for calls and add an extra null parameter everywhere, or just concatenate some of the extras in the rare case that you didn't plan on enough parameters.
Note also, there is a cost for parameter passing. With this solution, we always pass the maximum number of parameters we might need, wasting the cost of passing a bunch of nulls (or empty strings) when the call doesn't need that many parameters.
Of course, the number of parameters we need to pass depends on the particular error message we are generating. That means calling toString methods for some parameters, and those can be quite computationally intensive. Converting a float or double to textual format is far from trivial.