Optimise tempt goal

[okx-code]

This patch attempts to optimise TemptGoal, where its behaviour causes every entity with that goal to check the items of every player in the same world every tick. With 2,000 entities and 50 players, that's 100,000 checks.

Instead, during a TemptGoal lookup, we iterate through all players and see if they have the correct items for the entity. The result is stored in a BitSet which can easily be looked up by future calls to TemptGoal to vastly cut down on the number of item comparisons and calls to getMainHandItem.

Benchmarks, performed with 50 bots and 500 pigs over one minute:

• Latest 1.21.4 paper: https://spark.lucko.me/Xc78N8lMng - 2.2% of the the tick time is in TemptGoal
• This patch: https://spark.lucko.me/pU4mhdX4Op - 0.17% of the tick time is in TemptGoal

These conditions were set up to highlight this improvement, but they are not unrealistic in real servers. This optimisation leads to a ~1 mspt decrease for the tested conditions.

[okx-code]

I don't think that storing data on the player would be nearly as effective.

The resizing of the BitSet is effectively a non-issue - we can represent the state for 64 players in a single long. A resizing is only required at 65 players and for every additional 64 players. Other than that, there are no serious additional allocations required every tick.

With this change, an entity running TemptGoal.canUse can check all players with just that one BitSet. This is very effective, because no player objects are actually looked up; the data required is in a single cache line.

If extra data was stored on the player, it would be a new cache line for every player, and rather inefficient.

[lynxplay]

Fair enough :+1:

[lynxplay]

Opinion in using an int index for access to the cached values? Means we can skip the temp goal lookup and bit set lookup for unoptimized goals implemented by e.g. plugins + we do not rely on hashmap and the predicate object hashcode being nice.

Also, rangeTargetConditions can/should probably not check the already checked item again. Would need a // dif on change on both the ctor tho

(e.g. https://pastebin.com/nyVarYwc)

[okx-code]

I opted for a HashMap here as it keeps the constructor signature the same and reduces the maintenance burden. We are already skipping the bit set lookup if the items predicate is not one of ours: if (lookupBitSet != null)

I think it's fine to rely on the Predicate hashCode because we are only adding the Predicates defined in the TemptGoalLookup class and nothing user-provided, so the implementation will always be the default Object.hashCode implementation, and we are effectively getting reference equality, which is all we need. If that's really a concern then we could use IdentityHashMap which calls System.identityHashCode instead.

I've added a change to remove the extra check on rangeTargetConditions.

[SirYwell]

One downside of the current approach here is that the calculation is eager. I think it would make sense to make it lazy by inversing the meaning of the bitset and marking players that shouldn't be followed. This can then be computed the first time it is actually needed. With the selector separated, you can also directly use the shouldFollow method directly, requiring less copied logic.

[lynxplay]

You are not skipping the bitset lookup, you'll be running into a HashMap#get miss on every tick in a hashmap that is nearly completely saturated (e.g. we will be doing 1 or more object comparisons, depending on the uncertain hashmap bucket layout, which may or may not be on the "cache line")

I am not particularly concerned over what hashcode is used, given the predicates do not overwrite this, it is indeed whatever. I am more concerned about the fact that the hashmap is going to end up with buckets/nodes with size > 1 given the unpredicable nature of the object hashes so our #get calls also need to dabble through the hashmap node table, so even a downside on the vanilla case where an optimized predicate is used.

Overloading a constructor really isn't that big of a deal, especially with a constructor that has not changed since 1.17.

Regarding your change, selector nulling can just be done in the ctor, also easier if we just overload the ctor if we end up passing an int index instead of a hashmap lookup.

[okx-code]

I've changed the code to use an integer index similar to your pastebin suggestion and I've also made the calculation lazy for each entity.

[lynxplay]

I've changed the code to use an integer index similar to your pastebin suggestion and I've also made the calculation lazy for each entity.

Thank you for the quick changes! I'll get to testing it tonight so we can get this merged. Especially with this now being lazy, it should be a performance improvement in any usecase, not just the ones where entities of this type exist.

[lynxplay]

For reference, SirYwell suggestion would have probably looked like this:

I personally do not have much of a preference between the two implementations, nextClearBit has to invert the words vs the one bitset lookup your implementation has to do on a single long for the predicate index. But yea, just for you to look at, maybe you find it prettier.

diff --git a/paper-server/patches/sources/io/papermc/paper/entity/goal/TemptGoalLookup.java.patch b/paper-server/patches/sources/io/papermc/paper/entity/goal/TemptGoalLookup.java.patch
index 95a44e4a15..bd9f5d9464 100644
--- a/paper-server/patches/sources/io/papermc/paper/entity/goal/TemptGoalLookup.java.patch
+++ b/paper-server/patches/sources/io/papermc/paper/entity/goal/TemptGoalLookup.java.patch
@@ -1,6 +1,6 @@
 --- /dev/null
 +++ b/io/papermc/paper/entity/goal/TemptGoalLookup.java
-@@ -1,0 +_,64 @@
+@@ -1,0 +_,54 @@
 +package io.papermc.paper.entity.goal;
 +
 +import java.util.ArrayList;
@@ -38,7 +38,6 @@
 +    }
 +
 +    private final List<BitSet> precalculatedTemptItems = new ArrayList<>();
