Steven Schveighoffer wrote:
On Thu, 06 May 2010 17:07:12 -0400, Walter Bright
<[email protected]> 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 )
-----------------------------------------
