From: Junio C Hamano <gitster@pobox•com>
To: Jeff King <peff@peff•net>
Cc: git@vger•kernel.org, Michael Haggerty <mhagger@alum•mit.edu>
Subject: Re: [PATCH v2 06/25] reachable: use traverse_commit_list instead of custom walk
Date: Thu, 16 Oct 2014 10:53:52 -0700 [thread overview]
Message-ID: <xmqqmw8vuci7.fsf@gitster.dls.corp.google.com> (raw)
In-Reply-To: <20141015223728.GF25630@peff.net> (Jeff King's message of "Wed, 15 Oct 2014 18:37:28 -0400")
Jeff King <peff@peff•net> writes:
> To find the set of reachable objects, we add a bunch of
> possible sources to our rev_info, call prepare_revision_walk,
> and then launch into a custom walker that handles each
> object top. This is a subset of what traverse_commit_list
> does, so we can just reuse that code (it can also handle
> more complex cases like UNINTERESTING commits and pathspecs,
> but we don't use those features).
>
> Signed-off-by: Jeff King <peff@peff•net>
> ---
> I was concerned this would be slower because traverse_commit_list is
> more featureful. To my surprise, it was consistently about 3-4% faster!
> The major difference is that traverse_commit_list will hit all of the
> commits first, and then the trees. For reachability that doesn't matter
> either way, but I suspect the new way has slightly better cache
> locality, leading to the minor speedup.
I am not very surprised, as "custom walk" hasn't changed much ever
since it was done in ba84a797 (builtin "git prune", 2006-07-06),
while the generic traversal code has been worked heavily while it
was still in builtin-rev-list.c and then later moved to
list-objects.c.
> reachable.c | 130 ++++++++----------------------------------------------------
> 1 file changed, 17 insertions(+), 113 deletions(-)
;-) ;-) ;-) ;-) ;-)
next prev parent reply other threads:[~2014-10-16 17:53 UTC|newest]
Thread overview: 48+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-10-15 22:32 [PATCH v2 0/25] prune-safety Jeff King
2014-10-15 22:33 ` [PATCH v2 01/25] foreach_alt_odb: propagate return value from callback Jeff King
2014-10-15 22:34 ` [PATCH v2 02/25] isxdigit: cast input to unsigned char Jeff King
2014-10-16 17:16 ` Junio C Hamano
2014-10-15 22:34 ` [PATCH v2 03/25] object_array: factor out slopbuf-freeing logic Jeff King
2014-10-16 17:39 ` Junio C Hamano
2014-10-17 0:33 ` git-bundle rev handling and de-duping Jeff King
2014-10-17 21:03 ` Philip Oakley
2014-10-17 22:41 ` Junio C Hamano
2014-10-15 22:34 ` [PATCH v2 04/25] object_array: add a "clear" function Jeff King
2014-10-15 22:35 ` [PATCH v2 05/25] clean up name allocation in prepare_revision_walk Jeff King
2014-10-15 22:37 ` [PATCH v2 06/25] reachable: use traverse_commit_list instead of custom walk Jeff King
2014-10-16 17:53 ` Junio C Hamano [this message]
2014-10-15 22:38 ` [PATCH v2 07/25] reachable: reuse revision.c "add all reflogs" code Jeff King
2014-10-15 22:38 ` [PATCH v2 08/25] prune: factor out loose-object directory traversal Jeff King
2014-10-15 22:40 ` [PATCH v2 09/25] reachable: mark index blobs as SEEN Jeff King
2014-10-15 22:40 ` [PATCH v2 10/25] prune-packed: use for_each_loose_file_in_objdir Jeff King
2014-10-15 22:40 ` [PATCH v2 11/25] count-objects: do not use xsize_t when counting object size Jeff King
2014-10-15 22:41 ` [PATCH v2 12/25] count-objects: use for_each_loose_file_in_objdir Jeff King
2014-10-15 22:41 ` [PATCH v2 13/25] sha1_file: add for_each iterators for loose and packed objects Jeff King
2014-10-15 22:41 ` [PATCH v2 14/25] prune: keep objects reachable from recent objects Jeff King
2014-10-15 22:41 ` [PATCH v2 15/25] pack-objects: refactor unpack-unreachable expiration check Jeff King
2014-10-15 22:42 ` [PATCH v2 16/25] pack-objects: match prune logic for discarding objects Jeff King
2014-10-15 22:42 ` [PATCH v2 17/25] write_sha1_file: freshen existing objects Jeff King
2014-10-15 22:42 ` [PATCH v2 18/25] make add_object_array_with_context interface more sane Jeff King
2014-10-15 22:43 ` [PATCH v2 19/25] traverse_commit_list: support pending blobs/trees with paths Jeff King
2014-10-15 22:43 ` [PATCH v2 20/25] rev-list: document --reflog option Jeff King
2014-10-15 22:44 ` [PATCH v2 21/25] rev-list: add --index-objects option Jeff King
2014-10-16 18:41 ` Junio C Hamano
2014-10-17 0:12 ` Jeff King
2014-10-17 0:43 ` Jeff King
2014-10-17 0:44 ` [PATCH v3 22/26] rev-list: add --indexed-objects option Jeff King
2014-10-17 0:44 ` [PATCH v3 23/26] reachable: use revision machinery's --indexed-objects code Jeff King
2014-10-17 0:44 ` [PATCH v3 24/26] pack-objects: use argv_array Jeff King
2014-10-17 0:44 ` [PATCH v3 25/26] repack: pack objects mentioned by the index Jeff King
2014-10-17 0:44 ` [PATCH v3 26/26] pack-objects: double-check options before discarding objects Jeff King
2014-10-15 22:44 ` [PATCH v2 22/25] reachable: use revision machinery's --index-objects code Jeff King
2014-10-15 22:45 ` [PATCH v2 23/25] pack-objects: use argv_array Jeff King
2014-10-15 22:46 ` [PATCH v2 24/25] repack: pack objects mentioned by the index Jeff King
2014-10-15 22:48 ` [PATCH v2 25/25] pack-objects: double-check options before discarding objects Jeff King
2014-10-16 21:07 ` [PATCH v2 0/25] prune-safety Junio C Hamano
2014-10-16 21:10 ` Junio C Hamano
2014-10-16 21:21 ` Jeff King
2014-10-16 21:39 ` Jeff King
2014-10-16 22:18 ` Junio C Hamano
2014-10-17 0:03 ` Jeff King
[not found] ` <CAPc5daX0AFv9jDrFyd_OnupW5AfZW9Je_rgzaViX_xxs3SG5zg@mail.gmail.com>
2014-10-17 4:49 ` Jeff King
2014-10-18 12:31 ` Jeff King
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=xmqqmw8vuci7.fsf@gitster.dls.corp.google.com \
--to=gitster@pobox$(echo .)com \
--cc=git@vger$(echo .)kernel.org \
--cc=mhagger@alum$(echo .)mit.edu \
--cc=peff@peff$(echo .)net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox