threads / patch / 45076

patchdir: avoid allocation in fill_directory()

Subject: [PATCH] dir: avoid allocation in fill_directory()

## tl;dr

4 messages between Feb 7, 2017 and Feb 10, 2017. Diffs are folded; open one to read it.

replies: 3people: 3as markdown or json

René Scharfe· Feb 7, 2017, 22:04 UTC · lore

Pass the match member of the first pathspec item directly to read_directory() instead of using common_prefix() to duplicate it first, thus avoiding memory duplication, strlen(3) and free(3).

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
This updates 966de3028 (dir: convert fill_directory to use the pathspec
struct interface).  The result is closer to the original, yet still
using the modern interface.
This patch eerily resembles 2b189435 (dir: simplify fill_directory()).
 dir.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
Show changes to dir.c +3 −4
diff --git a/dir.c b/dir.c
index 65c3e681b8..4541f9e146 100644
--- a/dir.c
+++ b/dir.c
@@ -174,20 +174,19 @@ char *common_prefix(const struct pathspec *pathspec)
 
 int fill_directory(struct dir_struct *dir, const struct pathspec *pathspec)
 {
-	char *prefix;
+	const char *prefix;
 	size_t prefix_len;
 
 	/*
 	 * Calculate common prefix for the pathspec, and
 	 * use that to optimize the directory walk
 	 */
-	prefix = common_prefix(pathspec);
-	prefix_len = prefix ? strlen(prefix) : 0;
+	prefix_len = common_prefix_len(pathspec);
+	prefix = prefix_len ? pathspec->items[0].match : "";
 
 	/* Read the directory and prune it */
 	read_directory(dir, prefix, prefix_len, pathspec);
 
-	free(prefix);
 	return prefix_len;
 }
 

-- 
2.11.1
Duy Nguyen· Feb 8, 2017, 06:22 UTC · re: René Scharfe · lore

Re: [PATCH] dir: avoid allocation in fill_directory()

On Wed, Feb 8, 2017 at 5:04 AM, René Scharfe <l.s.r@web.de> wrote:
> Pass the match member of the first pathspec item directly to
> read_directory() instead of using common_prefix() to duplicate it first,
> thus avoiding memory duplication, strlen(3) and free(3).

How about killing common_prefix()? There are two other callers in ls-files.c and commit.c and it looks safe to do (but I didn't look very hard).

Show 20 quoted lines
> diff --git a/dir.c b/dir.c
> index 65c3e681b8..4541f9e146 100644
> --- a/dir.c
> +++ b/dir.c
> @@ -174,20 +174,19 @@ char *common_prefix(const struct pathspec *pathspec)
>
>  int fill_directory(struct dir_struct *dir, const struct pathspec *pathspec)
>  {
> -       char *prefix;
> +       const char *prefix;
>         size_t prefix_len;
>
>         /*
>          * Calculate common prefix for the pathspec, and
>          * use that to optimize the directory walk
>          */
> -       prefix = common_prefix(pathspec);
> -       prefix_len = prefix ? strlen(prefix) : 0;
> +       prefix_len = common_prefix_len(pathspec);
> +       prefix = prefix_len ? pathspec->items[0].match : "";

There's a subtle difference. Before the patch, prefix[prefix_len] is NUL. After the patch, it's not always true. If some code (incorrectly) depends on that, this patch exposes it. I had a look inside read_directory() though and it looks like no such code exists. So, all good.

Show 7 quoted lines
>
>         /* Read the directory and prune it */
>         read_directory(dir, prefix, prefix_len, pathspec);
>
> -       free(prefix);
>         return prefix_len;
>  }
-- 
Duy
Brandon Williams· Feb 8, 2017, 19:54 UTC · re: Duy Nguyen · lore

Re: [PATCH] dir: avoid allocation in fill_directory()

On 02/08, Duy Nguyen wrote:
Show 35 quoted lines
> On Wed, Feb 8, 2017 at 5:04 AM, René Scharfe <l.s.r@web.de> wrote:
> > Pass the match member of the first pathspec item directly to
> > read_directory() instead of using common_prefix() to duplicate it first,
> > thus avoiding memory duplication, strlen(3) and free(3).
> 
> How about killing common_prefix()? There are two other callers in
> ls-files.c and commit.c and it looks safe to do (but I didn't look
> very hard).
> 
> > diff --git a/dir.c b/dir.c
> > index 65c3e681b8..4541f9e146 100644
> > --- a/dir.c
> > +++ b/dir.c
> > @@ -174,20 +174,19 @@ char *common_prefix(const struct pathspec *pathspec)
> >
> >  int fill_directory(struct dir_struct *dir, const struct pathspec *pathspec)
> >  {
> > -       char *prefix;
> > +       const char *prefix;
> >         size_t prefix_len;
> >
> >         /*
> >          * Calculate common prefix for the pathspec, and
> >          * use that to optimize the directory walk
> >          */
> > -       prefix = common_prefix(pathspec);
> > -       prefix_len = prefix ? strlen(prefix) : 0;
> > +       prefix_len = common_prefix_len(pathspec);
> > +       prefix = prefix_len ? pathspec->items[0].match : "";
> 
> There's a subtle difference. Before the patch, prefix[prefix_len] is
> NUL. After the patch, it's not always true. If some code (incorrectly)
> depends on that, this patch exposes it. I had a look inside
> read_directory() though and it looks like no such code exists. So, all
> good.

Yeah I had the exact same thought when looking at this, but I agree everything looks fine. And if something does indeed depend on prefix having a \0 at prefix_len then this will allow us to more easily find the bug and fix it.

Show 10 quoted lines
> 
> >
> >         /* Read the directory and prune it */
> >         read_directory(dir, prefix, prefix_len, pathspec);
> >
> > -       free(prefix);
> >         return prefix_len;
> >  }
> -- 
> Duy
-- 
Brandon Williams
René Scharfe· Feb 10, 2017, 19:42 UTC · re: Duy Nguyen · lore

Re: [PATCH] dir: avoid allocation in fill_directory()

Am 08.02.2017 um 07:22 schrieb Duy Nguyen:
Show 8 quoted lines
> On Wed, Feb 8, 2017 at 5:04 AM, René Scharfe <l.s.r@web.de> wrote:
>> Pass the match member of the first pathspec item directly to
>> read_directory() instead of using common_prefix() to duplicate it first,
>> thus avoiding memory duplication, strlen(3) and free(3).
>
> How about killing common_prefix()? There are two other callers in
> ls-files.c and commit.c and it looks safe to do (but I didn't look
> very hard).

I would like that, but it doesn't look like it's worth it. I have a patch series for making overlay_tree_on_cache() take pointer+length, but it's surprisingly long and bloats the code. Duplicating a small piece of memory once per command doesn't look so bad in comparison.

(The payoff for avoiding an allocation is higher for library functions like fill_directory().)

But while working on that I found two opportunities for improvement in prune_cache(). I'll send patches shortly.

Show 5 quoted lines
> There's a subtle difference. Before the patch, prefix[prefix_len] is
> NUL. After the patch, it's not always true. If some code (incorrectly)
> depends on that, this patch exposes it. I had a look inside
> read_directory() though and it looks like no such code exists. So, all
> good.
Thanks for checking.
NB: The code before 966de302 (dir: convert fill_directory to use the 
pathspec struct interface, committed 2017-01-04) made the same 
assumption, i.e. that NUL is not needed.
René

← back to recent threads