HashMap performance issue



I’ve just spent 2 hours trying to spot a performance issue. I’m using a HashMap<int,int> to store/search the position of dead pixels in a video stream.
The issue was that I was wasting most of the time in the HashMap::contains() function (115% CPU), and as I figured out with cachegrind, most of the time was spent in “isPositiveAndBelow”.
It turns out that the HashMap::contains() method resorts to using operator[] for the returned index from the hash function, but the hash function result is already checked to be in-bounds of the size.
Changing this to “getUnchecked()” resulted in a much lower CPU usage (35% CPU).

I think it’s safe to use getUnchecked() here anyway.


Ok, I was probably being a bit cautious there. If the hash generator was to go wrong and return an out-of-range value, then using operator[] would be helpful, but since there’s already an assertion, I think it’s fair to expect that function to do the correct thing, and for people to pay the price if they write a malfunctioning hash algorithm!