Steven Schveighoffer wrote:
> On Tue, 24 Aug 2010 03:58:57 -0400, Walter Bright <newshound2@digitalmars.com> wrote:
> 
>> Steven Schveighoffer wrote:
>>> With profiling enabled, gprof outputs this as the top hitters:
>>>   Flat profile:
>>>  Each sample counts as 0.01 seconds.
>>>   %   cumulative   self              self     total
>>>  time   seconds   seconds    calls  ms/call  ms/call  name
>>>  77.76      6.68     6.68     2952     2.26     2.26  elf_findstr(Outbuffer*, char const*, char const*)
>>>   2.10      6.86     0.18     4342     0.04     0.04  searchfixlist
>>
>> elf_findstr definitely looks like a problem area. I can't look at it right now, so can you post this to bugzilla please?
> 
> http://d.puremagic.com/issues/show_bug.cgi?id=4721

Also, putting a printf in elf_findstr to print its arguments will be helpful.

On Tue, 24 Aug 2010 14:31:26 -0400, Walter Bright <newshound2@digitalmars.com> wrote:

> Steven Schveighoffer wrote:
>> On Tue, 24 Aug 2010 03:58:57 -0400, Walter Bright <newshound2@digitalmars.com> wrote:
>>
>>> Steven Schveighoffer wrote:
>>>> With profiling enabled, gprof outputs this as the top hitters:
>>>>   Flat profile:
>>>>  Each sample counts as 0.01 seconds.
>>>>   %   cumulative   self              self     total
>>>>  time   seconds   seconds    calls  ms/call  ms/call  name
>>>>  77.76      6.68     6.68     2952     2.26     2.26  elf_findstr(Outbuffer*, char const*, char const*)
>>>>   2.10      6.86     0.18     4342     0.04     0.04  searchfixlist
>>>
>>> elf_findstr definitely looks like a problem area. I can't look at it right now, so can you post this to bugzilla please?
>>  http://d.puremagic.com/issues/show_bug.cgi?id=4721
>
> Also, putting a printf in elf_findstr to print its arguments will be helpful.

Through some more work with printf, I have to agree with bearophile, this lookup function is horrid.

I think it's supposed to look for a symbol in the symbol table, but it uses a linear search through all symbols to find it.  Not only that, but the table is stored in one giant buffer, so once it finds the current symbol it's checking against doesn't match, it has to still loop through the remaining characters of the unmatched symbol to find the next 0 byte.

I added a simple running printout of how many times the function has been called, along with how large the symbol table has grown.

The code is as follows:


static IDXSTR elf_findstr(Outbuffer *strtab, const char *str, const char *suffix)
{
+    static int ncalls = 0;
+    ncalls++;
+    printf("\r%d\t%d", ncalls, strtab->size());
+    fflush(stdout);
    const char *ent = (char *)strtab->buf+1;
    const char *pend = ent+strtab->size() - 1;


At the end, the symbol table is over 4 million characters and the number of calls is 12677.  You can watch it slow down noticeably.

I also added some code to count the number of times a symbol is matched -- 648, so about 5% of the time.  This means that 95% of the time, the whole table is searched.

If you multiply those factors together, and take into account the nature of how it grows, you have probably 20 billion loop iterations.  Whereas, a hash table would probably be much faster.  I'm thinking a correct compilation time should be on the order of 3-4 seconds vs. 67 seconds it now takes.

I am not sure how to fix it, but that's the gist of it.  I think the symbol table is so large because of the template proliferation of dcollections, and the verbosity of D symbol names.

-Steve

Am 24.08.2010 22:56, schrieb Steven Schveighoffer:

> I am not sure how to fix it, but that's the gist of it.  I think the
> symbol table is so large because of the template proliferation of
> dcollections, and the verbosity of D symbol names.

Why are D's symbols verbose?  if I understood you corectly, dmd makes a linear search no matter if i used foo or ArrayOutOfBoundsException (that's a real Java exception).

On Tue, 24 Aug 2010 17:05:30 -0400, Mafi <mafi@example.org> wrote:

> Am 24.08.2010 22:56, schrieb Steven Schveighoffer:
>
>> I am not sure how to fix it, but that's the gist of it.  I think the
>> symbol table is so large because of the template proliferation of
>> dcollections, and the verbosity of D symbol names.
>
> Why are D's symbols verbose?  if I understood you corectly, dmd makes a linear search no matter if i used foo or ArrayOutOfBoundsException (that's a real Java exception).

A symbol includes the module name, and the mangled version of the function argument types, which could be class/struct names, plus any template info associated with it.

