On Tue, 29 Jan 2013, Radek Pazdera wrote: > Date: Tue, 29 Jan 2013 17:38:46 +0100 > From: Radek Pazdera <rpazdera@xxxxxxxxxx> > To: Andreas Dilger <adilger@xxxxxxxxx> > Cc: Theodore Ts'o <tytso@xxxxxxx>, linux-ext4@xxxxxxxxxxxxxxx, > Lukáš Czerner <lczerner@xxxxxxxxxx> > Subject: Re: [RFC] Optimizing readdir() > > On Tue, Jan 15, 2013 at 03:44:57PM -0700, Andreas Dilger wrote: > >Having an upper limit on the directory cache is OK too. Read all > >of the entries that fit into the cache size, sort them, and return > >them to the caller. When the caller has processed all of those > >entries, read another batch, sort it, return this list, repeat. > > > >As long as the list is piecewise ordered, I suspect it would gain > >most of the benefit of linear ordering (sequential inode table > >reads, avoiding repeated lookups of blocks). Maybe worthwhile if > >you could test this out? > > I did the tests last week. I modified the spd_readdir preload to > read at most $SPD_READDIR_CACHE_LIMIT entries, sort them and repeat. > The patch is here: > > http://www.stud.fit.vutbr.cz/~xpazde00/soubory/dir-index-test-ext4/ > > I tested it with the limit set to 0 (i.e., no limit), 1000, 10000, > 50000, and completely without the preload. The test runs were > performed on the same directory, so the results shouldn't be > affected by positioning on disk. > > Directory sizes went from 10k to 1.5M. The tests were run twice. > The first run is only with metadata. In the second run, each file > has 4096B of data. > > Here are the results: > 0B files: > http://www.stud.fit.vutbr.cz/~xpazde00/soubory/dir-index-test-ext4/0B-files > > 4096B files: > http://www.stud.fit.vutbr.cz/~xpazde00/soubory/dir-index-test-ext4/4096B-files/ > > The times seem to decrease accordingly as the limit of the cache > increases. The differences are bigger in case of 4096B files, where > the data blocks start to evict the inode tables. However, copying is > still more than two times slower for 1.5M files when 50000 entries > are cached. > > It might be interesting to test what happens when the size of the > files in the directory increases. > > Best Regards > Radek Hi Radek, those are interesting results and it supports the idea that you can get most of the performance of completely sorted inode list by doing it in "batches" as long as the size of the batch is sufficiently large. However I do not think that using spd_readdir is the best approach for the problem, nor do I think that it should be part of the generic library. Aside from it's "hackish" nature and the fact you will never be able to tell how much memory you can actually use for the sorting, the fact is that other file systems can handle this problem well enough in comparison with ext4 and we should really focus on fixing it, rather than going around it. Thanks! -Lukas
