Subject: [BAD PATCH 0/9] v4-aware tree walker API

From: Nguyễn Thái Ngọc Duy <[email-masked]>
Date: Wed, 9 Oct 2013 21:46:07 +0700

I know I still have a lot of holes to plug, but this was more
interesting because we could see some encouraging numbers.
Unfortunately the result is disappointing. Maybe I did it in a stupid
way and need to restart with a totally different way.

"rev-list --objects" on v2 takes 4 secs, v4 with current walker 11s
and the new walker 16s (worst!). perf's top functions with v2 are

 23,51%  git  libz.so.1.2.7       [.] inflate
 16,66%  git  git                 [.] lookup_object
 11,46%  git  libz.so.1.2.7       [.] inflate_fast
  6,89%  git  libc-2.16.so        [.] __memcpy_ssse3_back
  4,19%  git  libz.so.1.2.7       [.] inflate_table
  4,15%  git  git                 [.] find_pack_entry_one
  3,84%  git  git                 [.] decode_tree_entry

and with new walker

 58,61%  git  git                [.] decode_entries
 18,66%  git  git                [.] decode_varint
  9,73%  git  git                [.] use_pack
  3,31%  git  git                [.] nth_packed_object_offset
  1,73%  git  git                [.] process_tree
  1,66%  git  git                [.] pv4_lookup_blob
  1,09%  git  git                [.] get_pathref
  1,03%  git  libc-2.16.so       [.] __memcpy_ssse3_back
  0,90%  git  libz.so.1.2.7      [.] inflate
  0,50%  git  libz.so.1.2.7      [.] inflate_table

It's no surprise that lookup_object is no longer hot. The closet is
pv4_lookup_blob. nth_packed_object_offset is getting hotter as it's
used extensively by decode_entries.

And decode_entries is getting toooo hot. This function is now called
for each tree entry of every tree. And it does get_tree_offset_cache()
lookup for every call (ironically we try hard to avoid hash lookup in
lookup_object).

The only bit I haven't done is avoid checking if a tree is already
examined, if so do not bother with copy sequences referring to it.
That should cut down the number of decode_entries but not sure how
much because there's no relation between tree traversing order and how
copy sequences are made.

Maybe we could make an exception and allow the tree walker to pass
pv4_tree_cache* directly to decode_entries so it does not need to do
the first lookup every time..

Suggestions?

Nguyễn Thái Ngọc Duy (9):
  sha1_file: provide real packed type in object_info_extended
  pack v4: move v2 tree entry generation code out of decode_entries
  pv4_tree_desc: introduce new struct for pack v4 tree walker
  pv4_tree_desc: use struct tree_desc from pv4_tree_desc
  pv4_tree_desc: allow decode_entries to return v4 trees, one at a time
  pv4_tree_desc: complete interface
  pv4_tree_desc: don't bother looking for v4 trees if no v4 packs are present
  pv4_tree_desc: avoid lookup_object() when possible
  list-object.c: take "advantage" of new pv4_tree_desc interface

 cache.h        |   3 +-
 list-objects.c |  38 +++++----
 packv4-parse.c | 263 ++++++++++++++++++++++++++++++++++++++++++++++-----------
 packv4-parse.h |  48 +++++++++++
 sha1_file.c    |   9 +-
 streaming.c    |   9 +-
 6 files changed, 300 insertions(+), 70 deletions(-)

-- 
1.8.2.83.gc99314b