Residence

Residence

960k Downloads

Improvements to lookup performance

aikar opened this issue ยท 1 comments

commented

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.

Code: https://github.com/bekvon/Residence/blob/master/src/com/bekvon/bukkit/residence/protection/ResidenceManager.java#L53-L63

  1. Doing 2 get(world) lookups. Should store a reference to first and reuse.
  2. 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.
  3. 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:

  1. My ClaimedResidence is renamed Residence
  2. 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)
  3. 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.
  4. 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
  5. Since iterating Residences by world is a very uncommon task (namely saving), I simply store world as a separate collection.
  6. 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)

commented

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.