Re: [Bug 417] New: htree much slower than regular ext3

Daniel Phillips
2003-02-27T19:54:16Z

On Thursday 27 February 2003 18:31, Martin J. Bligh wrote:
> Problem Description:
> I created a directory ("test") with 32000 (ok, 31998) directories in it,
> and put a file called 'foo' in each of them (for i in `ls`; do cd $i &&
> touch bar && cd .. ; done). Then I took that ext3 partion, umounted it,
> did a 'tune2fs -O dir_index', then 'fsck -fD', and remounted. I then did a
> 'time du -hs' on the test directory, and here are the results.
>
> ext3+htree:
> bwindle@razor:/giant/inodes$ time du -hs
> 126M .
>
> real 7m21.756s
> user 0m2.021s
> sys 0m22.190s
>
> I then unmounted, tune2fs -O ^dir_index, e2fsck -fD /dev/hdb1, remounted,
> and did another du -hs on the test directory. It took 1 minute, 48
> seconds.
>
> bwindle@razor:/giant/test$ time du -hs
> 126M .
>
> real 1m48.760s
> user 0m1.986s
> sys 0m21.563s
>
>
> I thought htree was supposed to speed up access with large numbers of
> directories?

The du just does getdents and lstats in physical storage order, so there's no
possible benefit from indexing in this case, and unindexed ext3 avoids long
search times by caching the position at which it last found an entry. That
answers the question "why doesn't it speed up", however, "why did it slow way
down" is harder.

The single-file leaves of your directory tree don't carry any index (it's not
worth it with only one file) and therfore use the same code path as unindexed
ext3, so there's no culprit there. I'm looking suspiciously at
ext3_dx_readdir, which is apparently absorbing about 11 ms per returned
entry. To put this in perspective, I'm used to seeing individual directory
operation times well below 100 us, so even if each dirent cost as much as a
full lookup, you'd see less than 3 seconds overhead for your 30,000
directories.

11 ms sounds like two seeks for each returned dirent, which sounds like a bug.

Regards,

Daniel