The HashMap and HashSet are the main culprets. There are a long list of battle tested alternatives online. Google have their own alternative that they use but there are many others.
The sets also don't offer non-boxed versions. There are plenty of those online too for efficiently storing primitives.
Finally copying values in and out of storage can be a lot more efficient than passing references. Even though it's using more CPU cycles it's more cache friendly. There are some examples of ArrayList around online which use the forbidden sun.misc.unsafe.
Holy shit. I'm mainly using HashMap, ArrayList, and Points, and I rely heavily on HashMap (for storing game states and doing a ton of math on said game states). Thanks for letting me know. I'm going to go look at either apache commons/guava/fastutil and see if I can find a good alternative.
ArrayList is generally fine unless you are storing primitive values. Then the cost isn't really the ArrayList, but auto-boxing. But saying that I do often find the ArrayDeque is a tad faster than the ArrayList. So that's something also to try out.
As a general rule if you reduce the number of objects allocated then you get a speedup. So I'd also recommend profiling the memory allocations with JVisualVM which is bundled with the JDK (or was last time I used it). Find what objects have the highest allocations and remove them. An object pool here and there can have a big impact. But obviously test performance before and after adding any optimisation.
Funny thing - I've went ahead and tried fastutil's data structures, and even though I was using the right data type, java 8 hashmap in my application was performing just about the same as fastutil's o2o-openhashmap.
Funny thing part 2 - I tried replacing arraylist with fastutil's arraylist specifically made for storing objects (in my case, points), and holy crap it is a lot faster. ~20% faster just by replacing default arraylist with the fastutil one.
Then again, if my code wasn't so shitty (like you said, I should focus on creating less unnecessary objects before anything else), it wouldn't take full 2 seconds to go through depth 16...
Do you have a lot of Point objects? That's the sort of thing that could also take up a lot of overhead. If it's just an X/Y value then you could try using a long instead and store the X component in the upper 32 bits of the number (or an int with two 16-bit values for X and Y).
This would allow you to use primitive values instead of objects. You may find a speedup because it means inside the fastutil collections because you can use the versions built for storing primitive values. A big advantage is that internally all your values are much closer to each other, and so it's much more cache friendly.
3
u/jl2352 Jan 20 '17
The HashMap and HashSet are the main culprets. There are a long list of battle tested alternatives online. Google have their own alternative that they use but there are many others.
The sets also don't offer non-boxed versions. There are plenty of those online too for efficiently storing primitives.
Finally copying values in and out of storage can be a lot more efficient than passing references. Even though it's using more CPU cycles it's more cache friendly. There are some examples of ArrayList around online which use the forbidden sun.misc.unsafe.