Bug 107371 – Pre-allocate our CompatHTMLToken Vector since we know how big it will be the the common case

• Status: RESOLVED
• Resolution: WONTFIX
• Component: New Bugs

[Eric Seidel (no email)]

Pre-allocate our CompatHTMLToken Vector since we know how big it will be the the common case

[Eric Seidel (no email)]

Created attachment 183617 [details]
Patch

[Eric Seidel (no email)]

The real wins will come from making HTMLCompactToken smaller.  Then we'll be allocating much less memory each time.

[Adam Barth]

Comment on attachment 183617 [details]
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.

[Eric Seidel (no email)]

I guess we could re-explore this change now that we have fancy telemetry to help us.

[Eric Seidel (no email)]

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()

[Eric Seidel (no email)]

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)));

[Eric Seidel (no email)]

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()

[Eric Seidel (no email)]

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

[Anne van Kesteren]

Threaded HTML parser was removed.