From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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----- --=-=-=--