[url] Reserve output buffer for various URL parsing paths

[url] Reserve output buffer for various URL parsing paths

This patch moves buffer reservation to the internals of //url code, 
whereas previously this was the caller's (e.g. GURL, KURL) 
responsibility.

The reason for this change was that KURL was *not* doing any buffer reservation,
so a naive exponential buffer growth algorithm was being used. Rather than
expecting all callers to be bug free, this patch opts to always do the right thing. 

For a ~1.5MB data URL, this yields a ~13% improvement of
DoCanonicalizePathComponent<char, unsigned>, which translates to a ~8%
improvement for the overall KURL::init.

BUG=657978
Review-Url: https://codereview.chromium.org/2617173003
Cr-Commit-Position: refs/heads/master@{#444558}
Committed: https://chromium.googlesource.com/chromium/src/+/96b890e58809d310e0b70029913e0f72a00a4414

[Charlie Harrison, 2017-01-06 20:03:13]

The CQ bit was checked by csharrison@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-01-06 20:03:52]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Charlie Harrison, 2017-01-06 20:29:38]

The CQ bit was checked by csharrison@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-01-06 20:29:46]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Charlie Harrison, 2017-01-06 20:29:50]

csharrison@chromium.org changed reviewers:
+ brettw@chromium.org

[Charlie Harrison, 2017-01-06 20:29:50]

Brett, is this reasonable? I think huge data URLs are where we'd appreciate this
optimization the most, so I only implemented this for the path URL case.

[commit-bot: I haz the power, 2017-01-06 21:51:54]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-01-06 21:51:55]

Dry run: This issue passed the CQ dry run.

[brettw, 2017-01-07 23:20:00]

I think it's a good idea to be reserving appropriate space. But I think we
should do so consistently.

Right now the GURL object does std::string::reserve based on the size of the
input before it calls into the canonicalizer.

I never realized KURL didn't do this. It probably makes sense to add this to all
the Canonicalize and ReplaceComponents entry points and then remove the calls in
the GURL object.

[Charlie Harrison, 2017-01-07 23:53:32]

SGTM I'll try that.

[Charlie Harrison, 2017-01-09 16:51:33]

The CQ bit was checked by csharrison@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-01-09 16:51:52]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Charlie Harrison, 2017-01-09 17:33:59]

Description was changed from

==========
[url] Reserve output buffer for "Path" URLs (data/javascript)

This yields one extra branch, but avoids any extra buffer growth during
canonicalization for ascii URLs.

For a ~1.5MB data URL, this yields a ~13% improvement of
DoCanonicalizePathComponent<char, unsigned>, which translates to a ~8%
improvement for the overall KURL::init.

BUG=657978
==========

to

==========
[url] Reserve output buffer for various URL parsing paths

This patch moves buffer reservation to the internals of //url code, whereas
previously this was the caller's (e.g. GURL, KURL) responsibility.

The reason for this change was that KURL was *not* doing any buffer reservation,
so a naive exponential buffer growth algorithm was being used. Rather than
expecting all callers to be bug free, this patch opts to always do the right
thing. 

For a ~1.5MB data URL, this yields a ~13% improvement of
DoCanonicalizePathComponent<char, unsigned>, which translates to a ~8%
improvement for the overall KURL::init.

BUG=657978
==========

[Charlie Harrison, 2017-01-09 18:03:36]

Ok! Here's an updated patch which moves all size reservation into internal url
parsing code.

All code paths should be at least as performant as the GURL reservation code
(i.e. blindly reserving spec_.length() regardless of operation), but please let
me know if you think I've missed something.

Some code paths (i.e. resolving relative URLs) got a bit more love, as we know
that we'll need to resolve base length + relative length in many cases. I
decided to give this more attention because this is the hot path in KURL,
whereas I think ReplaceComponent is not called as often.

PTAL?

[Charlie Harrison, 2017-01-18 17:21:42]

Brett: friendly ping

[Charlie Harrison, 2017-01-18 17:22:55]

Description was changed from

==========
[url] Reserve output buffer for various URL parsing paths

This patch moves buffer reservation to the internals of //url code, whereas
previously this was the caller's (e.g. GURL, KURL) responsibility.

The reason for this change was that KURL was *not* doing any buffer reservation,
so a naive exponential buffer growth algorithm was being used. Rather than
expecting all callers to be bug free, this patch opts to always do the right
thing. 

For a ~1.5MB data URL, this yields a ~13% improvement of
DoCanonicalizePathComponent<char, unsigned>, which translates to a ~8%
improvement for the overall KURL::init.

BUG=657978
==========

to

==========
[url] Reserve output buffer for various URL parsing paths

This patch moves buffer reservation to the internals of //url code, 
whereas previously this was the caller's (e.g. GURL, KURL) 
responsibility.

The reason for this change was that KURL was *not* doing any buffer reservation,
so a naive exponential buffer growth algorithm was being used. Rather than
expecting all callers to be bug free, this patch opts to always do the right
thing. 

For a ~1.5MB data URL, this yields a ~13% improvement of
DoCanonicalizePathComponent<char, unsigned>, which translates to a ~8%
improvement for the overall KURL::init.

BUG=657978
==========

[brettw, 2017-01-18 20:50:49]

Sorry!

[brettw, 2017-01-18 21:12:28]

https://codereview.chromium.org/2617173003/diff/80001/url/url_canon_relative.cc
File url/url_canon_relative.cc (right):

