From: Carl Worth <cworth@cworth.org>
To: Austin Clements <amdragon@MIT.EDU>, notmuch@notmuchmail.org
Subject: Re: [PATCH 3/4] Optimize thread search using matched docid sets.
In-Reply-To: <20101118073828.GD2439@mit.edu>
References: <20101117192826.GU2439@mit.edu> <20101118073828.GD2439@mit.edu>
User-Agent: Notmuch/0.5 (http://notmuchmail.org) Emacs/23.2.1
	(i486-pc-linux-gnu)
Date: Tue, 07 Dec 2010 17:20:22 -0800
Message-ID: <8739q95acp.fsf@yoom.home.cworth.org>
MIME-Version: 1.0
Content-Type: multipart/signed; boundary="=-=-=";
	micalg=pgp-sha1; protocol="application/pgp-signature"
Precedence: list

--=-=-=
Content-Transfer-Encoding: quoted-printable

On Thu, 18 Nov 2010 02:38:29 -0500, Austin Clements <amdragon@MIT.EDU> wrot=
e:
> Currently this code uses a bitmap indexed by docid as a simple, fast
> set structure.  This is quite memory-efficient if the docid space is
> dense, even if the largest docid is quite large.  Is there a danger
> that the docid space will be large and sparse?  Is it worth replacing
> this with a smarter bit set structure?

When simply adding messages, the docid space is optimally dense, (see
_notmuch_database_generate_doc_id which generates sequential docid
values).

As messages are removed, the space will become less dense as there is
currently never any reuse of docid values. We could imagine adding some
sort of packing operation to get back to dense packing, (but forcing
that kind of thing on the user isn't so kind, of course).

Meanwhile, Xapian can very efficiently tell us how packed the space is,
(since we can query document count and the last docid allocated). So we
definitely have the ability to tune things automatically if needed.

We're currently using GHashTable in several places, but I've thought of
incorporating a nice, little hash-table implementation that Eric Anholt
wrote some time ago. If we did that, we could intelligently choose
whichever data structure is more memory-efficient depending on how
packed the docid space is.

Personally, though, I'm not that much of a micro-optimizer. As can be
seen in the current thread, I generally leave the optimization to
others. Thanks again, Austin!

=2DCarl

=2D-=20
carl.d.worth@intel.com

--=-=-=
Content-Type: application/pgp-signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)

iD8DBQFM/t1W6JDdNq8qSWgRAlgPAJ0b4Zv0IZ56UlbnwCcJW9r+oJbLKwCgp4bF
iiF7G8qs3IhtYeYdIwDPXA0=
=8kfY
-----END PGP SIGNATURE-----
--=-=-=--