Repeatability in software development

Developing software has compared to other engineering disciplines a great advantage in testability. We can automatically test our whole product within a short period of time and after every change we did. Comparing this to quality testing, for example in mechanical engineering, reveals, that we can save a lot of time and test more often even during development. This provides us a quality assurance with high performance compared to other disciplines.

Repeatability in tests

To gain this performance we have to write tests with certain properties. Andy Hunt and David Thomas, and in the newer version also Jeff Langr, describe in their book Pragmatic Unit Testing the A-TRIP or FIRST properties of tests. Both sets are comparable and both contain repeatability, which provides reliable results between test runs. This is a property which is also required in simulations.

Repeatability in simulations

Given the same inputs, and the same version, a simulation must produce the same output. In fields, where simulations should cover a certain amount of uncertainty, like in traffic simulations, randomness is introduced to model human decision making. The simulations are designed as a kind of a monte carlo experiment.

As randomness in general is not repeatable, pseudo randomness is used. This means, a random number generator with a specified seed is used to provide reproducible experiments. As long as the seed is equal, the simulation should produce the same output. After the seed has been changed, the simulation might produce another output.

Using controlled random number generators is one aspect to reproduce results of earlier experiments. Another aspect is avoiding to use data structures, that store data in an uncontrolled way, like HashMaps. As HashMap might change to order of the stored objects during a rehash. Due to this, the iteration order at different times during the execution of the program might be different. This is also mentioned in the JavaDoc comment.

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

On the other side, HashMap is based on the hashCode Method of Object to store and distribute the objects in the internal data structure. As mentioned in the JavaDoc of hashCode, a hashCode must not be equal for the same object at different executions of the same application.

This integer need not remain consistent from one execution of an application to another execution of the same application.

The first aspect might not corrupt repeatability as long as the elements are added to the map in the same way and the rehashing does not change between the executions. The second aspect is only relevant when the application iterates over the map and might corrupt repeatability. In case only the lookup mechanism of the map is used, HashMap is just fine.

Alternatives

There are several alternatives which provide repeatable iteration order. When using comparable keys with a natural order, one can use TreeMap, which implements SortedMap. Entries implementing Comparable are sorted based on the compareTo method or a given Comparator. As long as the compare mechanism stays the same, the results will be repeatable.

If there is no natural order of elements or no order could be defined, one could use a LinkedHashMap. LinkedHashMap does not rely on comparable objects, but can store objects in the order they have been added. This results in repeatable simulation experiments as long as the input data is stored in the same order.

Conclusion

When your application must produce the same output given the same input, think twice which data structures you use. In case you want to iterate over the entries or keys of a Map, use an implementation which will provide a repeatable iteration order, like TreeMap or LinkedHashMap. The same applies in tests. Otherwise your tests may run on your machine, but fail on another one. So be sure to use the right data structure for the right task.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s