Last Comment Bug 638178 - Extend jsdIScript to allow fast retrieval of executable lines
: Extend jsdIScript to allow fast retrieval of executable lines
Status: RESOLVED FIXED
[fixed-in-tracemonkey]
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: x86_64 Linux
: -- normal (vote)
: ---
Assigned To: Steve Fink [:sfink] [:s:]
: jsd
Mentors:
Depends on: 639943
Blocks:
  Show dependency treegraph
 
Reported: 2011-03-02 11:55 PST by Steve Fink [:sfink] [:s:]
Modified: 2012-07-19 22:01 PDT (History)
4 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Fetch batch of executable lines at a time from jsdIScript (14.00 KB, patch)
2011-03-02 14:25 PST, Steve Fink [:sfink] [:s:]
timeless: review-
Details | Diff | Review
Mochitest for getExecutableLines (5.17 KB, patch)
2011-03-02 14:26 PST, Steve Fink [:sfink] [:s:]
timeless: review+
Details | Diff | Review
Fetch batch of executable lines at a time from jsdIScript (14.07 KB, patch)
2011-03-08 11:49 PST, Steve Fink [:sfink] [:s:]
timeless: review-
Details | Diff | Review
Fetch batch of executable lines at a time from jsdIScript (14.07 KB, patch)
2011-03-14 23:16 PDT, Steve Fink [:sfink] [:s:]
no flags Details | Diff | Review
Fetch batch of executable lines at a time from jsdIScript (14.10 KB, patch)
2011-03-14 23:19 PDT, Steve Fink [:sfink] [:s:]
timeless: review-
Details | Diff | Review
Fetch batch of executable lines at a time from jsdIScript (14.13 KB, patch)
2011-04-28 14:50 PDT, Steve Fink [:sfink] [:s:]
timeless: review+
Details | Diff | Review

