On Fri, Feb 10, 2023 at 3:38 AM Andrew MacLeod <amacl...@redhat.com> wrote: > > > The change for 108356 allowed the cache to scan the dominator trees when > it was attempting a lookup rather than using the local value. I > inadvertantly changed the external interface to also do this, so all the > GORI queries via range_on_edge of the cache could also do lookups in > this mode. > > This triggered a quadratic, possible exponential time increase when the > right conditions were presented. That being a cascading series of > recomputations on outgoing edge calculations that at then searched the > dom tree instead of being a simple calculation using whats easily available. > > The fix is to use the internal API within the cache rather than the > extrenal one that GORI uses. This leaves GORI computations to be > resolved in linear time. GORI is designed to only use what immediately > available and should never trigger new lookups of its own. Doh. > > This may possibly fix a a few other new large time growth issues in DOM > and friends, such as 108705. > > bootstrapped on x86_64-pc-linux-gnu, regtesting ongoing.. assuming no > issues, OK for trunk?
OK. Thanks, Richard. > Andrew
