Re: [RFC] Optimizing readdir()

[Radek Pazdera <rpazdera@redhat.com>]

[-- Attachment #1: ext4m.txt --]
[-- Type: text/plain, Size: 1775 bytes --]

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