[MC-258195] Performance degradation of NBT modification

The bug

Due to the fix of ~~MC-201769~~, the depth and size of the resulting NBT is now estimated before NBT modification by calculating the depths and sizes of target and source NBTs. If the estimated depth is too deep (> 512) or the estimated size is too large (> 2097152 bits or bytes?), the exception ERROR_DATA_TOO_DEEP or ERROR_DATA_TOO_LARGE will be thrown respectively.

However, this approach comes at a cost. Since the calculation of NBT depth/size is recursive down to the leaf NBTs, the time complexity of the NBT modification is now proportional to the sum of the deep size of the target and source NBTs. This makes NBT modification too
inefficient.

Code analysis

See:

net.minecraft.commands.arguments.NbtPathArgument#set
net.minecraft.commands.arguments.NbtPathArgument#insert
net.minecraft.nbt.Tag#sizeInBits

Benchmark

Using my benchmark harness, the following functions are benchmarked in 1.19.3 Pre-release 2 and 1.19.3 Pre-release 3 respectively. These functions repeatedly append and remove 0 to the list tag with different elements. Note that resizing the internal ArrayList does not affect the benchmark results because if resizing happens, it is done only once during the warmup phase and never during the measurement phase.

small.mcfunction

# `0 0` is an empty list tag
data modify storage 0 0 append value 0
data remove storage 0 0[-1]

medium.mcfunction

# `2 0` is a list tag of length 8180, filled with 0
data modify storage 2 0 append value 0
data remove storage 2 0[-1]

large.mcfunction

# `1 0` is a list tag of length 16360, filled with 0
data modify storage 1 0 append value 0
data remove storage 1 0[-1]

Results in 1.19.3 Pre-release 2

Benchmark	Count	Score	Error	Unit
`small`	25	758.901189	± 15.948235	ns/op
`medium`	25	747.289191	± 13.055334	ns/op
`large`	25	734.006977	± 15.747783	ns/op

Results in 1.19.3 Pre-release 3

Benchmark	Count	Score	Error	Unit
`small`	25	778.666580	± 7.356554	ns/op
`medium`	25	6616.585742	± 320.822705	ns/op
`large`	25	12798.060863	± 48.623119	ns/op

As the results suggest, in 1.19.3 Pre-release 2, we could append an element to a list tag in constant time, no matter how many elements it had. On the other hand, in 1.19.3 Pre-release 3, the larger the target NBT size, the linearly worse the performance of the NBT modification. We can no longer append an element to a list tag in a storage in constant time.
In general, the larger the entire size of the storage to be modified, the higher the cost of modifying the NBTs in that storage.