1190454 - Reduce Code Coverage overhead

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Nicolas B. Pierron [:nbp]]

As reported in Bug 1190446, the overhead of having code coverage in the interpreter and in baseline is of 11%.

At the whistler meeting, we decided [1] that 10% overhead would be the maximum for a code coverage implementation in SpiderMonkey.

Currently, the approach taken with PCCounts was to increment counters for every instruction, which is not practical in terms of performance apparently.  While being precise, we do not have to profile every instrumentation, but only branches and record when a script throws.

To make this information practical, the easiest approach is to record the location of the "pc" after each taken branch, and at the entry point of the script.  Then, recovering the code coverage information becomes an iterative process which iterates linearly over the bytecode.

[1] https://etherpad.mozilla.org/JS-Code-Coverage-meeting-notes

Comment 1

[Nicolas B. Pierron [:nbp]]

Attachment: part 0 - Remove unnecessary use of AppendArrayJSONMProperties.

Comment 2

[Nicolas B. Pierron [:nbp]]

Attachment: part 1 - PCCounts use uint64_t instead of a double to count the number of hits.

This reduces the overhead to ~9%.

Comment 3

[Nicolas B. Pierron [:nbp]]

Attachment: part 2 - Only compute code coverage of jump targets.

This surprisingly does not reduce the overhead while running the jsreftest
suite, but this should definitely use less memory.

I presume that we should probably only instrument the JOF_JUMP instruction
instead of keeping the code for every instruction, but I have no idea on how
to make this work for the script->main() pc otherwise.

Comment 4

[Tom S. (please needinfo tschuster)]

Comment on attachment 8643588 [details] [diff] [review]
part 1 - PCCounts use uint64_t instead of a double to count the number of hits.

Review of attachment 8643588 [details] [diff] [review]:
-----------------------------------------------------------------

Huhu my 2% was really good.

Comment 5

[Brian Hackett [Laid off!]]

Comment on attachment 8643589 [details] [diff] [review]
part 2 - Only compute code coverage of jump targets.

Review of attachment 8643589 [details] [diff] [review]:
-----------------------------------------------------------------

This patch doesn't seem like a great idea.  If we only compute code coverage for jump targets then we won't really be able to recover coverage information for the rest of the script, since looking at jump targets doesn't account for exceptional control flow paths.  If there is code like:

if (a) {
   f();
   g();
}

If we only know how many times the call to f() executes, we still don't know whether the call to g() ever executed, if f() always throws.  Presumably a code coverage tool will want to know for sure whether the call to g() has ever executed.

Comment 6

[Nicolas B. Pierron [:nbp]]

(In reply to Brian Hackett (:bhackett) from comment #5)
> If we only know how many times the call to f() executes, we still don't know
> whether the call to g() ever executed, if f() always throws.  Presumably a
> code coverage tool will want to know for sure whether the call to g() has
> ever executed.

Indeed, I was planning on addressing that later, by allocating a map of throwing-pc to their PCCounts.  Should I implemented it as part of this bug, or would it be fine to make a follow-up bug for it?

Comment 7

[Brian Hackett [Laid off!]]

(In reply to Nicolas B. Pierron [:nbp] from comment #6)
> (In reply to Brian Hackett (:bhackett) from comment #5)
> > If we only know how many times the call to f() executes, we still don't know
> > whether the call to g() ever executed, if f() always throws.  Presumably a
> > code coverage tool will want to know for sure whether the call to g() has
> > ever executed.
> 
> Indeed, I was planning on addressing that later, by allocating a map of
> throwing-pc to their PCCounts.  Should I implemented it as part of this bug,
> or would it be fine to make a follow-up bug for it?

It seems to me like the two should happen in the same bug, so that the code coverage information will always be able to provide a precise hit count for each bytecode.

Comment 8

[Nicolas B. Pierron [:nbp]]

Attachment: part 3 - PCCounts: Collect throw/catch hit counts.

This patch add a new vector of PCCounts which records number of exception
handled and their PC.

This works correctly (see test case of Bug 1191289).

Note: I will make a follow-up patch to update the JSON output.

Comment 9

[Brian Hackett [Laid off!]]

Comment on attachment 8648862 [details] [diff] [review]
part 3 - PCCounts: Collect throw/catch hit counts.

Review of attachment 8648862 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsscript.cpp
@@ +1300,5 @@
>              }
>          }
>      }
>  
> +    // Mark catch blocks as being jump targets.

