1111252 - IonMonkey: Use Vector's API more cleverly to eliminate intermediate allocations

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, enhancement)

Description

[Dan Gohman [:sunfish]]

Attachment: reserve.patch

This patch follows up on bug 1105261, adding an infallibleReserve method to Vector, for cases where it is desired to prereserve the inline allocation space. It then uses infallibleReserve, and plain reserve, in various places in SpiderMonkey to reduce intermediate allocations and error checking.

Comment 1

[Jeff Walden [:Waldo]]

Comment on attachment 8536072 [details] [diff] [review]
reserve.patch

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

::: js/src/jit/AliasAnalysis.cpp
@@ +163,5 @@
>  bool
>  AliasAnalysis::analyze()
>  {
>      Vector<MInstructionVector, AliasSet::NumCategories, JitAllocPolicy> stores(alloc());
> +    stores.infallibleReserve(AliasSet::NumCategories);

The inline capacity of a Vector is currently considered an implementation detail, so really it's impossible for this method to be used correctly, in the sense you mean for it to be used.  I'm not sure whether we want to change this or not -- or how we might want to change this.

Right now, a Vector<T, N> will have N elements of type T inline storage if sizeof(T) * N <= 1024.  However, if N and sizeof(T) conspire correctly, Vector<T, N> will M elements inline storage, where M < N.  For small T and N that basically won't happen.  But we can't ignore the edge case entirely -- for example, if someone used a Vector to back up entire pages of memory or so and wanted inline storage (say, because it would always contain at least one page).

The benefit to possibly M < N is that Vector is 100% general -- you can stuff anything you want in it at all, requesting any particular inline amount you want, and you'll get a best-effort attempt to use that much inline space.

The demerit to M < N is that because 1024 and the calculations that use it) are implementation details that likely shouldn't be promoted to interface, there's a mini-perf loss when the user grows a Vector past the indeterminate-size inline storage limit, and constant reservations/vector growth under that limit appear fallible when they never will be fallible.

So we have a few options.

1) Do nothing, allow M < N, do not expose M.  No code may assume any vector has any particular amount of inline storage.
2) Allow M < N, but expose M = Vector<T, N>::InlineCapacity.  Code can assume that much inline storage is available, assert that space reservations up to M, assert that growth up to M will not fail, &c.
3) Forbid M < N and *guarantee* that Vector<T, N> has N inline capacity.  Code can make all the assumptions from 2 using N directly.  Some code that requires more than 1024 bytes inline space will no longer compile (enforced by, say, static_assert).

3 does not seem like a good choice to me.  If someone has a super-large vector, we don't want them going off and implementing their own vector (and adding that much complexity) just because of an interface simplification we made.

1 and 2 both have some appeal to me.  1 draws a clear line in the sand; it's easy to see that a particular vector use doesn't transgress, because we wouldn't have an infallibleReserve, and reserve/initCapacity/resize/growBy and so on always require failure-checks.  2 is more powerful, but by making the line fuzzier makes bugs easier.  And probably some people will assume M = N, not realizing they have to use their vector's actual inline capacity constant.

So.  Comments?

Comment 2

[Nicolas B. Pierron [:nbp]]

Don't we want to use a mozilla::Array for statically known size instead of a Vector, after all the JitAllocPolicy should not be used as the inline capacity is reserved on the stack.

Comment 3

[Jeff Walden [:Waldo]]

Comment on attachment 8536072 [details] [diff] [review]
reserve.patch

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

r=me on everything except for AliasAnalysis.cpp and Vector.h.  Those two require more discussion, see my previous comment.

::: js/src/jit/Ion.cpp
@@ +2472,5 @@
>  
>          if (data.numActualArgs >= numFormals) {
>              data.maxArgv = args.base() + 1;
>          } else {
>              // Pad missing arguments with |undefined|.

This comment belongs on the append-undefined loop below, right?

And the append-args.base()[i] loop should have "// Append |this| and any provided arguments." by it, because appending starting at 1, and going to length+2 is not immediately clear.

This block could use a MOZ_ASSERT(vals.length() == 0) at the start, because otherwise the len < numFormals + 1 assertion is possibly not right.

@@ +2475,5 @@
>          } else {
>              // Pad missing arguments with |undefined|.
> +            if (!vals.reserve(Max(args.length() + 1, numFormals + 1)))
> +                return false;
> +        

Trailing WS.

@@ +2485,3 @@
>  
>              MOZ_ASSERT(vals.length() >= numFormals + 1);
>              data.maxArgv = vals.begin();

This is kind of dodgy, relying as it does on the vector being live so long as this particular value is needed/live, with no guarantees of it.  In a separate bug/followup, is there a reason we can't move the Vector directly into EnterJitData?  Would let us more or less get rid of the zero-length assertion, I think.

::: js/src/jit/IonBuilder.cpp
@@ +5584,5 @@
>      // Keep track of the originals as we need to case on them for poly inline.
>      bool hasClones = false;
>      ObjectVector targets(alloc());
> +    if (!targets.reserve(originals.length()))
> +        return false;

Fine enough (along with the infallibleAppend change beneath) as it goes, but is it the case that most entries in originals will pass the gauntlet below, or that originals will usually be pretty small?  I don't know.  Worth asking someone who knows and can intelligently discuss/describe the tradeoffs in a comment here, for everyone's edification.

Comment 4

[Dan Gohman [:sunfish]]

I removed the AliasAnalysis and Vector.h parts, and fixed up the things you commented on.

It looks like we can fold the vals Vector into EnterJitData. I'll submit a separate bug for that with a patch. And, I'll ask around about the IonBuilder question.

https://hg.mozilla.org/integration/mozilla-inbound/rev/1a46aaa946e5

Comment 5

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/1a46aaa946e5