Other relevant bazel discussions in bazelbuild/bazel#20862 and bazelbuild/bazel#18686

Confirmed that buck2 has similar poor performance here: https://github.com/cjhopman/repro-bazel-nested-set

buck1 approach is potentially more performant here. It maintains an map of tsetnode equivalent -> interned MerkleTreeNode. and then a MerkleTreeNode lazily computes and caches its encoded form only when requested. see https://github.com/facebook/buck/blob/9c7c421e49f4d92d67321f18c6d1cd90974c77c4/src/com/facebook/buck/remoteexecution/util/MerkleTreeNodeCache.java and https://github.com/facebook/buck/blob/9c7c421e49f4d92d67321f18c6d1cd90974c77c4/src/com/facebook/buck/rules/modern/builders/ModernBuildRuleRemoteExecutionHelper.java#L531

That model doesn't fit great into buck and there's a question of the cost of interning. But actually I think it could be fine to just depend on sharing based on the dice value cached for the tset already for the interning part of that.

but still, it might just be too costly to do all the tree merges themselves.

if this is something like a flat directory of items, and each item is a value in one tset and then there's a densish graph between them, producing the merged directories is going to be O(n^2). lazily doing the fingerprinting just improves the constant.