201455 - Small optimization in MetaData of nsCacheEntry, and 'unsafe' relation removed

Status: RESOLVED FIXED

(Core :: Networking: Cache, defect)

Description

[Alfred Kayser]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.4b) Gecko/20030408
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.4b) Gecko/20030408

Another (small) optimization is in the Size() function.
As it is only called in nsCacheEntry.cpp right after a SetElement
or a UnflattenMetaData, where in both functions the entry list is walked
anyway (and in Unflatten even the size is calculated), just walking it again
to update MetaDataSize of CacheEntry is redundant.

Do the following:
Move PRUint32 mMetaSize; from nsCacheEntry to nsMetaData.
in nsCacheEntry.h: replace mMetaSize by mMeta.Size().
in nsCacheMetaEntry.cpp: 
   change SetElement to do:
           mMetaSize -= size of entry removed
           mMetaSize += size of entry added
           (See patch below)
   change UnflattenData to: 
           add mMetaSize = 0 as the first line (before the if (size==0))
   change Size() to:
           return mMetaSize;
(note the comment in Size: // XXX this should be computed in SetElement)
That's thus this bug!

--- Patch of SetElement ----

nsresult
nsCacheMetaData::SetElement(const char * key,
                            const char * value)
{
    nsCOMPtr<nsIAtom> keyAtom = do_GetAtom(key);
    if (!keyAtom)
        return NS_ERROR_OUT_OF_MEMORY;

    // find and remove old meta data element
    MetaElement * elem = mData, * last = nsnull;
    while (elem) {
        if (elem->mKey == keyAtom) {
            // remove elem
            if (last)
                last->mNext = elem->mNext;
            else
                mData = elem->mNext;
**            mMetaSize -= 2 + strlen(key) + strlen(elem->mValue);
            delete elem;
            break;
        }
        last = elem;
        elem = elem->mNext;
    }

    // allocate new meta data element
    if (value) {
        elem = new (value) MetaElement;
        if (!elem)
            return NS_ERROR_OUT_OF_MEMORY;
        elem->mKey = keyAtom;

        // insert after last or as first element...
        if (last) {
            elem->mNext = last->mNext;
            last->mNext = elem;
        }
        else {
            elem->mNext = mData;
            mData = elem;
        }

**        mMetaSize += 2 + strlen(key) + strlen(value);
    }
    return NS_OK;
}


This make both nsCacheEntry::SetMetaDataElement and
nsCacheEntry::UnflattenMetaData faster, as it doesn't need to walk the
MetaElements list twice, and do the strlen's for all entries.
Both will be thus about twice as fast?

Furthermore it closes a unsafe connection between mMetaSize in nsCacheEntry and
the list maintained in nsMetaData. Keeping the size up to date in the nsMetaData
itself, prevent problems if others call MetaData::SetElement directly.
Note, this doesn'it increase total data size of nsCacheEntry, but will reduce
some code footprint.

Reproducible: Always

Steps to Reproduce:

Comment 1

[Darin Fisher]

alfred:

yup, thanks for the pointers.  was planning on cleaning this up eventually ;-)

Comment 2

[Alfred Kayser]

Attachment: More complete patch directions.

This further optimizes (for speed, not for size) by 'inlining' new into
SetElement, and by 'inlining' SetElement into UnflattenMetaData.
This prevents strlen be called three times for the value, and prevents 
SetElement trying to delete keys, when they are being created (in Unflatten..)
Result should be still smaller (in code) than before, as '::Size' becomes very
small. Also the MetaElement::operator new can be removed now.

Note, this move MetaData stuff from CacheEntry to CacheMetaData (as seen in
CacheEntry.h)
Note, this is not a normal 'diff' as I don't have a full build locally.
This is done just for fun, so if you want to do it differently, no problem by
me.

Comment 3

[Alfred Kayser]

Attachment: Complete and tested patch

Remove 'unsafeness' around mMetaSize by keeping in the Metadata class
itself. Furthermore, some optimisations so that strlen is only called
once instead of trice. Also inlined new to allow for these optimisations.
Also optimised for value update in case of same value-length (rarely,
but (almost) no code impact, so a cheap quickwin).
Inlined SetElement in Unflatten, to prevent searching the linked list for
items to be deleted (which never happens in Unflatten).

Comment 4

[Darin Fisher]

Comment on attachment 121676 [details] [diff] [review]
Complete and tested patch

gordon should review this as well.

alfred: don't you think it would have been cleaner to just add another
parameter (say valueLen) to operator new?  duplicating allocation and
construction code doesn't seem to be worth it.	i seriously doubt the code
increase (due to inlining) is worth the tiny speed increase.  unless you can
prove that it makes any kind of real improvement in speed, let's favor code
reduction here instead.  also, i don't think the memsets are necessary.

