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

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

[Sascha Silbe]

All the time I thought what makes "notmuch new" so abysmally slow is the
stat() for each maildir. But as it continued to be slow even after I
moved most mails out of 'new' (into 'new-20120624'), I strace'd notmuch
and noticed it listed even unchanged directories, thereby listing and
iterating over each and every single of the 900k mails in my mail store.

There's still quite some room for further improvements as it continues
to take several minutes to scan < 100 new mails in changed directories
containing < 1000 mails in total. Even the rsync run that fetches the
new mails is faster.

Sascha Silbe (3):
  lib: fix NULL checks for filenames iterators
  lib: add support for rewinding a filenames iterator
  new: don't read unchanged directories from disk

 lib/filenames.c |   15 ++++++-
 lib/notmuch.h   |    8 ++++
 notmuch-new.c   |  130 +++++++++++++++++++++++++++++++++++++++++--------------
 3 files changed, 119 insertions(+), 34 deletions(-)

-- 
1.7.10

[PATCH 1/3] lib: fix NULL checks for filenames iterators

[Sascha Silbe]

The API documentation (notmuch.h) states that the parameter may be NULL,
but the implementation only checked the current element, potentially
dereferencing a NULL pointer in the process.

Signed-off-by: Sascha Silbe <sascha-pgp@silbe.org>
---
 lib/filenames.c |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/filenames.c b/lib/filenames.c
