git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH v2 16/19] tree-diff: reuse base str(buf) memory on sub-tree recursion

From
Kirill Smelkov <kirr@navytux.spb.ru>
Date
Mar 27, 2014, 14:22 UTC
Message-ID
<20140327142207.GB17333@mini.zxlink>
In-Reply-To
<20140325092320.GC3777@mini.zxlink>
On Tue, Mar 25, 2014 at 01:23:20PM +0400, Kirill Smelkov wrote:
Show 75 quoted lines
> On Mon, Mar 24, 2014 at 02:43:36PM -0700, Junio C Hamano wrote:
> > Kirill Smelkov <kirr@mns.spb.ru> writes:
> > 
> > > instead of allocating it all the time for every subtree in
> > > __diff_tree_sha1, let's allocate it once in diff_tree_sha1, and then all
> > > callee just use it in stacking style, without memory allocations.
> > >
> > > This should be faster, and for me this change gives the following
> > > slight speedups for
> > >
> > >     git log --raw --no-abbrev --no-renames --format='%H'
> > >
> > >                 navy.git    linux.git v3.10..v3.11
> > >
> > >     before      0.618s      1.903s
> > >     after       0.611s      1.889s
> > >     speedup     1.1%        0.7%
> > >
> > > Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
> > > ---
> > >
> > > Changes since v1:
> > >
> > >  - don't need to touch diff.h, as the function we are changing became static.
> > >
> > >  tree-diff.c | 36 ++++++++++++++++++------------------
> > >  1 file changed, 18 insertions(+), 18 deletions(-)
> > >
> > > diff --git a/tree-diff.c b/tree-diff.c
> > > index aea0297..c76821d 100644
> > > --- a/tree-diff.c
> > > +++ b/tree-diff.c
> > > @@ -115,7 +115,7 @@ static void show_path(struct strbuf *base, struct diff_options *opt,
> > >  	if (recurse) {
> > >  		strbuf_addch(base, '/');
> > >  		__diff_tree_sha1(t1 ? t1->entry.sha1 : NULL,
> > > -				 t2 ? t2->entry.sha1 : NULL, base->buf, opt);
> > > +				 t2 ? t2->entry.sha1 : NULL, base, opt);
> > >  	}
> > >  
> > >  	strbuf_setlen(base, old_baselen);
> > 
> > I was scratching my head for a while, after seeing that there does
> > not seem to be any *new* code added by this patch in order to
> > store-away the original length and restore the singleton base buffer
> > to the original length after using addch/addstr to extend it.
> > 
> > But I see that the code has already been prepared to do this
> > conversion.  I wonder why we didn't do this earlier ;-)
> 
> The conversion to reusing memory started in 48932677 "diff-tree: convert
> base+baselen to writable strbuf" which allowed to avoid "quite a bit of
> malloc() and memcpy()", but for this to work allocation at diff_tree()
> entry had to be there.
> 
> In particular it had to be there, because diff_tree() accepted base as C
> string, not strbuf, and since diff_tree() was calling itself
> recursively - oops - new allocation on every subtree.
> 
> I've opened the door for avoiding allocations via splitting diff_tree
> into high-level and low-level parts. The high-level part still accepts
> `char *base`, but low-level function operates on strbuf and recurses
> into low-level self.
> 
> The high-level diff_tree_sha1() still allocates memory for every
> diff(tree1,tree2), but that is significantly lower compared to
> allocating memory on every subtree...
> 
> The lesson here is: better use strbuf for api unless there is a reason
> not to.
> 
> 
> > Looks good.  Thanks.
> 
> Thanks.
Thanks again. Here it goes adjusted to __diff_tree_sha1 -> ll_diff_tree_sha1 renaming:
(please keep author email)
---- 8< ----
From: Kirill Smelkov <kirr@mns.spb.ru>
Date: Mon, 24 Feb 2014 20:21:48 +0400
Subject: [PATCH v3] tree-diff: reuse base str(buf) memory on sub-tree recursion

instead of allocating it all the time for every subtree in ll_diff_tree_sha1, let's allocate it once in diff_tree_sha1, and then all callee just use it in stacking style, without memory allocations.

This should be faster, and for me this change gives the following slight speedups for

    git log --raw --no-abbrev --no-renames --format='%H'
                navy.git    linux.git v3.10..v3.11
    before      0.618s      1.903s
    after       0.611s      1.889s
    speedup     1.1%        0.7%
Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
---
Changes since v2:
 - adjust to __diff_tree_sha1 -> ll_diff_tree_sha1 renaming.
Changes since v1:
 - don't need to touch diff.h, as the function we are changing became
   static.
 tree-diff.c | 38 +++++++++++++++++++-------------------
 1 file changed, 19 insertions(+), 19 deletions(-)
diff --git a/tree-diff.c b/tree-diff.c
index 7fbb022..8c8bde6 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -8,7 +8,7 @@
 
 
 static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
-			     const char *base_str, struct diff_options *opt);
+			     struct strbuf *base, struct diff_options *opt);
 
 /*
  * Compare two tree entries, taking into account only path/S_ISDIR(mode),
@@ -123,7 +123,7 @@ static void show_path(struct strbuf *base, struct diff_options *opt,
 	if (recurse) {
 		strbuf_addch(base, '/');
 		ll_diff_tree_sha1(t1 ? t1->entry.sha1 : NULL,
-				  t2 ? t2->entry.sha1 : NULL, base->buf, opt);
+				  t2 ? t2->entry.sha1 : NULL, base, opt);
 	}
 
 	strbuf_setlen(base, old_baselen);
@@ -146,12 +146,10 @@ static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
 }
 
 static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
-			     const char *base_str, struct diff_options *opt)
+			     struct strbuf *base, struct diff_options *opt)
 {
 	struct tree_desc t1, t2;
 	void *t1tree, *t2tree;
-	struct strbuf base;
-	int baselen = strlen(base_str);
 
 	t1tree = fill_tree_descriptor(&t1, old);
 	t2tree = fill_tree_descriptor(&t2, new);
@@ -159,17 +157,14 @@ static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
 	/* Enable recursion indefinitely */
 	opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
 
-	strbuf_init(&base, PATH_MAX);
-	strbuf_add(&base, base_str, baselen);
-
 	for (;;) {
 		int cmp;
 
 		if (diff_can_quit_early(opt))
 			break;
 		if (opt->pathspec.nr) {
-			skip_uninteresting(&t1, &base, opt);
-			skip_uninteresting(&t2, &base, opt);
+			skip_uninteresting(&t1, base, opt);
+			skip_uninteresting(&t2, base, opt);
 		}
 		if (!t1.size && !t2.size)
 			break;
@@ -181,7 +176,7 @@ static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
 			if (DIFF_OPT_TST(opt, FIND_COPIES_HARDER) ||
 			    hashcmp(t1.entry.sha1, t2.entry.sha1) ||
 			    (t1.entry.mode != t2.entry.mode))
-				show_path(&base, opt, &t1, &t2);
+				show_path(base, opt, &t1, &t2);
 
 			update_tree_entry(&t1);
 			update_tree_entry(&t2);
@@ -189,18 +184,17 @@ static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
 
 		/* t1 < t2 */
 		else if (cmp < 0) {
-			show_path(&base, opt, &t1, /*t2=*/NULL);
+			show_path(base, opt, &t1, /*t2=*/NULL);
 			update_tree_entry(&t1);
 		}
 
 		/* t1 > t2 */
 		else {
-			show_path(&base, opt, /*t1=*/NULL, &t2);
+			show_path(base, opt, /*t1=*/NULL, &t2);
 			update_tree_entry(&t2);
 		}
 	}
 
-	strbuf_release(&base);
 	free(t2tree);
 	free(t1tree);
 	return 0;
@@ -217,7 +211,7 @@ static inline int diff_might_be_rename(void)
 		!DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);
 }
 
