dmd 1.060 and 2.045 release
Walter Bright
newshound1 at digitalmars.com
Thu May 6 14:35:05 PDT 2010
Steven Schveighoffer wrote:
> On Thu, 06 May 2010 17:07:12 -0400, Walter Bright
> <newshound1 at digitalmars.com> wrote:
>
>> Steven Schveighoffer wrote:
>>> That can't be it. The identifier shown by Alex is only 33
>>> characters. O(n^2) is not that slow, especially for smaller
>>> variables. There must be other factors you're not considering...
>>
>> I recompiled dmd with the profiler (-gt switch) which confirmed it.
>
> So a single unknown symbol (from Alex's example) which can be checked
> against each existing symbol in O(n^2) time, takes 40 seconds on a
> decent CPU? How many other symbols are there? 33^2 == 1089, if there
> are 10000 symbols, that's 10 million iterations, that shouldn't take 40
> seconds to run, should it? Are there more symbols to compare against?
> Do you use heuristics to prune the search? For example, if the max
> distance is 2, and the difference in length between two strings is >2,
> you should be able to return immediately.
Check out the profiler output. It's clearly the vast number of calls to the
symbol lookup, not the time spent in each call.
-----------------------------------------
Num Tree Func Per
Calls Time Time Call
50409318 632285778 145858160 2 Dsymbol *syscall
ScopeDsymbol::search(Loc ,Identifier *,int )
50411264 131394915 106356855 2 void **syscall
StringTable::search(char const *,unsigned )
50409329 341960075 105532978 2 Dsymbol *syscall
DsymbolTable::lookup(Identifier *)
50409329 236427096 105037393 2 StringValue *syscall
StringTable::lookup(char const *,unsigned )
12602340 613890619 67393753 5 Dsymbol *syscall
Scope::search(Loc ,Identifier *,Dsymbol **)
12602178 693915197 66918360 5 void *cdecl
scope_search_fp(void *,char const *)
25204505 461352920 52529164 2 Dsymbol *syscall
Module::search(Loc ,Identifier *,int )
50412137 25038474 25038474 0 unsigned cdecl
Dchar::calcHash(char const *,unsigned )
3520 1428323068 20349375 5781 void *cdecl spellerX(char const
*,void *cdecl (*)(void *,char const *),void *,char const *,int )
12602664 6811916 6811916 0 syscall
Identifier::Identifier(char const *,int )
12602178 6299089 6299089 0 void cdecl Module::clearCache()
12602183 6151175 6151175 0 Module *syscall Module::isModule()
1600 11329 4261 2 StringValue *syscall
StringTable::update(char const *,unsigned )
-----------------------------------------
More information about the Digitalmars-d-announce
mailing list