[PATCH] notmuch-restore.c: only update tags for messages that differ from dump file.

[PATCH] notmuch-restore.c: only update tags for messages that differ from dump file.

[david]

From: David Bremner <bremner@unb.ca>

The main feature of this patch is that it compares the list of current
tags on a message with those read by restore. Only if the two lists
differ is the tag list in the message replaced.  In my experiments this leads to
a large performance improvement.

Since I had to rewrite the parsing of tags from the dump file anyway
to keep a list of tags (in case they should be written to the
database), I decided to make it a bit more robust. It sorts the
incoming tags (it is critical for the comparison of the two tag lists
that they are both sorted), and allows arbitrary whitespace (as
determined by "isspace") between tags.

The patch allocates a temporary array to keep track of the current
list of tags using calloc and grows it as neccesary using realloc.
---
 notmuch-restore.c |   73 ++++++++++++++++++++++++++++++++++++++++++++--------
 1 files changed, 61 insertions(+), 12 deletions(-)

diff --git a/notmuch-restore.c b/notmuch-restore.c
index 1b9598d..31e29f6 100644
--- a/notmuch-restore.c
+++ b/notmuch-restore.c
@@ -18,8 +18,17 @@
  * Author: Carl Worth <cworth@cworth.org>
  */
 
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
 #include "notmuch-client.h"
 
+#define DEFAULT_TAG_ARRAY_SIZE 2
+/* for qsort */
+static int scmp( const void *sp1, const void *sp2 )
+{
+    return( strcmp(*(const char **)sp1, *(const char **)sp2) );
+}
 int
 notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
 {
@@ -31,6 +40,9 @@ notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
     ssize_t line_len;
     regex_t regex;
     int rerr;
+    char **tag_array=NULL;
+    int tag_array_size=DEFAULT_TAG_ARRAY_SIZE;
+
 
     config = notmuch_config_open (ctx, NULL, NULL);
     if (config == NULL)
@@ -61,11 +73,18 @@ notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
 	      "^([^ ]+) \\(([^)]*)\\)$",
 	      REG_EXTENDED);
 
+    /* Make an array of pointers to point to individual tokens */
+    tag_array=calloc(tag_array_size,sizeof(char*));
+
     while ((line_len = getline (&line, &line_size, input)) != -1) {
 	regmatch_t match[3];
-	char *message_id, *tags, *tag, *next;
+	char *message_id, *tags,  *next;
 	notmuch_message_t *message;
 	notmuch_status_t status;
+	int tag_count;
+
+	notmuch_tags_t *tag_list;
+	int i;
 
 	chomp_newline (line);
 
@@ -89,26 +108,53 @@ notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
 	    goto NEXT_LINE;
 	}
 
-	notmuch_message_freeze (message);
+	next=tags;
+	tag_count=0;
+	while(*next){
+	  while(*next && isspace(*next))
+	    next++;
+	  if (*next) {
+	    while (tag_count>= tag_array_size){
+	      tag_array_size*=2;
+	      tag_array=realloc(tag_array,tag_array_size*sizeof(char *));
+	    }
+	    tag_array[tag_count]=next;
+	    tag_count++;
+	  }
+	  while (*next && !isspace(*next))
+	    next++;
+	  if (*next){
+	    *next='\0';
+	    next++;
+	  }
+	}
+
+	qsort(tag_array,tag_count,sizeof(char*),scmp);
+	
+	tag_list = notmuch_message_get_tags (message);
+	i=0;
+	while (notmuch_tags_has_more (tag_list) && i<tag_count &&
+	       (strcmp(notmuch_tags_get (tag_list),tag_array[i])==0)){
+	  notmuch_tags_advance (tag_list);
+	  i++;
+	}
 
-	notmuch_message_remove_all_tags (message);
+	if (notmuch_tags_has_more (tag_list) && i<tag_count ){
+	  notmuch_message_freeze (message);
+	  notmuch_message_remove_all_tags (message);
 
-	next = tags;
-	while (next) {
-	    tag = strsep (&next, " ");
-	    if (*tag == '\0')
-		continue;
-	    status = notmuch_message_add_tag (message, tag);
+	  for (i=0; i<tag_count; i++) {
+	    status = notmuch_message_add_tag (message, tag_array[i]);
 	    if (status) {
 		fprintf (stderr,
 			 "Error applying tag %s to message %s:\n",
-			 tag, message_id);
+			 tag_array[i], message_id);
 		fprintf (stderr, "%s\n",
 			 notmuch_status_to_string (status));
 	    }
+	  }
+	  notmuch_message_thaw (message);
 	}
-
-	notmuch_message_thaw (message);
 	notmuch_message_destroy (message);
       NEXT_LINE:
 	free (message_id);
@@ -120,6 +166,9 @@ notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
     if (line)
 	free (line);
 
+    if (tag_array)
+      free (tag_array);
+
     notmuch_database_close (notmuch);
     if (input != stdin)
 	fclose (input);
-- 
1.6.5.3

[PATCH] notmuch-restore.c: only update tags for messages that differ from dump file.

[david]

From: David Bremner <bremner@unb.ca>

The main feature of this patch is that it compares the list of current
tags on a message with those read by restore. Only if the two lists
differ is the tag list in the message replaced.  In my experiments this leads to
a large performance improvement.

Since I had to rewrite the parsing of tags from the dump file anyway
to keep a list of tags (in case they should be written to the
database), I decided to make it a bit more robust. It sorts the
incoming tags (it is critical for the comparison of the two tag lists
that they are both sorted), and allows arbitrary whitespace (as
determined by "isspace") between tags.

The patch allocates a temporary array to keep track of the current
list of tags using calloc and grows it as neccesary using realloc.
---

This is the second version of the patch, the only difference is in the test 
on line 144 (used to be 142), and the comment before explaining it.

 notmuch-restore.c |   75 ++++++++++++++++++++++++++++++++++++++++++++--------
 1 files changed, 63 insertions(+), 12 deletions(-)

diff --git a/notmuch-restore.c b/notmuch-restore.c
index 1b9598d..9d7bd17 100644
--- a/notmuch-restore.c
+++ b/notmuch-restore.c
@@ -18,8 +18,17 @@
  * Author: Carl Worth <cworth@cworth.org>
  */
 
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
 #include "notmuch-client.h"
 
+#define DEFAULT_TAG_ARRAY_SIZE 2
+/* for qsort */
+static int scmp( const void *sp1, const void *sp2 )
+{
+    return( strcmp(*(const char **)sp1, *(const char **)sp2) );
+}
 int
 notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
 {
@@ -31,6 +40,9 @@ notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
     ssize_t line_len;
     regex_t regex;
     int rerr;
+    char **tag_array=NULL;
+    int tag_array_size=DEFAULT_TAG_ARRAY_SIZE;
+
 
     config = notmuch_config_open (ctx, NULL, NULL);
     if (config == NULL)
@@ -61,11 +73,18 @@ notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
 	      "^([^ ]+) \\(([^)]*)\\)$",
 	      REG_EXTENDED);
 
+    /* Make an array of pointers to point to individual tokens */
+    tag_array=calloc(tag_array_size,sizeof(char*));
+
     while ((line_len = getline (&line, &line_size, input)) != -1) {
 	regmatch_t match[3];
-	char *message_id, *tags, *tag, *next;
+	char *message_id, *tags,  *next;
 	notmuch_message_t *message;
 	notmuch_status_t status;
+	int tag_count;
+
+	notmuch_tags_t *tag_list;
+	int i;
 
 	chomp_newline (line);
 
@@ -89,26 +108,55 @@ notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
 	    goto NEXT_LINE;
 	}
 
