70743 - nsIURI::SchemeIs() should take a const char* so it is extensible.

Status: RESOLVED FIXED

(Core :: Networking: Cache, defect)

Description

[Judson Valeski]

currently IsScheme takes a hardcoded enum to do a scheme query. this methodology 
 is not extensible because the schemes are hardcoded and other protocols cannot 
use this.  If the param were an nsIAtom, we maintain extensibility.

Comment 1

[Gagan]

its delibrate. The intent is for optimizing on common cases. For all of the rest
you can always getScheme and do the comparison yourself. 

Comment 2

[Judson Valeski]

understood, but nsIAtom can be used for the optimization purpose, and it's also 
extensible.

Comment 3

[Judson Valeski]

changing comment from: "nsIURI::IsScheme() should take an nsIAtom so it is
extensible.
"

After talking this through at the API review meeting (see
http://www.mozilla.org/projects/embedding/apiReviewNotes.html#nsIURI ), we
concluded that the method should take a "const char*", do a first char check,
then a string compare. Something like...

uriImpl::schemeIs(const char * aScheme) {
 if (*aScheme != *mScheme) return PR_FALSE;
 if (PL_strcmp(aScheme, mScheme)) return PR_FALSE;
 return PR_TRUE;
}

This will allow it to be extensible, as well as performant.

Comment 4

[Gagan]

The whole purpose of schemeIs was to provide a faster compare than the string 
compares, purely for performance reasons. The 'hard-coded' list of schemes is 
there for a good reason-- these compares are needed frequently and so reducing 
the compares to that of an int made sense. I still am not convinced that we need 
to change this signature. 

Comment 5

[Judson Valeski]

taking bug, I have a patch for this and will post it here after my build completes.

Comment 6

[Gagan]

jud: it doesn't matter who has the bug. Its more important that the change you 
are proposing is correct.

Comment 7

[Judson Valeski]

agreed. I believe I've stated my case though, and I haven't heard rebuttal. it
looks like the original optimization was made partially because of some
strduping that was going on. strduping + strcmp would indeed be heavy. I'm
posting a patch that does no strduping, and rarely does strcmps. Regardless, the
api as it stands cannot be extended at run time.

Comment 8

[Judson Valeski]

Attachment: patch to nsIURI.idl, callers of schemeIs() and implementors of schemeIs()

Comment 9

[Judson Valeski]

patch does the following:
1. updates callers of ->schemeIs() to use regular strings instead of the enum types.
2. updates implementors of ::SchemeIs() to do the char * comparison. these impls
do a first char verification check first to avoid strcmp as much as possible.
3. nsHTTPHandler - added a char* mScheme protected memeber variable so
inheriting classes (nsHTTPSHandler) can replace the scheme.
4. nsHTTPSHandler - removed static create method in favor of the generic init
constructor (in nsNetModule.cpp). Added an Init() method which calls
nsHTTPHandler::Init() and replaces the mScheme w/ "https"

Comment 10

[rpotts (gone)]

hey gagan,

Basically, what the change involves is removing the hardcoded enumeration and 
performing a byte comparision (using an extensible string) rather than an 
unsigned long comparision (using a hardcoded enumeration).

I *really* doubt if anyone will see the performance difference between the byte 
and long comparisions :-)  However, the result is *huge* because it opens up a 
*key* API for future extensibility!

There is absolutely no reason why some protocols should be more "special" than 
others in our APIs...

-- rick

Comment 11

[rpotts (gone)]

sr=rpotts

Comment 12

[Gagan]

My only reasoning for keeping some cases as special was becuz of the frequency 
with which they are used. Other than that, the patch looks ok to me. I just had 
one concern-- why don't we ensure mScheme to be lower case in nsSimpleURI just 
like nsStdURL instead of the mLower check? Seems like it would be easiar to do 
the same stuff in nsSimpleURI. 

Comment 13

[Judson Valeski]

yea, I had the same question/concern buzzing around in my mind. the only reason
I left it was that I was thinking that it's *possible* that some simple URI
usage may need to conserve the the case of the scheme? I mean, we know our
stdURL impl and its usage wants lower-case, but what about UR_I_s? Being the
more generic, conceptually, of the two, is it legal for lower-case schemes?

I'd love to get rid of the mLower var and do a toLower on the scheme of
nsSimpleURI, but I'm not sure if that would hurt some simple URI users; thoughts?

Comment 14

[Gagan]

all uri schemes are expected to be case-insensitive (simple or otherwise) and so 
doing the lower case makes sense. with that change r=gagan

Comment 15

[Judson Valeski]

fix is in. thanks all.

Comment 16

[Mike Shaver (:shaver emeritus)]

