125608 - NewURI does larger allocations than needed

Status: RESOLVED FIXED

(Core :: Networking, defect)

Description

[Randell Jesup [:jesup] (needinfo me)]

NewURI gets a fair number of hits in jprofs (see bug 124999 for an example).
It does need to allocate, but right now there's a magic "+32" to the allocation.

I have a patch that builds the string in a static buffer if it fits, else
allocates (with space for the worst-case, which is actually +19).  If we didn't
allocate to begin with, we Assign, else we Adopt (as it did before).

Won't make much difference in speed; but not assuming worse-than-worst-case for
the allocation size will save around 25-30 bytes per NewURI (modulo granularity
issues).

Comment 1

[Randell Jesup [:jesup] (needinfo me)]

Attachment: patch to allocate correct sizes

I chose 2048 out of thin air - the size is a tuning parameter, and I'm probably
way over.  To reduce VM/cache spins, it might make sense to use say 256 or 512.
 Note that if the URI is longer than the static buf, we end up doing an
allocation that may be 15ish bytes longer than needed.

Comment 2

[[e-mail]]

platform = all.

Randall: are you going to drive this patch? If so, you should "assign to"
yourself. If not, you can keyword it "helpwanted"

Comment 3

[Randell Jesup [:jesup] (needinfo me)]

Taking the bug.  Darin, any comments?  I'd like to do some more optimizations;
as per your email normalizing seems to be the biggest hit now.

Comment 4

[Darin Fisher]

rjesup: why is static-buf + Assign better than malloc-buf + Adopt?  the Assign
case is bad because it incurs an additional memcpy.  why do that?  if you want
to trim 32 down to 19 that is fine, but otherwise i don't see there being any
win to this at all.  have you run any performance tests?

Comment 5

[Randell Jesup [:jesup] (needinfo me)]

I ran a perf test, but the results were inconclusive, and I don't expect any
perf win from this patch unless I were to do some more serious rewriting to
avoid the extra escape allocations.  As per the keywords, this is a footprint
bug, not a perf bug.  Part of the reason for the static buf was to avoid
allocating worst-case size (+19), while also avoiding adding a entire set of
duplicate if's to figure out the correct size before allocation, which bloats
code and makes maintenance tougher (since they'd need to stay precisely in sync
with the code that adds data to the buffer).

Most of that +19 aren't needed for most NewURI's/SetSpec's.  As per my comment,
I suspect we'll save 25-30 bytes per NewURI.

Comment 6

[Darin Fisher]

rjesup: you're trading minimal bloat (+19 bytes at most per URL) for the runtime
cost of an extra memcpy.  at the very least we should step down from 32 bytes to
19 bytes, but again .. i don't see the justification for adding the extra
mandatory memcpy.  can you provide any sort of figures to confirm that the extra
19 bytes per URL is really hurting us?  maybe it would be worthwhile to improve
our estimate of the URL string size.  or maybe we could call realloc once we're
done building the URL so as to let the allocator potentially reclaim the
additional 19 bytes + whatever padding goes along with it?!?

Comment 7

[Randell Jesup [:jesup] (needinfo me)]

My apologies; the magic number in the source (+32) with no commentary made me
VERY uneasy, and knowing we rarely need much if any of that extra space seemed
like an easy/safe (smallish) footprint win, hardly worth measuring.

memcpy is orders of magnitude cheaper than realloc, plus realloc often saves you
nothing for small differences other than promoting fragmentation.  I _strongly_
doubt any perf loss here from adding a memcpy.  (Plus, weirdo cache effects
might help you while building it.)

I started out (as per above) trying to calculate it exactly and thus avoid the
memcpy, but that's likely to cause maintenance problems (to many conditionals to
keep in sync).

If the number of live NewURI's is circa dozens, it's not a big deal.  If it's
hundreds or thousands (which is quite possible, depending on what's holding onto
them), then 15-20 bytes each is non-trivial (still not a huge amount, but
appreciable).

