580877 - TM: dense arrays always have dslots

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Andreas Gal :gal]

Objects that don't need dslots are frequent. In case of dense arrays however only [] doesn't need dslots. Anything else does. We access arrays a lot more often than making them, so ensure we always have dslots. This makes it possible to always read dslots[-1].

Comment 1

[Mike Shaver (:shaver emeritus)]

Can probably have a const jsval newbornDslots[] = { jsval(0), JSVAL_HOLE } and point dslots at &newbornDslots[1] to start.  That'll save an allocation, and fall into the slow growth path the first time it's touched.

Comment 2

[Brian Hackett [Laid off!]]

Some numbers:

SS allocates a total of 53207 arrays, 24k through 'new Array' and the rest as part of a native.  Of these, 53202 will have at least one element added and need their own dslots.  This is probably pretty extreme; it'd be great to know how often website JS creates empty arrays that stay empty.  If empty arrays are rare though, it might make sense to always preallocate space.  This would both remove the need for the dslots check and also remove about 23k slow paths in JM for doing the initial resize.

Second issue: the allocations for small arrays are slow; on SS we spend 10ms doing the initial allocations, about 200ns each.  There are only 587 array resizes that go beyond the initial allocation.  It might make sense to put initial array dslots on the GC heap (or a similar heap we control), to take advantage of faster allocation, better locality, and future improvements to the GC (bump allocation, optimization for page faults).

Comment 3

[Andreas Gal :gal]

Attachment: patch

Comment 4

[Nicholas Nethercote [inactive]]

Instruction counts with this patch and the one from bug 580846 are below.  The comparison is against TM tip with neither patch applied.  So this more than makes up for the slight instruction count increase seen in bug 580846, nice work.

------------------------------------------------------------------
instructions executed (nb: "on-trace" may overestimate slightly)
------------------------------------------------------------------
3d-cube:
  total         114,440,038     111,811,196     1.024x better
  on-trace       20,999,018      20,950,687     1.002x better
3d-morph:
  total          56,664,028      55,885,971     1.014x better
  on-trace       21,881,556      21,881,436     -- 
3d-raytrace:
  total         147,484,282     146,718,527     1.005x better
  on-trace       21,922,292      21,841,380     1.004x better
access-binary-trees:
  total          78,383,640      78,383,517     -- 
  on-trace       17,603,761      17,603,771     -- 
access-fannkuch:
  total         176,446,223     172,996,836     1.020x better
  on-trace      101,475,889     101,415,240     1.001x better
access-nbody:
  total          41,565,430      41,546,285     -- 
  on-trace       17,632,035      17,631,857     -- 
access-nsieve:
  total          60,689,467      58,174,452     1.043x better
  on-trace       26,450,583      26,450,454     -- 
bitops-3bit-bits-in-byte:
  total          15,806,746      15,806,968     -- 
  on-trace        2,990,397       2,990,399     -- 
bitops-bits-in-byte:
  total          44,095,914      44,096,212     -- 
  on-trace       31,086,898      31,086,902     -- 
bitops-bitwise-and:
  total          23,366,240      23,366,530     -- 
  on-trace       10,818,733      10,818,733     -- 
bitops-nsieve-bits:
  total          70,192,937      69,728,694     1.007x better
  on-trace       38,775,818      38,775,786     -- 
controlflow-recursive:
  total          43,141,198      43,141,450     -- 
  on-trace       27,491,058      27,491,062     -- 
crypto-md5:
  total          46,963,944      47,086,605    *1.003x worse*
  on-trace        5,473,093       5,491,282    *1.003x worse*
crypto-sha1:
  total          31,084,448      31,243,662    *1.005x worse*
  on-trace        6,958,580       6,980,335    *1.003x worse*
date-format-tofte:
  total         137,777,880     135,608,484     1.016x better
  on-trace       10,785,521      10,767,974     1.002x better
date-format-xparb:
  total          97,743,981      97,726,050     -- 
  on-trace       10,481,471      10,465,641     1.002x better
math-cordic:
  total          53,254,599      53,016,778     1.004x better
  on-trace       28,238,799      27,988,812     1.009x better
math-partial-sums:
  total          38,459,239      38,460,717     -- 
  on-trace        6,283,431       6,283,431     -- 
math-spectral-norm:
  total          28,596,885      28,588,935     -- 
  on-trace       10,394,377      10,394,362     -- 
regexp-dna:
  total         113,323,088     113,319,563     -- 
  on-trace       75,040,923      75,041,171     -- 
string-base64:
  total          43,849,050      43,845,963     -- 
  on-trace        8,097,207       8,097,451     -- 
string-fasta:
  total         123,212,158     122,865,097     1.003x better
  on-trace       24,541,265      24,541,235     -- 
string-tagcloud:
  total         273,793,076     273,150,024     1.002x better
  on-trace        6,637,722       6,634,752     -- 
string-unpack-code:
  total         274,103,068     274,092,401     -- 
  on-trace        5,670,452       5,664,992     1.001x better
string-validate-input:
  total          74,363,328      74,376,378     -- 
  on-trace        7,506,646       7,518,638    *1.002x worse*
-------
all:
  total       2,208,800,887   2,195,037,295     1.006x better
  on-trace      545,237,525     544,807,783     1.001x better

Comment 5

[Andreas Gal :gal]

Attachment: patch

Comment 6

[Nicholas Nethercote [inactive]]

Comment on attachment 459694 [details] [diff] [review]
patch


>+bool
>+JSObject::shrinkDenseArrayElements(JSContext *cx, uint32 newcap)
>+{
>+    JS_ASSERT(isDenseArray());
>+    JS_ASSERT(newcap < getDenseArrayCapacity());
>+    JS_ASSERT(dslots);
>+
>+    uint32 fill = newcap;
>+
>+    if (newcap < ARRAY_CAPACITY_MIN)
>+        newcap = ARRAY_CAPACITY_MIN;
>+
>+    /* dslots can be briefly NULL during array creation */
>+    Value *newslots = (Value *) cx->realloc(dslots - 1, (size_t(newcap) + 1) * sizeof(Value));
>+    if (!newslots)
>+        return false;

Nit: That comment doesn't apply in this case.

I don't love the whole dslots-is-briefly-NULL thing, but I can't see a
better way to do it.  I guess the worse that could happen is that it'll be
NULL at a point we don't expect, which will lead to a very obvious crash.


> static void
> array_trace(JSTracer *trc, JSObject *obj)
> {
>     JS_ASSERT(obj->isDenseArray());
>     obj->traceProtoAndParent(trc);
> 
>+    if (!obj->dslots)
>+        return;

dslots can be NULL here?  I wouldn't have thought array_trace could occur
during the brief period when dslots==NULL is possible?

js_NewArrayObjectWithCapacity() is a JS_FRIEND_API, so I guess we should be
careful about removing it?  

Nice patch.  I particularly like that you are removing some of the dozen
or so different ways we have of initializing an array.

Comment 7

[Andreas Gal :gal]

http://hg.mozilla.org/tracemonkey/rev/550af63e01c9

Comment 8

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/550af63e01c9