Method Specialization w.r.t. Function Objects

Method Specialization w.r.t. Function Objects

While both the C++ and Java programming do not support higher-order functions, there is a common workaround: function objects (or functors for short). These objects' sole function (no pun intended) is to stand in for what would otherwise by a first-class function – and not an object.

A Classic Example

/* Sort objects by their String representation */
Collections.sort(collection, new Comparator() {
    public int compare(Object lhs, Object rhs) {
        String s = lhs.toString();
        String t  = rhs.toString();
        return t.compareTo(s);
Java's sort method parameterized with a comparator function object

Arguably, the above code lacks some of the syntactic elegance of languages with true first-class functions – or even of C++ with its operator overloading. However, functors make an powerful idiom available to Java programmers. Still, it hasn't seen widespread use, although, e.g., the Collections framework of the Apache Commons project heartily embraces this technique. This is in no small part due to performance problems – which equivalent code in C++ does no suffer from, or at least to a much smaller extent.

Performance Problems and Optimization Opportunities

The performance problems are due to the fact that calls to compare are dynamically dispatched which adds overhead to each call. (And sort may call compare lots of times.) The goal of this hands-on training is thus to improve the performance of methods like sort which take a functor as an argument, up to the level of equivalent, hand-written code which performs the comparision directly. This can be accomplished by method specialization. In the case of sort, e.g., different comparators can cause different versions of sort to be invoked. Inside each of these versions the comparator's type is known; thus, the call to compare can be inlined, i.e., it vanishes completely – and with it the overhead of dynamic dispatch.

Such an inlining strategy should be implemented as part of the Jikes RVM , a Java virtual machine written in Java. Hereby one challenge is to identify function objects: what makes a function object a function object and which properties yield the optimization opportunities outlined above? Another challenge is to set up an rigorous benchmark so that different design decisions can be made – and evaluated.