Bug 107371 - Pre-allocate our CompatHTMLToken Vector since we know how big it will be the the common case
Summary: Pre-allocate our CompatHTMLToken Vector since we know how big it will be the ...
Status: NEW
Alias: None
Product: WebKit
Classification: Unclassified
Component: New Bugs (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Eric Seidel (no email)
URL:
Keywords:
Depends on:
Blocks: 111645
  Show dependency treegraph
 
Reported: 2013-01-19 03:39 PST by Eric Seidel (no email)
Modified: 2013-03-09 14:02 PST (History)
3 users (show)

See Also:


Attachments
Patch (1.68 KB, patch)
2013-01-19 03:41 PST, Eric Seidel (no email)
abarth: review-
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
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]
Patch
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]
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.
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:
https://docs.google.com/spreadsheet/ccc?key=0AlC4tS7Ao1fIdE1xa1pRc3Y3R2FRMGJoeGw2ZWk0dVE#gid=0