-static void try_to_follow_renames(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
+static void try_to_follow_renames(const unsigned char *old, const unsigned char *new, struct strbuf *base, struct diff_options *opt)
 {
 	struct diff_options diff_opts;
 	struct diff_queue_struct *q = &diff_queued_diff;
@@ -314,13 +308,19 @@ static void try_to_follow_renames(const unsigned char *old, const unsigned char
 	q->nr = 1;
 }
 
-int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
+int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base_str, struct diff_options *opt)
 {
+	struct strbuf base;
 	int retval;
 
-	retval = ll_diff_tree_sha1(old, new, base, opt);
-	if (!*base && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename())
-		try_to_follow_renames(old, new, base, opt);
+	strbuf_init(&base, PATH_MAX);
+	strbuf_addstr(&base, base_str);
+
+	retval = ll_diff_tree_sha1(old, new, &base, opt);
+	if (!*base_str && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename())
+		try_to_follow_renames(old, new, &base, opt);
+
+	strbuf_release(&base);
 
 	return retval;
 }

-- 
1.9.rc0.143.g6fd479e
Previous: Kirill SmelkovNext: Kirill Smelkov
Message 42 of 64 in “Multiparent diff tree-walker + combine-diff speedup”
  1. 00/19 Multiparent diff tree-walker + combine-diff speedupKirill Smelkov, Feb 24, 2014
  2. 01/19 combine-diff: move show_log_first logic/action out of paths scanningKirill Smelkov, Feb 24, 2014
  3. 02/19 combine-diff: move changed-paths scanning logic into its own functionKirill Smelkov, Feb 24, 2014
  4. 03/19 tree-diff: no need to manually verify that there is no mode change for a pathKirill Smelkov, Feb 24, 2014
  5. 04/19 tree-diff: no need to pass match to skip_uninteresting()Kirill Smelkov, Feb 24, 2014
  6. 05/19 tree-diff: show_tree() is not neededKirill Smelkov, Feb 24, 2014
  7. 06/19 tree-diff: consolidate code for emitting diffs and recursion in one placeKirill Smelkov, Feb 24, 2014
  8. 07/19 tree-diff: don't assume compare_tree_entry() returns -1,0,1Kirill Smelkov, Feb 24, 2014
  9. 08/19 tree-diff: move all action-taking code out of compare_tree_entry()Kirill Smelkov, Feb 24, 2014
  10. 09/19 tree-diff: rename compare_tree_entry -> tree_entry_pathcmpKirill Smelkov, Feb 24, 2014
  11. 10/19 tree-diff: show_path prototype is not needed anymoreKirill Smelkov, Feb 24, 2014
  12. 11/19 tree-diff: simplify tree_entry_pathcmpKirill Smelkov, Feb 24, 2014
  13. Junio C HamanoMar 24, 2014
  14. Kirill SmelkovMar 25, 2014
  15. 12/19 tree-diff: remove special-case diff-emitting code for empty-tree casesKirill Smelkov, Feb 24, 2014
  16. Junio C HamanoMar 24, 2014
  17. Kirill SmelkovMar 25, 2014
  18. Junio C HamanoMar 25, 2014
  19. Junio C HamanoMar 25, 2014
  20. Kirill SmelkovMar 26, 2014
  21. 13/19 tree-diff: diff_tree() should now be staticKirill Smelkov, Feb 24, 2014
  22. 14/19 tree-diff: rework diff_tree interface to be sha1 basedKirill Smelkov, Feb 24, 2014
  23. Junio C HamanoMar 24, 2014
  24. Kirill SmelkovMar 25, 2014
  25. Junio C HamanoMar 25, 2014
  26. Kirill SmelkovMar 26, 2014
  27. Junio C HamanoMar 26, 2014
  28. Kirill SmelkovMar 27, 2014
  29. Junio C HamanoMar 27, 2014
  30. Kirill SmelkovMar 27, 2014
  31. Johannes SixtMar 28, 2014
  32. Junio C HamanoMar 28, 2014
  33. Johannes SixtMar 28, 2014
  34. Junio C HamanoMar 28, 2014
  35. Johannes SixtMar 28, 2014
  36. Junio C HamanoMar 28, 2014
  37. 15/19 tree-diff: no need to call "full" diff_tree_sha1 from show_path()Kirill Smelkov, Feb 24, 2014
  38. Kirill SmelkovMar 27, 2014
  39. 16/19 tree-diff: reuse base str(buf) memory on sub-tree recursionKirill Smelkov, Feb 24, 2014
  40. Junio C HamanoMar 24, 2014
  41. Kirill SmelkovMar 25, 2014
  42. Kirill SmelkovMar 27, 2014
  43. 17/19 Portable alloca for GitKirill Smelkov, Feb 24, 2014
  44. Thomas SchwingeFeb 28, 2014
  45. Erik Faye-LundFeb 28, 2014
  46. Erik Faye-LundFeb 28, 2014
  47. Kirill SmelkovFeb 28, 2014
  48. Erik Faye-LundFeb 28, 2014
  49. Kirill SmelkovMar 5, 2014
  50. Junio C HamanoMar 24, 2014
  51. Kirill SmelkovMar 27, 2014
  52. Kirill SmelkovApr 9, 2014
  53. Erik Faye-LundApr 9, 2014
  54. Junio C HamanoApr 10, 2014
  55. 18/19 tree-diff: rework diff_tree() to generate diffs for multiparent cases as wellKirill Smelkov, Feb 24, 2014
  56. Kirill SmelkovMar 27, 2014
  57. Junio C HamanoApr 4, 2014
  58. Kirill SmelkovApr 6, 2014
  59. Junio C HamanoApr 7, 2014
  60. Junio C HamanoApr 7, 2014
  61. Kirill SmelkovApr 7, 2014
  62. 19/19 combine-diff: speed it up, by using multiparent diff tree-walker directlyKirill Smelkov, Feb 24, 2014
  63. Duy NguyenFeb 24, 2014
  64. Kirill SmelkovFeb 25, 2014

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.