[PATCH 3/4] Optimize thread search using matched docid sets.

[PATCH 3/4] Optimize thread search using matched docid sets.

[Austin Clements]

This reduces thread search's 1+2t Xapian queries (where t is the
number of matched threads) to 1+t queries and constructs exactly one
notmuch_message_t for each message instead of 2 to 3.
notmuch_query_search_threads eagerly fetches the docids of all
messages matching the user query instead of lazily constructing
message objects and fetching thread ID's from term lists.
_notmuch_thread_create takes a seed docid and the set of all matched
docids and uses a single Xapian query to expand this docid to its
containing thread, using the matched docid set to determine which
messages in the thread match the user query instead of using a second
Xapian query.

As a side effect, this fixes author order so authors are always sorted
by first occurrence in each thread.  This breaks two emacs tests that
hard-code the old, buggy author order.

This reduces the amount of time required to load my inbox from 4.523
seconds to 3.025 seconds (1.5X faster).
---
 lib/message.cc        |    6 ++
 lib/notmuch-private.h |   17 +++++-
 lib/query.cc          |  142 ++++++++++++++++++++++++++++++++++++------------
 lib/thread.cc         |  102 ++++++++++-------------------------
 test/emacs            |    4 +-
 5 files changed, 158 insertions(+), 113 deletions(-)

diff --git a/lib/message.cc b/lib/message.cc
index 225b7e9..adcd07d 100644
--- a/lib/message.cc
+++ b/lib/message.cc
@@ -254,6 +254,12 @@ _notmuch_message_create_for_message_id (notmuch_database_t *notmuch,
     return message;
 }
 
+unsigned int
+_notmuch_message_get_doc_id (notmuch_message_t *message)
+{
+    return message->doc_id;
+}
+
 const char *
 notmuch_message_get_message_id (notmuch_message_t *message)
 {
diff --git a/lib/notmuch-private.h b/lib/notmuch-private.h
index 592cfb2..303aeb3 100644
--- a/lib/notmuch-private.h
+++ b/lib/notmuch-private.h
@@ -156,6 +156,8 @@ typedef enum _notmuch_private_status {
      :									\
      (notmuch_status_t) private_status)
 
+typedef struct _notmuch_doc_id_set notmuch_doc_id_set_t;
+
 /* database.cc */
 
 /* Lookup a prefix value by name.
@@ -222,8 +224,8 @@ _notmuch_directory_get_document_id (notmuch_directory_t *directory);
 notmuch_thread_t *
 _notmuch_thread_create (void *ctx,
 			notmuch_database_t *notmuch,
-			const char *thread_id,
-			const char *query_string,
+			unsigned int seed_doc_id,
+			notmuch_doc_id_set_t *match_set,
 			notmuch_sort_t sort);
 
 /* message.cc */
@@ -239,6 +241,9 @@ _notmuch_message_create_for_message_id (notmuch_database_t *notmuch,
 					const char *message_id,
 					notmuch_private_status_t *status);
 
+unsigned int
+_notmuch_message_get_doc_id (notmuch_message_t *message);
+
 const char *
 _notmuch_message_get_in_reply_to (notmuch_message_t *message);
 
@@ -426,6 +431,14 @@ _notmuch_mset_messages_get (notmuch_messages_t *messages);
 void
 _notmuch_mset_messages_move_to_next (notmuch_messages_t *messages);
 
+notmuch_bool_t
+_notmuch_doc_id_set_contains (notmuch_doc_id_set_t *doc_ids,
+                              unsigned int doc_id);
+
+void
+_notmuch_doc_id_set_remove (notmuch_doc_id_set_t *doc_ids,
+                            unsigned int doc_id);
+
 /* message.cc */
 
 void
diff --git a/lib/query.cc b/lib/query.cc
index 7916421..c7ae4ee 100644
--- a/lib/query.cc
+++ b/lib/query.cc
@@ -36,13 +36,21 @@ typedef struct _notmuch_mset_messages {
     Xapian::MSetIterator iterator_end;
 } notmuch_mset_messages_t;
 
+struct _notmuch_doc_id_set {
+    unsigned int *bitmap;
+    unsigned int bound;
+};
+
 struct _notmuch_threads {
     notmuch_query_t *query;
-    GHashTable *threads;
-    notmuch_messages_t *messages;
 
-    /* This thread ID is our iterator state. */
-    const char *thread_id;
+    /* The ordered list of doc ids matched by the query. */
+    GArray *doc_ids;
+    /* Our iterator's current position in doc_ids. */
+    unsigned int doc_id_pos;
+    /* The set of matched docid's that have not been assigned to a
+     * thread. Initially, this contains every docid in doc_ids. */
+    notmuch_doc_id_set_t match_set;
 };
 
 notmuch_query_t *
@@ -195,6 +203,19 @@ _notmuch_mset_messages_valid (notmuch_messages_t *messages)
     return (mset_messages->iterator != mset_messages->iterator_end);
 }
 
+static Xapian::docid
+_notmuch_mset_messages_get_doc_id (notmuch_messages_t *messages)
+{
+    notmuch_mset_messages_t *mset_messages;
+
+    mset_messages = (notmuch_mset_messages_t *) messages;
+
+    if (! _notmuch_mset_messages_valid (&mset_messages->base))
+	return 0;
+
+    return *mset_messages->iterator;
+}
+
 notmuch_message_t *
 _notmuch_mset_messages_get (notmuch_messages_t *messages)
 {
@@ -233,6 +254,49 @@ _notmuch_mset_messages_move_to_next (notmuch_messages_t *messages)
     mset_messages->iterator++;
 }
 
