1589142 - Investigate combining JSObject shape and group pointers into "shuples" (shape tuples)

Status: RESOLVED INVALID

(Core :: JavaScript Engine: JIT, enhancement, P3)

Description

[Chris Fallin [:cfallin]]

We've been discussing an idea that involves merging bits of metadata for JSObjects, starting with shape and group, into a unified system that tracks tuples (we've called them metadata tuples, shape tuples, shuples, or type cursors). Each JSObject would have a single reference to a top-level tuple, and these tuples would then contain the metadata elements, either directly, or via a tree of tuples.

The initial benefit of this scheme is to save one machine word per object, hopefully at negligible performance cost. However, it also opens the door to other more interesting changes later, for example (i) unifying the way that guards are generated, allowing for simpler code and more likelihood of correctness especially as we do more work on the JITs, and (ii) providing a single place where tradeoffs between mutation-time and guard-time cost can happen as a policy decision (guard on top-level tuple vs. subtrees, immutable tuples for cheap guards vs. mutable tuples per object for less churn, etc.) and potentially others. In any case, the initial memory win could motivate us to start down this path, regardless of other benefits.

Comment 1

[Chris Fallin [:cfallin]]

Attachment: count-shooples.patch

Patch to dump shape and group pointers from every object on every GC, in order to collect data for experimentation.

Comment 2

[Chris Fallin [:cfallin]]

Attachment: shoople-analyze.rs

Little Rust utility to analyze the output of the shape/group pointer dump (from Firefox patched with count-shooples.patch).

Comment 3

[Chris Fallin [:cfallin]]

Attachment: shooples-reddit-nytimes-amazon.log.bz2

Raw output of a Firefox browsing session (to Reddit, NYTimes, and Amazon) dumping shape and group pointers.

Comment 4

[Chris Fallin [:cfallin]]

I did a quick analysis looking at (group, shape) pointer-tuples on objects (see attached patch and analysis utility). Here are a few quick summaries of the heap at major GCs:

pairs: size 250930, uniques 53755
unique groups: 39808
unique shapes: 14184
---
pairs: size 320466, uniques 71341
unique groups: 46520
unique shapes: 12235

The utility dumps histograms of the number of shapes with N groups, and number of groups with N shapes, as well. These are very heavily focused around 1, but there's definitely a long tail (moreso for shapes aggregated by group -- makes sense, as shape changes more often), so we might want to consider adaptive heuristics too (e.g., switching to a mutable tuple per object after too much mutation of one tuple field rather than continuing to intern new immutable tuples).

Comment 5

[Chris Fallin [:cfallin]]

Attachment: shooples-analysis-20191016.tar.bz2

Updated analysis attached. After lots of discussion with Kannan and Iain today, we've focused on one particular issue: the ratio of objects to groups is actually not that high (5-7 objs/group commonly) so on average, the bar is pretty high for a central shoople infrastructure to save memory. We're focusing specifically on why this is the case, and it seems that a majority of groups are actually Function groups, and most of these are not singletons (so e.g. callbacks/inner functions). We're discussing whether we should tackle this problem first so we don't have to be overly clever with hybrid data structures, etc. to save memory here.

Analysis summary for some browsing of Reddit, NYTimes, YouTube, Amazon, from a typical major GC:

total objects: 351884 
total groups: 62091, singletons: 3055, lazy: 434, singletons and lazy: 434, functions: 43735, function singletons: 1072
objects with function groups: 194580 
total shapes: 19170
unique (group, shape) tuples: 82237
unique (group, shape) tuples, excluding singletons: 78055
mean objects per (group, shape) tuple: 4.278901224509649

Comment 6

[Chris Fallin [:cfallin]]

Attachment: shooples-analysis-20191017.tar.bz2

Latest empircal realizations and discussion conclusions with Kannan and Iain:

• We initially focused on why there are so many function groups, many non-singleton: these are real functions, many of them callbacks. Arrow functions seem to be used at least in the Reddit source. Since Ion needs the groups to reason about inlining, we aren't seriously considering ways to get rid of the groups; we have to design shooples around the existence of them without blowing up the number of shooples.

• However... of all the function objects with a function-class ObjectGroup, only a few shapes are in use, and by far the most common is the empty shape (one per realm). Here's a sample dump at major-GC time of the shapes held by all function objects:

