A number of software engineers believe that design patterns are overly complicated, mythical, and abstract things that do not add any practical value to software development. It is sad. In order to prove that this is indeed something real, in this article (s) (and some to come) we are going to take a look at some examples of how real software products implement some of the GoF design patterns. Today we are going to visit Strategy, from HotSpot point of view. (See the previous post on Flyweight here).
Wikipedia defines the strategy as follows:
In computer programming, the strategy model (also known as policy model) is a software design model that allows you to select the behavior of an algorithm at run time. The strategy model
- defines a family of algorithms,
- encapsulates each algorithm, and
- makes the algorithms interchangeable within this family.
A generally good starting example is sorting arrays / collections. Let’s say we need to sort an array of numbers, so we implement BubbleSort, because it’s relatively easy. Within days, we realize that the input data is sometimes much larger than expected, so we implement QuickSort instead, to speed things up. Now QuickSort is great for large datasets, but for small tables it involves a lot of overhead. What if we take the best of both approaches and choose the right sort strategy at run time, based on the information we have about the dataset? Let’s look at the diagram below:
We simply extracted a common interface of the two sorting algorithms. The interface (or the abstract class, depending on the implementation) is called the abstract strategy, while BubbleSorter and QuickSorter are the concrete strategies. The worker can choose the right sorting strategy once he encounters the data to be sorted; this policy can be passed to the client via the constructor or a method argument.
Classes Collections and tables
Perhaps not surprisingly, one of the most obvious strategy implementations in the JDK is introduced by the Comparable interface. And just like in the example above, it’s all about sorting. Just look at the following diagram; it shows how sorting is implemented in Java for lists and arrays:
The similarities are easy to spot between the two diagrams. The comparator interface represents the abstract strategy, BooleanComparator, TestComparator and UserDefinedComparator are the concrete strategies, while Strategy’s clients are represented by Arrays and Collections in this case. Of course, starting with Java 8, classes like UserDefinedComparator become more and more rare, because Comparator
Let’s take a look at this. At first glance, a rather strange dependency of Collections.sort on Arrays.sort. The first method first converts the list to an array, using its toArray method. Then the Arrays.sort method is called and, in a final step, the elements of the list are overwritten by the elements of the array, using a ListIterator. There is therefore no specific sorting method implemented for the lists, Arrays.sort is reused.
Note that Collections.sort () cannot sort any type of collection, as many believe; it can only sort a list. Well that makes sense if you think about it. If one needs to sort a set, they must first use a sorted set. The same is true for maps – there is SortedMap which sorts entries based on their keys. For queues, a sorting method would contradict its primary use case – putting new items on one end, taking on the other – or taking on both ends in case of Dequeues. The only collection that makes sense to have a sort method is List.
But back to the implementation of the strategy, Arrays.sort is another interesting thing. This method first checks whether the transmitted comparator is zero or not. If so, the natural order of the items will be used for sorting. Note that the natural order (implemented as an inner class in Arrays, with the name NaturalOrder) assumes that the elements of the array are comparable (that is, they implement Comparable
Then the sorting method is selected. In most cases, Tim Sort will be used, unless the old Merge Sort is explicitly requested. The latter is not a good idea, as it will be removed in a future version, according to his comment. (To request a merge sort, the JVM must be started using the -Djava.util.Arrays.useLegacyMergeSort = true VM argument).
I was curious how the two sorting methods stacked up against each other in terms of speed. I didn’t use any sophisticated measurement method, just used larger and larger arrays with random integer values, and measured the time it took to sort. The run times below reflect the time taken by the sort method only, they do not include the time taken to create the test data:
|TimSort (ms)||Sort inherited (ms)|
As you can see, TimSort is generally a bit faster (except for arrays with very few elements) until we hit a fairly large dataset; from this point on, the inherited algorithm surpasses the new one.
Java 8 functional interfaces
It is not difficult to find more examples of the Strategy design model in the JDK, and it is even easier from version 8. Do a quick reference search for new functional interfaces (Predicate, Function , Consumer, Supplier, etc.) that this model is used literally everywhere.
Just an example: ArrayList defines a forEach method, which takes a Consumer as a parameter. The ArrayList class has no knowledge of specific Consumers, it only knows the interface. The collection client is responsible for delivering the desired implementation of this interface. Of course, these consumers usually don’t manifest as a class, but rather are represented as lambda expressions.
HashMap and ConcurrentHashMap also rely heavily on the Functional and BiFunction functional interfaces for computing and merging inputs.