From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 1720 invoked by alias); 25 May 2018 21:54:58 -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 1705 invoked by uid 89); 25 May 2018 21:54:55 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-11.1 required=5.0 tests=BAYES_00,FREEMAIL_FROM,GIT_PATCH_2,GIT_PATCH_3,KAM_ASCII_DIVIDERS,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.2 spammy=HX-Received:sk:b8-v6mr, UD:parse.c, HX-Received:4c88, parse.c X-HELO: mail-pl0-f65.google.com Received: from mail-pl0-f65.google.com (HELO mail-pl0-f65.google.com) (209.85.160.65) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 25 May 2018 21:54:53 +0000 Received: by mail-pl0-f65.google.com with SMTP id n10-v6so3860200plp.0 for ; Fri, 25 May 2018 14:54:52 -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=GfkzmMHiRFZOP0X2SXU3ZlDFyKPFKKgRM/jhxSOm9aY=; b=D8obyZOYvWAY+uE2xkwZIzfV8o15475zRJ/3Z0fzmoOag1ddvPuXKfueMBxnDuycw1 n63rS8+3um98+Wq/9z6Gh+xo5RVRfckWGWFwtol24FNNYEzV/3nR40pTwYTlGJcjrnCC GBC+ZHLPxifmk1RujWkWeDU2N5pzLtnEW3ZVQNlz66YPx+D6If4pIPLlX8BP0NVPWCvI kLY2gZg8+bh8IB4axNzm2snrELmW6SxrpYxKjVFVx8rjJHsap13gNUjMAIHwM9ELU14i Os0PlX3EuD0rU5+an0/yYEmVGSXplPszGBAwIHubtQRWZrD8/qCrXpIuz70iCRQWoT2x tjEQ== X-Gm-Message-State: ALKqPwejSiWPRcSNSfr8bs6/1Frmd+ECif8oOtxJt0bH7B+f/xzERIXS BxSJhh46f5uuVve49qDCnjc= X-Google-Smtp-Source: AB8JxZoJ/BaGMQxNXR2WcogABkQt0qqTdsxbvdGfOhjzYszUJwD9T6GohKiLFpfPf370rBxAPZbsGw== X-Received: by 2002:a17:902:4c88:: with SMTP id b8-v6mr4161250ple.285.1527285291458; Fri, 25 May 2018 14:54:51 -0700 (PDT) Received: from andrew-precision-3520.localnet (66-215-238-7.dhcp.rvsd.ca.charter.com. [66.215.238.7]) by smtp.gmail.com with ESMTPSA id k2-v6sm47436578pfg.82.2018.05.25.14.54.50 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 25 May 2018 14:54:50 -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: Fri, 25 May 2018 21:54:00 -0000 Message-ID: <4775872.iWz7lGoeLh@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> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="nextPart36367041.YLMumk3kVr" Content-Transfer-Encoding: 7Bit X-IsSubscribed: yes X-SW-Source: 2018-05/txt/msg00105.txt.bz2 This is a multi-part message in MIME format. --nextPart36367041.YLMumk3kVr Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="us-ascii" Content-length: 2843 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). 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 > 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 --nextPart36367041.YLMumk3kVr Content-Disposition: attachment; filename="patch.diff" Content-Transfer-Encoding: 7Bit Content-Type: text/x-patch; charset="UTF-8"; name="patch.diff" Content-length: 7020 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_dt_list *dt_next; } gfc_symbol; @@ -1716,7 +1719,6 @@ gfc_symtree; typedef struct gfc_dt_list { struct gfc_symbol *derived; - struct gfc_dt_list *next; } gfc_dt_list; Index: gcc/fortran/parse.c =================================================================== --- gcc/fortran/parse.c (revision 260682) +++ gcc/fortran/parse.c (working copy) @@ -6123,6 +6123,9 @@ translate_all_program_units (gfc_namespace *gfc_gl } /* Clean up all the namespaces after translation. */ + + clean_up_modules (gfc_gsym_root); + gfc_current_ns = gfc_global_ns_list; for (;gfc_current_ns;) { @@ -6141,7 +6144,6 @@ translate_all_program_units (gfc_namespace *gfc_gl gfc_current_ns = ns; } - clean_up_modules (gfc_gsym_root); } Index: gcc/fortran/resolve.c =================================================================== --- gcc/fortran/resolve.c (revision 260682) +++ gcc/fortran/resolve.c (working copy) @@ -13437,14 +13437,18 @@ 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) { + dt_list = gfc_get_dt_list (); + dt_list->derived = derived; + if (gfc_derived_types) { + derived->dt_next = gfc_derived_types->derived->dt_next; + gfc_derived_types->derived->dt_next = dt_list; + } else { + derived->dt_next = dt_list; + } + gfc_derived_types = dt_list; + } + } Index: gcc/fortran/symbol.c =================================================================== --- gcc/fortran/symbol.c (revision 260682) +++ gcc/fortran/symbol.c (working copy) @@ -3885,11 +3885,15 @@ gfc_free_dt_list (void) { gfc_dt_list *dt, *n; - for (dt = gfc_derived_types; dt; dt = n) - { - n = dt->next; - free (dt); + if (gfc_derived_types) { + dt = gfc_derived_types; + while (dt->derived->dt_next != dt) { + n = dt->derived->dt_next; + dt->derived->dt_next = n->derived->dt_next; + free(n); } + free(dt); + } gfc_derived_types = NULL; } @@ -4072,6 +4076,7 @@ gfc_symbol_init_2 (void) void gfc_symbol_done_2 (void) { + gfc_free_dt_list (); if (gfc_current_ns != NULL) { /* free everything from the root. */ @@ -4080,7 +4085,6 @@ gfc_symbol_done_2 (void) gfc_free_namespace (gfc_current_ns); gfc_current_ns = NULL; } - gfc_free_dt_list (); enforce_single_undo_checkpoint (); free_undo_change_set_data (*latest_undo_chgset); @@ -4350,15 +4354,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->derived->dt_next != gfc_derived_types) + { + if (dt_list->derived->from_intmod != INTMOD_NONE + && dt_list->derived->intmod_sym_id == sym_id) + return dt_list->derived; + + dt_list = dt_list->derived->dt_next; + } + } - dt_list = dt_list->next; - } - return NULL; } @@ -4765,8 +4771,13 @@ generate_isocbinding_symbol (const char *mod_name, 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->derived->dt_next; + gfc_derived_types->derived->dt_next = dt_list; + } else { + tmp_sym->dt_next = dt_list; + } + gfc_derived_types = dt_list; } return tmp_symtree; @@ -4874,7 +4885,7 @@ generate_isocbinding_symbol (const char *mod_name, case ISOCBINDING_FUNPTR: { gfc_symbol *dt_sym; - gfc_dt_list **dt_list_ptr = NULL; + gfc_dt_list *dt_list = NULL; gfc_component *tmp_comp = NULL; /* Generate real derived type. */ @@ -4936,18 +4947,16 @@ 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; - + dt_list = gfc_get_dt_list (); + if (gfc_derived_types) { + dt_sym->dt_next = gfc_derived_types->derived->dt_next; + gfc_derived_types->derived->dt_next = dt_list; + } else { + dt_sym->dt_next = dt_list; + } + dt_list->derived = dt_sym; + gfc_derived_types = dt_list; + 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) @@ -2599,13 +2599,15 @@ 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 (; dt->derived->dt_next != ns->derived_types && !canonical; dt = dt->derived->dt_next) + { + gfc_copy_dt_decls_ifequal (dt->derived, derived, true); + if (derived->backend_decl) + got_canonical = true; + } + } } } @@ -2867,9 +2869,11 @@ 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) { + for (dt = gfc_derived_types; dt->derived->dt_next != gfc_derived_types; dt = dt->derived->dt_next) + gfc_copy_dt_decls_ifequal (derived, dt->derived, false); + } + return derived->backend_decl; } --nextPart36367041.YLMumk3kVr--