-+    private final BitSet calculatedThisTick = new java.util.BitSet();
 +
 +    {
 +        for (int i = 0; i < registeredPredicateCounter; i++) {
@@ -50,18 +49,9 @@
 +        for (int i = 0; i < registeredPredicateCounter; i++) {
 +            this.precalculatedTemptItems.get(i).clear();
 +        }
-+        this.calculatedThisTick.clear();
 +    }
 +
-+    public boolean isCalculated(int index) {
-+        return this.calculatedThisTick.get(index);
-+    }
-+
-+    public void setCalculated(int index) {
-+        this.calculatedThisTick.set(index);
-+    }
-+
-+    public BitSet getBitSet(int index) {
++    public BitSet getBitSet(final int index) {
 +        return this.precalculatedTemptItems.get(index);
 +    }
 +}
diff --git a/paper-server/patches/sources/net/minecraft/world/entity/ai/goal/TemptGoal.java.patch b/paper-server/patches/sources/net/minecraft/world/entity/ai/goal/TemptGoal.java.patch
index b860b63cc2..cfa3b1f4fd 100644
--- a/paper-server/patches/sources/net/minecraft/world/entity/ai/goal/TemptGoal.java.patch
+++ b/paper-server/patches/sources/net/minecraft/world/entity/ai/goal/TemptGoal.java.patch
@@ -36,7 +36,7 @@
  
      @Override
      public boolean canUse() {
-@@ -42,8 +_,48 @@
+@@ -42,8 +_,47 @@
              this.calmDown--;
              return false;
          } else {
@@ -47,19 +47,18 @@
 +
 +            if (this.temptGoalLookupIndex != -1) {
 +                final io.papermc.paper.entity.goal.TemptGoalLookup lookup = ((net.minecraft.server.level.ServerLevel) this.mob.level()).getTemptGoalLookup();
-+                java.util.BitSet lookupBitSet = lookup.getBitSet(this.temptGoalLookupIndex);
++                final java.util.BitSet discardedPlayers = lookup.getBitSet(this.temptGoalLookupIndex);
 +                final net.minecraft.server.level.ServerLevel level = getServerLevel(this.mob);
 +                final java.util.List<net.minecraft.server.level.ServerPlayer> players = level.players();
-+                if (!lookup.isCalculated(this.temptGoalLookupIndex)) {
-+                    for (int i = 0; i < players.size(); i++) {
-+                        lookupBitSet.set(i, shouldFollow(players.get(i)));
-+                    }
-+                    lookup.setCalculated(this.temptGoalLookupIndex);
-+                }
 +                double d = -1.0;
 +                net.minecraft.server.level.ServerPlayer nearestPlayer = null;
-+                for (int i = lookupBitSet.nextSetBit(0); i >= 0; i = lookupBitSet.nextSetBit(i + 1)) {
++                // Iterate over all non-discarded players
++                for (int i = discardedPlayers.nextClearBit(0); i >= 0; i = discardedPlayers.nextClearBit(i + 1)) {
 +                    final net.minecraft.server.level.ServerPlayer player = players.get(i);
++                    if (!this.shouldFollow(player)) { // If we cannot follow the player, mark it as discarded so that other runs of tempt goal do not need to check.
++                        discardedPlayers.set(i);
++                        continue;
++                    }
 +                    if (rangeTargetingConditions.test(level, this.mob, player)) {
 +                        final double d1 = player.distanceToSqr(this.mob.getX(), this.mob.getY(), this.mob.getZ());
 +                        if (d == -1.0 || d1 < d) {

[okx-code]

Yeah that's not a bad way to do it, but you are calling shouldFollow potentially multiple times for the same player if they are not discarded.

[AnttiMK]

Did the TemptGoalLookup class accidentally slip into the wrong source tree (src/minecraft/java instead of src/main/java)? Pretty sure it shouldn't be a .patch since it's in Paper's package and not a feature patch

[okx-code]

There are class files in Paper's package in both src/minecraft/java and src/main/java, but I believe that src/minecraft/java is for non-API classes, and TemptGoalLookup is not API.

[lynxplay]

no, src/main/java is for everything not mojang :+1: It should indeed live in src/main/java. src/mojang/java only includes mojang types.

Tho I am considering moving all of these changes into a feature patch instead as it is semi-involved and we could live without it during an update / apply in experimental.

[okx-code]

ah ok, I'll move it

[SirYwell]

Yeah that's not a bad way to do it, but you are calling shouldFollow potentially multiple times for the same player if they are not discarded.

Yes, I expect that to be a rather uncommon case, but that claim might be hard to validate :)

Tho I am considering moving all of these changes into a feature patch instead as it is semi-involved and we could live without it during an update / apply in experimental.

One way to reduce the surface of the patch would be to get rid of the TemptGoalPredicate again and use the fact that all the current lambdas are non-capturing:

Index: paper-server/src/minecraft/java/net/minecraft/world/entity/ai/goal/TemptGoal.java
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/paper-server/src/minecraft/java/net/minecraft/world/entity/ai/goal/TemptGoal.java b/paper-server/src/minecraft/java/net/minecraft/world/entity/ai/goal/TemptGoal.java
--- a/paper-server/src/minecraft/java/net/minecraft/world/entity/ai/goal/TemptGoal.java	(revision 438ee55d4e6dc51b320f90b6fc4bb194f839a5f0)
+++ b/paper-server/src/minecraft/java/net/minecraft/world/entity/ai/goal/TemptGoal.java	(date 1736669373923)
@@ -7,7 +7,6 @@
 import net.minecraft.world.entity.PathfinderMob;
 import net.minecraft.world.entity.ai.attributes.Attributes;
 import net.minecraft.world.entity.ai.targeting.TargetingConditions;
-import net.minecraft.world.entity.player.Player;
 import net.minecraft.world.item.ItemStack;
 
 public class TemptGoal extends Goal {
@@ -26,7 +25,6 @@
     private boolean isRunning;
     private final Predicate<ItemStack> items;
     private final boolean canScare;
-    private final int temptGoalLookupIndex; // Paper - optimise tempt goal
 
     public TemptGoal(PathfinderMob mob, double speedModifier, Predicate<ItemStack> items, boolean canScare) {
         this.mob = mob;
@@ -34,21 +32,14 @@
         this.items = items;
         this.canScare = canScare;
         this.setFlags(EnumSet.of(Goal.Flag.MOVE, Goal.Flag.LOOK));
-        this.targetingConditions = TEMPT_TARGETING.copy().selector((entity, level) -> this.shouldFollow(entity));
-        this.temptGoalLookupIndex = -1; // Paper - optimise tempt goal
-    }
-
-    // Paper start - optimise tempt goal
-    public TemptGoal(PathfinderMob mob, double speedModifier, io.papermc.paper.entity.goal.TemptGoalLookup.TemptGoalPredicate temptGoalPredicate, boolean canScare) {
-        this.mob = mob;
-        this.speedModifier = speedModifier;
-        this.items = temptGoalPredicate.predicate();
-        this.canScare = canScare;
-        this.setFlags(EnumSet.of(Goal.Flag.MOVE, Goal.Flag.LOOK));
-        this.targetingConditions = TEMPT_TARGETING.copy();
-        this.temptGoalLookupIndex = temptGoalPredicate.index();
-    }
-    // Paper end - optimise tempt goal
+        // Paper start - optimise tempt goal
+        if (io.papermc.paper.entity.goal.TemptGoalLookup.canOptimise(items)) {
+            this.targetingConditions = TEMPT_TARGETING.copy();
+        } else {
+            this.targetingConditions = TEMPT_TARGETING.copy().selector((entity, level) -> this.shouldFollow(entity));
+        }
+        // Paper end - optimise tempt goal
+    }
 
     @Override
     public boolean canUse() {
@@ -59,17 +50,11 @@
             // Paper start - optimise tempt goal
             final TargetingConditions rangeTargetingConditions = this.targetingConditions.range(this.mob.getAttributeValue(Attributes.TEMPT_RANGE));
 
-            if (this.temptGoalLookupIndex != -1) {
-                final io.papermc.paper.entity.goal.TemptGoalLookup lookup = ((net.minecraft.server.level.ServerLevel) this.mob.level()).getTemptGoalLookup();
-                final java.util.BitSet lookupBitSet = lookup.getBitSet(this.temptGoalLookupIndex);
-                final net.minecraft.server.level.ServerLevel level = getServerLevel(this.mob);
+            final net.minecraft.server.level.ServerLevel level = getServerLevel(this.mob);
+            final io.papermc.paper.entity.goal.TemptGoalLookup lookup = level.getTemptGoalLookup();
+            final java.util.BitSet lookupBitSet = lookup.getBitSet(this.items, level, this::shouldFollow);
+            if (lookupBitSet != null) {
                 final java.util.List<net.minecraft.server.level.ServerPlayer> players = level.players();
-                if (!lookup.isCalculated(this.temptGoalLookupIndex)) {
-                    for (int i = 0; i < players.size(); i++) {
-                        lookupBitSet.set(i, shouldFollow(players.get(i)));
-                    }
-                    lookup.setCalculated(this.temptGoalLookupIndex);
-                }
                 double d = -1.0;
                 net.minecraft.server.level.ServerPlayer nearestPlayer = null;
                 for (int i = lookupBitSet.nextSetBit(0); i >= 0; i = lookupBitSet.nextSetBit(i + 1)) {
Index: paper-server/src/main/java/io/papermc/paper/entity/goal/TemptGoalLookup.java
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/paper-server/src/main/java/io/papermc/paper/entity/goal/TemptGoalLookup.java b/paper-server/src/main/java/io/papermc/paper/entity/goal/TemptGoalLookup.java
--- a/paper-server/src/main/java/io/papermc/paper/entity/goal/TemptGoalLookup.java	(revision 5e3d84a9e3fd4518e99452eb96c0f3a421973e2f)
+++ b/paper-server/src/main/java/io/papermc/paper/entity/goal/TemptGoalLookup.java	(date 1736670768945)
@@ -5,60 +5,66 @@
 import java.util.List;
 import java.util.function.Predicate;
 
-import net.minecraft.tags.ItemTags;
+import net.minecraft.server.level.ServerLevel;
+import net.minecraft.server.level.ServerPlayer;
 import net.minecraft.world.item.ItemStack;
-import net.minecraft.world.item.Items;
 
 public class TemptGoalLookup {
     private static int registeredPredicateCounter = 0;
 
-    public static final TemptGoalPredicate BEE_TEMPT = register(stack -> stack.is(ItemTags.BEE_FOOD));
-    public static final TemptGoalPredicate CHICKEN_TEMPT = register(stack -> stack.is(ItemTags.CHICKEN_FOOD));
-    public static final TemptGoalPredicate COW_TEMPT = register(stack -> stack.is(ItemTags.COW_FOOD));
-    public static final TemptGoalPredicate PANDA_TEMPT = register(stack -> stack.is(ItemTags.PANDA_FOOD));
-    public static final TemptGoalPredicate PIG_TEMPT_STICK = register(stack -> stack.is(Items.CARROT_ON_A_STICK));
-    public static final TemptGoalPredicate PIG_TEMPT = register(stack -> stack.is(ItemTags.PIG_FOOD));
-    public static final TemptGoalPredicate RABBIT_TEMPT = register(stack -> stack.is(ItemTags.RABBIT_FOOD));
-    public static final TemptGoalPredicate SHEEP_TEMPT = register(stack -> stack.is(ItemTags.SHEEP_FOOD));
-    public static final TemptGoalPredicate TURTLE_TEMPT = register(stack -> stack.is(ItemTags.TURTLE_FOOD));
-    public static final TemptGoalPredicate HORSE_TEMPT = register(stack -> stack.is(ItemTags.HORSE_TEMPT_ITEMS));
-    public static final TemptGoalPredicate LLAMA_TEMPT = register(stack -> stack.is(ItemTags.LLAMA_TEMPT_ITEMS));
-    public static final TemptGoalPredicate STRIDER_TEMPT = register(stack -> stack.is(ItemTags.STRIDER_TEMPT_ITEMS));
+
+    private static final ClassValue<Integer> TEMPT_GOAL_PREDICATE_CACHE = new ClassValue<>() {
 
-    public record TemptGoalPredicate(int index, Predicate<ItemStack> predicate) {
-    }
+        @Override
+        protected Integer computeValue(Class<?> type) {
+            // only consider non-capturing lambdas as pre-computable
+            if (type.isHidden() && type.getDeclaredFields().length == 0) {
+                return registeredPredicateCounter++;
+            }
+            return -1;
+        }
+    };
 
-    private static TemptGoalPredicate register(final Predicate<ItemStack> predicate) {
-        final TemptGoalPredicate val = new TemptGoalPredicate(registeredPredicateCounter, predicate);
-        registeredPredicateCounter++;
-        return val;
+    public static boolean canOptimise(Predicate<ItemStack> predicate) {
+        int i = TEMPT_GOAL_PREDICATE_CACHE.get(predicate.getClass());
+        return i >= 0;
     }
 
     private final List<BitSet> precalculatedTemptItems = new ArrayList<>();
-    private final BitSet calculatedThisTick = new java.util.BitSet();
-
-    {
-        for (int i = 0; i < registeredPredicateCounter; i++) {
-            this.precalculatedTemptItems.add(new BitSet());
-        }
-    }
+    private final BitSet calculatedThisTick = new BitSet();
 
     public void reset() {
-        for (int i = 0; i < registeredPredicateCounter; i++) {
+        for (int i = 0; i < this.precalculatedTemptItems.size(); i++) {
             this.precalculatedTemptItems.get(i).clear();
         }
         this.calculatedThisTick.clear();
     }
 
-    public boolean isCalculated(int index) {
-        return this.calculatedThisTick.get(index);
+    private boolean needsCalculation(int index) {
+        return !this.calculatedThisTick.get(index);
     }
 
-    public void setCalculated(int index) {
+    private void setCalculated(int index) {
         this.calculatedThisTick.set(index);
     }
 
-    public BitSet getBitSet(int index) {
-        return this.precalculatedTemptItems.get(index);
+    public BitSet getBitSet(Predicate<ItemStack> predicate, ServerLevel level, Predicate<? super ServerPlayer> shouldFollow) {
+        int idx = TEMPT_GOAL_PREDICATE_CACHE.get(predicate.getClass());
+        if (idx < 0) {
+            return null;
+        }
+        while (idx >= this.precalculatedTemptItems.size()) {
+            this.precalculatedTemptItems.add(new BitSet());
+        }
+        final BitSet bitSet = this.precalculatedTemptItems.get(idx);
+        if (needsCalculation(idx)) {
+            List<ServerPlayer> players = level.players();
+            for (int i = 0; i < players.size(); i++) {
+                bitSet.set(i, shouldFollow.test(players.get(i)));
+            }
+
+            setCalculated(idx);
+        }
+        return bitSet;
     }
 }

(+ reverting the changes in the mob classes)

This has the additional benefit that custom predicates might benefit as well. There are a few adjustments that could be made to this, e.g. avoiding the capturing lambda this::shouldFollow, but that's just a rough design how the change could be made less involved.

[lynxplay]

Rebased this and moved it into a feature patch. Also applied the changes to the brain sensor given it uses an (even worse) bit of logic for the same thing.

[okx-code]

Looks good, are we able to merge this?

[lynxplay]

Hopefully today yea, I'll run my own performance benchmarks and throw it at some more people for checks etc.

[tofipix]

any updates on this?

[lynxplay]

I have been swallowed by university work. I don't have a timeline for this but I'll rebase the patch once I have time. (if okx-code reads this).

[okx-code]

Dear paper, please my pr merge danke :)

[lynxplay]

Finally got around to benchmarking this myself.

50 player characters with 400 pigs, so maximum 20_000 checks a tick. Running the server for 2400 ticks, or 2 minutes, the required CPU time of TemptGoal#canUse is reduced from 2507ms (1.04ms per tick) to 160ms (or 0.06ms per tick).

Obviously this kind of scenario is incredibly fabricated, normal servers are not going to be running into such extreme situations if their player base is remotely distributed. This however could be in the realm of responsibility if case of larger farms using animals with tempt goals etc. Given the only regression compared to vanilla this patch introduces is the skipped recomputation mid-tick, and tick order is generally not something reliably exploited/depended upon, I'd argue this is fine to merge.

We should still monitor this patch once merged. In case the behaviour change does infact prove problematic, the behaviour could easily be toggled via a configuration option. With how easy this is toggled, it might just be worth adding a config option ahead of time, tho I'd appreciate more input from team members on that.

[okx-code]

Hi paper any update on merging this?

[lynxplay]

Rebased onto 1.21.6

[okx-code]

Hey thanks for rebasing, is there anything still blocking this PR?

[electronicboy]

Time, and the nature of concern around merging such things right before we jump onto the next MC build; hopefully we'll get this into .7

[okx-code]

Any hold up on this still now that we're on 1.21.8? I've backported this to 1.21.4, it has been on my server for a while and with ~130 players we have TemptGoal.canUse reduced from 2.4% to 0.4% of the tick

before: https://spark.lucko.me/RaqNgioLkT after: https://spark.lucko.me/wSyDiKDZa5

[lynxplay]

Rebased for 1.21.9, we cope.

[TauCu]

What about reversing the responsibility?

Modify ServerPlayer's doTick() so when it checks the held item and the item is animal food, it checks for nearby Animals and updates their goal every tick.

That way it's only checked for players, when holding animal food items.