[cookies] move to hashtables

RESOLVED FIXED in mozilla1.6alpha

Status

()

enhancement
P2
normal
RESOLVED FIXED
18 years ago
16 years ago

People

(Reporter: dbaron, Assigned: dwitte)

Tracking

({perf})

Trunk
mozilla1.6alpha
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments)

COOKIE_GetCookie is slow -- it's taking about 1% of the non-idle page load time
on the main thread when running through 40 URLs somewhat like the jrgm test, but
live.

I'll attach a jprof profile showing the time spent within COOKIE_GetCookie.  I
admit to having a lot of stored cookies -- 243, to be exact, of which 155 are
domain cookies.

It seems like it would be nice to use a hashtable here for the host cookies, and
either a hashtable (where you would do multiple lookups) or a lexicographic tree
(where the child lists would be hashtables when they're larger than a certain
size) for the domain cookies -- probably the former would be simpler and fast
enough.
Status: NEW → ASSIGNED
Target Milestone: --- → mozilla1.0.1
Target Milestone: mozilla1.0.1 → mozilla1.1alpha
Priority: -- → P2
Target Milestone: mozilla1.1alpha → mozilla1.1beta
Whiteboard: nsbeta1
Keywords: nsbeta1
Whiteboard: nsbeta1
Target Milestone: mozilla1.1beta → mozilla1.2beta
OS: Linux → All
Hardware: PC → All
Severity: normal → enhancement
Target Milestone: mozilla1.2beta → Future
Nav triage team: nsbeta1-
Keywords: nsbeta1nsbeta1-
Will be taken care of when we move to hashtables as part of the backend cookie
rewrite.
Blocks: 187304
taking
Assignee: morse → dwitte
Status: ASSIGNED → NEW
Dan, do you have patch ready for review  (cookie backend re-write)?  

I think the risk of re-write could be pretty high, but if reviews show it's good
to land, then we most likely need to try for early 1.4alpha, so that the code
can be baked on trunk, and we would have time to iron out unforeseen issues.
cathleen:

I've posted a reply to your comment in bug 187304 (tracking bug for the
rewrite)... take a look :)
i have a patch in hand for this. i need to polish it a tad more before it's
ready for review.

codesize will be neutral (which is great, because the hashtable code is more
complex... but we get some neat savings in a few places), and perf will be
greatly improved. my earlier measurements indicate about a 2x speedup in
GetCookie() for moderately-sized lists, and i expect a large improvement in
SetCookie() (mostly because of reworked semantics, owing to the cheaper list
operations).

darin, what's your schedule looking like for the freeze? if we can get this in,
it would be neat... but i don't want to bog you down with all these patches :)
Status: NEW → ASSIGNED
Summary: COOKIE_GetCookie is slow → [cookies] move to hashtables
Target Milestone: Future → mozilla1.6alpha
ok, here it is. this patch is diffed against a bunch of other things in my
tree, so don't try to apply it. for review purposes only. ;)

(if you want to test it, just let me know and i can diff up my tree for you.)

the patch is mostly refactoring and shuffling of code, to optimize everything
for the capabilities the hashtables provide (see e.g. AddInternal()). the
architecture i've chosen is a hashtable of Host() entries (which means they
keep the leading dot if they are domain cookies). the nsCookie's themselves are
stored as a linked list within the nsCookieEntry hash entryclass, which is
optimal for the common case of one or two cookies per domain. (using a
voidarray would be bloaty for this case). so, to find all the cookies for a
given URL (say in GetCookie()), you just walk up the domain levels by looking
for '.' in the host URI, and do a hash lookup at each stage. you then traverse
the linked list.

another nice little win is killing off our custom nsCookieEnumerator class for
nsICookieManager::GetEnumerator()... we just roll an nsCOMArray and grab an
enumerator off that. overall, this patch is codesize-neutral (actually it
reduces it a tad).
Attachment #133188 - Flags: superreview?(darin)
Attachment #133188 - Flags: review?(mvl)
Comment on attachment 133188 [details] [diff] [review]
patch v1 (readable; for review only)

>-nsCookieService *nsCookieService::gCookieService = nsnull;
>+static nsCookieService *gCookieService = nsnull;

As I mentioned on IRC, file-scoped statics are considered deprecated in the C++
standard, so leave the static class member.

>+  if (gCookieService) {
>+    NS_ADDREF(gCookieService);
>+    if (NS_FAILED(gCookieService->Init())) {
>+      NS_RELEASE(gCookieService);
>+    }
>+  }
> 
>   return gCookieService;
> }

If gCookieService->Init fails, you need to null out gCookieService so that this
method doesn't return an bad pointer.

