880538 - OdinMonkey: avoid parse node memory spike by LifoAlloc::release()ing after every function

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Luke Wagner [:luke]]

One way to fix the parse-time memory spike associated with asm.js code is to not create parse nodes at all by writing an asm.js parser (bug 854061) which would also improve load time.  However, we'd probably like to fix the memory spike problem sooner than it looks like bug 854061 would be ready.  So, a shorter-term fix is to LifoAlloc::mark/release before and after parsing every function (which would limit the total parse node memory consumed to the size of a single function).  I haven't thought through all the ramifications of this (have to audit for any dangling pointers into these released nodes), but I think it'd be relatively straightforward.

Comment 1

[Luke Wagner [:luke]]

Attachment: Part 1: change Odin to make a single pass over the parse tree

Comment 2

[Luke Wagner [:luke]]

Attachment: Part 1: change Odin to make a single pass over the parse tree

Rebased on top of bug 883175 (which ended up simplifying all the maybeReturnType stuff; now a Signature always has a return type).

Comment 3

[Luke Wagner [:luke]]

Woohoo, it works!  Patches soon after I tidy up.

On Epic Citadel, ParseNode memory usage drops from 881MB to 6MB.  It also saves 1.5s total parse+compile time (on my slow MBP).

Note: with these patches, parse time is now included in the time reported by "Successfully compiled asm.js", so the reported times actually go up; don't be fooled.

Comment 4

[Alon Zakai (:azakai)]

