[Issue 4721] compilation slow when compiling unittests on dcollections

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=4721



--- Comment #6 from Steven Schveighoffer <schveiguy at yahoo.com> 2010-08-24 14:10:26 PDT ---
More testing, I did some printf debugging.

According to the comments and the code of the function, it's a *linear* search
through the symbol table for a match to a given symbol + suffix.

The symbol table is a null-separated single buffer.  So not only is it linear
through the strings, but it's linear on the *characters*.  That is, when
comparing the current symbol and it's a mismatch, the code must iterate through
all the characters anyways to find the next null character.

I added some printouts to determine the eventual size of the symbol table, and
the number of times the function is called.  I also added printouts to show the
number of matches found (those should theoretically not do a linear search
through the entire table, but likely would search through most of it).

The eventual numbers for dcollections:

symbol table size: 4,253,953
number of calls:   12,677
number of matches: 648

doing the math, thats probably conservatively about 20 billion loop iterations
-- way unacceptable for something that should be done via a hash lookup, or at
least a tree/trie/binary search.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------