What is the most efficient Java Collections library? [closed]
What is the most efficient Java Collections library?
A few years ago, I did a lot of Java and had the impression back then that trove is the best (most efficient) Java Collections implementation. But when I read the answers to the question "Most useful free Java libraries?" I noticed that trove is hardly mentioned. So which Java Collections library is best now?
UPDATE: To clarify, I mostly want to know what library to use when I have to store millions of entries in a hash table etc. (need a small runtime and memory footprint).
Solution 1:
The question is (now) about storing lots of data, which can be represented using primitive types like int, in a Map. Some of the answers here are very misleading in my opinion. Let's see why.
I modified the benchmark from trove to measure both runtime and memory consumption. I also added PCJ to this benchmark, which is another collections library for primitive types (I use that one extensively). The 'official' trove benchmark does not compare IntIntMaps to Java Collection's Map<Integer, Integer>, probably storing Integers and storing ints is not the same from a technical point of view. But a user might not care about this technical detail, he wants to store data representable with ints efficiently.
First the relevant part of the code:
new Operation() {
private long usedMem() {
System.gc();
return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
}
// trove
public void ours() {
long mem = usedMem();
TIntIntHashMap ours = new TIntIntHashMap(SET_SIZE);
for ( int i = dataset.size(); i-- > 0; ) {
ours.put(i, i);
}
mem = usedMem() - mem;
System.err.println("trove " + mem + " bytes");
ours.clear();
}
public void pcj() {
long mem = usedMem();
IntKeyIntMap map = new IntKeyIntOpenHashMap(SET_SIZE);
for ( int i = dataset.size(); i-- > 0; ) {
map.put(i, i);
}
mem = usedMem() - mem;
System.err.println("pcj " + mem + " bytes");
map.clear();
}
// java collections
public void theirs() {
long mem = usedMem();
Map<Integer, Integer> map = new HashMap<Integer, Integer>(SET_SIZE);
for ( int i = dataset.size(); i-- > 0; ) {
map.put(i, i);
}
mem = usedMem() - mem;
System.err.println("java " + mem + " bytes");
map.clear();
}
I assume the data comes as primitive ints, which seems sane. But this implies a runtime penalty for java util, because of the auto-boxing, which is not neccessary for the primitive collections frameworks.
The runtime results (without gc() calls, of course) on WinXP, jdk1.6.0_10:
100000 put operations 100000 contains operations
java collections 1938 ms 203 ms
trove 234 ms 125 ms
pcj 516 ms 94 ms
While this might already seem drastic, this is not the reason to use such a framework.
The reason is memory performance. The results for a Map containing 100000 int entries:
java collections oscillates between 6644536 and 7168840 bytes trove 1853296 bytes pcj 1866112 bytes
Java Collections needs more than three times the memory compared to the primitive collection frameworks. I.e. you can keep three times as much data in memory, without resorting to disk IO which lowers runtime performance by magnitudes. And this matters. Read highscalability to find out why.
In my experience high memory consumption is the biggest performance issue with Java, which of course results in worse runtime performance as well. Primitive collection frameworks can really help here.
So: No, java.util is not the answer. And "adding functionality" to Java collections is not the point when asking about efficiency. Also the modern JDK collections do not "out-perform even the specialized Trove collections".
Disclaimer: The benchmark here is far from complete, nor is it perfect. It is meant to drive home the point, which I have experienced in many projects. Primitive collections are useful enough to tolerate fishy API - if you work with lots of data.
Solution 2:
From inspection, it looks like Trove is just a library of collections for primitive types - it's not like it's meant to be adding a lot of functionality over the normal collections in the JDK.
Personally (and I'm biased) I love Guava (including the former Google Java Collections project). It makes various tasks (including collections) a lot easier, in a way which is at least reasonably efficient. Given that collection operations rarely form a bottleneck in my code (in my experience) this is "better" than a collections API which may be more efficient but doesn't make my code as readable.
Given that the overlap between Trove and the Guava is pretty much nil, perhaps you could clarify what you're actually looking for from a collections library.
Solution 3:
I know this is an old post and there are a ton of answers here. But, The answers above are superficial and over simplified in terms of suggesting a library. There is no one library that does well across the various benchmarks presented here. The only conclusion I derive is if you care about performance and memory and specifically dealing with primitive types, its more than worth looking at the non jdk alternatives.
Here is a more sound analysis, in terms of benchmark mechanics and the libraries covered. This is a thread in the mahout dev list.
The libraries covered are
- HPPC
- Trove
- FastUtil
- Mahout ( Colt )
- Java Collections
Update June 2015: Unfortunately, the original benchmarks are no longer available and besides its a bit outdated. Here is a fairly recent (Jan 2015) benchmarks done by someone else. It is not as comprehensive nor does it have the interactive exploratory tools as the original link.
Solution 4:
As other commentators have noticed, the definition of "efficient" casts a wide net. However no one has yet mentioned the Javolution library.
Some of the highlights:
- Javolution classes are fast, very fast (e.g. Text insertion/deletion in O[Log(n)] instead of O[n] for standard StringBuffer/StringBuilder).
- All Javolution classes are hard real-time compliant and have highly deterministic behavior (in the microsecond range). Furthermore (unlike the standard library), Javolution is RTSJ safe (no memory clash or memory leak when used with Java Real-Time extension).
- Javolution's real-time collection classes (map, list, table and set) can be used in place of most standard collection classes and provide additional functionality.
- The Javolution collections provide concurrency guarantees to make implementation of parallel algorithms easier.
The Javolution distribution includes a benchmark suite so you can see how they stack up against other libraries/the built-in collections.
Solution 5:
Some collection libs to consider:
- Java collections in java.util
- Trove
- Google Collections library
- Apache Commons Collections
- High-scale lib from Cliff Click
- Doug Lea's collections lib - no longer supported and mostly rebuilt in JDK
I would first and foremost reach for the JDK collection library. It covers most common things you need to do and is obviously already available to you.
Google Collections is probably the best high-quality library outside the JDK. It's heavily used and well supported.
Apache Commons Collections is older and suffers a bit from the "too many cooks" problem but has a lot of useful stuff as well.
Trove has very specialized collections for cases like primitive keys/values. These days we find that on modern JDKs and with the Java 5+ collections and concurrent use cases, the JDK collections out-perform even the specialized Trove collections.
If you have really high concurrency use cases, you should definitely check out stuff like the NonBlockingHashMap in the high-scale lib, which is a lock-free implementation and can stomp on ConcurrentHashMap if you have the right use case for it.