* Performance issue with GNU/ld and DLL @ 2012-01-28 13:55 Pascal Obry 2012-02-05 9:11 ` Pascal Obry 0 siblings, 1 reply; 12+ messages in thread From: Pascal Obry @ 2012-01-28 13:55 UTC (permalink / raw) To: binutils [-- Attachment #1: Type: text/plain, Size: 968 bytes --] Hello, This is a performance issue report when building DLL on Windows. To reproduce I have attached a python script (to generate C files). The steps to reproduce are: Run gen.py on an empty directory. $ gcc -c *.c $ time gcc -o main.exe *.o takes 0.4 seconds. $ time gcc -shared -o dll.dll *.o takes 12 seconds. It seems that the times goes exponentially. I had generated 1000 files instead of 200 (N=1000 in gen.py) and I had to kill the linker command after 10 minutes. Is that a known problem? Is there a workaround? Thanks in advance. Pascal. -- --|------------------------------------------------------ --| Pascal Obry Team-Ada Member --| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE --|------------------------------------------------------ --| http://www.obry.net - http://v2p.fr.eu.org --| "The best way to travel is by means of imagination" --| --| gpg --keyserver keys.gnupg.net --recv-key F949BD3B [-- Attachment #2: gen.py --] [-- Type: text/x-python, Size: 348 bytes --] #! /usr/bin/python m = open ("main.c", "w") m.write ("void main ()\n"); m.write ("{\n") N=200 for k in range(1,N): f = open ("file" + str(k) + ".c", "w") for n in range(1,N): f.write ("void call" + str(k) + "_" + str(n) + "() {}"); f.close m.write (" call" + str(k) + "_" + str(k) + " ();\n"); m.write ("}\n") m.close ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Performance issue with GNU/ld and DLL 2012-01-28 13:55 Performance issue with GNU/ld and DLL Pascal Obry @ 2012-02-05 9:11 ` Pascal Obry 2012-02-06 13:19 ` nick clifton 0 siblings, 1 reply; 12+ messages in thread From: Pascal Obry @ 2012-02-05 9:11 UTC (permalink / raw) To: pascal; +Cc: binutils PING? Has this been sent to the right mailing-list? Le 28/01/2012 14:55, Pascal Obry a écrit : > Hello, > > This is a performance issue report when building DLL on Windows. To > reproduce I have attached a python script (to generate C files). > > The steps to reproduce are: > > Run gen.py on an empty directory. > > $ gcc -c *.c > > $ time gcc -o main.exe *.o > > takes 0.4 seconds. > > $ time gcc -shared -o dll.dll *.o > > takes 12 seconds. > > It seems that the times goes exponentially. I had generated 1000 files > instead of 200 (N=1000 in gen.py) and I had to kill the linker command > after 10 minutes. > > Is that a known problem? > > Is there a workaround? > > Thanks in advance. > > Pascal. > -- --|------------------------------------------------------ --| Pascal Obry Team-Ada Member --| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE --|------------------------------------------------------ --| http://www.obry.net - http://v2p.fr.eu.org --| "The best way to travel is by means of imagination" --| --| gpg --keyserver keys.gnupg.net --recv-key F949BD3B ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Performance issue with GNU/ld and DLL 2012-02-05 9:11 ` Pascal Obry @ 2012-02-06 13:19 ` nick clifton 2012-02-09 18:31 ` Pascal Obry 2012-02-10 8:01 ` Pascal Obry 0 siblings, 2 replies; 12+ messages in thread From: nick clifton @ 2012-02-06 13:19 UTC (permalink / raw) To: pascal; +Cc: binutils Hi Pascal, > PING? > > Has this been sent to the right mailing-list? Yes it has. I am sorry, but I have not had time to look at this problem yet. I will post when I have had a chance to look at it though. Cheers Nick ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Performance issue with GNU/ld and DLL 2012-02-06 13:19 ` nick clifton @ 2012-02-09 18:31 ` Pascal Obry 2012-02-09 21:46 ` Pascal Obry 2012-02-10 8:01 ` Pascal Obry 1 sibling, 1 reply; 12+ messages in thread From: Pascal Obry @ 2012-02-09 18:31 UTC (permalink / raw) To: nick clifton; +Cc: binutils Nick, First thanks for your answer. I have identified the slowness. This is because in pe-dll.c we have: << static int auto_export (bfd *abfd, def_file *d, const char *n) { int i; struct exclude_list_struct *ex; const autofilter_entry_type *afptr; const char * libname = 0; if (abfd && abfd->my_archive) libname = lbasename (abfd->my_archive->filename); for (i = 0; i < d->num_exports; i++) if (strcmp (d->exports[i].name, n) == 0) return 0; ... >> Removing the above loop the code runs has fast for building executable than for building DLL. Just looking at the code it is clear that we have an O(n²) performance issue. For each export we look at all currently exports to see if it has not yet been handled! A solution would be to use a hash table or something like that. What would you advise (I do not know well the binutils sources), I'm willing to try fixing this issue. Thanks, Pascal. -- --|------------------------------------------------------ --| Pascal Obry Team-Ada Member --| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE --|------------------------------------------------------ --| http://www.obry.net - http://v2p.fr.eu.org --| "The best way to travel is by means of imagination" --| --| gpg --keyserver keys.gnupg.net --recv-key F949BD3B ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Performance issue with GNU/ld and DLL 2012-02-09 18:31 ` Pascal Obry @ 2012-02-09 21:46 ` Pascal Obry 2012-02-10 6:46 ` Pascal Obry 0 siblings, 1 reply; 12+ messages in thread From: Pascal Obry @ 2012-02-09 21:46 UTC (permalink / raw) To: nick clifton; +Cc: binutils Le 09/02/2012 19:31, Pascal Obry a écrit : > A solution would be to use a hash table or something like that. What > would you advise (I do not know well the binutils sources), I'm willing > to try fixing this issue. Another solution would be to sort the d->exports[] table (where?) and search by dichotomy. Pascal. -- --|------------------------------------------------------ --| Pascal Obry Team-Ada Member --| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE --|------------------------------------------------------ --| http://www.obry.net - http://v2p.fr.eu.org --| "The best way to travel is by means of imagination" --| --| gpg --keyserver keys.gnupg.net --recv-key F949BD3B ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Performance issue with GNU/ld and DLL 2012-02-09 21:46 ` Pascal Obry @ 2012-02-10 6:46 ` Pascal Obry 0 siblings, 0 replies; 12+ messages in thread From: Pascal Obry @ 2012-02-10 6:46 UTC (permalink / raw) To: pascal; +Cc: nick clifton, binutils Le 09/02/2012 22:45, Pascal Obry a écrit : > Another solution would be to sort the d->exports[] table (where?) and > search by dichotomy. Hum... looks like this array is already sorted by names, so I'll test a dichotomy search and will propose a patch. Let me know if this is not the right solution or if you see another better approach. Pascal. -- --|------------------------------------------------------ --| Pascal Obry Team-Ada Member --| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE --|------------------------------------------------------ --| http://www.obry.net - http://v2p.fr.eu.org --| "The best way to travel is by means of imagination" --| --| gpg --keyserver keys.gnupg.net --recv-key F949BD3B ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Performance issue with GNU/ld and DLL 2012-02-06 13:19 ` nick clifton 2012-02-09 18:31 ` Pascal Obry @ 2012-02-10 8:01 ` Pascal Obry 2012-02-10 9:27 ` Kai Tietz 2012-02-11 19:26 ` nick clifton 1 sibling, 2 replies; 12+ messages in thread From: Pascal Obry @ 2012-02-10 8:01 UTC (permalink / raw) To: nick clifton; +Cc: binutils [-- Attachment #1: Type: text/plain, Size: 480 bytes --] Here is the patch I'm proposing to solve this issue. Comments? Pascal. -- --|------------------------------------------------------ --| Pascal Obry Team-Ada Member --| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE --|------------------------------------------------------ --| http://www.obry.net - http://v2p.fr.eu.org --| "The best way to travel is by means of imagination" --| --| gpg --keyserver keys.gnupg.net --recv-key F949BD3B [-- Attachment #2: 0001-pe-dll.c-auto_export-Use-bsearch-instead-of-linear-s.patch --] [-- Type: text/x-diff, Size: 1603 bytes --] From 826e3c2ab58cabf0c02aee9e29248b1daef2b1e9 Mon Sep 17 00:00:00 2001 From: Pascal Obry <pascal@obry.net> Date: Fri, 10 Feb 2012 08:57:32 +0100 Subject: [PATCH] * pe-dll.c: (auto_export): Use bsearch instead of linear search. Fixes a performance issue when building large DLL (with many exports). --- ld/pe-dll.c | 15 ++++++++++----- 1 files changed, 10 insertions(+), 5 deletions(-) diff --git a/ld/pe-dll.c b/ld/pe-dll.c index ce0ab5d..c65616d 100644 --- a/ld/pe-dll.c +++ b/ld/pe-dll.c @@ -1,6 +1,6 @@ /* Routines to help build PEI-format DLLs (Win32 etc) Copyright 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, - 2008, 2009, 2010, 2011 Free Software Foundation, Inc. + 2008, 2009, 2010, 2011, 2012 Free Software Foundation, Inc. Written by DJ Delorie <dj@cygnus.com> This file is part of the GNU Binutils. @@ -529,16 +529,21 @@ is_import (const char* n) static int auto_export (bfd *abfd, def_file *d, const char *n) { - int i; + def_file_export key; struct exclude_list_struct *ex; const autofilter_entry_type *afptr; const char * libname = 0; if (abfd && abfd->my_archive) libname = lbasename (abfd->my_archive->filename); - for (i = 0; i < d->num_exports; i++) - if (strcmp (d->exports[i].name, n) == 0) - return 0; + /* Returns if n is in the d->exports table */ + + key.name = (char *)n; + key.its_name = (char *)n; + + if (bsearch (&key, d->exports, d->num_exports, + sizeof (pe_def_file->exports[0]), pe_export_sort)) + return 0; if (pe_dll_do_default_excludes) { -- 1.7.9.188.g12766 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Performance issue with GNU/ld and DLL 2012-02-10 8:01 ` Pascal Obry @ 2012-02-10 9:27 ` Kai Tietz 2012-02-10 16:11 ` Pascal Obry 2012-02-11 19:26 ` nick clifton 1 sibling, 1 reply; 12+ messages in thread From: Kai Tietz @ 2012-02-10 9:27 UTC (permalink / raw) To: pascal; +Cc: nick clifton, binutils 2012/2/10 Pascal Obry <pascal@obry.net>: > > Here is the patch I'm proposing to solve this issue. > > Comments? > > Pascal. Well, the idea is ok, but I see that first usage of auto_export () is before actual sorting of list. The usage of it is in process_def_file_and_directve at line 749. The sorting happens later on in this function at line 832. So this patch seems to me not ok, as for binary-searching we need to make sure list is sorted. Regards, Kai ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Performance issue with GNU/ld and DLL 2012-02-10 9:27 ` Kai Tietz @ 2012-02-10 16:11 ` Pascal Obry 2012-02-10 16:16 ` Kai Tietz 0 siblings, 1 reply; 12+ messages in thread From: Pascal Obry @ 2012-02-10 16:11 UTC (permalink / raw) To: Kai Tietz; +Cc: nick clifton, binutils [-- Attachment #1: Type: text/plain, Size: 1070 bytes --] Kai, > So this patch seems to me not ok, as for binary-searching we need to > make sure list is sorted. I've reviewed the code and in fact the exports table is update by def_file_add_export(). This routine insert the items at the good location, keeping the table sorted. The only location where the table is updated without using this routine is in the process_def_file_and_directve line 780 in the section where @ is removed. /* Canonicalize the export list. */ if (pe_dll_kill_ats) My patch sort the exports table only in this case and only when needed. If I have not overlooked some other update the attached patch should be ok. Comments? Pascal. -- --|------------------------------------------------------ --| Pascal Obry Team-Ada Member --| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE --|------------------------------------------------------ --| http://www.obry.net - http://v2p.fr.eu.org --| "The best way to travel is by means of imagination" --| --| gpg --keyserver keys.gnupg.net --recv-key F949BD3B [-- Attachment #2: 0001-pe-dll.c-auto_export-Use-bsearch-instead-of-linear-s.patch --] [-- Type: text/x-diff, Size: 2860 bytes --] From c38ca49a56bba9f87aa10fe9f5292272ac250d07 Mon Sep 17 00:00:00 2001 From: Pascal Obry <pascal@obry.net> Date: Fri, 10 Feb 2012 08:57:32 +0100 Subject: [PATCH] * pe-dll.c: (auto_export): Use bsearch instead of linear search. Fixes a performance issue when building large DLL (with many exports). (process_def_file_and_drectve): Sort export table only when needed. --- ld/pe-dll.c | 25 ++++++++++++++++++------- 1 files changed, 18 insertions(+), 7 deletions(-) diff --git a/ld/pe-dll.c b/ld/pe-dll.c index ce0ab5d..9964a8e 100644 --- a/ld/pe-dll.c +++ b/ld/pe-dll.c @@ -1,6 +1,6 @@ /* Routines to help build PEI-format DLLs (Win32 etc) Copyright 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, - 2008, 2009, 2010, 2011 Free Software Foundation, Inc. + 2008, 2009, 2010, 2011, 2012 Free Software Foundation, Inc. Written by DJ Delorie <dj@cygnus.com> This file is part of the GNU Binutils. @@ -529,16 +529,21 @@ is_import (const char* n) static int auto_export (bfd *abfd, def_file *d, const char *n) { - int i; + def_file_export key; struct exclude_list_struct *ex; const autofilter_entry_type *afptr; const char * libname = 0; if (abfd && abfd->my_archive) libname = lbasename (abfd->my_archive->filename); - for (i = 0; i < d->num_exports; i++) - if (strcmp (d->exports[i].name, n) == 0) - return 0; + /* Returns if n is in the d->exports table */ + + key.name = (char *)n; + key.its_name = (char *)n; + + if (bsearch (&key, d->exports, d->num_exports, + sizeof (pe_def_file->exports[0]), pe_export_sort)) + return 0; if (pe_dll_do_default_excludes) { @@ -644,6 +649,7 @@ process_def_file_and_drectve (bfd *abfd ATTRIBUTE_UNUSED, struct bfd_link_info * bfd *b; struct bfd_section *s; def_file_export *e = 0; + int sort_needed = 0; if (!pe_def_file) pe_def_file = def_file_empty (); @@ -788,10 +794,17 @@ process_def_file_and_drectve (bfd *abfd ATTRIBUTE_UNUSED, struct bfd_link_info * einfo (_("%XCannot export %s: invalid export name\n"), pe_def_file->exports[i].name); pe_def_file->exports[i].name = tmp; + sort_needed = 1; } } } + /* Sort as we have possibly changed the order by removing leading @ */ + + if (sort_needed) + qsort (pe_def_file->exports, NE, sizeof (pe_def_file->exports[0]), + pe_export_sort); + if (pe_dll_stdcall_aliases) { for (i = 0; i < NE; i++) @@ -829,8 +842,6 @@ process_def_file_and_drectve (bfd *abfd ATTRIBUTE_UNUSED, struct bfd_link_info * count_exported_byname = 0; count_with_ordinals = 0; - qsort (pe_def_file->exports, NE, sizeof (pe_def_file->exports[0]), - pe_export_sort); for (i = 0, j = 0; i < NE; i++) { if (i > 0 && strcmp (e[i].name, e[i - 1].name) == 0) -- 1.7.9.188.g12766 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Performance issue with GNU/ld and DLL 2012-02-10 16:11 ` Pascal Obry @ 2012-02-10 16:16 ` Kai Tietz 0 siblings, 0 replies; 12+ messages in thread From: Kai Tietz @ 2012-02-10 16:16 UTC (permalink / raw) To: pascal; +Cc: nick clifton, binutils, Dave Korn 2012/2/10 Pascal Obry <pascal@obry.net>: > > Kai, > >> So this patch seems to me not ok, as for binary-searching we need to >> make sure list is sorted. > > I've reviewed the code and in fact the exports table is update by > def_file_add_export(). This routine insert the items at the good > location, keeping the table sorted. > > The only location where the table is updated without using this routine > is in the process_def_file_and_directve line 780 in the section where @ > is removed. > > /* Canonicalize the export list. */ > if (pe_dll_kill_ats) > > My patch sort the exports table only in this case and only when needed. > > If I have not overlooked some other update the attached patch should be ok. > > Comments? > > Pascal. Yes, looks fine to me now. I can't approve it, but Dave or Nick are able to. So I added Dave here, too. Regards, Kai ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Performance issue with GNU/ld and DLL 2012-02-10 8:01 ` Pascal Obry 2012-02-10 9:27 ` Kai Tietz @ 2012-02-11 19:26 ` nick clifton 2012-02-11 22:17 ` Pascal Obry 1 sibling, 1 reply; 12+ messages in thread From: nick clifton @ 2012-02-11 19:26 UTC (permalink / raw) To: pascal; +Cc: binutils Hi Pascal, I agree with Kai - the patch is OK. There were a couple of very minor formatting issues, but I have fixed these and checked the patch in along with this changelog entry. Cheers Nick ld/ChangeLog 2012-02-11 Pascal Obry <pascal@obry.net> * pe-dll.c (auto_export): Use bsearch to speed up scan of exports table. (process_def_file_and_drectve): Maintain sorting of exports table after stripping leading @ signs. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Performance issue with GNU/ld and DLL 2012-02-11 19:26 ` nick clifton @ 2012-02-11 22:17 ` Pascal Obry 0 siblings, 0 replies; 12+ messages in thread From: Pascal Obry @ 2012-02-11 22:17 UTC (permalink / raw) To: nick clifton; +Cc: pascal, binutils Hi Nick, > I agree with Kai - the patch is OK. There were a couple of very minor > formatting issues, but I have fixed these and checked the patch in along > with this changelog entry. Thanks a lot! -- Pascal Obry -- gpg --keyserver keys.gnupg.net --recv-key F949BD3B ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2012-02-11 22:17 UTC | newest] Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2012-01-28 13:55 Performance issue with GNU/ld and DLL Pascal Obry 2012-02-05 9:11 ` Pascal Obry 2012-02-06 13:19 ` nick clifton 2012-02-09 18:31 ` Pascal Obry 2012-02-09 21:46 ` Pascal Obry 2012-02-10 6:46 ` Pascal Obry 2012-02-10 8:01 ` Pascal Obry 2012-02-10 9:27 ` Kai Tietz 2012-02-10 16:11 ` Pascal Obry 2012-02-10 16:16 ` Kai Tietz 2012-02-11 19:26 ` nick clifton 2012-02-11 22:17 ` Pascal Obry
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).