Bug 130820 - HTMLConverter::_processText is slow because it walks up ancestor elements
Summary: HTMLConverter::_processText is slow because it walks up ancestor elements
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: HTML Editing (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Ryosuke Niwa
URL:
Keywords:
Depends on:
Blocks: 130227
  Show dependency treegraph
 
Reported: 2014-03-26 22:30 PDT by Ryosuke Niwa
Modified: 2014-03-26 23:23 PDT (History)
5 users (show)

See Also:


Attachments
Adds a new cache (4.99 KB, patch)
2014-03-26 22:35 PDT, Ryosuke Niwa
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Ryosuke Niwa 2014-03-26 22:30:53 PDT
Right now HTMLConverter::_processText walks up the entire ancestor chain to merge their attributed strings.
Doing that for every text node results in O(kn) runtime complexity where k is the depth of the tree and n is the number of text nodes in the tree.
Comment 1 Ryosuke Niwa 2014-03-26 22:35:46 PDT
Created attachment 227922 [details]
Adds a new cache
Comment 2 WebKit Commit Bot 2014-03-26 23:23:15 PDT
Comment on attachment 227922 [details]
Adds a new cache

Clearing flags on attachment: 227922

Committed r166347: <http://trac.webkit.org/changeset/166347>
Comment 3 WebKit Commit Bot 2014-03-26 23:23:18 PDT
All reviewed patches have been landed.  Closing bug.