-	notmuch_message_freeze (message);
+	next=tags;
+	tag_count=0;
+	while(*next){
+	  while(*next && isspace(*next))
+	    next++;
+	  if (*next) {
+	    while (tag_count>= tag_array_size){
+	      tag_array_size*=2;
+	      tag_array=realloc(tag_array,tag_array_size*sizeof(char *));
+	    }
+	    tag_array[tag_count]=next;
+	    tag_count++;
+	  }
+	  while (*next && !isspace(*next))
+	    next++;
+	  if (*next){
+	    *next='\0';
+	    next++;
+	  }
+	}
+
+	qsort(tag_array,tag_count,sizeof(char*),scmp);
+	
+	tag_list = notmuch_message_get_tags (message);
+	i=0;
+	while (notmuch_tags_has_more (tag_list) && i<tag_count &&
+	       (strcmp(notmuch_tags_get (tag_list),tag_array[i])==0)){
+	  notmuch_tags_advance (tag_list);
+	  i++;
+	}
 
-	notmuch_message_remove_all_tags (message);
+	/* the only success condition is for the tag list comparison is to run
+	   off the end of both lists at the same time */
+	if (notmuch_tags_has_more (tag_list) || i<tag_count ){
+	  notmuch_message_freeze (message);
+	  notmuch_message_remove_all_tags (message);
 
-	next = tags;
-	while (next) {
-	    tag = strsep (&next, " ");
-	    if (*tag == '\0')
-		continue;
-	    status = notmuch_message_add_tag (message, tag);
+	  for (i=0; i<tag_count; i++) {
+	    status = notmuch_message_add_tag (message, tag_array[i]);
 	    if (status) {
 		fprintf (stderr,
 			 "Error applying tag %s to message %s:\n",
-			 tag, message_id);
+			 tag_array[i], message_id);
 		fprintf (stderr, "%s\n",
 			 notmuch_status_to_string (status));
 	    }
+	  }
+	  notmuch_message_thaw (message);
 	}
-
-	notmuch_message_thaw (message);
 	notmuch_message_destroy (message);
       NEXT_LINE:
 	free (message_id);
@@ -120,6 +168,9 @@ notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
     if (line)
 	free (line);
 
+    if (tag_array)
+      free (tag_array);
+
     notmuch_database_close (notmuch);
     if (input != stdin)
 	fclose (input);
-- 
1.6.5.3

Re: [PATCH] notmuch-restore.c: only update tags for messages that differ from dump file.

[Scott Robinson]

Excerpts from david's message of Mon Dec 07 19:14:48 -0800 2009:
> The patch allocates a temporary array to keep track of the current
> list of tags using calloc and grows it as neccesary using realloc.

The codebase has already well established the use of the talloc library. Why
did you break with that?
-- 
Scott Robinson | http://quadhome.com/

Q: Why are my replies five sentences or less?
A: http://five.sentenc.es/

Re: [PATCH] notmuch-restore.c: only update tags for messages that differ from dump file.

[Carl Worth]

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

On Mon,  7 Dec 2009 23:14:48 -0400, david@tethera.net wrote:
> The main feature of this patch is that it compares the list of current
> tags on a message with those read by restore. Only if the two lists
> differ is the tag list in the message replaced.  In my experiments this leads to
> a large performance improvement.

Hi David,

This is going to be a nice performance fix. Thanks for working on it!

I noticed that the code is in a style that is inconsistent with the
prevailing style of the notmuch code. So here are a few points on some
obvious style differences (there are other similar issues that I don't
mention specifically).

And I don't mean anything personal here. We all have different styles
that we prefer and find most legible. I do think it's important that the
code be in a consistent style throughout though, (and I will make a
CODING_STYLE document for the source tree soon).

> +/* for qsort */
> +static int scmp( const void *sp1, const void *sp2 )

The function name really needs to be on its own line (flush with the
left-most column). I don't like the interior whitespace for the argument
list. I really don't like a name as dramatically abbreviated as
"scmp". I'd prefer something like strcmp_for_qsort or whatever this is
actually doing.

> +    return( strcmp(*(const char **)sp1, *(const char **)sp2) );

More whitespace here. There should be a space *before* the '(' not
after, (and then not before the ')'). Finally, with void* arguments, I
like to take care of the ugly casts up front, (assigning to approriately
named local variables) rather than cluttering a function call with casts
like this.

