360324 - Research better JS value tagging scheme

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P4)

Description

[Brendan Eich [:brendan]]

Investigate whether we want a tagging scheme more like Tamarin's, or whether it would want a scheme more like SpiderMonkey's, or whether there's a better scheme that's different from both engines.

Patch attached next provides these stats:

op\tag  obj(0)  int(1)  dbl(2)  int(3)  str(4)  int(5) bool(6)  int(7)  sum(8)
==============================================================================
get     577231    9061    1612    1672  893051    1370   17847    2180 1504024
set     272061       0       0       0       0       0       0       0  272061
clr    1200104       0    1321       0 1179979       0       0       0 2381404
obj     233469    5609     140    1173   74056    1003    1060    1241  317751
num         45     510      16      28     678      24      75      19    1395
int         52  365422     175    7222   40839   13508    1044    4496  432758
dbl         49     540     274      15    1002      17    1046     274    3217
str      25694     865      93     212  633863     137    1046     373  662283
bool    314153     689    1077      14  149298      10   14656       5  479902
null    179084    1191      45     174   36388     111    1026     233  218252
void     10633    2886      43    1977   36320    1142     990    1116   55107
prim    162180    2742      51     157   10095     109      20      72  175426

After loading gmail:
op\tag  obj(0)  int(1)  dbl(2)  int(3)  str(4)  int(5) bool(6)  int(7)  sum(8)
==============================================================================
get    1877796   40454    9646   14415 2197105    7791   75142   10310 4232659
set     596682       0       0       0       0       0       0       0  596682
clr    3616488       0    7515       0 2897261       0       0       0 6521264
obj     698091   20927    1637    6497  238656    4164    2917    4285  977174
num         46    2316     201     144    2963     125     407     140    6342
int        339 1190968    2627   40652  146886   51611    2475   24481 1460039
dbl         61    2388    2707      54    5666      48    2499     527   13950
str      74451    5694     739    3495 1409959    2053    2495    1944 1500830
bool   1098700    5811    4530    1075  498168     152   66961     198 1675595
null    521608    9347     305    2792   49389    1052    2553    1474  588520
void     22291   21921     161   10283   48854   10131    2234    8075  123950
prim    474477    9076    1018    3077   38862    2051     485    1793  530839

After google maps:
op\tag  obj(0)  int(1)  dbl(2)  int(3)  str(4)  int(5) bool(6)  int(7)  sum(8)
==============================================================================
get    2687550   62610   42342   21747 2942124   14353  112948   14926 5898600
set     791058       0       0       0       0       0       0       0  791058
clr    5831169       0   27438       0 3823072       0       0       0 9681679
obj    1135243   31671   10412   10269  360956    7736    4042    6987 1567316
num         46    2637     358     235    3571     172     827     218    8064
int        342 1897394   19996   68519  221434   87531    3536   42548 2341300
dbl         64    3046   20171      84    9318      69    3579     601   36932
str     124359    9864    3768    5205 1887447    3608    3575    2981 2040807
bool   1418701    9560    6596    1228  632222     369  101401     242 2170319
null    911968   14716    1189    3866   57747    2298    3618    2107  997509
void     85816   36729     931   16159   57043   15065    2862   11723  226328
prim    794066   14556    5783    5231   49608    3665     568    3020  876497

Shutdown:
op\tag  obj(0)  int(1)  dbl(2)  int(3)  str(4)  int(5) bool(6)  int(7)  sum(8)
==============================================================================
get    3661610   66099   45655   22611 3602529   15057  126217   15208 7554986
set     817604       0       0       0       0       0       0       0  817604
clr    7048646       0   30683       0 4522536       0       0       0 11601865
obj    1213349   33192   10460   10929  384882    8078    4661    7125 1672676
num         46    2642     358     238    3647     174    1061     219    8385
int        342 2276855   20037   74625  235848   91625    4093   44526 2747951
dbl         65    3117   20213      96    9564      82    4157     614   37908
str     135296   10339    3786    5326 1964704    3789    4153    3047 2130440
bool   2302688   10414    9801    1236 1190612     506  112894     247 3628398
null    999420   15685    1189    3909   58899    2464    4153    2152 1087871
void     99375   40976     931   17039   58124   16873    3163   12329  248810
prim    851461   15297    5810    5399   50528    3712     631    3095  935933

