[PATCH 0/3] a few grep patches

[PATCH 0/3] a few grep patches

[Rasmus Villemoes]

I believe the first two should be ok, but I'm not sure what I myself
think of the third one. Perhaps the saving is not worth the
complexity, but it does annoy my optimization nerve to see all the
unnecessary duplicated work being done.

Rasmus Villemoes (3):
  grep: move grep_source_init outside critical section
  grep: simplify grep_oid and grep_file
  grep: avoid one strdup() per file

 builtin/grep.c | 25 ++++++++++++-------------
 grep.c         |  8 ++++++--
 2 files changed, 18 insertions(+), 15 deletions(-)

-- 
2.15.1

[PATCH 1/3] grep: move grep_source_init outside critical section

[Rasmus Villemoes]

grep_source_init typically does three strdup()s, and in the threaded
case, the call from add_work() happens while holding grep_mutex.

We can thus reduce the time we hold grep_mutex by moving the
grep_source_init() call out of add_work(), and simply have add_work()
copy the initialized structure to the available slot in the todo
array.

This also simplifies the prototype of add_work(), since it no longer
needs to duplicate all the parameters of grep_source_init(). In the
callers of add_work(), we get to reduce the amount of code duplicated in
the threaded and non-threaded cases slightly (avoiding repeating the
"GREP_SOURCE_OID, pathbuf.buf, path, oid" argument list); a subsequent
cleanup patch will make that even more so.

Signed-off-by: Rasmus Villemoes <rv@rasmusvillemoes.dk>
---
 builtin/grep.c | 19 ++++++++++---------
 1 file changed, 10 insertions(+), 9 deletions(-)

diff --git a/builtin/grep.c b/builtin/grep.c
index 3ca4ac80d..4a4f15172 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -92,8 +92,7 @@ static pthread_cond_t cond_result;
 
 static int skip_first_line;
 
-static void add_work(struct grep_opt *opt, enum grep_source_type type,
-		     const char *name, const char *path, const void *id)
+static void add_work(struct grep_opt *opt, const struct grep_source *gs)
 {
 	grep_lock();
 
@@ -101,7 +100,7 @@ static void add_work(struct grep_opt *opt, enum grep_source_type type,
 		pthread_cond_wait(&cond_write, &grep_mutex);
 	}
 
-	grep_source_init(&todo[todo_end].source, type, name, path, id);
+	todo[todo_end].source = *gs;
 	if (opt->binary != GREP_BINARY_TEXT)
 		grep_source_load_driver(&todo[todo_end].source);
 	todo[todo_end].done = 0;
@@ -317,6 +316,7 @@ static int grep_oid(struct grep_opt *opt, const struct object_id *oid,
 		     const char *path)
 {
 	struct strbuf pathbuf = STRBUF_INIT;
+	struct grep_source gs;
 
 	if (opt->relative && opt->prefix_length) {
 		quote_path_relative(filename + tree_name_len, opt->prefix, &pathbuf);
@@ -325,18 +325,18 @@ static int grep_oid(struct grep_opt *opt, const struct object_id *oid,
 		strbuf_addstr(&pathbuf, filename);
 	}
 
+	grep_source_init(&gs, GREP_SOURCE_OID, pathbuf.buf, path, oid);
+
 #ifndef NO_PTHREADS
 	if (num_threads) {
-		add_work(opt, GREP_SOURCE_OID, pathbuf.buf, path, oid);
+		add_work(opt, &gs);
 		strbuf_release(&pathbuf);
 		return 0;
 	} else
 #endif
 	{
-		struct grep_source gs;
 		int hit;
 
-		grep_source_init(&gs, GREP_SOURCE_OID, pathbuf.buf, path, oid);
 		strbuf_release(&pathbuf);
 		hit = grep_source(opt, &gs);
 
@@ -348,24 +348,25 @@ static int grep_oid(struct grep_opt *opt, const struct object_id *oid,
 static int grep_file(struct grep_opt *opt, const char *filename)
 {
 	struct strbuf buf = STRBUF_INIT;
+	struct grep_source gs;
 
 	if (opt->relative && opt->prefix_length)
 		quote_path_relative(filename, opt->prefix, &buf);
 	else
 		strbuf_addstr(&buf, filename);
 
+	grep_source_init(&gs, GREP_SOURCE_FILE, buf.buf, filename, filename);
+
 #ifndef NO_PTHREADS
 	if (num_threads) {
-		add_work(opt, GREP_SOURCE_FILE, buf.buf, filename, filename);
+		add_work(opt, &gs);
 		strbuf_release(&buf);
 		return 0;
 	} else
 #endif
 	{
-		struct grep_source gs;
 		int hit;
 
-		grep_source_init(&gs, GREP_SOURCE_FILE, buf.buf, filename, filename);
 		strbuf_release(&buf);
 		hit = grep_source(opt, &gs);
 
-- 
2.15.1

Re: [PATCH 1/3] grep: move grep_source_init outside critical section

[Jeff King]

On Thu, Feb 15, 2018 at 10:56:13PM +0100, Rasmus Villemoes wrote:

> grep_source_init typically does three strdup()s, and in the threaded
> case, the call from add_work() happens while holding grep_mutex.
> 
> We can thus reduce the time we hold grep_mutex by moving the
> grep_source_init() call out of add_work(), and simply have add_work()
> copy the initialized structure to the available slot in the todo
> array.
> 
> This also simplifies the prototype of add_work(), since it no longer
> needs to duplicate all the parameters of grep_source_init(). In the
> callers of add_work(), we get to reduce the amount of code duplicated in
> the threaded and non-threaded cases slightly (avoiding repeating the
> "GREP_SOURCE_OID, pathbuf.buf, path, oid" argument list); a subsequent
> cleanup patch will make that even more so.

I think this makes sense. It does blur the memory ownership lines of the
grep_source, though. Can we make that more clear with a comment here:

> +	grep_source_init(&gs, GREP_SOURCE_OID, pathbuf.buf, path, oid);
> +
>  #ifndef NO_PTHREADS
>  	if (num_threads) {
> -		add_work(opt, GREP_SOURCE_OID, pathbuf.buf, path, oid);
> +		add_work(opt, &gs);
>  		strbuf_release(&pathbuf);
>  		return 0;
>  	} else

like:

  /* leak grep_source, whose fields are now owned by add_work() */

or something? We could even memset() it back to all-zeroes to avoid an
accidental call to grep_source_clear(), but that's probably unnecessary
if we have a comment.

-Peff

Re: [PATCH 1/3] grep: move grep_source_init outside critical section

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> I think this makes sense. It does blur the memory ownership lines of the
> grep_source, though. Can we make that more clear with a comment here:
>
>> +	grep_source_init(&gs, GREP_SOURCE_OID, pathbuf.buf, path, oid);
>> +
>>  #ifndef NO_PTHREADS
>>  	if (num_threads) {
>> -		add_work(opt, GREP_SOURCE_OID, pathbuf.buf, path, oid);
>> +		add_work(opt, &gs);
>>  		strbuf_release(&pathbuf);
>>  		return 0;
>>  	} else
>
> like:
>
>   /* leak grep_source, whose fields are now owned by add_work() */
>
> or something? We could even memset() it back to all-zeroes to avoid an
> accidental call to grep_source_clear(), but that's probably unnecessary
> if we have a comment.

I share the same uneasiness about the fuzzy memory ownership this
change brings in.  Thanks for suggesting improvements.

[PATCH 2/3] grep: simplify grep_oid and grep_file

[Rasmus Villemoes]

In the NO_PTHREADS or !num_threads case, this doesn't change
anything. In the threaded case, note that grep_source_init duplicates
its third argument, so there is no need to keep [path]buf.buf alive
across the call of add_work().

Signed-off-by: Rasmus Villemoes <rv@rasmusvillemoes.dk>
---
 builtin/grep.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/builtin/grep.c b/builtin/grep.c
index 4a4f15172..593f48d59 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -326,18 +326,17 @@ static int grep_oid(struct grep_opt *opt, const struct object_id *oid,
 	}
 
 	grep_source_init(&gs, GREP_SOURCE_OID, pathbuf.buf, path, oid);
+	strbuf_release(&pathbuf);
 
 #ifndef NO_PTHREADS
 	if (num_threads) {
 		add_work(opt, &gs);
-		strbuf_release(&pathbuf);
 		return 0;
 	} else
 #endif
 	{
 		int hit;
 
-		strbuf_release(&pathbuf);
 		hit = grep_source(opt, &gs);
 
 		grep_source_clear(&gs);
@@ -356,18 +355,17 @@ static int grep_file(struct grep_opt *opt, const char *filename)
 		strbuf_addstr(&buf, filename);
 
 	grep_source_init(&gs, GREP_SOURCE_FILE, buf.buf, filename, filename);
+	strbuf_release(&buf);
 
 #ifndef NO_PTHREADS
 	if (num_threads) {
 		add_work(opt, &gs);
-		strbuf_release(&buf);
 		return 0;
 	} else
 #endif
 	{
 		int hit;
 
-		strbuf_release(&buf);
 		hit = grep_source(opt, &gs);
 
 		grep_source_clear(&gs);
-- 
2.15.1

[PATCH 3/3] grep: avoid one strdup() per file

[Rasmus Villemoes]

There is only one instance of grep_source_init(GREP_SOURCE_FILE), and in
that case the path and identifier arguments are equal - not just as
strings, but the same pointer is passed. So we can save some time and
memory by reusing the gs->path = xstrdup_or_null(path) we have already
done as gs->identifier, and changing grep_source_clear accordingly
to avoid a double free.

Signed-off-by: Rasmus Villemoes <rv@rasmusvillemoes.dk>
---
 grep.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/grep.c b/grep.c
index 3d7cd0e96..b1532b1b6 100644
--- a/grep.c
+++ b/grep.c
@@ -1972,7 +1972,8 @@ void grep_source_init(struct grep_source *gs, enum grep_source_type type,
 
 	switch (type) {
 	case GREP_SOURCE_FILE:
-		gs->identifier = xstrdup(identifier);
+		gs->identifier = identifier == path ?
+			gs->path : xstrdup(identifier);
 		break;
 	case GREP_SOURCE_OID:
 		gs->identifier = oiddup(identifier);
@@ -1986,7 +1987,10 @@ void grep_source_init(struct grep_source *gs, enum grep_source_type type,
 void grep_source_clear(struct grep_source *gs)
 {
 	FREE_AND_NULL(gs->name);
-	FREE_AND_NULL(gs->path);
+	if (gs->path == gs->identifier)
+		gs->path = NULL;
+	else
+		FREE_AND_NULL(gs->path);
 	FREE_AND_NULL(gs->identifier);
 	grep_source_clear_data(gs);
 }
-- 
2.15.1

Re: [PATCH 3/3] grep: avoid one strdup() per file

[Jeff King]

On Thu, Feb 15, 2018 at 10:56:15PM +0100, Rasmus Villemoes wrote:

> There is only one instance of grep_source_init(GREP_SOURCE_FILE), and in
> that case the path and identifier arguments are equal - not just as
> strings, but the same pointer is passed. So we can save some time and
> memory by reusing the gs->path = xstrdup_or_null(path) we have already
> done as gs->identifier, and changing grep_source_clear accordingly
> to avoid a double free.

IMHO this special case is not really worth it, unless we can show that
those few bytes saved somehow make a measurable difference in either
peak memory or execution speed.

-Peff

Re: [PATCH 0/3] a few grep patches

[Brandon Williams]

On 02/15, Rasmus Villemoes wrote:
> I believe the first two should be ok, but I'm not sure what I myself
> think of the third one. Perhaps the saving is not worth the
> complexity, but it does annoy my optimization nerve to see all the
> unnecessary duplicated work being done.

I agree, the first two seem like good changes to me though I don't know
if i like the complexity that the third introduces.

> 
> Rasmus Villemoes (3):
>   grep: move grep_source_init outside critical section
>   grep: simplify grep_oid and grep_file
>   grep: avoid one strdup() per file
> 
>  builtin/grep.c | 25 ++++++++++++-------------
>  grep.c         |  8 ++++++--
>  2 files changed, 18 insertions(+), 15 deletions(-)
> 
> -- 
> 2.15.1
> 

-- 
Brandon Williams

[PATCH v2 0/2] two small grep patches

[Rasmus Villemoes]

Changes in v2:

- Drop patch 3 with dubious gain/complexity ratio
- Add comments regarding ownership of grep_source

I was a little torn between copy-pasting the comment or just saying
"see above" in the second case. I think a memset would be confusing,
at least unless one extends the comment to explain why one then does
the memset despite the first half of the comment.

Rasmus Villemoes (2):
  grep: move grep_source_init outside critical section
  grep: simplify grep_oid and grep_file

 builtin/grep.c | 33 ++++++++++++++++++++-------------
 1 file changed, 20 insertions(+), 13 deletions(-)

-- 
2.15.1

[PATCH v2 1/2] grep: move grep_source_init outside critical section

[Rasmus Villemoes]

grep_source_init typically does three strdup()s, and in the threaded
case, the call from add_work() happens while holding grep_mutex.

We can thus reduce the time we hold grep_mutex by moving the
grep_source_init() call out of add_work(), and simply have add_work()
copy the initialized structure to the available slot in the todo
array.

This also simplifies the prototype of add_work(), since it no longer
needs to duplicate all the parameters of grep_source_init(). In the
callers of add_work(), we get to reduce the amount of code duplicated in
the threaded and non-threaded cases slightly (avoiding repeating the
long "GREP_SOURCE_OID, pathbuf.buf, path, oid" argument list); a
subsequent cleanup patch will make that even more so.

Signed-off-by: Rasmus Villemoes <rv@rasmusvillemoes.dk>
---
 builtin/grep.c | 27 ++++++++++++++++++---------
 1 file changed, 18 insertions(+), 9 deletions(-)

diff --git a/builtin/grep.c b/builtin/grep.c
index 3ca4ac80d..aad422bb6 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -92,8 +92,7 @@ static pthread_cond_t cond_result;
 
 static int skip_first_line;
 
-static void add_work(struct grep_opt *opt, enum grep_source_type type,
-		     const char *name, const char *path, const void *id)
+static void add_work(struct grep_opt *opt, const struct grep_source *gs)
 {
 	grep_lock();
 
@@ -101,7 +100,7 @@ static void add_work(struct grep_opt *opt, enum grep_source_type type,
 		pthread_cond_wait(&cond_write, &grep_mutex);
 	}
 
-	grep_source_init(&todo[todo_end].source, type, name, path, id);
+	todo[todo_end].source = *gs;
 	if (opt->binary != GREP_BINARY_TEXT)
 		grep_source_load_driver(&todo[todo_end].source);
 	todo[todo_end].done = 0;
@@ -317,6 +316,7 @@ static int grep_oid(struct grep_opt *opt, const struct object_id *oid,
 		     const char *path)
 {
 	struct strbuf pathbuf = STRBUF_INIT;
+	struct grep_source gs;
 
 	if (opt->relative && opt->prefix_length) {
 		quote_path_relative(filename + tree_name_len, opt->prefix, &pathbuf);
@@ -325,18 +325,22 @@ static int grep_oid(struct grep_opt *opt, const struct object_id *oid,
 		strbuf_addstr(&pathbuf, filename);
 	}
 
+	grep_source_init(&gs, GREP_SOURCE_OID, pathbuf.buf, path, oid);
+
 #ifndef NO_PTHREADS
 	if (num_threads) {
-		add_work(opt, GREP_SOURCE_OID, pathbuf.buf, path, oid);
+		/*
+		 * add_work() copies gs and thus assumes ownership of
+		 * its fields, so do not call grep_source_clear()
+		 */
+		add_work(opt, &gs);
 		strbuf_release(&pathbuf);
 		return 0;
 	} else
 #endif
 	{
-		struct grep_source gs;
 		int hit;
 
-		grep_source_init(&gs, GREP_SOURCE_OID, pathbuf.buf, path, oid);
 		strbuf_release(&pathbuf);
 		hit = grep_source(opt, &gs);
 
@@ -348,24 +352,29 @@ static int grep_oid(struct grep_opt *opt, const struct object_id *oid,
 static int grep_file(struct grep_opt *opt, const char *filename)
 {
 	struct strbuf buf = STRBUF_INIT;
+	struct grep_source gs;
 
 	if (opt->relative && opt->prefix_length)
 		quote_path_relative(filename, opt->prefix, &buf);
 	else
 		strbuf_addstr(&buf, filename);
 
+	grep_source_init(&gs, GREP_SOURCE_FILE, buf.buf, filename, filename);
+
 #ifndef NO_PTHREADS
 	if (num_threads) {
-		add_work(opt, GREP_SOURCE_FILE, buf.buf, filename, filename);
+		/*
+		 * add_work() copies gs and thus assumes ownership of
+		 * its fields, so do not call grep_source_clear()
+		 */
+		add_work(opt, &gs);
 		strbuf_release(&buf);
 		return 0;
 	} else
 #endif
 	{
-		struct grep_source gs;
 		int hit;
 
-		grep_source_init(&gs, GREP_SOURCE_FILE, buf.buf, filename, filename);
 		strbuf_release(&buf);
 		hit = grep_source(opt, &gs);
 
-- 
2.15.1

[PATCH v2 2/2] grep: simplify grep_oid and grep_file

[Rasmus Villemoes]

In the NO_PTHREADS or !num_threads case, this doesn't change
anything. In the threaded case, note that grep_source_init duplicates
its third argument, so there is no need to keep [path]buf.buf alive
across the call of add_work().

Signed-off-by: Rasmus Villemoes <rv@rasmusvillemoes.dk>
---
 builtin/grep.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/builtin/grep.c b/builtin/grep.c
index aad422bb6..9a8e4fada 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -326,6 +326,7 @@ static int grep_oid(struct grep_opt *opt, const struct object_id *oid,
 	}
 
 	grep_source_init(&gs, GREP_SOURCE_OID, pathbuf.buf, path, oid);
+	strbuf_release(&pathbuf);
 
 #ifndef NO_PTHREADS
 	if (num_threads) {
@@ -334,14 +335,12 @@ static int grep_oid(struct grep_opt *opt, const struct object_id *oid,
 		 * its fields, so do not call grep_source_clear()
 		 */
 		add_work(opt, &gs);
-		strbuf_release(&pathbuf);
 		return 0;
 	} else
 #endif
 	{
 		int hit;
 
-		strbuf_release(&pathbuf);
 		hit = grep_source(opt, &gs);
 
 		grep_source_clear(&gs);
@@ -360,6 +359,7 @@ static int grep_file(struct grep_opt *opt, const char *filename)
 		strbuf_addstr(&buf, filename);
 
 	grep_source_init(&gs, GREP_SOURCE_FILE, buf.buf, filename, filename);
+	strbuf_release(&buf);
 
 #ifndef NO_PTHREADS
 	if (num_threads) {
@@ -368,14 +368,12 @@ static int grep_file(struct grep_opt *opt, const char *filename)
 		 * its fields, so do not call grep_source_clear()
 		 */
 		add_work(opt, &gs);
-		strbuf_release(&buf);
 		return 0;
 	} else
 #endif
 	{
 		int hit;
 
-		strbuf_release(&buf);
 		hit = grep_source(opt, &gs);
 
 		grep_source_clear(&gs);
-- 
2.15.1

Re: [PATCH v2 0/2] two small grep patches

[Jeff King]

On Fri, Feb 23, 2018 at 03:47:55PM +0100, Rasmus Villemoes wrote:

> Changes in v2:
> 
> - Drop patch 3 with dubious gain/complexity ratio
> - Add comments regarding ownership of grep_source
> 
> I was a little torn between copy-pasting the comment or just saying
> "see above" in the second case. I think a memset would be confusing,
> at least unless one extends the comment to explain why one then does
> the memset despite the first half of the comment.

This looks good to me. Thanks for following up.

-Peff