> +    char **tag_array=NULL;
> +    int tag_array_size=DEFAULT_TAG_ARRAY_SIZE;

Need whitespace on either side of '=' here, (and similar throughout).

> +	while(*next){

More missing space. I would prefer:

	while (*next) {

> +	  while(*next && isspace(*next))
> +	    next++;

Current indentation in notmuch is 4 columns per indent level, not 2.

> +	      tag_array=realloc(tag_array,tag_array_size*sizeof(char *));

I can't read that at all with so much missing space. I'd prefer to see:

	      tag_array = realloc (tag_array, tag_array_size * sizeof (char *));

> +	while (notmuch_tags_has_more (tag_list) && i<tag_count &&
> +	       (strcmp(notmuch_tags_get (tag_list),tag_array[i])==0)){
> +	  notmuch_tags_advance (tag_list);
> +	  i++;
> +	}

While I don't mind an opening brace on the same line as an "if" or
"while" condition, I do mind it when the condition spans more than one
line. In that case, the opening brace really needs to be on a line of
its own. And again, lots of missing space in the above.

> +	  for (i=0; i<tag_count; i++) {

More missing space. Should be:

	  for (i = 0; i < tag_count; i++) {

-Carl

PS. Why is the commit mentioning using calloc, not talloc? Is there a
reason talloc is inappropriate here? Or were you just not familiar with
how to use it? I'd be glad to answer any questions you have about use of
talloc in notmuch.

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

[PATCH] notmuch-restore.c: only update tags for messages that differ from dump file.

[david]

From: David Bremner <bremner@unb.ca>

The main feature of this patch is that it compares the list of current
tags on a message with those read by restore. Only if the two lists
differ is the tag list in the message replaced.  In my experiments this leads to
a large performance improvement.

Since I had to rewrite the parsing of tags from the dump file anyway
to keep a list of tags (in case they should be written to the
database), I decided to make it a bit more robust. It sorts the
incoming tags (it is critical for the comparison of the two tag lists
that they are both sorted), and allows arbitrary whitespace (as
determined by "isspace") between tags.

The patch allocates a temporary array to keep track of the current
list of tags using talloc_array and grows it as neccesary using
talloc_realloc.
---

This is posting 3 of the patch. The second version fixed a bug.  This
version replaces calloc/realloc with talloc equivalents, prettifies
the comparison function for qsort, reindents, and adds a bunch of
whitespace.

 notmuch-restore.c |   98 +++++++++++++++++++++++++++++++++++++++++++----------
 1 files changed, 80 insertions(+), 18 deletions(-)

diff --git a/notmuch-restore.c b/notmuch-restore.c
index 1b9598d..818bd15 100644
--- a/notmuch-restore.c
+++ b/notmuch-restore.c
@@ -19,9 +19,22 @@
  */
 
 #include "notmuch-client.h"
+#include <stdlib.h>
+#include <ctype.h>
+
+#define DEFAULT_TAG_ARRAY_SIZE 2
+
+static int 
+strcmp_for_qsort (const void *ptr1, const void *ptr2)
+{
+    char * const * str1_p = ptr1;
+    char * const * str2_p = ptr2;
+
+    return strcmp(*str1_p, *str2_p);
+}
 
 int
-notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
+notmuch_restore_command (void *ctx, int argc, char *argv[])
 {
     notmuch_config_t *config;
     notmuch_database_t *notmuch;
@@ -31,6 +44,8 @@ notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
     ssize_t line_len;
     regex_t regex;
     int rerr;
+    char **tag_array = NULL;
+    int tag_array_size = DEFAULT_TAG_ARRAY_SIZE;
 
     config = notmuch_config_open (ctx, NULL, NULL);
     if (config == NULL)
@@ -61,11 +76,21 @@ notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
 	      "^([^ ]+) \\(([^)]*)\\)$",
 	      REG_EXTENDED);
 
+    /* Make an array of pointers to point to individual tokens */
+    tag_array = talloc_array (ctx, char *, tag_array_size);
+    if  (!tag_array) {
+	fprintf (stderr, "fatal: overflow in talloc_array");
+	exit(1);
+    }
+    
     while ((line_len = getline (&line, &line_size, input)) != -1) {
 	regmatch_t match[3];
-	char *message_id, *tags, *tag, *next;
+	char *message_id, *tags,  *next;
 	notmuch_message_t *message;
 	notmuch_status_t status;
+	int tag_count;
+	notmuch_tags_t *tag_list;
+	int i;
 
 	chomp_newline (line);
 
@@ -89,26 +114,61 @@ notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
 	    goto NEXT_LINE;
 	}
 
-	notmuch_message_freeze (message);
-
-	notmuch_message_remove_all_tags (message);
-
 	next = tags;
-	while (next) {
-	    tag = strsep (&next, " ");
-	    if (*tag == '\0')
-		continue;
-	    status = notmuch_message_add_tag (message, tag);
-	    if (status) {
-		fprintf (stderr,
-			 "Error applying tag %s to message %s:\n",
-			 tag, message_id);
-		fprintf (stderr, "%s\n",
-			 notmuch_status_to_string (status));
+	tag_count = 0;
+	while (*next) {
+	    while (*next && isspace(*next))
+		next++;
+	    if (*next) {
+		while (tag_count >= tag_array_size) {
+		    tag_array_size *= 2;
+		    tag_array = talloc_realloc (ctx, tag_array, char *, 
+						tag_array_size);
+		    if  (!tag_array) {
+			fprintf (stderr, "fatal: overflow in talloc_realloc");
+			exit(1);
+		    }
+		} 
+		tag_array[tag_count] = next;
+		tag_count++;
 	    }
+	    while (*next && !isspace(*next))
+		next++;
+	    if (*next) {
+		*next = '\0';
+		next++;
+	    }
+	}
+
+	qsort(tag_array,tag_count,sizeof(char*),strcmp_for_qsort);
+	
+	tag_list = notmuch_message_get_tags (message);
+	i = 0;
+	while (notmuch_tags_has_more (tag_list) && i < tag_count &&
+	       (strcmp(notmuch_tags_get (tag_list),tag_array[i]) == 0))
+	{
+	    notmuch_tags_advance (tag_list);
+	    i++;
 	}
 
-	notmuch_message_thaw (message);
+	/* the only success condition is for the tag list comparison is to run
+	   off the end of both lists at the same time */
+	if (notmuch_tags_has_more (tag_list) || i < tag_count ){
+	    notmuch_message_freeze (message);
+	    notmuch_message_remove_all_tags (message);
+
+	    for (i=0; i < tag_count; i++) {
+		status = notmuch_message_add_tag (message, tag_array[i]);
+		if (status) {
+		    fprintf (stderr,
+			     "Error applying tag %s to message %s:\n",
+			     tag_array[i], message_id);
+		    fprintf (stderr, "%s\n",
+			     notmuch_status_to_string (status));
+		}
+	    }
+	    notmuch_message_thaw (message);
+	}
 	notmuch_message_destroy (message);
       NEXT_LINE:
 	free (message_id);
@@ -120,6 +180,8 @@ notmuch_restore_command (unused (void *ctx), int argc, char *argv[])
     if (line)
 	free (line);
 
+    talloc_free (tag_array);
+
     notmuch_database_close (notmuch);
     if (input != stdin)
 	fclose (input);
-- 
1.6.5.3

Re: [PATCH] notmuch-restore.c: only update tags for messages that differ from dump file.

[Carl Worth]

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

On Tue,  8 Dec 2009 18:07:43 -0400, david@tethera.net wrote:
> This is posting 3 of the patch. The second version fixed a bug.  This
> version replaces calloc/realloc with talloc equivalents, prettifies
> the comparison function for qsort, reindents, and adds a bunch of
> whitespace.

It's odd that even after reviewing a couple of rounds of this patch, I
then went and forgot about it when I wrote my own version. I could have
saved myself some work otherwise.

Ah well, let me know if you see anything that you think should be
changed in the code that's in place now.

Thanks,

-Carl

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