Stable vs Unstable maps

[janngo...@gmail.com]

What is the difference between a stable and unstable map?

Context: I'm trying to understand this line of code https://cs.chromium.org/chromium/src/v8/src/compiler/js-native-context-specialization.cc?l=3227&rcl=4c53f9a51444393133ff303952f1296603d44ab7 but can't seem to find any documentation about stable maps. Comments and diffs are sparse on the subject as well.

[Leszek Swirski]

Hi,

A stable map is one from which a transition has never been observed, i.e. it's the leaf of the transition tree and objects with that map can be assumed to be "stable". Perhaps "is_leaf" or "never_transitioned_away_from" could be alternative names but it's a subtle concept to name and naming is hard anyway :)

In the code you linked, I'm not 100% familiar with the reasoning but I assume that the compiler assumes that inferred stable maps are a "safe bet" as far as speculation is concerned, since they're a reliable end state, and can be assumed to be a correct inference even if the data is unreliable. That's mostly just a guess from the context though.

- Leszek

On Tue, 31 Dec 2019, 05:46 , <janngo...@gmail.com> wrote:

What is the difference between a stable and unstable map?

Context: I'm trying to understand this line of code https://cs.chromium.org/chromium/src/v8/src/compiler/js-native-context-specialization.cc?l=3227&rcl=4c53f9a51444393133ff303952f1296603d44ab7 but can't seem to find any documentation about stable maps. Comments and diffs are sparse on the subject as well.

--
--
v8-dev mailing list
v8-...@googlegroups.com
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to v8-dev+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/v8-dev/d8383180-787c-4bac-8ac3-d9295d400b2c%40googlegroups.com.

[janngo...@gmail.com]

Thanks!

What is the point of marking a map as stable? If there was a normalization isn't a new map created? So if types can't get mixed up after normalization, what is the point of marking a map as stable?

- Jann

On Tuesday, December 31, 2019 at 1:33:36 AM UTC-6, Leszek Swirski wrote:

Hi,

A stable map is one from which a transition has never been observed, i.e. it's the leaf of the transition tree and objects with that map can be assumed to be "stable". Perhaps "is_leaf" or "never_transitioned_away_from" could be alternative names but it's a subtle concept to name and naming is hard anyway :)

In the code you linked, I'm not 100% familiar with the reasoning but I assume that the compiler assumes that inferred stable maps are a "safe bet" as far as speculation is concerned, since they're a reliable end state, and can be assumed to be a correct inference even if the data is unreliable. That's mostly just a guess from the context though.

- Leszek

On Tue, 31 Dec 2019, 05:46 , <janngo...@gmail.com> wrote:

What is the difference between a stable and unstable map?

Context: I'm trying to understand this line of code https://cs.chromium.org/chromium/src/v8/src/compiler/js-native-context-specialization.cc?l=3227&rcl=4c53f9a51444393133ff303952f1296603d44ab7 but can't seem to find any documentation about stable maps. Comments and diffs are sparse on the subject as well.

--
--
v8-dev mailing list
v8-...@googlegroups.com
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.

To unsubscribe from this group and stop receiving emails from it, send an email to v8-...@googlegroups.com.

[Tobias Tebbi]

As long as a map is stable, no object with this map has changed map, which is a very useful property especially for optimized code. To be able to exploit this in optimized code, transitioning from a previously stable map will invalidate and deoptimize all optimized code that made use of the map being stable up to this point.

- Tobias

To unsubscribe from this group and stop receiving emails from it, send an email to v8-dev+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/v8-dev/b2064f2a-93ea-4354-ac53-150a8eb56f68%40googlegroups.com.

[janngo...@gmail.com]

Why does it matter if an object with this map has a changed map for optimized code? For example,

```

var a = {x: 5, y: 5};

var b = {x: 10, y: 10};

b.z = 55; // b now has a new map. a is marked as unstable

```

