Closed Bug 944930 Opened 6 years ago Closed 6 years ago

Remove blockIndex from aliasedvar ops


(Core :: JavaScript Engine, defect)

Not set





(Reporter: bhackett, Assigned: bhackett)


(Blocks 1 open bug)


(Whiteboard: [qa-])


(1 file, 1 obsolete file)

Attached patch patch (obsolete) — Splinter Review
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.
Attachment #8340681 - Flags: review?(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).
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 on attachment 8340681 [details] [diff] [review]

oh duh, sorry
Attachment #8340681 - Flags: review?(luke) → review+
Blocks: 947044
Attached patch updatedSplinter Review
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.
Attachment #8340681 - Attachment is obsolete: true
Attachment #8344031 - Flags: review?(luke)
Comment on attachment 8344031 [details] [diff] [review]

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


::: 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.
Attachment #8344031 - Flags: review?(luke) → review+
Assignee: nobody → bhackett1024
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla28
Depends on: 947661
Depends on: 947680
Depends on: 947703
Whiteboard: [qa-]
You need to log in before you can comment on or make changes to this bug.