Bug 130820

Summary: HTMLConverter::_processText is slow because it walks up ancestor elements
Product: WebKit Reporter: Ryosuke Niwa <rniwa>
Component: HTML EditingAssignee: Ryosuke Niwa <rniwa>
Status: RESOLVED FIXED    
Severity: Normal CC: commit-queue, darin, enrica, kling, sam
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on:    
Bug Blocks: 130227    
Attachments:
Description Flags
Adds a new cache none

Ryosuke Niwa
Reported 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.
Attachments
Adds a new cache (4.99 KB, patch)
2014-03-26 22:35 PDT, Ryosuke Niwa 		no flags
DetailsFormatted DiffDiff
View All Add attachment proposed patch, testcase, etc.
Ryosuke Niwa
Comment 1 2014-03-26 22:35:46 PDT
Created attachment 227922 [details] Adds a new cache
WebKit Commit Bot
Comment 2 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>
WebKit Commit Bot
Comment 3 2014-03-26 23:23:18 PDT
All reviewed patches have been landed. Closing bug.
Note You need to log in before you can comment on or make changes to this bug.