580846 - TM: simplify array-is-becoming-too-sparse logic

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Andreas Gal :gal]

We currently track the number of holes only so we can judge with precision whether the array is becoming too sparse. We can simplify this and save the constant updating.

Comment 1

[Andreas Gal :gal]

Attachment: patch

As shaver and I independently and simultaneously realized we can do the hole-based part of the heuristics at GC time. This gets rid of count in the array header.

Comment 2

[Brendan Eich [:brendan]]

Don't hide OOM (which is reported) under js::GC. Suppress the report, I guess.

/be

Comment 3

[Andreas Gal :gal]

Attachment: patch

Also remove MinCapLen.

Comment 4

[Andreas Gal :gal]

ignore the maybegc stuff, already removed in my queue

Comment 5

[Jeff Walden [:Waldo]]

I'm glad smarter people than me work on this code and think up ideas like this -- great idea, patch is an excellent simplification.

Comment 6

[Mike Shaver (:shaver emeritus)]

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

>+            for (Value *src = srcbeg, *dst = dstbeg; src > srcend; --src, --dst)
>+                *dst = *src;

memmove?

>+            for (Value *src = srcbeg, *dst = dstbeg; src < srcend; ++src, ++dst)
>+                *dst = *src;

memmove!

> struct JSGCTracer : public JSTracer {
>     uint32 color;
>+    js::Vector<JSObject *, 0, js::SystemAllocPolicy> tooSparseArrays;
> };

I will come up with a better name for this new member in the morning.

Looks like some patch-bleed from your callback work, please check your blind spot when merging.


Up to

>diff --git a/js/src/jstracer.cpp b/js/src/jstracer.cpp

and need to sleep.  Also want to remember why we put minlencap in so that I can feel good about taking it out.

Comment 7

[Robert Sayre]