Severity -> trivial (hadn't set it)
Taking bug for real this time (oops)

Working on Normalize might be a measurable perf win.

Comment 8

[Darin Fisher]

rjesup: you probably want to wait until my nsStandardURL changes from bug 124042
land... else we're likely to collide.

Comment 9

[Darin Fisher]

rjesup: are you still interested in seeing this patch through?  i think it is
probably a good idea, and would love to see this for 1.3 alpha.  what do you think?

Comment 10

[Randell Jesup [:jesup] (needinfo me)]

Sure, I'll update this patch

Comment 11

[Randell Jesup [:jesup] (needinfo me)]

Dredging a bug from the depth of bugzilla...

This bug still exists - magic 32 constant added to URI allocations, then an ASSERT to kill us if for some reason it wasn't enough.  Previous estimation was that 19 is the maximum, but the typical number would be circa 4 or 5.  The code itself has been rewritten for UTF-8 URLs/etc, but the issue remains.

I'm updating the patch, and will also throw in a quick instrumentation to check how much this will actually save (count number of these, amount of savings and high-water mark of actual savings, if I can - that'll be trickier since there no destructor specifically for these).  Given the other changes it should be fairly easy to calculate the actual size needed instead of having to worse-case it or do a memcpy, etc.  Typical savings would be 27-28 bytes per URI.

As far as visible impacts, I don't expect anything large except in degenerate cases, but magic constants on allocations are simply a bad idea and are fodder for future accidental breakage.  There should be a small footprint win, perhaps unmeasurable in normal cases, and no impact on perf.

Comment 12

[Randell Jesup [:jesup] (needinfo me)]

As a quickie test, loading 13 tabs (several of them jprof results, others fairly uninteresting) cause 17000 BuildNormalizedURL()s.  All savings were 27-30 bytes per URL (and only a small handful of 27's).  Not all are active at once!  I need to figure out a way to do that - perhaps add a destructor/change it to a class?

Maximum savings would be ~28*17000 = ~475-500K.

Without the 4 jprofs (very boring set of tabs left) it's only around 2150 URLs.

Still, in some cases (lots-o-links and lots-o-tabs) it will add up; small-footprint devices will care (fennec), and as mentioned it's just plain wrong (and slightly dangerous for maintenance).  I still don't know how many are active at once, but I'd guess the majority of them.

Comment 13

[Randell Jesup [:jesup] (needinfo me)]

Revising target to Mozilla5 (severity to minor), since I plan to land this patch in the near future.  Even a few thousand URLs is 50-100K savings, and with people often having 10's or even 100's of tabs open, the savings could easily be over a MB or two.

Comment 14

[Ryan VanderMeulen [:RyanVM]]

For what it's worth, you've already missed the cutoff for 5.0. Gecko 6.0 will branch on 5-24, so you've got a few weeks still to hit that.

Comment 15

[Randell Jesup [:jesup] (needinfo me)]

Attachment: Up-to-date patch

Typically saves 27-29 bytes per URL.  Small footprint improvement; moderate improvement (hundreds of KB, maybe single-digit MB) if you load link-heavy pages like jprofs.

Comment 16

[Boris Zbarsky [:bzbarsky]]

Do we have any numbers on how this affects the time taken for NS_NewURI?  I'm a heck of a lot worried about the performance of that (which is something we see bigtime in profiles) than with the space usage here.

Do we have any idea how often we actually end up not fitting in the approxLen after this patch?

Comment 17

[Randell Jesup [:jesup] (needinfo me)]

Sorry for the delay - missed that you'd commented.

Perf should be a wash.  EncodeSegmentCount() gets an extra param is about the limit of the perf difference.  I seriously doubt it would be measurable.  Side comment: what's building enough of these to be a perf hotspot??  I'd like to look at why.  Could be, with that type of traffic, you'd get a (very) small perf win by improved cache efficiency from not wasting space.

We should always fit into approxLen - it should now be correct or 1 too big; it was normally 27-30 bytes too big before.  The math I have in there says it's right; we have an NS_ASSERTION as a guarantee (as we always have had).  As you'd expect, I've been unable to make the assertion fail - it's more there to catch someone changing an assumption about URL formatting.

Comment 18

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 532137 [details] [diff] [review]
Up-to-date patch

>-    }
>+}

