hg status not showing empty dirs out of dirstate

[Matt Mackall]

On Fri, Jun 16, 2006 at 04:37:20PM +0200, Andrea Arcangeli wrote:
> On Fri, Jun 16, 2006 at 07:05:21AM -0700, Bryan O'Sullivan wrote:
> > Actually, dc is a dict containing (at the beginning) every file
> > Mercurial knows about.  Track 135,000 files and it will have 135,000
> > entries, which it will iterate over every trip through the loop.  Not
> > just a theoretical consideration, then :-)
> 
> dc yes of course, that's the N, but the other N is not 1350000, the
> other N is only the number of directories, that's some order of mangitude
> lower in most secenarios.

If you assume that the number of directories is, on average, in some
linear proportion to the number of files, it's still quadratic in the
number of files. For the case above, even a couple orders of magnitude
fewer dirs (a 1:100 ratio) means we're still multiplying by 135000,
just dividing by a constant ratio afterwards. Which means 182M
operations rather than .14M. Probably noticeable.

For reference, the ratio for the kernel tree is 1:12 and for my entire
laptop is 1:18.

-- 
Mathematics is the supreme nostalgia of our time.