Quite often, a program needs to go through all elements of a Map. Unfortunately, like a Set, a Map doesn’t have index in the data structure so you can’t just get a key of certain index or a value of certain index.
The most common practice used to iterate all elements in a Map is to get the key set and then based on the key, we can retrieve the value. The template we use for such case is something like this:
for (String k : m.keySet()) {
Integer v = m.get(k);
// do something with the key and value
}
This works of course, but based on quick observation, this should be not that efficient because we have to retrieve value using key for every step. It would be much better to get the key and value as a pair in the beginning. This is unfortunately less obvious and less used. The template would be something like this (of course, we need to change the generic type as properly):
for (Entry<String, Integer> e : m.entrySet()) {
Integer v = e.getValue();
// do something with the key and value
}
Now let’s make some tests. I use this template for the test and changing the backing object, number of iteration, and the method to get the key and value from the map (of course it’s not that real, because we only use the value and ignore the key, in which case we can use values() for better performance).
public static void main(String[] args) {
java.util.Map<String, Integer> m = new TreeMap<String, Integer>();
for (int i = 0; i < 500000; i++) {
m.put(i + "", i);
}
List<Integer> l = new ArrayList<Integer>();
long st = System.currentTimeMillis();
for (String string : m.keySet()) {
l.add(m.get(string));
}
System.out.println(System.currentTimeMillis() - st);
}
From my tests, I observe that the performance of the first template depends on the backing object. If we are using HashMap, the performance is less or more the same as the second template. If we are using Hashtable, the performance of the first template is about 1.5 times worse as the second template and if we are using TreeMap, the performance of the first template is more than 5 times worse as the second template. This proved my original hypotheses and we as developers should try to change our instinct to use the second template every time we encounter such problem.
UPDATE: I redo the test using nanotime and it’s just confirming my original observation.
Related posts:
What was your total time? And what O/S was this run on? 500000 iterations should be pretty quick, and at least on windows currentTimeMillis only gets ~15ms resolution. I would be curious to see the performance with varying numbers of iterations and using the ‘nano’ time resolution instead currentTimeMillis. I agree with you on principle, just because its so needless to re execute the get, when you’ve already had to traverse the whole map anyways. It’s amazing to me how often I see this ‘bad’ practice.
Nice post
I tested this on a 3-4 years old laptop using Windows XP as OS. I got 40-45ms for HashMap, 60-65ms for Hashtable, and >200ms for TreeMap.
When you have a time less than one second you should always use nanotime. Resolution is 10-20ms for currentTimeMillis so your results are probably very inaccurate.
Completely untrustworthy microbenchmark, for too many reasons to mention.
Also, you have no idea if hotspot compiled one or the other version. The only way to make sure is to run it much much longer and pre-warm it a couple of seconds.
Thank you for the suggestion guys, I’ll keep it in mind. Overall, this is just a simple benchmark that shows us (OK… me, if you are not convinced), that we should change our instinct in such case. There is no down side to that, after all.
Hi,
this is guy of an obvious result if you think about the underling implementation
when you go through a map of n elements by the keyset and a lookup – the get method-
the cost is about n for going through the map a 1 for each look for a hasmap, log2(n) for a treemap
that gives you 2n and n + n log2(n)
when you go through with the entry set the cost is only n.
as Hashtable is synchronized the cost of the lookup is maybe s*n where so (s + 1)n
n< 2n < n (1 + log2(n)) < (s +1) n
Complexity theory is the key … Check your data structure courses …
> n (1 + log2(n)) < (s +1) n
Maybe you should retake some of those courses yourself
does that not depend on the value of s ?
s does not increase with n, aka “a constant”. O(sn) = O(n) < O(nlogn)
Nice discussion guys. Well, speaking theoretically, you’re conclusion is correct, but practically HashMap and Hashtable might also have worse performance (in case of bad implementation of hashcode).
My point is, regardless of our backing object, please traverse the map using Entry. That will save you a day of performance tuning later.
Dimitris agree, was putting the number in the context of the result of that test were it’s very likely that s > log2(n).
But if the hotspot can detect that the synchronization is useless then s = 1. and obviously that goes with the HashMap.
Nanda,
I sure agree with that. And I did not that it was a unknown fact. Also I meet a lot of developer who are not that fluent on the Collection framework…
@Arnaud: why are you keep saying that s > log2(n)? s is on most of the case is lesser than log2(n) and so my test result. I don’t think hotspot can do anything to make s = 1. And afterall, if the map is in a multi-thread environment, then HashMap and TreeMap are useless, we will have to synchronize them manually.
Nanda sorry my mistake there I read wrong.
http://www.j2ee.me/javase/7/docs/technotes/guides/vm/performance-enhancements-7.html
The server compiler may eliminate synchronization blocks (lock elision) if it determines that an object is thread local. For example, methods of classes such as StringBuffer and Vector are synchronized because they can be accessed by different threads. However, in most scenarios, they are used in a thread local manner. In cases where the usage is thread local, the compiler may optimize and remove the synchronization blocks.
http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/ConcurrentHashMap.html
I can only read the following as a joke:
>>My point is, regardless of our backing object, please traverse the map using Entry. That will save you a day of performance tuning later.<<
If someone wasted a day for such kind of "performance tuning", I would fire him on the spot, unless his wage is so low that he practically works for free, that is
Man you’re rude ! I would fire you for spending you time leaving snarky comment on blogs
though I understand your point… That’s not gonna make any real application faster …
@Arnaud: that’s nice enhancement of Java 7
@Dimitris: Thanks God I don’t work for you
Sorry guys, I just have a grumpy temper when confronted with, ahem, “dubious” advice helpfully offered, but then, what do I care for? If someone gets mislead by some remark he didn’t critically think before absorbing, then he had it coming. Anyway, I’ll try to be more polite and considering
Many bad practices are OK in most cases but can lead to a disaster in a specific case (eg when your application is using a very big Map). String concatenation, using Hashtable in a single thread app, etc you name it. What I try to offer is a way to prevent problem in those specific case (which will be very hard to detect) by developing best practices habit in their programming instinct.
Especially for this tips, it has no bad effect of developing it, doesn’t it?
I find the slower version more readable than the faster version, mostly because the entrySet() version is more verbose. My advice would be to always use the more readable form unless you discover that traversing a Map in this way is a perfomance bottleneck in your application (which I suspect is unlikely). Avoid premature optimisation!
@Matt: then I guess you are the supporter of using string concatenation instead of StringBuilder, right?
@Nanda Firdausi: yes, when there’s no serious risk of performance problems. You use common sense; in practice, you probably want to make sure there’s an upper bound on the size/number of Strings you’re concatenating, because the performance goes from linear to quadratic time complexity. By contrast, the difference between the two ways of iterating over a Map’s contents differ by a constant factor, and you’re unlikely to run into catastrophic performance problems by using one idiom over the other.
@Matt: “the difference between the two ways of iterating over a Map’s contents differ by a constant factor”. As the commentators above explained, the difference between one method and another is not a constant factor, but can be log(n) in case of TreeMap.
@Nanda — I wouldn’t even worry about TreeMaps, unless it was clear through profiling that it was a performance hotspot. I think it’s good to note the opportunity for performance tuning, but I don’t agree that it’s worth encouraging developers to *always* use a (somewhat) less readable idiom when 99% of the time the speed-up will be negligible.
@Matt: about less readable, I tend to disagree with you. In my opinion, my approach is just as readable as the usual one if not conciser. Since this is subjective manner, I don’t intend to prolong the debate in that direction.
@Nanda: Agreed that there’s little value in debating subjective “readability”, but I feel I have to take you up on your assertion that the entrySet() version is more concise. Not so:
In your code sample above, you don’t get the key out of the entry. To be comparable, you’d need more code to fetch it from the entry (you’d probably want to do that to improve your benchmark, by the way). Second, I’d argue that it’s particularly verbose in Java 5+ because of the type parameters on Entry. It’s not too bad for Entry, but it’s more often that you end up working with longer-winded types, like Entry<CustomerId, List>.
Obviously, everyone has their own style and preferences, but the keySet() route is definitely shorter code, and I personally think that makes it just a little more readable.
I’ll just say “ditto” to many of Matt’s comments. Unfortunately, many new programmers fall into the trap of spending hours (days… weeks…) collecting these kinds of almost-always-irrelevant optimizations, and integrating *all* of them religiously into their code — often resulting in horribly unmaintainable messes and huge wastes of time. And of course they still have performance problems, because they often don’t really understand where I/O, database queries, etc. will have a far greater toll.
Funny that there was also a mention of the “StringBuilder vs. concatenation” debate… I’ve seen people actually rewriting perfectly good code to remove all string concatenation, making it far less readable in the process and often not actually making ANY improvement to performance (not even shaving off a few millis), because in many of those cases the standard concatenation was being compiled into uses of StringBuilder anyway. Ugh.
In general, optimization should only be done in the context of performance testing — so you know the real benefits you’re getting in exchange for less readable code, and you’re attacking the actual hotspots in your code… not just showing off your latest tricks at the cost of a less maintainable codebase.
I’m not really complaining about the original post — it’s very useful to think in terms of efficiency when coding — but any “optimization” discussion should be extra careful to put any gains in perspective (including real examples of when this might actually matter, i.e., NOT the vast majority of the time!), to try and educate about optimization in general.
I’ve been programming Java professionally for more than a decade now, and I can’t think of any instance where I was iterating through an entire Map that was larger than a few dozen elements. Sure, I’ve used larger Maps (but without ever iterating through their entire contents… they’re for lookups, generally; that’s the point). And generally any larger dataset would be in a database, anyway….
Does anyone have an actual project example where this would have fixed a performance hotspot?
@Rob: Please share your opinion whether the entrySet is for you more unreadable than keySet version or not. Thanks.
I wrote an article to continue our discussion here: http://satukubik.com/2009/08/10/premature-optimization-vs-best-practice/
It’s a fairly small difference in this case, I think — the standard idiom is easier to read simply because it’s the standard idiom, really. My main point is (I suppose) that any discussion of optimization really needs this context of reality.
In other words — the cost of the change here is quite small; but the gain is also pretty much nil in all but some very rare special cases (as far as I can think of), so I’m not sure it’s even worth discussing.
I’ll check out your continued discussion, I suspect you’ll touch on some of these issues — thanks!