Comment 5

[Darin Fisher]

Comment on attachment 121676 [details] [diff] [review]
Complete and tested patch

also, i'm fine with the change away from operator new/delete.  maybe you could
just create a static NewMetaElement function or something like that to avoid
code duplication.

Comment 6

[Alfred Kayser]

Attachment: Corrected patch

Created NewMetaElement to do the allocation and value setting.

Comment 7

[Darin Fisher]

Comment on attachment 121889 [details] [diff] [review]
Corrected patch

>+    PRUint32 keySize = strlen(key);
>+    PRUint32 valueSize = value?strlen(value):0;

nit: this file "likes" whitespace.  use it.

   = value ? strlen(value) : 0;


>+        elem = NewMetaElement(value,valueSize);

same nit


>+        // Increase size of key with new value
>+        mMetaSize -= 2 + keySize + valueSize;
> }

indentation looks wrong in the above patch snipet.  make sure
you keep things at 4 spaces.


>+    if (mMetaSize > bufSize) {
>             // not enough space to copy key/value pair
>             NS_ERROR("buffer size too small for meta data.");
>             return NS_ERROR_OUT_OF_MEMORY;
>         }

patch created without whitespace modifications?  if not, please
make sure to cleanup the indentation.  thx!


>+            MetaElement *elem = NewMetaElement(data,valueSize);

same nit about whitespace.


>+            if (!elem)
>+                 return NS_ERROR_OUT_OF_MEMORY;
>+            elem->mKey = keyAtom;
>+            if (last) {
>+                last->mNext = elem;
>+            } else {
>+                mData = elem;
>+            }
>+            last = elem;

any of this list manipulation code shared with SetElement?  any
chance some of it could be factored into NewMetaElement?  isn't
it always the case that after calling NewMetaElement we want to
append the new element to the list?  hmm...


please add a comment like:

// sizeof(MetaElement) has space for value's null byte.

or something like that (i should have put such a comment in the code
originally!)

>+    MetaElement *elem = (MetaElement *)malloc(sizeof(MetaElement)+valueSize);


overall, this patch looks really good.	just fixup my nits and sr=me ;-)

Comment 8

[Alfred Kayser]

Attachment: Incorporated review comments of Darin

Fixed whitespace.
Moved linked list linkage to NewMetaElement.
Added comment on extra nullbyte space.
P.s. indenting is ok, due to diff -uw output.

Comment 9

[Darin Fisher]

Comment on attachment 121991 [details] [diff] [review]
Incorporated review comments of Darin

looks great!  sr=darin

Comment 10

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 121991 [details] [diff] [review]
Incorporated review comments of Darin

>Index: nsCacheEntry.h
>+                                     const char *  value){ return mMetaData.SetElement(key, value); }

Add a space before the '{'?

>+    PRUint32 MetaDataSize() { return mMetaData.Size();}  

Space before the '}'?

>Index: nsCacheMetaData.cpp
>-        delete mData;
>+        free(mData);

free() does not call destructors.  In particular, you will not call the
destructor of the nsCacheMetaData, hence will not call the destructor of the
nsCOMPtr, hence will leak the key atom.

>     // find and remove old meta data element

This comment is no longer correct... That's not all you do anymore

>-            delete elem;
>+            mMetaSize -= 2 + keySize + valueSize;
>+            free(elem);

Same comment as above on "free"; not clear to me where this magic "2" number
comes from.

>+        mMetaSize -= 2 + keySize + valueSize;

again, where does the 2 come from?  I'm starting to suspect that this is for
the null bytes....

>+            mMetaSize += 2 + nameSize + valueSize;

Another magic 2.

I have to admit to being confused by the operator new removal.	You could just
change that operator to take both the string and its length if you are worried
about calling strlen too much....

In any case, the leak issues need to be fixed.

Comment 11

[Alfred Kayser]

Attachment: Comments from bzbarsky incorporated

Thanks for the comments:

* Add a space before the '{'?
Done.

* Space before the '}'?
Made spacing of ;} consistent with rest.

* free() does not call destructors.  
Changed back to delete

* >	// find and remove old meta data element
Fixed.

* >+		mMetaSize -= 2 + keySize + valueSize;
* not clear to me where this magic "2" number comes from.
Added comment (to each of these) to explain the the 2 for the two zero bytes.

* In any case, the leak issues need to be fixed.
Done, by replace back to delete

Comment 12

[Darin Fisher]

