Lag when trading with villager

[mvez73]

Timings or Profile link:

We ask that all timings/profiles are a link, not a screenshot. Screenshots inhibit our ability to figure out the real cause of the issue.
https://spark.lucko.me/#kG0ynD014n
https://timings.aikar.co/?id=2ff0defeecb24960a5eed9d948a97171

Description of issue:

Big lags when trading with villager (cartographer)
I had a discussion with Techcable in the general chan of Discord

Plugin list:

All plugins running on the server
AdvancedAchievements, AdvancedNMotd*, ajParkour, AnvilColor, AuthMe, BeastWithdraw, BeautyQuests, BetterSleeping3, CasinoPlugin, ChatManager, ChestShop, Citizens, CitizensCMD, CitizensText, CommandButtons, CrazyCrates, CustomWings, DeluxeMenus, Duels, DurabilityAlert, eBackup, EconomyShopGUI, Elevators, Essentials, EssentialsSpawn, EzLottery, GriefPrevention, HolographicDisplays, HorseOverhaul, Jobs, LuckPerms, Minepacks, MobHunting, Multiverse-Core, PlaceholderAPI, PlayerKits, PluginManager*, Poop, ProtocolLib, RandomTeleport, Sickle, SimpleRename, SkinsRestorer, SortingHopper2, spark, SuperBet, SystemInfo, TempFly, TradeSystem, UltimateCatcher, UltimateFishing, UltimateMachine*, UltraRepair, Vault, VillagerOptimiser, VoidGenerator, WorldEdit, WorldEditSelectionVisualizer, WorldGuard, WorldGuardExtraFlags

bukkit.yml, spigot.yml, paper.yml, server.properties

Gist/pastebin/hastebin links

Other helpful links

The more information we receive, the quicker and more effective we can be at finding the solution to the
issue.

Paper build number:

This can be found by running /version on your server. latest is not a proper version number; we require the output of /version so we can properly track down the issue.
This server is running Paper version git-Paper-347 (MC: 1.15.2) (Implementing API version 1.15.2-R0.1-SNAPSHOT)

[Techcable]

Based on the spark profile, it appears the lag is caused by EntityVillager.populateTrades() calling ItemWorldMap.applySepiaFilter().

I had a discussion about this with @Phoenix616 in the #general channel of Discord.
As far as I can tell, the "sepia filter" method is just there to shade in ItemWorldMap.colors.
This calls out to WordServer.getBiomeBySeed which triggers some sort of weird recursive generation (essentially making this quadratic behavior). Then the generated biome information is used to color in the villager's map.

We could just precompute the biomes based on whatever chunks happen to be loaded at the time. That information can be accessed with a relatively cheap chunk lookup instead of recursively generating biome generation each time. This will be entirely correct for the loaded chunks. As a downside, the generated maps will have missing information for unloaded chunks.

As an alternative, we could compute all this information async and send it back to the main thread. It appears (at first glance) that this biome generation code is a pure function of the world seed. From the few classes I've looked at there doesn't seem to be any actual world access - just recursive requests for more biome information.

[aikar]

That's quite the opposite @Techcable, we just recently made it do this to avoid chunk lookups because chunk lookups kill the server (because it has to run that same code anyways)

There's possibility thread contention at risk here as thats the main problem with that code is it synchronizes and blocks a lot, so can't even parallelize that either (not that it would do any good since the operation is blocking)

It's likely you had world generation occurring at same time and caused a lot of lock contention.
benefit may be to see if we can reduce that contention on AreaLazy

[Techcable]

The server owner did in fact have world generation going on at the same time.

Avoiding contention in AreaLazy isn't going to be as simple as a ConcurrentHashMap. I was assuming that if multiple threads to optimistically called an ArenaTrasnformer at the same time than they'd return the same results. That does not appear to be the case. I don't see any internal state in the couple of AreaTransformers that I've looked at but it could be hidden.

Deadlocks have been an issue with a couple of the modifications I've tried. Apparently computing the biomes triggered some sort of internal locking.

We must go deeper!!!!

[Proximyst]

Marking as duplicate of #2312. I've added the PR closing this issue as a closing for the other issue.