289571 - Optimization for nsRecyclingAllocator

Status: VERIFIED FIXED

(Core :: XPCOM, defect)

Description

[Alfred Kayser]

The attached patch optimizes the nsRecyleAllocator as follows:
* Don't use an fixed size array to keep the list of freed items (use the memory
blocks themselves)
* Initiate the timer in the free instead of alloc call.

The principle of thinking behind this is as follows:
The task of the nsRecyclingAllocator is to maintain x entries after the free, so
that they can be reused, and to only free them really after an 'idle time'
period. So, instead of maintaining a list of allocated items, the new code will
only maintain a list of 'freed' items, checked for at the next alloc.

This saves the memory size of the allocator from 8*4+n*12 bytes to 7*4 bytes,
and reduces codesize of the allocator. The timer is only started after the first
free, instead of the first alloc.
Also the maximum number of entries to be kept is no longer limited.

So, for example if the GIF decoder only allocates and frees one item at the
time, even if bucket size is set larger than 1, it has then only the overhead of
the 7*4 and the 4 bytes for the allocated block.

So:
init {
  set members (max items)
}
alloc {
  if (freelist) return block from freelist;
  allocate new block, store size in the extra bytes in front.
}
free {
  if (max(freeItems)) 
    PR_Free(block)
  else
    Add block to the freelist, using block itself to store the next pointer
    Start timer to free the freelist
}
freeunusedbuckets {
  stop timer
  free all items from the freelist
}
timer {
  if (!touched) freeunusedbuckets()
}
destroy {
  freeunusedbuckets();
}

Comment 1

[Alfred Kayser]

Attachment: Patch as described above

Comment 2

[Stephen Donner [:stephend] Not actively reading bugmail]

Couple of spelling/grammatical nits:

