On Fri, 2007-06-08 at 10:05 +0100, Thomas Fischbacher wrote:
> skaller wrote:
> 
> > You mention in the ticket there is a hard way out .. using
> > binary trees; hard because it would require changes everywhere
> > in the compiler. Is this actually enough? Seems to reduce
> > 
> > 	O(n * n * log n)
> > 
> > to 
> > 
> > 	O( n * log n * log n)
>  >
> > which is still pretty bad.. is that right?
> 
> What would be so bad about O(n log n log n)?
> After all, in our relevant computing universe, there
> always is an upper bound to log n which is quite
> a small constant (like 25 or so).

Perhaps you're right .. still, there's a big difference
between a 5 minute compile (enough time to make a coffee!)
and a 2 hour compile (enough time to have lunch!)

I just went through this: Felix normal build time is
about 20 minutes including all tests. With an early version
of Dypgen parser, this was changed to around 4 hours...
luckily, back to 20 minutes now. Even a small % increase
in times can be quite significant.

I usually illustrate this by asking if you'd be happy
to give up your 2 / 52 week annual holiday .. that's
under 4% of the year.. I'm sure you'd be horrified ..
4% is a LOT!

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net