1004110 - Memoize PCToLineNumber lookups in SavedStacks

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

From https://lists.mozilla.org/pipermail/dev-tech-js-engine-internals/2014-January/001555.html by jimb:

When we're running bytecode, looking up the corresponding source 
location entails parsing source notes until we have reached the desired 
bytecode location, by which time the source notes have told us the 
current line and column number. So this lookup is linear in the length 
of the source notes.

Similarly, when we're running IonMonkey code, finding the corresponding 
source location entails looking up the OsiIndex for the given return 
address, and then (I gather) consulting the snapshot for more details. 
And that work yields a JSScript and bytecode offset, which must be 
looked up in the source notes, as above.

But for profiling - and, I suspect, many other uses - this work is 
usually wasted: we often capture stacks that we don't print. So we 
should put off all these lookups as long as possible.

It seemed to me that we could minimize the actual lookups by 
representing code positions using a type that was quick to construct, 
and put off doing the lookups until asked. This AbstractCodePtr class 
could store an <IonScript, displacement> pair, or a <JSScript, bytecode 
offset> pair, or an actual <URL, line, column> - and mutate itself from 
lazier to more reified forms on demand.

If each compartment stored a HashMap from scripts to sets of 
AbstractCodePtrs in that script, then the destructors for IonScripts and 
JSScripts could do a just-in-time de-lazification, so that holding an 
AbstractCodePtr needn't force the underlying IonScript or JSScript to be 
held alive as well. An AbstractCodePtr would simply delazify itself as 
needed to allow its referent to die first.

Comment 1

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Jim, how will this affect the hashing of SavedFrame instances? Would we hash the <IonScript, displacement> or the <JSScript, bytecode offset> and keep rehashing as we get more and more reified?

Couldn't this result in multiple SavedFrame objects representing the same source location? For example, if the stack is captured before its script is bumped up into Ion, and then once again when its in Ion. Is this an acceptable price to pay?

Comment 2

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Also, because we are using ScriptFrameIter when traversing the stack to save, we will always have a JSScript and only need to lazily go from <JSScript, bytecode offset> to full location. No need for the Ion layer.

Comment 3

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

After talking with shu, we decided it is simpler to just memoize the PCToLineNumber lookup in a table on JSCompartment and then prune the table whenever an entry's JSScript is about to be finalized.

Comment 4

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: memoize-pc-to-line-number.patch

https://tbpl.mozilla.org/?tree=Try&rev=ad7db2078aa2

Comment 5

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

New debugger benchmark results. TLDR: 2.6x faster with this patch (vs bug 993085 comment 6)! Still about 6x slower than just enabling debugger mode, though.

~~~~~~~~~~~~~~~~~~~

--ion,    debugger, trackingAllocationSites
warmup
measure
[Stats total: 640.0504309082035s, mean: 1.280100861816407s, stddev: 6%]

--no-ion, debugger, trackingAllocationSites
warmup
measure
[Stats total: 630.1740961914061s, mean: 1.2603481923828121s, stddev: 6%]

--ion,    debugger, no hooks
warmup
measure
[Stats total: 105.39166625976573s, mean: 0.21078333251953146s, stddev: 3%]

--no-ion, debugger, no hooks
warmup
measure
[Stats total: 104.71202416992179s, mean: 0.20942404833984357s, stddev: 4%]

Comment 6

[Shu-yu Guo [:shu]]

Comment on attachment 8440974 [details] [diff] [review]
memoize-pc-to-line-number.patch

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

The structure and approach looks good to me.

What I'm not clear on are the ReadBarriered and RelocatablePtr stuff inside the hash map key structs. AFAICT, those fields are not overwritten except during rekeying, which is done under GC anyways, so write barriers should not be needed. I'm changing review to Terrence for the barrier bits.

::: js/src/vm/SavedStacks.cpp
@@ +524,5 @@
>      SavedFrame &f = frameObj->as<SavedFrame>();
>      f.initFromLookup(lookup);
>      return &f;
>  }
> +/*

Nit: newline above /*

@@ +535,5 @@
> +        PCKey key = e.front().key();
> +        JSScript *script = key.script.get();
> +        if (IsScriptAboutToBeFinalized(&script))
> +            e.removeFront();
> +        else if (script != key.script.get()) {

Style nit: if one branch of an if needs braces, use braces for both. i.e.,

if (IsScriptAboutToBeFinalized(&script)) {
    e.removeFront();
} else if (...) {

::: js/src/vm/SavedStacks.h
@@ +79,5 @@
>      static SavedFrame *checkThis(JSContext *cx, CallArgs &args, const char *fnName);
>  };
>  struct SavedFrame::Lookup {
>      Lookup(JSAtom *source, size_t line, size_t column, JSAtom *functionDisplayName,
> +           SavedFrame* parent, JSPrincipals *principals)

Style nit: SavedFrame *parent

@@ +142,5 @@
> +
> +    // Cache for memoizing PCToLineNumber lookups.
> +
> +    struct PCKey {
> +        PCKey(JSScript *script, jsbytecode *pc) : script(script), pc(pc) { };

Stray semicolon?

@@ +149,5 @@
> +        jsbytecode           *pc;
> +    };
> +
> +    struct LocationValue {
> +        LocationValue() : source(nullptr), line(0), column(0) { };

Ditto.

Comment 7

[Shu-yu Guo [:shu]]

It also seems to me that if your Lookup struct can be live across a can-GC call, maybe it needs an on-stack analogue with a Rooted?

Comment 8

[Terrence Cole [:terrence]]

Comment on attachment 8440974 [details] [diff] [review]
memoize-pc-to-line-number.patch

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

Looks fine other than the GC concerns. Should be easy to fix, but I'd like to take a second look after. Sorry this stuff is so complicated.

::: js/src/vm/SavedStacks.cpp
@@ +448,2 @@
>          return false;
> +    RootedFunction callee(cx, thisFrame.maybeCallee());

It doesn't look like callee needs to be rooted here. Please remove and fire off an Hs build on try to verify once you've applied the other comments.

::: js/src/vm/SavedStacks.h
@@ +94,5 @@
> +    size_t                      line;
> +    size_t                      column;
> +    PreBarriered<JSAtom*>       functionDisplayName;
> +    RelocatablePtr<SavedFrame*> parent;
> +    JSPrincipals                *principals;

Lookup values are not stored in the table and should generally only be live across hashtable calls, which should not GC. Just make all of these fields raw pointers.

@@ +144,5 @@
> +
> +    struct PCKey {
> +        PCKey(JSScript *script, jsbytecode *pc) : script(script), pc(pc) { };
> +
> +        RelocatablePtrScript script;

This is backwards -- keys normally need to use PreBarriered and the value needs to use RelocatablePtr. This should be PreBarrieredScript.

@@ +156,5 @@
> +              line(line),
> +              column(column)
> +        { };
> +
> +        PreBarriered<JSAtom*> source;

For normal tables this would be RelocatablePtrAtom. In this case, however -- since the table is weak -- you need to make this ReadBarrieredAtom.

Explanation:
Let's say you are running in js code between incremental slices after marking is finished and before sweeping with |source| dead, but still in the table. Then some code does a lookup on this table, grabbing the LocationValue. While using the |source|, another gc slice happens, sweeping |source| since it is unmarked. You will crash after resuming because |source| is now dead. Using a ReadBarriered here will cause |source| to be marked when you get it out of the table.

Comment 9

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: memoize-pc-to-line-number.patch

Fixed up based on review comments.

New try push: https://tbpl.mozilla.org/?tree=Try&rev=18e229425154

Comment 10

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/466812b83481

Comment 11

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/466812b83481