REGRESSION(r121420): Performance regression of form state saving for pages with multi...
authortkent@chromium.org <tkent@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 20 Jul 2012 08:03:59 +0000 (08:03 +0000)
committertkent@chromium.org <tkent@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 20 Jul 2012 08:03:59 +0000 (08:03 +0000)
https://bugs.webkit.org/show_bug.cgi?id=91804

Reviewed by Hajime Morita.

The complexity of FormKeyGenerator::formKey() was O(N) where N is the
number of form elements with an identical action URL, and formKey() is
called for every form. So, it's O(N^2). A page in www.reddit.com
contains hundreds of form elements with action="#". So FormController::
formElementsState() took a few seconds on a slow machine.

In order to avoid O(N^2) operation, storing a map from form signatures
to next index numbers, instead of storing existing formKey strings.

No new tests. Just a performance improvement.

* html/FormController.cpp:
(FormKeyGenerator): Remove m_existingKeys. Add a map from a form
signature string to the next index number.
(WebCore::formSignature): Returns a signature string for a form, without
an index number. This is like "actionURL [name1 name2 ]"
(WebCore::FormKeyGenerator::formKey):
Creates a formKey string by concatenating a formSignature and #n. N is
obtained from m_formSignatureToNextIndexMap in O(1).
(WebCore::FormKeyGenerator::willDeleteForm):
Remove the code for m_existingKeys.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@123191 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/html/FormController.cpp

index d4839eb..8380777 100644 (file)
@@ -1,3 +1,32 @@
+2012-07-20  Kent Tamura  <tkent@chromium.org>
+
+        REGRESSION(r121420): Performance regression of form state saving for pages with multiple forms
+        https://bugs.webkit.org/show_bug.cgi?id=91804
+
+        Reviewed by Hajime Morita.
+
+        The complexity of FormKeyGenerator::formKey() was O(N) where N is the
+        number of form elements with an identical action URL, and formKey() is
+        called for every form. So, it's O(N^2). A page in www.reddit.com
+        contains hundreds of form elements with action="#". So FormController::
+        formElementsState() took a few seconds on a slow machine.
+
+        In order to avoid O(N^2) operation, storing a map from form signatures
+        to next index numbers, instead of storing existing formKey strings.
+
+        No new tests. Just a performance improvement.
+
+        * html/FormController.cpp:
+        (FormKeyGenerator): Remove m_existingKeys. Add a map from a form
+        signature string to the next index number.
+        (WebCore::formSignature): Returns a signature string for a form, without
+        an index number. This is like "actionURL [name1 name2 ]"
+        (WebCore::FormKeyGenerator::formKey):
+        Creates a formKey string by concatenating a formSignature and #n. N is
+        obtained from m_formSignatureToNextIndexMap in O(1).
+        (WebCore::FormKeyGenerator::willDeleteForm):
+        Remove the code for m_existingKeys.
+
 2012-07-20  Keishi Hattori  <keishi@webkit.org>
 
         Fix crash in WebCore::HTMLInputElement::dataList
index 35594b8..5e39fe2 100644 (file)
@@ -278,8 +278,9 @@ private:
     FormKeyGenerator() { }
 
     typedef HashMap<HTMLFormElement*, AtomicString> FormToKeyMap;
+    typedef HashMap<String, unsigned> FormSignatureToNextIndexMap;
     FormToKeyMap m_formToKeyMap;
-    HashSet<AtomicString> m_existingKeys;
+    FormSignatureToNextIndexMap m_formSignatureToNextIndexMap;
 };
 
 static inline void recordFormStructure(const HTMLFormElement& form, StringBuilder& builder)
@@ -304,10 +305,9 @@ static inline void recordFormStructure(const HTMLFormElement& form, StringBuilde
     builder.append("]");
 }
 
-static inline AtomicString createKey(HTMLFormElement* form, unsigned index)
+static inline String formSignature(const HTMLFormElement& form)
 {
-    ASSERT(form);
-    KURL actionURL = form->getURLAttribute(actionAttr);
+    KURL actionURL = form.getURLAttribute(actionAttr);
     // Remove the query part because it might contain volatile parameters such
     // as a session key.
     actionURL.setQuery(String());
@@ -315,11 +315,8 @@ static inline AtomicString createKey(HTMLFormElement* form, unsigned index)
     if (!actionURL.isEmpty())
         builder.append(actionURL.string());
 
-    recordFormStructure(*form, builder);
-
-    builder.append(" #");
-    builder.append(String::number(index));
-    return builder.toAtomicString();
+    recordFormStructure(form, builder);
+    return builder.toString();
 }
 
 AtomicString FormKeyGenerator::formKey(const HTMLFormControlElementWithState& control)
@@ -333,13 +330,18 @@ AtomicString FormKeyGenerator::formKey(const HTMLFormControlElementWithState& co
     if (it != m_formToKeyMap.end())
         return it->second;
 
-    AtomicString candidateKey;
-    unsigned index = 0;
-    do {
-        candidateKey = createKey(form, index++);
-    } while (!m_existingKeys.add(candidateKey).isNewEntry);
-    m_formToKeyMap.add(form, candidateKey);
-    return candidateKey;
+    String signature = formSignature(*form);
+    ASSERT(!signature.isNull());
+    FormSignatureToNextIndexMap::AddResult result = m_formSignatureToNextIndexMap.add(signature, 0);
+    unsigned nextIndex = result.iterator->second++;
+
+    StringBuilder builder;
+    builder.append(signature);
+    builder.append(" #");
+    builder.append(String::number(nextIndex));
+    AtomicString formKey = builder.toAtomicString();
+    m_formToKeyMap.add(form, formKey);
+    return formKey;
 }
 
 void FormKeyGenerator::willDeleteForm(HTMLFormElement* form)
@@ -350,7 +352,6 @@ void FormKeyGenerator::willDeleteForm(HTMLFormElement* form)
     FormToKeyMap::iterator it = m_formToKeyMap.find(form);
     if (it == m_formToKeyMap.end())
         return;
-    m_existingKeys.remove(it->second);
     m_formToKeyMap.remove(it);
 }