total objects: 308753
total groups: 17520, singletons: 880, lazy: 125, singletons and lazy: 125, functions: 12063, function singletons: 322, selfhosted/native functions: 323
objects with function groups: 61720
Shape for function objects, with object counts:
 - shape 20565671092680 (empty true attrs 0 mut_flags 21 immut_flags 16777215 realm 140474478991360): count 46590
 - shape 24685349096672 (empty true attrs 0 mut_flags 21 immut_flags 16777215 realm 140474504484864): count 3292
 - shape 14919207328592 (empty true attrs 0 mut_flags 21 immut_flags 16777215 realm 140474370038784): count 2156
 - shape 12899596445584 (empty true attrs 0 mut_flags 21 immut_flags 16777215 realm 140474432220160): count 1350
 - shape 36012936849336 (empty true attrs 0 mut_flags 2 immut_flags 16777215 realm 140474395240448): count 835
 - shape 24685349523912 (empty true attrs 0 mut_flags 2 immut_flags 16777215 realm 140474485511168): count 832
 - shape 22009674626640 (empty false attrs 6 mut_flags 5 immut_flags 3 realm 140474478991360): count 733
 - shape 24685348836144 (empty true attrs 0 mut_flags 21 immut_flags 16777215 realm 140474504476672): count 694
 - shape 51837468557688 (empty true attrs 0 mut_flags 1 immut_flags 16777215 realm 140474370038784): count 692
 - shape 36012936458616 (empty true attrs 0 mut_flags 2 immut_flags 16777215 realm 140474478991360): count 467
 - shape 51837468425640 (empty false attrs 4 mut_flags 29 immut_flags 0 realm 140474478991360): count 422
 - shape 36012936278392 (empty true attrs 0 mut_flags 1 immut_flags 16777215 realm 140474478991360): count 394
 - shape 41319878734200 (empty true attrs 0 mut_flags 21 immut_flags 16777215 realm 140474478991360): count 285
 - shape 22009674688440 (empty false attrs 1 mut_flags 29 immut_flags 0 realm 140474478991360): count 229
 - shape 8963894673784 (empty true attrs 0 mut_flags 21 immut_flags 16777215 realm 140474478991360): count 222
 - shape 36012936401272 (empty true attrs 0 mut_flags 21 immut_flags 16777215 realm 140474478991360): count 181

• So, enter Kannan's idea: "compressed shooples" that are implicitly equivalent to (group, shape) but are actually just the group pointer with a single tag bit that indicates "default empty shape with default class/proto for a Function". Then, most unique (group, shape) tuples due to function objects go away, and we have a higher ratio of objects per (group, shape) hence higher opportunity to save memory.

Currently working on the design for the shoople table -- we're thinking a simple arena of GC things for now, but there are questions around how we integrate the dedup'ing hashtable into that.

Comment 7

[Kannan Vijayan [:djvj]]

So to motivate the "compress the shuple" approach - one of my eventual goals (not necessarily with the near-term implementation) is to try to remove ObjectGroups entirely. That was the original design intent with the Shypes proposal, and I don't wan't the shuples implementation approach to block that eventual goal.

As per Chris's analysis, it's turning out that the objects to ObjectGroups ratio is very low (5 to 1 or so), and it's mostly due to ObjectGroups for functions.

As far as I can tell, there are two reasons ObjectGroups are needed for functions - one is to identify the canonical function for the group. These show up because of scoped functions that are allocating multiple function instances per canonical function (one per activation).

If there are no unusual changes to the function (i.e. added properties, etc.), then the default ObjectGroup for a function should very only by the underlying canonical function. The property type-sets for the default properties can be derived automatically otherwise. This means that only functions which have unusual things done to them will need ObjectGroups. The standard JS usage of inner functions (callbacks, handlers, higher-order code) should all be able to infer everything about the object from the fact that it's 1) a function, and 2) the canonical function for it.

In the short term, it probably doesn't make sense to implement all of this. But it's the long-term motivation behind the idea of doing a shuples implementation where we "compress" the shuple representation and inline it directly into the (now single-word) type pointer for an object.

For now, that can be just a pointer to the existing group infrastructure with a boolean flag indicating that it's a standard function shaped thing. In the future, it should be possible to eliminate the ObjectGroup allocation for Function entirely, and just have a tagged pointer to the canonical function stand in as an object-group for the function.

