1004816 - Simplify FreeSpan

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

FreeSpan is kind of awful. I have patches to clean it up.

Current design:
- For spans other than the final span, |first| points to the first thing and
  |last| points to the last thing.
- For the final span, |last| points to the last byte in the arena.
- If the final thing in the arena is not free, the final span will be
  degenerate, with |first| pointing just past the arena's end. (Another way of
  saying this: an in-use thing is always followed by a FreeSpan, albeit a
  possibly degenerate one.) An exception to this: spans created by initAsEmpty
  are even more degenerate, having first==4096 and last==4095; this works in
  practice because isEmpty() is true for this case.

New design:
- An empty span has first==0 and last==0.
- For non-empty spans, |first| points to the first thing and |last| points to
  the last thing.
- Every free list ends with an empty span.

This is a more typical list design, and it doesn't have all the special cases.

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: (part 1) - Simplify and encapsulate FreeSpan

This patch implements the design described in comment 0. Much nicer. Look at
the change in checkSpan() in particular.

The patch also makes FreeSpan::{first,last} private. The encapsulation isn't
total -- for example, Arena::finalize() would need changing if the internal
representation of FreeSpan change -- but I think it's an improvement
nonetheless.

I was unable to detect any change in performance. The hottest relevant code is
the first case in FreeList::allocate(), and that's unchanged.