>+  // begin hash lookup, walking up the subdomain levels.
>+  // we use nextDot to make sure we have at least one embedded dot remaining.
>+  while (nextDot) {
>+    nsCookieEntry *entry = mHostTable.GetEntry(currentDot);
>+    for (cookie = entry ? entry->Head() : nsnull; cookie; cookie = cookie->Next()) {

IMO this would be more readable if you moved "cookie = entry..." on its own
line before the "for", or even better, made this a while loop.

>+      // if the cookie is secure and the host scheme isn't, we can't send it
>+      if (cookie->IsSecure() & !isSecure) {
>+        continue;
>+      }

I have two questions about this... first, what is bitwise-& doing there?
second, shouldn't this test go in both directions? non-secure cookies should
not be fed to secure webpages.

>-    // check if the cookie has expired, and remove if so.
>-    // note that we do this *after* previous tests passed - so we're only removing
>-    // the ones that are relevant to this particular search.

Did you/do you need to add this logic back somewhere else? 

@ nsCookieService::Remove(const nsACString &aHost,
>+  if (!FindCookie(PromiseFlatCString(aHost),
>+                  PromiseFlatCString(aName),
>+                  PromiseFlatCString(aPath),
>+                  matchIter))
>+    return NS_ERROR_UNEXPECTED;

Is this truly an unexpected error? Wouldn't it make more sense to define/use a
"success" code "NS_COOKIE_NOT_FOUND"?

r=bsmedberg if you address the comments above
Attachment #133188 - Flags: review?(mvl) → review+
thanks for the review bsmedberg! ;)

>If gCookieService->Init fails, you need to null out gCookieService so that this
>method doesn't return an bad pointer.

actually, NS_RELEASE() nulls the pointer...

>IMO this would be more readable if you moved "cookie = entry..." on its own
>line before the "for", or even better, made this a while loop.

yeah; i would've used the nsListIter helper class, only we don't need the extra
"prev" member here. i'll tidy it up.

>I have two questions about this... first, what is bitwise-& doing there?
>second, shouldn't this test go in both directions? non-secure cookies should
>not be fed to secure webpages.

great catch... i owe you one. i just fixed that to a logical-&& on trunk. as for
bidirectionality... the "secure" attribute on a cookie just means that the
browser should only send the cookie contents over a secure connection. it
doesn't mean that _only_ secure cookies can be sent over secure connections -
it's just a hint the server can use to say the cookie contents are sensitive.

>Did you/do you need to add this logic back somewhere else? 

nope... cookie expiry semantics have changed in this patch. previously, since we
were traversing the entire list anyway, we could expire old cookies in
GetCookie(); but now, we only want to traverse the entire list when it's
absolutely necessary. so we only expire cookies when we're trying to set a
cookie, and the list is full (300 cookies), to try and free up space. cookie
expiry should be a fairly rare event (distinct from deletion or replacement,
which can happen frequently).

>Is this truly an unexpected error? Wouldn't it make more sense to define/use a
>"success" code "NS_COOKIE_NOT_FOUND"?

yeah, i guess there are legitimate cases where this could happen... is it worth
defining a special returncode? how do i do that? ;)

thx again for the review!
you would define your new error code in netwerk/base/public/nsNetError.h, in a
new section, adding a new section to the end.

#define NS_SUCCESS_COOKIE_NOT_FOUND \
    NS_ERROR_GENERATE_SUCCESS(NS_ERROR_MODULE_NETWORK, 80)

The other option, of course, is to return NS_OK... who cares if we can't delete
a cookie that doesn't exist?
yeah, NS_OK sounds fine to me... can't think of a reason why the caller would
care  to know :)
Comment on attachment 133188 [details] [diff] [review]
patch v1 (readable; for review only)

Looks good to me too. r=mvl for what it is worth
Comment on attachment 133188 [details] [diff] [review]
patch v1 (readable; for review only)

>+struct nsListIter
>+{
>+  nsListIter() {}
...
>+  nsCookieEntry *entry;
>+  nsCookie      *prev;
>+  nsCookie      *current;
>+};
...
>+struct nsEnumerationData
>+{
>+  nsEnumerationData(nsInt64 aCurrentTime,
>+                    PRInt64 aOldestTime)
>+   : currentTime(aCurrentTime)
>+   , oldestTime(aOldestTime) {}
...
>+  nsListIter iter;
>+};

concerns me that |iter| will be uninitialized after normal construction
of a nsEnumerationData object.	maybe your default constructor should
null out nsListIter's fields.  in a perfect world this is overkill, but
it is easier to track down problems related to dereferencing a null pointer
than it is with dereferencing a junk pointer.


>+  // return cookies in order of path length; longest to shortest
>+  foundCookieList.Sort(compareCookiesByPath, nsnull);

maybe comment that this sorting is done per spec.


overall, this patch looks great! sr=darin
Attachment #133188 - Flags: superreview?(darin) → superreview+
landed for alpha. fixed!
Status: ASSIGNED → RESOLVED
Closed: 16 years ago
Resolution: --- → FIXED
nice work - looks like this knocked down Ts on some platforms (also could have
been other checkins, but this looks like a good culprit)
You need to log in before you can comment on or make changes to this bug.