107371 2013-01-19 03:39:50 -0800 Pre-allocate our CompatHTMLToken Vector since we know how big it will be the the common case 2023-12-25 10:05:28 -0800 1 1 1 Unclassified WebKit New Bugs 528+ (Nightly build) Unspecified Unspecified RESOLVED WONTFIX P2 Normal --- 111645 1 eric eric annevk ojan.autocc tonyg webkit.review.bot oldest_to_newest 811373 0 eric 2013-01-19 03:39:50 -0800 Pre-allocate our CompatHTMLToken Vector since we know how big it will be the the common case 811374 1 183617 eric 2013-01-19 03:41:16 -0800 Created attachment 183617 Patch 811375 2 eric 2013-01-19 03:41:48 -0800 The real wins will come from making HTMLCompactToken smaller. Then we'll be allocating much less memory each time. 811434 3 183617 abarth 2013-01-19 11:12:47 -0800 Comment on attachment 183617 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=183617&action=review > Source/WebCore/ChangeLog:10 > + We know the maximum size of this buffer, so pre-allocate it to that size > + for a small savings. This shows us spending slightly less time in malloc, > + but doesn't seem noticable on the final runtime (at least not outside the error bars). I looked at this patch and didn't see much if any change in the benchmark. On other workloads (say those with many scripts), it's not clear to me whether reserving this much space is actually a good thing. If we're only sending off a hundred tokens in a chunk, then reserving space for 4k seems wasteful in terms of memory. Before making this change, I'd like to either see some data showing its a win or be convinced that it's never a loss. 847550 4 eric 2013-03-05 04:22:36 -0800 I guess we could re-explore this change now that we have fancy telemetry to help us. 850612 5 eric 2013-03-07 16:32:58 -0800 Allocs from our current lazy-strategy currently account for about 1% of total time: Running Time Self Symbol Name 51.2ms 5.7% 51.2 WTF::fastMalloc(unsigned long) 8.7ms 0.9% 0.0 WTF::Vector<WebCore::CompactHTMLToken::Attribute, 0ul>::Vector(WTF::Vector<WebCore::CompactHTMLToken::Attribute, 0ul> const&) 5.8ms 0.6% 0.0 WTF::VectorMover<false, WebCore::CompactHTMLToken>::move(WebCore::CompactHTMLToken const*, WebCore::CompactHTMLToken const*, WebCore::CompactHTMLToken*) 5.8ms 0.6% 0.0 WTF::Vector<WebCore::CompactHTMLToken, 0ul>::reserveCapacity(unsigned long) 5.8ms 0.6% 0.0 void WTF::Vector<WebCore::CompactHTMLToken, 0ul>::appendSlowCase<WebCore::CompactHTMLToken>(WebCore::CompactHTMLToken const&) 5.8ms 0.6% 0.0 WebCore::BackgroundHTMLParser::pumpTokenizer() 850614 6 eric 2013-03-07 16:34:46 -0800 Related: abarth suggests that we at least set: static const size_t pendingTokenLimit = 1000; to align with one of the Vector pre-allocation sizes. This is the vector algorithm: reserveCapacity(std::max(newMinCapacity, std::max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1))); 850619 7 eric 2013-03-07 16:40:52 -0800 Actually this is worse than I thought. We have an extra 2.5% of total time spent copying CompactHTMLTokens around these growing vectors: Running Time Self Symbol Name 22.6ms 2.5% 0.0 WTF::Vector<WebCore::CompactHTMLToken, 0ul>::reserveCapacity(unsigned long) 22.6ms 2.5% 0.0 void WTF::Vector<WebCore::CompactHTMLToken, 0ul>::appendSlowCase<WebCore::CompactHTMLToken>(WebCore::CompactHTMLToken const&) 22.6ms 2.5% 0.0 WebCore::BackgroundHTMLParser::pumpTokenizer() 851825 8 eric 2013-03-09 14:02:35 -0800 Assuming I'm understanding the vector growth curve correctly, I'm not sure it's the one we want: https://docs.google.com/spreadsheet/ccc?key=0AlC4tS7Ao1fIdE1xa1pRc3Y3R2FRMGJoeGw2ZWk0dVE#gid=0 2001930 9 annevk 2023-12-25 10:05:28 -0800 Threaded HTML parser was removed. 183617 2013-01-19 03:41:16 -0800 2013-01-19 11:12:47 -0800 Patch bug-107371-20130119033814.patch text/plain 1716 eric U3VidmVyc2lvbiBSZXZpc2lvbjogMTQwMjM5CmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggNjZhZDNhMzVmNjg2MmJi NjU1MjY0NjhmZTY3NjRhZGVjZWQ3MDE4OS4uZTU1NDVmODRkNTU5YzBlZWYwYzM3ZjM3OWYxMjU1 NmY5M2ZlZTRkYiAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSw1ICsxLDE5IEBACiAyMDEzLTAxLTE5ICBFcmlj IFNlaWRlbCAgPGVyaWNAd2Via2l0Lm9yZz4KIAorICAgICAgICBQcmUtYWxsb2NhdGUgb3VyIENv bXBhdEhUTUxUb2tlbiBWZWN0b3Igc2luY2Ugd2Uga25vdyBob3cgYmlnIGl0IHdpbGwgYmUgdGhl IHRoZSBjb21tb24gY2FzZQorICAgICAgICBodHRwczovL2J1Z3Mud2Via2l0Lm9yZy9zaG93X2J1 Zy5jZ2k/aWQ9MTA3MzcxCisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZIChPT1BTISkuCisK KyAgICAgICAgV2Uga25vdyB0aGUgbWF4aW11bSBzaXplIG9mIHRoaXMgYnVmZmVyLCBzbyBwcmUt YWxsb2NhdGUgaXQgdG8gdGhhdCBzaXplCisgICAgICAgIGZvciBhIHNtYWxsIHNhdmluZ3MuICBU aGlzIHNob3dzIHVzIHNwZW5kaW5nIHNsaWdodGx5IGxlc3MgdGltZSBpbiBtYWxsb2MsCisgICAg ICAgIGJ1dCBkb2Vzbid0IHNlZW0gbm90aWNhYmxlIG9uIHRoZSBmaW5hbCBydW50aW1lIChhdCBs ZWFzdCBub3Qgb3V0c2lkZSB0aGUgZXJyb3IgYmFycykuCisKKyAgICAgICAgKiBodG1sL3BhcnNl ci9CYWNrZ3JvdW5kSFRNTFBhcnNlci5jcHA6CisgICAgICAgIChXZWJDb3JlOjpCYWNrZ3JvdW5k SFRNTFBhcnNlcjo6cHVtcFRva2VuaXplcik6CisKKzIwMTMtMDEtMTkgIEVyaWMgU2VpZGVsICA8 ZXJpY0B3ZWJraXQub3JnPgorCiAgICAgICAgIEFkZCBhIGhlbHBlciBmdW5jdGlvbiBmb3IgZ2V0 dGluZyBzdHJpbmdzIGZyb20gdG9rZW5zIChhbmQgbWFrZSBpdCA4LWJpdCBhd2FyZSkKICAgICAg ICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTEwNzM2OAogCmRpZmYg LS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9odG1sL3BhcnNlci9CYWNrZ3JvdW5kSFRNTFBhcnNlci5j cHAgYi9Tb3VyY2UvV2ViQ29yZS9odG1sL3BhcnNlci9CYWNrZ3JvdW5kSFRNTFBhcnNlci5jcHAK aW5kZXggYWYwZDc4ZjMwNzE5MjkzNjdiMDc4MjVhNmZjNTM0NWEwMjE5NzhlNi4uNDdlNDI5NTY2 M2MxODc3M2Q2YTljMWJkYjFjYjlkNDhhMDRkOTQ4NyAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNv cmUvaHRtbC9wYXJzZXIvQmFja2dyb3VuZEhUTUxQYXJzZXIuY3BwCisrKyBiL1NvdXJjZS9XZWJD b3JlL2h0bWwvcGFyc2VyL0JhY2tncm91bmRIVE1MUGFyc2VyLmNwcApAQCAtMTIzLDYgKzEyMyw4 IEBAIHZvaWQgQmFja2dyb3VuZEhUTUxQYXJzZXI6OnB1bXBUb2tlbml6ZXIoKQogICAgIGlmICht X2lzUGF1c2VkV2FpdGluZ0ZvclNjcmlwdHMpCiAgICAgICAgIHJldHVybjsKIAorICAgIG1fcGVu ZGluZ1Rva2Vucy5yZXNlcnZlQ2FwYWNpdHkocGVuZGluZ1Rva2VuTGltaXQpOworCiAgICAgd2hp bGUgKG1fdG9rZW5pemVyLT5uZXh0VG9rZW4obV9pbnB1dC5jdXJyZW50KCksIG1fdG9rZW4pKSB7 CiAgICAgICAgIG1fcGVuZGluZ1Rva2Vucy5hcHBlbmQoQ29tcGFjdEhUTUxUb2tlbihtX3Rva2Vu KSk7CiAK