Title: [123691] trunk/Source/WebCore
- Revision
- 123691
- Author
- tk...@chromium.org
- Date
- 2012-07-25 18:36:33 -0700 (Wed, 25 Jul 2012)
Log Message
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 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.
Note: This is a re-landing of r123191. We rolled it out because of
suspicion of a performance regression. However it was innocent.
* 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.
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (123690 => 123691)
--- trunk/Source/WebCore/ChangeLog 2012-07-26 01:22:59 UTC (rev 123690)
+++ trunk/Source/WebCore/ChangeLog 2012-07-26 01:36:33 UTC (rev 123691)
@@ -1,3 +1,35 @@
+2012-07-25 Kent Tamura <tk...@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 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.
+
+ Note: This is a re-landing of r123191. We rolled it out because of
+ suspicion of a performance regression. However it was innocent.
+
+ * 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-25 Benjamin Poulain <bpoul...@apple.com>
Initialize QualifiedName's strings from the read only data segment
Modified: trunk/Source/WebCore/html/FormController.cpp (123690 => 123691)
--- trunk/Source/WebCore/html/FormController.cpp 2012-07-26 01:22:59 UTC (rev 123690)
+++ trunk/Source/WebCore/html/FormController.cpp 2012-07-26 01:36:33 UTC (rev 123691)
@@ -278,8 +278,9 @@
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 @@
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 @@
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 @@
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 @@
FormToKeyMap::iterator it = m_formToKeyMap.find(form);
if (it == m_formToKeyMap.end())
return;
- m_existingKeys.remove(it->second);
m_formToKeyMap.remove(it);
}
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
http://lists.webkit.org/mailman/listinfo/webkit-changes
