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#setnet.minecraft.commands.arguments.NbtPathArgument#insertnet.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 |
|---|---|---|---|---|
| 25 | 758.901189 | ± 15.948235 | ns/op |
| 25 | 747.289191 | ± 13.055334 | ns/op |
| 25 | 734.006977 | ± 15.747783 | ns/op |
Results in 1.19.3 Pre-release 3
Benchmark | Count | Score | Error | Unit |
|---|---|---|---|---|
| 25 | 778.666580 | ± 7.356554 | ns/op |
| 25 | 6616.585742 | ± 320.822705 | ns/op |
| 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.
Comments 3
Here is a repo from last year advent of code : oac2021
90% of the solutions are obsolete now because it often involves inputs of around 10k characters. Input are not included in the repo because they are automatically generated, but here is how one input would look like : gist
In the pre-3, that command fail.
I cannot test the impact on speed because size is the main issue there.
There is a data structure/algorithm called list-mapped trie, which is briefly explained in my blog post. A list-mapped trie can be efficiently indexed by an integer (score or NBT) in O(log²N) time, where N is the max size of the structure. If this ticket is not fixed, the time complexity will drop to O(NlogN), which is impractical for large N.
Based on that data structure, there is a library datapack called OhMyDat, which provides per-entity storage and garbage collector. This library uses a large list mapped-trie with size 4⁸ (arity=4, depth=8), and there will be a tangible performance impact.
As far as I know, two major skyblocks in Japan, The Unusual SkyBlock and The Sky Blessing, both depend on that library. These maps will also be affected by this performance degradation. (Although not directly related to this ticket, this library does not work correctly with 1.19.3 pre-3 due to the size limitation.)
I can provide these benchmark results if needed.
Is there a real-world impact, or example of a creation, that is impacted by this? Thanks.