* Setup is a noun, you want Set up as a verb (these were pre-existing, but
please fix them since you're here)
* Any place you see "dont", please add an apostrophe to make it a proper contraction

Comment 3

[Doug Turner (:dougt)]

Comment on attachment 180067 [details] [diff] [review]
Patch as described above

punting to dbaron.

Comment 4

[Caleb]

CC'ing dbaron because he might have missed this?

Comment 5

[Alfred Kayser]

dbaron, can you review this? 
This is a small and simple optimisation saving on footprint and codesize, all to make the core of the mozilla applications smaller and faster!

Comment 6

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Some initial comments:

The comment in the header file about mLock needs to be updated, since one of the things it protects no longer exists.

You removed the locking from Init.  The current API seems to allow re-initialization, which implies that such locking may be necessary.  It's not well documented what calling |Init| again means, though.

Comment 7

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

So removing the locking from Init actually seems like it's OK, since FreeUnusedBuckets does locking.  However, the locking that's done seems insufficient to protect mRecycleTimer -- there are a whole bunch of cases where multiple calls on different threads could do bad things (double-free, double-assignment) to mRecycleTimer.

Comment 8

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Did you do any measurements showing that this is a performance improvement?

Comment 9

[Alfred Kayser]

Ok, I will checking the locking and mRecycleTimer thing.
As for performance, I wont expect a real measurable performance gain 
(and hopefully no loss (but will try to test this out)).
The gains are in codesize and memory usage.

Note, currently nsRecyclingAllocator is only used in:
nsGIFDecoder2.cpp and nsZipArchive.cpp

Comment 10

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Please fix the comment about mMaxBlocks in nsRecyclingAllocator.h -- it's the maximum size of the freelist, and it looks like it's always been (although it also looks like the code used to crash when the freelist exceeded it, which meant it really was the maximum number of blocks).

I think you should lock around the uses of mRecycleTimer -- both in FreeUnusedBuckets (just move locking earlier) and in Free (where you might want to add a block scope just in case someone adds something later in the function).  You should also update the comment in the .h about mLock.

With those changes, r=dbaron, although I'd like to see the revised version of the patch.

(FWIW, I think the way this uses timers is a bit odd.  I'm not sure if a timer is really what's wanted here.)

Comment 11

[Alfred Kayser]

Attachment: V2: With comments from dbaron incorporated

>> Please fix the comment about mMaxBlocks in nsRecyclingAllocator.h
Done.

>> I think you should lock around the uses of mRecycleTimer
Lock also around mRecycleTimer

>> You should also update the comment in the .h about mLock.
Done.

Furthermore, mTouched is now protected by mLock, and doesn't need PR_AtomicSet anymore. In all cases it was immediately followed by the lock anyway.
This also means that first time malloc (with empty freelist) there is no overhead (no lock, no AtomicSet), except for the addition of 4 bytes to the block. 

Renamed FreeUnusedBuckets to ClearFreeList to better indicate its real function.

Statistics:
    Codesize:                 Before             After    Savings
    nsRecyclingAllocator.obj: 19.734             17.654   2.080 bytes
    xpcomds_s.lib:            983.762            981.232  2.530 bytes
    Memory usage:             9*4+mMaxBlocks*12  7*4      Upto 296 bytes

Generally, this should have a small impact on startup, as Init doesn't need to setup an array of mMaxBuckets entries (mMaxBuckets times a 'new' operation) and the first malloc doesn't need to lock or atomicset things... It will be unmeaserable small though. Note that the overhead of atomicset is not very small as a real 'atom', as it really consists of lock, set and unlock operation...

Comment 12

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 204151 [details] [diff] [review]
V2: With comments from dbaron incorporated

It's not clear to me why you merged FindFreeBlock and AddToFreeList into their callers.  You're allowed to document that a lock must be held when calling a function -- there is probably even a way to assert it.  I didn't look over that merging very closely anyway, but r=dbaron (and feel free to undo it if you want).

Comment 13

[Alfred Kayser]

Comment on attachment 204151 [details] [diff] [review]
V2: With comments from dbaron incorporated

I choose to inline the functions as this reduces codesize, and optimizes the most common path. 
The functions were reduced to very simple linked list operations anyway.

Comment 14

[Doug Turner (:dougt)]

Comment on attachment 204151 [details] [diff] [review]
V2: With comments from dbaron incorporated

do you need someone to check this in?

Comment 15

[Alfred Kayser]

I don't have CVS access, so if someone can check this in for me, I would me much obliged!

Comment 16

[Stephen Donner [:stephend] Not actively reading bugmail]

1 out of 1 hunk FAILED -- saving rejects to file nsRecyclingAllocator.cpp.rej
1 out of 2 hunks FAILED -- saving rejects to file nsRecyclingAllocator.h.rej

Alfred, can you do a cvs update and then post a new patch for someone to land?

Comment 17

[Alfred Kayser]

Attachment: V3: Updated to current tree (trunk)

Comment 18

[Stephen Donner [:stephend] Not actively reading bugmail]

2005-12-22 16:08	timeless%mozdev.org 	mozilla/ xpcom/ ds/ nsRecyclingAllocator.h 	1.13 	17/56  	Bug 289571 Optimization for nsRecyclingAllocator patch by [e-mail] r=dougt sr=dbaron
2005-12-22 16:08	timeless%mozdev.org 	mozilla/ xpcom/ ds/ nsRecyclingAllocator.cpp 	1.18 	116/202 

timeless landed this.  Leaving it up to Alfred to mark FIXED.

Comment 19

[Alfred Kayser]

Marking as fixed. The codesize is reduced, and the allocator seems to work OK.

What is the policy for the 1.8 branch for FF2.0?

  libxpcom_core.so
  	Total:	       -736 (+243/-979)
  	Code:	       -736 (+243/-979)
  	Data:	         +0 (+0/+0)
  	       -736 (+243/-979)	text (CODE)
  		       -736 (+243/-979)	UNDEF:libxpcom_core.so:text
  			       +113	nsRecyclingAllocator::ClearFreeList()
  			       +104	nsRecyclingAllocator::Free(void*)
  			        +26	nsRecyclingAllocator::Malloc(unsigned, int)
  			        -13	nsRecyclingAllocator::nsRecycleTimerCallback(nsITimer*, void*)
  			        -37	nsRecyclingAllocator::nsRecyclingAllocator[not-in-charge](unsigned, unsigned, char const*)
  			        -37	nsRecyclingAllocator::nsRecyclingAllocator[in-charge](unsigned, unsigned, char const*)
  			        -90	nsRecyclingAllocator::~nsRecyclingAllocator [not-in-charge]()
  			        -90	nsRecyclingAllocator::~nsRecyclingAllocator [in-charge]()
  			       -162	nsRecyclingAllocator::FindFreeBlock(unsigned)
  			       -165	nsRecyclingAllocator::AddToFreeList(nsRecyclingAllocator::Block*)
  			       -179	nsRecyclingAllocator::FreeUnusedBuckets()
  			       -206	nsRecyclingAllocator::Init(unsigned, unsigned, char const*)