[PATCH] This patch is a little finger excercise for working with git. I found a piece of code that I didn't understand at first.

[PATCH] This patch is a little finger excercise for working with git. I found a piece of code that I didn't understand at first.

[Robert Mast]

Reading it in detail I thought it allocated way too much memory and
didn't use the full size of the allocated unsigned ints for storing
bits.

Am I right, and is this the right way to patch code to notmuch?

---
 lib/query.cc |    6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/lib/query.cc b/lib/query.cc
index e9c1a2d..046663a 100644
--- a/lib/query.cc
+++ b/lib/query.cc
@@ -43,8 +43,8 @@ struct _notmuch_doc_id_set {
     unsigned int bound;
 };
 
-#define DOCIDSET_WORD(bit) ((bit) / sizeof (unsigned int))
-#define DOCIDSET_BIT(bit) ((bit) % sizeof (unsigned int))
+#define DOCIDSET_WORD(bit) ((bit) / (sizeof (unsigned int) * CHAR_BIT))
+#define DOCIDSET_BIT(bit) ((bit) % (sizeof (unsigned int) * CHAR_BIT))
 
 struct visible _notmuch_threads {
     notmuch_query_t *query;
@@ -363,7 +363,7 @@ _notmuch_doc_id_set_init (void *ctx,
 
     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));
+    bitmap = talloc_zero_array (ctx, unsigned int, (DOCIDSET_WORD(max) + 1) * sizeof (*bitmap));
 
     if (bitmap == NULL)
 	return FALSE;
-- 
1.7.9.5

Re: [PATCH] This patch is a little finger excercise for working with git. I found a piece of code that I didn't understand at first.

[Austin Clements]

If I'm reading this right, this patch reduces a 8x memory waste to a
4x memory waste, but doesn't actually eliminate the waste.

Quoth Robert Mast on Feb 03 at  7:51 pm:
> Reading it in detail I thought it allocated way too much memory and
> didn't use the full size of the allocated unsigned ints for storing
> bits.
> 
> Am I right, and is this the right way to patch code to notmuch?

Side-comments about a patch like these should go under the "---" line,
while the commit message should explain what a patch does and why.
From your message, I didn't even understand this was fixing a bug; it
sounded like a cleanup.

  http://notmuchmail.org/contributing/#index5h2
has a bit to say about commit message contents and the notmuch git
history has a lot to say.

> 
> ---
>  lib/query.cc |    6 +++---
>  1 file changed, 3 insertions(+), 3 deletions(-)
> 
> diff --git a/lib/query.cc b/lib/query.cc
> index e9c1a2d..046663a 100644
> --- a/lib/query.cc
> +++ b/lib/query.cc
> @@ -43,8 +43,8 @@ struct _notmuch_doc_id_set {
>      unsigned int bound;
>  };
>  
> -#define DOCIDSET_WORD(bit) ((bit) / sizeof (unsigned int))
> -#define DOCIDSET_BIT(bit) ((bit) % sizeof (unsigned int))
> +#define DOCIDSET_WORD(bit) ((bit) / (sizeof (unsigned int) * CHAR_BIT))
> +#define DOCIDSET_BIT(bit) ((bit) % (sizeof (unsigned int) * CHAR_BIT))

This is definitely the right thing to do, though a possibly clearer
way to fix this would be to change the type of
_notmuch_doc_id_set::bitmap to unsigned char.  Then the macros would
become simply

#define DOCIDSET_WORD(bit) ((bit) / CHAR_BIT)
#define DOCIDSET_BIT(bit) ((bit) % CHAR_BIT)

>  
>  struct visible _notmuch_threads {
>      notmuch_query_t *query;
> @@ -363,7 +363,7 @@ _notmuch_doc_id_set_init (void *ctx,
>  
>      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));
> +    bitmap = talloc_zero_array (ctx, unsigned int, (DOCIDSET_WORD(max) + 1) * sizeof (*bitmap));

This, however, isn't quite right.  I like your idea of using the
macros to compute the size, but the size argument should just be
  DOCIDSET_WORD(max) + 1
since talloc_zero_array expects the number of array elements, not the
number of bytes.

>  
>      if (bitmap == NULL)
>  	return FALSE;

[PATCH] convert bitmap to unsigned char

[Robert Mast]

---
 lib/query.cc |   10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/lib/query.cc b/lib/query.cc
index 046663a..7381a54 100644
--- a/lib/query.cc
+++ b/lib/query.cc
@@ -39,12 +39,12 @@ typedef struct _notmuch_mset_messages {
 } notmuch_mset_messages_t;
 
 struct _notmuch_doc_id_set {
-    unsigned int *bitmap;
+    unsigned char *bitmap;
     unsigned int bound;
 };
 
-#define DOCIDSET_WORD(bit) ((bit) / (sizeof (unsigned int) * CHAR_BIT))
-#define DOCIDSET_BIT(bit) ((bit) % (sizeof (unsigned int) * CHAR_BIT))
+#define DOCIDSET_WORD(bit) ((bit) / CHAR_BIT)
+#define DOCIDSET_BIT(bit) ((bit) % CHAR_BIT)
 
 struct visible _notmuch_threads {
     notmuch_query_t *query;
@@ -359,11 +359,11 @@ _notmuch_doc_id_set_init (void *ctx,
 			  GArray *arr)
 {
     unsigned int max = 0;
-    unsigned int *bitmap;
+    unsigned char *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, (DOCIDSET_WORD(max) + 1) * sizeof (*bitmap));
+    bitmap = talloc_zero_array (ctx, unsigned char, DOCIDSET_WORD(max) + 1);
 
     if (bitmap == NULL)
 	return FALSE;
-- 
1.7.9.5

[PATCH] bitmap:improve memory usage using CHAR_BITS and unsigned CHAR

[Robert Mast]

A little bug-fix to learn how to contribute to nutmuch, this time a combined commit with git rebase to provide one patch from 15.1.
---
 lib/query.cc |   10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/lib/query.cc b/lib/query.cc
index e9c1a2d..7381a54 100644
--- a/lib/query.cc
+++ b/lib/query.cc
@@ -39,12 +39,12 @@ typedef struct _notmuch_mset_messages {
 } notmuch_mset_messages_t;
 
 struct _notmuch_doc_id_set {
-    unsigned int *bitmap;
+    unsigned char *bitmap;
     unsigned int bound;
 };
 
-#define DOCIDSET_WORD(bit) ((bit) / sizeof (unsigned int))
-#define DOCIDSET_BIT(bit) ((bit) % sizeof (unsigned int))
+#define DOCIDSET_WORD(bit) ((bit) / CHAR_BIT)
+#define DOCIDSET_BIT(bit) ((bit) % CHAR_BIT)
 
 struct visible _notmuch_threads {
     notmuch_query_t *query;
@@ -359,11 +359,11 @@ _notmuch_doc_id_set_init (void *ctx,
 			  GArray *arr)
 {
     unsigned int max = 0;
-    unsigned int *bitmap;
+    unsigned char *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));
+    bitmap = talloc_zero_array (ctx, unsigned char, DOCIDSET_WORD(max) + 1);
 
     if (bitmap == NULL)
 	return FALSE;
-- 
1.7.9.5

Re: [PATCH] convert bitmap to unsigned char

[Carl Worth]

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

Robert Mast <beheerder@tekenbeetziekten.nl> writes:
> ---

Hi Robert,

It looks like the git exercise is proving useful. Keep it up!

If you look through the git logs a bit you'll find that the overwhelming
convention is for a commit message to have a single-line summary
followed by a (potentially longer) expanded comment.

The convention I like best is for the single-line summary to
efficiently  describe everything about "what" the patch does. If it's
hard to fit this into a single line there's a good chance your patch
should be split up. With your commit message here, the one-line summary
is great, (and much better than in your first submission).

The expanded comment should describe the "why" of the change. And here,
your commit message doesn't have anything. So I'm left wondering why
your commit exists. Does this save memory? Does this fix some type error
or expected alignment somewhere? etc.

Please re-submit your patch with a little more explanation of the
motivation behind the patch.

-Carl

PS. I do know that you did have more in the commit message originally,
and Austin recommended removing "snide" issues, (doubts and
meta-questions about the patch---things that don't belong in the commit
history).

Your previous commit message was:

  Reading it in detail I thought it allocated way too much memory and
  didn't use the full size of the allocated unsigned ints for storing
  bits.

  Am I right, and is this the right way to patch code to notmuch?

I'm not actually looking at the code in context now, so I can't render a
correct commit message, but this attempted rewording should hopefully
give you the idea:

  Using char instead of int allows for simpler definitions of the
  DOCIDSET macros so the code is easier to understand.

  ---

  Am I reading that correctly? Or is there also some space saving
  happening here as well? Please re-submit a new patch with a commit
  message that makes things clear one way or the other.

Do you see how this "why" part of the commit message is ready to stand
alone in our commit history (assuming it's correct and
accepted). Meta-questions like "is this even a sane way of doing
things?" are great to ask, and very helpful for code reviewers, but best
placed after the "---" so that they don't become part of the commit
message.

Thanks for playing with notmuch!

-Carl

-- 
carl.d.worth@intel.com

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

[PATCH] bitmap:improve memory usage using CHAR_BITS and unsigned CHAR

[Robert Mast]

diff --git a/lib/query.cc b/lib/query.cc
index e9c1a2d..7381a54 100644
--- a/lib/query.cc
+++ b/lib/query.cc
@@ -39,12 +39,12 @@ typedef struct _notmuch_mset_messages {
 } notmuch_mset_messages_t;
 
 struct _notmuch_doc_id_set {
-    unsigned int *bitmap;
+    unsigned char *bitmap;
     unsigned int bound;
 };
 
-#define DOCIDSET_WORD(bit) ((bit) / sizeof (unsigned int))
-#define DOCIDSET_BIT(bit) ((bit) % sizeof (unsigned int))
+#define DOCIDSET_WORD(bit) ((bit) / CHAR_BIT)
+#define DOCIDSET_BIT(bit) ((bit) % CHAR_BIT)
 
 struct visible _notmuch_threads {
     notmuch_query_t *query;
@@ -359,11 +359,11 @@ _notmuch_doc_id_set_init (void *ctx,
 			  GArray *arr)
 {
     unsigned int max = 0;
-    unsigned int *bitmap;
+    unsigned char *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));
+    bitmap = talloc_zero_array (ctx, unsigned char, DOCIDSET_WORD(max) + 1);
 
     if (bitmap == NULL)
 	return FALSE;
-- 
1.7.9.5

RE: [english 100%] [PATCH] bitmap:improve memory usage using CHAR_BITS and unsigned CHAR

[Robert Mast]

Somehow my comments don't get through... I'll try it another way.

-----Oorspronkelijk bericht-----
Van: Robert Mast [mailto:beheerder@tekenbeetziekten.nl] 
Verzonden: woensdag 13 februari 2013 16:12
Aan: notmuch@notmuchmail.org
CC: Robert Mast
Onderwerp: [english 100%] [PATCH] bitmap:improve memory usage using CHAR_BITS and unsigned CHAR

diff --git a/lib/query.cc b/lib/query.cc index e9c1a2d..7381a54 100644
--- a/lib/query.cc
+++ b/lib/query.cc
@@ -39,12 +39,12 @@ typedef struct _notmuch_mset_messages {  } notmuch_mset_messages_t;
 
 struct _notmuch_doc_id_set {
-    unsigned int *bitmap;
+    unsigned char *bitmap;
     unsigned int bound;
 };
 
-#define DOCIDSET_WORD(bit) ((bit) / sizeof (unsigned int)) -#define DOCIDSET_BIT(bit) ((bit) % sizeof (unsigned int))
+#define DOCIDSET_WORD(bit) ((bit) / CHAR_BIT) #define DOCIDSET_BIT(bit) 
+((bit) % CHAR_BIT)
 
 struct visible _notmuch_threads {
     notmuch_query_t *query;
@@ -359,11 +359,11 @@ _notmuch_doc_id_set_init (void *ctx,
 			  GArray *arr)
 {
     unsigned int max = 0;
-    unsigned int *bitmap;
+    unsigned char *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));
+    bitmap = talloc_zero_array (ctx, unsigned char, DOCIDSET_WORD(max) 
+ + 1);
 
     if (bitmap == NULL)
 	return FALSE;
--
1.7.9.5


.

[PATCH] bitmap:improve memory usage using CHAR_BITS and unsigned CHAR

[Robert Mast]

Using char instead of int allows for simpler definitions of the
DOCIDSET macros so the code is easier to understand and consistent with
respect to memory-usage. Estimated reduction of memory-usage for
bitmap about 8 times.

---

Re-submission for comment-reasons.

---
---
 lib/query.cc |   10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/lib/query.cc b/lib/query.cc
index e9c1a2d..7381a54 100644
--- a/lib/query.cc
+++ b/lib/query.cc
@@ -39,12 +39,12 @@ typedef struct _notmuch_mset_messages {
 } notmuch_mset_messages_t;
 
 struct _notmuch_doc_id_set {
-    unsigned int *bitmap;
+    unsigned char *bitmap;
     unsigned int bound;
 };
 
-#define DOCIDSET_WORD(bit) ((bit) / sizeof (unsigned int))
-#define DOCIDSET_BIT(bit) ((bit) % sizeof (unsigned int))
+#define DOCIDSET_WORD(bit) ((bit) / CHAR_BIT)
+#define DOCIDSET_BIT(bit) ((bit) % CHAR_BIT)
 
 struct visible _notmuch_threads {
     notmuch_query_t *query;
@@ -359,11 +359,11 @@ _notmuch_doc_id_set_init (void *ctx,
 			  GArray *arr)
 {
     unsigned int max = 0;
-    unsigned int *bitmap;
+    unsigned char *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));
+    bitmap = talloc_zero_array (ctx, unsigned char, DOCIDSET_WORD(max) + 1);
 
     if (bitmap == NULL)
 	return FALSE;
-- 
1.7.9.5

Re: [PATCH] bitmap:improve memory usage using CHAR_BITS and unsigned CHAR

[Carl Worth]

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

Robert Mast <beheerder@tekenbeetziekten.nl> writes:
> Re-submission for comment-reasons.

Very nicely done, Robert. Thanks.

-Carl (who's not quite merging patches again yet, but likely will be soon)

-- 
carl.d.worth@intel.com

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

Re: [PATCH] bitmap:improve memory usage using CHAR_BITS and unsigned CHAR

[David Bremner]

Robert Mast <beheerder@tekenbeetziekten.nl> writes:

> Using char instead of int allows for simpler definitions of the
> DOCIDSET macros so the code is easier to understand and consistent with
> respect to memory-usage. Estimated reduction of memory-usage for
> bitmap about 8 times.

Pushed to master.

I did a bit of testing, and this yields about a 7% improvement in the
total memory allocated on the medium corpus (running
performance-tests/M00-new) and about a 3% speedup running the large
corpus.  These are definitely improvements worth having, but I think I
won't push it to the bug fix release, but rather wait for the next
regular release.

d