hasSurfaceAccess calculation lag

pupnewfster commented 6 years ago

Recently I have run a mod called TickProfiler to try to find any sources of lag and it throws a lot of messages like the one at the bottom.

Looking at the method hasSurfaceAccess there are a few comments I have:

Given you call bp.up() a lot why do you not store it in a variable so it does not have to be recalculated. This may not be needed as I do not know the performance cost of calling "up" for BlockPos
The same goes with line 99 where you call isBlockHollow(w, bp.up(), EnumFacing.UP) and then call it again on line 102. Except that this method seems more costly. So it should most likely be more like
```
boolean hollow;
if(w.canSeeSky(bp) && hollow = isBlockHollow(w, bp.up(), EnumFacing.UP))
return true;
```

if(hollow && hasSurfaceAccess(w, bp.up(), was_at)) return true;

- Next for was_at, as it seems to only be used as a lookup to make sure the same block is not checked multiple times, it would potentially improve performance by using a map of xz to y, or y to xz. This way it would lower the number of different values it has to compare to. This of course should be tested to make sure that this is the case, because if it only on average has to check a couple blocks it may lower performance slightly. In a worst case scenario such as having to check nearly every block in the chunk it should improve lookup time.

For example if it was xz to y the method may look like:

```java
private static boolean hasSurfaceAccess(World w, BlockPos bp, HashMap<Long, List<Integer>> was_at)
{
    long xz = (((long)bp.getX()) << 32) | (bp.getZ() & 0xffffffffL);
    List<Integer> ys = was_at.get(xz);
    if(ys != null && ys.contains(bp.getY()))
        return false;

    boolean hollow;
    if(w.canSeeSky(bp) && hollow = isBlockHollow(w, bp.up(), EnumFacing.UP))
        return true;

    if(hollow && hasSurfaceAccess(w, bp.up(), was_at))
        return true;

    for(EnumFacing facing : EnumFacing.HORIZONTALS)
    {
        BlockPos b = bp.offset(facing);
        if(isBlockHollow(w, b, facing))
        {
            if(w.canSeeSky(b))
                return true;
            else if(isBlockHollow(w, b.up(), EnumFacing.UP) && hasSurfaceAccess(w, b.up(), was_at))
                return true;
        }
    }

    if(ys == null)
    {
        ys = new ArrayList<Integer>();
        ys.add(bp.getY());
        was_at.put(xz, ys);
    }
    else
        ys.add(bp.getY());
    return false;
}

You could even use a set of some kind instead of a List, as the order does not matter as it is only for lookup.

If you want I may look at some point through the rest of the code and see if there are any other potential performance improvements throughout it, and then submit them as a pull request.

[14:16:31] [LagSpikeProfiler/INFO] [TickProfiler]: 
The server appears to have lag spiked.
Last tick 0.21748224s ago."Server thread" RUNNABLE
    at java.util.ArrayList.indexOf(ArrayList.java:317)
    at java.util.ArrayList.contains(ArrayList.java:300)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:96)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:103)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:117)
    at ecomod.common.pollution.PollutionUtils.hasSurfaceAccess(PollutionUtils.java:201)
    at ecomod.asm.EcomodASMHooks.leavesTickAddition(EcomodASMHooks.java:125)
    at net.minecraft.block.BlockLeaves.func_180650_b(BlockLeaves.java:176)
    at net.minecraft.block.Block.func_180645_a(Block.java:508)
    at net.minecraft.world.WorldServer.func_147456_g(WorldServer.java:475)
    at net.minecraft.world.WorldServer.func_72835_b(WorldServer.java:225)
    at net.minecraft.server.MinecraftServer.func_71190_q(MinecraftServer.java:754)
    at net.minecraft.server.dedicated.DedicatedServer.func_71190_q(DedicatedServer.java:396)
    at net.minecraft.server.MinecraftServer.func_71217_p(MinecraftServer.java:666)
    at net.minecraft.server.MinecraftServer.run(MinecraftServer.java:524)
    at java.lang.Thread.run(Thread.java:748)

EcoMod version: 1.12.2 - 1.4.1.0

pupnewfster commented 6 years ago

Another pointer actually points to ecomod.asm.EcomodASMHooks.itemEntityItemUpdateAddition(EcomodASMHooks.java:341)

Which then also points to the hasSurfaceAccess method.

kabachuha commented 6 years ago

@pupnewfster, thank you for the work you've done. This function both has a high performance cost and is enough frequent used, so I will consider implementing the algorithm in the next version.

What about your proposal, I'll gladly accept any help towards the mod development.

pupnewfster commented 6 years ago

Ok. In fact when you are looping over

for(EnumFacing facing : EnumFacing.HORIZONTALS)

you probably also want to check to see if b is in was_at

pupnewfster commented 6 years ago

I am working on a pull request that should improve how the method works. (I noticed a couple errors with how I suggested doing it as I was writing it from outside a compiler). I am also looking at other locations where things may be calculated more times than required.

I will also see about performance differences between just using the list of BlockPos and my suggested way of changing to a HashMap.

kabachuha / MinecraftEcologyMod

hasSurfaceAccess calculation lag #24