Caching performance upgrade

[scorbett123]

Precomputing data in pathfinding leads to performance improvements.

This takes on average 7 - 10 ms to run initially, however then means that there is faster pathing throughout.

I've mainly focussed on changing occurrences during pathfinding, as MovementHelper.canWalkThrough being run every tick doesn't have any performance hit. A couple things I don't like about this though is that canWalkThrough is implemented again, with slightly different return values, so any change made to one, has to be also made to the other.

This is really dodgy in places, and is just an initial draft, which I'll later improve. I'd also appreciate it if other people can test it and tell me if there is any crashes / bugs.

[wagyourtail]

~~so, what's the status on this, I kinda want to include this (or #3375 until this is ready) for 1.19~~

edit: i thought this was implementing https://github.com/cabaletta/baritone/pull/3375#issuecomment-1089947417 but @scorbett123 says it's not

[scorbett123]

so, what's the status on this, I kinda want to include this (or #3375 until this is ready) for 1.19

Currently I've got exams, so don't have the same amount of time I usually do, I should be able to get this finished by the end of the week. It should only be a couple small changes moving some functions to movement helper, and fixing @ZacSharp's suggestion.

[scorbett123]

This should be Leijurv's requested changes. Does this look better to you?

[leijurv]

Let's make sure we get all the cases that happen on the pathing thread.

https://github.com/cabaletta/baritone/blob/868c023dbdd91012a074002ead135eee78d8c6d3/src/main/java/baritone/pathing/movement/MovementHelper.java#L460

Here's one example ^, this would be dreadfully nonperformant because it allocates an Optional<Boolean> as well as the orElseGet lambda, every time anything calls getMiningDurationTicks, which happens all the time in movement cost calculation.

Perhaps this could be tested by temporarily adding a if (!Minecraft.isCallingFromMainGameThread()) throw new IllegalStateException(); to the precomputed calculator (the one that makes optionals) and seeing if anything trips that?

Also - to anyone reading this thread, make sure to check out https://github.com/cabaletta/baritone/pull/3479#discussion_r892918082 (this discussion thread will probably be collapsed as resolved, so I want to put a link to it here)

[leijurv]

It also would just be really fun if instead of four boolean arrays for canWalkOn -> specialCases, canWalkOn -> dataPerBlockState, canWalkThrough -> specialCases, canWalkThrough -> dataPerBlockState, we instead just had a giant int[] (or even long[]) allDataForAllBlockStates and each bit represented one of those booleans. It would also probably be faster because it'd be way more cache friendly.

[scorbett123]

It also would just be really fun if instead of four boolean arrays for canWalkOn -> specialCases, canWalkOn -> dataPerBlockState, canWalkThrough -> specialCases, canWalkThrough -> dataPerBlockState, we instead just had a giant int[] (or even long[]) allDataForAllBlockStates and each bit represented one of those booleans. It would also probably be faster because it'd be way more cache friendly.

If someone else wants to do this then fine, but I don't even know how I'd get started doing something like this in a way with decent performance.

[wagyourtail]

NORMAL_CASE = 0xb1
SPECIAL_CASE_1 = 0xb10
SPECIAL_CASE _2 = 0xb100

assembling each

if (stuff for special case) value[blockstateid] |= SPECIAL_CASE_1

etc

and then I think java bytecode just does if statements on number that's not zero so value[blockstateid] & currentFlags != 0 would drop the neq 0 part.

[ZacSharp]

The bitpacking also allows checking two properties at once so if you have a lazy cache and in the value for a blockstate you set bit 0 indicate uninitialized values, bit 1 to indicate special cases and bit 3 to indicate the return value, if initialized and not special, then statemask & 0x11 == 0 is true only for nonspecial initialized blocks, meaning in that case you can return bit 3 without any further checks.

[scorbett123]

Ok, I understand now, I was getting confused with what leijurv was meaning, I thought it was many blocks in a single int / long, not an int per block. That makes more sense

[ZacSharp]

I thought it was many blocks in a single int / long

Which would require 10 or 20 times less memory for ints and longs respectively. Not sure about speed though. Minecraft does something like this to store chunk contents.

[leijurv]

Also let's do https://github.com/cabaletta/baritone/pull/3479#pullrequestreview-991101180 with the Optional<Boolean>, it bugs me to construct new Optionals for no reason.

private static final Optional<Boolean> TRUE = Optional.of(true);
private static final Optional<Boolean> FALSE = Optional.of(false);

👍

[leijurv]

Oh God, will this work in 1.13+? Or will IFluidState mess this up??

[ZacSharp]

Fluids are still tied to blocks pretty tightly with all waterloggable blocks having a waterlogged property so I think we can get away with at most a handful of new special cases (for those where the flowing state matters e.g. waterlogged open bottom trapdors in canWalkThrough).

[scorbett123]

Is that last commit the sort of thing you're looking for @leijurv? I still need to clean it up, but no point doing that if I'm going to need to significantly change it.

[leijurv]

Good stuff!

I think we shouldn't add precomputeddata as a constructor parameter to calcluationcontext anymore. It seems like there's essentially no downside to just making a new precomputeddata each time. Sharing precomputeddata across threads is a no-go, now that it's mutable.

Broadly, does this mean we don't actually need the setting modified event anymore?

[leijurv]

ok i pushed a commit to your branch (i didnt know this was possible until today)

[leijurv]

        if (block instanceof BlockLiquid) {
            if (state.getValue(BlockLiquid.LEVEL) != 0) {
                return NO;

Why?

[leijurv]

Ok this feels roughly about right.

I'd still like a 2nd/3rd/4th pair of eyes over MovementHelper's before/after to make sure it's about right. Also some testing would be good. Also benchmarking would be epic sauce.

[scorbett123]

What else is needed to be done on this to make this ready for merging @leijurv?

[leijurv]

@scorbett123 basically what I said here https://github.com/cabaletta/baritone/pull/3479#issuecomment-1185180741

i'd like if someone (maybe u could beg and plead in #dev-help lol) would closely look at the before/after in MovementHelper to make sure all the special cases were respected and none slipped through the cracks

a benchmark would be nice but not strictly needed

[leijurv]

ok whatever ill just merge it