Closed
Bug 944930
Opened 11 years ago
Closed 11 years ago
Remove blockIndex from aliasedvar ops
Categories
(Core :: JavaScript Engine, defect)
Tracking
()
RESOLVED
FIXED
mozilla28
People
(Reporter: bhackett1024, Assigned: bhackett1024)
References
(Blocks 1 open bug)
Details
(Whiteboard: [qa-])
Attachments
(1 file, 1 obsolete file)
14.38 KB,
patch
|
luke
:
review+
|
Details | Diff | 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)
![]() |
||
Comment 1•11 years ago
|
||
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).
Assignee | ||
Comment 2•11 years ago
|
||
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•11 years ago
|
||
Comment on attachment 8340681 [details] [diff] [review]
patch
oh duh, sorry
Attachment #8340681 -
Flags: review?(luke) → review+
Assignee | ||
Comment 4•11 years ago
|
||
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 5•11 years ago
|
||
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.
Attachment #8344031 -
Flags: review?(luke) → review+
Assignee | ||
Comment 6•11 years ago
|
||
Comment 7•11 years ago
|
||
Assignee: nobody → bhackett1024
Status: NEW → RESOLVED
Closed: 11 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla28
Updated•11 years ago
|
Whiteboard: [qa-]
You need to log in
before you can comment on or make changes to this bug.
Description
•