Don't waste unused chunks when servicing large allocations in LifoAlloc

RESOLVED WONTFIX

Status

()

defect
RESOLVED WONTFIX
7 years ago
5 years ago

People

(Reporter: bhackett, Assigned: bhackett)

Tracking

Other Branch
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [js:t])

Attachments

(1 attachment, 1 obsolete attachment)

Assignee

Description

7 years ago
Posted patch patch (obsolete) — Splinter Review
Spun off from bug 778724.

The memory in LifoAlloc can be released, which does not explicitly free it but makes it available for future allocations.  When servicing those future allocations, the LifoAlloc will walk through previous chunks looking for one which is big enough.  Any chunks which are skipped over in this way are unavailable for use until the allocator is released to an earlier point.

With bug 778724, we occasionally allocate chunks which are considerably larger than the default size, e.g. arrays of Bytecode* for large scripts, and can potentially end up with a lot internal fragmentation in the allocator as a result (did not measure how much).  The attached patch mitigates this by inserting any skipped chunks which are totally unused immediately after the chunk which is eventually returned, making them usable in subsequent allocations.
Attachment #651000 - Flags: review?(luke)
IIUC, if the 'last' chunk cannot satisfy the allocation (!last->canAlloc(n)) and it is empty (!last->used()), it will not be added after 'newChunk' and thus contribute to fragmentation.  Seems easy enough to fix.

Also, you can push the declaration of 'prev' into the 'if (first)' branch.
Assignee

Comment 2

7 years ago
Posted patch updatedSplinter Review
Allows reuse of the last (unused) chunk in a LifoAlloc and fixes a bug that showed up in testing where chunks with marks in them could be moved around.
Assignee: general → bhackett1024
Attachment #651000 - Attachment is obsolete: true
Attachment #651000 - Flags: review?(luke)
Attachment #654177 - Flags: review?(luke)
Comment on attachment 654177 [details] [diff] [review]
updated

Review of attachment 654177 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/ds/LifoAlloc.cpp
@@ +69,5 @@
> +    /*
> +     * Remove any unused chunks we skipped over for being too small, and append
> +     * them after the chunk we do end up returning, to avoid fragmentation when
> +     * servicing large allocations in allocators with a lot of unused space.
> +     */

I think this comment needs to explain a bit more about our operating assumptions; something to the effect of:

In the abstract, this chunk-rearranging is an O(n) operation (where n is the total number of chunks in the LifoAlloc) which means that, in the abstract, doing N small allocations followed by a release followed by M large allocations would take O(N*M) time. We assume that this cost is amortized by:
 (1) the relatively large size of BumpChunk allocations which should keep N and M relatively small
 (2) the relatively large amount of work performed by the caller for each large allocation
The primary intended beneficiary of this optimization is JSCompartment::analysisLifoAlloc which satisfies both criteria and allocates/releases/reuses large amounts of memory with large individual allocations.

@@ +76,4 @@
>      if (first) {
>          /* Look for existing, unused BumpChunks to satisfy the request. */
> +        while (true) {
> +            JS_ASSERT_IF(prev, prev->next() == latest && (prev->used() || markCount));

Can you JS_ASSERT(!latest->canAlloc(n))?  That would also make it more clear when reading why we start by immediately ignoring latest.

@@ +81,5 @@
> +                /*
> +                 * Remove from the list and append to removed. Unused chunks
> +                 * aren't removed if there are marks in the allocator, as
> +                 * releasing will break if chunks have been rearranged.
> +                 */

This comment explains the two conjuncts above so could you put it before the if?

@@ +97,5 @@
> +                    prev->setNext(latest);
> +                } else {
> +                    first->setNext(removed);
> +                    removed = first;
> +                    first = latest;

This first == latest special-case handling could be removed by having 'prev' be a pointer to the 'next' pointer of the previous BumpChunk or, if first == latest, LifoAlloc::first.  (This requires getting &BumpChunk::next_, but BumpChunk isn't a real abstraction anyway (LifoAlloc is the abstraction, BumpChunk is an internal detail), so it seems fine making 'next' a public field.)
Attachment #654177 - Flags: review?(luke) → review+
Whiteboard: [js:t]
bhackett: did you forget to land this r+'d patch from August 2012? Is it still relevant?
Flags: needinfo?(bhackett1024)
OS: Mac OS X → All
Hardware: x86 → All
Assignee

Comment 5

5 years ago
This bug was designed to help bug 778724, which isn't relevant anymore.  This could potentially still help but without anything that definitely would benefit I don't see much value in landing it now.
Flags: needinfo?(bhackett1024)
I'm closing this WONTFIX (to move this bug off the list of open bugs with r+'d patch), but if you think it might be useful to land someday, please reopen it.
Status: NEW → RESOLVED
Closed: 5 years ago
Resolution: --- → WONTFIX
You need to log in before you can comment on or make changes to this bug.