Some Examples of Generics in Java 1.5 and C# 2.0

Dr. Richard Wiener, Editor-in-Chief, JOT, Associate Professor of Computer Science, University of Colorado at Colorado Springs

COLUMN

PDF Version

The forthcoming releases of Java JDK v1.5 and C# v2.0 support generic classes (classes with generic type parameters) and generic methods. Furthermore, each also supports constrained generic types.

Much has been written about generic types. In “A Comparative Study of Language Support for Generic Programming” by Garcia et al (http://www.osl.iu.edu/publications/pubs/2003/comparing_generic_programming03.pdf), details of generic types and programming in C++, Haskell, Standard ML, Eiffel, Java and C# are compared. Useful details and generic coding examples from the soon to be released Java JDK 1.5 (now in beta) are presented in the paper “Generics in the Java Programming Language” by Gilad Bracha. Some of the examples used in this column were inspired by this paper.

Generic types in Java and C# introduce more expressiveness at the source code level and move type checking from run-time to compile-time when inserting objects into generic collections. In the current pre-generic versions of Java and C#, genericity in collections is obtained through the backdoor of using the universal super type Object as a polymorphic placeholder for the actual reference type that defines the objects to be inserted into the collection. Other than programmer comments, there is little in the source code that reveals the type of object that the programmer intends to hold in the collection. Only by carefully reverse-engineering the source code does this become apparent if in fact only a single type is inserted into the non-generic collection. Generic collections in both Java and C# provide useful self-documentation in the source code in addition to strengthening compile-time type checking.

Java and C# use invariant generic typing in contrast with Eiffel which uses covariant typing. In Java and C# a List<String> is not a subtype of a List<Object>. These are considered separate stand-alone classes. In Eiffel, a List<B> would be considered a subtype of a List<A> if B conforms to A (B is a descendent of A or equal to A). Although covariant typing generally leads to more flexibility in the use of generics, it has been shown to allow code that is statically correct but fails at runtime (see “Type-Save Covariance: Competent Compilers Can Catch All Catcalls” by Mark Howard et al). Wildcards have been introduced into the generic lexicon of Java 1.5 to provide more flexibility in the absence of covariant typing.

The declaration Collection<T> myCollection declares myCollection as a collection with some unknown element type.

// Assume class Person has been defined elsewhere
Collection<?> myCollection = new ArrayList<Person>();
myCollection.add(new Object()); // COMPILE-TIME ERROR

The add command cannot be invoked on the myCollection object since the wildcard represents some unknown type. Since we do not know the type, we are not allowed to pass anything except the value null into add.

There is no direct equivalent to wildcards in C# generics but the same functionality can be achieved indirectly. We consider an example used in Gilad Bracha’s “Generics in the Java Programming Language.” Thanks go to Peter Sestoft (Professor in Information Technology at the Department of Mathematics and Physics, http://www.matfys.kvl.dk/ of the Royal Veterinary and Agricultural University, http://www.kvl.dk, in Denmark) for his thoughtful comments concerning the C# version of the implementation.

We wish to store and maintain a list of lists that contain elements that conform to an abstract class Shape (are of type Shape or a descendent of Shape). We present the Java solution first using wildcards and then show how, without wildcards, we can achieve the same functionality using generic C#.

Listing 1 – List of generic lists extending Shape in Java

Program output

In draw method of class Circle. x = 3 y = 0 radius = 5
In draw method of class Circle. x = 1 y = 4 radius = 10
In draw method in class Rectangle. x = 0 y = 0 width = 10 height = 20
In draw method in class Rectangle. x = 3 y = 4 width = 20 height = 30
In draw method in class Rectangle. x = 20 y = 40 width = 1 height = 2
In draw method in class RightTriangle. x = 0 y = 0 base = 10 height = 20
In draw method in class RightTriangle. x = 3 y = 4 base = 20 height = 30
In draw method in class RightTriangle. x = 20 y = 40 base = 1 height = 2
In draw method in class RightTriangle. x = 200 y = 400 base = 11 height = 21
In draw method in class RightTriangle. x = 78 y = 42 base = 17 height = 21

In outputHistory method.
In draw method of class Circle. x = 3 y = 0 radius = 5
In draw method of class Circle. x = 1 y = 4 radius = 10
In draw method in class Rectangle. x = 0 y = 0 width = 10 height = 20
In draw method in class Rectangle. x = 3 y = 4 width = 20 height = 30
In draw method in class Rectangle. x = 20 y = 40 width = 1 height = 2
In draw method in class RightTriangle. x = 0 y = 0 base = 10 height = 20
In draw method in class RightTriangle. x = 3 y = 4 base = 20 height = 30
In draw method in class RightTriangle. x = 20 y = 40 base = 1 height = 2
In draw method in class RightTriangle. x = 200 y = 400 base = 11 height = 21
In draw method in class RightTriangle. x = 78 y = 42 base = 17 height = 21

Discussion of Listing 1

The declaration,

defines the static field history as an ArrayList containing a List of Shape objects where Shape is a polymorphic placeholder for any conforming sub-type (Circle, Rectangle or RightTriangle).

Method drawShapeList first adds a new List, shapes, to history. It then uses the new for loop construct (C#’s foreach loop) to iterate through the shapes and send each shape the draw command (which produces output to the console).

Finally, method outputHistory uses two nested for loops to iterate through the lists and then for each list to iterate through the shapes contained within that list.

We next examine how to achieve the same functionality in generic C#.

Listing 2 – List of generic lists extending Shape in C#

Program Output

In OutputHistory method
In draw method of class Circle. x = 3 y = 0 radius = 5
In draw method of class Circle. x = 1 y = 4 radius = 10
In draw method in class Rectangle. x = 0 y = 0 width = 10 height = 20
In draw method in class Rectangle. x = 3 y = 4 width = 20 height = 30
In draw method in class Rectangle. x = 20 y = 40 width = 1 height = 2
In draw method in class RightTriangle. x = 0 y = 0 base = 10 height = 20
In draw method in class RightTriangle. x = 3 y = 4 base = 20 height = 30
In draw method in class RightTriangle. x = 20 y = 40 base = 1 height = 2
In draw method in class RightTriangle. x = 200 y = 400 base = 11 height = 21
In draw method in class RightTriangle. x = 78 y = 42 base = 17 height = 21

Discussion of Listing 2

It is not possible in C# to declare history as a stand-alone field with a constrained generic parameter as was done in Java. It is necessary to embed the history field inside of a static generic class Consts that explicitly establishes the generic constraint through,

This class also contains the public methods DrawShapeList and OutputHistory. Each of these methods utilizes a generic parameter F that extends the constrained generic parameter E.

The private static method AddShapeList requires two downcasts as well.

From the three method invocations,

the DrawShapeList method is able to infer the parameter F (inner list type).

Clearly there is more complexity and subtlety associated with the generic C# implementation than the generic Java implementation.

Since generics in Java was designed to be totally compatible with the existing JVM (Java virtual machine), it offers no performance improvement over straight non-generic Java. One may in fact view Java generics as an extension to the allowable syntax of standard Java with the compiler translating generic code first to standard non-generic code. So the declaration,

Collection<Integer> is seen by the virtual machine as Collection<Object>.

Generics were designed into the .NET framework so List<int> (aka List<Int32>) does not translate to List<Object>. There is no wrapping and unwrapping overhead required when constructing collections of value types such as int in generic C#. C# uses code specialization (like C++) when implementing collections of value types and uses code sharing (like Java) when implementing collections of non-value types (ordinary reference types). A simple experiment was designed to enable performance comparisons to be undertaken so that the efficiency of C# generics could be compared with that of generic Java both for value types (primitive types in Java) and reference types. Listings 3 and 4 contain the code that was used in this simple experiment. In each experiment, four stacks of base-type integer (int in C# and Integer in Java) were constructed by pushing one million integer objects onto the first stack and then popping that stack while loading the contents of the first stack onto the second stack and repeating this process until the fourth and last of the stacks is loaded with a million objects and then the objects popped from this last stack. The same scenario was repeated only using String as the base type rather than integer objects. Since String is a reference type in both languages this second experiment allows us to see whether any significant differences exist between the performance on generic reference types versus value types.

Listing 3 – Benchmark for Java Generics

Program Output

sum = 1999998000000
Elapsed time for intStack = 2.11 seconds.
sum = 1999998000000
Elapsed time for strStack = 0.937 seconds.

Listing 4 - Benchmark for Java Generics

Program Output

sum = 1999998000000
Elapsed time for int stack = 0.921875 seconds.
Elapsed time for str stack = 0.78125 seconds.

Discussion of Listing 3 and 4

The experiments were conducted on the same computer. The ratio of execution times is interesting.

For integer types (primitive type in Java and value type in C#), generic Java was 2.29 slower than generic C#. That is significant. For reference types, generic Java was 1.20 times slower. That is not significant and is in part due to the overall efficiency of Java JIT compared with the C# JIT (other experiments have suggested that the C# JIT is slightly more efficient than the Java 1.5 JIT).

In conclusion, the design decision to use code specialization for value types in C# has paid off in performance benefits. The wildcard semantics in generic Java appear to provide a more straight-forward mechanism for expressing complex generic constructions than the equivalent C# implementation.

About the author

Richard Wiener is Associate Professor of Computer Science at the University of Colorado at Colorado Springs. He is also the Editor-in-Chief of JOT and former Editor-in-Chief of the Journal of Object Oriented Programming. In addition to University work, Dr. Wiener has authored or co-authored 21 books and works actively as a consultant and software contractor whenever the possibility arises.

Cite this column as follows: Richard Wiener: “Some Examples of Generics in Java 1.5 and C# 2.0”, in Journal of Object Technology, vol. 3, no. 8, September-October 2004, pp. 81-96. http://www.jot.fm/issues/issue_2004_09/column8

Previous column