In “Game of Life, hash tables and hash codes” we implemented Conway’s game of Life
HashMap. This implementation stored Life’s field as a hash map with cell co-ordinates as keys.
We tried several classes to represent those co-ordinates, mainly differing from each other by the hash function.
Each such class required its own implementation of Life algorithm. This is very unfortunate, because it causes a lot of code duplication, and requires additional effort introducing new hash functions. Since then (in “Optimising division-based hash functions”) we added two of them, and more are coming. I got tired of this duplication effort, so I want to investigate what can be done here.
In other words, we are now embarking on a process that most managers hate but most programmers love: refactoring. Most programmers consider refactoring the ultimate fun and are willing to spend their entire time doing it. Because of that it is important to make sure the process eventually stops. In real life this happens due to natural factors, such as a manager, a deadline and a year-end bonus, but in experiments like mine I have to rely on self-discipline.
We must also keep in mind that this process is usually the opposite to the process of optimisation. The programs become shorter and clearer, but hardly faster. One should make sure the cost in performance loss isn’t too high.
The entire code is in this repository. Here are the examples of the classes: one key class and one Life implementation based on it.
Here is the key class,
And here is the corresponding Life implementation,
is the original (coming from the reference implementation) class, representing the co-ordinates as a pair of integers,
LongUtil is a collection of
useful methods to operate on
long values – split, combine, convert to
LongPointX is accompanied by its own Life implementation
Hash_LongPointX. Why? It seems that
encapsulation, which is part of a classic object-oriented design, should make it unnecessary.
If the main program only uses methods from some public interface, it can work with objects of any classes that implement it.
However, one operation can’t be part of object interface: the object creation. Since we need to create objects
in the main program (we have three instances of
new LongPointX() there), a simplistic object-oriented approach
The Java generics won’t help either, for the same reason: they can’t create objects of the parameter classes. This isn’t valid Java:
Note that similar code is perfectly valid in C++:
In C++ we could make a
LongPointX class a template parameter and instantiate
Hash_LongPoint with appropriate
values of these parameters. It would create specialised versions of
Hash_LongPoint. Perhaps, I will try it later.
Unfortunately, this is not possible in Java.
There are two simple ways to resolve this problem in Java. In one we add a method “create new instance” to each
LongPointX class. Then we start the whole simulation with creating one dummy object, and then make sure we have
existing object around each time we create a new one.
Another way it to use factories. A factory is a companion class whose job is to create objects of our class. Just one instance of a factory is necessary; it can be kept inside main Life implementation.
Both solutions introduce a virtual call where a new object must be created. Both introduce some extra complexity to a program. That’s why in the original article I wrote:
- We could work that around by introducing
factory classes, but this would complicate our code and hardly improve performance.
However, a need to get rid of multiple implementations of Life is stronger. Besides, it’s interesting to test this statement.
Even though the factory-based solution seems a bit more complicated, I still prefer it to the one with “create new instance”
method, because it clearly separates the functionality. One class is responsible for creation, another one for operations.
We can even make
protected to make sure that the factory is the only way to create these objects.
We’ll keep our
HashLong implementations unchanged, but make a unified
This implementation will operate on objects of
LongPoint class, which will be the base class of all our
classes. Some functionality (such as
toString() and the value
v itself) can now
be implemented in the base class. The derived classes must only provide specific methods - in our case
First, we need an abstract class
LongPoint class is modified like this:
And this is what happens to the derived class:
The object creation in the main implementation must be replaced by calls to a factory object:
Finally, the main class can now run
test() is a test method that creates a Life structure, runs a given number of iterations and measures time.
As before, we have two classes for each
LongPointimplementation – a class itself and another class accompanying it. However, the classes are now smaller and much more code is re-used instead of being copy-pasted.
The code isn’t very ugly after all; it is slightly more complex since it introduces additional concept (a factory), but it is much better than endless replication of
The abstract factory class could be made an interface; I prefer using abstract classes wherever possible. I know that this is not a recommended Java way, but they usually perform better, and this is an optimisation exercise after all. Besides, our abstract class has one concrete method (
create (int x, int y)), and methods inside interfaces have only been introduced in Java 8.
The factory classes do not have to be placed right inside the main classes; they could be made top-level. It is a matter of personal style.
LongPoint.Factorycould fulfil the role or
LongPointFactory, then we would have one class less. However, I prefer current design, because it is safer: it forces the derived classes to implement abstract methods. If
LongPoint.Factorywas used as the base class, some derived class could by accident inherit its implementation of
create()(for that it’s enough to misspell the method name or change the signature, and omit the
Some final touches
I had to make some more modifications of the code. They are not so important and rather technical; so if the reader is not interested, I recommend skipping this chapter and going straight to test results.
The main test routine (in the class
Life) previously looked like this:
The Life implementation was passed as a class object rather than the instance object because we wanted clean fresh
object, not the one that has just gone through the test. We can’t do it anymore, since some implementations are
now parameterised with a factory, and some others are not. We’ll have to use the implementation object itself
reset() method to its interface, which returns the object to its original state (cleans the field). We
could use the factory technique here again, but that looks like an overkill.
We also can’t use the class name as the test output label, because most of the time it will be
means we need another method, called
getName(), in the
Worker interface. In the parameterised class it will return
the parameter class name.
And finally, the last change. Previously, all
Hash_LongPointX classes extended
LongUtil to get
unqualified access to handy utility methods such as
toPoint(). We can’t do it anymore,
LongPointX classes now extend
LongPoint, and we can’t extend two classes in Java.
One can argue, however, that extending a class for a sole purpose of using its static members as utility functions is a bad idea anyway. This is similar to defining constants in interfaces – a practice called Constant Interface Antipattern. This practice is discouraged by Java designers. Here is what the Java documentation says:
The problem is that a class's use of the static members of another class is a mere implementation detail.
When a class implements an interface, it becomes part of the class's public API.
Implementation details should not leak into public APIs.
The Wikipedia article referenced above offers some more arguments against this practice, which are fully applicable to the static methods in the abstract classes.
Fortunately, Java (since version 1.5) has an
import static construct that allows direct import of static methods
and fields from any class without need to inherit this class. There is just one catch: the class mustn’t be in the default package.
In real life this is not a problem, since no one is using default
packages in real life. However, I consider the default package appropriate for the test samples such as this Life project.
LongUtil has to leave the default package and go somewhere else (
util package in our case). The
class goes there, too.
Hash_LongPoint does not extend
Worker does not have to be an interface anymore; it can
become an abstract class. This allows it to contain a default implementation of
getName(), which works for non-
Here is the new version of the code. It does not look too complex, so the first part of my previous statement is probably not correct. And here are the execution times, measures on Java 7
|Class name||Comment||Time before||Time after||change|
|Point||Multiply by 3, 5||2743||2728||-0.55%|
|LongPoint||Multiply by 3, 5||2602||2719||+4.50%|
|LongPoint3||Multiply by 11, 17||2074||2257||+8.82%|
|LongPoint4||Multiply by two big primes||2000||2128||+6.40%|
|LongPoint5||Multiply by one big prime||1979||2150||+8.64%|
|LongPoint6||Modulo big prime||1890||2032||+7.51%|
|LongPoint60||Modulo optimised, unsigned||2124||2247||+5.79%|
|LongPoint61||Modulo optimised, signed||2198||2368||+7.73%|
and on Java 8
|Class name||Comment||Time before||Time after||change|
|Point||Multiply by 3, 5||4961||5049||+1.77%|
|LongPoint||Multiply by 3, 5||4836||4809||-0.56%|
|LongPoint3||Multiply by 11, 17||2028||1928||-4.93%|
|LongPoint4||Multiply by two big primes||1585||1611||+1.64%|
|LongPoint5||Multiply by one big prime||1553||1744||+12.30%|
|LongPoint6||Modulo big prime||1550||1650||+6.45%|
|LongPoint60||Modulo optimised, unsigned||1608||1877||+16.72%|
|LongPoint61||Modulo optimised, signed||1689||1885||+11.60%|
We expected that an extra virtual call would slow execution down, and, in most cases, it did. There are cases when the speed didn’t change much or when it became higher (in one case by as much as 18%), but most common outcome is a 5-15% slowdown. I consider this a fair price for getting rid of code duplication.
In our new code a virtual call is made for each object creation. We can reduce the number of virtual calls by increasing their size, for example,
if we create more than one object in each one. If we make virtual methods even bigger, we can reduce the number of calls more, the ultimate
case being our original code where there were no virtual calls at all (except those required by
HashMap). However, each increase in virtual
method size means extra code duplication. Somewhere between two extreme cases - “All the code is duplicated” and “All the code is generic; the lowest-level
methods are virtual” lies a sweet spot where performance is good and code duplication is still manageable. I want to show two versions that lie between these extremes
and check if they are better than our refactored version.
In our first version, which we’ll call “
Neighbours” we’ll have a virtual call that creates eight objects instead of one. We’ll revive
neighbours() method that existed in
Point class. The full code is in its own branch.
This is what we add to
We’ll override this method in all the other
LongPoint classes. Here is the code from
The factory class and
create() method is still there – we need it to initialise the field.
dec() methods in
Hash_LongPoint will look like this:
Since we don’t allocate objects in
dec() anymore, we had to change their signatures to accept
LongPoint rather than
Another alternative version (called
SetReset and stored in its own branch) goes further and pulls
LongPoint class as well, eliminating the need to allocate,
fill and iterate a neighbour array. This is what
LongPoint looks like in this version:
protected methods are identical for all
LongPoint classes and can be re-used; the other two must be overridden in all derived
The appropriate place from
Hash_LongPoint will look like this:
I’ll only run these versions for two of the versions – say,
LongPoint4 (multiply by two big primes) and
LongPoint6 (modulo big prime).
Here are the results on Java 7:
|LongPoint4||Multiply by two big primes||2000||2128||2370||2090|
|LongPoint6||Modulo big prime||1890||2032||2230||2080|
and on Java 8
|LongPoint4||Multiply by two big primes||1585||1611||1794||1600|
|LongPoint6||Modulo big prime||1550||1650||1749||1580|
The results are surprisingly consistent. The tests demonstrate the same pattern.
Neighboursfailed expectations and performed badly in all the cases; I’m not sure why and I’m too lazy to investigate. We’ve replaced eight virtual calls by one array allocation and some manipulations with this array. Perhaps, Java VM was able to optimise those virtual calls well.
SetResetmostly behaved as expected (between the performance of the original code and that of the refactored one).
SetResetsolution is very ugly, because it draws the boundary between the algorithm (
Hash_LongPoint) and the data item (
LongPoint) classes in very unusual place. Some implementation details of the
Hash_LongPointhave been pulled inside
LongPoint, making the overall solution less readable and more difficult to maintain. It even went as far as leaking the data structure used in the algorithm (a
LongPoint’s public interface. This is really a bad idea. I’d rather not use classes at all and write everything in plain C than use the code like this. Besides, the amount of code duplication is rather big.
Neighboursis better, because the
neighbours()method can qualify as a reasonable part of a public interface. It is natural to ask a point for a list of its neighbours, and it does not leak implementation details into fundamental classes. However, this method is long, and it must be written for every new version of
LongPointclasses, and the primary point of the entire refactoring exercise was to reduce the amount of code duplication. I would have used the
neighbours()method if there were very few of
LongPointclasses, but not in our situation. In addition, this solution didn’t improve performance.
In short, both solutions have failed, and I won’t bother with them anymore.
Abstract classes are good: improving the class hierarchy
While experimenting with the alternative versions described above, I initially modified all the
LongPointX classes, except for
LongPoint7. I just forgot to include
the required methods. And guess what? The
LongPoint7 version compiled and ran, but didn’t work. It produced incorrect results – fortunately, it was detected by a correctness check.
It was easy to forget to upgrade a class, because there was nothing that prevented us from it. All the methods were present in the base class.
This is a good point to remember for the future: if some classes differ from each other in the implementation of some method, this method
abstract. Otherwise, there is danger of accidentally inheriting the base class implementation, which may not be applicable, By the way, the
Object class doesn’t
follow this guideline, for it has default implementations of
This means that the best way to lay out our classes is to introduce some base
LongPoint class, containing
v field and all the common methods, and to let all the other
classes, including the original one (which we’ll rename as
LongPoint1) inherit it. Let’s do it. We won’t change the
SetReset, since I said I wouldn’t bother with
them anymore, but let’s fix the main solution (branch master). We’ll also remove one of the
HashTime classes (the original one)
and fix the remaining one use refactored classes.
Here is the code. The speed didn’t change.
Why did the correctness check fail when we forgot to modify
LongPoint7? This class inherited
LongPoint, which returns an array of
It would not have made a difference (except for performance), if the classes didn’t differ in the
hashCode() function. Strictly speaking, our design isn’t correct: our
equals() method is not in sync with
hashCode(). Java does not allow objects that are
equals to have different hash codes. The only reason why we still used
this design was that we planned to use only one class representing a point in the full program. Different classes were not supposed to mix, let alone be inserted into
the same hash map. This, however, happened by accident, so we have to watch out for such cases. In this respect our primary refactoring is better than the alternative
solutions – it requires less code it the derived class.
One more refactoring
The factory classes we’ve created do not require multiple instances. Exactly one instance of each of them is sufficient. Creating more than one identical factory just adds confusion,
so the best form of a factory is a singleton – the class with exactly one instance. Such a class doesn’t need a name - anonymous class would work. This is what it can looks like
The code in the main class must then be changed accordingly:
The new code is here. Again, the performance stays the same.
This is where the self-discipline mentioned in the beginning suggests that we stop refactoring. Not because there is no more improvements (I can’t think of any right now, but there are always some), but because we must stop somewhere, and now is a good time.
Moderate use of common design patterns can reduce the total code size and the amount of necessary code duplication. The code becomes neater and more maintainable.
It comes at a cost: overheads of extra virtual calls cause performance penalties. We saw speed reduction by as much as 16% in some cases.
There is more than one way to refactor a program, and some are better than another.
Refactoring is a pleasant and potentially endless process. Unless kept under control, it can use up all your time and energy, so it is important to stop somewhere. One must make a firm decision “This is good enough”.
Now we are ready to start adding more hash functions. These include new version of modulo- and CRC-based once. I’m also going to run an investigation of the strange behaviour of the modulo-based version, which performs poorly as a microbenchmark but well as a full test.