Compiler is too memory-hungry

[pfalcon]

When working with some code, I regularly check minimum heap required to run it, and so far in all cases saw the pattern that such figure if bound by memory required to finish compilation. Supposedly that can be called intuitively unexpected (because intuition says that memory required for compilations should be linear to program size, while runtime memory can be unbound), would be nice to prune that out. Without redoing analysis I did previously, my suspicion is on exponential container growth policy for internal compiler data structures - exponential with big enough base (2). Arguably, that's bad heuristics for anything "micro" - it essentially says "whatever we have, even more is coming", while "optimistic" policy for micro thing would be "whatever we have, it should end soon" ;-).

So, I propose cutting down exponent base to 1.5 or maybe even 1.25, if not going to fixed-increment policy. And as these choices have known theoretical performance impact, it should be configurable - at least by factoring out a policy as a macro, like

#define ALLOC_SIZE_POLICY(old_size ) (<compute new size here>)

[dpgeorge]

I did the factor of 2 simply because that was the easiest to implement. Certainly it can be tuned now that we have lots of example scripts to test it with.

There are 3 main parts allocating RAM in an unbounded way:

1. Parser stage allocating parse nodes.
2. Compiler allocating on the first pass: scopes and identifier info.
3. Compiler allocating on pass 3: memory for the bytecode (and native code). This is computed exactly in pass 2, so nothing to optimise here.

[dpgeorge]

One thing that could be done to make (compiler) memory allocation exact is to have a new compiler pass at the very start which works out how many scopes and how many ids there are. Thus it allocates only exactly what it needs.

[pfalcon]

I'd say that make sense - we should optimize for run time, and that means having more (sub)passes anyway. Then having extra pass to save on memory alloc sound good too. Unfortunately, I don't understand compiler well enough to do such changes. Do you think you would be interested to do that any time soon?

[dpgeorge]

I need to add another pass for the native emitters (pass 4), so I can add pass 0 to compute memory requirements at the same time. Might be a few days though :)

[dpgeorge]

See patch linked above.

Multiple passes in the compiler won't actually help: each scope is allocated only when needed, and you can't precompute number of ids per scope without keeping a list of them (to tell if you come across a duplicate or new id).

Parser and compiler now used fixed increment, tunable via mpconfigport.h. Defaults seem reasonable and have been very crudly tested against all tests in tests/ directory.

[pfalcon]

Ok, I see effect of it - previously, my asyncio_micro http server example could be started up only in 53000 bytes heap, now can be in 48500. Dunno why it's take so huge still - that's why I think of #533 (comment) .

And thanks for so promptly looking into this - didn't have intention to drag you away from stmhal and documenting work, just wanted to plan for "next targets". And after recent milestones, it itches to do some optimization ;-).

Closing this otherwise.

[dpgeorge]

Does your asyncio_micro example have a lot of doc strings? All strings in the source scripts are interned, even doc strings, and even when MICROPY_ENABLE_DOC_STRING is 0.

[pfalcon]

Good hint, I thought we've done with docstring. My stuff includes heapq.py from mainline, which has few K's of docstrings. So, is string interning happens on lexer level or something? Would it be too much work to postpone it until compiler? Well, I guess even parser could have adhoc rule to just throw away first string a module and in function body...

[dpgeorge]

is string interning happens on lexer level

No, on the parser level. It needs to convert to a qstr so that it can stuff it into a parse node pointer. Alternative would be to add a level of indirection for strings, and put them in a structure. This means all strings are wrapped in a heap-allocated data structure.

Another alternative would be for the parser to ignore all statements that consisted of just a string. This might actually be rather easy to implement, and would be clean and have no loss of generality.

[dpgeorge]

Of course, you still allocate the memory in the lexer's vstr to hold the parsed string, but that's unavoidable.

[pfalcon]

Another alternative would be for the parser to ignore all statements that consisted of just a string.

Yeah, good idea!

Of course, you still allocate the memory in the lexer's vstr to hold the parsed string

Sure, but those a deallocated explicitly, right?

[dpgeorge]

Of course, you still allocate the memory in the lexer's vstr to hold the parsed string

Sure, but those a deallocated explicitly, right?

Yes. And the same vstr memory is used for everything that that instance of the lexer tokenises.

[dpgeorge]

Grrr: there is a very easy way for the parser to ignore lonely constants (eg doc strings), but it can't be applied because the parser must know the scope context. When in module scope, lonely constants must remain (eg, at REPL, typing "abc" should print the string!).

Making parser know the scope is non-trivial.

[pfalcon]

@dpgeorge , what about just global flag in_repl? If it's false, throw away statement-level string literals, otherwise, process. That will let docstrings sneak in to repl-defined functions, but should be ok ;-).