Mozilla bug 1355441 - Reuse StackNode in TreeBuilder to avoid malloc. r=hsivonen
☠☠ backed out by eaa22b86f110 ☠ ☠
authorWilliam Chen <wchen@mozilla.com>
Mon, 01 May 2017 11:51:35 -0700
changeset 841 a944675b2b4ba9b7b20e312c0d11be2c06c52aca
parent 840 d3a1d8fdc4127726709fe9290b755258841b7711
child 842 eaa22b86f11067d8b1fccf2123565f4053bdba78
push id167
push userwchen@mozilla.com
push dateMon, 08 May 2017 21:27:14 +0000
reviewershsivonen
bugs1355441
Mozilla bug 1355441 - Reuse StackNode in TreeBuilder to avoid malloc. r=hsivonen
src/nu/validator/htmlparser/impl/StackNode.java
src/nu/validator/htmlparser/impl/StateSnapshot.java
src/nu/validator/htmlparser/impl/TreeBuilder.java
--- a/src/nu/validator/htmlparser/impl/StackNode.java
+++ b/src/nu/validator/htmlparser/impl/StackNode.java
@@ -23,34 +23,37 @@
 
 package nu.validator.htmlparser.impl;
 
 import nu.validator.htmlparser.annotation.Inline;
 import nu.validator.htmlparser.annotation.Local;
 import nu.validator.htmlparser.annotation.NsUri;
 
 final class StackNode<T> {
-    final int flags;
+    // Index where this stack node is stored in the tree builder's list of stack nodes.
+    final int idxInTreeBuilder;
 
-    final @Local String name;
+    int flags;
 
-    final @Local String popName;
+    @Local String name;
+
+    @Local String popName;
 
-    final @NsUri String ns;
+    @NsUri String ns;
 
-    final T node;
+    T node;
 
     // Only used on the list of formatting elements
     HtmlAttributes attributes;
 
-    private int refcount = 1;
+    private int refcount = 0;
 
     // [NOCPP[
 
-    private final TaintableLocatorImpl locator;
+    private TaintableLocatorImpl locator;
 
     public TaintableLocatorImpl getLocator() {
         return locator;
     }
 
     // ]NOCPP]
 
     @Inline public int getFlags() {
@@ -80,34 +83,40 @@ final class StackNode<T> {
     // [NOCPP[
 
     public boolean isOptionalEndTag() {
         return (flags & ElementName.OPTIONAL_END_TAG) != 0;
     }
 
     // ]NOCPP]
 
+    StackNode(int idxInTreeBuilder) {
+        this.idxInTreeBuilder = idxInTreeBuilder;
+        this.refcount = 0;
+    }
+
     /**
-     * Constructor for copying. This doesn't take another <code>StackNode</code>
-     * because in C++ the caller is reponsible for reobtaining the local names
+     * Setter for copying. This doesn't take another <code>StackNode</code>
+     * because in C++ the caller is responsible for reobtaining the local names
      * from another interner.
      *
      * @param flags
      * @param ns
      * @param name
      * @param node
      * @param popName
      * @param attributes
      */
-    StackNode(int flags, @NsUri String ns, @Local String name, T node,
+    void setValues(int flags, @NsUri String ns, @Local String name, T node,
             @Local String popName, HtmlAttributes attributes
             // [NOCPP[
             , TaintableLocatorImpl locator
-    // ]NOCPP]
+            // ]NOCPP]
     ) {
+        assert isUnused();
         this.flags = flags;
         this.name = name;
         this.popName = popName;
         this.ns = ns;
         this.node = node;
         this.attributes = attributes;
         this.refcount = 1;
         // [NOCPP[
@@ -116,124 +125,129 @@ final class StackNode<T> {
     }
 
     /**
      * Short hand for well-known HTML elements.
      *
      * @param elementName
      * @param node
      */
-    StackNode(ElementName elementName, T node
-    // [NOCPP[
+    void setValues(ElementName elementName, T node
+            // [NOCPP[
             , TaintableLocatorImpl locator
-    // ]NOCPP]
+            // ]NOCPP]
     ) {
+        assert isUnused();
         this.flags = elementName.getFlags();
         this.name = elementName.getName();
         this.popName = elementName.getName();
         this.ns = "http://www.w3.org/1999/xhtml";
         this.node = node;
         this.attributes = null;
         this.refcount = 1;
         assert elementName.isInterned() : "Don't use this constructor for custom elements.";
         // [NOCPP[
         this.locator = locator;
         // ]NOCPP]
     }
 
     /**
-     * Constructor for HTML formatting elements.
+     * Setter for HTML formatting elements.
      *
      * @param elementName
      * @param node
      * @param attributes
      */
-    StackNode(ElementName elementName, T node, HtmlAttributes attributes
-    // [NOCPP[
+    void setValues(ElementName elementName, T node, HtmlAttributes attributes
+            // [NOCPP[
             , TaintableLocatorImpl locator
-    // ]NOCPP]
+            // ]NOCPP]
     ) {
+        assert isUnused();
         this.flags = elementName.getFlags();
         this.name = elementName.getName();
         this.popName = elementName.getName();
         this.ns = "http://www.w3.org/1999/xhtml";
         this.node = node;
         this.attributes = attributes;
         this.refcount = 1;
         assert elementName.isInterned() : "Don't use this constructor for custom elements.";
         // [NOCPP[
         this.locator = locator;
         // ]NOCPP]
     }
 
     /**
-     * The common-case HTML constructor.
+     * The common-case HTML setter.
      *
      * @param elementName
      * @param node
      * @param popName
      */
-    StackNode(ElementName elementName, T node, @Local String popName
-    // [NOCPP[
+    void setValues(ElementName elementName, T node, @Local String popName
+            // [NOCPP[
             , TaintableLocatorImpl locator
-    // ]NOCPP]
+            // ]NOCPP]
     ) {
+        assert isUnused();
         this.flags = elementName.getFlags();
         this.name = elementName.getName();
         this.popName = popName;
         this.ns = "http://www.w3.org/1999/xhtml";
         this.node = node;
         this.attributes = null;
         this.refcount = 1;
         // [NOCPP[
         this.locator = locator;
         // ]NOCPP]
     }
 
     /**
-     * Constructor for SVG elements. Note that the order of the arguments is
-     * what distinguishes this from the HTML constructor. This is ugly, but
+     * Setter for SVG elements. Note that the order of the arguments is
+     * what distinguishes this from the HTML setter. This is ugly, but
      * AFAICT the least disruptive way to make this work with Java's generics
      * and without unnecessary branches. :-(
      *
      * @param elementName
      * @param popName
      * @param node
      */
-    StackNode(ElementName elementName, @Local String popName, T node
-    // [NOCPP[
+    void setValues(ElementName elementName, @Local String popName, T node
+            // [NOCPP[
             , TaintableLocatorImpl locator
-    // ]NOCPP]
+            // ]NOCPP]
     ) {
+        assert isUnused();
         this.flags = prepareSvgFlags(elementName.getFlags());
         this.name = elementName.getName();
         this.popName = popName;
         this.ns = "http://www.w3.org/2000/svg";
         this.node = node;
         this.attributes = null;
         this.refcount = 1;
         // [NOCPP[
         this.locator = locator;
         // ]NOCPP]
     }
 
     /**
-     * Constructor for MathML.
+     * Setter for MathML.
      *
      * @param elementName
      * @param node
      * @param popName
      * @param markAsIntegrationPoint
      */
-    StackNode(ElementName elementName, T node, @Local String popName,
+    void setValues(ElementName elementName, T node, @Local String popName,
             boolean markAsIntegrationPoint
             // [NOCPP[
             , TaintableLocatorImpl locator
-    // ]NOCPP]
+            // ]NOCPP]
     ) {
+        assert isUnused();
         this.flags = prepareMathFlags(elementName.getFlags(),
                 markAsIntegrationPoint);
         this.name = elementName.getName();
         this.popName = popName;
         this.ns = "http://www.w3.org/1998/Math/MathML";
         this.node = node;
         this.attributes = null;
         this.refcount = 1;
@@ -260,17 +274,17 @@ final class StackNode<T> {
         }
         if (markAsIntegrationPoint) {
             flags |= ElementName.HTML_INTEGRATION_POINT;
         }
         return flags;
     }
 
     @SuppressWarnings("unused") private void destructor() {
-        Portability.delete(attributes);
+        // The translator adds refcount debug code here.
     }
 
     public void dropAttributes() {
         attributes = null;
     }
 
     // [NOCPP[
     /**
@@ -281,15 +295,21 @@ final class StackNode<T> {
     }
 
     // ]NOCPP]
 
     public void retain() {
         refcount++;
     }
 
-    public void release() {
+    public void release(TreeBuilder<T> owningTreeBuilder) {
         refcount--;
+        assert refcount >= 0;
         if (refcount == 0) {
-            Portability.delete(this);
+            Portability.delete(attributes);
+            owningTreeBuilder.notifyUnusedStackNode(idxInTreeBuilder);
         }
     }
+
+    boolean isUnused() {
+        return refcount == 0;
+    }
 }
--- a/src/nu/validator/htmlparser/impl/StateSnapshot.java
+++ b/src/nu/validator/htmlparser/impl/StateSnapshot.java
@@ -22,16 +22,18 @@
 
 package nu.validator.htmlparser.impl;
 
 import nu.validator.htmlparser.annotation.Auto;
 
 
 public class StateSnapshot<T> implements TreeBuilderState<T> {
 
+    private final TreeBuilder<T> treeBuilder;
+
     private final @Auto StackNode<T>[] stack;
 
     private final @Auto StackNode<T>[] listOfActiveFormattingElements;
 
     private final @Auto int[] templateModeStack;
 
     private final T formPointer;
 
@@ -57,20 +59,21 @@ public class StateSnapshot<T> implements
      * @param headPointer
      * @param deepTreeSurrogateParent
      * @param mode
      * @param originalMode
      * @param framesetOk
      * @param needToDropLF
      * @param quirks
      */
-    StateSnapshot(StackNode<T>[] stack,
+    StateSnapshot(TreeBuilder<T> treeBuilder, StackNode<T>[] stack,
             StackNode<T>[] listOfActiveFormattingElements, int[] templateModeStack, T formPointer,
             T headPointer, T deepTreeSurrogateParent, int mode, int originalMode,
             boolean framesetOk, boolean needToDropLF, boolean quirks) {
+        this.treeBuilder = treeBuilder;
         this.stack = stack;
         this.listOfActiveFormattingElements = listOfActiveFormattingElements;
         this.templateModeStack = templateModeStack;
         this.formPointer = formPointer;
         this.headPointer = headPointer;
         this.deepTreeSurrogateParent = deepTreeSurrogateParent;
         this.mode = mode;
         this.originalMode = originalMode;
@@ -188,17 +191,17 @@ public class StateSnapshot<T> implements
      * @see nu.validator.htmlparser.impl.TreeBuilderState#getTemplateModeStackLength()
      */
     public int getTemplateModeStackLength() {
         return templateModeStack.length;
     }
 
     @SuppressWarnings("unused") private void destructor() {
         for (int i = 0; i < stack.length; i++) {
-            stack[i].release();
+            stack[i].release(treeBuilder);
         }
         for (int i = 0; i < listOfActiveFormattingElements.length; i++) {
             if (listOfActiveFormattingElements[i] != null) {
-                listOfActiveFormattingElements[i].release();                
+                listOfActiveFormattingElements[i].release(treeBuilder);
             }
         }
     }
 }
--- a/src/nu/validator/htmlparser/impl/TreeBuilder.java
+++ b/src/nu/validator/htmlparser/impl/TreeBuilder.java
@@ -420,16 +420,25 @@ public abstract class TreeBuilder<T> imp
      */
     private @Auto int[] templateModeStack;
 
     /**
      * Current template mode stack pointer.
      */
     private int templateModePtr = -1;
 
+    private @Auto StackNode<T>[] stackNodes;
+
+    /**
+     * Index of the earliest possible unused or empty element in stackNodes.
+     */
+    private int stackNodesIdx = -1;
+
+    private int numStackNodes = 0;
+
     private @Auto StackNode<T>[] stack;
 
     private int currentPtr = -1;
 
     private @Auto StackNode<T>[] listOfActiveFormattingElements;
 
     private int listPtr = -1;
 
@@ -578,22 +587,25 @@ public abstract class TreeBuilder<T> imp
         SAXParseException spe = new SAXParseException(message, locator);
         errorHandler.warning(spe);
     }
 
     // ]NOCPP]
 
     @SuppressWarnings("unchecked") public final void startTokenization(Tokenizer self) throws SAXException {
         tokenizer = self;
+        stackNodes = new StackNode[64];
         stack = new StackNode[64];
         templateModeStack = new int[64];
         listOfActiveFormattingElements = new StackNode[64];
         needToDropLF = false;
         originalMode = INITIAL;
         templateModePtr = -1;
+        stackNodesIdx = 0;
+        numStackNodes = 0;
         currentPtr = -1;
         listPtr = -1;
         formPointer = null;
         headPointer = null;
         deepTreeSurrogateParent = null;
         // [NOCPP[
         html4 = false;
         idLocations.clear();
@@ -626,17 +638,17 @@ public abstract class TreeBuilder<T> imp
                 ElementName elementName = ElementName.SVG;
                 if ("title" == contextName || "desc" == contextName
                         || "foreignObject" == contextName) {
                     // These elements are all alike and we don't care about
                     // the exact name.
                     elementName = ElementName.FOREIGNOBJECT;
                 }
                 // This is the SVG variant of the StackNode constructor.
-                StackNode<T> node = new StackNode<T>(elementName,
+                StackNode<T> node = createStackNode(elementName,
                         elementName.getCamelCaseName(), elt
                         // [NOCPP[
                         , errorHandler == null ? null
                                 : new TaintableLocatorImpl(tokenizer)
                 // ]NOCPP]
                 );
                 currentPtr++;
                 stack[currentPtr] = node;
@@ -657,32 +669,32 @@ public abstract class TreeBuilder<T> imp
                     elementName = ElementName.ANNOTATION_XML;
                     // Blink does not check the encoding attribute of the
                     // annotation-xml element innerHTML is being set on.
                     // Let's do the same at least until
                     // https://www.w3.org/Bugs/Public/show_bug.cgi?id=26783
                     // is resolved.
                 }
                 // This is the MathML variant of the StackNode constructor.
-                StackNode<T> node = new StackNode<T>(elementName, elt,
+                StackNode<T> node = createStackNode(elementName, elt,
                         elementName.getName(), false
                         // [NOCPP[
                         , errorHandler == null ? null
                                 : new TaintableLocatorImpl(tokenizer)
                 // ]NOCPP]
                 );
                 currentPtr++;
                 stack[currentPtr] = node;
                 tokenizer.setStateAndEndTagExpectation(Tokenizer.DATA,
                         contextName);
                 // The frameset-ok flag is set even though <frameset> never
                 // ends up being allowed as HTML frameset in the fragment case.
                 mode = FRAMESET_OK;
             } else { // html
-                StackNode<T> node = new StackNode<T>(ElementName.HTML, elt
+                StackNode<T> node = createStackNode(ElementName.HTML, elt
                 // [NOCPP[
                         , errorHandler == null ? null
                                 : new TaintableLocatorImpl(tokenizer)
                 // ]NOCPP]
                 );
                 currentPtr++;
                 stack[currentPtr] = node;
                 if ("template" == contextName) {
@@ -715,17 +727,17 @@ public abstract class TreeBuilder<T> imp
         } else {
             mode = INITIAL;
             // If we are viewing XML source, put a foreign element permanently
             // on the stack so that cdataSectionAllowed() returns true.
             // CPPONLY: if (tokenizer.isViewingXmlSource()) {
             // CPPONLY: T elt = createElement("http://www.w3.org/2000/svg",
             // CPPONLY: "svg",
             // CPPONLY: tokenizer.emptyAttributes(), null);
-            // CPPONLY: StackNode<T> node = new StackNode<T>(ElementName.SVG,
+            // CPPONLY: StackNode<T> node = createStackNode(ElementName.SVG,
             // CPPONLY: "svg",
             // CPPONLY: elt);
             // CPPONLY: currentPtr++;
             // CPPONLY: stack[currentPtr] = node;
             // CPPONLY: }
         }
     }
 
@@ -1618,30 +1630,39 @@ public abstract class TreeBuilder<T> imp
      */
     public final void endTokenization() throws SAXException {
         formPointer = null;
         headPointer = null;
         deepTreeSurrogateParent = null;
         templateModeStack = null;
         if (stack != null) {
             while (currentPtr > -1) {
-                stack[currentPtr].release();
+                stack[currentPtr].release(this);
                 currentPtr--;
             }
             stack = null;
         }
         if (listOfActiveFormattingElements != null) {
             while (listPtr > -1) {
                 if (listOfActiveFormattingElements[listPtr] != null) {
-                    listOfActiveFormattingElements[listPtr].release();
+                    listOfActiveFormattingElements[listPtr].release(this);
                 }
                 listPtr--;
             }
             listOfActiveFormattingElements = null;
         }
+        if (stackNodes != null) {
+            for (int i = 0; i < numStackNodes; i++) {
+                assert stackNodes[i].isUnused();
+                Portability.delete(stackNodes[i]);
+            }
+            numStackNodes = 0;
+            stackNodesIdx = 0;
+            stackNodes = null;
+        }
         // [NOCPP[
         idLocations.clear();
         // ]NOCPP]
         charBuffer = null;
         end();
     }
 
     public final void startTag(ElementName elementName,
@@ -2213,17 +2234,17 @@ public abstract class TreeBuilder<T> imp
                                     StackNode<T> activeA = listOfActiveFormattingElements[activeAPos];
                                     activeA.retain();
                                     adoptionAgencyEndTag("a");
                                     removeFromStack(activeA);
                                     activeAPos = findInListOfActiveFormattingElements(activeA);
                                     if (activeAPos != -1) {
                                         removeFromListOfActiveFormattingElements(activeAPos);
                                     }
-                                    activeA.release();
+                                    activeA.release(this);
                                 }
                                 reconstructTheActiveFormattingElements();
                                 appendToCurrentNodeAndPushFormattingElementMayFoster(
                                         elementName,
                                         attributes);
                                 attributes = null; // CPP
                                 break starttagloop;
                             case B_OR_BIG_OR_CODE_OR_EM_OR_I_OR_S_OR_SMALL_OR_STRIKE_OR_STRONG_OR_TT_OR_U:
@@ -4610,32 +4631,32 @@ public abstract class TreeBuilder<T> imp
     }
 
     private void clearTheListOfActiveFormattingElementsUpToTheLastMarker() {
         while (listPtr > -1) {
             if (listOfActiveFormattingElements[listPtr] == null) {
                 --listPtr;
                 return;
             }
-            listOfActiveFormattingElements[listPtr].release();
+            listOfActiveFormattingElements[listPtr].release(this);
             --listPtr;
         }
     }
 
     @Inline private boolean isCurrent(@Local String name) {
         return stack[currentPtr].ns == "http://www.w3.org/1999/xhtml" &&
                 name == stack[currentPtr].name;
     }
 
     private void removeFromStack(int pos) throws SAXException {
         if (currentPtr == pos) {
             pop();
         } else {
             fatal();
-            stack[pos].release();
+            stack[pos].release(this);
             System.arraycopy(stack, pos + 1, stack, pos, currentPtr - pos);
             assert debugOnlyClearLastStackSlot();
             currentPtr--;
         }
     }
 
     private void removeFromStack(StackNode<T> node) throws SAXException {
         if (stack[currentPtr] == node) {
@@ -4645,25 +4666,25 @@ public abstract class TreeBuilder<T> imp
             while (pos >= 0 && stack[pos] != node) {
                 pos--;
             }
             if (pos == -1) {
                 // dead code?
                 return;
             }
             fatal();
-            node.release();
+            node.release(this);
             System.arraycopy(stack, pos + 1, stack, pos, currentPtr - pos);
             currentPtr--;
         }
     }
 
     private void removeFromListOfActiveFormattingElements(int pos) {
         assert listOfActiveFormattingElements[pos] != null;
-        listOfActiveFormattingElements[pos].release();
+        listOfActiveFormattingElements[pos].release(this);
         if (pos == listPtr) {
             assert debugOnlyClearLastListSlot();
             listPtr--;
             return;
         }
         assert pos < listPtr;
         System.arraycopy(listOfActiveFormattingElements, pos + 1,
                 listOfActiveFormattingElements, pos, listPtr - pos);
@@ -4799,28 +4820,28 @@ public abstract class TreeBuilder<T> imp
                 if (nodePos == furthestBlockPos) {
                     bookmark = nodeListPos + 1;
                 }
                 // if (hasChildren(node.node)) { XXX AAA CHANGE
                 assert node == listOfActiveFormattingElements[nodeListPos];
                 assert node == stack[nodePos];
                 T clone = createElement("http://www.w3.org/1999/xhtml",
                         node.name, node.attributes.cloneAttributes(null), commonAncestor.node);
-                StackNode<T> newNode = new StackNode<T>(node.getFlags(), node.ns,
+                StackNode<T> newNode = createStackNode(node.getFlags(), node.ns,
                         node.name, clone, node.popName, node.attributes
                         // [NOCPP[
                         , node.getLocator()
                         // ]NOCPP]
                 ); // creation ownership goes to stack
                 node.dropAttributes(); // adopt ownership to newNode
                 stack[nodePos] = newNode;
                 newNode.retain(); // retain for list
                 listOfActiveFormattingElements[nodeListPos] = newNode;
-                node.release(); // release from stack
-                node.release(); // release from list
+                node.release(this); // release from stack
+                node.release(this); // release from list
                 node = newNode;
                 // } XXX AAA CHANGE
                 detachFromParent(lastNode.node);
                 appendElement(lastNode.node, node.node);
                 lastNode = node;
             }
             if (commonAncestor.isFosterParenting()) {
                 fatal();
@@ -4828,17 +4849,17 @@ public abstract class TreeBuilder<T> imp
                 insertIntoFosterParent(lastNode.node);
             } else {
                 detachFromParent(lastNode.node);
                 appendElement(lastNode.node, commonAncestor.node);
             }
             T clone = createElement("http://www.w3.org/1999/xhtml",
                     formattingElt.name,
                     formattingElt.attributes.cloneAttributes(null), furthestBlock.node);
-            StackNode<T> formattingClone = new StackNode<T>(
+            StackNode<T> formattingClone = createStackNode(
                     formattingElt.getFlags(), formattingElt.ns,
                     formattingElt.name, clone, formattingElt.popName,
                     formattingElt.attributes
                     // [NOCPP[
                     , errorHandler == null ? null : new TaintableLocatorImpl(tokenizer)
                     // ]NOCPP]
             ); // Ownership transfers to stack below
             formattingElt.dropAttributes(); // transfer ownership to
@@ -4971,17 +4992,17 @@ public abstract class TreeBuilder<T> imp
         // ]NOCPP]
         addAttributesToElement(stack[0].node, attributes);
     }
 
     private void pushHeadPointerOntoStack() throws SAXException {
         assert headPointer != null;
         assert mode == AFTER_HEAD;
         fatal();
-        silentPush(new StackNode<T>(ElementName.HEAD, headPointer
+        silentPush(createStackNode(ElementName.HEAD, headPointer
         // [NOCPP[
                 , errorHandler == null ? null : new TaintableLocatorImpl(tokenizer)
         // ]NOCPP]
         ));
     }
 
     /**
      * @throws SAXException
@@ -5018,35 +5039,156 @@ public abstract class TreeBuilder<T> imp
                 clone = createAndInsertFosterParentedElement("http://www.w3.org/1999/xhtml", entry.name,
                         entry.attributes.cloneAttributes(null));
             } else {
                 clone = createElement("http://www.w3.org/1999/xhtml", entry.name,
                         entry.attributes.cloneAttributes(null), currentNode.node);
                 appendElement(clone, currentNode.node);
             }
 
-            StackNode<T> entryClone = new StackNode<T>(entry.getFlags(),
+            StackNode<T> entryClone = createStackNode(entry.getFlags(),
                     entry.ns, entry.name, clone, entry.popName,
                     entry.attributes
                     // [NOCPP[
                     , entry.getLocator()
                     // ]NOCPP]
             );
 
             entry.dropAttributes(); // transfer ownership to entryClone
 
             push(entryClone);
             // stack takes ownership of the local variable
             listOfActiveFormattingElements[entryPos] = entryClone;
             // overwriting the old entry on the list, so release & retain
-            entry.release();
+            entry.release(this);
             entryClone.retain();
         }
     }
 
+    void notifyUnusedStackNode(int idxInStackNodes) {
+        // stackNodesIdx is the earliest possible index of a stack node that might be unused,
+        // so update the index if necessary.
+        if (idxInStackNodes < stackNodesIdx) {
+            stackNodesIdx = idxInStackNodes;
+        }
+    }
+
+    private StackNode<T> getUnusedStackNode() {
+        // Search for an unused stack node.
+        while (stackNodesIdx < numStackNodes) {
+            if (stackNodes[stackNodesIdx].isUnused()) {
+                return stackNodes[stackNodesIdx++];
+            }
+            stackNodesIdx++;
+        }
+
+        if (stackNodesIdx < stackNodes.length) {
+            // No unused stack nodes, but there is still space in the storage array.
+            stackNodes[stackNodesIdx] = new StackNode<T>(stackNodesIdx);
+            numStackNodes++;
+            return stackNodes[stackNodesIdx++];
+        }
+
+        // Could not find an unused stack node and storage array is full.
+        StackNode<T>[] newStack = new StackNode[stackNodes.length + 64];
+        System.arraycopy(stackNodes, 0, newStack, 0, stackNodes.length);
+        stackNodes = newStack;
+
+        // Create a new stack node and return it.
+        stackNodes[stackNodesIdx] = new StackNode<T>(stackNodesIdx);
+        numStackNodes++;
+        return stackNodes[stackNodesIdx++];
+    }
+
+    private StackNode<T> createStackNode(int flags, @NsUri String ns, @Local String name, T node,
+            @Local String popName, HtmlAttributes attributes
+            // [NOCPP[
+            , TaintableLocatorImpl locator
+            // ]NOCPP]
+    ) {
+        StackNode<T> instance = getUnusedStackNode();
+        instance.setValues(flags, ns, name, node, popName, attributes
+                // [NOCPP[
+                , locator
+                // ]NOCPP]
+        );
+        return instance;
+    }
+
+    private StackNode<T> createStackNode(ElementName elementName, T node
+            // [NOCPP[
+            , TaintableLocatorImpl locator
+            // ]NOCPP]
+    ) {
+        StackNode<T> instance = getUnusedStackNode();
+        instance.setValues(elementName, node
+                // [NOCPP[
+                , locator
+                // ]NOCPP]
+        );
+        return instance;
+    }
+
+    private StackNode<T> createStackNode(ElementName elementName, T node, HtmlAttributes attributes
+            // [NOCPP[
+            , TaintableLocatorImpl locator
+            // ]NOCPP]
+    ) {
+        StackNode<T> instance = getUnusedStackNode();
+        instance.setValues(elementName, node, attributes
+                // [NOCPP[
+                , locator
+                // ]NOCPP]
+        );
+        return instance;
+    }
+
+    private StackNode<T> createStackNode(ElementName elementName, T node, @Local String popName
+            // [NOCPP[
+            , TaintableLocatorImpl locator
+            // ]NOCPP]
+    ) {
+        StackNode<T> instance = getUnusedStackNode();
+        instance.setValues(elementName, node, popName
+                // [NOCPP[
+                , locator
+                // ]NOCPP]
+        );
+        return instance;
+    }
+
+    private StackNode<T> createStackNode(ElementName elementName, @Local String popName, T node
+            // [NOCPP[
+            , TaintableLocatorImpl locator
+            // ]NOCPP]
+    ) {
+        StackNode<T> instance = getUnusedStackNode();
+        instance.setValues(elementName, popName, node
+                // [NOCPP[
+                , locator
+                // ]NOCPP]
+        );
+        return instance;
+    }
+
+    private StackNode<T> createStackNode(ElementName elementName, T node, @Local String popName,
+            boolean markAsIntegrationPoint
+            // [NOCPP[
+            , TaintableLocatorImpl locator
+            // ]NOCPP]
+    ) {
+        StackNode<T> instance = getUnusedStackNode();
+        instance.setValues(elementName, node, popName, markAsIntegrationPoint
+                // [NOCPP[
+                , locator
+                // ]NOCPP]
+        );
+        return instance;
+    }
+
     private void insertIntoFosterParent(T child) throws SAXException {
         int tablePos = findLastOrRoot(TreeBuilder.TABLE);
         int templatePos = findLastOrRoot(TreeBuilder.TEMPLATE);
 
         if (templatePos >= tablePos) {
             appendElement(child, stack[templatePos].node);
             return;
         }
@@ -5088,33 +5230,33 @@ public abstract class TreeBuilder<T> imp
         templateModePtr--;
     }
 
     private void pop() throws SAXException {
         StackNode<T> node = stack[currentPtr];
         assert debugOnlyClearLastStackSlot();
         currentPtr--;
         elementPopped(node.ns, node.popName, node.node);
-        node.release();
+        node.release(this);
     }
 
     private void silentPop() throws SAXException {
         StackNode<T> node = stack[currentPtr];
         assert debugOnlyClearLastStackSlot();
         currentPtr--;
-        node.release();
+        node.release(this);
     }
 
     private void popOnEof() throws SAXException {
         StackNode<T> node = stack[currentPtr];
         assert debugOnlyClearLastStackSlot();
         currentPtr--;
         markMalformedIfScript(node.node);
         elementPopped(node.ns, node.popName, node.node);
-        node.release();
+        node.release(this);
     }
 
     // [NOCPP[
     private void checkAttributes(HtmlAttributes attributes, @NsUri String ns)
             throws SAXException {
         if (errorHandler != null) {
             int len = attributes.getXmlnsLength();
             for (int i = 0; i < len; i++) {
@@ -5206,17 +5348,17 @@ public abstract class TreeBuilder<T> imp
     // ]NOCPP]
 
     private void appendHtmlElementToDocumentAndPush(HtmlAttributes attributes)
             throws SAXException {
         // [NOCPP[
         checkAttributes(attributes, "http://www.w3.org/1999/xhtml");
         // ]NOCPP]
         T elt = createHtmlElementSetAsRoot(attributes);
-        StackNode<T> node = new StackNode<T>(ElementName.HTML,
+        StackNode<T> node = createStackNode(ElementName.HTML,
                 elt
                 // [NOCPP[
                 , errorHandler == null ? null : new TaintableLocatorImpl(tokenizer)
         // ]NOCPP]
         );
         push(node);
     }
 
@@ -5228,17 +5370,17 @@ public abstract class TreeBuilder<T> imp
             throws SAXException {
         // [NOCPP[
         checkAttributes(attributes, "http://www.w3.org/1999/xhtml");
         // ]NOCPP]
         T currentNode = stack[currentPtr].node;
         T elt = createElement("http://www.w3.org/1999/xhtml", "head", attributes, currentNode);
         appendElement(elt, currentNode);
         headPointer = elt;
-        StackNode<T> node = new StackNode<T>(ElementName.HEAD,
+        StackNode<T> node = createStackNode(ElementName.HEAD,
                 elt
                 // [NOCPP[
                 , errorHandler == null ? null : new TaintableLocatorImpl(tokenizer)
         // ]NOCPP]
         );
         push(node);
     }
 
@@ -5267,17 +5409,17 @@ public abstract class TreeBuilder<T> imp
             elt = createElement("http://www.w3.org/1999/xhtml", "form", attributes, current.node);
             appendElement(elt, current.node);
         }
 
         if (!isTemplateContents()) {
             formPointer = elt;
         }
 
-        StackNode<T> node = new StackNode<T>(ElementName.FORM,
+        StackNode<T> node = createStackNode(ElementName.FORM,
                 elt
                 // [NOCPP[
                 , errorHandler == null ? null : new TaintableLocatorImpl(tokenizer)
                 // ]NOCPP]
         );
         push(node);
     }
 
@@ -5295,17 +5437,17 @@ public abstract class TreeBuilder<T> imp
         StackNode<T> current = stack[currentPtr];
         if (current.isFosterParenting()) {
             fatal();
             elt = createAndInsertFosterParentedElement("http://www.w3.org/1999/xhtml", elementName.getName(), attributes);
         } else {
             elt = createElement("http://www.w3.org/1999/xhtml", elementName.getName(), attributes, current.node);
             appendElement(elt, current.node);
         }
-        StackNode<T> node = new StackNode<T>(elementName, elt, clone
+        StackNode<T> node = createStackNode(elementName, elt, clone
                 // [NOCPP[
                 , errorHandler == null ? null : new TaintableLocatorImpl(tokenizer)
         // ]NOCPP]
         );
         push(node);
         append(node);
         node.retain(); // append doesn't retain itself
     }
@@ -5318,17 +5460,17 @@ public abstract class TreeBuilder<T> imp
         // ]NOCPP]
         // This method can't be called for custom elements
         T currentNode = stack[currentPtr].node;
         T elt = createElement("http://www.w3.org/1999/xhtml", elementName.getName(), attributes, currentNode);
         appendElement(elt, currentNode);
         if (ElementName.TEMPLATE == elementName) {
             elt = getDocumentFragmentForTemplate(elt);
         }
-        StackNode<T> node = new StackNode<T>(elementName, elt
+        StackNode<T> node = createStackNode(elementName, elt
                 // [NOCPP[
                 , errorHandler == null ? null : new TaintableLocatorImpl(tokenizer)
         // ]NOCPP]
         );
         push(node);
     }
 
     private void appendToCurrentNodeAndPushElementMayFoster(ElementName elementName,
@@ -5345,17 +5487,17 @@ public abstract class TreeBuilder<T> imp
         StackNode<T> current = stack[currentPtr];
         if (current.isFosterParenting()) {
             fatal();
             elt = createAndInsertFosterParentedElement("http://www.w3.org/1999/xhtml", popName, attributes);
         } else {
             elt = createElement("http://www.w3.org/1999/xhtml", popName, attributes, current.node);
             appendElement(elt, current.node);
         }
-        StackNode<T> node = new StackNode<T>(elementName, elt, popName
+        StackNode<T> node = createStackNode(elementName, elt, popName
                 // [NOCPP[
                 , errorHandler == null ? null : new TaintableLocatorImpl(tokenizer)
         // ]NOCPP]
         );
         push(node);
     }
 
     private void appendToCurrentNodeAndPushElementMayFosterMathML(
@@ -5379,17 +5521,17 @@ public abstract class TreeBuilder<T> imp
         StackNode<T> current = stack[currentPtr];
         if (current.isFosterParenting()) {
             fatal();
             elt = createAndInsertFosterParentedElement("http://www.w3.org/1998/Math/MathML", popName, attributes);
         } else {
             elt  = createElement("http://www.w3.org/1998/Math/MathML", popName, attributes, current.node);
             appendElement(elt, current.node);
         }
-        StackNode<T> node = new StackNode<T>(elementName, elt, popName,
+        StackNode<T> node = createStackNode(elementName, elt, popName,
                 markAsHtmlIntegrationPoint
                 // [NOCPP[
                 , errorHandler == null ? null : new TaintableLocatorImpl(tokenizer)
         // ]NOCPP]
         );
         push(node);
     }
 
@@ -5428,17 +5570,17 @@ public abstract class TreeBuilder<T> imp
         StackNode<T> current = stack[currentPtr];
         if (current.isFosterParenting()) {
             fatal();
             elt = createAndInsertFosterParentedElement("http://www.w3.org/2000/svg", popName, attributes);
         } else {
             elt = createElement("http://www.w3.org/2000/svg", popName, attributes, current.node);
             appendElement(elt, current.node);
         }
-        StackNode<T> node = new StackNode<T>(elementName, popName, elt
+        StackNode<T> node = createStackNode(elementName, popName, elt
                 // [NOCPP[
                 , errorHandler == null ? null : new TaintableLocatorImpl(tokenizer)
         // ]NOCPP]
         );
         push(node);
     }
 
     private void appendToCurrentNodeAndPushElementMayFoster(ElementName elementName,
@@ -5455,17 +5597,17 @@ public abstract class TreeBuilder<T> imp
             fatal();
             elt = createAndInsertFosterParentedElement("http://www.w3.org/1999/xhtml", elementName.getName(),
                     attributes, formOwner);
         } else {
             elt = createElement("http://www.w3.org/1999/xhtml", elementName.getName(),
                     attributes, formOwner, current.node);
             appendElement(elt, current.node);
         }
-        StackNode<T> node = new StackNode<T>(elementName, elt
+        StackNode<T> node = createStackNode(elementName, elt
                 // [NOCPP[
                 , errorHandler == null ? null : new TaintableLocatorImpl(tokenizer)
         // ]NOCPP]
         );
         push(node);
     }
 
     private void appendVoidElementToCurrentMayFoster(
@@ -5938,50 +6080,50 @@ public abstract class TreeBuilder<T> imp
      * @throws SAXException
      */
     @SuppressWarnings("unchecked") public TreeBuilderState<T> newSnapshot()
             throws SAXException {
         StackNode<T>[] listCopy = new StackNode[listPtr + 1];
         for (int i = 0; i < listCopy.length; i++) {
             StackNode<T> node = listOfActiveFormattingElements[i];
             if (node != null) {
-                StackNode<T> newNode = new StackNode<T>(node.getFlags(), node.ns,
+                StackNode<T> newNode = createStackNode(node.getFlags(), node.ns,
                         node.name, node.node, node.popName,
                         node.attributes.cloneAttributes(null)
                         // [NOCPP[
                         , node.getLocator()
                 // ]NOCPP]
                 );
                 listCopy[i] = newNode;
             } else {
                 listCopy[i] = null;
             }
         }
         StackNode<T>[] stackCopy = new StackNode[currentPtr + 1];
         for (int i = 0; i < stackCopy.length; i++) {
             StackNode<T> node = stack[i];
             int listIndex = findInListOfActiveFormattingElements(node);
             if (listIndex == -1) {
-                StackNode<T> newNode = new StackNode<T>(node.getFlags(), node.ns,
+                StackNode<T> newNode = createStackNode(node.getFlags(), node.ns,
                         node.name, node.node, node.popName,
                         null
                         // [NOCPP[
                         , node.getLocator()
                 // ]NOCPP]
                 );
                 stackCopy[i] = newNode;
             } else {
                 stackCopy[i] = listCopy[listIndex];
                 stackCopy[i].retain();
             }
         }
         int[] templateModeStackCopy = new int[templateModePtr + 1];
         System.arraycopy(templateModeStack, 0, templateModeStackCopy, 0,
                 templateModeStackCopy.length);
-        return new StateSnapshot<T>(stackCopy, listCopy, templateModeStackCopy, formPointer,
+        return new StateSnapshot<T>(this, stackCopy, listCopy, templateModeStackCopy, formPointer,
                 headPointer, deepTreeSurrogateParent, mode, originalMode, framesetOk,
                 needToDropLF, quirks);
     }
 
     public boolean snapshotMatches(TreeBuilderState<T> snapshot) {
         StackNode<T>[] stackCopy = snapshot.getStack();
         int stackLen = snapshot.getStackLength();
         StackNode<T>[] listCopy = snapshot.getListOfActiveFormattingElements();
@@ -6035,58 +6177,58 @@ public abstract class TreeBuilder<T> imp
         int stackLen = snapshot.getStackLength();
         StackNode<T>[] listCopy = snapshot.getListOfActiveFormattingElements();
         int listLen = snapshot.getListOfActiveFormattingElementsLength();
         int[] templateModeStackCopy = snapshot.getTemplateModeStack();
         int templateModeStackLen = snapshot.getTemplateModeStackLength();
 
         for (int i = 0; i <= listPtr; i++) {
             if (listOfActiveFormattingElements[i] != null) {
-                listOfActiveFormattingElements[i].release();
+                listOfActiveFormattingElements[i].release(this);
             }
         }
         if (listOfActiveFormattingElements.length < listLen) {
             listOfActiveFormattingElements = new StackNode[listLen];
         }
         listPtr = listLen - 1;
 
         for (int i = 0; i <= currentPtr; i++) {
-            stack[i].release();
+            stack[i].release(this);
         }
         if (stack.length < stackLen) {
             stack = new StackNode[stackLen];
         }
         currentPtr = stackLen - 1;
 
         if (templateModeStack.length < templateModeStackLen) {
             templateModeStack = new int[templateModeStackLen];
         }
         templateModePtr = templateModeStackLen - 1;
 
         for (int i = 0; i < listLen; i++) {
             StackNode<T> node = listCopy[i];
             if (node != null) {
-                StackNode<T> newNode = new StackNode<T>(node.getFlags(), node.ns,
+                StackNode<T> newNode = createStackNode(node.getFlags(), node.ns,
                         Portability.newLocalFromLocal(node.name, interner), node.node,
                         Portability.newLocalFromLocal(node.popName, interner),
                         node.attributes.cloneAttributes(null)
                         // [NOCPP[
                         , node.getLocator()
                 // ]NOCPP]
                 );
                 listOfActiveFormattingElements[i] = newNode;
             } else {
                 listOfActiveFormattingElements[i] = null;
             }
         }
         for (int i = 0; i < stackLen; i++) {
             StackNode<T> node = stackCopy[i];
             int listIndex = findInArray(node, listCopy);
             if (listIndex == -1) {
-                StackNode<T> newNode = new StackNode<T>(node.getFlags(), node.ns,
+                StackNode<T> newNode = createStackNode(node.getFlags(), node.ns,
                         Portability.newLocalFromLocal(node.name, interner), node.node,
                         Portability.newLocalFromLocal(node.popName, interner),
                         null
                         // [NOCPP[
                         , node.getLocator()
                 // ]NOCPP]
                 );
                 stack[i] = newNode;