thodg/got/lib

Diff

• Show log

  Commit

• Hash : 70f8f24d
  Author :
  Date : 2022-04-14T15:05:19
  

  speed up initial stage of packing by adding a "skip" commit color
  
  The skip color marks boundary commits and their ancestors. Boundary commits
  are reachable both via references which we want to exclude from the pack,
  and via references which we want to include in the pack.
  We continue processing commit history up to the point we are left with only
  skip commits on the queue.  This can speed up findtwixt() significantly and
  avoids wrong results produced by the old algorithm which made no distinction
  between "drop" and "skip".
  
  This idea was first implemented by Michael Forney for git9:
  https://git.9front.org/plan9front/plan9front/2e47badb88312c5c045a8042dc2ef80148e5ab47/commit.html
  Michael's log message for git9 is reproduced below:
  
  git/query: refactor graph painting algorithm (findtwixt, lca)
  
  We now keep track of 3 sets during traversal:
  - keep: commits we've reached from head commits
  - drop: commits we've reached from tail commits
  - skip: ancestors of commits in both 'keep' and 'drop'
  
  Commits in 'keep' and/or 'drop' may be added later to the 'skip' set
  if we discover later that they are part of a common subgraph of the
  head and tail commits.
  
  From these sets we can calculate the commits we are interested in:
  lca commits are those in 'keep' and 'drop', but not in 'skip'.
  findtwixt commits are those in 'keep', but not in 'drop' or 'skip'.
  
  The "LCA" commit returned is a common ancestor such that there are no
  other common ancestors that can reach that commit.  Although there can
  be multiple commits that meet this criteria, where one is technically
  lower on the commit-graph than the other, these cases only happen in
  complex merge arrangements and any choice is likely a decent merge
  base.
  
  Repainting is now done in paint() directly.  When we find a boundary
  commit, we switch our paint color to 'skip'.  'skip' painting does
  not stop when it hits another color; we continue until we are left
  with only 'skip' commits on the queue.
  
  This fixes several mishandled cases in the current algorithm:
  1. If we hit the common subgraph from tail commits first (if the tail
     commit was newer than the head commit), we ended up traversing the
     entire commit graph.  This is because we couldn't distinguish
     between 'drop' commits that were part of the common subgraph, and
     those that were still looking for it.
  2. If we traversed through an initial part of the common subgraph from
     head commits before reaching it from tail commits, these commits
     were returned from findtwixt even though they were also reachable
     from tail commits.
  3. In the same case as 2, we might end up choosing an incorrect
     commit as the LCA, which is an ancestor of the real LCA.
  

• Files

• Makefile
• arraylist.h
• blame.c
• bloom.c
• bloom.h
• buf.c
• buf.h
• commit_graph.c
• deflate.c
• delta.c
• delta_cache.c
• deltify.c
• dial.c
• diff.c
• diff3.c
• diff_atomize_text.c
• diff_debug.h
• diff_internal.h
• diff_main.c
• diff_main.h
• diff_myers.c
• diff_output.c
• diff_output.h
• diff_output_edscript.c
• diff_output_plain.c
• diff_output_unidiff.c
• diff_patience.c
• diffreg.c
• error.c
• fetch.c
• fileindex.c
• gitconfig.c
• gitproto.c
• got_lib_deflate.h
• got_lib_delta.h
• got_lib_delta_cache.h
• got_lib_deltify.h
• got_lib_dial.h
• got_lib_diff.h
• got_lib_fileindex.h
• got_lib_gitconfig.h
• got_lib_gitproto.h
• got_lib_gotconfig.h
• got_lib_inflate.h
• got_lib_lockfile.h
• got_lib_object.h
• got_lib_object_cache.h
• got_lib_object_create.h
• got_lib_object_idcache.h
• got_lib_object_idset.h
• got_lib_object_parse.h
• got_lib_pack.h
• got_lib_pack_create.h
• got_lib_pkt.h
• got_lib_privsep.h
• got_lib_ratelimit.h
• got_lib_repository.h
• got_lib_sha1.h
• got_lib_worktree.h
• gotconfig.c
• inflate.c
• lockfile.c
• murmurhash2.c
• murmurhash2.h
• object.c
• object_cache.c
• object_create.c
• object_idset.c
• object_parse.c
• opentemp.c
• pack.c
• pack_create.c
• patch.c
• path.c
• pkt.c
• privsep.c
• ratelimit.c
• rcsutil.c
• rcsutil.h
• reference.c
• repository.c
• repository_admin.c
• send.c
• sha1.c
• utf8.c
• worktree.c
• worktree_open.c

• Properties

• Git HTTP	https://git.kmx.io/thodg/got.git
  Git SSH	git@git.kmx.io:thodg/got.git
  Public access ?	public
  Description	https://gameoftrees.org/
  Users
  Tags	0.9 0.8 0.72 0.71 0.70 0.7 0.69 0.68 0.67 0.66 0.65 0.64 0.63 0.62 0.61 0.60 0.6 0.59 0.58 0.57 0.56 0.55 0.54 0.53 0.52 0.51 0.50 0.5 0.49 0.48 0.47 0.46 0.45 0.44 0.43 0.42 0.41 0.40 0.4 0.39 0.38 0.37 0.36 0.35 0.34 0.33 0.32 0.31 0.30 0.3 0.29 0.28 0.27 0.26 0.25 0.24 0.23 0.22 0.21 0.20 0.2 0.19 0.18 0.17 0.16 0.15 0.14 0.13 0.12 0.11 0.10 0.1