Large performance regression in Root.load & loadSync in 7.5.0

[simon-paris]

In 7.5.0, Root.load calls resolveAll. Foreach call to load or loadSync, it will resolve every type, resulting in O(n^2) performance where n is the number of input files.

This is a very large performance regression in workflows that have more than one entry point proto file. In my project, initialization is ~100x slower (from 300ms to 30s).

Additionally, the async version calls resolveAll twice, doubling the performance hit. It appears that one call is meant to happen in the sync version and the other in the async version, but the async version actually runs both calls.

The change was made here: b802c42#diff-45840cbec0137d0498a3dbcf38eba6a358e2b8bfd9f1eca20abdfc7b386d13b1R208

cc @sofisl

[Nushio]

I can confirm. We use Firestore (which uses protobufjs). A commit we made yesterday updated the protobuf library from 7.4.0 to 7.5.0.
The query time jumped from 0.4s to 16 seconds.

[mkruskal-google]

resolveAll is supposed to cache results and be efficient to call multiple times, this sounds like a bug. I'll investigate

[sofisl]

Are you calling .resolveAll() in your code?

[sofisl]

Moving 7.4.0 to latest while this gets resolved.

[mkruskal-google]

ok so there are a few problems here:

1. resolveAll doesn't cache most of the work it does. It only caches it for the root object, which seems to have been a pre-existing regression we made worse
2. feature resolution is required for correctness, and needs to know about the presence of groups (which naively uses resolved type info)
3. we added a bunch of new resolveAll calls in order for resolved features to always reliably be available

It's possible to fix 2) to use unresolved type information, and short-circuit this regression. I think resolveAll could still probably be optimized to cache state better, but if we just don't call it in the new locations it won't make things any worse. I have some benchmarks showing a 400-600x speedup for some really worst-case scenarios.

[mkruskal-google]

@simon-paris @Nushio could either of you test against 8.1.0-experimental to confirm this resolves your issues? There's a remote possibility further optimizations are needed, but I think this will fix the bulk of the problem. There's still some O(n^2) behavior for repeated loads, but it's for a significantly cheaper calculation

[mkruskal-google]

ok so I think another piece of what happened here is we misread the resolve() caching feature and then accidentally broke it in our various iterations. This commit restores the old behavior and according to benchmarks fixes all of the regressions from resolveAll itself.

[simon-paris]

@mkruskal-google Looks good. In my use case, it's only about 50% slower than 7.4.

Not sure if possible, but could caching be applied at the namespace level, with invalidation when a new item is added?

Like this maybe?

function closestNamespaceAncestor(ptr) {
    while (true) {
        if (ptr === null) return null;
        if (ptr instanceof Namespace) return ptr;
        ptr = ptr.parent;
    }
}

ReflectionObject.prototype.onAdd = function onAdd(parent) {
    // .....
    closestNamespaceAncestor(parent)?.__featuresResolvedRecursively = false;
};

Namespace.prototype._resolveFeaturesRecursive = function _resolveFeaturesRecursive(edition) {
    if (this._featuresResolvedRecursively) return this;
    this.__featuresResolvedRecursively = true;
    // ....
};

[mkruskal-google]

Yea it could be (and I considered that), it's just a more invasive change. This PR has already spiraled a bit though, so I might as well add that now lol.

Note: the latest commit also adds a fresh optimization to resolveAll that makes it even faster than before

[mkruskal-google]

Adding that optimization shows significant gains in my benchmark on repeated loads, showing that even with per-object caching the O(n^2) behavior from having to walk through the tree was non-negligible.

[mkruskal-google]

@simon-paris Can you try again with 8.1.2-experimental?

[simon-paris]

Looking good. Pretty much the same performance as before. Thanks!