Patch next, analysis soon after.

/be

Comment 1

[Brendan Eich [:brendan]]

Attachment: instrument jsval tagging

Comment 2

[Brendan Eich [:brendan]]

Each row (op is the legend name: get set clr obj num int dbl str bool null void prim are the ops) tells the counts for that op for each possible tag value in the macro operand (e.g., JSVAL_IS_INT(v) counts are given by the op=int row, with each column telling (v & JSVAL_TAGMASK)).

From the Firefox data in comment 0, bool tests of obj and bool values are most common, followed by int tests of int data, followed by str tests of str data.  SpiderMonkey in Firefox obviously sees a different workload from what the AVM in Flash 9 sees, so this is not decisive.  However a single-bit test for int seems like a win.

Both SpiderMonkey and Tamarin have fast null tests.  Tamarin has a fast null-or-void test, but the void test counts here don't argue for that being an important case.  More in a bit based on the get count (which includes tests not done via macros that correspond to any op row, so is greater than the sum of all non-int op sums).

/be

Comment 3

[Brendan Eich [:brendan]]

(In reply to comment #2)
> From the Firefox data in comment 0, bool tests of obj and bool values are most
> common,

Er, bool tests of obj and |str| values....

/be

Comment 4

[Brendan Eich [:brendan]]

Note that Tamarin's tagged pointer-or-value word type is called Atom.  See http://lxr.mozilla.org/mozilla/source/js/tamarin/core/avmplusTypes.h -- slightly confusing given the usual meaning of "atom", an interned string or value (see http://www.google.com/search?q=atom+interned+value), which SpiderMonkey employs.

/be

Comment 5

[Brendan Eich [:brendan]]

Using 0 for the int tag allows subtraction as well as addition to be done without a tag-restoring step (overflow checks are required as usual).  I'll try to measure how common int-tagged jsval subtraction is in Firefox.

/be

Comment 6

[Brendan Eich [:brendan]]

See bug 161110 comment 37.

/be

Comment 7

[Igor Bukanov]

Currently there are tenths checks for JSVAL_VOID hidden in JSVAL_IS_INT macro in js_Interpret since JSVAL_VOID & JSVAL_INT == 1. It would be nice at least to make JSVAL_VOID a pseudo boolean. That will also allow to optimize |, & and ^ not to check for jsval int overflow when storing the result of 2 int-tagged values.

Comment 8

[Brendan Eich [:brendan]]

JSVAL_VOID as pseudo-boolean was bug 432881.

/be

Comment 9

[Brendan Eich [:brendan]]

Pseudo-booleans along with true and false (non-pseudo-booleans, "true" booleans? Ugh) are likely to remain special, with their tag renamed to JSVAL_SPECIAL.

Bug 504587 comment 21 shows pain in having JSVAL_IS_OBJECT(JSVAL_NULL). We could make JSVAL_NULL be special too, perhaps.

Another likely win: invert JSVAL_INT so low jsval bit being zero means int jsval (including private 0 mod 2 or better aligned data pointer, no tagging required). This lets JSOP_ADD and JSOP_SUB avoid tag-clearing/restoring overhead in adding unshifted (tagged) operands.

/be

Comment 10

[Igor Bukanov]

Since objects are aligned on at least 4-words boundary, a tagging schema can differentiate, for example, functions and objects.

Comment 11

[Brendan Eich [:brendan]]

State of the art seems to be nan-boxing on 64-bit targets, something like jsval on 32-bit with tuning and tweaking as needed. Not sure this bug should live on as an open-ended research cause-of-action. A meta-bug tracking nan-boxing on x64, focused tweaks for 32-bit, etc. seems better. Putting back in the pool; feel free to grab, cc: buddies.

/be

Comment 12

[Nicholas Nethercote [inactive]]

I assume fatvals has rendered this bug moot?

Comment 13

[Brendan Eich [:brendan]]

Indeed, fixed by bug 549143 (I made its alias be "fatvals", who would search for "newjsvals"? :-P).

/be