118282 2013-07-01 23:06:52 -0700 plainText() is O(N^2) 2013-07-02 12:10:56 -0700 1 1 1 Unclassified WebKit New Bugs 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 1 ggaren ggaren ap benjamin msaboff oldest_to_newest 905259 0 ggaren 2013-07-01 23:06:52 -0700 plainText() is O(N^2) 905260 1 205870 ggaren 2013-07-01 23:08:23 -0700 Created attachment 205870 Patch 905264 2 205870 ap 2013-07-01 23:27:12 -0700 Comment on attachment 205870 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=205870&action=review > Source/WebCore/editing/TextIterator.cpp:2514 > if (builder.capacity() < builder.length() + it.length()) > - builder.reserveCapacity(builder.capacity() + cMaxSegmentSize); > + builder.reserveCapacity(builder.capacity() * 2); StringBuilder is supposed to do this internally. Would simply removing these lines fix the issue? 905267 3 ggaren 2013-07-01 23:48:55 -0700 > StringBuilder is supposed to do this internally. Would simply removing these lines fix the issue? No. Prior to 10/13/10 <http://trac.webkit.org/changeset/69683>, StringBuilder used the Vector grow algorithm. Since then, it has used a "grow to fit the requested length exactly" algorithm. It seems like the change in r69683 was inadvertent. Perhaps we should revisit the project-wide behavior in future. 905449 4 ap 2013-07-02 08:42:08 -0700 What about all that code saying "std::max(requiredLength, std::max(minimumCapacity, m_length * 2))" in StringBuilder.cpp? I didn't inspect all code paths, but it appears that it's there to implement capacity doubling. 905466 5 ggaren 2013-07-02 09:30:26 -0700 Eep! How could I miss that?! 905468 6 ggaren 2013-07-02 09:35:51 -0700 Now I have an excuse to fix two O(N^2) bugs in one patch! 905471 7 205923 ggaren 2013-07-02 09:40:50 -0700 Created attachment 205923 Patch 905474 8 205923 ap 2013-07-02 09:49:59 -0700 Comment on attachment 205923 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=205923&action=review > Source/WTF/wtf/text/StringBuilder.cpp:35 > +static size_t expandCapacity(size_t capacity, size_t newLength) I'm very much not sure about this function name. The function doesn't expand any capacity, it only calculates one. Perhaps something like bestCapacity? suggestedCapacity? expandedCapacity? 905527 9 ggaren 2013-07-02 12:10:19 -0700 Committed r152306: <http://trac.webkit.org/changeset/152306> 905529 10 ggaren 2013-07-02 12:10:56 -0700 I went with expandedCapacity. 205870 2013-07-01 23:08:23 -0700 2013-07-02 09:40:48 -0700 Patch bug-118282-20130701230619.patch text/plain 1432 ggaren SW5kZXg6IFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBTb3VyY2UvV2Vi Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDE1MjI4MCkKKysrIFNvdXJjZS9XZWJDb3JlL0NoYW5n ZUxvZwkod29ya2luZyBjb3B5KQpAQCAtMSwzICsxLDE3IEBACisyMDEzLTA3LTAxICBHZW9mZnJl eSBHYXJlbiAgPGdnYXJlbkBhcHBsZS5jb20+CisKKyAgICAgICAgcGxhaW5UZXh0KCkgaXMgTyhO XjIpCisgICAgICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD0xMTgy ODIKKyAgICAgICAgPHJkYXI6Ly9wcm9ibGVtLzE0Mjg0MzYwPgorCisgICAgICAgIFJldmlld2Vk IGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgICogZWRpdGluZy9UZXh0SXRlcmF0b3IuY3Bw OgorICAgICAgICAoV2ViQ29yZTo6cGxhaW5UZXh0KTogQXBwbHkgYSBsaXR0bGUgQ1MgMTAxLgor CisgICAgICAgIFRoZSBidWlsZGVyIHNocmlua3MgdG8gZml0IGF0IHRoZSBlbmQsIHNvIHRoZXJl J3Mgbm8gZG93bnNpZGUgdG8gdGhlCisgICAgICAgIGV4dHJhIG1lbW9yeSB1c2UuCisKIDIwMTMt MDctMDEgIEFsZXggQ2hyaXN0ZW5zZW4gIDxhY2hyaXN0ZW5zZW5AYXBwbGUuY29tPgogCiAgICAg ICAgIFdpbmRvd3Mgc2hvdWxkIGJlIGluY2x1ZGVkIGluIHRoZSBsaXN0IG9mIHBsYXRmb3JtcyB0 aGF0IGNhbiB1c2UgT3BlbkdMIEVTIDIuCkluZGV4OiBTb3VyY2UvV2ViQ29yZS9lZGl0aW5nL1Rl eHRJdGVyYXRvci5jcHAKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gU291cmNlL1dlYkNvcmUvZWRpdGluZy9UZXh0 SXRlcmF0b3IuY3BwCShyZXZpc2lvbiAxNTE5MTYpCisrKyBTb3VyY2UvV2ViQ29yZS9lZGl0aW5n L1RleHRJdGVyYXRvci5jcHAJKHdvcmtpbmcgY29weSkKQEAgLTI1MTEsNyArMjUxMSw3IEBAIFN0 cmluZyBwbGFpblRleHQoY29uc3QgUmFuZ2UqIHIsIFRleHRJdGUKICAgICAKICAgICBmb3IgKFRl eHRJdGVyYXRvciBpdChyLCBiZWhhdmlvcik7ICFpdC5hdEVuZCgpOyBpdC5hZHZhbmNlKCkpIHsK ICAgICAgICAgaWYgKGJ1aWxkZXIuY2FwYWNpdHkoKSA8IGJ1aWxkZXIubGVuZ3RoKCkgKyBpdC5s ZW5ndGgoKSkKLSAgICAgICAgICAgIGJ1aWxkZXIucmVzZXJ2ZUNhcGFjaXR5KGJ1aWxkZXIuY2Fw YWNpdHkoKSArIGNNYXhTZWdtZW50U2l6ZSk7CisgICAgICAgICAgICBidWlsZGVyLnJlc2VydmVD YXBhY2l0eShidWlsZGVyLmNhcGFjaXR5KCkgKiAyKTsKIAogICAgICAgICBpdC5hcHBlbmRUZXh0 VG9TdHJpbmdCdWlsZGVyKGJ1aWxkZXIpOwogICAgICAgICBidWZmZXJMZW5ndGggKz0gaXQubGVu Z3RoKCk7Cg== 205923 2013-07-02 09:40:50 -0700 2013-07-02 09:49:59 -0700 Patch bug-118282-20130702093846.patch text/plain 5407 ggaren SW5kZXg6IFNvdXJjZS9XVEYvQ2hhbmdlTG9nCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFNvdXJjZS9XVEYvQ2hh bmdlTG9nCShyZXZpc2lvbiAxNTIyOTcpCisrKyBTb3VyY2UvV1RGL0NoYW5nZUxvZwkod29ya2lu ZyBjb3B5KQpAQCAtMSwzICsxLDIyIEBACisyMDEzLTA3LTAyICBHZW9mZnJleSBHYXJlbiAgPGdn YXJlbkBhcHBsZS5jb20+CisKKyAgICAgICAgcGxhaW5UZXh0KCkgaXMgTyhOXjIpCisgICAgICAg IGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD0xMTgyODIKKyAgICAgICAg PHJkYXI6Ly9wcm9ibGVtLzE0Mjg0MzYwPgorCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAo T09QUyEpLgorCisgICAgICAgICogd3RmL3RleHQvU3RyaW5nQnVpbGRlci5jcHA6CisgICAgICAg IChXVEY6OmV4cGFuZENhcGFjaXR5KTogRmFjdG9yZWQgb3V0IHRoaXMgaGVscGVyIGZ1bmN0aW9u IHRvIHNpbXBsaWZ5CisgICAgICAgIHNvbWUgY29kZSB0aGF0IHdhcyBkdXBsaWNhdGVkIGluIGZv dXIgcGxhY2VzLgorCisgICAgICAgIChXVEY6OlN0cmluZ0J1aWxkZXI6OmFwcGVuZFVuaW5pdGlh bGl6ZWRTbG93KToKKyAgICAgICAgKFdURjo6U3RyaW5nQnVpbGRlcjo6YXBwZW5kKTogVXNlIGV4 cGFuZENhcGFjaXR5KCkuIE9uZSBvZiB0aGUgY2FzZXMKKyAgICAgICAgd2FzIG5vdCBkb2luZyBh bnl0aGluZyBzcGVjaWFsLCBhbmQgc28gd2FzIE8oTl4yKS4KKworICAgICAgICBBbHNvLCBhbHdh eXMgY2FsbCBleHBhbmRDYXBhY2l0eSgpIGl0IGluIGEgc3RhbmRhcmQgd2F5LCBjYWxsaW5nCisg ICAgICAgIGNhcGFjaXR5KCkgZmlyc3QsIHNvIGl0J3MgZWFzeSB0byB0ZWxsIGF0IGEgZ2xhbmNl IHRoYXQgeW91IGdvdCBpdCByaWdodC4KKwogMjAxMy0wNy0wMiAgTWlraGFpbCBQb3pkbnlha292 ICA8bWlraGFpbC5wb3pkbnlha292QGludGVsLmNvbT4KIAogICAgICAgICBBdm9pZCBjb2RlIGR1 cGxpY2F0aW9uIGluc2lkZSBTdHJpbmc6OmFwcGVuZCgpCkluZGV4OiBTb3VyY2UvV1RGL3d0Zi90 ZXh0L1N0cmluZ0J1aWxkZXIuY3BwCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFNvdXJjZS9XVEYvd3RmL3RleHQv U3RyaW5nQnVpbGRlci5jcHAJKHJldmlzaW9uIDE1MTkxNikKKysrIFNvdXJjZS9XVEYvd3RmL3Rl eHQvU3RyaW5nQnVpbGRlci5jcHAJKHdvcmtpbmcgY29weSkKQEAgLTMyLDcgKzMyLDExIEBACiAK IG5hbWVzcGFjZSBXVEYgewogCi1zdGF0aWMgY29uc3QgdW5zaWduZWQgbWluaW11bUNhcGFjaXR5 ID0gMTY7CitzdGF0aWMgc2l6ZV90IGV4cGFuZENhcGFjaXR5KHNpemVfdCBjYXBhY2l0eSwgc2l6 ZV90IG5ld0xlbmd0aCkKK3sKKyAgICBzdGF0aWMgY29uc3Qgc2l6ZV90IG1pbmltdW1DYXBhY2l0 eSA9IDE2OworICAgIHJldHVybiBzdGQ6Om1heChjYXBhY2l0eSwgc3RkOjptYXgobWluaW11bUNh cGFjaXR5LCBuZXdMZW5ndGggKiAyKSk7Cit9CiAKIHZvaWQgU3RyaW5nQnVpbGRlcjo6cmVpZnlT dHJpbmcoKSBjb25zdAogewpAQCAtMjI0LDEwICsyMjgsMTAgQEAgQ2hhclR5cGUqIFN0cmluZ0J1 aWxkZXI6OmFwcGVuZFVuaW5pdGlhbAogICAgICAgICAvLyBJZiB0aGUgYnVmZmVyIGlzIHZhbGlk IGl0IG11c3QgYmUgYXQgbGVhc3QgYXMgbG9uZyBhcyB0aGUgY3VycmVudCBidWlsZGVyIGNvbnRl bnRzIQogICAgICAgICBBU1NFUlQobV9idWZmZXItPmxlbmd0aCgpID49IG1fbGVuZ3RoKTsKICAg ICAgICAgCi0gICAgICAgIHJlYWxsb2NhdGVCdWZmZXI8Q2hhclR5cGU+KHN0ZDo6bWF4KHJlcXVp cmVkTGVuZ3RoLCBzdGQ6Om1heChtaW5pbXVtQ2FwYWNpdHksIG1fYnVmZmVyLT5sZW5ndGgoKSAq IDIpKSk7CisgICAgICAgIHJlYWxsb2NhdGVCdWZmZXI8Q2hhclR5cGU+KGV4cGFuZENhcGFjaXR5 KGNhcGFjaXR5KCksIHJlcXVpcmVkTGVuZ3RoKSk7CiAgICAgfSBlbHNlIHsKICAgICAgICAgQVNT RVJUKG1fc3RyaW5nLmxlbmd0aCgpID09IG1fbGVuZ3RoKTsKLSAgICAgICAgYWxsb2NhdGVCdWZm ZXIobV9sZW5ndGggPyBtX3N0cmluZy5nZXRDaGFyYWN0ZXJzPENoYXJUeXBlPigpIDogMCwgc3Rk OjptYXgocmVxdWlyZWRMZW5ndGgsIHN0ZDo6bWF4KG1pbmltdW1DYXBhY2l0eSwgbV9sZW5ndGgg KiAyKSkpOworICAgICAgICBhbGxvY2F0ZUJ1ZmZlcihtX2xlbmd0aCA/IG1fc3RyaW5nLmdldENo YXJhY3RlcnM8Q2hhclR5cGU+KCkgOiAwLCBleHBhbmRDYXBhY2l0eShjYXBhY2l0eSgpLCByZXF1 aXJlZExlbmd0aCkpOwogICAgIH0KICAgICAKICAgICBDaGFyVHlwZSogcmVzdWx0ID0gZ2V0QnVm ZmVyQ2hhcmFjdGVyczxDaGFyVHlwZT4oKSArIG1fbGVuZ3RoOwpAQCAtMjU5LDEwICsyNjMsMTAg QEAgdm9pZCBTdHJpbmdCdWlsZGVyOjphcHBlbmQoY29uc3QgVUNoYXIqIAogICAgICAgICAgICAg Ly8gSWYgdGhlIGJ1ZmZlciBpcyB2YWxpZCBpdCBtdXN0IGJlIGF0IGxlYXN0IGFzIGxvbmcgYXMg dGhlIGN1cnJlbnQgYnVpbGRlciBjb250ZW50cyEKICAgICAgICAgICAgIEFTU0VSVChtX2J1ZmZl ci0+bGVuZ3RoKCkgPj0gbV9sZW5ndGgpOwogICAgICAgICAgICAgCi0gICAgICAgICAgICBhbGxv Y2F0ZUJ1ZmZlclVwQ29udmVydChtX2J1ZmZlci0+Y2hhcmFjdGVyczgoKSwgcmVxdWlyZWRMZW5n dGgpOworICAgICAgICAgICAgYWxsb2NhdGVCdWZmZXJVcENvbnZlcnQobV9idWZmZXItPmNoYXJh Y3RlcnM4KCksIGV4cGFuZENhcGFjaXR5KGNhcGFjaXR5KCksIHJlcXVpcmVkTGVuZ3RoKSk7CiAg ICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICBBU1NFUlQobV9zdHJpbmcubGVuZ3RoKCkgPT0g bV9sZW5ndGgpOwotICAgICAgICAgICAgYWxsb2NhdGVCdWZmZXJVcENvbnZlcnQobV9zdHJpbmcu aXNOdWxsKCkgPyAwIDogbV9zdHJpbmcuY2hhcmFjdGVyczgoKSwgc3RkOjptYXgocmVxdWlyZWRM ZW5ndGgsIHN0ZDo6bWF4KG1pbmltdW1DYXBhY2l0eSwgbV9sZW5ndGggKiAyKSkpOworICAgICAg ICAgICAgYWxsb2NhdGVCdWZmZXJVcENvbnZlcnQobV9zdHJpbmcuaXNOdWxsKCkgPyAwIDogbV9z dHJpbmcuY2hhcmFjdGVyczgoKSwgZXhwYW5kQ2FwYWNpdHkoY2FwYWNpdHkoKSwgcmVxdWlyZWRM ZW5ndGgpKTsKICAgICAgICAgfQogCiAgICAgICAgIG1lbWNweShtX2J1ZmZlckNoYXJhY3RlcnMx NiArIG1fbGVuZ3RoLCBjaGFyYWN0ZXJzLCBzdGF0aWNfY2FzdDxzaXplX3Q+KGxlbmd0aCkgKiBz aXplb2YoVUNoYXIpKTsgICAgICAgIApJbmRleDogU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCj09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT0KLS0tIFNvdXJjZS9XZWJDb3JlL0NoYW5nZUxvZwkocmV2aXNpb24gMTUyMjgwKQor KysgU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCSh3b3JraW5nIGNvcHkpCkBAIC0xLDMgKzEsMTYg QEAKKzIwMTMtMDctMDIgIEdlb2ZmcmV5IEdhcmVuICA8Z2dhcmVuQGFwcGxlLmNvbT4KKworICAg ICAgICBwbGFpblRleHQoKSBpcyBPKE5eMikKKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtpdC5v cmcvc2hvd19idWcuY2dpP2lkPTExODI4MgorICAgICAgICA8cmRhcjovL3Byb2JsZW0vMTQyODQz NjA+CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZIChPT1BTISkuCisKKyAgICAgICAgKiBl ZGl0aW5nL1RleHRJdGVyYXRvci5jcHA6CisgICAgICAgIChXZWJDb3JlOjpwbGFpblRleHQpOiBM aW5lYXIgZ3Jvd3RoIGZvciBhIHZlY3RvciBkYXRhIHR5cGUgaXMgTyhOXjIpLgorICAgICAgICBE b24ndCBkbyB0aGF0LiBMdWNraWx5LCBTdHJpbmdCdWlsZGVyIGRvZXMgdGhlIHJpZ2h0IHRoaW5n IGF1dG9tYXRpY2FsbHksCisgICAgICAgIHNvIHdlIGNhbiBqdXN0IGRlbGV0ZSBjb2RlLgorCiAy MDEzLTA3LTAxICBBbGV4IENocmlzdGVuc2VuICA8YWNocmlzdGVuc2VuQGFwcGxlLmNvbT4KIAog ICAgICAgICBXaW5kb3dzIHNob3VsZCBiZSBpbmNsdWRlZCBpbiB0aGUgbGlzdCBvZiBwbGF0Zm9y bXMgdGhhdCBjYW4gdXNlIE9wZW5HTCBFUyAyLgpJbmRleDogU291cmNlL1dlYkNvcmUvZWRpdGlu Zy9UZXh0SXRlcmF0b3IuY3BwCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFNvdXJjZS9XZWJDb3JlL2VkaXRpbmcv VGV4dEl0ZXJhdG9yLmNwcAkocmV2aXNpb24gMTUxOTE2KQorKysgU291cmNlL1dlYkNvcmUvZWRp dGluZy9UZXh0SXRlcmF0b3IuY3BwCSh3b3JraW5nIGNvcHkpCkBAIC0yNTAwLDE5ICsyNTAwLDE2 IEBAIGJvb2wgVGV4dEl0ZXJhdG9yOjpnZXRMb2NhdGlvbkFuZExlbmd0aEYKIFN0cmluZyBwbGFp blRleHQoY29uc3QgUmFuZ2UqIHIsIFRleHRJdGVyYXRvckJlaGF2aW9yIGRlZmF1bHRCZWhhdmlv ciwgYm9vbCBpc0Rpc3BsYXlTdHJpbmcpCiB7CiAgICAgLy8gVGhlIGluaXRpYWwgYnVmZmVyIHNp emUgY2FuIGJlIGNyaXRpY2FsIGZvciBwZXJmb3JtYW5jZTogaHR0cHM6Ly9idWdzLndlYmtpdC5v cmcvc2hvd19idWcuY2dpP2lkPTgxMTkyCi0gICAgc3RhdGljIGNvbnN0IHVuc2lnbmVkIGNNYXhT ZWdtZW50U2l6ZSA9IDEgPDwgMTU7CisgICAgc3RhdGljIGNvbnN0IHVuc2lnbmVkIGluaXRpYWxD YXBhY2l0eSA9IDEgPDwgMTU7CiAKICAgICB1bnNpZ25lZCBidWZmZXJMZW5ndGggPSAwOwogICAg IFN0cmluZ0J1aWxkZXIgYnVpbGRlcjsKLSAgICBidWlsZGVyLnJlc2VydmVDYXBhY2l0eShjTWF4 U2VnbWVudFNpemUpOworICAgIGJ1aWxkZXIucmVzZXJ2ZUNhcGFjaXR5KGluaXRpYWxDYXBhY2l0 eSk7CiAgICAgVGV4dEl0ZXJhdG9yQmVoYXZpb3IgYmVoYXZpb3IgPSBkZWZhdWx0QmVoYXZpb3I7 CiAgICAgaWYgKCFpc0Rpc3BsYXlTdHJpbmcpCiAgICAgICAgIGJlaGF2aW9yID0gc3RhdGljX2Nh c3Q8VGV4dEl0ZXJhdG9yQmVoYXZpb3I+KGJlaGF2aW9yIHwgVGV4dEl0ZXJhdG9yRW1pdHNUZXh0 c1dpdGhvdXRUcmFuc2NvZGluZyk7CiAgICAgCiAgICAgZm9yIChUZXh0SXRlcmF0b3IgaXQociwg YmVoYXZpb3IpOyAhaXQuYXRFbmQoKTsgaXQuYWR2YW5jZSgpKSB7Ci0gICAgICAgIGlmIChidWls ZGVyLmNhcGFjaXR5KCkgPCBidWlsZGVyLmxlbmd0aCgpICsgaXQubGVuZ3RoKCkpCi0gICAgICAg ICAgICBidWlsZGVyLnJlc2VydmVDYXBhY2l0eShidWlsZGVyLmNhcGFjaXR5KCkgKyBjTWF4U2Vn bWVudFNpemUpOwotCiAgICAgICAgIGl0LmFwcGVuZFRleHRUb1N0cmluZ0J1aWxkZXIoYnVpbGRl cik7CiAgICAgICAgIGJ1ZmZlckxlbmd0aCArPSBpdC5sZW5ndGgoKTsKICAgICB9Cg==