index f1ea243..4f7c0d8 100644
--- a/lib/filenames.c
+++ b/lib/filenames.c
@@ -54,7 +54,7 @@ notmuch_filenames_valid (notmuch_filenames_t *filenames)
 const char *
 notmuch_filenames_get (notmuch_filenames_t *filenames)
 {
-    if (filenames->iterator == NULL)
+    if ((filenames == NULL) || (filenames->iterator == NULL))
 	return NULL;
 
     return filenames->iterator->string;
@@ -63,7 +63,7 @@ notmuch_filenames_get (notmuch_filenames_t *filenames)
 void
 notmuch_filenames_move_to_next (notmuch_filenames_t *filenames)
 {
-    if (filenames->iterator == NULL)
+    if ((filenames == NULL) || (filenames->iterator == NULL))
 	return;
 
     filenames->iterator = filenames->iterator->next;
-- 
1.7.10

Re: [PATCH 1/3] lib: fix NULL checks for filenames iterators

[David Bremner]

Sascha Silbe <sascha-pgp@silbe.org> writes:

> The API documentation (notmuch.h) states that the parameter may be NULL,
> but the implementation only checked the current element, potentially
> dereferencing a NULL pointer in the process.
>

Pushed this one patch.

d

[PATCH 2/3] lib: add support for rewinding a filenames iterator

[Sascha Silbe]

This allows the same iterator to be traversed multiple times, instead of
destroying and reconstructing it.

Signed-off-by: Sascha Silbe <sascha-pgp@silbe.org>
---
 lib/filenames.c |   11 +++++++++++
 lib/notmuch.h   |    8 ++++++++
 2 files changed, 19 insertions(+)

diff --git a/lib/filenames.c b/lib/filenames.c
index 4f7c0d8..62ccb39 100644
--- a/lib/filenames.c
+++ b/lib/filenames.c
@@ -21,6 +21,7 @@
 #include "notmuch-private.h"
 
 struct _notmuch_filenames {
+    notmuch_string_node_t *first;
     notmuch_string_node_t *iterator;
 };
 
@@ -36,6 +37,7 @@ _notmuch_filenames_create (const void *ctx,
     if (unlikely (filenames == NULL))
 	return NULL;
 
+    filenames->first = list->head;
     filenames->iterator = list->head;
     (void) talloc_reference (filenames, list);
 
@@ -70,6 +72,15 @@ notmuch_filenames_move_to_next (notmuch_filenames_t *filenames)
 }
 
 void
+notmuch_filenames_rewind (notmuch_filenames_t *filenames)
+{
+    if (filenames == NULL)
+	return;
+
+    filenames->iterator = filenames->first;
+}
+
+void
 notmuch_filenames_destroy (notmuch_filenames_t *filenames)
 {
     talloc_free (filenames);
diff --git a/lib/notmuch.h b/lib/notmuch.h
index 3633bed..e99e2a3 100644
--- a/lib/notmuch.h
+++ b/lib/notmuch.h
@@ -1382,6 +1382,14 @@ notmuch_filenames_get (notmuch_filenames_t *filenames);
 void
 notmuch_filenames_move_to_next (notmuch_filenames_t *filenames);
 
+/* Move the 'filenames' iterator back to the first filename.
+ *
+ * It is acceptable to pass NULL for 'filenames', in which case this
+ * function will do nothing.
+ */
+void
+notmuch_filenames_rewind (notmuch_filenames_t *filenames);
+
 /* Destroy a notmuch_filenames_t object.
  *
  * It's not strictly necessary to call this function. All memory from
-- 
1.7.10

[PATCH 3/3] new: don't read unchanged directories from disk

[Sascha Silbe]

Previously, notmuch new listed all directories on disk, even if they
were unchanged from the state recorded in the database. This could take
a huge amount of time for large numbers of mails as it would list each
individual mail.

By iterating over the subdirectories recorded in the database we can
avoid accessing the file system for each unchanged directory. If the
modification time does not match we fall back to a full file system scan
so new subdirectories will get picked up and scanned recursively.

Timings for an Athlon BE-2300 with 4GiB RAM and a Samsung HD204UI hard
disk containing a mail store of around 900k mails, for the "no new mail"
case, three samples each:

Hot cache (first run discarded):
	Before			After				Speedup
real	mean 5.0s stdev 0.1s	mean 1.8s stdev 0.1s	2.8
user	mean 2.4s stdev 0.1s	mean 1.0s stdev 0.1s	2.4
sys	mean 2.6s stdev 0.0s	mean 0.9s stdev 0.0s	2.9

Cold cache on each run:
	Before			After				Speedup
real	mean 433s stdev 1.2s	mean 130s stdev 0.1s	3.3
user	mean 6.0s stdev 0.2s	mean 2.5s stdev 0.0s	2.4
sys	mean 6.7s stdev 0.1s	mean 2.8s stdev 0.1s	2.4

Signed-off-by: Sascha Silbe <sascha-pgp@silbe.org>
---
 notmuch-new.c |  130 +++++++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 98 insertions(+), 32 deletions(-)

diff --git a/notmuch-new.c b/notmuch-new.c
index 938ae29..93feb5c 100644
--- a/notmuch-new.c
+++ b/notmuch-new.c
@@ -225,6 +225,33 @@ _entries_resemble_maildir (const char *path, struct dirent **entries, int count)
     return 0;
 }
 
+/* Test if a directory recorded in the database looks like a Maildir directory.
+ *
+ * Search through the iterator of directory entries to see if we can find all
+ * three subdirectories typical for Maildir, that is "new", "cur", and "tmp".
+ *
+ * Return 1 if the directory looks like a Maildir and 0 otherwise.
+ */
+static int
+_subdirs_resemble_maildir (notmuch_filenames_t *db_subdirs)
+{
+    int found = 0;
+
+    while (notmuch_filenames_valid(db_subdirs) && found != 3)
+    {
+	const char *filename = notmuch_filenames_get(db_subdirs);
+
+	if (strcmp(filename, "new") == 0 || strcmp(filename, "cur") == 0 ||
+	    strcmp(filename, "tmp") == 0)
+	{
+	    found++;
+	}
+	notmuch_filenames_move_to_next (db_subdirs);
+    }
+
+    return (found == 3) ? 1 : 0 ;
+}
+
 /* Test if the file/directory is to be ignored.
  */
 static notmuch_bool_t
@@ -243,20 +270,22 @@ _entry_in_ignore_list (const char *entry, add_files_state_t *state)
  *
  *   o Ask the filesystem for the mtime of 'path' (fs_mtime)
  *   o Ask the database for its timestamp of 'path' (db_mtime)
+ *   o Ask the database for directories within 'path' (db_subdirs)
  *
- *   o Ask the filesystem for files and directories within 'path'
- *     (via scandir and stored in fs_entries)
+ *   o If fs_mtime is newer than db_mtime, ask the filesystem for
+ *     files and directories within 'path' (via scandir and stored in
+ *     fs_entries)
  *
- *   o Pass 1: For each directory in fs_entries, recursively call into
- *     this same function.
+ *   o Pass 1: For each subdirectory, recursively call into this same
+ *     function. If fs_mtime is newer than db_mtime, scan fs_entries
+ *     for subdirectories. Otherwise use the database (db_subdirs).
  *
  *   o Compare fs_mtime to db_mtime. If they are equivalent, terminate
  *     the algorithm at this point, (this directory has not been
  *     updated in the filesystem since the last database scan of PASS
  *     2).
  *
- *   o Ask the database for files and directories within 'path'
- *     (db_files and db_subdirs)
+ *   o Ask the database for files within 'path' (db_files)
  *
  *   o Pass 2: Walk fs_entries simultaneously with db_files and
  *     db_subdirs. Look for one of three interesting cases:
@@ -321,28 +350,48 @@ add_files (notmuch_database_t *notmuch,
 	goto DONE;
     }
     db_mtime = directory ? notmuch_directory_get_mtime (directory) : 0;
+    if (directory)
+	db_subdirs = notmuch_directory_get_child_directories (directory);
 
-    /* If the database knows about this directory, then we sort based
-     * on strcmp to match the database sorting. Otherwise, we can do
-     * inode-based sorting for faster filesystem operation. */
-    num_fs_entries = scandir (path, &fs_entries, 0,
-			      directory ?
-			      dirent_sort_strcmp_name : dirent_sort_inode);
+    /* If the directory's modification time in the filesystem is the
+     * same as what we recorded in the database the last time we
+     * scanned it, then we can skip reading the entries from disk.
+     *
+     * We test for strict equality here to avoid a bug that can happen
+     * if the system clock jumps backward, (preventing new mail from
+     * being discovered until the clock catches up and the directory
+     * is modified again).
+     */
+    if (fs_mtime != db_mtime)
+    {
+	/* If the database knows about this directory, then we sort based
+	 * on strcmp to match the database sorting. Otherwise, we can do
+	 * inode-based sorting for faster filesystem operation. */
+	num_fs_entries = scandir (path, &fs_entries, 0,
+				  directory ?
+				  dirent_sort_strcmp_name : dirent_sort_inode);
+
+	if (num_fs_entries == -1) {
+	    fprintf (stderr, "Error opening directory %s: %s\n",
+		     path, strerror (errno));
+	    /* We consider this a fatal error because, if a user moved a
+	     * message from another directory that we were able to scan
+	     * into this directory, skipping this directory will cause
+	     * that message to be lost. */
+	    ret = NOTMUCH_STATUS_FILE_ERROR;
+	    goto DONE;
+	}
+    }
 
-    if (num_fs_entries == -1) {
-	fprintf (stderr, "Error opening directory %s: %s\n",
-		 path, strerror (errno));
-	/* We consider this a fatal error because, if a user moved a
-	 * message from another directory that we were able to scan
-	 * into this directory, skipping this directory will cause
-	 * that message to be lost. */
-	ret = NOTMUCH_STATUS_FILE_ERROR;
-	goto DONE;
+    if (fs_entries)
+	is_maildir = _entries_resemble_maildir (path, fs_entries, num_fs_entries);
+    else
+    {
+	is_maildir = _subdirs_resemble_maildir (db_subdirs);
+	notmuch_filenames_rewind(db_subdirs);
     }
 
     /* Pass 1: Recurse into all sub-directories. */
-    is_maildir = _entries_resemble_maildir (path, fs_entries, num_fs_entries);
-
     for (i = 0; i < num_fs_entries; i++) {
 	if (interrupted)
 	    break;
@@ -386,24 +435,41 @@ add_files (notmuch_database_t *notmuch,
 	next = NULL;
     }
 
+    /* Reading the directory from disk was skipped because it hasn't
+     * changed since the last time we scanned it. Recurse over the
+     * subdirectories using the database instead.
+     */
+    while (!fs_entries && notmuch_filenames_valid (db_subdirs))
+    {
+	const char *filename = notmuch_filenames_get (db_subdirs);
+	if (interrupted)
+	    break;
+
+	next = talloc_asprintf (notmuch, "%s/%s", path, filename);
+	if (!_entry_in_ignore_list (filename, state) && stat (next, &st) == 0)
+	{
+	    status = add_files (notmuch, next, state);
+	    if (status) {
+		ret = status;
+		goto DONE;
+	    }
+	}
+	talloc_free (next);
+	next = NULL;
+	notmuch_filenames_move_to_next (db_subdirs);
+    }
+
     /* If the directory's modification time in the filesystem is the
      * same as what we recorded in the database the last time we
      * scanned it, then we can skip the second pass entirely.
-     *
-     * We test for strict equality here to avoid a bug that can happen
-     * if the system clock jumps backward, (preventing new mail from
-     * being discovered until the clock catches up and the directory
-     * is modified again).
      */
     if (directory && fs_mtime == db_mtime)
 	goto DONE;
 
     /* If the database has never seen this directory before, we can
-     * simply leave db_files and db_subdirs NULL. */
-    if (directory) {
+     * simply leave db_files NULL. */
+    if (directory)
 	db_files = notmuch_directory_get_child_files (directory);
-	db_subdirs = notmuch_directory_get_child_directories (directory);
-    }
 
     /* Pass 2: Scan for new files, removed files, and removed directories. */
     for (i = 0; i < num_fs_entries; i++)
-- 
1.7.10

Re: [PATCH 3/3] new: don't read unchanged directories from disk

[Ethan Glasser-Camp]

Sascha Silbe <sascha-pgp@silbe.org> writes:

> Previously, notmuch new listed all directories on disk, even if they
> were unchanged from the state recorded in the database. This could take
> a huge amount of time for large numbers of mails as it would list each
> individual mail.
>
> By iterating over the subdirectories recorded in the database we can
> avoid accessing the file system for each unchanged directory. If the
> modification time does not match we fall back to a full file system scan
> so new subdirectories will get picked up and scanned recursively.

Hi! Just going through the patch queue. These patches look fine to me,
but I think architecturally, notmuch needs to decide what it wants to do
-- if it wants to optimize directory-rescanning, or if it wants to
provide a better way to just add files known to be new, and let mail
delivery hook into that system. I'd prefer the second, but I think it's
OK to merge working code that does the first in the meantime. The
perfect is the enemy of the good.

Austin raised some concerns on this patch set that I'm not sure were
completely addressed. For my part, it seems intuitive that a stat()
would be faster than a scandir() and so I would have no problem with
merging this series.

Ethan

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

[Austin Clements]

On Sun, 24 Jun 2012, Sascha Silbe <sascha-pgp@silbe.org> wrote:
> All the time I thought what makes "notmuch new" so abysmally slow is the
> stat() for each maildir. But as it continued to be slow even after I
> moved most mails out of 'new' (into 'new-20120624'), I strace'd notmuch
> and noticed it listed even unchanged directories, thereby listing and
> iterating over each and every single of the 900k mails in my mail store.
>
> There's still quite some room for further improvements as it continues
> to take several minutes to scan < 100 new mails in changed directories
> containing < 1000 mails in total. Even the rsync run that fetches the
> new mails is faster.

I haven't looked over your patches yet, but this result surprises me.
Could you explain your setup a little more?  How much mail do you have
and across how many directories?  What file system are you using?

I'm also surprised that your new approach helps.  This directory listing
has to be read off disk one way or the other, but listing directories is
the bread-and-butter of file systems, whereas I would think that Xapian
would require more IO to accomplish the same effect.  Does your patch
win because you can specifically list subdirectories out of Xapian,
making the IO proportional to the number of subdirectories instead of
the number of subdirectories and files (even though the constant factors
probably favor reading from the file system)?

I like the idea of these patches, I just want to make sure I have a firm
grip on what's being optimized and why it wins.

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

[Sascha Silbe]

[-- Attachment #1: Type: text/plain, Size: 3997 bytes --]

Austin Clements <amdragon@MIT.EDU> writes:

> On Sun, 24 Jun 2012, Sascha Silbe <sascha-pgp@silbe.org> wrote:

["notmuch new" listing every directory, even if it's unchanged]
> I haven't looked over your patches yet, but this result surprises me.
> Could you explain your setup a little more?  How much mail do you have
> and across how many directories?  What file system are you using?

As mentioned in passing already, I have a total of about 900k unique
mails (sometimes several copies of them, received over different paths,
e.g. mailing list and a direct CC). Most of that is "old" mails, in
directories that are not getting updated. If notmuch would support mbox,
I'd use that instead for those old mails. The total number of
directories in the mail store is about 29k and the total number of files
(including the git repository and mbox files that sup used) is about
1.25M.

Since a housekeeping job last weekend, the number of mails in
directories that are still getting updated is about 4k, i.e. about 5‰ of
the total number of mails or 3‰ of the total number of files. The number
of directories getting updated is 104, i.e. about 4‰ of the total number
of directories.

Ideally, we'd get the run-time of "notmuch new" down by a similar
factor. With just plain POSIX and no additional information that won't
be possible, but providing a way to channel information about updates
into notmuch (rather than having it scan everything over and over again)
should help. That information is already available as output from the
mail fetching process (rsync in my case). Of course, it would be purely
optional: "notmuch new" without additional information would simply
continue to scan everything.


> I'm also surprised that your new approach helps.  This directory listing
> has to be read off disk one way or the other, but listing directories is
> the bread-and-butter of file systems, whereas I would think that Xapian
> would require more IO to accomplish the same effect.

"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). (*)

In practice, the speedup achieved by my patch is larger than what the
benchmark suggests because there are other processes running that use
RAM. If we need to read a lot from disk (like "notmuch new" did before
my patch), there's a good chance it's already been evicted from the
cache since the last run. The fewer we need to read, the more likely it
is to still be in the cache. Similarly, reading lots of data from disk
will displace other data in the cache. These effects are not covered by
the pure "hot cache" and "cold cache" timings.


> Does your patch win because you can specifically list subdirectories
> out of Xapian, making the IO proportional to the number of
> subdirectories instead of the number of subdirectories and files (even
> though the constant factors probably favor reading from the file
> system)?

It wins because the factor is the number of files in each directory, not
just some low constant based on file system overhead vs. Xapian
overhead.


> I like the idea of these patches, I just want to make sure I have a firm
> grip on what's being optimized and why it wins.

Certainly a good idea. Thanks for taking the time!

Sascha

(*) float(linsolve([29000*x + 1250000*y = 3.3 * 29000*x], [x])); in
    maxima, if you'd like to check the math.
-- 
http://sascha.silbe.org/
http://www.infra-silbe.de/

[-- Attachment #2: Type: application/pgp-signature, Size: 489 bytes --]

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

[Austin Clements]

Quoth Sascha Silbe on Jun 26 at 12:13 am:
> Austin Clements <amdragon@MIT.EDU> writes:
> > On Sun, 24 Jun 2012, Sascha Silbe <sascha-pgp@silbe.org> wrote:
> 
> ["notmuch new" listing every directory, even if it's unchanged]
> > I haven't looked over your patches yet, but this result surprises me.
> > Could you explain your setup a little more?  How much mail do you have
> > and across how many directories?  What file system are you using?
> 
> As mentioned in passing already, I have a total of about 900k unique
> mails (sometimes several copies of them, received over different paths,
> e.g. mailing list and a direct CC). Most of that is "old" mails, in
> directories that are not getting updated. If notmuch would support mbox,
> I'd use that instead for those old mails. The total number of
> directories in the mail store is about 29k and the total number of files
> (including the git repository and mbox files that sup used) is about
> 1.25M.
> 
> Since a housekeeping job last weekend, the number of mails in
> directories that are still getting updated is about 4k, i.e. about 5‰ of
> the total number of mails or 3‰ of the total number of files. The number
> of directories getting updated is 104, i.e. about 4‰ of the total number
> of directories.
> 
> Ideally, we'd get the run-time of "notmuch new" down by a similar
> factor. With just plain POSIX and no additional information that won't
> be possible, but providing a way to channel information about updates
> into notmuch (rather than having it scan everything over and over again)
> should help. That information is already available as output from the
> mail fetching process (rsync in my case). Of course, it would be purely
> optional: "notmuch new" without additional information would simply
> continue to scan everything.

This would be great.  I've been thinking along similar lines for a
while (in my case, I want to feed notmuch new from inotify), though I
haven't written any code for it.

> > I'm also surprised that your new approach helps.  This directory listing
> > has to be read off disk one way or the other, but listing directories is
> > the bread-and-butter of file systems, whereas I would think that Xapian
> > would require more IO to accomplish the same effect.
> 
> "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.  Some of the stat seeks
will be eliminated by the buffer cache, even starting cold, because of
inode locality (absolute best case is 16x reduction, but if you
created the directories over time, then this locality is probably
quite poor).  There are a few other potential seeks to get the
directory document from Xapian and to get its mtime value, but those
should exhibit strong locality, so they probably don't contribute
much.  NewEgg says your drive has an average seek time of 8.9ms, so
with 29k directories and assuming your directories are sequential on
disk, that's at least 258s and closer to 512s, which agrees with your
benchmark results.

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).

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

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

[Sascha Silbe]

[-- Attachment #1: Type: text/plain, Size: 3342 bytes --]

Austin Clements <amdragon@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/

[-- Attachment #2: Type: application/pgp-signature, Size: 489 bytes --]