99/1f7f5d2ba5750c79d83d19584ae734fd4cc2c1

   1 Return-Path: <cworth@cworth.org>\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 1EE5E41A549\r
   6         for <notmuch@notmuchmail.org>; Tue,  7 Dec 2010 17:20:24 -0800 (PST)\r
   7 X-Virus-Scanned: Debian amavisd-new at olra.theworths.org\r
   8 X-Spam-Flag: NO\r
   9 X-Spam-Score: -0.99\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=-0.99 tagged_above=-999 required=5\r
  12         tests=[ALL_TRUSTED=-1, T_MIME_NO_TEXT=0.01] 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 G8WqHwg4DOoP; Tue,  7 Dec 2010 17:20:23 -0800 (PST)\r
  16 Received: from yoom.home.cworth.org (localhost [127.0.0.1])\r
  17         by olra.theworths.org (Postfix) with ESMTP id 6506D431FB5;\r
  18         Tue,  7 Dec 2010 17:20:23 -0800 (PST)\r
  19 Received: by yoom.home.cworth.org (Postfix, from userid 1000)\r
  20         id 176F02540E7; Tue,  7 Dec 2010 17:20:23 -0800 (PST)\r
  21 From: Carl Worth <cworth@cworth.org>\r
  22 To: Austin Clements <amdragon@MIT.EDU>, notmuch@notmuchmail.org\r
  23 Subject: Re: [PATCH 3/4] Optimize thread search using matched docid sets.\r
  24 In-Reply-To: <20101118073828.GD2439@mit.edu>\r
  25 References: <20101117192826.GU2439@mit.edu> <20101118073828.GD2439@mit.edu>\r
  26 User-Agent: Notmuch/0.5 (http://notmuchmail.org) Emacs/23.2.1\r
  27         (i486-pc-linux-gnu)\r
  28 Date: Tue, 07 Dec 2010 17:20:22 -0800\r
  29 Message-ID: <8739q95acp.fsf@yoom.home.cworth.org>\r
  30 MIME-Version: 1.0\r
  31 Content-Type: multipart/signed; boundary="=-=-=";\r
  32         micalg=pgp-sha1; protocol="application/pgp-signature"\r
  33 X-BeenThere: notmuch@notmuchmail.org\r
  34 X-Mailman-Version: 2.1.13\r
  35 Precedence: list\r
  36 List-Id: "Use and development of the notmuch mail system."\r
  37         <notmuch.notmuchmail.org>\r
  38 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
  39         <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  40 List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
  41 List-Post: <mailto:notmuch@notmuchmail.org>\r
  42 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  43 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
  44         <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  45 X-List-Received-Date: Wed, 08 Dec 2010 01:20:24 -0000\r
  46 \r
  47 --=-=-=\r
  48 Content-Transfer-Encoding: quoted-printable\r
  49 \r
  50 On Thu, 18 Nov 2010 02:38:29 -0500, Austin Clements <amdragon@MIT.EDU> wrot=\r
  51 e:\r
  52 > Currently this code uses a bitmap indexed by docid as a simple, fast\r
  53 > set structure.  This is quite memory-efficient if the docid space is\r
  54 > dense, even if the largest docid is quite large.  Is there a danger\r
  55 > that the docid space will be large and sparse?  Is it worth replacing\r
  56 > this with a smarter bit set structure?\r
  57 \r
  58 When simply adding messages, the docid space is optimally dense, (see\r
  59 _notmuch_database_generate_doc_id which generates sequential docid\r
  60 values).\r
  61 \r
  62 As messages are removed, the space will become less dense as there is\r
  63 currently never any reuse of docid values. We could imagine adding some\r
  64 sort of packing operation to get back to dense packing, (but forcing\r
  65 that kind of thing on the user isn't so kind, of course).\r
  66 \r
  67 Meanwhile, Xapian can very efficiently tell us how packed the space is,\r
  68 (since we can query document count and the last docid allocated). So we\r
  69 definitely have the ability to tune things automatically if needed.\r
  70 \r
  71 We're currently using GHashTable in several places, but I've thought of\r
  72 incorporating a nice, little hash-table implementation that Eric Anholt\r
  73 wrote some time ago. If we did that, we could intelligently choose\r
  74 whichever data structure is more memory-efficient depending on how\r
  75 packed the docid space is.\r
  76 \r
  77 Personally, though, I'm not that much of a micro-optimizer. As can be\r
  78 seen in the current thread, I generally leave the optimization to\r
  79 others. Thanks again, Austin!\r
  80 \r
  81 =2DCarl\r
  82 \r
  83 =2D-=20\r
  84 carl.d.worth@intel.com\r
  85 \r
  86 --=-=-=\r
  87 Content-Type: application/pgp-signature\r
  88 \r
  89 -----BEGIN PGP SIGNATURE-----\r
  90 Version: GnuPG v1.4.10 (GNU/Linux)\r
  91 \r
  92 iD8DBQFM/t1W6JDdNq8qSWgRAlgPAJ0b4Zv0IZ56UlbnwCcJW9r+oJbLKwCgp4bF\r
  93 iiF7G8qs3IhtYeYdIwDPXA0=\r
  94 =8kfY\r
  95 -----END PGP SIGNATURE-----\r
  96 --=-=-=--\r