If Chris's measurements are right, that'll save us at least the size of an ObjectGroup (minimally 48 bytes) across ~12k objects, which is easily over 500k memory per compartment, which is a nice win to have in our pocket (and something of value to present to towards larger org goals - e.g. Fission. It would eliminate shuples memory overhead for a large class of objects, and allow for a lot more freedom (in terms of memory overhead) to play with shuples representation.

The tagged pointers-to-canonical functions should work for singleton functions as well - as we can check to see if the canonical function is the same and assume a singleton type if so.

Comment 8

[Kannan Vijayan [:djvj]]

Chris pointed out this omission. The second reason we need object-groups for functions - which I didn't comment on after mentioning two reasons - was to track types of functions in TypeSets. Since ObjectGroup is the only type we know of for a JSObject in a typeset, we need to produce one.

The short term implementation is independent of this concern - because we can keep using ObjectGroups for functions (just not allocate explicit shuples on the heap for them). But as with the other use of function ObjectGroups, this one too can be reduced to using tagged canonical functions as the type pointer.

In most cases, unless an ObjectGroup needs to be explicitly materialized to attach constraints and invalidation hooks, we should be able to eliminate the allocation of the group entirely and just infer the default properties.

All of this works out pretty well because the shuple is an immutable value type, and inferring it on demand from some token is just fine, as long any underlying mutable state (in this case the ObjectGroup part of the shuple) has not yet been materialized and still has its default initial value.

Comment 9

[Luke Wagner [:luke]]

(Not sure if info was being requested, but fwiw, excited to see this investigation and measurement; it generally sounds promising! I can't say I understand ObjectGroup's details enough to comment more on "compressed shuple". I do love the word "shuple" though.)

Comment 10

[Kannan Vijayan [:djvj]]

It was mostly a ping to see if you had any objections to that implementation path. I'll needinfo jandem and bhackett on this comment to confirm these assumptions and make sure I'm not missing anything crucial. jan and brian: see comment 7.

Comment 11

[Brian Hackett [Laid off!]]

(In reply to Kannan Vijayan [:djvj] from comment #10)

It was mostly a ping to see if you had any objections to that implementation path. I'll needinfo jandem and bhackett on this comment to confirm these assumptions and make sure I'm not missing anything crucial. jan and brian: see comment 7.

Hmm, I'm a little confused, comment 7 is mostly talking about a topic (eliminating object groups for inner functions) that seems different from the topic of the bug itself (eliminating a machine word from JSObject). These seem like they can be considered separately could the former be split into its own bug?

In general, I would be careful about maintaining simple paths (few branches/dereferences) for accessing the critical parts of an object's data, like its prototype. Back in the day the objshrink project added one or two extra dereferences to access a lot of an object's data by storing it in the shape or group instead of the JSObject itself, but I tried to avoid adding branches that wouldn't be easily predicted by the CPU. ObjectGroups are already compressed via the lazy ObjectGroup machinery for singleton JSObjects, but in that case the object still points to an ObjectGroup instead of a tagged pointer to something else, so that getting the critical data stored in the group (clasp/prototype/realm) is fast.

Eliminating object groups for inner functions would be a great improvement. I have some more thoughts below but as a caveat, I haven't looked at this stuff in several years and I'm going from (fuzzy) memory here.

(In reply to Kannan Vijayan [:djvj] from comment #7)

As far as I can tell, there are two reasons ObjectGroups are needed for functions - one is to identify the canonical function for the group. These show up because of scoped functions that are allocating multiple function instances per canonical function (one per activation).

If there are no unusual changes to the function (i.e. added properties, etc.), then the default ObjectGroup for a function should very only by the underlying canonical function. The property type-sets for the default properties can be derived automatically otherwise. This means that only functions which have unusual things done to them will need ObjectGroups. The standard JS usage of inner functions (callbacks, handlers, higher-order code) should all be able to infer everything about the object from the fact that it's 1) a function, and 2) the canonical function for it.

This was the motivation for using lazy object groups for singleton objects. In the singleton case we don't need to do anything when properties of the object change, as if the ObjectGroup is instantiated later its property types can be established from the contents of that single object. Having a lazy sort of group for non-singleton inner functions is tricky because you can't enumerate those objects and fill in the property types if the group needs to be instantiated. I see a couple options:

• As you suggest, instantiate the ObjectGroup for the inner functions as soon as one of them is modified. Is there an easy way to do this with hooks on the JSFunction class?

• Deoptimize type information for properties of inner functions --- the property types and other TI information for these functions are unknown. It seems like it would be rare for data properties to be added to these inner functions and used in a way that type information would be helpful for performance.

The latter one seems nice because it's simpler. Either way, the representation of these inner functions in type sets would need to change (using a tagged pointer to the canonical function like we do for singleton objects) which would making testing type set membership for a jsvalue a little trickier, but this doesn't seem like it would add much complexity or overhead.

Comment 12

[Chris Fallin [:cfallin]]

Thanks for the additional thoughts, :bhackett -- I've created another bug to track the implicit-ObjectGroups-for-functions change separately. We'll plan to work on that first, then come back to this once the object-vs-group ratio is more favorable.

Comment 13

[Jan de Mooij [:jandem]]

(Commented on bug 1590198.)

Comment 14

[Chris Fallin [:cfallin]]

Attachment: Bug 1589142: Work-in-progress Shoople implementation.

• Hits a segfault in JIT code; most likely I've missed somewhere that
  JIT code assumes object layout / tries to read or write a shape/group
  pointer directly.

• A number of asserts commented-out in GC. Shooples aren't being cleaned
  up properly at runtime teardown.

Comment 15

[BugBot [:suhaib / :marco/ :calixte]]

The bug assignee is inactive on Bugzilla, so the assignee is being reset.

Comment 16

[Jan de Mooij [:jandem]]

Groups are gone, objects now have just the shape pointer. I think we can close this, even though we might want to revisit some of these ideas at some point.