That looks wrong.  Fix please?

Why are you checking mPort > 0 some places and >= in others?  Seems like you should just check for != -1 in both.

Spaces after the commas for the extra EncodeSegmentCount arg, please.

r=me with those issues fixed.

Comment 19

[Randell Jesup [:jesup] (needinfo me)]

Thanks.  Unset mPort values are -1 here, but ports are positive integers from 0 to 65535, normally - though the RFCs don't put any upper bound of port numbers.  However, all negative numbers are invalid per the RFCs.  (There also are restrictions on use of TCP ports 0-1023.)

RFC 1738:

hostport       = host [ ":" port ]
port           = digits

RFC 3986:
authority     = [ userinfo "@" ] host [ ":" port ]
port          = *DIGIT

So if we're building valid URLs, we need to make sure the port is positive.  We *could* return NS_ERROR_MALFORMED_URI for negative ports - currently the code will ignore negative ports (the old code ignored -1, but would build a url like http://foo:-123/blah, which is invalid).  ::SetPort() has a similar problem with negative ports.

For the moment, I'll leave the negative port problem as it is (and change the test to mPort != -1).  I'll file another bug on negative port numbers.

Comment 20

[Boris Zbarsky [:bzbarsky]]

> We *could* return NS_ERROR_MALFORMED_URI for negative ports

We already do.  The code that sets mPort ends up coming through nsAuthURLParser::ParseServerInfo which does:

626                 *port = buf.ToInteger(&err);
627                 if (NS_FAILED(err) || *port <= 0)
628                     return NS_ERROR_MALFORMED_URI;

> but would build a url like http://foo:-123/blah,

Something tells me you didn't actually test this.... ;)  But now you can, because that string in your comment is linkified by Bugzilla but is NOT a link as far as Gecko is concerned (see lack of "hand" cursor when hovering it, for example).  Precisely because newURI on that string fails.

It looks like you can get a bogus port into mPort via an explicit SetPort call (and maybe we should add a check there).  But the code you're touching can assume that mPort == -1 or mPort > 0.

Comment 21

[Randell Jesup [:jesup] (needinfo me)]

I checked only so far as to be sure there were ways it could end up negative (SetPort()), which there are.

