Avoid N^2 walk placing renderers when building the render tree

Source/core/dom/Document.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  *           (C) 2006 Alexey Proskuryakov (ap@webkit.org)
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2011, 2012 Apple Inc. All rights reserved.
  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
  * Copyright (C) 2008, 2009, 2011, 2012 Google Inc. All rights reserved.
  * Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies)
  * Copyright (C) Research In Motion Limited 2010-2011. All rights reserved.
@@ skipping 1663 matching lines @@
         if ((change == Force) || (shouldDisplaySeamlesslyWithParent() && (change >= Inherit))) {
             // style selector may set this again during recalc
             m_hasNodesWithPlaceholderStyle = false;
 
             RefPtr<RenderStyle> documentStyle = StyleResolver::styleForDocument(this, m_styleResolver ? m_styleResolver->fontSelector() : 0);
             StyleChange ch = Node::diff(documentStyle.get(), renderer()->style(), this);
             if (ch != NoChange)
                 renderer()->setStyle(documentStyle.release());
         }
 
-        for (Node* n = firstChild(); n; n = n->nextSibling()) {
+        for (Node* n = lastChild(); n; n = n->previousSibling()) {
+        // for (Node* n = firstChild(); n; n = n->nextSibling()) {

[ojan, 2013/06/03 23:03:29]

derp.

             if (!n->isElementNode())
                 continue;
             Element* element = toElement(n);
             if (shouldRecalcStyle(change, element))
                 element->recalcStyle(change);
         }
 
         if (view())
             view()->updateCompositingLayersAfterStyleChange();
 
@@ skipping 3931 matching lines @@
         return;
 
     Vector<RefPtr<Element> > associatedFormControls;
     copyToVector(m_associatedFormControls, associatedFormControls);
 
     frame()->page()->chrome().client()->didAssociateFormControls(associatedFormControls);
     m_associatedFormControls.clear();
 }
 
 } // namespace WebCore