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

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, defect)

Description

[Brian Hackett [Laid off!]]

Attachment: patch

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.

Comment 1

[Luke Wagner [: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.

Comment 2

[Brian Hackett [Laid off!]]

Attachment: updated

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.

Comment 3

[Luke Wagner [: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.)

Comment 4

[Chris Peterson [:cpeterson]]

bhackett: did you forget to land this r+'d patch from August 2012? Is it still relevant?

Comment 5

[Brian Hackett [Laid off!]]

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.

Comment 6

[Chris Peterson [:cpeterson]]

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.