I changed the checks back to != -1 for the checkin.  Port 0 does seem to be allowed by the RFCs in theory, though it normally shouldn't be used and won't work (and really shouldn't in a URL).

Checked in:
http://hg.mozilla.org/mozilla-central/rev/369680a6f40b
but then backed out because the patch had a debug LOG() left in that shouldn't be there (and is bit-rotted in the patch).

Comment 22

[Boris Zbarsky [:bzbarsky]]

> I checked only so far as to be sure there were ways it could end up negative
> (SetPort()), which there are.

But the code you're changing runs before SetPort can happen in all cases, is the point.

Comment 23

[Randell Jesup [:jesup] (needinfo me)]

Attachment: Patch with the offending LOG() removed (and other mods per previous review)

Comment 24

[Randell Jesup [:jesup] (needinfo me)]

Right; SetPort() would be later - mPort get modified, but the buffer already is built.

Should I add a check to SetPort() as well before trying again?

Comment 25

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 535267 [details] [diff] [review]
Patch with the offending LOG() removed (and other mods per previous review)

r=me

Comment 26

[Boris Zbarsky [:bzbarsky]]

Let's patch SetPort in a separate bug, please.

Comment 27

[Randell Jesup [:jesup] (needinfo me)]

I assume there's no way the nsISerializable stuff could somehow insert a negative value - and/or that they also occur after the initial creation.  I haven't been exposed to the nsISerializable stuff thus far.

In any case, it's just my normal paranoia that an assumption (like mPort can't be < -1) might get broken in the future, usually by accident.  It would seem to cost nothing to make the code safer by specifying either mPort > 0 or >= 0 (since 0 is disallowed by ParseServerInfo also, and isn't *really* valid in a URL (though it is valid theoretically).

Will do on SetPort() bug.  Thanks!

Comment 28

[Boris Zbarsky [:bzbarsky]]

nsISerializable stuff is an alternative creation codepath.  If that's happening, the code you're changing won't get hit.

I would be quite happy with you adding something like:

  NS_ABORT_IF_FALSE(mPort > 0 || mPort == -1, "Bogus mPort");

at the two places involved in this patch.

Comment 29

[Randell Jesup [:jesup] (needinfo me)]

SetPort() is bug 659871

Comment 30

[Randell Jesup [:jesup] (needinfo me)]

Checked in again as http://hg.mozilla.org/mozilla-central/rev/2182d1af7522

Comment 31

[Mounir Lamouri (:mounir)]

Backed out due to perma orange on XPCshell tests:
http://tbpl.mozilla.org/?tree=Firefox&rev=0cf4fa02c0f2

Comment 32

[John P Baker]

>+        approxLen += encoder.EncodeSegmentCount(spec, mUsername,  esc_Username,      encUsername,  useEncUsername,1);

Having had to read through this code in the past, I would like to see a space after ',' in the EncodeSegmentCount calls.

Comment 33

[Randell Jesup [:jesup] (needinfo me)]

John: will do on EncodeSegmentCount() when it's ready to try again -- much more carefully - learning my lesson (the hard way) not to jump too fast.  I'm not back up to speed  yet (and more importantly my habits for dealing with the tree aren't re-established yet).  Got a false sense of security by my first couple of large changes going smoothly.

Comment 34

[Boris Zbarsky [:bzbarsky]]

> I would like to see a space after ',' 

Uh... that was one of my review comments see comment 18.  Did that not happen?

Comment 35

[Randell Jesup [:jesup] (needinfo me)]

bz: yes, I think that got lost by mistake when wrestling with hg trying to get the checkin to happen (still not comfortable with the flow of making sure things don't create a new head when getting a checkin ready).  I'll make sure it's corrected.

The failures causing the backout were were assertions hit in test_URIs.js - but running that on my system doesn't result in a failure (hmmm).  

Most of the oranges were on Mac of various flavors; one (perhaps more - I wonder if there's a tool for pulling "tinderbox results started between changeset X and Y") was on Fedora.  But http://tinderbox.mozilla.org/showlog.cgi?log=Firefox/1306482579.1306483618.24993.gz&fulltext=1 and http://tinderbox.mozilla.org/showlog.cgi?log=Firefox/1306481716.1306482867.21876.gz&fulltext=1 which are also Fedora (32 & 64-bit) got no failure from test_URI.js.  Weird.  Probably explains why it looked good to me before checkin; and (I guess) maybe a 'try' run wouldn't have caught it either, though I didn't run one.  I will before it goes in again once I figure this out.

Still investigating (though I'm not likely to get time to look at it before Monday sometime - big barbecue & family visiting).

Comment 36

[Randell Jesup [:jesup] (needinfo me)]

I reproduced the bug, and tracked it down.  EncodeSegmentCount() isn't adding "extraLen" to the size required if the length of the segment was 0 - which fails on "http://#".  But other uses of EncodeSegmentCount() assume the char won't be added on mLen==0, so the logic needs to change slightly.

The tinderboxen it passed were 'opt' tinderboxen - at least the two I referenced, and the failures I checked were debug, so that makes sense, but it's hard to check all the oranges to be sure.  My initial test probably was mistakenly 'opt' (I usually work with opt builds for jprof tests).

I'll be reattaching a patch with the fix (and the spaces fix) after updates and some more testing.

Comment 37

[Randell Jesup [:jesup] (needinfo me)]

Attachment: Updated patch that passed try server

Comment 38

[Randell Jesup [:jesup] (needinfo me)]

That patch passed the try server (http://tbpl.mozilla.org/?tree=Try&rev=d2be1663cf8a).  Spacing is also corrected.

Comment 39

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 536005 [details] [diff] [review]
Updated patch that passed try server

r=me

Comment 40

[Randell Jesup [:jesup] (needinfo me)]

Fix checked in: http://hg.mozilla.org/mozilla-central/rev/a44485cd1682