REGRESSION(r121420): Performance regression of form state saving for pages with multi...
authortkent@chromium.org <tkent@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 26 Jul 2012 01:36:33 +0000 (01:36 +0000)
committertkent@chromium.org <tkent@chromium.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 26 Jul 2012 01:36:33 +0000 (01:36 +0000)
commitefb9d7e096f55fe12c0c1c3af8514f5664456104
tree610feafef3b8936b12d3ed32bd3851dda3f4b45d
parentdba3024059254952b594625f01e45cda363b843e
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.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@123691 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Source/WebCore/ChangeLog
Source/WebCore/html/FormController.cpp