344421 - Javascript Debugger (Venkman) does not collect correct data in the presence of indirect recursion

Status: RESOLVED INCOMPLETE

(Other Applications Graveyard :: Venkman JS Debugger, defect)

Description

[Randy D. Smith]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.0.4) Gecko/20060508 Firefox/1.5.0.4
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.0.4) Gecko/20060508 Firefox/1.5.0.4

Lines 185&186 and Lines 244&245 may be sufficient for "direct recursion" (e.g., factorial), but it's insufficient to handle indirect recursion (foo calls bar that calls foo).

I'll attach a couple of files, IndRecurse.html and indRecurse.js; the .html file just takes a number and calls a .js function to deal with the number and display the results. It’s just boilerplate.

So I run this and call doit with a set to 0, bar is called with 0, and almost nothing is done… doit and bar show all 0s… no surprise.

I call doit with a set to 1, and foo is called with 1, then bar is called with 0, and we return… again doit and bar show all 0s… no surprise… while CPU-intensive foo takes ~330ms.

I call doit with a set to 2, and foo is called with 2, then bar is called with 1, so then we do just as I described above in the prior paragraph and we return back up the stack… SURPRISE… CPU-intensive foo shows its outer call double data size of ~650ms, but *bar* gets attribution for its original inner call of ~320ms!!

Call doit with 3, and the result is that foo *and* bar are shown to take ~980ms!!

As you should see from the simple .js file, bar should never take any significant time!

Reproducible: Always

Steps to Reproduce:
1. Visit the IndRecurse.html file with the indRecurse.js file in the same directory.
2. Run Venkman; profile; back on page hit 0 and "Doit"; profile; save data; clear data
3. Repeat as in 2 with 1, 2, and 3. Don't forget to clear between runs.
4. View results... bar should never be attributed with any time.

Actual Results:  
bar is attributed with significant time it did not use.

Expected Results:  
bar should never take any significant time.

I think you need to "++ into recursion and -- out of recursion" in Lines 153-184 and 190-243 only when caller==callee; otherwise, you can just treat it like yet another call. I presume that recursion handling was just an optimization of sorts... but it breaks the model and yields bad results!

By the way, I put this as major not due to the sample I'm giving you... obviously this is a condensed version of a "real problem" involving massive amounts of code... the results are just not reliable in the presence of composition of classes that involves mutual recursion.

Comment 1

[Randy D. Smith]

Attachment: Simple html file to drive Javascript

Comment 2

[Randy D. Smith]

Attachment: Simple Javascript file that uses mutual or indirect (not direct) recursion

Comment 3

[James Ross]

Reporter, you have omited quite a bit of important information from your verbose report. You should always include the version of the product being used, and it would help in verify the report to used the actual name for the values given in the profile - or better, attach a sample report.

Also, for others' reference, the file being refered to only by line number is:
  http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/js/jsd/jsd_step.c&rev=3.16

As far as I can tell from the little information here, this is no more than the known limitation of the profiler: it can only keep a profile handle on a single call to a function at a time. It counts the recursion level so that it does not get totally confused in the nested calls to that function, whether direct or indirect.

The assertion that the recursion counter should only be used for caller==callee is incorrect, as it will not be able to tell when it has unwound to the top call of a specific function and thus will calculate the data as if the first return from the nested function is matched to the first entry.

If this case (or direct recursion) can ever be completely mapped to the profile data, the structure of the stored profile data will need the addition of a stack of call information. That would allow the data stored on entry of only the first call could be stored for all calls instead; this isn't a particularily trivial change, although I believe the public interface would not need any changes to allow for it.

Comment 4

[Randy D. Smith]

For "omited quite a bit of important information", my apologies; I can only claim (1) I was lulled to sleep by the automated inclusion of version information for all the other browser components, and (2) the Version field only references the Gecko #s, not Venkman's, and (3) having given references to lines of code in the CVS HEAD, I naively thought it was a given it was "the latest". Venkman reports version 0.9.87 ... where should I record this?

For the rest of paragraph 1, I'm sorry... your comments have gone right over my head. I'm not sure what you're asking for here! And I'm not sure what the "quite a bit" is saying I missed beyond the Venkman version #!

My apologies for leaving out the jsd_step.c link! I can't believe I did that. Thanks for including it for me.

I'm having trouble correlating "omited information" and "little information" with "your verbose report" ... I'll err on the side of verbosity every time just to avoid the problems you mention! Apologies in advance if that offends you!

"known limitation of the profiler" ... known by whom? Documented where? I skimmed through the entirety of the newsgroup, and searched bugzilla as best I could. Not only do I question this being "known", I don't think it's true! It's not an inherent limitation at all... in reality given a single thread of execution, there is nothing actually problematic about the presence of recursion, whether direct or indirect.

You're right about my "only when caller==callee" comment... and that isn't what I meant to say. What I meant to say was that you shouldn't separate out the recursion handling from the "crossed transition point from caller to callee" (and vice-versa) more general (and in-depth) case that is handled correctly... still treat every call, recursive or not, as a caller-to-callee transition; even if foo calls foo, to update foo's time as having been left as caller and (re-)initializing foo's data as having been entered as callee isn't wrong, even if inefficient. Then WITHIN that handling you can deal with the "I'm in recursion, I need to keep track of recursive depth" side-issue. I disagree that this means we have to shift to a "stack of data"... I considered that, and realized the model was sufficient if you're willing to be less than totally efficient; it can still work as designed if we're careful (getting the ordering of caller adn callee updates just right in the situation where they are the same data structure). Keep the recursion depth handling, but remove that handling as a separate and distinct case that bypasses necessary data updating for the sake of efficiency!

Comment 5

[James Ross]

It may be just about possible to squeeze out all the data without a stack, although at least one extra member would be needed on the current data block, as far as I can see. I don't, however, feel that the code would be neat or make sense easily, and already think it's not always clear enough in what it is doing.

Comment 6

[BMO Automation]

Component is obsolete so resolving bugs as INCOMPLETE