From b328a8b8128b20de5aca908ae74ee5711cb0d2d1 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Wed, 2 Dec 2020 08:58:55 +0100 Subject: [PATCH 1/1] Add parent refcount cache The idea here is that we check with references towards root quite often. Since we have a one-byte gap in StatementContextBase, we can use it to track knowledge of what parent refs look like -- and side-step a lot of pointer chasing on our way to root. JIRA: YANGTOOLS-1184 Change-Id: I6342292d8f6675ef446dca8410bb859e2d6f230c Signed-off-by: Robert Varga --- .../reactor/AbstractResumedStatement.java | 6 + .../reactor/InferredStatementContext.java | 8 ++ .../parser/stmt/reactor/ReactorStmtCtx.java | 103 +++++++++++++----- .../stmt/reactor/ReplicaStatementContext.java | 5 + 4 files changed, 97 insertions(+), 25 deletions(-) diff --git a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/AbstractResumedStatement.java b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/AbstractResumedStatement.java index 646ea11218..b83df70b53 100644 --- a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/AbstractResumedStatement.java +++ b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/AbstractResumedStatement.java @@ -206,6 +206,12 @@ abstract class AbstractResumedStatement, E ext return effective.stream(); } + @Override + final void markNoParentRef() { + markNoParentRef(substatements); + markNoParentRef(effective); + } + @Override final int sweepSubstatements() { // First we need to sweep all statements, which may trigger sweeps all across the place, for example: diff --git a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/InferredStatementContext.java b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/InferredStatementContext.java index c355148b60..0119c6bc32 100644 --- a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/InferredStatementContext.java +++ b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/InferredStatementContext.java @@ -294,6 +294,14 @@ final class InferredStatementContext, E extend verify(substatements != SWEPT_SUBSTATEMENTS, "Attempted to access substatements of %s", this); } + @Override + void markNoParentRef() { + final Object local = substatements; + if (local != null) { + markNoParentRef(castEffective(local)); + } + } + @Override int sweepSubstatements() { final Object local = substatements; diff --git a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReactorStmtCtx.java b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReactorStmtCtx.java index 0ce875db9e..adca75ce7d 100644 --- a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReactorStmtCtx.java +++ b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReactorStmtCtx.java @@ -545,6 +545,16 @@ abstract class ReactorStmtCtx, E extends Effec // // + /** + * Local knowledge of {@link #refcount} values up to statement root. We use this field to prevent recursive lookups + * in {@link #noParentRefs(StatementContextBase)} -- once we discover a parent reference once, we keep that + * knowledge and update it when {@link #sweep()} is invoked. + */ + private byte parentRef = PARENTREF_UNKNOWN; + private static final byte PARENTREF_UNKNOWN = -1; + private static final byte PARENTREF_ABSENT = 0; + private static final byte PARENTREF_PRESENT = 1; + /** * Acquire a reference on this context. As long as there is at least one reference outstanding, * {@link #buildEffective()} will not result in {@link #effectiveSubstatements()} being discarded. @@ -582,28 +592,60 @@ abstract class ReactorStmtCtx, E extends Effec refcount = current - 1; LOG.trace("Refcount {} on {}", refcount, this); - if (isSweepable()) { + + if (refcount == REFCOUNT_NONE) { + lastDecRef(); + } + } + + private void lastDecRef() { + if (noImplictRef()) { // We are no longer guarded by effective instance sweepOnDecrement(); + return; + } + + final byte prevRefs = parentRef; + if (prevRefs == PARENTREF_ABSENT) { + // We are the last reference towards root, any children who observed PARENTREF_PRESENT from us need to be + // updated + markNoParentRef(); + } else if (prevRefs == PARENTREF_UNKNOWN) { + // Noone observed our parentRef, just update it + loadParentRefcount(); } } - /** - * Sweep this statement context as a result of {@link #sweepSubstatements()}, i.e. when parent is also being swept. - */ - private void sweep() { - if (isSweepable()) { - LOG.trace("Releasing {}", this); - sweepState(); + static final void markNoParentRef(final Collection> substatements) { + for (ReactorStmtCtx stmt : substatements) { + final byte prevRef = stmt.parentRef; + stmt.parentRef = PARENTREF_ABSENT; + if (prevRef == PARENTREF_PRESENT && stmt.refcount == REFCOUNT_NONE) { + // Child thinks it is pinned down, update its perspective + stmt.markNoParentRef(); + } } } + abstract void markNoParentRef(); + static final void sweep(final Collection> substatements) { for (ReactorStmtCtx stmt : substatements) { stmt.sweep(); } } + /** + * Sweep this statement context as a result of {@link #sweepSubstatements()}, i.e. when parent is also being swept. + */ + private void sweep() { + parentRef = PARENTREF_ABSENT; + if (refcount == REFCOUNT_NONE && noImplictRef()) { + LOG.trace("Releasing {}", this); + sweepState(); + } + } + static final int countUnswept(final Collection> substatements) { int result = 0; for (ReactorStmtCtx stmt : substatements) { @@ -629,7 +671,7 @@ abstract class ReactorStmtCtx, E extends Effec // Called when this statement does not have an implicit reference and have reached REFCOUNT_NONE private void sweepOnDecrement() { LOG.trace("Sweeping on decrement {}", this); - if (noParentRefcount()) { + if (noParentRef()) { // No further parent references, sweep our state. sweepState(); } @@ -657,7 +699,7 @@ abstract class ReactorStmtCtx, E extends Effec } // parent is potentially reclaimable - if (noParentRefcount()) { + if (noParentRef()) { LOG.trace("Cleanup {} of parent {}", refcount, this); if (sweepState()) { final ReactorStmtCtx parent = getParentContext(); @@ -672,29 +714,40 @@ abstract class ReactorStmtCtx, E extends Effec return effectiveInstance != null || !isSupportedToBuildEffective(); } - // FIXME: cache the resolution of this - private boolean noParentRefcount() { + private boolean noParentRef() { + return parentRefcount() == PARENTREF_ABSENT; + } + + private byte parentRefcount() { + final byte refs; + return (refs = parentRef) != PARENTREF_UNKNOWN ? refs : loadParentRefcount(); + } + + private byte loadParentRefcount() { + return parentRef = calculateParentRefcount(); + } + + private byte calculateParentRefcount() { final ReactorStmtCtx parent = getParentContext(); - if (parent != null) { - // There are three possibilities: - // - REFCOUNT_NONE, in which case we need to search next parent - // - negative (< REFCOUNT_NONE), meaning parent is in some stage of sweeping, hence it does not have - // a reference to us - // - positive (> REFCOUNT_NONE), meaning parent has an explicit refcount which is holding us down - final int refs = parent.refcount; - return refs == REFCOUNT_NONE ? parent.noParentRefcount() : refs < REFCOUNT_NONE; + if (parent == null) { + return PARENTREF_ABSENT; + } + // There are three possibilities: + // - REFCOUNT_NONE, in which case we need to search next parent + // - negative (< REFCOUNT_NONE), meaning parent is in some stage of sweeping, hence it does not have + // a reference to us + // - positive (> REFCOUNT_NONE), meaning parent has an explicit refcount which is holding us down + final int refs = parent.refcount; + if (refs == REFCOUNT_NONE) { + return parent.parentRefcount(); } - return true; + return refs < REFCOUNT_NONE ? PARENTREF_ABSENT : PARENTREF_PRESENT; } private boolean isAwaitingChildren() { return refcount > REFCOUNT_SWEEPING && refcount < REFCOUNT_NONE; } - private boolean isSweepable() { - return refcount == REFCOUNT_NONE && noImplictRef(); - } - private void sweepOnChildDone() { LOG.trace("Sweeping on child done {}", this); final int current = refcount; diff --git a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReplicaStatementContext.java b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReplicaStatementContext.java index 173e9315ba..199416dcf2 100644 --- a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReplicaStatementContext.java +++ b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReplicaStatementContext.java @@ -117,6 +117,11 @@ final class ReplicaStatementContext, E extends return source.definition(); } + @Override + void markNoParentRef() { + // No-op + } + @Override int sweepSubstatements() { if (fullyDefined()) { -- 2.36.6