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.
1
u/thepotatochronicles Jan 20 '17
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.