118061 - 10 sec timer to release memory held by zlib allocator

Status: RESOLVED FIXED

(Core :: General, defect, P3)

Description

[Suresh Duddi (gone)]

Timers are in xpcom. Let us use a 10 sec timer to free any memory held by
allocators if they arent used. Allocators to target are

- zlib
- gif

Comment 1

[Suresh Duddi (gone)]

Attachment: First draft of nsRecycleAllocator

This implements nsRecycleAllocator in xpcom/ds. As a test I converted gif
allocator to use this.

TODO
- unix
- mac
- convert zlib allocator to use this

Comment 2

[Brendan Eich [:brendan]]

I'm leery of general mechanisms like this, but it looks like you already made a
pass over high-frequency or otherwise-costly malloc users, and implemented the
same (or nearly the same) solution at least twice.  Is that right?  I saw only
the zlib one in a recent review, didn't realize the same approach was being used
in GIF code.

The zlib allocator was convincing as a special case because you could tune it to
the memory demand, with not too many buckets.  But it would be unfortunate if
someone used a large (>> 10) nbucket parameter with nsRecycleAllocator.  I'm not
sure how to fix this and other problems that can arise from making a seemingly
general facility available in xpcom/ds.

I can review the patch in detail, but I wanted to say first, in addition to
raising this point of order, that Touch and Untouch are not thread-safe.

BTW, nsRecycleAllocator is too vague a name, and not grammatical to boot.  How
about something like nsTemporarilyPoolingAllocator?  I'm not kidding!

/be

Comment 3

[Suresh Duddi (gone)]

> I'm leery of general mechanisms like this, but it looks like you already made a
> pass over high-frequency or otherwise-costly malloc users, and implemented the
> same (or nearly the same) solution at least twice.  Is that right?  I saw only
>the zlib one in a recent review, didn't realize the same approach was being used
> in GIF code.

Yeah. We have two places using (almost) similar mechanism. I will convert zlib
to use this too and it will fit in. The key is the number of buckets.

> But it would be unfortunate if someone used a large (>> 10) nbucket parameter 
> with nsRecycleAllocator.  I'm not sure how to fix this

I have the constructor cap the number of buckets.

