Add iterator cache to UnsafeList and use it in hotspots

Adds a specialized iterator for the list and a pool of iterators to avoid
object churn. Also optimizes the clear() method to reduce object creation.

4 files changed, 120 insertions, 20 deletions

diff --git a/src/main/java/net/minecraft/server/Chunk.java b/src/main/java/net/minecraft/server/Chunk.java
index 9fedd372..fb9bf205 100644
--- a/src/main/java/net/minecraft/server/Chunk.java
+++ b/src/main/java/net/minecraft/server/Chunk.java
@@ -57,7 +57,7 @@ public class Chunk {
         this.heightMap = new int[256];
 
         for (int k = 0; k < this.entitySlices.length; ++k) {
-            this.entitySlices[k] = new ArrayList();
+            this.entitySlices[k] = new org.bukkit.craftbukkit.util.UnsafeList(); // CraftBukkit - ArrayList -> UnsafeList
         }
 
         Arrays.fill(this.b, -999);
diff --git a/src/main/java/net/minecraft/server/PathfinderGoalSelector.java b/src/main/java/net/minecraft/server/PathfinderGoalSelector.java
index dc16a625..9ef8ec76 100644
--- a/src/main/java/net/minecraft/server/PathfinderGoalSelector.java
+++ b/src/main/java/net/minecraft/server/PathfinderGoalSelector.java
@@ -4,10 +4,14 @@ import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.List;
 
+import org.bukkit.craftbukkit.util.UnsafeList; // CraftBukkit
+
 public class PathfinderGoalSelector {
 
-    private List a = new ArrayList();
-    private List b = new ArrayList();
+    // CraftBukkit start - ArrayList -> UnsafeList
+    private List a = new UnsafeList();
+    private List b = new UnsafeList();
+    // CraftBukkit end
     private final MethodProfiler c;
     private int d = 0;
     private int e = 3;
@@ -21,7 +25,7 @@ public class PathfinderGoalSelector {
     }
 
     public void a() {
-        ArrayList arraylist = new ArrayList();
+        UnsafeList arraylist = new UnsafeList(); // CraftBukkit - ArrayList -> UnsafeList
         Iterator iterator;
         PathfinderGoalSelectorItem pathfindergoalselectoritem;
 
diff --git a/src/main/java/net/minecraft/server/World.java b/src/main/java/net/minecraft/server/World.java
index d552df0f..56c5df05 100644
--- a/src/main/java/net/minecraft/server/World.java
+++ b/src/main/java/net/minecraft/server/World.java
@@ -10,6 +10,7 @@ import java.util.concurrent.Callable;
 // CraftBukkit start
 import org.bukkit.Bukkit;
 import org.bukkit.craftbukkit.util.LongHashset;
+import org.bukkit.craftbukkit.util.UnsafeList;
 import org.bukkit.generator.ChunkGenerator;
 import org.bukkit.craftbukkit.CraftServer;
 import org.bukkit.craftbukkit.CraftWorld;
@@ -54,7 +55,7 @@ public abstract class World implements IBlockAccess {
     public final VillageCollection villages = new VillageCollection(this);
     protected final VillageSiege siegeManager = new VillageSiege(this);
     public final MethodProfiler methodProfiler;
-    private ArrayList d = new ArrayList();
+    private UnsafeList d = new UnsafeList(); // CraftBukkit - ArrayList -> UnsafeList
     private boolean L;
     // CraftBukkit start - public, longhashset
     public boolean allowMonsters = true;
@@ -112,7 +113,7 @@ public abstract class World implements IBlockAccess {
 
         this.M = this.random.nextInt(12000);
         this.J = new int['\u8000'];
-        this.N = new ArrayList();
+        this.N = new UnsafeList(); // CraftBukkit - ArrayList -> UnsafeList
         this.isStatic = false;
         this.dataManager = idatamanager;
         this.methodProfiler = methodprofiler;
diff --git a/src/main/java/org/bukkit/craftbukkit/util/UnsafeList.java b/src/main/java/org/bukkit/craftbukkit/util/UnsafeList.java
index c6deec14..b1e3416d 100644
--- a/src/main/java/org/bukkit/craftbukkit/util/UnsafeList.java
+++ b/src/main/java/org/bukkit/craftbukkit/util/UnsafeList.java
@@ -5,26 +5,38 @@ import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.Serializable;
 import java.util.AbstractList;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
 import java.util.List;
+import java.util.NoSuchElementException;
 import java.util.RandomAccess;
 
 // implementation of an ArrayList that offers a getter without range checks
+@SuppressWarnings("unchecked")
 public class UnsafeList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
     private static final long serialVersionUID = 8683452581112892190L;
+
     private transient Object[] data;
     private int size;
     private int initialCapacity;
 
+    private Iterator[] iterPool = new Iterator[3];
+    private int poolCounter;
+
     public UnsafeList(int capacity) {
         super();
-        if (capacity < 0) capacity = 128;
+        if (capacity < 0) capacity = 32;
         int rounded = Integer.highestOneBit(capacity - 1) << 1;
         data = new Object[rounded];
         initialCapacity = rounded;
+
+        for (int i = 0; i < iterPool.length; i++) {
+            iterPool[i] = new Itr();
+        }
     }
 
     public UnsafeList() {
-        this(128);
+        this(32);
     }
 
     public E get(int index) {
@@ -98,7 +110,15 @@ public class UnsafeList<E> extends AbstractList<E> implements List<E>, RandomAcc
     public void clear() {
         // Create new array to reset memory usage to initial capacity
         size = 0;
-        data = new Object[initialCapacity];
+
+        // If array has grown too large create new one, otherwise just clear it
+        if (data.length > initialCapacity << 3) {
+            data = new Object[initialCapacity];
+        } else {
+            for (int i = 0; i < data.length; i++) {
+                data[i] = null;
+            }
+        }
     }
 
     // actually rounds up to nearest power of two
@@ -115,7 +135,39 @@ public class UnsafeList<E> extends AbstractList<E> implements List<E>, RandomAcc
     }
 
     public boolean isEmpty() {
-        return size != 0;
+        return size == 0;
+    }
+
+    public Object clone() throws CloneNotSupportedException {
+        UnsafeList<E> copy = (UnsafeList<E>) super.clone();
+        copy.data = Java15Compat.Arrays_copyOf(data, size);
+        copy.size = size;
+        copy.initialCapacity = initialCapacity;
+        copy.iterPool = new Iterator[iterPool.length];
+        return copy;
+    }
+
+    public Iterator<E> iterator() {
+        Itr iterator = null;
+        poolCounter = poolCounter++ % iterPool.length;
+
+        // Try to find an iterator that isn't in use
+        for (Iterator iter : iterPool) {
+            if (!((Itr) iter).valid) {
+                iterator = (Itr) iter;
+                break;
+            }
+        }
+
+        // Couldn't find a free one, round robin replace one with a new iterator
+        // This is done in the hope that the new one finishes so can be reused
+        if (iterator == null) {
+            iterPool[poolCounter] = new Itr();
+            iterator = (Itr) iterPool[poolCounter];
+        }
+
+        iterator.reset();
+        return iterator;
     }
 
     private void rangeCheck(int index) {
@@ -153,16 +205,59 @@ public class UnsafeList<E> extends AbstractList<E> implements List<E>, RandomAcc
         }
     }
 
-    public UnsafeList<E> clone() {
-        try {
-            UnsafeList<E> copy = (UnsafeList<E>) super.clone();
-            copy.data = Java15Compat.Arrays_copyOf(data, size);
-            copy.size = size;
-            copy.initialCapacity = initialCapacity;
-            return copy;
-        } catch (CloneNotSupportedException ex) {
-            // This should never happen
-            return null;
+    private class Itr implements Iterator<E> {
+        int index;
+        int lastRet = -1;
+        int expectedModCount = modCount;
+        boolean valid = true;
+
+        public void reset() {
+            index = 0;
+            lastRet = -1;
+            expectedModCount = modCount;
+            valid = true;
+        }
+
+        public boolean hasNext() {
+            valid = index != size;
+            return valid;
+        }
+
+        public E next() {
+            if (modCount != expectedModCount) {
+                throw new ConcurrentModificationException();
+            }
+
+            int i = index;
+            if (i >= size) {
+                throw new NoSuchElementException();
+            }
+
+            if (i >= data.length) {
+                throw new ConcurrentModificationException();
+            }
+
+            index = i + 1;
+            return (E) data[lastRet = i];
+        }
+
+        public void remove() {
+            if (lastRet < 0) {
+                throw new IllegalStateException();
+            }
+
+            if (modCount != expectedModCount) {
+                throw new ConcurrentModificationException();
+            }
+
+            try {
+                UnsafeList.this.remove(lastRet);
+                index = lastRet;
+                lastRet = -1;
+                expectedModCount = modCount;
+            } catch (IndexOutOfBoundsException ex) {
+                throw new ConcurrentModificationException();
+            }
         }
     }
 }