CollisionMap.getNeighbors now checks if a neighbor has already been visited saving a little time while eliminating whole lot of extra allocations. In addition, I've replaced the old HashMap<Integer, List<Transport>> with a new PrimitiveIntHashMap. This new hashmap only accepts primitive ints as keys. This removes the need to create new Integer objects like a generic hashmap would. This new hashmap ends up being faster than the standard Java HashMap but only for this specific use-case; it is not a general purpose hashmap nor should it be used as such. I also ran an experiment to find the best hash function for packed WorldPoints that keeps the hashmap buckets as small as possible both for speed and space (though buckets are allowed to grow if needed).
Also included is another test file to check and verify that the PrimitiveIntHashMap works as expected using real transport data.
Results
Same as before, testing the worst case of GE to some point in the top-left of the map in the ocean. Avoid wilderness is off so all nodes are visited.
CollisionMap.getNeighbors
now checks if a neighbor has already been visited saving a little time while eliminating whole lot of extra allocations. In addition, I've replaced the oldHashMap<Integer, List<Transport>>
with a newPrimitiveIntHashMap
. This new hashmap only accepts primitive ints as keys. This removes the need to create newInteger
objects like a generic hashmap would. This new hashmap ends up being faster than the standard JavaHashMap
but only for this specific use-case; it is not a general purpose hashmap nor should it be used as such. I also ran an experiment to find the best hash function for packed WorldPoints that keeps the hashmap buckets as small as possible both for speed and space (though buckets are allowed to grow if needed).Also included is another test file to check and verify that the
PrimitiveIntHashMap
works as expected using real transport data.Results
Same as before, testing the worst case of GE to some point in the top-left of the map in the ocean. Avoid wilderness is off so all nodes are visited.
Before
Worst-Case Time: 175.0368ms Allocations:
After
Worst-Case Time: 133.1026ms Allocations: