Closed Bug 578272 Opened 14 years ago Closed 14 years ago

TM: remove Algol-like display optimization

Categories

(Core :: JavaScript Engine, defect)

x86
Linux
defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: cdleary, Assigned: cdleary)

References

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(1 file, 1 obsolete file)

Attached patch Remove Algol-like display. (obsolete) — Splinter Review
+++ This bug was initially created as a clone of Bug #577708 +++

This time on tracemonkey tip. Switched to uintN typed formal parameters, per conversation in bug 577708.
Attachment #457004 - Flags: review?(brendan)
Comment on attachment 457004 [details] [diff] [review]
Remove Algol-like display.

When this lands on TM, we should remember to back out the JM one and re-apply.
Attachment #457004 - Attachment is patch: true
Attachment #457004 - Attachment mime type: application/octet-stream → text/plain
Depends on: 557378
No longer depends on: 577708
Blocks: 557378
No longer blocks: JaegerSpeed
No longer depends on: 557378
Comment on attachment 457004 [details] [diff] [review]
Remove Algol-like display.

>+/*
>+ * Search the call stack for the nearest frame with static level targetLevel.
>+ * @param baseFrame If not provided, the context's current frame is used.
>+ */
>+static JS_INLINE JSStackFrame *
>+FindFrameAtLevel(JSContext *cx, uintN targetLevel, JSStackFrame * const baseFrame = NULL)
>+{
>+    JSStackFrame *it = baseFrame ? baseFrame : cx->fp;
>+    JS_ASSERT(it && it->script);

All callers pass only two args, so get rid of the baseFrame param and start with cx->fp.

Canonical naming: s/\<it\>/fp/g

This should be a JSContext inline method, no?

>+    while (it->script->staticLevel != targetLevel) {
>+        it = it->down;
>+        JS_ASSERT(it && it->script);

Require cx->fp to be non-null and write a do-while loop to common the JS_ASSERT here with the one before the loop.

>-    JSStackFrame *displayCopy[JS_DISPLAY_SIZE];
>-    if (cx->fp != fp) {
>-        memcpy(displayCopy, cx->display, sizeof displayCopy);
>+    bool ok = !!js_Execute(cx, scobj, script, fp, JSFRAME_DEBUGGER | JSFRAME_EVAL, rval);
> 
>-        /*
>-         * Set up cx->display as it would have been when fp was active.
>-         *
>-         * NB: To reconstruct cx->display for fp, we have to follow the frame
>-         * chain from oldest to youngest, in the opposite direction to its
>-         * single linkge. To avoid the obvious recursive reversal algorithm,
>-         * which might use too much stack, we reverse in place and reverse
>-         * again as we reconstruct the display. This is safe because cx is
>-         * thread-local and we can't cause GC until the call to js_Execute
>-         * below.
>-         */
>-        JSStackFrame *fp2 = fp, *last = NULL;
>-        while (fp2) {
>-            JSStackFrame *next = fp2->down;
>-            fp2->down = last;
>-            last = fp2;
>-            fp2 = next;
>-        }
>-
>-        fp2 = last;
>-        last = NULL;
>-        while (fp2) {
>-            JSStackFrame *next = fp2->down;
>-            fp2->down = last;
>-            last = fp2;
>-
>-            JSScript *script = fp2->script;
>-            if (script && script->staticLevel < JS_DISPLAY_SIZE)
>-                cx->display[script->staticLevel] = fp2;
>-            fp2 = next;
>-        }
>-    }
>-
>-    ok = js_Execute(cx, scobj, script, fp, JSFRAME_DEBUGGER | JSFRAME_EVAL,
>-                    rval);
>-
>-    if (cx->fp != fp)
>-        memcpy(cx->display, displayCopy, sizeof cx->display);

Good riddance to this rubbish! Thanks.

>-    if (cg->staticLevel >= JS_DISPLAY_SIZE || upvarLevel >= JS_DISPLAY_SIZE)
>+    if (cg->staticLevel >= UpvarCookie::MAX_LEVEL || upvarLevel >= UpvarCookie::MAX_LEVEL)

MAX means last valid value, LIMIT means fencepost, so there's an off-by-one in the use of >= or else a misnomer -- see below for which.

>@@ -81,16 +81,17 @@ class UpvarCookie
>     static const uint32 FREE_VALUE = 0xfffffffful;
> 
>   public:
>     /*
>      * All levels above-and-including FREE_LEVEL are reserved so that
>      * FREE_VALUE can be used as a special value.
>      */
>     static const uint16 FREE_LEVEL = 0x3fff;
>+    static const uint16 MAX_LEVEL = FREE_LEVEL - 1;

Should just use FREE_LEVEL for the fencepost -- could give it an UPVAR_LEVEL_LIMIT alias to abstract from the encoding of FREE_LEVEL.

This is a big number. Do we want a lower upper bound?

/be
Actually, now that I think about it, we *have* to use a lower bound.

When we had a display, the static levels were divided into three parts: < JS_DISPLAY_SIZE, >= JS_DISPLAY_SIZE, and >= FREE_LEVEL. References to variables in static levels less than JS_DISPLAY_SIZE *could* be optimized via the display; however, skirting the edge case a bit, we passed on optimizing upvars for any function with a static level >= JS_DISPLAY_SIZE. (This omits the optimization case where a function with static level >= JS_DISPLAY_SIZE is still referring to an upvar with static level < JS_DISPLAY_SIZE.)

Cleverly, knowing that we omitted that case, we tricked EvaluateUCInStackFrame into using JSOP_NAME for all references by passing its compilation a starting static level value of JS_DISPLAY_SIZE.

Looking back at it, my patch is wrong -- maybe we don't have a test for EvaluateUCInStackFrame with nested functions, but the compilation will fail with the current value of MAX_LEVEL == FREE_LEVEL - 1 when it tries to compile the nested function and set the static level for it in SetStaticLevel, because it encroaches on FREE_LEVEL space.

The situation is different now, since there is no fixed display size to limit us -- now we're thinking of our limitations in terms of level skip "deltas". Really, we want to say that we will optimize any level skip delta less than some value where there is still benefit of linked (frame) list traversal over the prop$ lookup.

Unfortunately, this doesn't mesh too well with the clever UCInStackFrame trick. To reconcile this going forward, we can assume that static levels >= some value, like 16, will be rare, and use the same approach for forcing emission of JSOP_NAMEs that we used for a fixed-size display. i.e. If the static level is greater than some value, don't even try to use JSOP_UPVAR.
Didn't make FindFrameAtLevel a method because I think people want to keep JSContext devoid of as many members as possible. All of the other things should be fixed!
Assignee: general → cdleary
Attachment #457004 - Attachment is obsolete: true
Status: NEW → ASSIGNED
Attachment #459652 - Flags: review?
Attachment #457004 - Flags: review?(brendan)
Attachment #459652 - Flags: review? → review?(brendan)
(In reply to comment #4)
> Created attachment 459652 [details] [diff] [review]
> Remove Algol-like display.
> 
> Didn't make FindFrameAtLevel a method because I think people want to keep
> JSContext devoid of as many members as possible. All of the other things should
> be fixed!

We talked on IRC, methods rule, functions drool -- the many added to jscntxt.h as inline helpers for JSContext date from our C99 interregnum, post C but ante C++. Reviewing now.

/be
Comment on attachment 459652 [details] [diff] [review]
Remove Algol-like display.

>+FindFrameAtLevel(JSContext *cx, uintN targetLevel)

Methodize.

>@@ -1904,17 +1904,18 @@ MakeUpvarForEval(JSParseNode *pn, JSCode
>     JSAtom *atom = pn->pn_atom;
> 
>     uintN index;
>     JSLocalKind localKind = js_LookupLocal(cx, fun, atom, &index);
>     if (localKind == JSLOCAL_NONE)
>         return true;
> 
>     JS_ASSERT(cg->staticLevel > upvarLevel);
>-    if (cg->staticLevel >= JS_DISPLAY_SIZE || upvarLevel >= JS_DISPLAY_SIZE)
>+    if (cg->staticLevel >= UpvarCookie::UPVAR_LEVEL_LIMIT ||
>+        upvarLevel >= UpvarCookie::UPVAR_LEVEL_LIMIT)

Brace, or since that takes as many lines (gross), write two if-return line-pairs.

>-    JS_ASSERT(level < JS_DISPLAY_SIZE);
>-
>-    JSStackFrame *fp = cx->display[level];
>-    JS_ASSERT(fp->script);
>-
>+js::GetUpvar(JSContext *cx, uintN closureLevel, UpvarCookie cookie)
>+{
>+    JS_ASSERT(closureLevel >= cookie.level() && cookie.level() > 0);
>+    const uintN targetLevel = closureLevel - cookie.level();
>+    JSStackFrame *fp = FindFrameAtLevel(cx, targetLevel);

You lost the JS_ASSERT(level < JS_DISPLAY_SIZE), which would now be JS_ASSERT(targetLevel < UpvarCookie::UPVAR_LEVEL_LIMIT), right?

>@@ -3121,18 +3121,18 @@ GetUpvarOnTrace(JSContext* cx, uint32 up
>         *result = state->stackBase[native_slot];
>         return state->callstackBase[0]->get_typemap()[native_slot];
>     }
> 
>     /*
>      * If we did not find the upvar in the frames for the active traces,
>      * then we simply get the value from the interpreter state.
>      */
>-    JS_ASSERT(upvarLevel < JS_DISPLAY_SIZE);
>-    JSStackFrame* fp = cx->display[upvarLevel];
>+    JS_ASSERT(upvarLevel < UpvarCookie::FREE_LEVEL);

Not FREE_LEVEL, UPVAR_LEVEL_LIMIT -- check other JS_DISPLAY_SIZE on the left instances in the diff where there's a new counterpart on the right, I think I got 'em but you should verify. r=me with that.

/be
Attachment #459652 - Flags: review?(brendan) → review+
Blocks: 582422
Status: ASSIGNED → RESOLVED
Closed: 14 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: