8f/0251b391b15382a4c4ec739819a590af50128b

   1 Return-Path: <amdragon@mit.edu>\r
   2 X-Original-To: notmuch@notmuchmail.org\r
   3 Delivered-To: notmuch@notmuchmail.org\r
   4 Received: from localhost (localhost [127.0.0.1])\r
   5         by olra.theworths.org (Postfix) with ESMTP id 9B42A431FB6\r
   6         for <notmuch@notmuchmail.org>; Mon, 25 Jun 2012 18:48:00 -0700 (PDT)\r
   7 X-Virus-Scanned: Debian amavisd-new at olra.theworths.org\r
   8 X-Spam-Flag: NO\r
   9 X-Spam-Score: -0.7\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=-0.7 tagged_above=-999 required=5\r
  12         tests=[RCVD_IN_DNSWL_LOW=-0.7] autolearn=disabled\r
  13 Received: from olra.theworths.org ([127.0.0.1])\r
  14         by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024)\r
  15         with ESMTP id uS-oFf0wmzln for <notmuch@notmuchmail.org>;\r
  16         Mon, 25 Jun 2012 18:47:58 -0700 (PDT)\r
  17 Received: from dmz-mailsec-scanner-3.mit.edu (DMZ-MAILSEC-SCANNER-3.MIT.EDU\r
  18         [18.9.25.14])\r
  19         by olra.theworths.org (Postfix) with ESMTP id 44F36431FAF\r
  20         for <notmuch@notmuchmail.org>; Mon, 25 Jun 2012 18:47:58 -0700 (PDT)\r
  21 X-AuditID: 1209190e-b7fb56d0000008b2-0c-4fe914cc9f7c\r
  22 Received: from mailhub-auth-4.mit.edu ( [18.7.62.39])\r
  23         by dmz-mailsec-scanner-3.mit.edu (Symantec Messaging Gateway) with SMTP\r
  24         id F7.2C.02226.CC419EF4; Mon, 25 Jun 2012 21:47:56 -0400 (EDT)\r
  25 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103])\r
  26         by mailhub-auth-4.mit.edu (8.13.8/8.9.2) with ESMTP id q5Q1ltJq011643; \r
  27         Mon, 25 Jun 2012 21:47:56 -0400\r
  28 Received: from awakening.csail.mit.edu (awakening.csail.mit.edu [18.26.4.91])\r
  29         (authenticated bits=0)\r
  30         (User authenticated as amdragon@ATHENA.MIT.EDU)\r
  31         by outgoing.mit.edu (8.13.6/8.12.4) with ESMTP id q5Q1lsP2026639\r
  32         (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT);\r
  33         Mon, 25 Jun 2012 21:47:55 -0400 (EDT)\r
  34 Received: from amthrax by awakening.csail.mit.edu with local (Exim 4.77)\r
  35         (envelope-from <amdragon@mit.edu>)\r
  36         id 1SjKsk-0005uu-9E; Mon, 25 Jun 2012 21:47:54 -0400\r
  37 Date: Mon, 25 Jun 2012 21:47:54 -0400\r
  38 From: Austin Clements <amdragon@MIT.EDU>\r
  39 To: Sascha Silbe <sascha-ml-reply-to-2012-3@silbe.org>\r
  40 Subject: Re: [PATCH 0/3] Speed up notmuch new for unchanged directories\r
  41 Message-ID: <20120626014754.GO24342@mit.edu>\r
  42 References: <1340555366-25891-1-git-send-email-sascha-pgp@silbe.org>\r
  43         <87pq8n1de4.fsf@awakening.csail.mit.edu>\r
  44         <toed34nyr8r.fsf@twin.sascha.silbe.org>\r
  45 MIME-Version: 1.0\r
  46 Content-Type: text/plain; charset=utf-8\r
  47 Content-Disposition: inline\r
  48 Content-Transfer-Encoding: 8bit\r
  49 In-Reply-To: <toed34nyr8r.fsf@twin.sascha.silbe.org>\r
  50 User-Agent: Mutt/1.5.21 (2010-09-15)\r
  51 X-Brightmail-Tracker:\r
  52  H4sIAAAAAAAAA+NgFlrBKsWRmVeSWpSXmKPExsUixG6nrntG5KW/wew7ehbXb85ktnj77Aaj\r
  53         A5PHs1W3mD02/v3BEsAUxWWTkpqTWZZapG+XwJWx4O58poKlyhW9xy+yNTBukOli5OSQEDCR\r
  54         2NvxhBnCFpO4cG89WxcjF4eQwD5GieN7G5ggnA2MEnMXnWKGcE4ySRy+cBasRUhgCaPE4h0x\r
  55         IDaLgKrE6cezGUFsNgENiW37l4PZIgJmEus3TwKrZwaqaVx7EcwWFnCXWPjmAhOIzSugI9E3\r
  56         9R/UtpmMEgfad0ElBCVOznzCAtGsLvFn3iWgZg4gW1pi+T8OiLC8RPPW2WAzOYHeufUdYpeo\r
  57         gIrElJPb2CYwCs9CMmkWkkmzECbNQjJpASPLKkbZlNwq3dzEzJzi1GTd4uTEvLzUIl1jvdzM\r
  58         Er3UlNJNjKBI4JTk28H49aDSIUYBDkYlHl6P+hf+QqyJZcWVuYcYJTmYlER5Q4Vf+gvxJeWn\r
  59         VGYkFmfEF5XmpBYfYpTgYFYS4d19A6icNyWxsiq1KB8mJc3BoiTOeyXlpr+QQHpiSWp2ampB\r
  60         ahFMVoaDQ0mCVwgY8UKCRanpqRVpmTklCGkmDk6Q4TxAw5VAaniLCxJzizPTIfKnGHU51r05\r
  61         coNRiCUvPy9VSpxXBaRIAKQoozQPbg4sgb1iFAd6S5j3K8gPPMDkBzfpFdASJqAlHJtAPigu\r
  62         SURISTUwruDRUuCeeF7qj1f8P1b90NIfXtba66JqfliF7HlyybRTUlnFuGSPvHu5L8dJvpI3\r
  63         wkm+F/1nn5C/edic6cCUpocR4cUmmy2/Rp/lZHMLNskzsLOp/OqatOHqK5Utd3+4bjNfvPq+\r
  64         wfSL3SoOUTckHfcHxfVZpL83tTy/v/O1zcHWS2f0XuUqsRRnJBpqMRcVJwIANU+9gjsDAAA=\r
  65 Cc: notmuch <notmuch@notmuchmail.org>\r
  66 X-BeenThere: notmuch@notmuchmail.org\r
  67 X-Mailman-Version: 2.1.13\r
  68 Precedence: list\r
  69 List-Id: "Use and development of the notmuch mail system."\r
  70         <notmuch.notmuchmail.org>\r
  71 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
  72         <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  73 List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
  74 List-Post: <mailto:notmuch@notmuchmail.org>\r
  75 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  76 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
  77         <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  78 X-List-Received-Date: Tue, 26 Jun 2012 01:48:00 -0000\r
  79 \r
  80 Quoth Sascha Silbe on Jun 26 at 12:13 am:\r
  81 > Austin Clements <amdragon@MIT.EDU> writes:\r
  82 > > On Sun, 24 Jun 2012, Sascha Silbe <sascha-pgp@silbe.org> wrote:\r
  83 > \r
  84 > ["notmuch new" listing every directory, even if it's unchanged]\r
  85 > > I haven't looked over your patches yet, but this result surprises me.\r
  86 > > Could you explain your setup a little more?  How much mail do you have\r
  87 > > and across how many directories?  What file system are you using?\r
  88 > \r
  89 > As mentioned in passing already, I have a total of about 900k unique\r
  90 > mails (sometimes several copies of them, received over different paths,\r
  91 > e.g. mailing list and a direct CC). Most of that is "old" mails, in\r
  92 > directories that are not getting updated. If notmuch would support mbox,\r
  93 > I'd use that instead for those old mails. The total number of\r
  94 > directories in the mail store is about 29k and the total number of files\r
  95 > (including the git repository and mbox files that sup used) is about\r
  96 > 1.25M.\r
  97 > \r
  98 > Since a housekeeping job last weekend, the number of mails in\r
  99 > directories that are still getting updated is about 4k, i.e. about 5‰ of\r
 100 > the total number of mails or 3‰ of the total number of files. The number\r
 101 > of directories getting updated is 104, i.e. about 4‰ of the total number\r
 102 > of directories.\r
 103 > \r
 104 > Ideally, we'd get the run-time of "notmuch new" down by a similar\r
 105 > factor. With just plain POSIX and no additional information that won't\r
 106 > be possible, but providing a way to channel information about updates\r
 107 > into notmuch (rather than having it scan everything over and over again)\r
 108 > should help. That information is already available as output from the\r
 109 > mail fetching process (rsync in my case). Of course, it would be purely\r
 110 > optional: "notmuch new" without additional information would simply\r
 111 > continue to scan everything.\r
 112 \r
 113 This would be great.  I've been thinking along similar lines for a\r
 114 while (in my case, I want to feed notmuch new from inotify), though I\r
 115 haven't written any code for it.\r
 116 \r
 117 > > I'm also surprised that your new approach helps.  This directory listing\r
 118 > > has to be read off disk one way or the other, but listing directories is\r
 119 > > the bread-and-butter of file systems, whereas I would think that Xapian\r
 120 > > would require more IO to accomplish the same effect.\r
 121 > \r
 122 > "notmuch new" needs to iterate over a list of all directories to find\r
 123 > those with new mails (and potentially new subdirectories). However, it\r
 124 > does not need to list the *contents* of those folders. I'm surprised as\r
 125 > well, but rather in the opposite direction: Based on a naive\r
 126 > calculation, we'd expect to see a speedup on the order of\r
 127 > (1.25M+29k)/29k = 44. The actual results suggest that stat()ing (done\r
 128 > 29k times both before and after the patch) is taking about 19 times as\r
 129 > long as listing a directory entry (before the patch we listed 1M\r
 130 > entries, now we list none if nothing has changed). (*)\r
 131 \r
 132 For a cold cache, these aren't the numbers that matter.  With an HDD\r
 133 and how few files your directories contain on average, only seeks will\r
 134 matter.  I would expect your workload without your patch to have at\r
 135 least 1 but closer to 2 seeks per directory: one to stat the directory\r
 136 and one to get the directory contents block.  Some of the stat seeks\r
 137 will be eliminated by the buffer cache, even starting cold, because of\r
 138 inode locality (absolute best case is 16x reduction, but if you\r
 139 created the directories over time, then this locality is probably\r
 140 quite poor).  There are a few other potential seeks to get the\r
 141 directory document from Xapian and to get its mtime value, but those\r
 142 should exhibit strong locality, so they probably don't contribute\r
 143 much.  NewEgg says your drive has an average seek time of 8.9ms, so\r
 144 with 29k directories and assuming your directories are sequential on\r
 145 disk, that's at least 258s and closer to 512s, which agrees with your\r
 146 benchmark results.\r
 147 \r
 148 I'm surprised by your results because I would expect your workload\r
 149 with your patches to exhibit about the same number of seeks: one to\r
 150 stat the directory (same as before) and one for\r
 151 notmuch_directory_get_child_files, which has to seek in the term index\r
 152 to get the child directories.  My guess is that this exhibits better\r
 153 locality because the child directory terms are stored contiguously in\r
 154 the database's key space (though not necessarily sequentially on disk\r
 155 unless this is a fresh database).\r
 156 \r
 157 Unfortunately, I'm not sure of a good way to test this hypothesis.\r
 158 Any thoughts?\r