+static notmuch_bool_t
+_notmuch_doc_id_set_init (void *ctx,
+			  notmuch_doc_id_set_t *doc_ids,
+			  GArray *arr, unsigned int bound)
+{
+    size_t count = (bound + sizeof (doc_ids->bitmap[0]) - 1) /
+	sizeof (doc_ids->bitmap[0]);
+    unsigned int *bitmap = talloc_zero_array (ctx, unsigned int, count);
+
+    if (bitmap == NULL)
+	return FALSE;
+
+    doc_ids->bitmap = bitmap;
+    doc_ids->bound = bound;
+
+    for (unsigned int i = 0; i < arr->len; i++) {
+	unsigned int doc_id = g_array_index(arr, unsigned int, i);
+	bitmap[doc_id / sizeof (bitmap[0])] |=
+	    1 << (doc_id % sizeof (bitmap[0]));
+    }
+
+    return TRUE;
+}
+
+notmuch_bool_t
+_notmuch_doc_id_set_contains (notmuch_doc_id_set_t *doc_ids,
+			      unsigned int doc_id)
+{
+    if (doc_id >= doc_ids->bound)
+	return FALSE;
+    return (doc_ids->bitmap[doc_id / sizeof (doc_ids->bitmap[0])] &
+	    (1 << (doc_id % sizeof (doc_ids->bitmap[0])))) != 0;
+}
+
+void
+_notmuch_doc_id_set_remove (notmuch_doc_id_set_t *doc_ids,
+                            unsigned int doc_id)
+{
+    if (doc_id < doc_ids->bound)
+	doc_ids->bitmap[doc_id / sizeof (doc_ids->bitmap[0])] &=
+	    ~(1 << (doc_id % sizeof (doc_ids->bitmap[0])));
+}
+
 /* Glib objects force use to use a talloc destructor as well, (but not
  * nearly as ugly as the for messages due to C++ objects). At
  * this point, I'd really like to have some talloc-friendly
@@ -240,7 +304,8 @@ _notmuch_mset_messages_move_to_next (notmuch_messages_t *messages)
 static int
 _notmuch_threads_destructor (notmuch_threads_t *threads)
 {
-    g_hash_table_unref (threads->threads);
+    if (threads->doc_ids)
+	g_array_unref (threads->doc_ids);
 
     return 0;
 }
@@ -249,24 +314,39 @@ notmuch_threads_t *
 notmuch_query_search_threads (notmuch_query_t *query)
 {
     notmuch_threads_t *threads;
+    notmuch_messages_t *messages;
+    Xapian::docid max_doc_id = 0;
 
     threads = talloc (query, notmuch_threads_t);
     if (threads == NULL)
 	return NULL;
+    threads->doc_ids = NULL;
+    talloc_set_destructor (threads, _notmuch_threads_destructor);
 
     threads->query = query;
-    threads->threads = g_hash_table_new_full (g_str_hash, g_str_equal,
-					      free, NULL);
 
-    threads->messages = notmuch_query_search_messages (query);
-    if (threads->messages == NULL) {
+    messages = notmuch_query_search_messages (query);
+    if (messages == NULL) {
 	    talloc_free (threads);
 	    return NULL;
     }
 
-    threads->thread_id = NULL;
+    threads->doc_ids = g_array_new (FALSE, FALSE, sizeof (unsigned int));
+    while (notmuch_messages_valid (messages)) {
+	unsigned int doc_id = _notmuch_mset_messages_get_doc_id (messages);
+	g_array_append_val (threads->doc_ids, doc_id);
+	max_doc_id = MAX (max_doc_id, doc_id);
+	notmuch_messages_move_to_next (messages);
+    }
+    threads->doc_id_pos = 0;
 
-    talloc_set_destructor (threads, _notmuch_threads_destructor);
+    talloc_free (messages);
+
+    if (! _notmuch_doc_id_set_init (threads, &threads->match_set,
+				    threads->doc_ids, max_doc_id + 1)) {
+	talloc_free (threads);
+	return NULL;
+    }
 
     return threads;
 }
@@ -280,51 +360,41 @@ notmuch_query_destroy (notmuch_query_t *query)
 notmuch_bool_t
 notmuch_threads_valid (notmuch_threads_t *threads)
 {
-    notmuch_message_t *message;
-
-    if (threads->thread_id)
-	return TRUE;
-
-    while (notmuch_messages_valid (threads->messages))
-    {
-	message = notmuch_messages_get (threads->messages);
+    unsigned int doc_id;
 
-	threads->thread_id = notmuch_message_get_thread_id (message);
-
-	if (! g_hash_table_lookup_extended (threads->threads,
-					    threads->thread_id,
-					    NULL, NULL))
-	{
-	    g_hash_table_insert (threads->threads,
-				 xstrdup (threads->thread_id), NULL);
-	    notmuch_messages_move_to_next (threads->messages);
-	    return TRUE;
-	}
+    while (threads->doc_id_pos < threads->doc_ids->len) {
+	doc_id = g_array_index (threads->doc_ids, unsigned int,
+				threads->doc_id_pos);
+	if (_notmuch_doc_id_set_contains (&threads->match_set, doc_id))
+	    break;
 
-	notmuch_messages_move_to_next (threads->messages);
+	threads->doc_id_pos++;
     }
 
-    threads->thread_id = NULL;
-    return FALSE;
+    return threads->doc_id_pos < threads->doc_ids->len;
 }
 
 notmuch_thread_t *
 notmuch_threads_get (notmuch_threads_t *threads)
 {
+    unsigned int doc_id;
+
     if (! notmuch_threads_valid (threads))
 	return NULL;
 
+    doc_id = g_array_index (threads->doc_ids, unsigned int,
+			    threads->doc_id_pos);
     return _notmuch_thread_create (threads->query,
 				   threads->query->notmuch,
-				   threads->thread_id,
-				   threads->query->query_string,
+				   doc_id,
+				   &threads->match_set,
 				   threads->query->sort);
 }
 
 void
 notmuch_threads_move_to_next (notmuch_threads_t *threads)
 {
-    threads->thread_id = NULL;
+    threads->doc_id_pos++;
 }
 
 void
diff --git a/lib/thread.cc b/lib/thread.cc
index 7f15586..244c038 100644
--- a/lib/thread.cc
+++ b/lib/thread.cc
@@ -305,7 +305,7 @@ _thread_add_matched_message (notmuch_thread_t *thread,
 
     _thread_add_matched_author (thread, notmuch_message_get_author (hashed_message));
 
-    if ((sort == NOTMUCH_SORT_OLDEST_FIRST && date <= thread->newest) ||
+    if ((sort == NOTMUCH_SORT_OLDEST_FIRST && date == thread->oldest) ||
 	(sort != NOTMUCH_SORT_OLDEST_FIRST && date == thread->newest))
     {
 	_thread_set_subject_from_message (thread, message);
@@ -350,16 +350,17 @@ _resolve_thread_relationships (unused (notmuch_thread_t *thread))
      */
 }
 
-/* Create a new notmuch_thread_t object for the given thread ID,
- * treating any messages matching 'query_string' as "matched".
+/* Create a new notmuch_thread_t object by finding the thread
+ * containing the message with the given doc ID, treating any messages
+ * contained in match_set as "matched".  Remove all messages in the
+ * thread from match_set.
  *
- * Creating the thread will trigger two database searches. The first
- * is for all messages belonging to the thread, (to get the first
- * subject line, the total count of messages, and all authors). The
- * second search is for all messages that are in the thread and that
- * also match the given query_string. This is to allow for a separate
- * count of matched messages, and to allow a viewer to display these
- * messages differently.
+ * Creating the thread will perform a database search to get all
+ * messages belonging to the thread and will get the first subject
+ * line, the total count of messages, and all authors in the thread.
+ * Each message in the thread is checked against match_set to allow
+ * for a separate count of matched messages, and to allow a viewer to
+ * display these messages differently.
  *
  * Here, 'ctx' is talloc context for the resulting thread object.
  *
@@ -368,53 +369,28 @@ _resolve_thread_relationships (unused (notmuch_thread_t *thread))
 notmuch_thread_t *
 _notmuch_thread_create (void *ctx,
 			notmuch_database_t *notmuch,
-			const char *thread_id,
-			const char *query_string,
+			unsigned int seed_doc_id,
+			notmuch_doc_id_set_t *match_set,
 			notmuch_sort_t sort)
 {
     notmuch_thread_t *thread;
+    notmuch_message_t *seed_message;
+    const char *thread_id;
     const char *thread_id_query_string;
     notmuch_query_t *thread_id_query;
 
     notmuch_messages_t *messages;
     notmuch_message_t *message;
-    notmuch_bool_t matched_is_subset_of_thread;
 
+    seed_message = _notmuch_message_create (ctx, notmuch, seed_doc_id, NULL);
+    if (! seed_message)
+	INTERNAL_ERROR ("Thread seed message %u does not exist", seed_doc_id);
+
+    thread_id = notmuch_message_get_thread_id (seed_message);
     thread_id_query_string = talloc_asprintf (ctx, "thread:%s", thread_id);
-    if (unlikely (query_string == NULL))
+    if (unlikely (thread_id_query_string == NULL))
 	return NULL;
 
-    /* Under normal circumstances we need to do two database
-     * queries. One is for the thread itself (thread_id_query_string)
-     * and the second is to determine which messages in that thread
-     * match the original query (matched_query_string).
-     *
-     * But under two circumstances, we use only the
-     * thread_id_query_string:
-     *
-     *	1. If the original query_string *is* just the thread
-     *	   specification.
-     *
-     *  2. If the original query_string matches all messages ("" or
-     *     "*").
-     *
-     * In either of these cases, we can be more efficient by running
-     * just the thread_id query (since we know all messages in the
-     * thread will match the query_string).
-     *
-     * Beyond the performance advantage, in the second case, it's
-     * important to not try to create a concatenated query because our
-     * parser handles "" and "*" as special cases and will not do the
-     * right thing with a query string of "* and thread:<foo>".
-     **/
-    matched_is_subset_of_thread = 1;
-    if (strcmp (query_string, thread_id_query_string) == 0 ||
-	strcmp (query_string, "") == 0 ||
-	strcmp (query_string, "*") == 0)
-    {
-	matched_is_subset_of_thread = 0;
-    }
-
     thread_id_query = notmuch_query_create (notmuch, thread_id_query_string);
     if (unlikely (thread_id_query == NULL))
 	return NULL;
@@ -457,45 +433,25 @@ _notmuch_thread_create (void *ctx,
 	 notmuch_messages_valid (messages);
 	 notmuch_messages_move_to_next (messages))
     {
+	unsigned int doc_id;
+
 	message = notmuch_messages_get (messages);
+	doc_id = _notmuch_message_get_doc_id (message);
+	if (doc_id == seed_doc_id)
+	    message = seed_message;
 
 	_thread_add_message (thread, message);
 
-	if (! matched_is_subset_of_thread)
+	if ( _notmuch_doc_id_set_contains (match_set, doc_id)) {
+	    _notmuch_doc_id_set_remove (match_set, doc_id);
 	    _thread_add_matched_message (thread, message, sort);
+	}
 
 	_notmuch_message_close (message);
     }
 
     notmuch_query_destroy (thread_id_query);
 
-    if (matched_is_subset_of_thread)
-    {
-	const char *matched_query_string;
-	notmuch_query_t *matched_query;
-
-	matched_query_string = talloc_asprintf (ctx, "%s AND (%s)",
-						thread_id_query_string,
-						query_string);
-	if (unlikely (matched_query_string == NULL))
-	    return NULL;
-
-	matched_query = notmuch_query_create (notmuch, matched_query_string);
-	if (unlikely (matched_query == NULL))
-	    return NULL;
-
-	for (messages = notmuch_query_search_messages (matched_query);
-	     notmuch_messages_valid (messages);
-	     notmuch_messages_move_to_next (messages))
-	{
-	    message = notmuch_messages_get (messages);
-	    _thread_add_matched_message (thread, message, sort);
-	    _notmuch_message_close (message);
-	}
-
-	notmuch_query_destroy (matched_query);
-    }
-
     _complete_thread_authors (thread);
 
     _resolve_thread_relationships (thread);
diff --git a/test/emacs b/test/emacs
index 75dec89..fd5ae07 100755
--- a/test/emacs
+++ b/test/emacs
@@ -24,12 +24,12 @@ test_expect_equal "$output" "$expected"
 test_begin_subtest "Basic notmuch-search view in emacs"
 output=$(test_emacs '(notmuch-search "tag:inbox") (notmuch-test-wait) (message (buffer-string))' 2>&1)
 expected=$(cat $EXPECTED/notmuch-search-tag-inbox)
-test_expect_equal "$output" "$expected"
+test_expect_equal_failure "$output" "$expected"
 
 test_begin_subtest "Navigation of notmuch-hello to search results"
 output=$(test_emacs '(notmuch-hello) (goto-char (point-min)) (re-search-forward "inbox") (widget-button-press (point)) (notmuch-test-wait) (message (buffer-string))' 2>&1)
 expected=$(cat $EXPECTED/notmuch-hello-view-inbox)
-test_expect_equal "$output" "$expected"
+test_expect_equal_failure "$output" "$expected"
 
 test_begin_subtest "Basic notmuch-show view in emacs"
 maildir_storage_thread=$(notmuch search --output=threads id:20091117190054.GU3165@dottiness.seas.harvard.edu)
-- 
1.7.2.3

Re: [PATCH 3/4] Optimize thread search using matched docid sets.

[Austin Clements]

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?

Quoth myself on Nov 17 at  2:28 pm:
> This reduces thread search's 1+2t Xapian queries (where t is the
> number of matched threads) to 1+t queries and constructs exactly one
> notmuch_message_t for each message instead of 2 to 3.
> notmuch_query_search_threads eagerly fetches the docids of all
> messages matching the user query instead of lazily constructing
> message objects and fetching thread ID's from term lists.
> _notmuch_thread_create takes a seed docid and the set of all matched
> docids and uses a single Xapian query to expand this docid to its
> containing thread, using the matched docid set to determine which
> messages in the thread match the user query instead of using a second
> Xapian query.
> 
> As a side effect, this fixes author order so authors are always sorted
> by first occurrence in each thread.  This breaks two emacs tests that
> hard-code the old, buggy author order.
> 
> This reduces the amount of time required to load my inbox from 4.523
> seconds to 3.025 seconds (1.5X faster).

Re: [PATCH 3/4] Optimize thread search using matched docid sets.

[Carl Worth]

[-- Attachment #1: Type: text/plain, Size: 1708 bytes --]

On Wed, 17 Nov 2010 14:28:26 -0500, Austin Clements <amdragon@MIT.EDU> wrote:
> This reduces thread search's 1+2t Xapian queries (where t is the
> number of matched threads) to 1+t queries and constructs exactly one
> notmuch_message_t for each message instead of 2 to 3.

Fantastic stuff, Austin!

I've merged this now, (sorry it took me a while to get to it).

One of the reasons I didn't merge it immediately is that I wanted to
ensure that I understood the original author-ordering bug. Basically,
I'm inherently uncomfortable with a performance optimization that fixes
a bug as a side effect, (unless we understand that very well).