(In reply to Luke Wagner [:luke] from comment #3)
> Woohoo, it works!  Patches soon after I tidy up.
> 
> On Epic Citadel, ParseNode memory usage drops from 881MB to 6MB.  It also
> saves 1.5s total parse+compile time (on my slow MBP).
> 

\o/

Comment 5

[Luke Wagner [:luke]]

Attachment: combined patch for fuzzing v.1 (applies to cset 0252b45289f5)

This is a combined patch that applies to trunk (0252b45289f5).  I'd really appreciate fuzzing (iiuc, there are now 3 :).  The patch touches the frontend and thus must contain a bug involving the simultaneous use of arrow functions, with, generator expressions and lazy parsing.

Comment 6

[Luke Wagner [:luke]]

Attachment: Part 0: generalize how we reparse for strict mode

If asm.js validation fails, we have to backup and reparse, just like we already do when we discover "use strict".  This patch wraps 'strict' in a 'Directives' struct that preserves existing behavior so that the last patch can simply add a second 'bool asmJS' field to Directive.

Comment 7

[Luke Wagner [:luke]]

Attachment: Part 1: change Odin to make a single pass over the parse tree (updated)

This is just a rebase of the already-posted patch.

Comment 8

[Luke Wagner [:luke]]

Attachment: Part 2: set pn->pn_funbox immediately

No reason that I can see to wait to set it at the end and setting it early simplifies the last patch.

Comment 9

[Luke Wagner [:luke]]

Attachment: Part 3: store a pointer from a ParseContext to it's PNK_FUNCTION ParseNode

This patch adds ParseContext::maybeFunction which is a pointer to the PNK_FUNCTION ParseNode (if pc->sc->isFunctionBox()).  Otherwise there is no good way to get to your enclosing PNK_FUNCTION when you are parsing a statement in that function (as we are in maybeParseDirective in the last patch).

Comment 10

[Luke Wagner [:luke]]

Attachment: Part 4: move the "hasDestructuringArgs" flag into the FunctionBox

This patch moves the local bool var 'destructuringArg' into FunctionBox so that we can tell, after Parser::functionArguments(), whether we have destructuring arguments.  Before the last patch, we trigger a validation error because of the extra parse nodes before "use asm" that get inserted; however these nodes are only inserted after parsing the body completes so that are not available to CompileAsmJS and we need the flag.

Comment 11

[Luke Wagner [:luke]]

Attachment: Part 5: LifoAlloc::release after parsing every function

This patch does the deed; nothing too tricky given all the preceding patches.  I'd appreciate careful consideration of anywhere I explicitly touch the tokenStream.

Comment 12

[Luke Wagner [:luke]]

Attachment: Part 1b: avoid creating an IonContext in MacroAssembler

Oops, missed this one.  If there isn't already an active IonContext, MacroAssembler()'s constructor will create one and use cx->tempLifoAlloc() as the LifoAlloc.  This interacts poorly with parsing which also uses cx->tempLifoAlloc.  This patch adds a new constructor for MacroAssembler that never creates an IonContext.  This is nice since we get a clean JS_ASSERT anywhere where we depend on an IonContext where we haven't explicitly pushed one in AsmJS.cpp (there was one, which this patch fixes).

Comment 13

[Luke Wagner [:luke]]

Green on try:
https://tbpl.mozilla.org/?tree=Try&rev=0faeb5cea7ea

Comment 14

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Attachment: stacks

(In reply to Luke Wagner [:luke] from comment #5)
> Created attachment 769156 [details] [diff] [review]
> combined patch for fuzzing v.1 (applies to cset 0252b45289f5)

parse("\
    ({\
        r: function() {}\
        (function(){\
        \"use asm\";\
        function f() {}\
        return f\
")

Crash [@ ModuleCompiler::staticallyLink]

parse("\
    function e() {\
        \"use asm\";\
        return\
        )\
")

Crash [@ CheckModule]

tested on 64-bit deterministic threadsafe debug shell, patched on top of m-c rev 942686767e5e.

Comment 15

[Luke Wagner [:luke]]

Attachment: Part 5: LifoAlloc::release after parsing every function (v.2)

Oops, bug involving shell-only Parse() method.

Comment 16

[Luke Wagner [:luke]]

Attachment: combined patch for fuzzing v.2 (applies to cset 0252b45289f5)

Comment 17

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Attachment: stack

Function("\
    \"use asm\";\
    var z=-2w;\
")

Crash [@ js::frontend::TokenStream::getTokenInternal]

Comment 18

[Luke Wagner [:luke]]

Attachment: Part 5: LifoAlloc::release after parsing every function (v.3)

Ah hah, the VarStmtIter interface obscured parse errors so getToken was called after an error was thrown.  Added more tests for parse errors.

Comment 19

[Luke Wagner [:luke]]

Attachment: combined patch for fuzzing v.3 (applies to cset 0252b45289f5)

Thanks Gary!

Comment 20

[Christian Holler (:decoder)]

Comment on attachment 769319 [details] [diff] [review]
combined patch for fuzzing v.3 (applies to cset 0252b45289f5)

Tests work with 32 bit debug shells, no options required:

g = { z: function() { "use asm"; function g() {} function g () {} } }

Assertion failure: !bound(), at ../ion/shared/Assembler-shared.h:234


(function() {
  'use asm';
  function _main() {
    var label=0;
      switch (label | 0) {
       case 1:
       case (100000000):
  }
})()

Assertion failure: curBlock_ == __null, at js/src/ion/AsmJS.cpp:1749



Overall it's very important to get more ASM.js tests into our testsuite. The existing jit-tests are very valuable, with the big exception of the initial test set that uses eval/strings for everything. These tests are completely useless for LangFuzz. So basically the LangFuzz fuzzing is solely relying on ASM.js regression tests being checked in.

Comment 21

[Luke Wagner [:luke]]

Attachment: combined patch for fuzzing v.4 (applied to cset 95e83b0f7cb2)

Thanks!  One is an assertion that incorrectly fires on OOM, the other was a preexisting bug covered by the old parsing scheme.

Comment 22

[Luke Wagner [:luke]]

Attachment: Part 5: LifoAlloc::release after parsing every function (v.3)

Now explicitly check for duplicates instead of relying on parser.

Comment 23

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Comment on attachment 769912 [details] [diff] [review]
combined patch for fuzzing v.4 (applied to cset 95e83b0f7cb2)

Didn't find any more problems related to this patch after a round of overnight fuzzing this time.

Comment 24

[Christian Holler (:decoder)]

Comment on attachment 769912 [details] [diff] [review]
combined patch for fuzzing v.4 (applied to cset 95e83b0f7cb2)

Same here :)

Comment 25

[Nicholas Nethercote [inactive]]

Luke: how Odin-specific is this?

Comment 26

[Luke Wagner [:luke]]

Totally (hence the "OdinMonkey:" prefix).  Good news though: in the non-Odin case, we already (as of bug 678037) avoid the memory spike since all the top-level functions will get a syntax-only parse (which doesn't create parse nodes).

Comment 27

[Luke Wagner [:luke]]

Thanks Gary and Christian!

Comment 28

[Sean Stangl [:sstangl]]

Comment on attachment 769192 [details] [diff] [review]
Part 1b: avoid creating an IonContext in MacroAssembler

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

::: js/src/ion/IonMacroAssembler.h
@@ +108,5 @@
>          m_buffer.id = GetIonContext()->getNextAssemblerId();
>  #endif
>      }
>  
> +    // asm.js compilation handles it's own IonContet-pushing

"pushes its own IonContext"

Comment 29

[Douglas Crosher [:dougc]]

Attachment: Rebase WIP

FWIW an attempt to rebase.  There are a few clashes with bug 885758 that could use some more attention.  An attempt has been made to get the 'perf' support rebased, and I'll keep developing and testing this.

Comment 30

[Douglas Crosher [:dougc]]

Attachment: Rebase, WIP.

Some of the issues encountered appear to be general regressions from other work and have been moved to separate bugs: Bug 893314, Bug 893315, and Bug 893317. This rebased patch assumes the patches from these other bugs have been applied. It still seems to work on x64, and passes all the tbpl jit-tests.

Comment 31

[Douglas Crosher [:dougc]]

Attachment: Minor include file fixes.

Fix some missing include files that are needed for a non-debug build.

Now also tested on ARM B2G and Firefox-for-Android and all is well so far.

Would be curious to know how to measure the difference this makes to the memory allocation?

Comment 32

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

For either of them, I usually just run ps (or top -m 5 or something) every half second or so via adb shell and watch the numbers.  At one point I had a script that would graph them, but have no idea where it went..

Comment 33

[Jason Orendorff [:jorendorff]]

Comment on attachment 769164 [details] [diff] [review]
Part 0: generalize how we reparse for strict mode

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

This is all a bit more of a maze than I'd like, but I don't see a more localized way to do it.

Someday soon I definitely want to collect all the function-parsing code in a contiguous block of craziness at the end of Parser.cpp and go through it with a red pencil (or machete).

::: js/src/frontend/Parser-inl.h
@@ +41,5 @@
>  }
>  
>  template <typename ParseHandler>
>  inline
> +ParseContext<ParseHandler>::ParseContext(Parser<ParseHandler> *prs, GenericParseContext *parent, 

trailing whitespace on this line

::: js/src/frontend/Parser.cpp
@@ +2104,5 @@
>  template <>
>  bool
>  Parser<SyntaxParseHandler>::functionArgsAndBody(Node pn, HandleFunction fun,
>                                                  FunctionType type, FunctionSyntaxKind kind,
> +                                                Directives directives,

Style nit: In the places where this is a parameter, it could be "inheritedDirectives", especially if the idea is that "use asm" is not inherited.

::: js/src/frontend/Parser.h
@@ +205,5 @@
> +    // In a function context, points to a Directive struct that can be updated
> +    // to reflect new directives encountered in the Directive Prologue that
> +    // require reparsing the function. In global/module/generator-tail
> +    // contexts, where there is no DirectivePrologue or need to reparse, this
> +    // pointer may be NULL;

Funny punctuation at the end there.

The comment is a bit misleading. Global contexts can have a DirectivePrologue, we just don't reparse for them.

::: js/src/frontend/SharedContext.h
@@ +152,5 @@
> +    void setStrict() { strict_ = true; }
> +    bool strict() const { return strict_; }
> +
> +    Directives &operator=(Directives rhs) {
> +        // Assignment must be monotonic to prevent reparsing iloops

Mmm, this is a kind of weird place to assert this. It could be checked in the loop itself instead, if you agree. No big deal either way.

Comment 34

[Luke Wagner [:luke]]

Comment on attachment 769165 [details] [diff] [review]
Part 1: change Odin to make a single pass over the parse tree (updated)

Benjamin, I think you have the most familiarity with the AsmJS code atm.  Jason is pretty busy with ES work, so could you please review this?  I'm sorry the patch is kinda big, but logically the change is pretty simple: we stop storing ParseNode* to function's we've already changing how we lookup and record function signatures.

Comment 35

[Luke Wagner [:luke]]

Part 0 (leave open):
https://hg.mozilla.org/integration/mozilla-inbound/rev/d9a84be1a35c

Comment 36

[Brian Hackett [Laid off!]]

Comment on attachment 769169 [details] [diff] [review]
Part 2: set pn->pn_funbox immediately

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

::: js/src/frontend/Parser.cpp
@@ +534,5 @@
>          return NULL;
>      }
>  
>      traceListHead = funbox;
> +    if (fn != ParseHandler::null())

Will just 'if (fn)' work here?

Comment 37

[Luke Wagner [:luke]]

Attachment: Part 5: LifoAlloc::release after parsing every function

Oops, wrong patch attached.

Comment 38

[Luke Wagner [:luke]]

Attachment: Part 1: change Odin to make a single pass over the parse tree (rebased)

Rebased to tip.

Comment 39

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/d9a84be1a35c

Comment 40

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 776561 [details] [diff] [review]
Part 1: change Odin to make a single pass over the parse tree (rebased)

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

Looks good to me! r+ with the TryEnablingFunction fix.

::: js/src/ion/AsmJS.cpp
@@ +35,5 @@
> +using namespace mozilla;
> +static const size_t LIFO_ALLOC_PRIMARY_CHUNK_SIZE = 1 << 12;
> +
> +using namespace js;
> +using namespace js::frontend;

Several |using namespace| seem to be written twice: js, js::frontend, mozilla.

@@ +1467,5 @@
>  
>          unsigned lineno = 0U, columnIndex = 0U;
>          tokenStream_.srcCoords.lineNumAndColumnIndex(func.fn()->pn_pos.begin, &lineno, &columnIndex);
>  
>          unsigned startCodeOffset = func.codeLabel()->offset();

If I understand correctly the change just above, changes are required here and in trackPerfProfiledBlocks too.

@@ +1628,5 @@
>  {
>    public:
>      struct Local
>      {
>          enum Which { Var, Arg } which;

Looks like this enum is not used any more.

@@ +1644,5 @@
>      typedef Vector<ParseNode*, 4> NodeStack;
>  
>      ModuleCompiler &       m_;
> +    LifoAlloc &            lifo_;
> +    ParseNode              *fn_;

Nit: |ParseNode * [spaces] fn_;| would be more consistent with the declarations above and below.

@@ +3424,5 @@
>      return true;
>  }
>  
>  static bool
> +CheckSignatureAgainstExisting(ModuleCompiler &m, ParseNode *usepn, const Signature &sig,

It's kind of sad that we cannot reuse == here without losing all the error reporting.

@@ +5447,1 @@
>          return true;

Shouldn't we still test |if (!script)| here?
Currently, this |return true| isn't bound to any condition, so Ion won't ever be enabled.

::: js/src/ion/AsmJS.h
@@ +144,5 @@
>      ion::LIRGraph *lir;     // Passed from worker to main thread.
>      unsigned compileTime;
>  
>      AsmJSParallelTask(size_t defaultChunkSize)
> +      : lifo(defaultChunkSize), mir(NULL), lir(NULL), compileTime(0)

Could you initialize func to NULL too, please?

::: js/src/ion/AsmJSModule.h
@@ +496,2 @@
>      bool addExit(unsigned ffiIndex, unsigned *exitIndex) {
> +        if (SIZE_MAX - funcPtrTableAndExitBytes_ < sizeof(void*))

Just to be consistent with the addition below, shouldn't it be sizeof(ExitDatum) here?

Comment 41

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 776560 [details] [diff] [review]
Part 5: LifoAlloc::release after parsing every function

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

Nice, looks good to me!

::: js/src/frontend/BytecodeEmitter.cpp
@@ +4523,1 @@
>                 .setForEval(false)

Nit: alignment is broken here.

::: js/src/ion/AsmJS.cpp
@@ +2456,5 @@
>      }
>  
>      /*************************************************************************/
>  
> +    MIRGenerator *extractMIR()

I like this name better too.

::: js/src/ion/AsmJS.h
@@ +41,2 @@
>  
> +// Implements an asm.js module function that has been successfully validated.

The previous comment seemed more explicit, IMHO.

Comment 42

[Luke Wagner [:luke]]

(In reply to Benjamin Bouvier [:bbouvier] from comment #40)
Whoa, nice find in TryEnablingIon!  That is what happens when you hg pull --rebase :)  Also, really nice comments overall, thanks!

Comment 43

[Luke Wagner [:luke]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/63d537758124
https://hg.mozilla.org/integration/mozilla-inbound/rev/4ae936372107
https://hg.mozilla.org/integration/mozilla-inbound/rev/d112cd2746c4
https://hg.mozilla.org/integration/mozilla-inbound/rev/ae3f61b13984
https://hg.mozilla.org/integration/mozilla-inbound/rev/eea0b122e8b5
https://hg.mozilla.org/integration/mozilla-inbound/rev/541c383c1698

Comment 44

[Alon Zakai (:azakai)]

Nice speedups on workload0 (pure startup time) on large benchmarks on awfy, http://arewefastyet.com/#machine=11&view=breakdown&suite=asmjs-apps

Happens on odin and non-odin (is that surprising? i thought this was odin-specific).

Comment 45

[Luke Wagner [:luke]]

Yes, that is surprising... I'm guessing there was an issue involving lazy parsing whereby we were either parsing more than once or decompressing multiple times.

Comment 46

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/63d537758124
https://hg.mozilla.org/mozilla-central/rev/4ae936372107
https://hg.mozilla.org/mozilla-central/rev/d112cd2746c4
https://hg.mozilla.org/mozilla-central/rev/ae3f61b13984
https://hg.mozilla.org/mozilla-central/rev/eea0b122e8b5
https://hg.mozilla.org/mozilla-central/rev/541c383c1698

Comment 47

[Eddie Maddox]

(In reply to Ryan VanderMeulen [:RyanVM UTC-4] from comment #46)
> Target Milestone: --- → mozilla25
With Ff24 being an ESR, this means an extra year to realize the
~100 times reduction in that memory usage spike for managed users.

Is it too risky to uplift this now?
Or is there just no interest/awareness?

Thanks,
Eddie Maddox

Comment 48

[lwagner]

I think the patch is way to big and risky to uplift.  Also note that the optimization only applies to asm.js which isn't yet widespread.

Comment 49

[Nicholas Nethercote [inactive]]

I've been using a version of one of the Unreal demos to measure asm.js parsing speed.  I have a 55 MiB file called unreal.data, and then I have unreal.js which is just this:

  parse(readRelativeToScript("unreal.data"));

On my 64-bit desktop, with current mozilla-inbound tip, I see a ParseNode peak of 
1,302,290,432 bytes.

parse() does a full parse, not a "syntax" parse, so I figure that must be the difference between what Luke saw in the browser and what I see in the shell?

Comment 50

[Luke Wagner [:luke]]

Not quite: parse() calls Parser::parse() which isn't a "real" parsing function and, among other things, doesn't create a ScriptSource which ends up completing avoiding the asm.js path (see Parser<FullParseHandler::asmJS).  This ends up being kinda nice since JS_BufferIsCompileableUnit uses Parser::parse() so this avoids compiling asm.js (and emitting the "success" message) twice on the REPL.

(To wit, asm.js aborts the syntax-only parse (for reasoning explaining in Parser<SyntaxParseHandler>::asmJS) so that asm.js compilation always occurs during a full parse.)

Comment 51

[Nicholas Nethercote [inactive]]

If I want to measure the start-up time (parsing, compilation, whatever else) of an asm.js program from the shell, is there a good way to do it?  Would compile() do it?  Alternatively, Marty suggested for the Unreal demo just removing the run() call at the end and then executing it normally.

Likewise, for normal JS code is there a better way to measure parsing time than with parse()?

Comment 52

[Luke Wagner [:luke]]

For asm.js, yeah, I tend to just download the entire file and just run it; it tends to hit a runtime error (for lack of document/window) really quickly.  For non-asm.js, parse() is great.