687838 - Prototype property lookup incorrectly assumes that hashtable fetch suffices.

Status: RESOLVED FIXED

(Tamarin Graveyard :: Library, defect, P2)

Description

[Felix S. Klock II [:pnkfelix, :fklock]]

% cat /tmp/foo.as 
  var a = [];
  print(a[10]);
  Array.prototype[10] = "hello";
  print(a[10]);

64-bit DebugDebugger shell.  First at rev 5711, second at rev 5713.

% ./shell/avmshell.r5711 /tmp/foo.abc 
undefined
hello

% ./shell/avmshell.r5713 /tmp/foo.abc 
undefined
undefined

% hg log -r 5711:5713
changeset:   5711:93a6f1d1128f
user:        Edwin Smith <[e-mail]>
date:        Tue Jan 04 14:56:48 2011 -0500
summary:     Bug 622903 - Valgrind/memcheck false positive on thisPage in TraceConservatePointer() (r=fklockii+)

changeset:   5712:9c0aeb405ad3
user:        Steven Johnson <[e-mail]>
date:        Tue Jan 04 12:55:41 2011 -0800
summary:     Bug 610063 - Port 'dense array' work from TT (r=lhansen)

changeset:   5713:96816b60cf0f
user:        Steven Johnson <[e-mail]>
date:        Tue Jan 04 13:19:17 2011 -0800
summary:     Fix unused-arg warnings in previous checkin (r=stejohns)


So this is another injection from dense array work.

Comment 1

[Felix S. Klock II [:pnkfelix, :fklock]]

Sigh; our Array implementation inconsistencies from the past continue to surprise.

Code:
  var a = [];
  Array.prototype[1] = "hello";
  Array.prototype[10] = "world";
  print("  a[   1]: " + a[   1]);
  print("  a[  10]: " + a[  10]);

  print("                  (now setting near element)")
  Array.prototype[0] = "introducing";
  print("  a[   0]: " + a[   0]);
  print("  a[   1]: " + a[   1]);
  print("  a[  10]: " + a[  10]);

  print("                  (now setting far element)")
  Array.prototype[1000] = "from far away";
  print("  a[   0]: " + a[   0]);
  print("  a[   1]: " + a[   1]);
  print("  a[  10]: " + a[  10]);
  print("  a[1000]: " + a[1000]);

rev5711:
  a[   1]: hello
  a[  10]: world
                  (now setting near element)
  a[   0]: undefined
  a[   1]: undefined
  a[  10]: world
                  (now setting far element)
  a[   0]: undefined
  a[   1]: undefined
  a[  10]: world
  a[1000]: from far away


rev5713:
  a[   1]: undefined
  a[  10]: undefined
                  (now setting near element)
  a[   0]: undefined
  a[   1]: undefined
  a[  10]: undefined
                  (now setting far element)
  a[   0]: introducing
  a[   1]: hello
  a[  10]: world
  a[1000]: from far away


This seems to be a case where the shift between dense and sparse is being exposed to user code.  The ScriptObject::getUintProperty code always uses the object hashtables for lookup while ascending the prototype-chain.  The Array in turn uses the object hashtable as the basis for its sparse storage.  And finally, in both cases, an instance of an Array is used as the prototype for instances of Array.  With the old code circa rev 5711, the array storage was split between a dense prefix and sparse suffix, and so the prototype lookup skips looking in the dense prefix (that's reflected in the change in how a[1] is printed above after setting Array.prototype[0]).  With the new code circa rev 5713, the array storage is always 100% dense or 100% sparse, but we try harder to keep it dense.  That's why one has to write a property at an index that is far far away before seeing any of the lookups succeed, but once it does become sparse, all of the properties become visible.

What's the right solution here?  Perhaps not to assume that the sparse hashtable lookup is the right one to use while traversing the prototype chain?

(That leads me to wonder: couldn't one observe this more generally for any object that has had its constructor's prototype set to an array instance?  Will investigate.)

Comment 2

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to Felix S Klock II from comment #1)
> (That leads me to wonder: couldn't one observe this more generally for any
> object that has had its constructor's prototype set to an array instance? 
> Will investigate.)

The answer is: Yes, this is a general problem with lookups that traverse the prototype chain.

Assuming the right thing is to fix the prototype-lookup loop to handle arrays, this behavior may need to be versioned-checked.

Comment 3

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: test B v1: test lookup when prototype is an Array

(this is a simple port of the code from comment 1 with a non-array constructor that has an array as its prototype.)

Comment 4

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to Felix S Klock II from comment #2)
> Assuming the right thing is to fix the prototype-lookup loop to handle
> arrays, this behavior may need to be versioned-checked.

(but then again, a *good* version check may be impossible.  Its not like we can bring back the prior oh-so-strange behavior where the presence/absence depended on the dense/sparse policy.)

Comment 5

[Felix S. Klock II [:pnkfelix, :fklock]]

Also, this comment above ScriptObject::getAtomProperty probably needs to be refined in light of this ticket:

     * traverse the delegate chain looking for a value.
     * [ed] it's okay to look only at the HT's in the delegate chain because
     * delegate values may only be instances of Object.  They cannot be objects
     * with slots.  We don't need to look at traits at each step.

Comment 6

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: patch P v1: no version checks. no performance tuning.

Sketch of one way to skin this cat.

No version checks, because I'm not convinced they'd be meaningful here.

No performance tuning, because I haven't run any comparative benchmarks yet.

But it does bring the behavior of my reference test back in line with my expectations:

  a[   1]: hello
  a[  10]: world
                  (now setting near element)
  a[   0]: introducing
  a[   1]: hello
  a[  10]: world
                  (now setting far element)
  a[   0]: introducing
  a[   1]: hello
  a[  10]: world
  a[1000]: from far away

Comment 7

[Lars T Hansen]

Comment on attachment 561320 [details] [diff] [review]
patch P v1: no version checks.  no performance tuning.

I've not checked this carefully in all its details but the approach seems reasonable.

Comment 8

[Lars T Hansen]

BTW:

- This strikes me as a shoo-in for Anza and it really should have been in Serrano,
  since technically it regresses relative to Argo, no?
- I agree versioning of a fix is probably meaningless and not desirable.

Comment 9

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: csv data for patch P v1

(will post .txt version shortly.)

Comment 10

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: text formatted performance data for patch P v1

There are some troubling regressions.

It is possible that the regressions will go away when Bug 688486 is wrapped up.

I'd like to confirm that hypothesis before landing this.  (And even then, if this is targeted for Anza but Bug 688486 is targeted for a later release, then it might be worthwhile to figure out where the time is going in this patch alone...)

Comment 11

[Felix S. Klock II [:pnkfelix, :fklock]]

Oh, the data from the two posted attachments were taken from a 32-bit release shell atop Mac OS X on a 2x3.2 Ghz Quad-Core Intel Xeon MacPro.

Comment 12

[Felix S. Klock II [:pnkfelix, :fklock]]

this is targeted to Anza.  I suggest deferral; the regressions trouble me enough that I would not want to land patch P v1 as is, but I do not think I have time to revise it.

Comment 13

[Dan Smith]

Agree with delaying patch until regressions are resolved.  Moving to Brannan.

Comment 14

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: test B v2: more thorough testing of all kinds of corners

On TR rev 5711 (i.e. before dense array work landed):

Array .proto start0 array          ref  1 a = undefined FAILED! expected: one A
Class .proto start0 array trans    ref  1 b = undefined FAILED! expected: one A
Function .proto start0 array trans ref  1 d_post = undefined FAILED! expected: one A
Function .proto start0 array immed ref  1 e_post = undefined FAILED! expected: one Epost
Array .proto sparse array          ref  1 a = undefined FAILED! expected: one A
Class .proto sparse array trans    ref  1 b = undefined FAILED! expected: one A
Function .proto sparse array trans ref  1 d_post = undefined FAILED! expected: one A
Function .proto sparse array immed ref  1 e_post = undefined FAILED! expected: one Epost
Function .proto sparse array trans ref 1k d_pre = undefined FAILED! expected: thousand D
Function .proto sparse array immed ref 1k e_pre = undefined FAILED! expected: thousand Epre
Function .proto sparse array immed ref 1k e_post = thousand E FAILED! expected: thousand Epost
Array .proto+self sparse           ref  1 a_s = undefined FAILED! expected: one A
Class .proto+self sparse trans     ref  1 b_s = undefined FAILED! expected: one A


On TR rev 6749 (i.e. current repo tip):

Array .proto start1 array          ref  1 a = undefined FAILED! expected: one A
Class .proto start1 array trans    ref  1 b = undefined FAILED! expected: one A
Function .proto start1 array trans ref  1 d = undefined FAILED! expected: one A
Function .proto start1 array immed ref  1 e = undefined FAILED! expected: one Epost
Array .proto start1 array          ref 10 a = undefined FAILED! expected: ten A
Class .proto start1 array trans    ref 10 b = undefined FAILED! expected: ten A
Function .proto start1 array trans ref 10 d = undefined FAILED! expected: ten A
Function .proto start1 array immed ref 10 e = undefined FAILED! expected: ten Epost
Array .proto start0 array          ref  1 a = undefined FAILED! expected: one A
Class .proto start0 array trans    ref  1 b = undefined FAILED! expected: one A
Function .proto start0 array trans ref  1 d_post = undefined FAILED! expected: one A
Function .proto start0 array immed ref  1 e_post = undefined FAILED! expected: one Epost
Array .proto start0 array          ref 10 a = undefined FAILED! expected: ten A
Class .proto start0 array trans    ref 10 b = undefined FAILED! expected: ten A
Function .proto start0 array trans ref 10 d_post = undefined FAILED! expected: ten A
Function .proto start0 array immed ref 10 e_post = undefined FAILED! expected: ten Epost
Function .proto sparse array trans ref 1k d_pre = undefined FAILED! expected: thousand D
Function .proto sparse array immed ref 1k e_pre = undefined FAILED! expected: thousand Epre
Function .proto sparse array immed ref 1k e_post = thousand E FAILED! expected: thousand Epost




(The thing to note about the above is how crazy different the sets of errors look.  At least to my eye.  I'll try with my patch for the bug later tonight to see how many it helps with, I need to take a break at the moment.)

Comment 15

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: patch P v2: no version checks. no performance tuning.

(rebased patch; no substantial difference from v1)

Comment 16

[Felix S. Klock II [:pnkfelix, :fklock]]

On TR rev 6749 with patch P v2 applied, test B yields:

Function .proto sparse array trans ref 1k d_pre = undefined FAILED! expected: thousand D
Function .proto sparse array immed ref 1k e_pre = undefined FAILED! expected: thousand Epre
Function .proto sparse array immed ref 1k e_post = thousand E FAILED! expected: thousand Epost

So that's significantly better than where we were in comment 14.

And in fact, reviewing the code for attachment B v2 now, the test for Function .proto sparse array trans ref 1k d_pre is obviously broken, and it seems likely that the same is true for Function .proto sparse array immed ref 1k e_{pre,post}.

So I suspect that after fixing attachment test B, patch P v2 will fix all of the correctly encoded test cases in attachment B v2.

Comment 17

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: test B v3: more thorough testing of all kinds of corners

fixed test

Comment 18

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: test B v4: thorough testing of all kinds of corners

(fixed test, revised presentation/encoding slightly to make grouping clearer via block alignment in source text.)

Executive summary: I'm happy with this set of tests.  They show that Patch P v2 is an improvement on our past.

Still don't want to land until I do one round of performance tests, but at this point the simple array jit work has landed and so I am hoping that performance is not an issue (because real world code should almost never get into this control path in the VM).

More details: With this version, the breakdown is:

TR rev 5711 (i.e. before dense array work landed):

   Arr .proto start0 array       ref  1 a = undefined FAILED! expected: one A
   Cls .proto start0 array trans ref  1 b = undefined FAILED! expected: one A
   Fcn .proto start0 array trans ref  1 d = undefined FAILED! expected: one A
   Fcn .proto start0 array immed ref  1 e = undefined FAILED! expected: one Epost
   Arr .proto sparse array       ref  1 a = undefined FAILED! expected: one A
   Arr .proto+self sparse        ref  1 a = undefined FAILED! expected: one A
   Cls .proto sparse array trans ref  1 b = undefined FAILED! expected: one A
   Cls .proto+self sparse trans  ref  1 b = undefined FAILED! expected: one A
   Fcn .proto sparse array trans ref  1 d = undefined FAILED! expected: one A
   Fcn .proto sparse array immed ref  1 e = undefined FAILED! expected: one Epost
   FAILED passes:101 fails:10 unexpected passes: 0 expected failures: 0

TR rev 6749 (i.e. the repo tip as of yesterday):
   Arr .proto start1 array       ref  1 a = undefined FAILED! expected: one A
   Arr .proto start1 self sparse ref  1 a = undefined FAILED! expected: one A
   Cls .proto start1 array trans ref  1 b = undefined FAILED! expected: one A
   Cls .proto sparse array trans ref  1 b = undefined FAILED! expected: one A
   Fcn .proto start1 array trans ref  1 d = undefined FAILED! expected: one A
   Fcn .proto start1 array immed ref  1 e = undefined FAILED! expected: one Epost
   Arr .proto start1 array       ref 10 a = undefined FAILED! expected: ten A
   Cls .proto start1 array trans ref 10 b = undefined FAILED! expected: ten A
   Cls .proto sparse array trans ref 10 b = undefined FAILED! expected: ten A
   Fcn .proto start1 array trans ref 10 d = undefined FAILED! expected: ten A
   Fcn .proto start1 array immed ref 10 e = undefined FAILED! expected: ten Epost
   Arr .proto start0 array       ref  1 a = undefined FAILED! expected: one A
   Cls .proto start0 array trans ref  1 b = undefined FAILED! expected: one A
   Fcn .proto start0 array trans ref  1 d = undefined FAILED! expected: one A
   Fcn .proto start0 array immed ref  1 e = undefined FAILED! expected: one Epost
   Arr .proto start0 array       ref 10 a = undefined FAILED! expected: ten A
   Cls .proto start0 array trans ref 10 b = undefined FAILED! expected: ten A
   Fcn .proto start0 array trans ref 10 d = undefined FAILED! expected: ten A
   Fcn .proto start0 array immed ref 10 e = undefined FAILED! expected: ten Epost
   FAILED passes:92 fails:19 unexpected passes: 0 expected failures: 0

TR rev 6749 with patch P v2 applied:
   test run PASSED!

Comment 19

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: text formatted performance data for patch P v2

Another round of performance data.

I suspect most of the regressions can be disregarded because they are either:
1. In sparse array lookup (where one would expect a performance hit, especially when the key is not present), or

2. In benchmark suites that are known to be noisy junk (e.g. sunspider), or,

3. In untyped variants of code and the regressions are not reflected in the typed variants.

Comment 20

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to Felix S Klock II from comment #19)
> Created attachment 578008 [details]
> text formatted performance data for patch P v2

(p.s. these results were gathered on my iMac (a 2.66 Ghz Intel Core i5) using a 64-bit release avmshell build.)

Comment 21

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 577932 [details] [diff] [review]
test B v4: thorough testing of all kinds of corners

This test case is intended to land after the patch P v2 lands.  (It wouldn't make sense for it to land first since it exposes current buggy behavior.)

brbaker: feel free to hand off to dschaffe, or suggest that I demote the R? to a pending SR? and push.

Comment 22

[Lars T Hansen]

Comment on attachment 577674 [details] [diff] [review]
patch P v2: no version checks. no performance tuning.

A nit: the "ignoring proto" part is conventionally abbreviated as "own", eg, "hasOwnAtomProperty", "findOwnProperty".  What you have is perfectly clear so may actually be preferable.

Comment 23

[Tamarin Bot]

changeset: 6770:af3e1d66b791
user:      Felix S Klock II <[e-mail]>
summary:   Bug 687838: include sparse and dense parts during array prototype-chain lookups (r=lhansen).

http://hg.mozilla.org/tamarin-redux/rev/af3e1d66b791

Comment 24

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 577932 [details] [diff] [review]
test B v4: thorough testing of all kinds of corners

(switching to SR for QE and then pushing with a "SR pending" note)

Comment 25

[Tamarin Bot]

changeset: 6771:240207231e23
user:      Felix S Klock II <[e-mail]>
summary:   Bug 687838: test corner cases of array prototype chain lookup (sr pending=brbaker, f=lhansen).

http://hg.mozilla.org/tamarin-redux/rev/240207231e23