I was in this bug looking to see if the ``id (*i_Scheme...'' thing was in the
reviewed patch, and noticed your wacky byte-compare-then-string-compare thing?

What's the deal?  If you want a fast string compare:

 - use the system strcasecmp, rather than going through the silly extra
   layers of PL_strcasecmp

 - don't check the first byte again in strcmp, once you've checked it inline!

(I think PL_str* should be a shooting offense, myself, but hey.)

I'm also not thrilled about seeing code that could never have been compiled by
the author, and was obviously not compiled or read carefully by the reviewers,
being slammed into the tree the day before 0.8.1.  Again, what gives?

Comment 17

[Judson Valeski]

< use the system strcasecmp, rather than going through the silly extra
< layers of PL_strcasecmp

If you've got a better way of doing strcmps, sweep the tree and change the
existing usages, then do something to make sure people don't use the suboptimal
stuff.

< don't check the first byte again in strcmp, once you've checked it inline!
Yea, the reason I didn't skip the first byte was:
1. I figured it would confuse someone looking at the code.
2. falling into the PL_ compare was is generally a rarity so not much of a perf hit.

obviously you looked at the code though and noticed the better case, so I'll
submit a patch for that.

< (I think PL_str* should be a shooting offense, myself, but hey.)
good for you, make a difference and change the way we use (or don't) PL_*

Comment 18

[Judson Valeski]

I'd like to note that the bustage was in a directory that is *not* turned on by
default in regular builds. *all* three platforms were built (default pull/build)
before checking in. things that aren't in default builds obviously can't benefit
from regular pull/build error checking.

I apologize for the typo.

Comment 19

[Judson Valeski]

after talking about this a bit w/ Rick, we'll leave the changes as they stand. 
skipping the first byte would add readability complexity, and could potentially 
be more expensive than the extra byte compare as the pointers need to be 
incremented by one in order to do the skipping. Also, falling into the PL_strcmp 
is an edge case to begin w/.

Comment 20

[Daniel Veditz [:dveditz]]

All https vs http comparisons will fall into the strcmp. In fact, won't most 
URL's be http? That means to know they're really the same--the usual case--we 
take the performance hit.

Comment 21

[Judson Valeski]

I believe most urls are chrome/resource, http comes next.

the heaviest usage of a http/https check is in image lib and that hunk of code, 
I've verified w/ pavlov, won't exist in the new imagelib.

the next heaviest usage is probably shouldaddtoglobalhistory. 

maybe SchemeIs() should take the len of the string too? that would widdle it 
down even further and nix the http/https case.

Comment 22

[Judson Valeski]

or, we could use atoms instead.

Comment 23

[Gagan]

If this discussion has come down to atoms then I have to say that we have 
covered a full circle. I did consider atoms as a potential parameter to check on 
when I first did SchemeIs, but the problem was that atoms do not have a clean 
ownership model across different components. Creating a new atom each time was 
not necessarily cheap. I landed up with "faking" atoms with the hardcoded enum 
list. Since the SchemeIs function was purely an optimization we sacrificed 
extensibility for performance. I am still not completely convinced that we need 
to keep this extensible for other schemes (that aren't being used in the product 
as yet, but would be common enough to be optimized for) but I'd let jud make 
that call. 

Comment 24

[Judson Valeski]

at first glance it looks to me like the ->SchemeIs() callers can cache their 
atom's so I don't see the ownership issue.

there are a few embeddors I can think of that are already impl'ing their own 
proto handlers.

Comment 25

[rpotts (gone)]

Before we start worrying about the "performance hit" of doing a strcmp vs an 
unsigned long comparision, let's remember why this API was created in the first 
place.

Before IsScheme(...) was introduced, the caller was forced to call 
nsIURI::GetScheme(...) which involved a buffer copy and then do a strcmp() and 
finally free the buffer which held the scheme.

Clearly, in that situation, the calls to allocate and deallocate memory far 
outweighed the strcmp() call in terms of time.

In Jud's new code we, at most, make a call to strcmp()...  I'm sure we could 
even unroll the strcmp and write a quick comparision loop inline if necessary.

But, *please* lets collect some data before we call this change a perfomance 
hit and start trying to "fix" it!!

-- rick

Comment 26

[Judson Valeski]

I just did a quick sanity check on the number of times SchemeIs() gets called.

I set conditional break points in simple::SchemeIs() and std::SchemeIs(), I 
asked them to break when they fell into their strcmp case 1000 times (and in 
stdurl::schemeis() after it fell into it's full strcmp 500 times). after 
launching mozilla (w/ mail/news opening at startup w/ 5k messages in inbox), and 
visiting www.abcnews.com (a "heavy" page), no breakpoints hit. After hovering on 
one of the abcnews links, I got the stdURL::SchemeIs()::strcmp version to fire.

At that point, the strcmp had been called 500 times, and SchemeIs() was hit 926 
times. So, there's an ~50% chance of hitting the full strcmp (not exactly the 
edge case I had earlier deduced) in this limited test case. Most of those calls 
came from imagelib and I've verified that pavlov has removed that code from 
imglib2 and we talked about the strong likely hood of it not coming back.

So, before taking another cut at this, can someone (brendan? rick?) speak to 
whether or not a 4 byte strcmp being called 500 times per top level URL load 
(which includes inline content), is expensive? I would doubt it.

Comment 27

[Gagan]

I'd just like to know why extensibility of "common cases" is important? Do you 
really see a new scheme becoming more common than http/chrome/res/etc...? So 
much so that we need to optimize for it?

Comment 28

[Judson Valeski]

why lock ourselves into a nsIURI interface definition for embedding 1.0, then
turn around and produce nsIURI2, for a case we already know is on our plate to
cover.

If this is a perf hit, I propose nsIAtom instead.

Comment 29

[Judson Valeski]

using a debug build and a test driver for SchemeIs(), I tested the following.

Running SchemeIs() 1,000,000 times, w/ "http://www.foo.com" as the uri and
"https" as the check value (our 50% case in SeaMonkey).

PRUint32 compare: average run time was 125,000 micro seconds

nsIAtom compare: average run time was  125,000 micro seconds (expected to be the
same as PRUint32 as it's simply address equality checking)

The current checked in 1st byte, strcmp compare: average run time was 330,000
micro seconds.

homegrown inline strcmp: average run time was 230,000 micro seconds

The test used "http" and "https" which forced us into the full strcmp everytime.

So, current impl is 3x slower than the old one, and the homegrown strcmp version
was 2x slower.

Conclusion: for API consistencies sake (rather than making nsIAtom public) we're
going to leave things as they are. Based on this strcmp only being called 50% of
the time in our "normal" usage which can probably be measured in the tens or
hundreds of thousands rather than millions. I can make the change to knock a 3rd
of the time off, but I just don't see the need at this stage.

Comment 30

[Brendan Eich [:brendan]]

I was arguing the other week with gagan and dougt, before gagan's enum-based
schemeIs change went in, that they were optimizing prematurely.  They were not
persuaded, and I didn't see an extensibility barrier (I still don't), so I gave
in and gagan did an ownerly job of getting that change in.

Now, premature optimization is the root of all evil, but in this case, untested
code checkin kinda balances things out!  :-/

Since we're talking premature optimization, the first-char test is one, too. 
And then reloading and case-folding that char on a tentative match takes back
that premature optimization for that tentative-match case, and bloats the code
to boot.  Why not use good ol' strcasecmp and let gcc/glibc (on Linux) handle
the (shared) optimization?

/be

Comment 31

[rpotts (gone)]

ok... I give up.  I guess I'm the only one in the world that feels that all 
protocols should be treated equal by our APIs...  

It escapes me why everyone else thinks it's ok to have a method on nsIURI that 
only works for *some* protocols!! HELLO - is anybody thinking??

Lets just screw aim:// and any other "unimportant" protocols and force consumers 
to do a MEMORY ALLOCATION/DEALOCCATION just to determine the fucking scheme!!  
HELLO - is anybody thinking??

After all, if we really are calling this method THOUSANDS OF TIMES per URL load, 
then by all means lets make the function fast rather than fixing the real 
problem - that we are calling this method THOUSANDS OF TIMES per URL load :-(  
HELLO - is anybody thinking??

I guess not - so I'll just shut up

-- rick

Comment 32

[Brendan Eich [:brendan]]

rpotts: hey, I'm on your side -- i don't see a need for the enum-based thing.
Where is the data showing thousands of scheme-tests per URL load?

/be

Comment 33

[Judson Valeski]

using my off the cuff counter based breakpoints, on a heavy load
(www.abcnews.com), we were calling it at worst, say ~400 times (per top level
load. so that includes all the inline content). I didn't get into *who* was
calling any deeper than noticing that il_PermitLoad() was checking to see if it
was http or https (two sequential calls), on each image load. We're leaving it
as is because this won't show up on profiling radar at an app-level. If it does,
we can dig into it then, and at that point we should be asking why it's called
so much, rather than how to make it even faster.

A common calling case was "is the scheme of this url http or https, we only want
to deal w/ http based schemes in this section of code."

Comment 34

[Gagan]

I have a solution that keeps things optimized for standard/known/commonly used 
cases and is also extensible! How about we change the signature of SchemeIs to 
be something like--

boolean schemeIs(in PRUint32 schemetype, in string scheme);

The implementation stays like the way it was before Jud's checkin and will 
ignore scheme if the schemetype is anything but nsIURI::UNKNOWN. And in case the 
schemetype is indeed nsIURI::UNKNOWN it can then default to the string compares 
(with or without the first letter checks) as Jud wants.

This way we stay at our best performance on compares of common cases and still 
make this function work for new ones.

Comments? 

Comment 35

[Judson Valeski]

I think doubling up the the signature just adds complexity, and we've determined
we don't want to be optimizing at this in-perceivable level.