From a2875fa95f779ce59edb2e94afd672f1e8d79da2 Mon Sep 17 00:00:00 2001 From: Sascha Silbe Date: Thu, 5 Jul 2012 09:37:22 +0200 Subject: [PATCH] Re: [PATCH 0/3] Speed up notmuch new for unchanged directories --- 30/1276127aa341da20bfb7e0d6e4a8810b0d597c | 143 ++++++++++++++++++++++ 1 file changed, 143 insertions(+) create mode 100644 30/1276127aa341da20bfb7e0d6e4a8810b0d597c diff --git a/30/1276127aa341da20bfb7e0d6e4a8810b0d597c b/30/1276127aa341da20bfb7e0d6e4a8810b0d597c new file mode 100644 index 000000000..cae353f9b --- /dev/null +++ b/30/1276127aa341da20bfb7e0d6e4a8810b0d597c @@ -0,0 +1,143 @@ +Return-Path: +X-Original-To: notmuch@notmuchmail.org +Delivered-To: notmuch@notmuchmail.org +Received: from localhost (localhost [127.0.0.1]) + by olra.theworths.org (Postfix) with ESMTP id 2D515431FB6 + for ; Thu, 5 Jul 2012 00:37:54 -0700 (PDT) +X-Virus-Scanned: Debian amavisd-new at olra.theworths.org +X-Spam-Flag: NO +X-Spam-Score: 0 +X-Spam-Level: +X-Spam-Status: No, score=0 tagged_above=-999 required=5 tests=[none] + autolearn=disabled +Received: from olra.theworths.org ([127.0.0.1]) + by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024) + with ESMTP id UhgVPmhv0SUU for ; + Thu, 5 Jul 2012 00:37:53 -0700 (PDT) +Received: from smtp.chost.de (setoy.chost.de [217.160.209.225]) + (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) + (No client certificate requested) + by olra.theworths.org (Postfix) with ESMTPS id DD975431FAE + for ; Thu, 5 Jul 2012 00:37:52 -0700 (PDT) +Received: (qmail 1719 invoked by uid 5015); 5 Jul 2012 07:37:48 -0000 +Received: (nullmailer pid 19070 invoked by uid 123); + Thu, 05 Jul 2012 07:37:48 -0000 +Received: from twin.sascha.silbe.org (twin.sascha.silbe.org [192.168.1.2]) + by flatty.sascha.silbe.org ([192.168.1.252]) + with SMTP via TCP; 05 Jul 2012 07:37:48 -0000 +Received: (nullmailer pid 10893 invoked by uid 8193); + Thu, 05 Jul 2012 07:37:48 -0000 +To: Austin Clements , notmuch +Subject: Re: [PATCH 0/3] Speed up notmuch new for unchanged directories +In-Reply-To: <20120626014754.GO24342@mit.edu> +References: <1340555366-25891-1-git-send-email-sascha-pgp@silbe.org> + <87pq8n1de4.fsf@awakening.csail.mit.edu> + + <20120626014754.GO24342@mit.edu> +User-Agent: Notmuch/0.13.2+51~gecf7cfe (http://notmuchmail.org) Emacs/23.2.1 + (x86_64-pc-linux-gnu) +Date: Thu, 05 Jul 2012 09:37:22 +0200 +Message-ID: +MIME-Version: 1.0 +Content-Type: multipart/signed; boundary="=-=-="; + micalg=pgp-sha512; protocol="application/pgp-signature" +From: Sascha Silbe +X-BeenThere: notmuch@notmuchmail.org +X-Mailman-Version: 2.1.13 +Precedence: list +List-Id: "Use and development of the notmuch mail system." + +List-Unsubscribe: , + +List-Archive: +List-Post: +List-Help: +List-Subscribe: , + +X-List-Received-Date: Thu, 05 Jul 2012 07:37:54 -0000 + +--=-=-= +Content-Type: text/plain; charset=utf-8 +Content-Transfer-Encoding: quoted-printable + +Austin Clements 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=C2=A0=3D=C2=A044. 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 +=2D-=20 +http://sascha.silbe.org/ +http://www.infra-silbe.de/ + +--=-=-= +Content-Type: application/pgp-signature + +-----BEGIN PGP SIGNATURE----- +Version: GnuPG v1.4.10 (GNU/Linux) + +iQEcBAEBCgAGBQJP9UQzAAoJELpz82VMF3Dae+cH/jGO/XftuSdBnegEdKOu4P7O +ANKgrfMIBaF8sbX+ftP4LisP6KO8jB/8/mwk4f9vmvvoP1+IMpHcJ2MLE/TzcDlq +H8se7xL1rr1uWOfheVZdB9mBzf0Ag03xcjSxBo9yIbaVMwF6XXeeSXGirhichzhk +6/2Gm9JjoFmjTrm3sQEs/nlV5SlxgyxblzrJWgQIuoDRTl0dw9duDk5zSY28ih3g +u8Y5NwIyBVF9zPMFXMCIyfV2Zwhowv5bt1Vfc0iw+l7mKS0P0YKnShEVAXP48kE9 +vd/6cKljSTyWGsQZri1N4jCIL1Kskx3Gfi3376zNaux+CC+7kX6g/D0guFAj1eM= +=ncvA +-----END PGP SIGNATURE----- +--=-=-=-- -- 2.26.2