Significant Performance Issue in TreeCutter.findTree for Large / Connected Trees

[KhloeLeclair]

Description

Within the findTree method, specifically on lines 153 and 171, the following line of code is present:

if (!logs.contains(currentPos) && !visited.add(currentPos))

I hope drawing attention to it is enough to prove my point, but as logs is an ArrayList and visited is a HashSet you're effectively guarding an O(1) check behind an O(n) check rather than doing the opposite. For a moderately sized tree farm, this can cause incredibly long execution times in this method and lead a server to hang. On the server I play on, this specific issue has caused the server to hang long enough for a health watchdog to forcibly restart it no less than three times in the past week.

I can reproduce this behavior by creating a fresh instance of Minecraft 1.21.1 with Neoforge 21.1.209, installing only Create 6.0.6, and building a sufficiently large plot of mangrove trees before attempting to harvest them with a contraption using saws.

Game Log

https://mclo.gs/3YOIezn

Debug Information

Client Info

Create:
	Mod Version: 6.0.6
	Mod Git Commit: 20ad05b5e525166018d21e88c96986f867c7088f
	Ponder Version: 1.0.56
	NeoForge Version: 21.1.209
	Minecraft Version: 1.21.1

Graphics:
	Flywheel Version: 1.0.4
	Flywheel Backend: flywheel:indirect
	OpenGL Renderer: NVIDIA GeForce RTX 3090/PCIe/SSE2
	OpenGL Version: 4.6.0 NVIDIA 566.36
	Graphics Mode: fancy
	PojavLauncher Detected: false

System Information:
	Operating System: Windows 10 (amd64) version 10.0
	Java Version: 21.0.7, Microsoft
	JVM Flags: 3 total; -XX:HeapDumpPath=MojangTricksIntelDriversForPerformance_javaw.exe_minecraft.exe.heapdump -Xms512m -Xmx4096m
	Memory: 151527264 bytes (144 MiB) / 1514143744 bytes (1444 MiB) up to 4294967296 bytes (4096 MiB)
	Total Memory: 1366418504 bytes (1303 MiB) / 1514143744 bytes (1444 MiB)
	CPU: AMD Ryzen 7 9700X 8-Core Processor @ 3.79 GHz; 8 cores / 16 threads on 1 socket(s)
	Graphics cards: none

Other Mods:

Server Info

Create:
	Mod Version: 6.0.6
	Mod Git Commit: 20ad05b5e525166018d21e88c96986f867c7088f
	Ponder Version: 1.0.56
	NeoForge Version: 21.1.209
	Minecraft Version: 1.21.1

System Information:
	Operating System: Windows 10 (amd64) version 10.0
	Java Version: 21.0.7, Microsoft
	JVM Flags: 3 total; -XX:HeapDumpPath=MojangTricksIntelDriversForPerformance_javaw.exe_minecraft.exe.heapdump -Xms512m -Xmx4096m
	Memory: 151527264 bytes (144 MiB) / 1514143744 bytes (1444 MiB) up to 4294967296 bytes (4096 MiB)
	Total Memory: 1366418504 bytes (1303 MiB) / 1514143744 bytes (1444 MiB)
	CPU: AMD Ryzen 7 9700X 8-Core Processor @ 3.79 GHz; 8 cores / 16 threads on 1 socket(s)
	Graphics cards: none

Other Mods:

[KhloeLeclair]

As an added data point, I was messing around with this in a debugger to see the kind of numbers we're dealing with and got a particularly long hang locally with:

• 17,997 entries in logs
• 139,402 entries in leaves
• 2,668 entries in attachments
• 23,308 entries in visited
• 37,385 entries in frontier

That was with a row of mangrove trees 32 or so blocks long, which is well within the scope of farms I've seen players build.

If the checks for logs.contains() are mandatory, it might be better to just replace logs with a HashSet as well.

[VoidLeech]

There is an open issue for the crash caused by this already in #5785, though the analysis is very welcome. For chorus and vertical plants, the logs list is reversed (but not for trees), so insertion order seems important, though from what I can tell the only place it matters is for a contraption inventory, which takes the HashSet out of the equation, but even switching to a LinkedHashSet over a list already massively helps in my quick test, with the performance bottleneck (there is definitely still a hang) firmly shifting to the actual block breaking.

Aside that, these entry counts are suspect in combination with your reported size of mangrove row as they far exceed the volume of the bounding box (leaves especially): 32 * 17 * 27 = 14688 i.e. what you'd expect if the entire thing was solid, which it obviously isn't; it's split between logs/roots, leaves, attachments, and air still, so that requires further investigation.

[KhloeLeclair]

Ah, sorry. I did a search for tree in issues but I missed that one. Definitely the same issue.

For chorus and vertical plants, maintaining the order definitely makes sense as a block update could cause them to break if you don't harvest in the correct order. That bit could probably be optimized too by initializing logs with a LinkedList for chorus and vertical plants and inserting at position zero the reverse operation could be skipped.

I hadn't been thinking about a LinkedHashSet, but if we need to maintain the insertion order and we need a List at the end, then there could be a HashSet and a List that are both updated for logs, with the HashSet used for presence checks. That would avoid needing another iteration over the entire collection to make a List later.

Also my apologies, the "32 or so blocks long" was specifically for the placement of propagules, the outer bounding box of the mangrove trees in my test extended beyond 32 blocks and there were a couple columns. Even in that case the number of leaves was suspicious, I should probably check again.