Replace LongObjectHashMap with a more efficient implementation

After further testing it appears that while the original LongHashtable
has issues with object creation churn and is severly slower than even
java.util.HashMap in general case benchmarks it is in fact very efficient
for our use case.

With this in mind I wrote a replacement LongObjectHashMap modeled after
LongHashtable. Unlike the original implementation this one does not use
Entry objects for storage so does not have the same object creation churn.
It also uses a 2D array instead of a 3D one and does not use a cache as
benchmarking shows this is more efficient. The "bucket size" was chosen
based on benchmarking performance of the HashMap with contents that would
be plausible for a 200+ player server. This means it uses a little extra
memory for smaller servers but almost always uses less than the normal
java.util.HashMap.

To make up for the original LongHashtable being a poor choice for generic
datasets I added a mixer to the new implementation based on code from
MurmurHash. While this has no noticable effect positive or negative with
our normal use of chunk coordinates it makes the HashMap perform just as
well with nearly any kind of dataset.

After these changes ChunkProviderServer.isChunkLoaded() goes from using
20% CPU time while sampling to not even showing up after 45 minutes of
sampling due to the CPU usage being too low to be noticed.

2 files changed, 10 insertions, 9 deletions

diff --git a/src/main/java/net/minecraft/server/ChunkProviderServer.java b/src/main/java/net/minecraft/server/ChunkProviderServer.java
index 72701d16..a9d0567d 100644
--- a/src/main/java/net/minecraft/server/ChunkProviderServer.java
+++ b/src/main/java/net/minecraft/server/ChunkProviderServer.java
@@ -11,6 +11,7 @@ import java.util.Set;
 import java.util.Random;
 
 import org.bukkit.Server;
+import org.bukkit.craftbukkit.util.LongHash;
 import org.bukkit.craftbukkit.util.LongHashSet;
 import org.bukkit.craftbukkit.util.LongObjectHashMap;
 import org.bukkit.event.world.ChunkUnloadEvent;
@@ -36,7 +37,7 @@ public class ChunkProviderServer implements IChunkProvider {
     }
 
     public boolean isChunkLoaded(int i, int j) {
-        return this.chunks.containsKey(i, j); // CraftBukkit
+        return this.chunks.containsKey(LongHash.toLong(i, j)); // CraftBukkit
     }
 
     public void queueUnload(int i, int j) {
@@ -50,7 +51,7 @@ public class ChunkProviderServer implements IChunkProvider {
             if (k < -short1 || k > short1 || l < -short1 || l > short1 || !(this.world.keepSpawnInMemory)) { // Added 'this.world.keepSpawnInMemory'
                 this.unloadQueue.add(i, j);
 
-                Chunk c = this.chunks.get(i, j);
+                Chunk c = this.chunks.get(LongHash.toLong(i, j));
                 if (c != null) {
                     c.mustSave = true;
                 }
@@ -60,7 +61,7 @@ public class ChunkProviderServer implements IChunkProvider {
             // CraftBukkit start
             this.unloadQueue.add(i, j);
 
-            Chunk c = this.chunks.get(i, j);
+            Chunk c = this.chunks.get(LongHash.toLong(i, j));
             if (c != null) {
                 c.mustSave = true;
             }
@@ -81,7 +82,7 @@ public class ChunkProviderServer implements IChunkProvider {
     public Chunk getChunkAt(int i, int j) {
         // CraftBukkit start
         this.unloadQueue.remove(i, j);
-        Chunk chunk = (Chunk) this.chunks.get(i, j);
+        Chunk chunk = (Chunk) this.chunks.get(LongHash.toLong(i, j));
         boolean newChunk = false;
         // CraftBukkit end
 
@@ -96,7 +97,7 @@ public class ChunkProviderServer implements IChunkProvider {
                 newChunk = true; // CraftBukkit
             }
 
-            this.chunks.put(i, j, chunk); // CraftBukkit
+            this.chunks.put(LongHash.toLong(i, j), chunk); // CraftBukkit
             if (chunk != null) {
                 chunk.addEntities();
             }
@@ -121,7 +122,7 @@ public class ChunkProviderServer implements IChunkProvider {
 
     public Chunk getOrCreateChunk(int i, int j) {
         // CraftBukkit start
-        Chunk chunk = (Chunk) this.chunks.get(i, j);
+        Chunk chunk = (Chunk) this.chunks.get(LongHash.toLong(i, j));
 
         chunk = chunk == null ? (!this.world.isLoading && !this.forceChunkLoad ? this.emptyChunk : this.getChunkAt(i, j)) : chunk;
         if (chunk == this.emptyChunk) return chunk;
diff --git a/src/main/java/net/minecraft/server/SpawnerCreature.java b/src/main/java/net/minecraft/server/SpawnerCreature.java
index c9870fd1..efde3f71 100644
--- a/src/main/java/net/minecraft/server/SpawnerCreature.java
+++ b/src/main/java/net/minecraft/server/SpawnerCreature.java
@@ -7,14 +7,14 @@ import java.util.List;
 import java.util.Random;
 
 // CraftBukkit start
-import org.bukkit.craftbukkit.util.LongObjectHashMap;
 import org.bukkit.craftbukkit.util.LongHash;
+import org.bukkit.craftbukkit.util.LongObjectHashMap;
 import org.bukkit.event.entity.CreatureSpawnEvent.SpawnReason;
 // CraftBukkit end
 
 public final class SpawnerCreature {
 
-    private static LongObjectHashMap b = new LongObjectHashMap(); // CraftBukkit - HashMap -> LongObjectHashMap
+    private static LongObjectHashMap<Boolean> b = new LongObjectHashMap<Boolean>(); // CraftBukkit - HashMap -> LongObjectHashMap
     protected static final Class[] a = new Class[] { EntitySpider.class, EntityZombie.class, EntitySkeleton.class};
 
     protected static ChunkPosition getRandomPosition(World world, int i, int j) {
@@ -95,7 +95,7 @@ public final class SpawnerCreature {
                         // CraftBukkit start
                         long key = ((Long) iterator.next()).longValue();
 
-                        if (!((Boolean) b.get(key)).booleanValue()) {
+                        if (!b.get(key)) {
                             ChunkPosition chunkposition = getRandomPosition(worldserver, LongHash.msw(key), LongHash.lsw(key));
                             // CraftBukkit end
                             int k1 = chunkposition.x;