[Bug c++/80290] [6/7/8 Regression] g++ uses unreasonable amount of memory compiling nested string maps

[aoliva at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80290

--- Comment #21 from Alexandre Oliva <aoliva at gcc dot gnu.org> ---
Author: aoliva
Date: Wed Apr 18 05:17:26 2018
New Revision: 259457

URL: https://gcc.gnu.org/viewcvs?rev=259457&root=gcc&view=rev
Log:
[PR c++/80290] recycle tinst garbage sooner

tinst_level objects are created during template instantiation, and
they're most often quite short-lived, but since there's no intervening
garbage collection, they accumulate throughout the pass while most by
far could be recycled after a short while.  The original testcase in
PR80290, for example, creates almost 55 million tinst_level objects,
all but 10 thousand of them without intervening GC, but we don't need
more than 284 of them live at a time.

Furthermore, in many cases, TREE_LIST objects are created to stand for
the decl in tinst_level.  In most cases, those can be recycled as soon
as the tinst_level object is recycled; in some relatively common
cases, they are modified and reused in up to 3 tinst_level objects.
In the same testcase, TREE_LISTs are used in all but 3 thousand of the
tinst_level objects, and we don't need more than 89 tinst_level
objects with TREE_LISTs live at a time.  Furthermore, all but 2
thousand of those are created without intervening GC.

This patch arranges for tinst_level objects to be refcounted (I've
seen as many as 20 live references to a single tinst_level object in
my testing), and for pending_template, tinst_level and TREE_LIST
objects that can be recycled to be added to freelists; that's much
faster than ggc_free()ing them and reallocating them shortly
thereafter.  In fact, the introduction of such freelists is what makes
this entire patch lighter-weight, when it comes to memory use, and
faster.  With refcounting alone, the total memory footprint was still
about the same, and we spent more time.

In order to further reduce memory use, I've arranged for us to create
TREE_LISTs lazily, only at points that really need them (when printing
error messages).  This grows tinst_level by an additional pointer, but
since a TREE_LIST holds a lot more than an extra pointer, and
tinst_levels with TREE_LISTs used to be allocated tens of thousands of
times more often than plain decl ones, we still save memory overall.

I was still not quite happy about growing memory use in cases that
used template classes but not template overload resolution, so I
changed the type of the errors field to unsigned short, from int.
With that change, in_system_header_p and refcount move into the same
word or half-word that used to hold errors, releasing a full word,
bringing tinst_level back to its original size, now without any
padding.

The errors field is only used to test whether we've had any errors
since the expansion of some template, to skip the expansion of further
templates.  If we get 2^16 errors or more, it is probably reasonable
to refrain from expanding further templates, even if we would expand
them before this change.

With these changes, compile time for the original testcase at -O0,
with default checking enabled, is cut down by some 3.7%, total GCable
memory allocation is cut down by almost 20%, and total memory use (as
reported by GNU time as maxresident) is cut down by slightly over 15%.


for  gcc/cp/ChangeLog

        PR c++/80290
        * cp-tree.h (struct tinst_level): Split decl into tldcl and
        targs.  Add private split_list_p, tree_list_p, and not_list_p
        inline const predicates; to_list private member function
        declaration; free public member function declaration; list_p,
        get_node and maybe_get_node accessors, and refcount data
        member.  Narrow errors to unsigned short.
        * error.c (print_instantiation_full_context): Use new
        accessors.
        (print_instantiation_partial_context_line): Likewise.  Drop
        const from tinst_level-typed parameter.
        * mangle.c (mangle_decl_string): Likewise.
        * pt.c (freelist): New template class.
        (tree_list_freelist_head): New var.
        (tree_list_freelist): New fn, along with specializations.
        (tinst_level_freelist_head): New var.
        (pending_template_freelist_head): Likewise.
        (tinst_level_freelist, pending_template_freelist): New fns.
        (tinst_level::to_list, tinst_level::free): Define.
        (inc_refcount_use, dec_refcount_use): New fns for tinst_level.
        (set_refcount_ptr): New template fn.
        (add_pending_template): Adjust for refcounting, freelists and
        new accessors.
        (neglectable_inst_p): Take a NULL d as a non-DECL.
        (limit_bad_template_recursion): Use new accessors.
        (push_tinst_level): New overload to create the list.
        (push_tinst_level_loc): Make it static, split decl into two
        args, adjust tests and initialization to cope with split
        lists, use freelist, adjust for refcounting.
        (push_tinst_level_loc): New wrapper with the old interface.
        (pop_tinst_level): Adjust for refcounting.
        (record_last_problematic_instantiation): Likewise.
        (reopen_tinst_level): Likewise.  Use new accessors.
        (instantiate_alias_template): Adjust for split list.
        (fn_type_unification): Likewise.
        (get_partial_spec_bindings): Likewise.
        (instantiate_pending_templates): Use new accessors.  Adjust
        for refcount.  Release pending_template to freelist.
        (instantiating_current_function_p): Use new accessors.

Modified:
    trunk/gcc/cp/ChangeLog
    trunk/gcc/cp/cp-tree.h
    trunk/gcc/cp/error.c
    trunk/gcc/cp/mangle.c
    trunk/gcc/cp/pt.c