[PATCH 0/3] Speed up notmuch new for unchanged directories

[Sascha Silbe]

Austin Clements <amdragon at MIT.EDU> writes:

>> "notmuch new" needs to iterate over a list of all directories to find
>> those with new mails (and potentially new subdirectories). However, it
>> does not need to list the *contents* of those folders. I'm surprised as
>> well, but rather in the opposite direction: Based on a naive
>> calculation, we'd expect to see a speedup on the order of
>> (1.25M+29k)/29k = 44. The actual results suggest that stat()ing (done
>> 29k times both before and after the patch) is taking about 19 times as
>> long as listing a directory entry (before the patch we listed 1M
>> entries, now we list none if nothing has changed). (*)
>
> For a cold cache, these aren't the numbers that matter. With an HDD
> and how few files your directories contain on average, only seeks will
> matter. I would expect your workload without your patch to have at
> least 1 but closer to 2 seeks per directory: one to stat the directory
> and one to get the directory contents block.
[...]
> I'm surprised by your results because I would expect your workload
> with your patches to exhibit about the same number of seeks: one to
> stat the directory (same as before) and one for
> notmuch_directory_get_child_files, which has to seek in the term index
> to get the child directories.  My guess is that this exhibits better
> locality because the child directory terms are stored contiguously in
> the database's key space (though not necessarily sequentially on disk
> unless this is a fresh database).

Well, what I'd expect from the file system is good locality for large
files. So once you are at the database index, reading is fast (about
50MB/s). But the directories are dispersed and were created over time,
so their overall locality (remember that we need only a few blocks per
directory) is likely to be rather poor.

I would have to take a closer look at ext4 (the last time I looked at
the on-disk structures of ext* was several years ago), but IIRC
everything we need for the stat() should be either in its inode. So the
patch saves a read of the leaf directory data blocks. I'd expect leaf
directories to outnumber intermediate directories by about 3-4:1 (cur/,
new/, tmp/ and additionally new-20120623 in my case). That would be
consistent with the speedup, but may just be coincidence.

What we'd really need to know here (to understand the particular numbers
my tests resulted in) is the block allocation strategies of ext4.


> Unfortunately, I'm not sure of a good way to test this hypothesis.
> Any thoughts?

The only scientific way to test it that I can think of would be to
determine the actual block numbers on disk (does FIEMAP work for
directories?) to calculate locality and / or record access times during
the "notmuch new" run. However that would gather a rather large amount
of data, requiring a custom tool to condense it into something we (as
humans) can understand. I don't have time to write the analysis tool,
but if someone else does I'm happy to provide the data.

An engineer would probably do a test series on various hardware
instead. Given the wide variety of hardware and file systems that
notmuch should work well with, that would be a good idea in itself.

Sascha
-- 
http://sascha.silbe.org/
http://www.infra-silbe.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 489 bytes
Desc: not available
URL: <http://notmuchmail.org/pipermail/notmuch/attachments/20120705/ce650dd4/attachment.pgp>