py: Turn down amount of RAM parser and compiler use.

There are 2 locations in parser, and 1 in compiler, where memory
allocation is not precise.  In the parser it's the rule stack and result
stack, in the compiler it's the array for the identifiers in the current
scope.  All other mallocs are exact (ie they don't allocate more than is
needed).

This patch adds tuning options (MP_ALLOC_*) to mpconfig.h for these 3
inexact allocations.

The inexact allocations in the parser should actually be close to
logarithmic: you need an exponentially larger script (absent pathological
cases) to use up more room on the rule and result stacks.  As such, the
default allocation policy for these is now to start with a modest sized
stack, but grow only in small increments.

For the identifier arrays in the compiler, these now start out quite
small (4 entries, since most functions don't have that many ids), and
grow incrementally by 6 (since if you have more ids than 4, you probably
have quite a few more, but it wouldn't be exponentially more).

Partially addresses issue #560.

3 files changed, 42 insertions, 9 deletions

diff --git a/py/mpconfig.h b/py/mpconfig.h
index 78147609ca..435140dc72 100644
--- a/py/mpconfig.h
+++ b/py/mpconfig.h
@@ -34,6 +34,39 @@
 // values below.
 
 /*****************************************************************************/
+/* Memory allocation policy                                                  */
+
+// Initial amount for parse rule stack
+#ifndef MP_ALLOC_PARSE_RULE_INIT
+#define MP_ALLOC_PARSE_RULE_INIT (64)
+#endif
+
+// Increment for parse rule stack
+#ifndef MP_ALLOC_PARSE_RULE_INC
+#define MP_ALLOC_PARSE_RULE_INC (16)
+#endif
+
+// Initial amount for parse result stack
+#ifndef MP_ALLOC_PARSE_RESULT_INIT
+#define MP_ALLOC_PARSE_RESULT_INIT (32)
+#endif
+
+// Increment for parse result stack
+#ifndef MP_ALLOC_PARSE_RESULT_INC
+#define MP_ALLOC_PARSE_RESULT_INC (16)
+#endif
+
+// Initial amount for ids in a scope
+#ifndef MP_ALLOC_SCOPE_ID_INIT
+#define MP_ALLOC_SCOPE_ID_INIT (4)
+#endif
+
+// Increment for ids in a scope
+#ifndef MP_ALLOC_SCOPE_ID_INC
+#define MP_ALLOC_SCOPE_ID_INC (6)
+#endif
+
+/*****************************************************************************/
 /* Micro Python emitters                                                     */
 
 // Whether to emit CPython byte codes (for debugging/testing)
diff --git a/py/parse.c b/py/parse.c
index 13b137fb34..f512eea3b2 100644
--- a/py/parse.c
+++ b/py/parse.c
@@ -134,13 +134,13 @@ STATIC void push_rule(parser_t *parser, int src_line, const rule_t *rule, int ar
         return;
     }
     if (parser->rule_stack_top >= parser->rule_stack_alloc) {
-        rule_stack_t *rs = m_renew_maybe(rule_stack_t, parser->rule_stack, parser->rule_stack_alloc, parser->rule_stack_alloc * 2);
+        rule_stack_t *rs = m_renew_maybe(rule_stack_t, parser->rule_stack, parser->rule_stack_alloc, parser->rule_stack_alloc + MP_ALLOC_PARSE_RULE_INC);
         if (rs == NULL) {
             memory_error(parser);
             return;
         }
         parser->rule_stack = rs;
-        parser->rule_stack_alloc *= 2;
+        parser->rule_stack_alloc += MP_ALLOC_PARSE_RULE_INC;
     }
     rule_stack_t *rs = &parser->rule_stack[parser->rule_stack_top++];
     rs->src_line = src_line;
@@ -263,13 +263,13 @@ STATIC void push_result_node(parser_t *parser, mp_parse_node_t pn) {
         return;
     }
     if (parser->result_stack_top >= parser->result_stack_alloc) {
-        mp_parse_node_t *pn = m_renew_maybe(mp_parse_node_t, parser->result_stack, parser->result_stack_alloc, parser->result_stack_alloc * 2);
+        mp_parse_node_t *pn = m_renew_maybe(mp_parse_node_t, parser->result_stack, parser->result_stack_alloc, parser->result_stack_alloc + MP_ALLOC_PARSE_RESULT_INC);
         if (pn == NULL) {
             memory_error(parser);
             return;
         }
         parser->result_stack = pn;
-        parser->result_stack_alloc *= 2;
+        parser->result_stack_alloc += MP_ALLOC_PARSE_RESULT_INC;
     }
     parser->result_stack[parser->result_stack_top++] = pn;
 }
@@ -350,11 +350,11 @@ mp_parse_node_t mp_parse(mp_lexer_t *lex, mp_parse_input_kind_t input_kind, mp_p
 
     parser->had_memory_error = false;
 
-    parser->rule_stack_alloc = 64;
+    parser->rule_stack_alloc = MP_ALLOC_PARSE_RULE_INIT;
     parser->rule_stack_top = 0;
     parser->rule_stack = m_new(rule_stack_t, parser->rule_stack_alloc);
 
-    parser->result_stack_alloc = 64;
+    parser->result_stack_alloc = MP_ALLOC_PARSE_RESULT_INIT;
     parser->result_stack_top = 0;
     parser->result_stack = m_new(mp_parse_node_t, parser->result_stack_alloc);
 
diff --git a/py/scope.c b/py/scope.c
index 8d3f7bada2..ab29af78ab 100644
--- a/py/scope.c
+++ b/py/scope.c
@@ -71,7 +71,7 @@ scope_t *scope_new(scope_kind_t kind, mp_parse_node_t pn, qstr source_file, uint
     }
     scope->raw_code = mp_emit_glue_new_raw_code();
     scope->emit_options = emit_options;
-    scope->id_info_alloc = 8;
+    scope->id_info_alloc = MP_ALLOC_SCOPE_ID_INIT;
     scope->id_info = m_new(id_info_t, scope->id_info_alloc);
 
     return scope;
@@ -92,8 +92,8 @@ id_info_t *scope_find_or_add_id(scope_t *scope, qstr qstr, bool *added) {
 
     // make sure we have enough memory
     if (scope->id_info_len >= scope->id_info_alloc) {
-        scope->id_info = m_renew(id_info_t, scope->id_info, scope->id_info_alloc, scope->id_info_alloc * 2);
-        scope->id_info_alloc *= 2;
+        scope->id_info = m_renew(id_info_t, scope->id_info, scope->id_info_alloc, scope->id_info_alloc + MP_ALLOC_SCOPE_ID_INC);
+        scope->id_info_alloc += MP_ALLOC_SCOPE_ID_INC;
     }
 
     // add new id to end of array of all ids; this seems to match CPython