zly2006 / Enclosure

A server-side minecraft mod that allows players to protect their homes.
https://enclosure.fandom.com/wiki/Enclosure_Wiki
Other
16 stars 6 forks source link

perf: improve performance of getSmallestEnclosure #41

Closed wafarm closed 3 months ago

wafarm commented 3 months ago

Motivation

image Though not on every tick, still a significant impact on MSPT.

Benchmark

Look up 1,000,000 random positions with enclosures data in our 1.21 server.

Code:

dispatcher.register(
    CommandManager.literal("bench")
        .executes {
            val posList: MutableList<BlockPos> = ArrayList(1000000)
            val random = Random()
            for (i in 1..1000000) {
                val x = random.nextInt(-1000, 1001)
                val z = random.nextInt(-1000, 1001)
                val y = random.nextInt(-10, 101)
                posList.add(BlockPos(x, y, z))
            }

            val time = measureTimeMillis {
                for (pos in posList) {
                    getSmallestEnclosure(it.source.world, pos)
                }
            }

            it.source.sendMessage(Text.literal("Time elapsed: $time ms"))
            1
        }
)

Result (10 tests each):

before          (ms): 666 650 650 628 628 627 656 642 649 659
after(w/ locks) (ms): 388 398 388 321 364 408 336 357 364 333
after(w/o locks)(ms): 151 125 138 136 137 145 131 132 132 135

Changes

HashMap.values iterations is slow so used a list to cache the areas

Also removed the lockChecker for coordinates as it is not used. Possible reason: https://stackoverflow.com/questions/39152264/kotlin-how-can-i-avoid-autoboxing-garbage-in-delegated-properties but I can't fix the problem with the code in the link

zly2006 commented 3 months ago

HashMap.values iterations is slow so used a list to cache the areas

How about to use LinkedHashMap?

wafarm commented 3 months ago

How about to use LinkedHashMap?

About 40ms slower than current implementation. If you want I will change to that.

zly2006 commented 3 months ago

Also I didn't consider too much when designing this data structure. The best way might be save all interacting areas in a chunk

zly2006 commented 3 months ago

OK I am going to implement a lookup based on chunks. Thanks so much for figuring out this performance issue.

zly2006 commented 3 months ago

May I close this PR since #42 has been merged?