From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 43185 invoked by alias); 29 May 2018 20:25:44 -0000 Mailing-List: contact fortran-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Post: List-Help: , Sender: fortran-owner@gcc.gnu.org Received: (qmail 31541 invoked by uid 89); 29 May 2018 20:25:07 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-11.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE,SPF_PASS,TIME_LIMIT_EXCEEDED autolearn=unavailable version=3.3.2 spammy=UD:contact.html, contacthtml, contact.html, sk:userso X-HELO: mail-pg0-f52.google.com Received: from mail-pg0-f52.google.com (HELO mail-pg0-f52.google.com) (74.125.83.52) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 29 May 2018 20:24:38 +0000 Received: by mail-pg0-f52.google.com with SMTP id m5-v6so2696886pgd.3 for ; Tue, 29 May 2018 13:24:08 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:organization :user-agent:in-reply-to:references:mime-version :content-transfer-encoding; bh=Yz9VrCr/ByWcg/ZnPkbONqNA+9+7luTVzIoAtL/fkSM=; b=XuIGg6f1d4HUMMqmCECUKgqgFPEQo+F/6SW6ZiurBGwmFx6yX67yFEdPZLdtQNTgC3 D4a+WMEqCN2+470TYnvQV+XqegrrFKmBUQ6jsRHEiUpjSu8RdgJ/U/xMurmeHPqb25sg 2kfpNyQaSO1xjFEBHs4nlJ2viF6A9JAYE+mISrEPn5hIkIWQGnBgz5XqqijW/O5waVLl BRHGez9JhpasT6ZX51oVnJj3hkzNbb/V2N+KIhHTfg2LMLR/4BCnhJzyF1bkCwAL1ozA 54b3KxzJjqsFLr5a9pkLX2CreW0Tdb3VC04Cqf2v9ybD93bnwLQlPrCzBElDEIwca/1f ZKvw== X-Gm-Message-State: ALKqPwfQSxc5SWAXDFQM2HHH+1wLs61VP/0J7omeJ4u3JaMOFj/z+m9C jMBJIcLZ+xw7QJ1sXadV/14QF9tU X-Google-Smtp-Source: AB8JxZp3OIaH/rHsRYles2uS47T3tpUmrv9hXAFgj8zPOuM83qZZ0hNEHrMieR3RH/N5USagxE3yWw== X-Received: by 2002:a63:9c01:: with SMTP id f1-v6mr15354399pge.223.1527625446863; Tue, 29 May 2018 13:24:06 -0700 (PDT) Received: from andrew-precision-3520.localnet (pool-239.obs.carnegiescience.edu. [192.91.178.239]) by smtp.gmail.com with ESMTPSA id e87-v6sm83306269pfl.65.2018.05.29.13.24.05 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 29 May 2018 13:24:05 -0700 (PDT) From: Andrew Benson To: Richard Biener Cc: "fortran@gcc.gnu.org" Subject: Re: Optimization of add_dt_to_dt_list() in resolve.c Date: Tue, 29 May 2018 20:25:00 -0000 Message-ID: <2946507.05iJNWrpSJ@andrew-precision-3520> User-Agent: KMail/5.2.3 (Linux/4.4.0-124-generic; KDE/5.36.0; x86_64; ; ) In-Reply-To: References: <6944935.KTWIneVxun@andrew-precision-3520> <4775872.iWz7lGoeLh@andrew-precision-3520> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="nextPart3108035.G46GXl6ko6" Content-Transfer-Encoding: 7Bit X-IsSubscribed: yes X-SW-Source: 2018-05/txt/msg00122.txt.bz2 This is a multi-part message in MIME format. --nextPart3108035.G46GXl6ko6 Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="us-ascii" Content-length: 4317 Yes - definitely possible to remove gfc_dt_list entirely - new patch is attached. Thanks, Andrew On Monday, May 28, 2018 11:54:41 AM PDT Richard Biener wrote: > On Fri, May 25, 2018 at 11:54 PM Andrew Benson > wrote: > > Richard: > > > > Thanks for the suggestion. I changed my patch (new version attached) so > > that > > > there's a *dt_next in gfc_symbol, which is now used to construct the > > (circular) linked list. There were a couple places where I had to change > > the > > > order in which clean up of symbols and derived type lists were done - > > it's now > > > necessary to free the derived type list before its associated symbols > > (since > > > the symbols carry the links for the derived type list). > > Hmm, it still has the indirection via gfc_dt_list. I think it should be > possible > to do away with gfc_dt_list objects alltogether by no doing > sym->dt_next->derived > but sym->derived thus > > @@ -1611,6 +1611,9 @@ typedef struct gfc_symbol > > /* Link to corresponding association-list if this is an associate name. > */ > struct gfc_association_list *assoc; > + > + /* Link to next entry in derived type list */ > + gfc_symbol *dt_next; > } > gfc_symbol; > > that means for example gfc_free_dt_list can be simply removed. The > gfc_derived_types global would then point to the first derived type > directly. > > Richard. > > > This passes "make check-fortran" and seems to retain the speed-up from my > > original patch. > > > > Thanks, > > Andrew > > > > On Friday, May 25, 2018 9:06:22 AM PDT Richard Biener wrote: > > > On Fri, May 25, 2018 at 12:53 AM Andrew Benson < > > abenson@carnegiescience.edu> > > > > wrote: > > > > I've been attempting to track down some of the causes of very long > > compile > > > > > times for files which use modules that contain a large number of > > symbols. > > > > The > > > > > > > worst case offender in my code takes around 12 minutes to compile. > > > > > > > > After profiling f951 for this source file it turns out that the > > majority > > > > of the > > > > > > > time is spent in add_dt_to_dt_list() in resolve.c. In cases where the > > > > > > number > > > > > > > of symbols imported becomes very large (~10,000 in some cases in this > > > > > > code), > > > > > > > the O(N) search in this function becomes inefficient. > > > > > > > > A simple optimization for this problem seems to be to just have the > > > > > > gfc_symbol > > > > > > > struct include a pointer back to the corresponding entry in the > > > > gfc_derived_types list. It's then fast to check if a symbol is > > already on > > > > that > > > > > > > list by checking if this pointer is non-null. (It could just as > > easily be > > > > an > > > > > > > int in gfc_symbol which indicates if the symbol is already added to > > the > > > > list - > > > > > > > I don't know if having a pointer to the list entry is useful for any > > other > > > > > reason.) > > > > > > > > With this change in place compile times are much faster - my worst > > case > > > > > offender now takes just under 1 minute to compile. > > > > > > > > My patch is attached. I freely admit that I have only a very shallow > > > > understanding of the inner workings of the compiler, so I would not be > > > > surprised if there are good reasons not to do this. I did "make > > > > > > check-fortran" > > > > > > > and did not see any failures. If any one wants to try this out and/or > > > > > > provide > > > > > > > any feedback I'd be happy to hear it. > > > > > > It looks like it would be cheaper to simply embed gtc_dt_list *next in > > > gfc_symbol? > > > (in case a gfc_symbol can be only on one gfc_dt_list which your patch > > > assumes as well) > > > > > > Richard. > > > > > > > Thanks, > > > > Andrew > > > > > > > > -- > > > > > * Andrew Benson: > http://users.obs.carnegiescience.edu/abenson/contact.html > > > > > * Galacticus: https://bitbucket.org/abensonca/galacticus > > > > -- > > > > * Andrew Benson: http://users.obs.carnegiescience.edu/abenson/contact.html > > > > * Galacticus: https://bitbucket.org/abensonca/galacticus -- * Andrew Benson: http://users.obs.carnegiescience.edu/abenson/contact.html * Galacticus: https://bitbucket.org/abensonca/galacticus --nextPart3108035.G46GXl6ko6 Content-Disposition: attachment; filename="patch.diff" Content-Transfer-Encoding: 7Bit Content-Type: text/x-patch; charset="UTF-8"; name="patch.diff" Content-length: 8423 Index: gcc/fortran/gfortran.h =================================================================== --- gcc/fortran/gfortran.h (revision 260682) +++ gcc/fortran/gfortran.h (working copy) @@ -1611,6 +1611,9 @@ typedef struct gfc_symbol /* Link to corresponding association-list if this is an associate name. */ struct gfc_association_list *assoc; + + /* Link to next entry in derived type list */ + struct gfc_symbol *dt_next; } gfc_symbol; @@ -1712,19 +1715,9 @@ typedef struct gfc_symtree } gfc_symtree; -/* A linked list of derived types in the namespace. */ -typedef struct gfc_dt_list -{ - struct gfc_symbol *derived; - struct gfc_dt_list *next; -} -gfc_dt_list; +/* A list of all derived types. */ +extern gfc_symbol *gfc_derived_types; -#define gfc_get_dt_list() XCNEW (gfc_dt_list) - - /* A list of all derived types. */ - extern gfc_dt_list *gfc_derived_types; - typedef struct gfc_oacc_routine_name { struct gfc_symbol *sym; @@ -1809,7 +1802,7 @@ typedef struct gfc_namespace gfc_charlen *cl_list; - gfc_dt_list *derived_types; + gfc_symbol *derived_types; int save_all, seen_save, seen_implicit_none; Index: gcc/fortran/parse.c =================================================================== --- gcc/fortran/parse.c (revision 260682) +++ gcc/fortran/parse.c (working copy) @@ -6047,7 +6047,7 @@ add_global_program (void) static void resolve_all_program_units (gfc_namespace *gfc_global_ns_list) { - gfc_free_dt_list (); + gfc_derived_types = NULL; gfc_current_ns = gfc_global_ns_list; for (; gfc_current_ns; gfc_current_ns = gfc_current_ns->sibling) { Index: gcc/fortran/resolve.c =================================================================== --- gcc/fortran/resolve.c (revision 260682) +++ gcc/fortran/resolve.c (working copy) @@ -2504,7 +2504,7 @@ resolve_global_procedure (gfc_symbol *sym, locus * /* Resolve the gsymbol namespace if needed. */ if (!gsym->ns->resolved) { - gfc_dt_list *old_dt_list; + gfc_symbol *old_dt_list; /* Stash away derived types so that the backend_decls do not get mixed up. */ @@ -13435,16 +13435,17 @@ resolve_typebound_procedures (gfc_symbol* derived) static void add_dt_to_dt_list (gfc_symbol *derived) { - gfc_dt_list *dt_list; - for (dt_list = gfc_derived_types; dt_list; dt_list = dt_list->next) - if (derived == dt_list->derived) - return; - - dt_list = gfc_get_dt_list (); - dt_list->next = gfc_derived_types; - dt_list->derived = derived; - gfc_derived_types = dt_list; + if (!derived->dt_next) { + if (gfc_derived_types) { + derived->dt_next = gfc_derived_types->dt_next; + gfc_derived_types->dt_next = derived; + } else { + derived->dt_next = derived; + } + gfc_derived_types = derived; + } + } Index: gcc/fortran/symbol.c =================================================================== --- gcc/fortran/symbol.c (revision 260682) +++ gcc/fortran/symbol.c (working copy) @@ -107,7 +107,7 @@ gfc_namespace *gfc_global_ns_list; gfc_gsymbol *gfc_gsym_root = NULL; -gfc_dt_list *gfc_derived_types; +gfc_symbol *gfc_derived_types; static gfc_undo_change_set default_undo_chgset_var = { vNULL, vNULL, NULL }; static gfc_undo_change_set *latest_undo_chgset = &default_undo_chgset_var; @@ -3119,6 +3119,7 @@ gfc_new_symbol (const char *name, gfc_namespace *n p->common_block = NULL; p->f2k_derived = NULL; p->assoc = NULL; + p->dt_next = NULL; p->fn_result_spec = 0; return p; @@ -3878,23 +3879,6 @@ free_sym_tree (gfc_symtree *sym_tree) } -/* Free the derived type list. */ - -void -gfc_free_dt_list (void) -{ - gfc_dt_list *dt, *n; - - for (dt = gfc_derived_types; dt; dt = n) - { - n = dt->next; - free (dt); - } - - gfc_derived_types = NULL; -} - - /* Free the gfc_equiv_info's. */ static void @@ -4080,7 +4064,7 @@ gfc_symbol_done_2 (void) gfc_free_namespace (gfc_current_ns); gfc_current_ns = NULL; } - gfc_free_dt_list (); + gfc_derived_types = NULL; enforce_single_undo_checkpoint (); free_undo_change_set_data (*latest_undo_chgset); @@ -4343,7 +4327,7 @@ gfc_get_gsymbol (const char *name) static gfc_symbol * get_iso_c_binding_dt (int sym_id) { - gfc_dt_list *dt_list; + gfc_symbol *dt_list; dt_list = gfc_derived_types; @@ -4350,15 +4334,17 @@ get_iso_c_binding_dt (int sym_id) /* Loop through the derived types in the name list, searching for the desired symbol from iso_c_binding. Search the parent namespaces if necessary and requested to (parent_flag). */ - while (dt_list != NULL) - { - if (dt_list->derived->from_intmod != INTMOD_NONE - && dt_list->derived->intmod_sym_id == sym_id) - return dt_list->derived; + if (dt_list) { + while (dt_list->dt_next != gfc_derived_types) + { + if (dt_list->from_intmod != INTMOD_NONE + && dt_list->intmod_sym_id == sym_id) + return dt_list; + + dt_list = dt_list->dt_next; + } + } - dt_list = dt_list->next; - } - return NULL; } @@ -4762,11 +4748,13 @@ generate_isocbinding_symbol (const char *mod_name, if (tmp_sym->attr.flavor == FL_DERIVED && !get_iso_c_binding_dt (tmp_sym->intmod_sym_id)) { - gfc_dt_list *dt_list; - dt_list = gfc_get_dt_list (); - dt_list->derived = tmp_sym; - dt_list->next = gfc_derived_types; - gfc_derived_types = dt_list; + if (gfc_derived_types) { + tmp_sym->dt_next = gfc_derived_types->dt_next; + gfc_derived_types->dt_next = tmp_sym; + } else { + tmp_sym->dt_next = tmp_sym; + } + gfc_derived_types = tmp_sym; } return tmp_symtree; @@ -4874,7 +4862,6 @@ generate_isocbinding_symbol (const char *mod_name, case ISOCBINDING_FUNPTR: { gfc_symbol *dt_sym; - gfc_dt_list **dt_list_ptr = NULL; gfc_component *tmp_comp = NULL; /* Generate real derived type. */ @@ -4936,18 +4923,14 @@ generate_isocbinding_symbol (const char *mod_name, dt_sym->ts.u.derived = dt_sym; /* Add the symbol created for the derived type to the current ns. */ - dt_list_ptr = &(gfc_derived_types); - while (*dt_list_ptr != NULL && (*dt_list_ptr)->next != NULL) - dt_list_ptr = &((*dt_list_ptr)->next); - - /* There is already at least one derived type in the list, so append - the one we're currently building for c_ptr or c_funptr. */ - if (*dt_list_ptr != NULL) - dt_list_ptr = &((*dt_list_ptr)->next); - (*dt_list_ptr) = gfc_get_dt_list (); - (*dt_list_ptr)->derived = dt_sym; - (*dt_list_ptr)->next = NULL; - + if (gfc_derived_types) { + dt_sym->dt_next = gfc_derived_types->dt_next; + gfc_derived_types->dt_next = dt_sym; + } else { + dt_sym->dt_next = dt_sym; + } + gfc_derived_types = dt_sym; + gfc_add_component (dt_sym, "c_address", &tmp_comp); if (tmp_comp == NULL) gcc_unreachable (); Index: gcc/fortran/trans-types.c =================================================================== --- gcc/fortran/trans-types.c (revision 260682) +++ gcc/fortran/trans-types.c (working copy) @@ -2534,7 +2534,7 @@ gfc_get_derived_type (gfc_symbol * derived, int co bool got_canonical = false; bool unlimited_entity = false; gfc_component *c; - gfc_dt_list *dt; + gfc_symbol *dt; gfc_namespace *ns; tree tmp; bool coarray_flag; @@ -2599,13 +2599,18 @@ gfc_get_derived_type (gfc_symbol * derived, int co ns->translated && !got_canonical; ns = ns->sibling) { - dt = ns->derived_types; - for (; dt && !canonical; dt = dt->next) - { - gfc_copy_dt_decls_ifequal (dt->derived, derived, true); - if (derived->backend_decl) - got_canonical = true; - } + if (ns->derived_types) { + dt = ns->derived_types; + for (;;) + { + gfc_copy_dt_decls_ifequal (dt, derived, true); + if (derived->backend_decl) + got_canonical = true; + if (dt->dt_next == ns->derived_types) + break; + dt = dt->dt_next; + } + } } } @@ -2867,9 +2872,16 @@ copy_derived_types: } } - for (dt = gfc_derived_types; dt; dt = dt->next) - gfc_copy_dt_decls_ifequal (derived, dt->derived, false); - + if (gfc_derived_types) { + dt = gfc_derived_types; + for (;;) + { + gfc_copy_dt_decls_ifequal (derived, dt, false); + if (dt->dt_next == gfc_derived_types) + break; + dt = dt->dt_next; + } + } return derived->backend_decl; } --nextPart3108035.G46GXl6ko6--