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

[PATCH 0/3] Clean up and optimize tree walking some more

From
Linus Torvalds <torvalds@linux-foundation.org>
Date
Mar 21, 2007, 17:07 UTC
Message-ID
<Pine.LNX.4.64.0703210955370.6730@woody.linux-foundation.org>

This series of three patches improves blame performance on the eclipse tree by about 15% in my tests by improving the tree walk a bit.

  [ Before-best-of-five: 11.649s
    After-best-of-five:   9.675s ]

The first two patches are just boring cleanups: the first removes an unnecessary field from the "name_entry" structure, because I wanted to embed it into the "tree_desc" one and it was just totally redundant and I felt bad about growing tree_desc more than necessary. No real code changes, just replacing the use of "pathlen" with the helper function we introduced ealier ("tree_entry_len()").

The second one just makes sure that we always initialize the tree_desc structure with a helper function rather than doing it by hand. Again, this doesn't actually change any code, although I changed the name of the "buf" entry to "buffer", and the type of "size", so that we get nice compiler warnings if they are used the old way by mistake.

The second patch is the largest of the lot, but really doesn't do anything interesting, just preparatory cleanup.

The third patch is the one that actually changes any code, and is fairly straightforward: it just switches around where we actually do the tree entry parsing, which is now possible thanks to patch #2. By doing it up-front, we only need to do it once (we used to have to do it both when doing the "extract" *and* when doing the "update" op - now we do it only once per entry, and "extract" is just about looking at the cached contents).

The resulting diffstat of the tree patches ends up removing a few more lines than it adds (not by a lot), but perhaps more importantly (even more than the performance advantage) the code looks nicer, I think.

 builtin-fsck.c         |    5 +-
 builtin-grep.c         |   13 +++--
 builtin-pack-objects.c |    8 +--
 builtin-read-tree.c    |    3 +-
 builtin-reflog.c       |   10 ++--
 fetch.c                |    3 +-
 http-push.c            |    3 +-
 list-objects.c         |    3 +-
 merge-tree.c           |    9 ++--
 reachable.c            |    3 +-
 revision.c             |   12 ++---
 tree-diff.c            |   22 +++++----
 tree-walk.c            |  123 ++++++++++++++++++++++--------------------------
 tree-walk.h            |   20 ++++++--
 tree.c                 |   18 +++----
 unpack-trees.c         |    3 +-
 16 files changed, 125 insertions(+), 133 deletions(-)

I'm pretty sure this is all good, and it obviously passes all the tests, but more importantly none of the changes were really very complicated, and patch#2 (which is the big one) was set up so that the compiler would not even compile code that wasn't properly converted, so it should all be good.

			Linus
Next: Linus Torvalds
Message 1 of 5 in “Clean up and optimize tree walking some more”
  1. 0/3 Clean up and optimize tree walking some moreLinus Torvalds, Mar 21, 2007
  2. 1/3 Remove "pathlen" from "struct name_entry"Linus Torvalds, Mar 21, 2007
  3. 2/3 Initialize tree descriptors with a helper function rather than by hand.Linus Torvalds, Mar 21, 2007
  4. 3/3 Switch over tree descriptors to contain a pre-parsed entryLinus Torvalds, Mar 21, 2007
  5. Resend: [PATCH 0/3] Clean up and optimize tree walking some moreLinus Torvalds, Mar 21, 2007

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.