Description Steve Fink [:sfink] [:s:] 2011-03-02 11:55:51 PST
Currently, if you want to know which lines of a script are executable, you have to loop over all the lines in the script and call isLineExecutable, which does an O(n) search. The result is slow enough that firebug apparently has to spawn off asynchronous jobs to collect the set of lines incrementally. (The code in firebug's content/firebug/sourceFile.js claims about 1ms per isLineExecutable call.)

Bug 449473 proposes one mechanism to speed this up: allow retrieving the maximum PC for a script, map the set of PCs to a set of lines, then iterate over those lines. That would be better, but it's still quadratic.

This bug proposes another mechanism: add an API specifically for returning the set of executable lines for a script. This is the only way to allow a linear scan over the source notes. It'll still require iterating over all scripts in a source file to find the executable lines, but the concept of a source file is nebulous so I don't see how to do better right now.

Honza, you mentioned a test case that was insanely slow. It had lots of functions within one file or something? Can you send it to me, so I can check whether this actually helps or if there's something else going on? (I don't know why multiple functions would hurt, other than making the outer script particularly slow because you're iterating over many many lines that have no code.)
Comment 1 John J. Barton 2011-03-02 12:14:43 PST
(In reply to comment #0)
> scan over the source notes. It'll still require iterating over all scripts in a
> source file to find the executable lines, but the concept of a source file is
> nebulous so I don't see how to do better right now.

I don't think that the "compilation unit" sent to the compiler is nebulous in any way: its just the bytes sent to the compiler and the result of compiling. True, it may not live in a file, but that's pretty much true for all of our source.  So I'll put a another plug in for compilation units, bug 449464, though I think Jim has some overlapping ideas from his new DebugObject work.
Comment 2 Steve Fink [:sfink] [:s:] 2011-03-02 14:20:44 PST
Yes. I meant "right now" as in "with JSD currently lacking any notion of source file or compilation unit." I'm experimenting with making a set of modest improvements to the current JSDv1, with two goals: (1) try out some changes to see if they're really what things like Firebug need, and (2) serve as a somewhat better basis for JSDv2's feature set. (Or maybe I should just call them JSD and... DebugObject?)

Unfortunately, it's a pain to make these sorts of changes to JSD. For example, for this minor change I have to modify 8 different source files for about 4 distinct layers that JSD goes through, when I'm really only doing significant work in one place. Not to mention the C vs C++ problem.
Comment 3 Steve Fink [:sfink] [:s:] 2011-03-02 14:25:22 PST
Created attachment 516406 [details] [diff] [review]
Fetch batch of executable lines at a time from jsdIScript

This adds a getExecutableLines call to jsdIScript to retrieve all executable lines in one go. (Actually, it allows the caller to specify a max number of lines it wants to get back, to handle really large cases.)

Note that internally, it calls a function that returns both the line numbers and the earliest PCs associated with each line number, discarding the latter. It might be useful to expose the PCs as well for some other purpose. (Or perhaps the API should be at that level, and the JS caller could discard them?)

Lightly tested.
Comment 4 Steve Fink [:sfink] [:s:] 2011-03-02 14:26:09 PST
Created attachment 516407 [details] [diff] [review]
Mochitest for getExecutableLines
Comment 5 Jim Blandy :jimb 2011-03-03 18:09:24 PST
Adding an API to retrieve this information explicitly is totally the way to go. I'll make sure Debug.Script has something for this.
Comment 6 Jim Blandy :jimb 2011-03-03 18:12:14 PST
(In reply to comment #2)
> (Or maybe I should just call
> them JSD and... DebugObject?)

It's going to appear in chrome globals as 'Debug', so "the Debug object" is the best name, I guess.
Comment 7 timeless 2011-03-05 13:31:38 PST
Comment on attachment 516406 [details] [diff] [review]
Fetch batch of executable lines at a time from jsdIScript

would endLine be better than maxlLines?

this is over indented by one space:
+     /**
      * Set a breakpoint at a PC in this script.
      */
     void setBreakpoint (in unsigned long pc);
     /**
      * Clear a breakpoint at a PC in this script.

on the subject of style, since you're doing this post 2.0 release, you might want to land a style enforcement patch first. e.g. get rid of the spaces between 'setBreakpoint' and '(...)' for all methods in the idl file.

+jsdScript::GetExecutableLines(PRUint32 aPcmap, PRUint32 aStartLine, PRUint32 aMaxLines,
+    if (aPcmap == PCMAP_SOURCETEXT) {
+        return NS_OK;

since you're returning above you should remove the |else| token here:
+    } else if (aPcmap == PCMAP_PRETTYPRINT) {
+        return NS_OK;

and since you're returning above, there's no need for the |else| token here or the bracing-block here:
+    } else {
+        return NS_ERROR_INVALID_ARG;

i suspect this should be a || condition:
+        if (!mPPLineMap && !CreatePPLineMap())
+            return NS_ERROR_OUT_OF_MEMORY;
Comment 8 timeless 2011-03-05 13:36:35 PST
Comment on attachment 516407 [details] [diff] [review]
Mochitest for getExecutableLines

seems fine pending my api comments
Comment 9 Steve Fink [:sfink] [:s:] 2011-03-08 11:49:31 PST
Created attachment 517826 [details] [diff] [review]
Fetch batch of executable lines at a time from jsdIScript

(In reply to comment #7)
> Comment on attachment 516406 [details] [diff] [review]
> Fetch batch of executable lines at a time from jsdIScript
> 
> would endLine be better than maxlLines?
> 
> this is over indented by one space:
> +     /**
>       * Set a breakpoint at a PC in this script.
>       */
>      void setBreakpoint (in unsigned long pc);
>      /**
>       * Clear a breakpoint at a PC in this script.

Fixed.

> on the subject of style, since you're doing this post 2.0 release, you might
> want to land a style enforcement patch first. e.g. get rid of the spaces
> between 'setBreakpoint' and '(...)' for all methods in the idl file.

Ok, done in bug 639943.

> 
> +jsdScript::GetExecutableLines(PRUint32 aPcmap, PRUint32 aStartLine, PRUint32
> aMaxLines,
> +    if (aPcmap == PCMAP_SOURCETEXT) {
> +        return NS_OK;
> 
> since you're returning above you should remove the |else| token here:
> +    } else if (aPcmap == PCMAP_PRETTYPRINT) {
> +        return NS_OK;

ok

> and since you're returning above, there's no need for the |else| token here or
> the bracing-block here:
> +    } else {
> +        return NS_ERROR_INVALID_ARG;

ok

> i suspect this should be a || condition:
> +        if (!mPPLineMap && !CreatePPLineMap())
> +            return NS_ERROR_OUT_OF_MEMORY;

No, I don't think so. mPPLineMap is being computed lazily by CreatePPLineMap(). This is copied from IsLineExecutable, and is a condensed form of

  if (!mPPLineMap) {
    if (!CreatePPLineMap)
      return NS_ERROR_OUT_OF_MEMORY;
  }

What about the UUID updates? From discussion on #developers resulting from http://blog.mozilla.com/sfink/2011/03/02/updating-uuids/ it seems like people only update immediately impacted interfaces' uuids. Am I updating too many in this patch?
Comment 10 timeless 2011-03-12 16:18:03 PST
Comment on attachment 517826 [details] [diff] [review]
Fetch batch of executable lines at a time from jsdIScript

+jsd_GetLinePCs(JSDContext* jsdc, JSDScript* jsdscript,

please don't use 'rv' unless it's 'nsresult', use 'ok' for JSBool:
+    JSBool rv;

+jsdScript::GetExecutableLines(PRUint32 aPcmap, PRUint32 aStartLine, PRUint32 aMaxLines,
+        *aExecutableLines = static_cast<PRUint32*>(NS_Alloc((end - start + 1) * sizeof(PRUint32)));

i think you're missing an alloc check here

+        if (!JSD_GetLinePCs (mCx, mScript, aStartLine, aMaxLines, aCount, aExecutableLines, NULL))

please no space between function and (args).

i think i'd rather the expanded form here:
+        if (!mPPLineMap && !CreatePPLineMap())
+            return NS_ERROR_OUT_OF_MEMORY;

yes you can collapse things, but i spend a lot of time dealing w/ coding errors as reported by certain tools and some verbosity to avoid guessing that an operator is confused is appreciated.
+
+        *aExecutableLines = static_cast<PRUint32*>(NS_Alloc(lines.Length() * sizeof(PRUint32)));
+        if (!*aExecutableLines)
+            return NS_ERROR_OUT_OF_MEMORY;

+            (*aExecutableLines)[i] = lines[i];

please avoid trailing whitespace:
+        


+ * Get a list of lines and the corresponding earliest PC for each (see
+ * JSD_GetClosestPC). Lines without any PCs associated with them will not be
+ * returned. NULL may be passed for either lines or pcs to avoid filling
+ * anything in.

in <for that argument> ?

otherwise, it sounds like it won't fill in the provided arguments either.

---

to your question about bumping iid's. simply put, the people with whom you spoke almost certainly don't spend their time analyzing unhappy crashes relating to third party bits which suffer from this problem. because of the way iid's work, these problems can happen. we have all sorts of problems which result in lots of crash reports that take years to diagnose which stem from similar stupid shortcuts. there's a recent case where we had a mix of .dll's from other versions because the updater probably failed to deal w/ locked files or something. it replaces a previous incarnation involving leftover xpt files or a previous version involving unzipping over previous versions. we are cavalier and the result is many lost hours.
Comment 11 Steve Fink [:sfink] [:s:] 2011-03-14 23:16:38 PDT
Created attachment 519339 [details] [diff] [review]
Fetch batch of executable lines at a time from jsdIScript

Addressed review comments.

But jimb is proposing a slightly different, more complete interface for the Debug Object, so I'll rework this to match his getAllOffsets() before requesting review again.

https://wiki.mozilla.org/Debug_Object#Properties_of_the_Debug.Script_Prototype_Object
Comment 12 Steve Fink [:sfink] [:s:] 2011-03-14 23:19:08 PDT
Created attachment 519340 [details] [diff] [review]
Fetch batch of executable lines at a time from jsdIScript

Whoops, forgot to qref.
Comment 13 Steve Fink [:sfink] [:s:] 2011-03-31 15:06:56 PDT
Comment on attachment 519340 [details] [diff] [review]
Fetch batch of executable lines at a time from jsdIScript

Never mind. I sat down to finally make the update. I think I'd still want the API I just added, and it seems like much of the code wouldn't be reusable for the Debug object. So although it would be nice to have an IDL-based getAllOffsets(), I'd rather get this getExecutableLines() in first. (It won't be hard for users to migrate from getExecutableLines -> getAllOffsets.)

So I'm requesting review again. I think I've resolved all of your previous comments.
Comment 14 timeless 2011-04-09 17:58:36 PDT
Comment on attachment 519340 [details] [diff] [review]
Fetch batch of executable lines at a time from jsdIScript

>+     * Return a list of all executable lines in a script.
>+     * |pcmap| specifies which pc to source line map to use.
>+     * |startLine| and |maxLines| may be used to retrieve a chunk at a time.

>+    void getExecutableLines(in unsigned long pcmap,
>+                            in unsigned long startLine, in unsigned long maxLines,

i'm not sure how [optional] works, i don't suppose you have a useful reference for it?
>+                            [optional] out unsigned long count,
>+                            [array, size_is(count), retval] out unsigned long executableLines);

>+    if (last < startLine)

space after 'if':
>+    if(!call)

split this condition:
>+    if (ok && retPCs) {
>+    }
so the primary if is shared with this:
>+    if (ok) {
>+    }

>+jsdScript::GetExecutableLines(PRUint32 aPcmap, PRUint32 aStartLine, PRUint32 aMaxLines,

>+        if (!*aExecutableLines)
>+            return NS_ERROR_OUT_OF_MEMORY;
insert blank line here
>+        for (i = 0; i < lines.Length(); ++i)

jsdebug has a stupid comment style: file a bug and fix it?
> /*
> */
> extern JSD_PUBLIC_API(uintN)
> JSD_GetClosestLine(JSDContext* jsdc, JSDScript* jsdscript, jsuword pc);

>+/*
>+ * Get a list of lines and the corresponding earliest PC for each (see
>+ * JSD_GetClosestPC). Lines with no PCs associated will not be returned. NULL
should PCs here be written in that case:
>+ * may be passed for either lines or pcs to avoid filling anything in for that

>+JS_GetLinePCs(JSContext *cx, JSScript *script,

>+    if (!lines)
>+        return JS_FALSE;
insert blank line here
>+    pcs = (jsbytecode**) cx->malloc(len * sizeof(jsbytecode*));
Comment 15 Steve Fink [:sfink] [:s:] 2011-04-28 14:50:31 PDT
Created attachment 528957 [details] [diff] [review]
Fetch batch of executable lines at a time from jsdIScript

(In reply to comment #14)
> Comment on attachment 519340 [details] [diff] [review]
> Fetch batch of executable lines at a time from jsdIScript
> 
> >+     * Return a list of all executable lines in a script.
> >+     * |pcmap| specifies which pc to source line map to use.
> >+     * |startLine| and |maxLines| may be used to retrieve a chunk at a time.
> 
> >+    void getExecutableLines(in unsigned long pcmap,
> >+                            in unsigned long startLine, in unsigned long maxLines,
> 
> i'm not sure how [optional] works, i don't suppose you have a useful reference
> for it?

Oh, it's easy. You just cut & paste it from another IDL definition and... oh, sorry. You mean what it's for, not how to use it.

http://www.w3.org/TR/2008/WD-WebIDL-20081219/#Optional says it's equivalent to defining overloaded versions of the same entry with and without each optional argument. But the latest working draft says that "[optional]" has been removed, though plain "optional" still exists. And xpidl doesn't accept plain "optional"; am I looking at the right spec?

I copied it from getParameterNames.

I tried removing it to see what the behavior is like. It definitely wants it (though it's rather useless for a scripted caller). It demands to have an object passed in and it sets its .value property. I can't just pass in a numeric variable and have it updated.

I could make a [script] and non-[script] version, leaving it off the [script] version...?

> >+                            [optional] out unsigned long count,
> >+                            [array, size_is(count), retval] out unsigned long executableLines);
> 
> >+    if (last < startLine)
> 
> space after 'if':
> >+    if(!call)
> 

err... which is good and which is bad? There are 26 'if (' and 45 'if(' in jsd_scpt.c. (My annoyance level is bringing me closer to reformatting everything and renaming to .cpp.)

> split this condition:
> >+    if (ok && retPCs) {
> >+    }
> so the primary if is shared with this:
> >+    if (ok) {
> >+    }

done

> 
> >+jsdScript::GetExecutableLines(PRUint32 aPcmap, PRUint32 aStartLine, PRUint32 aMaxLines,
> 
> >+        if (!*aExecutableLines)
> >+            return NS_ERROR_OUT_OF_MEMORY;
> insert blank line here
> >+        for (i = 0; i < lines.Length(); ++i)
> 
> jsdebug has a stupid comment style: file a bug and fix it?
> > /*
> > */
> > extern JSD_PUBLIC_API(uintN)
> > JSD_GetClosestLine(JSDContext* jsdc, JSDScript* jsdscript, jsuword pc);

Maybe once I work through some backlog.

> >+/*
> >+ * Get a list of lines and the corresponding earliest PC for each (see
> >+ * JSD_GetClosestPC). Lines with no PCs associated will not be returned. NULL
> should PCs here be written in that case:
> >+ * may be passed for either lines or pcs to avoid filling anything in for that
> 
> >+JS_GetLinePCs(JSContext *cx, JSScript *script,
> 
> >+    if (!lines)
> >+        return JS_FALSE;
> insert blank line here
> >+    pcs = (jsbytecode**) cx->malloc(len * sizeof(jsbytecode*));

done
Comment 16 Steve Fink [:sfink] [:s:] 2011-05-23 17:49:17 PDT
review ping.

Although I know timeless isn't actively reading bugmail right now, so I'll pester him via another channel.
Comment 17 timeless 2011-05-24 06:48:50 PDT
Comment on attachment 528957 [details] [diff] [review]
Fetch batch of executable lines at a time from jsdIScript

> +        if (aCount)
> +            *aCount = lines.Length();
<insert blank line here>
> +        *aExecutableLines = static_cast<PRUint32*>(NS_Alloc(lines.Length() * sizeof(PRUint32)));
> +        if (!*aExecutableLines)
> +            return NS_ERROR_OUT_OF_MEMORY;

re your question about style...
the style i want has a space between `if` and `(`

and yes, when you get around to it, please just commit a patch which reformats the whole thing r=me.

Note You need to log in before you can comment on or make changes to this bug.