a's map is now unstable, but the map hasn't changed at all has it? The type of a's map hasn't changed either so why is it marked as unstable? From what I can tell, the only thing that has changed about the map is that a transition has been added to it? Why do we deoptimize code that uses this map?

Thanks!

- Jann

To view this discussion on the web visit https://groups.google.com/d/msgid/v8-dev/b2064f2a-93ea-4354-ac53-150a8eb56f68%40googlegroups.com.

[Seth Brenith]

I'm far from a TurboFan expert, but I'll take a guess. Corrections from actual experts are welcome.

Consider this function:

function sumThreeThings(point) {

  return point.x + someNotInlinedFunction() + point.y;

}

Imagine the "unstable" flag doesn't exist, and you're acting as TurboFan and optimizing that function. The feedback vectors for the loads of x and y both contain only a single map, where the properties x and y are represented as simple data properties (not accessors or anything fancy). You would emit something like the following:

1. Check whether `point` has the expected map. If it's wrong, deoptimize.

2. Fetch `x` from `point` by reading at the index specified by the expected map.

3. Call someNotInlinedFunction.

4. Check (again!) whether `point` has the expected map. If it's wrong, deoptimize.

5. Fetch `y` from `point` by reading at the index specified by the expected map.

Step 4 feels kind of repetitive. Could you maybe make it go away? Not without more information. someNotInlinedFunction could do absolutely anything including changing the map of `point`, so you do need that second deoptimization check.

However, if you knew that the map of `point` was stable, you could omit step 4, safe in the knowledge that some other code elsewhere would take care of deoptimizing this function if someNotInlinedFunction caused a change to the map of `point`. Of course this deoptimization could also be triggered by changes to other variables that aren't `point` and just happen to have the same shape, but that's the risk we take in exchange for the power to remove step 4.

[Leszek Swirski]

Perfect explanation, thanks Seth!

To unsubscribe from this group and stop receiving emails from it, send an email to v8-dev+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/v8-dev/21da254d-b2f4-4021-8933-bbeadf97b73e%40googlegroups.com.

[janngo...@gmail.com]

Thanks Seth for the amazing explanation! So we're just being extra careful when we deprecate a map that is shared by another object

```

function sumThreeThings(point) {

  return point.x + someNotInlinedFunction() + point.y;

}

var pointa = {x: 0, y: 0};

var pointb = {x: 1, y:1};

// now pointa and pointb share maps

for (var i = 0; i < 100000; i++) {

  sumThreeThings(pointa);

}

pointb.z = 55; // This deprecates pointa's map!

sumThreeThings(pointa); // this is no longer optimized

```

[Leszek Swirski]

Deprecation is a slightly different mechanism, but roughly speaking yes it's a similar concept. There's a concept of "dependent code" where some piece of optimised code is dependent on that map stability, and changing the stability deoptimises all code dependent on it.

To unsubscribe from this group and stop receiving emails from it, send an email to v8-dev+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/v8-dev/d5ee1c81-0e5f-494b-94ce-97bb35bcf685%40googlegroups.com.

[Toon Verwaest]

We also use this for field type tracking (that's why we originally introduced it).

E.g.,

point = {x:0, y:0}; // shape Point

point_wrapper: {point}; // shape PointWrapper

function sum(p) {

  return p.point.x + p.point.y;

}

After checking the shape of p, we should normally need to check the shape of p.point before reading x and y from it. We can eliminate this check by tracking the type of values and tracking them in the containing shape. E.g., PointerWrapper.point is known to have the shape Point since every PointerWrapper we've seen had a Point shape for the value stored in the point field. Hence we can omit the shape check for p.point.

However, we can only do this because Point is a stable shape. It's not because we saw p.point come in as a Point that it still has that shape by the time we load it in sum. Someone could have done p.point.z = 10. That's where stability comes in.

hth,

Toon

To view this discussion on the web visit https://groups.google.com/d/msgid/v8-dev/CAGRskv_NyUZBLMfC6bv%3DiL0XAC-R%2BXkd0L-1KeGXFHouHy%3DUZg%40mail.gmail.com.