For example, foo(HashSet!int hs) inside the module testme becomes:

_D6testme3fooFC12dcollections7HashSet14__T7HashSetTiZ7HashSetZv

-Steve

Steven Schveighoffer:
> For example, foo(HashSet!int hs) inside the module testme becomes: _D6testme3fooFC12dcollections7HashSet14__T7HashSetTiZ7HashSetZv

And I think some more things needs to be added to that string, like a representation for the pure attribute, etc.

Bye,
bearophile

On 2010-08-24 12:25, bearophile wrote:
> Walter Bright:
>> elf_findstr definitely looks like a problem area. I can't look at it right now,
>> so can you post this to bugzilla please?
>
> I am able to find two versions of elf_findstr, one in elfobj.c and one in machobj.c, so it may be possible to remove one of them.

As the files indicate elfobj.c is for generating ELF (linux) object files and machobj.c is for generating Mach-O (osx) object files, both are needed. I guess he uses the same name for the functions to have a uniform interface, no need to change the code on the calling side.

> Its docstring doesn't seem to show the 'suffix' argument.
>
> I have seen that it performs strlen() of str and suffix at the beginning, so using fat pointers (C structs that keep ptr + len) as D may be enough to avoid those strelen calls and save some time.
>
>  From what I see it seems to perform a linear search inside an Outbuffer, something like a search of strtab~strs inside an array of strings, so the structure may be replaced by an associative set or ordered set lookup instead.
>
> Bye,
> bearophile


-- 
/Jacob Carlborg

On Tuesday, August 24, 2010 14:37:09 bearophile wrote:
> Steven Schveighoffer:
> > For example, foo(HashSet!int hs) inside the module testme becomes: _D6testme3fooFC12dcollections7HashSet14__T7HashSetTiZ7HashSetZv
> 
> And I think some more things needs to be added to that string, like a representation for the pure attribute, etc.
> 
> Bye,
> bearophile

They probably aren't there because

1. They have nothing to do with overrideability.

2. They have nothing to do with C linking.

Presumably, dmd deals with those attributes at the appropriate time and then doesn't bother putting them in the symbol table because they're not relevant any more (or if they are relevant, it has other ways of getting at them). If they were actually necessary in the symbol name, they'd be there. If they aren't necessary, why bother putting them in there, making the symbol names even longer?

- Jonathan M Davis

Steven Schveighoffer wrote:
> Through some more work with printf, I have to agree with bearophile, this lookup function is horrid.

It is now, but when it was originally written (maybe as long as 20 years ago) there were only a few strings in the table, and it was fine. It's just outlived its design. Clearly, it should now be a hash table.

Just goes to show how useful a profiler is.

On Tue, 24 Aug 2010 23:53:44 +0200, Jonathan M Davis <jmdavisprog@gmail.com> wrote:

> On Tuesday, August 24, 2010 14:37:09 bearophile wrote:
>> Steven Schveighoffer:
>> > For example, foo(HashSet!int hs) inside the module testme becomes:
>> > _D6testme3fooFC12dcollections7HashSet14__T7HashSetTiZ7HashSetZv
>>
>> And I think some more things needs to be added to that string, like a
>> representation for the pure attribute, etc.
>>
>> Bye,
>> bearophile
>
> They probably aren't there because
>
> 1. They have nothing to do with overrideability.
>
> 2. They have nothing to do with C linking.
>
> Presumably, dmd deals with those attributes at the appropriate time and then
> doesn't bother putting them in the symbol table because they're not relevant any
> more (or if they are relevant, it has other ways of getting at them). If they
> were actually necessary in the symbol name, they'd be there. If they aren't
> necessary, why bother putting them in there, making the symbol names even
> longer?

Pure might be worth stuffing in the symbol name, as the compiler may
optimize things differently for pure vs. non-pure(dirty?) code.
E.g. the result of a large, pure function that takes a while to compute
might be cached to prevent calling it twice.

-- 
Simen

== Quote from Walter Bright (newshound2@digitalmars.com)'s article
> Steven Schveighoffer wrote:
> > Through some more work with printf, I have to agree with bearophile, this lookup function is horrid.
> It is now, but when it was originally written (maybe as long as 20 years ago)
> there were only a few strings in the table, and it was fine. It's just outlived
> its design. Clearly, it should now be a hash table.
> Just goes to show how useful a profiler is.

Wow, now it's really hit home for me how much programming languages and libraries have advanced in the past 20 years.  Nowadays any reasonable person would generally use a hash table even for small N because it's not any harder to code. Any modern language worth its salt comes with one either built in or in the standard lib.  I guess 20 years ago this wasn't so.