The bug

When there are extreme numbers of block entities (even non-ticking) a lot of time can be spent unloading them from a list in the world. This happens when you have a huge number of block entities and leave the area.

How to reproduce

1. Create a new superflat world and /tp 0 ~ 0
2. Create a lot of block entities spread over a few chunks: /fill 0 ~ 0 100 ~2 100 minecraft:furnace
3. Fly away, witness huge lag spikes when block entities begin to be unloaded

Sampling results looks like this: list.png

Code analysis (using MCP names)

Several fields in World.java use List methods with very bad time complexity.

These fields are using add, remove, removeAll, and iterators:

net.minecraft.world.World#loadedTileEntityList
net.minecraft.world.World#tickableTileEntities

After replacing those two Lists with Set, there is no lag spike and the sampling results look much better: set.png

After discussing this with others, we think the best solution is to break up these lists so they are indexed by chunk.
That way, an unloaded chunk can just drop its ticking list and there is no slow remove on a giant list.
It could also make finding nearby entities more efficient.