Namespace `lookup` performance far worse than O(N)

[raycohen]

trafficstars

In the Namespace lookup method, when the initial get call fails to find something, we hit what I'd call the unhappy search path.

This unhappy path begins by recursing deeper into the Namespace graph, with a special parentAlreadyChecked param set to true so that part of the search won't also recurse outward from the current Namespace (avoiding an infinite loop).

However, if that deeper recursion also fails to find anything, the code steps outward to the parent Namespace, and then when it recurses deeper again it doesn't exclude the child Namespace we just checked. And that repeats for each parent Namespace we have to visit before something is finally found.

My app was hitting this because we were generating a JSON schema with every type field set to an absolute path, and not taking advantage of the fact that a leading period in the type field will force a lookup from the root, something I didn't see mentioned in any documentation.

It seems like it would be nice to at least make sure lookup visits a given Namespace at most once, which would probably give a small perf improvement even to a more typical user.

[mkruskal-google]

I'm not going to mark this issue fixed, but I happened to hit this issue while trying to optimize resolveAll and took a first (minimal) pass at it. Some basic refactoring and caching showed substantial improvements in performance! Basically what I did was I stored a cache of every path hit at or below each namespace (and invalidate it whenever anything changes in that scope). That speeds up repeated calls, and notably avoids all of the double work when the parents recurse back down into their children that have already been searched

[raycohen]

in https://github.com/protobufjs/protobuf.js/pull/2068 the change to read object.fullName in _handleAdd seems to be showing as quite expensive for my app: