10818 2006-09-11 19:38:34 -0700 String::append does 2 full copies instead of 1 (or zero!) 2007-10-31 01:32:01 -0700 1 1 1 Unclassified WebKit Platform 420+ Mac OS X 10.4 RESOLVED FIXED P2 Normal --- 1 eric ap ap oldest_to_newest 55277 0 eric 2006-09-11 19:38:34 -0700 I'm surprised this hasn't been noticed before. It seems String::append is about as inefficient as possible. String::append results in 2 full copies of the string being made. That's one more than necessary. If String was even smarter, it would pre-allocate a certain amount of extra space, resulting in 0 necessary copies. Safari hung for several minutes loading a 30MB SVG file. Pretty much all of that time was spent copying strings for String::append: 0.0% 100.0% WebCore WebCore::Frame::addData(char const*, int) 0.0% 100.0% WebCore WebCore::Frame::write(char const*, int) 0.0% 100.0% WebCore WebCore::Decoder::decode(char const*, unsigned long) 0.0% 100.0% WebCore WebCore::TextDecoder::decode(char const*, unsigned long, bool) 0.0% 100.0% WebCore WebCore::TextDecoder::checkForBOM(char const*, unsigned long, bool) 0.6% 100.0% WebCore WebCore::TextCodecICU::decode(char const*, unsigned long, bool) 0.5% 99.4% WebCore WebCore::TextCodec::appendOmittingBOM(WebCore::String&, unsigned short const*, unsigned long) 0.0% 98.8% WebCore WebCore::String::append(WebCore::String const&) 0.0% 49.8% WebCore WebCore::StringImpl::copy() const 48.9% 48.9% WebCore WebCore::StringImpl::append(WebCore::StringImpl const*) 40959 1 eric 2006-12-21 03:52:48 -0800 Wow. This is still the case: void String::append(const String &str) { if (str.m_impl) { if (!m_impl) { // ### FIXME!!! m_impl = str.m_impl; return; } m_impl = m_impl->copy(); m_impl->append(str.m_impl.get()); } } 59847 2 16947 ap 2007-10-30 07:15:47 -0700 Created attachment 16947 proposed fix Granted, String::append() is not about performance, but I guess someone has to fix this, after all :-) 59906 3 16947 darin 2007-10-30 22:56:11 -0700 Comment on attachment 16947 proposed fix r=me But these are so inefficient we might some day decide to get rid of them just to encourage people to use some other idiom. 59907 4 eric 2007-10-30 22:58:44 -0700 I can outfit you with the SVG in question if you like. maciej and olliej probably have a copy as well, it's called "plan". 59914 5 ap 2007-10-31 01:32:01 -0700 Committed revision 27300. 16947 2007-10-30 07:15:47 -0700 2007-10-30 22:56:11 -0700 proposed fix 10818r1_patch.txt text/plain 2777 ap SW5kZXg6IFdlYkNvcmUvQ2hhbmdlTG9nCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFdlYkNvcmUvQ2hhbmdlTG9n CShyZXZpc2lvbiAyNzI1NikKKysrIFdlYkNvcmUvQ2hhbmdlTG9nCSh3b3JraW5nIGNvcHkpCkBA IC0xLDMgKzEsMTggQEAKKzIwMDctMTAtMzAgIEFsZXhleSBQcm9za3VyeWFrb3YgIDxhcEB3ZWJr aXQub3JnPgorCisgICAgICAgIFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAg IGh0dHA6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTEwODE4CisgICAgICAgIFN0 cmluZzo6YXBwZW5kIGRvZXMgMiBmdWxsIGNvcGllcyBpbnN0ZWFkIG9mIDEgKG9yIHplcm8hKQor CisgICAgICAgIE5vIGNoYW5nZSBpbiBmdW5jdGlvbmFsaXR5LCB0aHVzIG5vIHRlc3QuCisKKyAg ICAgICAgKiBwbGF0Zm9ybS9TdHJpbmcuY3BwOgorICAgICAgICAoV2ViQ29yZTo6U3RyaW5nOjph cHBlbmQpOiBSZXdyb3RlIHRvIGNvcHkgb25jZS4gQWxzbyByZW1vdmVkIGFuIGFuY2llbnQKKyAg ICAgICAgRklYTUUgdGhhdCBkb2Vzbid0IHNlZW0gdG8gbWFrZSBhbnkgc2Vuc2UuIE5vdGUgdGhh dCBhcHBlbmQoKSBiZWhhdmlvciBkb2Vzbid0IAorICAgICAgICBtYXRjaCBkb2N1bWVudGVkIFN0 cmluZyBiZWhhdmlvciAoIm1vZGlmaWNhdGlvbnMgdG8gb25lIGluc3RhbmNlIHdpbGwKKyAgICAg ICAgYWxzbyBtb2RpZnkgYWxsIG90aGVycyIpLCBidXQgdGhlcmUgYXJlIGEgbG90IG9mIG1ldGhv ZHMgdGhhdCBkb24ndC4KKwogMjAwNy0xMC0yOSAgQmV0aCBEYWtpbiAgPGJkYWtpbkBhcHBsZS5j b20+CiAKICAgICAgICAgUmV2aWV3ZWQgYnkgSHlhdHQuCkluZGV4OiBXZWJDb3JlL3BsYXRmb3Jt L1N0cmluZy5jcHAKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PQotLS0gV2ViQ29yZS9wbGF0Zm9ybS9TdHJpbmcuY3BwCShy ZXZpc2lvbiAyNzI1MykKKysrIFdlYkNvcmUvcGxhdGZvcm0vU3RyaW5nLmNwcAkod29ya2luZyBj b3B5KQpAQCAtOTksMzQgKzk5LDM2IEBAIFN0cmluZzo6U3RyaW5nKGNvbnN0IGNoYXIqIHN0ciwg dW5zaWduZWQKIHZvaWQgU3RyaW5nOjphcHBlbmQoY29uc3QgU3RyaW5nICZzdHIpCiB7CiAgICAg aWYgKHN0ci5tX2ltcGwpIHsKLSAgICAgICAgaWYgKCFtX2ltcGwpIHsKLSAgICAgICAgICAgIC8v ICMjIyBGSVhNRSEhIQorICAgICAgICBpZiAobV9pbXBsKSB7CisgICAgICAgICAgICBWZWN0b3I8 VUNoYXI+IG5ld0NoYXJhY3RlcnMobV9pbXBsLT5sZW5ndGgoKSArIHN0ci5sZW5ndGgoKSk7Cisg ICAgICAgICAgICBtZW1jcHkobmV3Q2hhcmFjdGVycy5kYXRhKCksIG1faW1wbC0+Y2hhcmFjdGVy cygpLCBtX2ltcGwtPmxlbmd0aCgpICogc2l6ZW9mKFVDaGFyKSk7CisgICAgICAgICAgICBtZW1j cHkobmV3Q2hhcmFjdGVycy5kYXRhKCkgKyBtX2ltcGwtPmxlbmd0aCgpLCBzdHIuY2hhcmFjdGVy cygpLCBzdHIubGVuZ3RoKCkgKiBzaXplb2YoVUNoYXIpKTsKKyAgICAgICAgICAgIG1faW1wbCA9 IFN0cmluZ0ltcGw6OmFkb3B0KG5ld0NoYXJhY3RlcnMpOworICAgICAgICB9IGVsc2UKICAgICAg ICAgICAgIG1faW1wbCA9IHN0ci5tX2ltcGw7Ci0gICAgICAgICAgICByZXR1cm47Ci0gICAgICAg IH0KLSAgICAgICAgbV9pbXBsID0gbV9pbXBsLT5jb3B5KCk7Ci0gICAgICAgIG1faW1wbC0+YXBw ZW5kKHN0ci5tX2ltcGwuZ2V0KCkpOwogICAgIH0KIH0KIAogdm9pZCBTdHJpbmc6OmFwcGVuZChj aGFyIGMpCiB7Ci0gICAgaWYgKCFtX2ltcGwpCisgICAgaWYgKG1faW1wbCkgeworICAgICAgICBW ZWN0b3I8VUNoYXI+IG5ld0NoYXJhY3RlcnMobV9pbXBsLT5sZW5ndGgoKSArIDEpOworICAgICAg ICBtZW1jcHkobmV3Q2hhcmFjdGVycy5kYXRhKCksIG1faW1wbC0+Y2hhcmFjdGVycygpLCBtX2lt cGwtPmxlbmd0aCgpICogc2l6ZW9mKFVDaGFyKSk7CisgICAgICAgIG5ld0NoYXJhY3RlcnNbbV9p bXBsLT5sZW5ndGgoKV0gPSBjOworICAgICAgICBtX2ltcGwgPSBTdHJpbmdJbXBsOjphZG9wdChu ZXdDaGFyYWN0ZXJzKTsKKyAgICB9IGVsc2UKICAgICAgICAgbV9pbXBsID0gbmV3IFN0cmluZ0lt cGwoJmMsIDEpOwotICAgIGVsc2UgewotICAgICAgICBtX2ltcGwgPSBtX2ltcGwtPmNvcHkoKTsK LSAgICAgICAgbV9pbXBsLT5hcHBlbmQoYyk7Ci0gICAgfQogfQogCiB2b2lkIFN0cmluZzo6YXBw ZW5kKFVDaGFyIGMpCiB7Ci0gICAgaWYgKCFtX2ltcGwpCisgICAgaWYgKG1faW1wbCkgeworICAg ICAgICBWZWN0b3I8VUNoYXI+IG5ld0NoYXJhY3RlcnMobV9pbXBsLT5sZW5ndGgoKSArIDEpOwor ICAgICAgICBtZW1jcHkobmV3Q2hhcmFjdGVycy5kYXRhKCksIG1faW1wbC0+Y2hhcmFjdGVycygp LCBtX2ltcGwtPmxlbmd0aCgpICogc2l6ZW9mKFVDaGFyKSk7CisgICAgICAgIG5ld0NoYXJhY3Rl cnNbbV9pbXBsLT5sZW5ndGgoKV0gPSBjOworICAgICAgICBtX2ltcGwgPSBTdHJpbmdJbXBsOjph ZG9wdChuZXdDaGFyYWN0ZXJzKTsKKyAgICB9IGVsc2UKICAgICAgICAgbV9pbXBsID0gbmV3IFN0 cmluZ0ltcGwoJmMsIDEpOwotICAgIGVsc2UgewotICAgICAgICBtX2ltcGwgPSBtX2ltcGwtPmNv cHkoKTsKLSAgICAgICAgbV9pbXBsLT5hcHBlbmQoYyk7Ci0gICAgfQogfQogCiBTdHJpbmcgb3Bl cmF0b3IrKGNvbnN0IFN0cmluZyYgYSwgY29uc3QgU3RyaW5nJiBiKQo=