This handles finally blocks as well, right?  It would be good if the comment clarified this.

@@ +1419,5 @@
> +        end = throwCountsVector + throwCountsSize;
> +        std::copy_backward(elem, end - 1, end);
> +        *elem = searched;
> +    }
> +    return elem;

The manual memory management and array fiddling here is pretty unfortunate.  Could throwCountsVector be an actual Vector<> instead?  Then you could use Vector::insert for the insertion.

::: js/src/jsscript.h
@@ +462,5 @@
>  {
>      friend class ::JSScript;
>      friend struct ScriptAndCounts;
>  
> +    // This sorted vector is used to map an offset to the number of times a

s/vector/array/

@@ +494,5 @@
> +    PCCounts* getThrowCounts(size_t offset) const;
> +
> +    // Return the counter used to count the number of throws. Allocate it if
> +    // none exists yet. Returns null if the allocation failed.
> +    PCCounts* getThrowCountsAndAdd(size_t offset);

For more consistency with other parts of the VM it would be nice if these methods were named maybeGetPCCounts, maybeGetThrowCounts, and getThrowCounts, respectively.

::: js/src/vm/Interpreter.cpp
@@ +1428,5 @@
>      MOZ_ASSERT(regs.fp()->script()->containsPC(regs.pc));
>  
> +    if (regs.fp()->script()->hasScriptCounts()) {
> +        PCCounts* counts = regs.fp()->script()->getThrowCountsAndAdd(regs.pc);
> +        // If we failled to allocate, then skip the increment and continue to

typo

@@ +1429,5 @@
>  
> +    if (regs.fp()->script()->hasScriptCounts()) {
> +        PCCounts* counts = regs.fp()->script()->getThrowCountsAndAdd(regs.pc);
> +        // If we failled to allocate, then skip the increment and continue to
> +        // handle the exceptions.

exception

@@ +1472,3 @@
>            case FinallyContinuation:
> +            // No need to increment the PCCounts number of execution here, as the interpreter
> +            // increment any PCCounts if present.

increments

Comment 10

[Nicolas B. Pierron [:nbp]]

(In reply to Brian Hackett (:bhackett) from comment #9)
> @@ +1419,5 @@
> > +        end = throwCountsVector + throwCountsSize;
> > +        std::copy_backward(elem, end - 1, end);
> > +        *elem = searched;
> > +    }
> > +    return elem;
> 
> The manual memory management and array fiddling here is pretty unfortunate. 
> Could throwCountsVector be an actual Vector<> instead?  Then you could use
> Vector::insert for the insertion.

I tried at first, and this involved having 2 different scheme of allocation, changing the prototype of a few unrelated functions.  Thus I felt back on using the same allocation scheme for now.

I will do a follow-up patch to remove these bare pointers by mozilla::Vector<PCCounts>.

Comment 11

[Nicolas B. Pierron [:nbp]]

Attachment: part 2 - Only compute code coverage of jump targets.

Comment 12

[Nicolas B. Pierron [:nbp]]

Attachment: part 3 - PCCounts: Collect throw/catch hit counts.

Comment 13

[Nicolas B. Pierron [:nbp]]

Attachment: part 4 - Use mozilla::Vector in js::ScriptCounts.

Comment 14

[Nicolas B. Pierron [:nbp]]

Attachment: part 5 - Update GetPCCountJSON to consider jumpTargets and Throws.

Comment 15

[Brian Hackett [Laid off!]]

Comment on attachment 8652356 [details] [diff] [review]
part 2 - Only compute code coverage of jump targets.

Review of attachment 8652356 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsopcode.h
@@ +771,5 @@
>   * coherent fashion.
>   */
>  class PCCounts
>  {
> +    size_t offset_;

It would be nice if this field had either a comment or a more obvious name, like pcOffset_.

::: js/src/jsscript.cpp
@@ +1298,5 @@
> +    }
> +
> +    // Sort all pc, and remove duplicates.
> +    std::sort(jumpTargets.begin(), jumpTargets.end());
> +    std::unique(jumpTargets.begin(), jumpTargets.end());

I think you need to use the return value of this unique() call to trim the length of jumpTargets.

Comment 16

[Brian Hackett [Laid off!]]

Comment on attachment 8652357 [details] [diff] [review]
part 3 - PCCounts: Collect throw/catch hit counts.

Review of attachment 8652357 [details] [diff] [review]:
-----------------------------------------------------------------

This patch still has several of the same typos and other issues that I pointed out in my earlier review.  Can you fix those and post a new patch?

Comment 17

[Brian Hackett [Laid off!]]

Comment on attachment 8652360 [details] [diff] [review]
part 5 - Update GetPCCountJSON to consider jumpTargets and Throws.

Review of attachment 8652360 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsopcode.cpp
@@ +1809,5 @@
> +        // If the current instruction has thrown,
> +        // then decrement the hit counts with the number of throws.
> +        counts = sac.maybeGetThrowCounts(pc);
> +        if (counts)
> +            hits -= counts->numExec();

Shouldn't you decrement the hit counts for the *next* instruction, rather than the one which actually threw?  Even if an instruction throws, it still executed.

Comment 18

[Nicolas B. Pierron [:nbp]]

(In reply to Brian Hackett (:bhackett) from comment #16)
> Comment on attachment 8652357 [details] [diff] [review]
> part 3 - PCCounts: Collect throw/catch hit counts.
> 
> This patch still has several of the same typos and other issues that I
> pointed out in my earlier review.  Can you fix those and post a new patch?

Sorry, I did the modifications before and forgot to apply your comments in the HandleError function after merging the patches.

(In reply to Brian Hackett (:bhackett) from comment #17)
> Comment on attachment 8652360 [details] [diff] [review]
> part 5 - Update GetPCCountJSON to consider jumpTargets and Throws.
> 
> Shouldn't you decrement the hit counts for the *next* instruction, rather
> than the one which actually threw?  Even if an instruction throws, it still
> executed.

Indeed, I'll do the same modification in Bug 1191289 part 2.

Comment 19

[Nicolas B. Pierron [:nbp]]

Attachment: part 3 - PCCounts: Collect throw/catch hit counts.

Comment 20

[Nicolas B. Pierron [:nbp]]

Attachment: part 5 - Update GetPCCountJSON to consider jumpTargets and Throws.

Comment 21

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8643588 [details] [diff] [review]
part 1 - PCCounts use uint64_t instead of a double to count the number of hits.

Review of attachment 8643588 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsopcode.h
@@ +771,5 @@
>   * coherent fashion.
>   */
>  class PCCounts
>  {
> +    uint64_t numExec_;

As this change replace the double by an int64 increment (likely done in 2 int32 increments on MIPS/x86), we can safely remove the static assertion added by Bug 774760.

I'll do that as part of this patch.

Comment 22

[Nicolas B. Pierron [:nbp]]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=08b4be09818e

Comment 23

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/f0b4e8e1f38f
https://hg.mozilla.org/integration/mozilla-inbound/rev/10e601553e1e
https://hg.mozilla.org/integration/mozilla-inbound/rev/1257e50e5c95
https://hg.mozilla.org/integration/mozilla-inbound/rev/a3b2a13402ac
https://hg.mozilla.org/integration/mozilla-inbound/rev/b059a3535628
https://hg.mozilla.org/integration/mozilla-inbound/rev/bc8f81a31df4

Comment 25

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/f0b4e8e1f38f
https://hg.mozilla.org/mozilla-central/rev/10e601553e1e
https://hg.mozilla.org/mozilla-central/rev/1257e50e5c95
https://hg.mozilla.org/mozilla-central/rev/a3b2a13402ac
https://hg.mozilla.org/mozilla-central/rev/b059a3535628
https://hg.mozilla.org/mozilla-central/rev/bc8f81a31df4