Optimize the advancement data player iteration to be O(N) rather than O(N^2)

1 files changed, 54 insertions, 0 deletions

diff --git a/Spigot-Server-Patches/0551-Optimize-the-advancement-data-player-iteration-to-be.patch b/Spigot-Server-Patches/0551-Optimize-the-advancement-data-player-iteration-to-be.patch
new file mode 100644
index 0000000000..2f91d733b6
--- /dev/null
+++ b/Spigot-Server-Patches/0551-Optimize-the-advancement-data-player-iteration-to-be.patch
@@ -0,0 +1,54 @@
+From 0000000000000000000000000000000000000000 Mon Sep 17 00:00:00 2001
+From: Wyatt Childers <[email protected]>
+Date: Sat, 4 Jul 2020 23:07:43 -0400
+Subject: [PATCH] Optimize the advancement data player iteration to be O(N)
+ rather than O(N^2)
+
+
+diff --git a/src/main/java/net/minecraft/server/AdvancementDataPlayer.java b/src/main/java/net/minecraft/server/AdvancementDataPlayer.java
+index c41e1384724ab150f43dc43fe2a453c9b1262e48..ac7b6734728f912ab9f02dc417f5924b3725adde 100644
+--- a/src/main/java/net/minecraft/server/AdvancementDataPlayer.java
++++ b/src/main/java/net/minecraft/server/AdvancementDataPlayer.java
+@@ -436,6 +436,16 @@ public class AdvancementDataPlayer {
+     }
+ 
+     private void e(Advancement advancement) {
++        // Paper start
++        e(advancement, IterationEntryPoint.ROOT);
++    }
++    private enum IterationEntryPoint {
++        ROOT,
++        ITERATOR,
++        PARENT_OF_ITERATOR
++    }
++    private void e(Advancement advancement, IterationEntryPoint entryPoint) {
++        // Paper end
+         boolean flag = this.f(advancement);
+         boolean flag1 = this.g.contains(advancement);
+ 
+@@ -451,15 +461,23 @@ public class AdvancementDataPlayer {
+         }
+ 
+         if (flag != flag1 && advancement.b() != null) {
+-            this.e(advancement.b());
++            // Paper start - If we're not coming from an iterator consider this to be a root entry, otherwise
++            // market that we're entering from the parent of an iterator.
++            this.e(advancement.b(), entryPoint == IterationEntryPoint.ITERATOR ? IterationEntryPoint.PARENT_OF_ITERATOR : IterationEntryPoint.ROOT);
+         }
+ 
++        // If this is true, we've went through a child iteration, entered the parent, processed the parent
++        // and are about to reprocess the children. Stop processing here to prevent O(N^2) processing.
++        if (entryPoint == IterationEntryPoint.PARENT_OF_ITERATOR) {
++            return;
++        } // Paper end
++
+         Iterator iterator = advancement.e().iterator();
+ 
+         while (iterator.hasNext()) {
+             Advancement advancement1 = (Advancement) iterator.next();
+ 
+-            this.e(advancement1);
++            this.e(advancement1, IterationEntryPoint.ITERATOR); // Paper - Mark this call as being from iteration
+         }
+ 
+     }