Comment on attachment 128147 [details] [diff] [review]
Comments from bzbarsky incorporated

>Index: nsCacheMetaData.cpp

>     MetaElement * elem = mData, * last = nsnull;
...
>             delete elem;


>+    MetaElement *elem = (MetaElement *)malloc(sizeof(MetaElement) + valueSize);

you can't allocate using malloc and then free using delete.  these
need to match up!  if you want to use malloc/free, then you need to
rename the destructor and call it explicitly before freeing the 
memory.  otherwise, you need to provide an operator new that takes
parameters (like the original code did).

Comment 13

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 128147 [details] [diff] [review]
Comments from bzbarsky incorporated

What darin said; the way to go is to use new/delete and to pass the length to
new, imo...

Comment 14

[Alfred Kayser]

Attachment: Back to 'new & delete'

Ok, back to 'new' now with value and valueSize as extra params.

Summary of the changes accomplished with this patch:
* Move 'mMetaSize' to nsCacheMetaData, to make it the owner of its own size.
* in nsCacheMetaData keep mMetaSize current with each clear, setElement
unflatten operation, to prevent list-walking to get the size.
* Extra param to new to pass valueSize around, to prevent a number of strlen's
* Inlined SetElement in Unflatten, to prevent searching the linked list for
items to be deleted (which never happens in Unflatten).
* SetElement: Update value only in case of same value-length, instead of
delete/new.

So, all should be performance increasing, with minimal code impact (+99/-127
codelines).

Comment 15

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 128220 [details] [diff] [review]
Back to 'new & delete'

>Index: nsCacheEntry.h
>+    PRUint32 Size()                               { return mDataSize + mMetaData.Size();}

Space before the '}' please (missed that the first time :( ).

>     nsresult     SetMetaDataElement( const char *  key,
>-                                     const char *  value);
>-
>+                                     const char *  value) { return mMetaData.SetElement(key, value);}

Same.

>+    nsresult UnflattenMetaData(char * buffer, PRUint32 bufSize) { return mMetaData.UnflattenMetaData(buffer, bufSize);}
>+    PRUint32 MetaDataSize() { return mMetaData.Size();}  

Same.  See what GetMetaDataElement and FlattenMetaDataElement do, please. 
Although, maybe you changed those and I just can't tell -- please post normal
diffs in addition to -w ones....

>Index: nsCacheMetaData.cpp
>             // remove elem
>             if (last)
>                 last->mNext = elem->mNext;
>             else
>                 mData = elem->mNext;
>+            // 2 for the zero bytes of both strings
>+            mMetaSize -= 2 + keySize + valueSize;
>             delete elem;

Shouldn't that be:

  mMetaSize -= 2 + keySize + strlen(elem->mValue);

?  This is the case when strlen(elem->mValue) != valueSize, after all.... (you
may want to save the strlen() result in a temporary earlier).

>+    if (mMetaSize > bufSize) {
>             // not enough space to copy key/value pair
>             NS_ERROR("buffer size too small for meta data.");
>             return NS_ERROR_OUT_OF_MEMORY;
>         }

How about taking out that comment, which is no longer relevant?

r=me with those comments addressed (the only one that actually affects
correctness is the mMetaSize adjustment one).

Comment 16

[Darin Fisher]

Comment on attachment 128220 [details] [diff] [review]
Back to 'new & delete'

please post a final patch for me to review with bz's comments addressed. 
thanks.

Comment 17

[Alfred Kayser]

Attachment: Final patch (hopefully)

diff -u, so it shows all whitespace changes.
* Changed all ;} in nsCacheEntry.h to ; }
* Fixed the valueSize of deletion of old elements.

Comment 18

[Alfred Kayser]

Comment on attachment 128305 [details] [diff] [review]
Final patch (hopefully)

Darin, can you sr it?

Comment 19

[Darin Fisher]

Comment on attachment 128305 [details] [diff] [review]
Final patch (hopefully)

>Index: nsCacheMetaData.cpp

>+ *
>+ * Contributor(s):
>  *    Gordon Sheridan, 22-February-2001

typically, folks don't quote the original date of the file next to their
name in the contributors section.  gordon certainly has been involved
with the cache well after this date as well.  maybe just quote his name.


>+ * Contributor(s):
>  *    Gordon Sheridan, 22-February-2001

same here.

sr=darin ...no need to submit a revised patch; just check it in with this
nit fixed :)

sorry it took so long to get this patch through the system... it's great
stuff, and i really appreciate your help!

Comment 20

[amano]

why didn't the patch get checked in? there is a review and a superreview.

Comment 21

[Mike Kaply [:mkaply]]

Fix checked in.