hg status not showing empty dirs out of dirstate

[Andrea Arcangeli]

On Fri, Jun 16, 2006 at 09:52:36AM -0500, Matt Mackall wrote:
> 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.

Certainly measurable. I _immediately_ agreed to improve it and I know
how to do it. I answered again just to say that it's definitely _not_
135000**2 like the previous post seems to imply ;). As far as math is
concerned it's really N**2 but as far as math is concerned the kernel
hashtables are O(N) as well, but that doesn't mean their average cost is
so bad for similar reasons.