688772 - [pacman] Speculatively inline Array::setUintProperty in the JIT

Status: RESOLVED WONTFIX

(Tamarin Graveyard :: Library, defect)

Description

[Felix S. Klock II [:pnkfelix, :fklock]]

For Array stores on arrays that (1) are dense, (2) are not subclassed (due to that introducing potential sealed-ness [*], (3) have no holes and (4) start at 0, we can use a similar path to the inline code that recently landed for Vector (Bug 599099).

This is the analog of Bug 688486, and I plan to have it reuse the same infrastructure for tracking the simpleness of Array instances.

[*] We might still be able to allow the fast-path for subclasses of arrays, as long as they are dynamic.  The logic determining whether an array is simple during construction time has that information available.

Comment 1

[Felix S. Klock II [:pnkfelix, :fklock]]

One detail here that Vectors get for free: this optimization may only make sense for monomorphic arrays where we can statically speculate what values the Array holds.

It may be reasonable to make array's carry dynamic state tracking whether their contents are all of the same type; it is just more heavy-weight than what I originally conceived of with the simply-dense property I used in Bug 688486.

But that's not enough on its own, since the supposed payoff here is for the JIT to emit a specialized path that avoids the out-of-line call out.  That will only make sense when the JIT can correctly guess for what type it should emit the specialized path.

For example, it may be reasonable to speculate that in the code below, a is an array that holds only int's (and ) and have a specialized path for that case:

  var x:int
  var a:Array
  var i:int
  ...
  a[i] = x

Compare that with this case:
  var y:*
  var b:Array
  var j:int
  ...
  b[j] = y

In this second case, its hard for me to immediately see what we should do in the JIT to produce compact useful in-line code, since we don't have much of a clue what type b's contents are likely to be.  Maybe I am overlooking some other trick...

Comment 2

[Mason Chang]

Hi Felix,

I'm working on speculative optimizations in Halfmoon via runtime profiling. We basically run the ActionScript code for a few iterations, gather the runtime types of all variables, and then do true speculative optimizations based on the gathered runtime data in the half-moon jit. Eg, in your case (var y:*), we'd see the value y is actually assigned and speculatively coerce y to the observed runtime type. If y is not the same type we profiled, we have to deoptimize out of the JIT code. We only perform speculative optimizations on untyped values. In the cases where a value is type annotated, we don't speculate. You can see this code in halfmoon, if you look at halfmoon::hm-liremitter.cpp::speculate_array.

So the code in case:

var y:*	// We profiled and saw y is only an int
var b:Array
var j:int
...
b[j] = y // We know b is an array, and y is an int, specialize here

As for figuring out the type of all values stored in an array, that's a bit more work that I haven't thought much about yet.

Comment 3

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to Mason Chang from comment #2)
> As for figuring out the type of all values stored in an array, that's a bit
> more work that I haven't thought much about yet.

yeah, one point I should have stated more explicitly in my post above is why its important to know more about the array you are storing into, at least at the moment. 

If you are going to overwrite an RCObject in the array, then you need to decrement its reference count, and I doubt that logic is going to be reasonable to inline via the JIT at every Array setUintProperty.  (e.g. see how Lars handled that case in emitInlineVectorWrite in his patch for Bug 599099)

I don't know whether it will be useful to emit inline code that chooses between one specialized out-of-line call and another generalized one.  My gut tells me that's a hard path to go down, unless you get serious payoff from the specialization.

So I was planning to focus first on gathering data on whether we even have a significant number of monomorphic arrays that arise dynamically in practice.  If not, then I'll go back to the drawing board about what to do here.

Comment 4

[Lars T Hansen]

(In reply to Felix S Klock II from comment #1)
> One detail here that Vectors get for free: this optimization may only make
> sense for monomorphic arrays where we can statically speculate what values
> the Array holds.
> 
> It may be reasonable to make array's carry dynamic state tracking whether
> their contents are all of the same type; it is just more heavy-weight than
> what I originally conceived of with the simply-dense property I used in Bug
> 688486.

It is, but if there are enough arrays like that then it will probably pay off.

> But that's not enough on its own, since the supposed payoff here is for the
> JIT to emit a specialized path that avoids the out-of-line call out.  That
> will only make sense when the JIT can correctly guess for what type it
> should emit the specialized path.

Yes.

> 
> For example, it may be reasonable to speculate that in the code below, a is
> an array that holds only int's (and ) and have a specialized path for that
> case:
> 
>   var x:int
>   var a:Array
>   var i:int
>   ...
>   a[i] = x
> 
> Compare that with this case:
>   var y:*
>   var b:Array
>   var j:int
>   ...
>   b[j] = y
> 
> In this second case, its hard for me to immediately see what we should do in
> the JIT to produce compact useful in-line code, since we don't have much of
> a clue what type b's contents are likely to be.  Maybe I am overlooking some
> other trick...

I agree, in the second case it's not useful to speculate statically.

For Array we want to do a decent job, so that they are not horrifically expensive, but AS3 programmers can use Vector for performance when they need to go beyond that.  We should cover the easy cases: storing int into an Array.<int>, storing Number into an Array.<Number>, etc, when Array.<T> has a specialized representation.

The other thing here is to specialize the call-out to avoid what is currently a much too expensive general atomWriteBarrier.  It yielded good speedups on the Vector code when we could determine that the Vector contained some RCObject, not atom.  So for example, storing a known int into an Array.<*> can use a faster callout with only the "decrement" case of atomWriteBarrier.  HOWEVER, that's only true if the int is not boxed as a double, ie, on 64-bit systems or if we know the int's value does not require boxing, OR if the Array.<*> has a non-boxing representation.

(None of that has much to do with inlining, but it does make use of type information available "inline", I guess.  I expect I'm repeating myself :-)

Comment 5

[Felix S. Klock II [:pnkfelix, :fklock]]

not going to spend time on this right now, though it would be interesting if we can easily address the ideas Lars described in comment 4

Comment 6

[Sylvestre Ledru [:Sylvestre]]

Tamarin is a dead project now. Mass WONTFIX.

Comment 7

[Sylvestre Ledru [:Sylvestre]]

Tamarin isn't maintained anymore. WONTFIX remaining bugs.