* 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).