Introduction

fastutil extends the Java™ Collections Framework by providing type-specific maps, sets, lists and queues with a small memory footprint and fast access and insertion; it also includes a fast I/O API for binary and text files. It is free software distributed under the GNU Lesser General Public License.

The classes implement their standard counterpart interface (e.g., Map for maps) and can be plugged into existing code. Moreover, they provide additional features (such as bidirectional iterators) that are not available in the standard classes.

Besides objects and primitive types, fastutil classes provide support for references, that is, objects that are compared using the equality operator rather than the equals() method.

The sources are generated using a C preprocessor, starting from a set of driver files. You can peek at the javadoc-generated documentation. In particular, the overview explains the design choices used in fastutil.

Java™ 5

The release 5 of fastutil needs Java 5, and marks a revolution in the way the classes are organized. Besides full support for generics, which can help with object-based classes (but is rather irrelevant in type-specific classes), fastutil is now strongly based on what is probably the less hyped and most important feature of Java 5: covariant return-type overriding. A method x() returning an object of type T can now be overriden by a method returning an object of type U, where U is a subclass of (or implements) T.

Covariant return-type overriding has always been supported by the JVM, but was inaccessible at the syntax level. In Java 5 this irritant limitation has been lifted, opening a new world of clarity and orthogonality in organizing collection classes. In particular, interface strengthening makes it possible to use all features of fastutil classes without type casting: for instance, IntSet.iterator() is strengthened, w.r.t. Set.iterator(), so that it returns an IntIterator instead of a simple Iterator. Although type casting was previosuly used to simulate this feature, it made using the hundreds of classes in fastutil difficult and error-prone, as every type cast had to be checked against the documentation.

Another advantage of covariant return-type overriding is that implementations can declare to return more specific (usually, more powerful) types than those specified by their interface. For instance, IntAVLTreeSet.iterator() returns actually an IntListIterator, whereas IntSortedSet.iterator() is specified as returning just a IntBidirectionalIterator.

Installation

You just have to install the .jar file coming with the distribution. javadoc-generated documentation and sources are included. There are also Jpackage RPMs.

Note that the jar file is huge, due to the large number of classes: if you plan to ship your own jar with some fastutil classes included, you should look at AutoJar (also available at JPackage) to extract automatically the necessary classes.

History and Motivation

fastutil came up as a necessity during the development of UbiCrawler, as we needed to manage structures with dozens of millions of items very efficiently. The same reasons led to the development of the high-performance classes of dsiutils and MG4J (e.g., MutableString).