(In reply to comment #6)
> 
> and need to sleep.  Also want to remember why we put minlencap in so that I can
> feel good about taking it out.

njn knows

Comment 8

[Brendan Eich [:brendan]]

(In reply to comment #7)
> (In reply to comment #6)
> > 
> > and need to sleep.  Also want to remember why we put minlencap in so that I can
> > feel good about taking it out.
> 
> njn knows

But 562571, via sayrer's tweet and then one bug-hop away.

Instead of tooSparseArrays, how about arraysToMakeSparse?

/be

Comment 9

[Andreas Gal :gal]

Attachment: patch

Comment 10

[Andreas Gal :gal]

Attachment: patch

Comment 11

[Andreas Gal :gal]

Attachment: patch

Comment 12

[Nicholas Nethercote [inactive]]

The removal of 'count' is lovely, great work.

The removal of 'minLenCap' has me baffled.  It exists because of the following:

 * NB: the capacity and length of a dense array are entirely unrelated!  The
 * length may be greater than, less than, or equal to the capacity.  See
 * array_length_setter for an explanation of how the first, most surprising
 * case may occur.

So when you're bounds checking an array you need to compare the index against min(length, capacity), hence "minLenCap".

This patch changes it to just check the index against capacity.  I don't understand how the length < index < capacity case works.  Maybe it's because elements [length..capacity-1] will be already set to undefined, so reading them is ok?  If so, I'd really like a comment explaining it in jstracer.cpp, including a pointer to where in the code the undefined-setting occurs.

The removal of minLenCap increases the number of guards in the generated code for GETELEM -- before we had a "index < minLenCap" test, now we now have a "dslots != NULL" test and a "index < capacity" test.  It might be worth resurrecting the idea of having a predefined zero-length dslots array to avoid the dslots!=NULL test (bug 552837, which eventually got replaced by minLenCap).

You can see the extra guard is increasing the on-trace instruction counts, below.  Some tests still end up with fewer instructions executed due to the savings from removing hole-handling.  (And I assume this patch is a prereq for bug 580752, in which case the slight perf loss is well worth it.)

------------------------------------------------------------------
instructions executed (nb: "on-trace" may overestimate slightly)
------------------------------------------------------------------
3d-cube:
  total         114,440,007     114,091,882     1.003x better
  on-trace       20,999,018      21,391,551    *1.019x worse*
3d-morph:
  total          56,664,072      56,530,270     1.002x better
  on-trace       21,881,556      21,881,700     -- 
3d-raytrace:
  total         147,484,218     148,836,376    *1.009x worse*
  on-trace       21,922,292      22,223,742    *1.014x worse*
access-binary-trees:
  total          78,383,686      78,384,851     -- 
  on-trace       17,603,761      17,603,759     -- 
access-fannkuch:
  total         176,446,212     176,876,852    *1.002x worse*
  on-trace      101,475,889     103,725,771    *1.022x worse*
access-nbody:
  total          41,565,450      41,766,916    *1.005x worse*
  on-trace       17,632,035      17,812,851    *1.010x worse*
access-nsieve:
  total          60,689,480      59,840,390     1.014x better
  on-trace       26,450,583      26,730,639    *1.011x worse*
bitops-3bit-bits-in-byte:
  total          15,806,735      15,806,705     -- 
  on-trace        2,990,397       2,990,395     -- 
bitops-bits-in-byte:
  total          44,095,896      44,097,670     -- 
  on-trace       31,086,898      31,086,896     -- 
bitops-bitwise-and:
  total          23,366,264      23,366,419     -- 
  on-trace       10,818,733      10,818,731     -- 
bitops-nsieve-bits:
  total          70,192,981      72,182,370    *1.028x worse*
  on-trace       38,775,818      39,932,364    *1.030x worse*
controlflow-recursive:
  total          43,141,174      43,142,024     -- 
  on-trace       27,491,058      27,491,056     -- 
crypto-md5:
  total          46,963,966      47,214,095    *1.005x worse*
  on-trace        5,473,093       5,531,991    *1.011x worse*
crypto-sha1:
  total          31,084,472      31,452,212    *1.012x worse*
  on-trace        6,958,580       7,057,133    *1.014x worse*
date-format-tofte:
  total         137,777,836     136,454,533     1.010x better
  on-trace       10,785,521      11,227,262    *1.041x worse*
date-format-xparb:
  total          97,743,968      97,747,768     -- 
  on-trace       10,481,471      10,481,541     -- 
math-cordic:
  total          53,254,579      53,617,049    *1.007x worse*
  on-trace       28,238,799      28,588,924    *1.012x worse*
math-partial-sums:
  total          38,459,272      38,464,588     -- 
  on-trace        6,283,431       6,283,555     -- 
math-spectral-norm:
  total          28,596,852      28,877,395    *1.010x worse*
  on-trace       10,394,377      10,639,942    *1.024x worse*
regexp-dna:
  total         113,323,064     113,322,842     -- 
  on-trace       75,040,923      75,040,930     -- 
string-base64:
  total          43,849,041      43,918,507    *1.002x worse*
  on-trace        8,097,207       8,162,817    *1.008x worse*
string-fasta:
  total         123,212,081     122,581,473     1.005x better
  on-trace       24,541,265      24,541,266     -- 
string-tagcloud:
  total         273,793,085     273,704,968     -- 
  on-trace        6,637,722       6,675,184    *1.006x worse*
string-unpack-code:
  total         274,103,094     273,687,596     1.002x better
  on-trace        5,670,452       5,685,560    *1.003x worse*
string-validate-input:
  total          74,364,097      74,527,627    *1.002x worse*
  on-trace        7,506,646       7,566,770    *1.008x worse*
-------
all:
  total       2,208,801,582   2,210,493,378    *1.001x worse*
  on-trace      545,237,525     551,172,330    *1.011x worse*

Comment 13

[Nicholas Nethercote [inactive]]

(In reply to comment #12)
> If so, I'd really like a comment explaining it in jstracer.cpp,
> including a pointer to where in the code the undefined-setting occurs.

BTW this is not as straightforward as it sounds because we have about seven different ways of initializing an array.

Comment 14

[Andreas Gal :gal]

The bug this one blocks makes dslots always being allocated and removes the extra NULL check.

https://bugzilla.mozilla.org/show_bug.cgi?id=580877

Comment 15

[Andreas Gal :gal]

I don't know how to comment on this in the code. Dense arrays are a bit complex and I am not changing that part of the code, so I really don't know where and how to comment this, but resizeDenseArrayElements backfills with holes, so we don't need minlencap.

Comment 16

[Andreas Gal :gal]

Attachment: patch

Comment 17

[Andreas Gal :gal]

Attachment: remove target/src hole type optimization, its dead code now

Comment 18

[Nicholas Nethercote [inactive]]

(In reply to comment #15)
> I don't know how to comment on this in the code. Dense arrays are a bit complex
> and I am not changing that part of the code

Eh?  This whole patch is nothing but changes to dense arrays.

> , so I really don't know where and
> how to comment this, but resizeDenseArrayElements backfills with holes, so we
> don't need minlencap.

Oh come on, writing comments isn't hard, I do it all the time.

In denseArrayElement() just write something like "Arrays have both a length and a capacity, but we only need to check |index < capacity|;  in the case where |length < index < capacity| the entries [length..capacity-1] will have already been marked as undefined by resizeDenseArrayElements() so we can read them and get the correct value."

Comment 19

[Nicholas Nethercote [inactive]]

(In reply to comment #17)
> Created attachment 459584 [details] [diff] [review]
> remove target/src hole type optimization, its dead code now

I think you uploaded the old patch again?

Comment 20

[Nicholas Nethercote [inactive]]

Oh, in the interpreter's GETELEM implementation it still checks index against both length and capacity, the length check can be removed.

Comment 21

[Andreas Gal :gal]

yeah, we should fix the interpreter, too. file a new bug?

Comment 22

[Andreas Gal :gal]

host-5-73:src gal$ diff -u without2 with2
--- without2	2010-07-22 14:43:16.000000000 -0700
+++ with2	2010-07-22 14:43:20.000000000 -0700
@@ -11,24 +11,26 @@
 movq -48(rbp), rdi  <= spill state
 [label1]
 movq r13, 16(rdi)
-movq rbx, 0(rdi)
+movq r15, 0(rdi)
 movq r14, 24(rdi)
-movl r12d, 0(rbx)
+movl ebx, 0(r15)
+xorl r12d, r12d
+cmpl ebx, 0
+jne 0x1007a2ee1
+movq rbx, 1376(r14)
+movq 0(r13), rbx
+movl 8(r13), r12d
+movq r12, 8(rbx)
+lea r15, -5261365(rip)
+cmpq r12, r15
+jne 0x1007a2f04
+movq r15, 32(rbx)
 xorl ebx, ebx
+cmpq r15, 0
+je 0x1007a2f27
+movl r12d, -8(r15)
 cmpl r12d, 0
-jne 0x1007a2f04
-movq rax, 1376(r14)
-movq 0(r13), rax
-movl 8(r13), ebx
-movq rbx, 8(rax)
-lea r12, -5257281(rip)
-cmpq rbx, r12
-jne 0x1007a2f27
-movq r15, 32(rax)
-movl ebx, 64(rax)
-cmpl ebx, 0
 jna 0x1007a2f4a
-xorl ebx, ebx
 movq r12, rbx
 shlq r12, 3
 addq r15, r12
host-5-73:src gal$ wc -l with2
      52 with2
host-5-73:src gal$ wc -l without2
      50 without2

A bit hard to see but this is the change:

+cmpq r15, 0
+je 0x1007a2f27

The rest is reshuffling. As indicated above this will go away with the next patch.

Comment 23

[Andreas Gal :gal]

Attachment: patch

Comment 24

[Andreas Gal :gal]

Brendan made me fix the interpreter too. New patch in a sec.

Comment 25

[Andreas Gal :gal]

Attachment: patch

Comment 26

[Nicholas Nethercote [inactive]]

(In reply to comment #24)
> Brendan made me fix the interpreter too.

Good, I was about to do the same :)

Comment 27

[Nicholas Nethercote [inactive]]

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

r+ once you add the comment I suggested in comment 18!  

Great patch, BTW, 173 net lines of code removed, plus the follow-on perf benefits.

Comment 28

[Andreas Gal :gal]

http://hg.mozilla.org/tracemonkey/rev/219fa035af88

JM should be updated too.

Comment 29

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/219fa035af88