+nsRecycleAllocator::nsRecycleAllocator(PRUint32 nbucket, PRUint32 recyleAfter)
+    : mNBucket(nbucket), mRecycleTimer(nsnull), mRecycleAfter(recyleAfter),
mTouched(0),
+      mNAllocations(0)
+{
+    if (mNBucket > NS_MAX_BUCKETS)
+        mNBucket = NS_MAX_BUCKETS;

nsFixedSizeAllocator in xpcom has a similar contraint of use. Maybe I can add as
assert and that will prevent misuse.

I expect this to be the facility we would use to fix a bunch of other places we
identify. To give you a summary: we churn through 30MB of memory with 500k calls
to alloc on startup to keep a footprint of 7Mb. This is 35%-40% of the cost of
startup on windows. The timer stuff reclaims footprint hogged by these
allocators reusing memory.

I see a big win using this. I think this falls in the same category as
nsFixedSizeAllocator or nsArena

Yeah the name is too vague. Let me think more on a better one. 

Comment 4

[Brendan Eich [:brendan]]

I see there could be a big win, too -- but I'd rather see measurements.  We'll
"churn thru" the same amount of mem unless you change callers in deeper ways,
but we won't make malloc do the churning.  That should save cycles, the question
is how many.  It may also bloat our peak footprint, or not.  Got any numbers yet?

/be

Comment 5

[Suresh Duddi (gone)]

Attachment: more thread safety + zlib allocator converted to nsRecycleAllocator

Improves on previous patch
- mTouched uses atomic set
- mNAllocations uses atomic increments
- converts both zlib and gif allocators to use nsRecycleAllocator

Comment 6

[Suresh Duddi (gone)]

zip & Gif allocators together saves about 10% of all allocations cost. This
patch includes converting those to use this new xpcom facility - sharing code.

I guess you want more proof to convince ourselves that this could be put in
xpcom as opposed to duplicating the code in zlib & gif - right ? That would mean
more analysis to find big gain areas to plug the allocator in. I will try find a
few more. Areas that immediately spring to mind are Parser, necko, js.

And yes this could increase peak usage. It might also decrease peak usage by
reducing fragmentation of the malloc pool.

Taking the zlib & gif allocators for a test, would we like:
- peak usage
- total malloc cost
with and without allocator enabled. I could provide this number. Previous
results already prove this number will be less with allocator enabled. Let me
know if you are looking for different numbers.

Comment 7

[Suresh Duddi (gone)]

With recycle patch: (Recycle timer at 10 sec)
startup-recycle-tracemalloc.log
All allocations: # 229,259 = 2.351042
Peak: 8,451,232

With recycle patch: (no Recycle timer)
startup-recycle-notimer-tracemalloc.log
All Allocations: # 220,671 = 2.189691
Peak: 7,491,880

Recyle disabled:
startup-recycle-disable-tracemalloc.log
All Allocations: # 230,846 = 2.782391
Peak: 7,908,304

Conclusion:
- First, the peak usage varies dramatically betn runs.

- In general, the patch actually reduces peak memory usage. I would guess this
is caused by reduced fragmentation.

- Build with patch (&timer) uses more memory than with patch disabled because a
tracemalloc run takes about 200 secs to start during which time the recycle
timer s fire every 10 secs and clear allocated memory. So it is as thought the
patch is not there. The higher peak than when the allocator is disabled is
because the zlib allocator bumps up smaller x 4 allocs.

More data points: Max memory held by these allocators:
zlib : 46,936 bytes
gif  : 32,776 bytes

Comment 8

[Suresh Duddi (gone)]

Attachment: nsReusingAllocator

Comment 9

[Suresh Duddi (gone)]

Need r=/sr=  dougt/brendan ?

Comment 10

[Suresh Duddi (gone)]

Attachment: nsReusingAllocator (fixed Assert)

Comment 11

[Daniel Veditz [:dveditz]]

Comment on attachment 64255 [details] [diff] [review]
nsReusingAllocator (fixed Assert)

>+NS_NewTimer(nsITimer* *aResult, nsTimerCallbackFunc aCallback, void *aClosuer,

"aClosure"?


>+ * Portions created by the Initial Developer are Copyright (C) 2001

2002? Or not, I see this is derived from the zlib/gif allocators.

>+ * Contributor(s):
>+ *

You could put your name here which might help later if people have
questions about the code. (ok, they could use cvs blame, but not as
easily if they get the source as a tarball.)

>+nsReusingAllocator::nsReusingAllocator(PRUint32 nbucket, PRUint32 recyleAfter)
>+    : mNBucket(nbucket), mRecycleTimer(nsnull), mRecycleAfter(recyleAfter), mTouched(0),
>+      mNAllocations(0)
>+{
>+    NS_ASSERTION(mNBucket <= NS_MAX_BUCKETS, "Too many buckets. This will affect the allocator's performance.");
>+    if (mNBucket > NS_MAX_BUCKETS)
>+    {
>+        mNBucket = NS_MAX_BUCKETS;
>+    }

I don't mind the assertion or a warning, but resetting the user's value kinda
sucks. What if they picked 11 and *knew* that it behaved better shared than
having allocation churn in that last bucket?

r=dveditz -- won't hold that hostage over a matter of opinion :-)

Comment 12

[Suresh Duddi (gone)]

Fixed Contributor, Closuer and 2002.

Regarding the MAX_BUCKETS: If we do hit that point, we can always remove the
harsh resetting. For now since the facility is new, it is better to protect it,
I think.

Comment 13

[timeless]

Um, by 2002 i think dveditz was hinting that it would be 2001-2002 since some 
of the code is from 2001.

Comment 14

[Daniel Veditz [:dveditz]]

When I suggested 2002 I thought it was new code because it's a new file. Later I
noticed that it's derived from code that was 2001 (albeit December 2001) so
2001-2002 is defensible, but it is a new expression of that code by the same
author so 2002 might not be wrong. Dunno, IANAL.

Comment 15

[Suresh Duddi (gone)]

Attachment: Final patch

On the copyright issue: I put (C) 2001, 2002

Comment 16

[Suresh Duddi (gone)]

Comment on attachment 64424 [details] [diff] [review]
Final patch

r=dveditz from earlier patch

Comment 17

[Suresh Duddi (gone)]

Ccing Robert. He agreed to help with with mac export symbol list. Thanks!!!

Comment 18

[Suresh Duddi (gone)]

Attachment: Final patch (including timer files)

Missed xpcom/threads changes in earlier patch

Comment 19

[Brendan Eich [:brendan]]

Comment on attachment 64432 [details] [diff] [review]
Final patch (including timer files)

>+extern NS_COM nsresult
>+NS_NewTimer(nsITimer* *aResult, nsTimerCallbackFunc aCallback, void *aClosure,
>+            PRUint32 aDelay, PRUint32 aPriority, PRUint32 aType);

NB: aPriority is going away, so should we expose it here?

>+nsresult
>+NS_NewTimer(nsITimer* *aResult, nsTimerCallbackFunc aCallback, void *aClosure,
>+            PRUint32 aDelay, PRUint32 aPriority, PRUint32 aType)
>+{
>+    nsresult rv;
>+    nsTimerImpl* timer = new nsTimerImpl();
>+    if (timer == nsnull)
>+        return NS_ERROR_OUT_OF_MEMORY;
>+    NS_ADDREF(timer);
>+
>+    rv = timer->Init(aCallback, aClosure, aDelay, aPriority, aType);
>+    if (NS_FAILED(rv)) {
>+        NS_RELEASE(timer);
>+        return rv;
>+    }
>+
>+    *aResult = timer;
>+    return NS_OK;
>+  

Trailing space and an empty line here, but no empty line at the top, say after
the return NS_ERROR_OUT_OF_MEMORY.

Also, move the nsresult rv down to where it's first set.

>+}
>Index: xpcom/ds/Makefile.in
>===================================================================
>RCS file: /cvsroot/mozilla/xpcom/ds/Makefile.in,v
>retrieving revision 1.59
>diff -u -r1.59 Makefile.in
>--- xpcom/ds/Makefile.in	9 Dec 2001 07:04:26 -0000	1.59
>+++ xpcom/ds/Makefile.in	11 Jan 2002 02:08:21 -0000
>@@ -58,6 +58,7 @@
> 		nsProperties.cpp \
> 		nsPersistentProperties.cpp \
> 		nsQuickSort.cpp \
>+		nsReusingAllocator.cpp \

nsRecyclingAllocator, please.

>+#define NS_SEC_TO_MS(s) (s * 1000)

Parenthesize macro parameters when used with operators.

>+
>+void
>+nsRecycleTimerCallback(nsITimer *aTimer, void *aClosure)
>+{
>+    nsReusingAllocator *obj = (nsReusingAllocator *) aClosure;
>+    if (!obj->mTouched)
>+    {
>+#ifdef DEBUG_dp
>+        printf("DEBUG: nsReusingAllocator not touched: %d allocations avaliable\n", obj->mNAllocations);
>+#endif
>+        if (obj->mNAllocations)
>+            obj->FreeUnusedBuckets();
>+    }
>+    else
>+        // Clear touched so the next time the timer fires we can test whether
>+        // the allocator was used or not.
>+        obj->Untouch();

Style-nit: why not brace the else clause too -- it has "multiple lines"
(literally; two are comments, but still).

>+void*
>+nsReusingAllocator::Malloc(PRUint32 bytes)
>+{
>+    PRInt32 freeAllocatedBucketIndex = -1;

Kind of an oxymoronic name -- how about freeBucketIndex?  Or availBucketIndex?

>+void
>+nsReusingAllocator::Free(void *ptr)
>+{
>+    // Mark that we are using the allocator. This will prevent any
>+    // timer based release of unused memory.
>+    Touch();

Will it really?  What happens if the timer fires on one thread, tests mTouched
and finds it 0, then gets suspended for some reason?  If another thread starts
using the memory, then the timer thread resumes.

In that case, the Claim/Unclaim machinery will still protect any buckets in
use.  So what's the benefit of mTouched?  Why not free all unclaimed memory
from the timer?

>+    // Touch will mark that someone used this allocator
>+    // Timer based release will free unused memory only if allocator
>+    // was not touched for mRecycleAfter seconds.
>+    void Touch() {
>+        if (!mTouched)
>+            PR_AtomicSet(&mTouched, 1);
>+    }

The if (!mTouched) here doesn't really make sense.  But I question the whole
mTouched member.

/be

Comment 20

[Suresh Duddi (gone)]

>>+    void Touch() {
>>+        if (!mTouched)
>>+            PR_AtomicSet(&mTouched, 1);
>>+    }
>
>The if (!mTouched) here doesn't really make sense. 

Touch is going to happen for every malloc and free. The condition prevents the
AtomicSet from happening everytime, the premise being AtomicSet is much more
expensive that a test.

All other comments (except the mtouched) accepted.

> But I question the whole mTouched member.
...
> In that case, the Claim/Unclaim machinery will still protect any buckets in
> use.  So what's the benefit of mTouched?  Why not free all unclaimed memory
> from the timer?

The benefit is to find an appropriate time to release unused memory. The whole
reason the nsRecylingAllocator is effective for repeated operationsis that it
keeps around memory allocated for one operation and reuses it for further
operations.

app start----------------------------------------------startup DONE
[n allocations].....[n allocations].....[n allocations]............

If we dont have mtouched, then after 10 secs no matter where we are in startup,
we will end up freeing unused buckets and then reallocation them when the next
operation happens.

One solution is to make the timeout long enough that for the most common
hardware architectures, that would not cause memory to be freed by timer and
reallocated. Since this recylingallocator is going to be in xpcom and used in
different ways, perdicting when all repeating operations are over is hard.
Predicting when the first of the repeating cycle is impossible.

Timestamping last use of each bucket and timer freeing the bucket after n secs
of no use is another. But is expensive.

mtouched is another cheap solution. Whenever any bucket in the allocator is
used, the entire allocator is said to be touched. Timer checks if the allocator
has been touched since the previous timer and does not free anything unless the
entire allocator was not touched for the entire period of timeout. So here we
are predicting the frequency of the repeating operation and as long as the
timeout is  greater than the largest interval betn repeating operations,
churning by the reusingallocator wont happen. I think 10secs is a good
upperbound on the interval betn susequent operations. Also detection of the
first of the repeating operation is inbuilt - the first time mtouched is set.

Claim/Unclaim machinery is to prevent the rare case of the next cycle of
repeating operations starting after the timer has fired and decided to free
unused buckets.

There are two questions:
a) is this touched machinery required ?
b) would the mtouched as implemented achieve that ?

I hope to have answered both. Let me know what you think.

Regarding other comments - all accepted. Will attach new patch.

Comment 21

[Suresh Duddi (gone)]

Attachment: nsRecyclingAllocator

We can take the priority argument for NewTimer when we get rid of it.

Comment 22

[Suresh Duddi (gone)]

Hey brendan sr ?

Comment 23

[Simon Fraser [no longer active]]

Comments:

+void
+nsRecycleTimerCallback(nsITimer *aTimer, void *aClosure)

I'd rather see this be a static method of the class. Less chance for name 
collisions in static builds.


+    mMemBucket = (nsMemBucket *) malloc(mNBucket * sizeof(nsMemBucket));
+    if (!mMemBucket)
+        mNBucket = 0;
+    else
+    {
+        memset(mMemBucket, 0, mNBucket * sizeof(nsMemBucket));

malloc + memset can be less efficient than a calloc on some OSes, because calloc 
allows the VM system to zero out the bits at some time later when the memory 
block is actually accessed, rather than touching all the bits up front. So use 
calloc()  :)

+        // Setup timer for releasing memory
+        // If this fails, then we wont have a timer to release unused memory. We 
can live with that.
+        (void) NS_NewTimer(&mRecycleTimer, nsRecycleTimerCallback, this,
+                           NS_SEC_TO_MS(mRecycleAfter), NS_PRIORITY_LOWEST, 
NS_TYPE_REPEATING_SLACK);

Who owns the timer? Do we need to hold a ref to it? And...

+    // Cancel recycle timer
+    delete mRecycleTimer;

...Should this release?


+void*
+nsRecyclingAllocator::Calloc(PRUint32 items, PRUint32 bytes)
+{
+    PRUint32 totalsize = items * bytes;
+    void *ptr = Malloc(totalsize);
+    if (ptr)
+        memset(ptr, 0, totalsize);
+    return ptr;
+}

See comment about calloc() above. Maybe just pass a flag to Malloc() that says 
whether to zero out the block, so we can call calloc() in those cases that do a 
new allocation?

Address those and sr=sfraser

Comment 24

[Suresh Duddi (gone)]

All comments accepted.

nsRecyclingAllocator own the nsITimer and has to release it . I changed the
delete mRecycleTimer; to
    mRecycleTimer->Cancel();
    NS_RELEASE(mRecycleTimer);

Will attaching new patch in case you wanna take a look.

Comment 25

[Suresh Duddi (gone)]

Attachment: Comments from simon

Changes from previous patch:
- nsRecycleTimerCallback made static method of nsRecyclingAllocator
- Calling calloc() instead of malloc() + memset().
- NS_RELEASE(mRecycleTimer)
- changed modules/libjar/nsZipArchive.cpp to call Calloc() instead of Malloc()
as was in earlier patch

Comment 26

[Brendan Eich [:brendan]]

Comment on attachment 66187 [details] [diff] [review]
Comments from simon

dp, I owe you an sr.  My nit:

+    if (zeroit)
+      ptr = calloc(1, bytes);
+    else
+      ptr = malloc(bytes);

(1) use four space indentation if you must;
(2) better: use ptr = zeroit ? calloc(1, bytes) : malloc(bytes); all on one
line.

/be

Comment 27

[Suresh Duddi (gone)]

Fix checked in.