The only thing that worries me about this patch is setAsFullyUnused() is
entirely untested. I wrote a patch that caused that function to crash upon
entry, and a try server run was entirely green! :( Perhaps Niko or Lars knows
about this.

Comment 2

[Nicholas Nethercote [inactive]]

Attachment: (part 2) - Remove FreeList::infallibleAllocate()

infallibleAllocate() is almost the same as allocate(). It's not nearly hot
enough for this specialization to be worthwhile. This patch removes it.

Comment 3

[Nicholas Nethercote [inactive]]

Note that these patches apply on top of those in bug 1004790.

Comment 4

[Nicholas Nethercote [inactive]]

Niko and Lars: any comments about the final paragraph of comment 1? Thanks.

Comment 5

[Lars T Hansen [:lth]]

Re comment #4, I have no insights - I had the impression that the setAsFullyUnused function was part of the general freelist management regime, in the code I have I see only one indirect use, from FinalizeTypedArenas.  I would ask the GC guys.

Comment 6

[Niko Matsakis [:nmatsakis]]

setAsFullyUnused() was added as part of the extensions to support faster parallel allocation. I guess that we never got the benchmarks in question into the codebase, unfortunately. I haven't read the patch yet so I can't comment if it interferes with that work, though Lars is currently redesigning the GC support for parallel execution as well.

A test that should exercise setAsFullyUnused() can be found here:

https://github.com/nikomatsakis/arewefastyet/blob/nmatsakis-microbenchmarks/benchmarks/misc/tests/assorted/misc-parjs-deform.js

(I was planning on submitting it to AWFY at some point, but I never did.)

Comment 7

[Nicholas Nethercote [inactive]]

Thanks, Niko! That test certainly does hit setAsFullyUnused()... in fact it hits it 1.25 *million* times, which is surprising and possibly suspicious...

The behaviour seems to be the same with my patches applied -- there's no output, but it doesn't crash, and the execution time is similar (both "real" and "user", which are quite different). So I think the patches are ok.

Comment 8

[Niko Matsakis [:nmatsakis]]

njn -- hitting it 1.25 million times is indeed the expected behavior. It clears out the arenas after each execution, because all data is known to be dead.

Comment 9

[Nicholas Nethercote [inactive]]

Attachment: (part 1) - Simplify and encapsulate FreeSpan

This patch fixes a case I missed in ArenaHeader::isEmpty(). The effects of this
would have been that when running parallel JS code, sometimes empty arenas
would have been kept on the zone's arena list instead of being released to the
Chunk. I searched for any similar cases involving ArenaMask and didn't find
any.

Comment 10

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Comment on attachment 8419200 [details] [diff] [review]
(part 1) - Simplify and encapsulate FreeSpan

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

::: js/src/gc/Heap.h
@@ +174,5 @@
> +
> +    // This sets |first| and |last|, and also sets the next span stored at
> +    // |last| as empty. (As a result, |firstArg| and |lastArg| cannot represent
> +    // an empty span.)
> +    void initWithEmptyNext(uintptr_t firstArg, uintptr_t lastArg, size_t thingSize) {

It seems like this belongs more in FreeList.

@@ +222,5 @@
>      }
>  
>      const FreeSpan *nextSpan() const {
> +        JS_ASSERT(!isEmpty());
> +        return reinterpret_cast<FreeSpan*>(last);

Would be better to call nextSpanUnchecked here.

@@ +255,3 @@
>      }
>  
> +    bool inFreeList(uintptr_t thing) {

Seems like this would be better off as a member of FreeList, with perhaps some helper function in FreeSpan to check if thing is in the range of a FreeSpan.

@@ +268,5 @@
>      }
>  
> +    // This is useful when iterating over an arena. It takes and possibly
> +    // updates a (thing,span) pair.
> +    static void moveForwardIfFree(uintptr_t &thing, FreeSpan &span, size_t thingSize) {

I'm not at all sold on moving this code here from the iterator. It won't make any sense to someone reading this file, and it will just annoy someone reading the iterator file. Is there a reason the code needs to move?

@@ +269,5 @@
>  
> +    // This is useful when iterating over an arena. It takes and possibly
> +    // updates a (thing,span) pair.
> +    static void moveForwardIfFree(uintptr_t &thing, FreeSpan &span, size_t thingSize) {
> +        JS_ASSERT(thing != 0);

Just JS_ASSERT(thing).

Comment 11

[Nicholas Nethercote [inactive]]

> > +    void initWithEmptyNext(uintptr_t firstArg, uintptr_t lastArg, size_t thingSize) {
> 
> It seems like this belongs more in FreeList.

In both of the places it's used we only have a FreeSpan, so this won't work.

> > +    bool inFreeList(uintptr_t thing) {
> 
> Seems like this would be better off as a member of FreeList, with perhaps
> some helper function in FreeSpan to check if thing is in the range of a
> FreeSpan.

This already is something of a helper; it's called by InFreeList(). InFreeList() itself is called on ArenaHeaders which aren't necessarily at the head of the list. So it's a weird one, but we can't put it in FreeList.

> > +    // This is useful when iterating over an arena. It takes and possibly
> > +    // updates a (thing,span) pair.
> > +    static void moveForwardIfFree(uintptr_t &thing, FreeSpan &span, size_t thingSize) {
> 
> I'm not at all sold on moving this code here from the iterator. It won't
> make any sense to someone reading this file, and it will just annoy someone
> reading the iterator file. Is there a reason the code needs to move?

Neither |first| nor |last| have getters, and both would have to be added to move it back. And moving it back would diminish the encapsulation -- the iterator code would have to know about FreeSpan's internals, whereas with the current code it doesn't. So I'd prefer to keep it as is.

Comment 12

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

> In both of the places it's used we only have a FreeSpan, so this won't work.

It looks like there are some FreeLists pretty close at hand. I think you could probably make this work.

> Neither |first| nor |last| have getters, and both would have to be added to move it back. And
> moving it back would diminish the encapsulation -- the iterator code would have to know about
> FreeSpan's internals, whereas with the current code it doesn't. So I'd prefer to keep it as
> is.

In my opinion, when you have methods with names like moveForwardIfFree and initWithEmptyNext, there isn't any real encapsulation anyway. The purpose of abstraction is to allow the reader of code to avoid having to think about how a lower-level thing is implemented so that they can focus on the code at hand. Someone who sees a call to moveForwardIfFree or initWithEmptyNext will just have to read the implementations of those methods or else they'll have very little idea what the method is doing. Given the choice between superficial encapsulation and no encapsulation, I would prefer no encapsulation (i.e., just inlining the methods). At least the code is easier to follow. If you have to add some accessors, please go ahead and do that.

Comment 13

[Nicholas Nethercote [inactive]]

> It looks like there are some FreeLists pretty close at hand. I think you
> could probably make this work.

Nope. The one in Arena::finalize() in particular: that call is setting the final span in the list, and there is no FreeList available in that function. Arena::setAsFullyUnused() isn't much better. I renamed initWithEmptyNext() as initFinal(), though.

> If you have to add some accessors, please go ahead and do that.

I made ArenaCellIterImpl a friend of FreeSpan instead.

This is good enough to land, but I might do a follow-up to improve the encapsulation.

Comment 14

[Nicholas Nethercote [inactive]]

Try looks good:
https://tbpl.mozilla.org/?tree=Try&rev=32af36103a70

Comment 15

[Nicholas Nethercote [inactive]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/8cd7d42ddf56
https://hg.mozilla.org/integration/mozilla-inbound/rev/7b45070d7493

Comment 16

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/8cd7d42ddf56
https://hg.mozilla.org/mozilla-central/rev/7b45070d7493