905827 - Suggest optimizing ICs for many shapes/few slots

Status: RESOLVED INCOMPLETE

(Core :: JavaScript Engine, enhancement)

Description

[mmvitousek]

Attachment: Megamorphic instrumentation patch

Ion and Baseline have to fall back to a slow path in due to megamorphism at getprop/getelem sites in many programs. In some of these cases, however, even though many shapes are encountered (necessitating a fallback to the slow path), the actual values that are looked up reside only in a very small number of slots, often as little as two or three even when many thousands of shapes are encountered. 

In a subset of these access sites, not only is the number of slots used low, but also the number of actual shape objects in which property values are found (using LookupPropertyWithFlagsInline) is similarly low.

I've attached some comma-separated-value tables that demonstrate this phenomenon. These files can be opened in Open/LibreOffice, Excel, or some other editor of .csv files (use semicolons as the separator, rather than commas). Note especially the "Slots", "Shapes", and "Property-containing shapes" (the latter being exactly how many distinct shape objects are reached by the property lookup procedure).
* res_pdfjs_ecoop_paper.csv and res_pdfjs_0.csv are the AWFY pdf.js benchmark, except that the rendered pdf is replaced by tinyurl.com/q7x8sjo and iml.univ-mrs.fr/~girard/0.pdf respectively, and. The modified JS files are also attached. 
* res_escapegoat.csv is the JSIL-based Escape Goat benchmark tinyurl.com/pckzlsc, run in Firefox.

Megamorphic getprop sites that display this behavior consume about 15ms of the 1396ms total rendering time of the ECOOP paper. In the case of escapegoat, it is around 1 second out of a ~1 minute runtime.

Steps to reproduce:
1. Apply the attached megainst.patch
2. Run the js shell against one of the attached .js scripts, or against some other script, or run Firefox and visit a website, piping the output to a file.
3. Run results.py using python with the first argument being the file created in step 2, and the second argument being an output table to create.
(e.g., /path/to/objdir/bin/js pdfjs.js > raw_output; python results.py raw_output output_table.csv)
4. Open the output table from step 3 in some editor of CSV files.
5. Note that the timings reported will be inaccurate due to the overhead of instrumentation. Un-defining FULL_OUTPUT in js/src/study_output.h will result in better timing information, which can be combined with the slot/shape data from FULL_OUTPUT runs.

Comment 1

[mmvitousek]

Attachment: res_pdfjs_ecoop_paper.csv

Comment 2

[mmvitousek]

Attachment: res_pdfjs_0.csv

Comment 3

[mmvitousek]

Attachment: res_escapegoat.csv

Comment 4

[mmvitousek]

Attachment: 0.js

Comment 5

[mmvitousek]

Attachment: ecoop-eval.js

Comment 6

[Nicolas B. Pierron [:nbp]]

I guess, that Bug 835306 test case generates a lot of megamorphic cases which have a common ancestor chain and where having a reverse mapping of slots would help a lot.

Also, we need to take into account that some objects might have the same chain of slots with different shapes (see Bug 834614)  This cases can happen when we have functions which are doing batch operations.  For example, in GWT benchmarks, they allocate all the objects, then later add properties on them, and we just cannot inline the object reallocation as part of the IC.