Improvements to lookup performance
aikar opened this issue ยท 1 comments
Hi, I'm the one who gave the idea and implementation concept on how to do Chunk based residence lookups for locations to t00thpick. However since my fork was from a few years ago and has diverted massively (i'd say mine is like 75% different at this point), we implemented it a little different.
You recently made a change to use containsKey instead of get, which was mostly a good idea, but there are still a few more inefficiencies.
- Doing 2 get(world) lookups. Should store a reference to first and reuse.
- Using .containsKey on world. I would expect nearly all calls to this method to return a world, by doing containsKey followed by get() you are hashing twice. the containsKey first is only beneficial if most cases it DOESN'T contain the key, but in this case the majority will.
- Storing a String instead of the Residence object itself, then looking it up. I haven't fully inspected the code for the latest version, but surely the entire object isn't being recreated anywhere? Storing the object itself instead of a name and looking it up saves yet another hashmap lookup.
Here is my version of this https://gist.github.com/aikar/ab822955f94ef4380d71
Notes:
- My ClaimedResidence is renamed Residence
- The UUID Map I have has nothing to do with Player UUID's. I assign every residence a UUID just to have a distinct identifier for every residence object instead of using the name, as a name can change (in the same way we had to do it for players =P)
- I extend Location instead of completely new class to simply make use of its hashCode/equals but I do like the simpler hash code you have as locations does stuff that will never be needed.
- I use a Multimap to keep the code super simple. If you want to keep the world based bucketing, you can use a Guava Table: http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Table.html
- Since iterating Residences by world is a very uncommon task (namely saving), I simply store world as a separate collection.
- Setting 2100 initial capacity to improve server startup performance as I'm guaranteed to have ~2000 residences per server.
With my version, a location lookup is in most cases 1 hashmap lookup (guaranteed), 1 iteration of a single element collection (I could fast track for single elements but losing RandomAccess by using a Multimap hurt me there), and res.containsLoc() check for each res in the chunk.
Feel free to use anything in that file (not that you needed my permission anyways :P)
Changes I'm going to make to mine:
- Override ChunkRef hashCode to use the same as yours: x ^ z
- Move to ArrayListMultimap, I realize by using a HashMultimap I'm losing iteration performance. I chose HashMultimap originally since I know I never want duplicates, but I'm confident the code is structured in a way we will not be inserting duplicates, so no worries there. World would already be having the same problem anyways if it did.
- While not likely needed for public use, I know for a fact my code calls getByLoc multiple times for same location, so going to add a last access cache to shortcut if same location is looked up back to back.