So what I pushed actually adds the bug fix first, so that the
performance optimization makes no change at all to the test suite. That
feels better to me, (even though it simply demonstrated conclusively
that the bug was in a piece of code that was eliminated by the
optimization).

Anyway, in a quick reading of the code, the only little thing I saw was:

> +    size_t count = (bound + sizeof (doc_ids->bitmap[0]) - 1) /
> +	sizeof (doc_ids->bitmap[0]);

Which would look better to my eyes with a 1 factored out of the
division:

	size_t count = 1 + (bound - 1) / sizeof (doc_ids->bitmap[0]);

And the repeated use of "sizeof (doc_ids->bitmap[0])" could maybe do
with a macro for better legibility. Though it would be an evil macro if
it didn't accept an argument, and it wouldn't be much shorter if it
did. So maybe it's fine as-is.

Thanks for the optimization. Now all we need is a little notmuch
benchmark so that I can be sure not to regress any performance work with
my sloppy coding!

-Carl

-- 
carl.d.worth@intel.com

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 3/4] Optimize thread search using matched docid sets.

[Carl Worth]

[-- Attachment #1: Type: text/plain, Size: 1575 bytes --]

On Thu, 18 Nov 2010 02:38:29 -0500, Austin Clements <amdragon@MIT.EDU> wrote:
> 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!

-Carl

-- 
carl.d.worth@intel.com

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 3/4] Optimize thread search using matched docid sets.

[Austin Clements]

Quoth Carl Worth on Dec 07 at  5:19 pm:
> On Wed, 17 Nov 2010 14:28:26 -0500, Austin Clements <amdragon@MIT.EDU> wrote:
> > This reduces thread search's 1+2t Xapian queries (where t is the
> > number of matched threads) to 1+t queries and constructs exactly one
> > notmuch_message_t for each message instead of 2 to 3.
> 
> Fantastic stuff, Austin!
> 
> I've merged this now, (sorry it took me a while to get to it).
> 
> One of the reasons I didn't merge it immediately is that I wanted to
> ensure that I understood the original author-ordering bug. Basically,
> I'm inherently uncomfortable with a performance optimization that fixes
> a bug as a side effect, (unless we understand that very well).
> 
> So what I pushed actually adds the bug fix first, so that the
> performance optimization makes no change at all to the test suite. That
> feels better to me, (even though it simply demonstrated conclusively
> that the bug was in a piece of code that was eliminated by the
> optimization).

Ah, good.  You are less lazy than I.

> Anyway, in a quick reading of the code, the only little thing I saw was:
> 
> > +    size_t count = (bound + sizeof (doc_ids->bitmap[0]) - 1) /
> > +	sizeof (doc_ids->bitmap[0]);
> 
> Which would look better to my eyes with a 1 factored out of the
> division:
> 
> 	size_t count = 1 + (bound - 1) / sizeof (doc_ids->bitmap[0]);
> 
> And the repeated use of "sizeof (doc_ids->bitmap[0])" could maybe do
> with a macro for better legibility. Though it would be an evil macro if
> it didn't accept an argument, and it wouldn't be much shorter if it
> did. So maybe it's fine as-is.

I found what I think is a cleaner way to write that bit of code.  A
small patch is forthcoming.

> Thanks for the optimization. Now all we need is a little notmuch
> benchmark so that I can be sure not to regress any performance work with
> my sloppy coding!

Now that this is in (and I have a temporary respite from TA duties),
I'm going to finish up and send out my other ~1.7X improvement, just
to get it out of my queue.  Then I'll look at making a performance
regression suite.  Were you thinking of some standard set of timed
operations wrapped in a little script that can tell you if you've made
things worse, or something more elaborate?

Thanks for pushing these patches!

[PATCH] Various small clean-ups to doc ID set code.

[Austin Clements]

Remove the repeated "sizeof (doc_ids->bitmap[0])" that bothered cworth
by instead defining macros to compute the word and bit offset of a
given bit in the bitmap.

Don't require the caller of _notmuch_doc_id_set_init to pass in a
correct bound; instead compute it from the array.  This simplifies the
caller and makes this interface easier to use correctly.
---
 lib/query.cc |   37 +++++++++++++++++++------------------
 1 files changed, 19 insertions(+), 18 deletions(-)

