Bug 107371

Summary: Pre-allocate our CompatHTMLToken Vector since we know how big it will be the the common case
Product: WebKit Reporter: Eric Seidel (no email) <eric>
Component: New BugsAssignee: Eric Seidel (no email) <eric>
Status: NEW ---    
Severity: Normal CC: ojan.autocc, tonyg, webkit.review.bot
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on:    
Bug Blocks: 111645    
Description Flags
Patch abarth: review-

Description Eric Seidel (no email) 2013-01-19 03:39:50 PST
Pre-allocate our CompatHTMLToken Vector since we know how big it will be the the common case
Comment 1 Eric Seidel (no email) 2013-01-19 03:41:16 PST
Created attachment 183617 [details]
Comment 2 Eric Seidel (no email) 2013-01-19 03:41:48 PST
The real wins will come from making HTMLCompactToken smaller.  Then we'll be allocating much less memory each time.
Comment 3 Adam Barth 2013-01-19 11:12:47 PST
Comment on attachment 183617 [details]

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.
Comment 4 Eric Seidel (no email) 2013-03-05 04:22:36 PST
I guess we could re-explore this change now that we have fancy telemetry to help us.
Comment 5 Eric Seidel (no email) 2013-03-07 16:32:58 PST
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()
Comment 6 Eric Seidel (no email) 2013-03-07 16:34:46 PST
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)));
Comment 7 Eric Seidel (no email) 2013-03-07 16:40:52 PST
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()
Comment 8 Eric Seidel (no email) 2013-03-09 14:02:35 PST
Assuming I'm understanding the vector growth curve correctly, I'm not sure it's the one we want: