944930 - Remove blockIndex from aliasedvar ops

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Brian Hackett [Laid off!]]

Attachment: patch

From measurements Luke did in in bug 939088, pruning the size of ALIASEDVAR ops from 9 to 5 bytes could save a non-trivial amount of memory, maybe .05% of explicit on typical workloads.  The attached patch removes the blockIndex from these ops, instead finding the static block object associated with the op by doing a binary search on the script's block scopes.

Comment 1

[Luke Wagner [:luke]]

Thanks for doing this.  I think there is a bug, but I'm not sure.  Since blockNotes are linear and let scopes form a tree, I assume blockNotes are stored in post-order so that the linear search tests children before it tests the enclosing parent scope.  Thus, if we do a binary search, it seems like we could hit the parent before the children.  Did you run jit-tests on this patch?

One obvious fix is to flatten the tree by breaking parent scopes into non-overlapping disjoint intervals.  This could potentially waste more space for block notes (roughly 2x if you have one big module function with lots of nested let scopes).

Another more fun algorithm I'm thinking of would work on the tree structure:

 i = binary_search(full range)
 if (i == -1)
   return -1;
 while ((j = binary_search(range up to but not including i) != -1)
   i = j;
 return i;

Assuming a max tree depth, this would still be O(log n).  For pathological nesting, it'd still only be O(n log n).

Comment 2

[Brian Hackett [Laid off!]]

The algorithm in this patch works on the tree structure.  jit-tests pass (which do test this functionality) and I did some additional local testing.  The block notes are actually stored in the other order, parents before children.  If things were the other way around, children before parents, the 'break' in the current code could hit on children before the parent was encountered.

The binary search works because if it finds a matching block it will still continue the search for another inner one at a higher index in the blockScopes.  This is what the 'We found a matching block chain ...' comment indicates.  The search only stops when the searched range has zero elements.

Comment 3

[Luke Wagner [:luke]]

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

oh duh, sorry

Comment 4

[Brian Hackett [Laid off!]]

Attachment: updated

Actually, the binary search in this patch turned out to be broken after all --- if it found an inner block before the searched pc, it would look at higher indexes but not for any block enclosing both the inner block and the searched pc.  The attached patch fixes this; the worst case performance here is O(n) when each block is nested in the one before it.

Comment 5

[Luke Wagner [:luke]]

Comment on attachment 8344031 [details] [diff] [review]
updated

Review of attachment 8344031 [details] [diff] [review]:
-----------------------------------------------------------------

D'oh!

::: js/src/jsopcode.cpp
@@ +1449,5 @@
> +
> +    // Find the innermost block chain using a binary search.
> +    size_t bottom = 0;
> +    size_t top = blockScopes->length;
> +    size_t mid = bottom + (top - bottom) / 2;

Can you move the decl+init of 'mid' into the 'while' and remove the assignment to 'mid' at the end of the loop?

@@ +1462,5 @@
> +            // the searched range for coverage.
> +            size_t check = mid;
> +            while (check >= bottom) {
> +                const BlockScopeNote *checkNote = &blockScopes->vector[check];
> +                if (checkNote->start <= offset && offset <= checkNote->start + checkNote->length) {

Since we're traversing the parent chain and (I assume) parent->start <= child->start and we've already checked child->start <= offset above, it seems like you could remove the first conjunct.

Comment 6

[Brian Hackett [Laid off!]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/5bb192fc539e

Comment 7

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/5bb192fc539e