diff --git a/lib/query.cc b/lib/query.cc
index c7ae4ee..3b76dc5 100644
--- a/lib/query.cc
+++ b/lib/query.cc
@@ -38,9 +38,12 @@ typedef struct _notmuch_mset_messages {
 
 struct _notmuch_doc_id_set {
     unsigned int *bitmap;
-    unsigned int bound;
+    unsigned int max;
 };
 
+#define BITMAP_WORD(bit) ((bit) / sizeof (unsigned int))
+#define BITMAP_BIT(bit) ((bit) % sizeof (unsigned int))
+
 struct _notmuch_threads {
     notmuch_query_t *query;
 
@@ -257,22 +260,24 @@ _notmuch_mset_messages_move_to_next (notmuch_messages_t *messages)
 static notmuch_bool_t
 _notmuch_doc_id_set_init (void *ctx,
 			  notmuch_doc_id_set_t *doc_ids,
-			  GArray *arr, unsigned int bound)
+			  GArray *arr)
 {
-    size_t count = (bound + sizeof (doc_ids->bitmap[0]) - 1) /
-	sizeof (doc_ids->bitmap[0]);
-    unsigned int *bitmap = talloc_zero_array (ctx, unsigned int, count);
+    unsigned int max = 0;
+    unsigned int *bitmap;
+
+    for (unsigned int i = 0; i < arr->len; i++)
+	max = MAX(max, g_array_index (arr, unsigned int, i));
+    bitmap = talloc_zero_array (ctx, unsigned int, 1 + max / sizeof (*bitmap));
 
     if (bitmap == NULL)
 	return FALSE;
 
     doc_ids->bitmap = bitmap;
-    doc_ids->bound = bound;
+    doc_ids->max = max;
 
     for (unsigned int i = 0; i < arr->len; i++) {
-	unsigned int doc_id = g_array_index(arr, unsigned int, i);
-	bitmap[doc_id / sizeof (bitmap[0])] |=
-	    1 << (doc_id % sizeof (bitmap[0]));
+	unsigned int doc_id = g_array_index (arr, unsigned int, i);
+	bitmap[BITMAP_WORD(doc_id)] |= 1 << BITMAP_BIT(doc_id);
     }
 
     return TRUE;
@@ -282,19 +287,17 @@ notmuch_bool_t
 _notmuch_doc_id_set_contains (notmuch_doc_id_set_t *doc_ids,
 			      unsigned int doc_id)
 {
-    if (doc_id >= doc_ids->bound)
+    if (doc_id > doc_ids->max)
 	return FALSE;
-    return (doc_ids->bitmap[doc_id / sizeof (doc_ids->bitmap[0])] &
-	    (1 << (doc_id % sizeof (doc_ids->bitmap[0])))) != 0;
+    return doc_ids->bitmap[BITMAP_WORD(doc_id)] & (1 << BITMAP_BIT(doc_id));
 }
 
 void
 _notmuch_doc_id_set_remove (notmuch_doc_id_set_t *doc_ids,
                             unsigned int doc_id)
 {
-    if (doc_id < doc_ids->bound)
-	doc_ids->bitmap[doc_id / sizeof (doc_ids->bitmap[0])] &=
-	    ~(1 << (doc_id % sizeof (doc_ids->bitmap[0])));
+    if (doc_id <= doc_ids->max)
+	doc_ids->bitmap[BITMAP_WORD(doc_id)] &= ~(1 << BITMAP_BIT(doc_id));
 }
 
 /* Glib objects force use to use a talloc destructor as well, (but not
@@ -315,7 +318,6 @@ notmuch_query_search_threads (notmuch_query_t *query)
 {
     notmuch_threads_t *threads;
     notmuch_messages_t *messages;
-    Xapian::docid max_doc_id = 0;
 
     threads = talloc (query, notmuch_threads_t);
     if (threads == NULL)
@@ -335,7 +337,6 @@ notmuch_query_search_threads (notmuch_query_t *query)
     while (notmuch_messages_valid (messages)) {
 	unsigned int doc_id = _notmuch_mset_messages_get_doc_id (messages);
 	g_array_append_val (threads->doc_ids, doc_id);
-	max_doc_id = MAX (max_doc_id, doc_id);
 	notmuch_messages_move_to_next (messages);
     }
     threads->doc_id_pos = 0;
@@ -343,7 +344,7 @@ notmuch_query_search_threads (notmuch_query_t *query)
     talloc_free (messages);
 
     if (! _notmuch_doc_id_set_init (threads, &threads->match_set,
-				    threads->doc_ids, max_doc_id + 1)) {
+				    threads->doc_ids)) {
 	talloc_free (threads);
 	return NULL;
     }
-- 
1.7.2.3

Re: [PATCH 3/4] Optimize thread search using matched docid sets.

[Carl Worth]

[-- Attachment #1.1: Type: text/plain, Size: 1708 bytes --]

On Wed, 8 Dec 2010 16:58:44 -0500, Austin Clements <amdragon@MIT.EDU> wrote:
> Now that this is in (and I have a temporary respite from TA duties),
> I'm going to finish up and send out my other ~1.7X improvement, just
> to get it out of my queue.  Then I'll look at making a performance
> regression suite.  Were you thinking of some standard set of timed
> operations wrapped in a little script that can tell you if you've made
> things worse, or something more elaborate?

I recently started making a perf/notmuch-perf script for notmuch (see
below). I was doing this in preparation for my linux.conf.au talk on
notmuch, (though I ended up not talking about performance in concrete
terms).

I don't know how much further I'll run with this now, but if this is a
useful starting place for anyone, let me know and I can obviously add
this to the repository.

So the idea with this script is that the timed operations actually
depend on local data, (your current mail collection as indicated by
NOTMUCH_CONFIG). So the operations aren't standardized to enable
comparison between different people, (unless they also agree on some
common mail collection).

My script as attached runs only "notmuch new" to time the original
indexing. Beyond that I'd like to time some common operations,
(adding a new message, searching for a single message, searching for
many messages, searching for all messages, etc.).

And then on top of this, I'd like to have a little utility that could
compare several different runs captured previously. That would let me do
the regression testing I'd like to ensure we never make performance
worse.

Please feel free to run with this or with your own approach as you see
fit.

-Carl


[-- Attachment #1.2: Type: application/pgp-signature, Size: 189 bytes --]

[-- Attachment #2: notmuch-perf --]
[-- Type: application/octet-stream, Size: 604 bytes --]

#!/bin/sh
set -e

SCRATCH="$(pwd)/notmuch-perf_$(date +%F_%T)"
CONFIG_ORIG=${NOTMUCH_CONFIG:-$HOME/.notmuch-config}

if ! [ -f "$CONFIG_ORIG" ]; then
   echo "Error: No configuration found at $CONFIG_ORIG"
   echo "Please provide a default configuration file to specify the mail to index."
   exit 1
fi

mkdir "$SCRATCH"
cd "$SCRATCH"

MAIL_PATH_ORIG=$(notmuch config get database.path)
MAIL_PATH="$SCRATCH/mail"

export NOTMUCH_CONFIG="$SCRATCH/notmuch-config"
cp "$CONFIG_ORIG" "$NOTMUCH_CONFIG"

ln -s "$MAIL_PATH_ORIG" "$MAIL_PATH"

echo "Now running notmuch new to index all mail"
time notmuch new

Re: [PATCH] Various small clean-ups to doc ID set code.

[Carl Worth]

[-- Attachment #1: Type: text/plain, Size: 1757 bytes --]

On Wed, 8 Dec 2010 17:01:53 -0500, Austin Clements <amdragon@MIT.EDU> wrote:
> Remove the repeated "sizeof (doc_ids->bitmap[0])" that bothered cworth
> by instead defining macros to compute the word and bit offset of a
> given bit in the bitmap.
> 
> Don't require the caller of _notmuch_doc_id_set_init to pass in a
> correct bound; instead compute it from the array.  This simplifies the
> caller and makes this interface easier to use correctly.
...
> +#define BITMAP_WORD(bit) ((bit) / sizeof (unsigned int))
> +#define BITMAP_BIT(bit) ((bit) % sizeof (unsigned int))

These macros look great, they definitely simplify the code.

>  _notmuch_doc_id_set_init (void *ctx,
>  			  notmuch_doc_id_set_t *doc_ids,
> -			  GArray *arr, unsigned int bound)
> +			  GArray *arr)
...
> +    for (unsigned int i = 0; i < arr->len; i++)
> +	max = MAX(max, g_array_index (arr, unsigned int, i));

And computing an argument automatically definitely makes the interface
easier to use. So that's good too. But those two changes are independent
so really need to be in separate commits.

> -    if (doc_id >= doc_ids->bound)
> +    if (doc_id > doc_ids->max)

And this looks really like a *third* independent change to me.

A code change like the above has the chance to introduce (or fix) an
off-by-one bug---or even leave the code effectively unchanged as the
intent is here.

In order to distinguish all of those cases, I'd like to see a change
like this as a minimal change, and described in the commit
message. (Rather than hidden amongst "various cleanups" that are mostly
about replacing some common code with a macro.)

So I'd be happy to see this patch broken up and sent again.

-Carl

-- 
carl.d.worth@intel.com

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

[PATCH v2 0/2] Small clean-ups to the doc ID set code

[Austin Clements]

I split up the patches as requested and also rebased to current
master.  Relative to the original patch, I stripped out the
bound-to-max change since I could no longer convince myself it was a
good idea, and changed BITMAP_* to DOCIDSET_* to clarify that the
macros were for working with the doc ID set bitmaps and not just any
old bitmaps.

As usual, this is also available in my git repo
  http://awakening.csail.mit.edu/git/notmuch.git
as the search-perf-3 branch.

[PATCH 1/2] Remove code repetition in the doc ID bitmap code.

[Austin Clements]

Remove the repeated "sizeof (doc_ids->bitmap[0])" that bothered cworth
by instead defining macros to compute the word and bit offset of a
given bit in the doc ID set bitmap.
---
 lib/query.cc |   14 +++++++-------
 1 files changed, 7 insertions(+), 7 deletions(-)

diff --git a/lib/query.cc b/lib/query.cc
index c7ae4ee..c155470 100644
--- a/lib/query.cc
+++ b/lib/query.cc
@@ -41,6 +41,9 @@ struct _notmuch_doc_id_set {
     unsigned int bound;
 };
 
+#define DOCIDSET_WORD(bit) ((bit) / sizeof (unsigned int))
+#define DOCIDSET_BIT(bit) ((bit) % sizeof (unsigned int))
+
 struct _notmuch_threads {
     notmuch_query_t *query;
 
@@ -270,9 +273,8 @@ _notmuch_doc_id_set_init (void *ctx,
     doc_ids->bound = bound;
 
     for (unsigned int i = 0; i < arr->len; i++) {
-	unsigned int doc_id = g_array_index(arr, unsigned int, i);
-	bitmap[doc_id / sizeof (bitmap[0])] |=
-	    1 << (doc_id % sizeof (bitmap[0]));
+	unsigned int doc_id = g_array_index (arr, unsigned int, i);
+	bitmap[DOCIDSET_WORD(doc_id)] |= 1 << DOCIDSET_BIT(doc_id);
     }
 
     return TRUE;
@@ -284,8 +286,7 @@ _notmuch_doc_id_set_contains (notmuch_doc_id_set_t *doc_ids,
 {
     if (doc_id >= doc_ids->bound)
 	return FALSE;
-    return (doc_ids->bitmap[doc_id / sizeof (doc_ids->bitmap[0])] &
-	    (1 << (doc_id % sizeof (doc_ids->bitmap[0])))) != 0;
+    return doc_ids->bitmap[DOCIDSET_WORD(doc_id)] & (1 << DOCIDSET_BIT(doc_id));
 }
 
 void
@@ -293,8 +294,7 @@ _notmuch_doc_id_set_remove (notmuch_doc_id_set_t *doc_ids,
                             unsigned int doc_id)
 {
     if (doc_id < doc_ids->bound)
-	doc_ids->bitmap[doc_id / sizeof (doc_ids->bitmap[0])] &=
-	    ~(1 << (doc_id % sizeof (doc_ids->bitmap[0])));
+	doc_ids->bitmap[DOCIDSET_WORD(doc_id)] &= ~(1 << DOCIDSET_BIT(doc_id));
 }
 
 /* Glib objects force use to use a talloc destructor as well, (but not
-- 
1.7.2.3

[PATCH 2/2] Simplify _notmuch_doc_id_set_init interface.

[Austin Clements]

Don't require the caller of _notmuch_doc_id_set_init to pass in a
correct bound; instead compute it from the array.  This simplifies the
caller and makes this interface easier to use correctly.
---
 lib/query.cc |   17 +++++++++--------
 1 files changed, 9 insertions(+), 8 deletions(-)

diff --git a/lib/query.cc b/lib/query.cc
index c155470..07e695b 100644
--- a/lib/query.cc
+++ b/lib/query.cc
@@ -260,17 +260,20 @@ _notmuch_mset_messages_move_to_next (notmuch_messages_t *messages)
 static notmuch_bool_t
 _notmuch_doc_id_set_init (void *ctx,
 			  notmuch_doc_id_set_t *doc_ids,
-			  GArray *arr, unsigned int bound)
+			  GArray *arr)
 {
-    size_t count = (bound + sizeof (doc_ids->bitmap[0]) - 1) /
-	sizeof (doc_ids->bitmap[0]);
-    unsigned int *bitmap = talloc_zero_array (ctx, unsigned int, count);
+    unsigned int max = 0;
+    unsigned int *bitmap;
+
+    for (unsigned int i = 0; i < arr->len; i++)
+	max = MAX(max, g_array_index (arr, unsigned int, i));
+    bitmap = talloc_zero_array (ctx, unsigned int, 1 + max / sizeof (*bitmap));
 
     if (bitmap == NULL)
 	return FALSE;
 
     doc_ids->bitmap = bitmap;
-    doc_ids->bound = bound;
+    doc_ids->bound = max + 1;
 
     for (unsigned int i = 0; i < arr->len; i++) {
 	unsigned int doc_id = g_array_index (arr, unsigned int, i);
@@ -315,7 +318,6 @@ notmuch_query_search_threads (notmuch_query_t *query)
 {
     notmuch_threads_t *threads;
     notmuch_messages_t *messages;
-    Xapian::docid max_doc_id = 0;
 
     threads = talloc (query, notmuch_threads_t);
     if (threads == NULL)
@@ -335,7 +337,6 @@ notmuch_query_search_threads (notmuch_query_t *query)
     while (notmuch_messages_valid (messages)) {
 	unsigned int doc_id = _notmuch_mset_messages_get_doc_id (messages);
 	g_array_append_val (threads->doc_ids, doc_id);
-	max_doc_id = MAX (max_doc_id, doc_id);
 	notmuch_messages_move_to_next (messages);
     }
     threads->doc_id_pos = 0;
@@ -343,7 +344,7 @@ notmuch_query_search_threads (notmuch_query_t *query)
     talloc_free (messages);
 
     if (! _notmuch_doc_id_set_init (threads, &threads->match_set,
-				    threads->doc_ids, max_doc_id + 1)) {
+				    threads->doc_ids)) {
 	talloc_free (threads);
 	return NULL;
     }
-- 
1.7.2.3

Re: [PATCH v2 0/2] Small clean-ups to the doc ID set code

[Carl Worth]

[-- Attachment #1: Type: text/plain, Size: 499 bytes --]

On Sun, 30 Jan 2011 23:22:31 -0500, Austin Clements <amdragon@MIT.EDU> wrote:
> As usual, this is also available in my git repo
>   http://awakening.csail.mit.edu/git/notmuch.git
> as the search-perf-3 branch.

Thanks. I've *finally* merged and pushed this now.

More to come soon, (though I'm going to have to stop almost before I
started today since I'm feeling fairly sick---hopefully tomorrow can be
a day of some serious notmuch code merging).

-Carl

-- 
carl.d.worth@intel.com

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH v2 0/2] Small clean-ups to the doc ID set code

[Austin Clements]

Thanks!

Hope you feel better tomorrow.

Quoth Carl Worth on Mar 09 at  3:21 pm:
> On Sun, 30 Jan 2011 23:22:31 -0500, Austin Clements <amdragon@MIT.EDU> wrote:
> > As usual, this is also available in my git repo
> >   http://awakening.csail.mit.edu/git/notmuch.git
> > as the search-perf-3 branch.
> 
> Thanks. I've *finally* merged and pushed this now.
> 
> More to come soon, (though I'm going to have to stop almost before I
> started today since I'm feeling fairly sick---hopefully tomorrow can be
> a day of some serious notmuch code merging).
> 
> -Carl