https://codereview.chromium.org/2617173003/diff/80001/url/url_canon_relative....
url/url_canon_relative.cc:291: std::max(path.end(), std::max(query.end(),
ref.end())) + 32);
You copied "32" from the old code. But when we start using this for all URLs, I
think this might be unnecessarily large since Blink does so much more URL
resolving than GURL does. Typically we don't expand the URL much, if at all, and
adding 32 bytes to each one in Blink will be a lot of memory. I think we should
do 8 for each one in this change. If somebody wants to do the analysis we can
consider expanding from there.

https://codereview.chromium.org/2617173003/diff/80001/url/url_canon_relative....
url/url_canon_relative.cc:407:
output->ReserveSizeIfNeeded(replacements.components().Length() + 32);
I don't follow this comment. In this case the input string will look like
"//gstatic.com/foo/bar.gif" and I think relative_component will normally be the
entire input string.

So I would expect to need to add
base_parsed.CountCharactersBefore(Parsed::USERNAME, false) to account for the
old scheme not being replaced.

[Charlie Harrison, 2017-01-18 21:30:38]

Thanks for the review, no worries about the slowness I sorta forgot about this
one too :P

https://codereview.chromium.org/2617173003/diff/80001/url/url_canon_relative.cc
File url/url_canon_relative.cc (right):

https://codereview.chromium.org/2617173003/diff/80001/url/url_canon_relative....
url/url_canon_relative.cc:291: std::max(path.end(), std::max(query.end(),
ref.end())) + 32);
On 2017/01/18 21:12:27, brettw (ping after 24h) wrote:
> You copied "32" from the old code. But when we start using this for all URLs,
I
> think this might be unnecessarily large since Blink does so much more URL
> resolving than GURL does. Typically we don't expand the URL much, if at all,
and
> adding 32 bytes to each one in Blink will be a lot of memory. I think we
should
> do 8 for each one in this change. If somebody wants to do the analysis we can
> consider expanding from there.

SGTM

https://codereview.chromium.org/2617173003/diff/80001/url/url_canon_relative....
url/url_canon_relative.cc:407:
output->ReserveSizeIfNeeded(replacements.components().Length() + 32);
On 2017/01/18 21:12:27, brettw (ping after 24h) wrote:
> I don't follow this comment. In this case the input string will look like
> "//gstatic.com/foo/bar.gif" and I think relative_component will normally be
the
> entire input string.
> 
> So I would expect to need to add
> base_parsed.CountCharactersBefore(Parsed::USERNAME, false) to account for the
> old scheme not being replaced.

Just read through the code and I think you're right. For some reason when I
wrote this code I thought relative_component.begin was indexed off of the end of
the base URL.

[Charlie Harrison, 2017-01-18 21:31:06]

oh, and PTAL

[brettw, 2017-01-18 21:32:41]

lgtm

[Charlie Harrison, 2017-01-18 21:33:45]

The CQ bit was checked by csharrison@chromium.org

[commit-bot: I haz the power, 2017-01-18 21:34:29]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-01-19 00:13:38]

CQ is committing da patch.

Bot data: {"patchset_id": 100001, "attempt_start_ts": 1484775225463010,
"parent_rev": "b28a77ff0b6d09ba31cafb8029eda163accae3c8", "commit_rev":
"96b890e58809d310e0b70029913e0f72a00a4414"}

[commit-bot: I haz the power, 2017-01-19 00:14:14]

Description was changed from

==========
[url] Reserve output buffer for various URL parsing paths

This patch moves buffer reservation to the internals of //url code, 
whereas previously this was the caller's (e.g. GURL, KURL) 
responsibility.

The reason for this change was that KURL was *not* doing any buffer reservation,
so a naive exponential buffer growth algorithm was being used. Rather than
expecting all callers to be bug free, this patch opts to always do the right
thing. 

For a ~1.5MB data URL, this yields a ~13% improvement of
DoCanonicalizePathComponent<char, unsigned>, which translates to a ~8%
improvement for the overall KURL::init.

BUG=657978
==========

to

==========
[url] Reserve output buffer for various URL parsing paths

This patch moves buffer reservation to the internals of //url code, 
whereas previously this was the caller's (e.g. GURL, KURL) 
responsibility.

The reason for this change was that KURL was *not* doing any buffer reservation,
so a naive exponential buffer growth algorithm was being used. Rather than
expecting all callers to be bug free, this patch opts to always do the right
thing. 

For a ~1.5MB data URL, this yields a ~13% improvement of
DoCanonicalizePathComponent<char, unsigned>, which translates to a ~8%
improvement for the overall KURL::init.

BUG=657978

Review-Url: https://codereview.chromium.org/2617173003
Cr-Commit-Position: refs/heads/master@{#444558}
Committed:
https://chromium.googlesource.com/chromium/src/+/96b890e58809d310e0b70029913e...
==========

[commit-bot: I haz the power, 2017-01-19 00:14:15]

Committed patchset #6 (id:100001) as
https://chromium.googlesource.com/chromium/src/+/96b890e58809d310e0b70029913e...

[Charlie Harrison, 2017-01-19 20:36:04]

This patch misses something key:
For callers that choose to pre-allocate their canon outputs, this patch
regresses performance because we immediately copy everything over into a +8
sized buffer (if the caller didn't use any extra padding).

I'll upload a patch addressing this by only adding the +8 buffer if we need to
resize.