Issue 4900 - compiler still slow due to a single function
Summary: compiler still slow due to a single function
Status: RESOLVED FIXED
Alias: None
Product: D
Classification: Unclassified
Component: dmd (show other issues)
Version: D2
Hardware: Other Linux
: P2 normal
Assignee: No Owner
URL:
Keywords: performance
Depends on:
Blocks:
 
Reported: 2010-09-20 05:20 UTC by Steven Schveighoffer
Modified: 2019-07-16 04:22 UTC (History)
4 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description Steven Schveighoffer 2010-09-20 05:20:20 UTC
As shown in bug 4721, there is still a problem in the compiler when compiling projects with a large number of symbols.  Here is a profiled version of dmd 2.048 compiling unit tests for dcollections:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 80.31     11.99    11.99    19000     0.63     0.63  searchfixlist
  0.67     12.09     0.10   203173     0.00     0.00  StringTable::search(char
const*, unsigned int)
  0.60     12.18     0.09   369389     0.00     0.00  Lexer::scan(Token*)
  0.54     12.26     0.08   953613     0.00     0.00  ScopeDsymbol::search(Loc,
Identifier*, int)
  0.47     12.33     0.07  1449798     0.00     0.00  calccodsize
...

Note the searchfixlist function uses 80% of the runtime (the compiler takes 17 seconds to produce a result), but only has 19000 calls.  Compare that to other functions which have orders of magnitude more calls but nothing takes more than 0.7%.

An examination of the searchfixlist function shows that it is a search through a linked list.  I'm unsure if the same methodology (replace with hash) can be applied as was in issue 4721, but it would be good to investigate possible ideas to replace the algorithm there.

I opened this as a separate bug, because the original bug in 4721 was fixed.
Comment 1 Walter Bright 2010-11-23 12:57:31 UTC
Yes, the linked list should be replaced with a hashtable.
Comment 2 bearophile_hugs 2010-11-25 20:19:58 UTC
See also bug 5276 for another possible (smaller) benchmark.
Comment 3 Trass3r 2012-05-11 12:50:48 UTC
Is this still the case? There was this commit: https://github.com/D-Programming-Language/dmd/commit/b329817
Comment 4 Steven Schveighoffer 2012-05-11 13:03:42 UTC
Well, I certainly have tested dcollections since then, but I don't remember there being a significant speedup.

I'd have to re-profile the compiler to be sure.
Comment 5 Mathias LANG 2019-07-16 04:22:41 UTC
`searchfixlist` is now a stub: https://github.com/dlang/dmd/blob/4fe0539aa604716d6dc469790eba096348069918/src/dmd/backend/code.d#L551
Doesn't mean that the compiler is fast, but at least this one can be closed :)