Using '/locate buried_treasure' or opening a chest in a shipwreck containing a buried treasure map can cause extreme TPS lag

History of bug

This issue was actually in the game before, from 1.13-1.16.5, but from some version between the first snapshot after 1.16.5 and 1.17 it was fixed. This fix is now broken since snapshot 21w37a. Previous reports of this bug (I initially found MC-190896 when encountering this bug) have been merged to MC-126244, which is a more general bug report encompassing the /locate command in general, not specifically concerning the loading of buried treasures, which is a different issue entirely (and one I have understood quite well through trial and error). 

Description

This is the bug itself: when attempting to locate a buried treasure (through either using the command or opening the chest), if you are ~800 meters or further away from it, there becomes a noticeable amount of TPS lag, and at around ~1000 meters away (which is rare but still quite possible in survival) TPS lag gets pretty high, as I'll show in recreating the bug.

Recreating the bug

I quickly found two seeds in both 1.16.4-1.17 where the locate command at the spawnpoint was sufficiently laggy enough to submit this report, and another seed that took ~10 attempts to find whose nearest shipwreck had a chest whose buried treasure map created 20 seconds of lag when you clicked on it.  

1.16.4-1.17 seed: -4446634296935719090 

          /locate buried_treasure at spawn: 1,071 meters away, 24s of TPS lag

21w37+ seed: 3109386031526602481

         /locate buried_treasure at spawn: 1425 meters away, 64s of TPS lag

21w37+ seed with survival implications: 8125943311898213873

          /locate shipwreck }}at spawn then click on chest with map: 780 meters away, 20s of TPS lag

Found another seed like this last one: -8232471837154039731 

         /locate shipwreck at spawn then click on chest with map: 818 meters away, 11s of TPS lag (which could be compared with the last seed to consider more factors at play rather than just distance being the only major factor in creating the lag)

If there is a shipwreck wherein the chest containing the map is ~ over 900 blocks away from the nearest buried treasure, the method currently used to search for the buried treasure to make a map from is terminated and the map is replaced with an empty map.

I'd estimate the average distance from any shipwreck with a map chest to the nearest buried treasure is (very roughly) 600 meters in 21w40a.  This means for each chest opened there'd be around several seconds of TPS lag. In general, I believe the lag created scales not linearly but exponentially with the distance between the two locations: the chest (or the player when the chest is opened) and the buried treasure, or the player and the buried treasure (with the /locate command).  

How this works

I don't think there is much I can offer as someone who can't do any code analysis but it seems that the current method the game uses to find the nearest buried treasure (from a shipwreck chest with a buried treasure map in it) is not optimized to say the least, and in 1.17 this method was changed to a far more efficient version. There is always the issue of adding new features re-adding bugs and this is I believe a case of that (especially since both 1.18 snapshot changes and buried treasure location picking are rooted in terrain generation).