lookup_object: prioritize recently found objects

The lookup_object function is backed by a hash table of all
objects we have seen in the program. We manage collisions
with a linear walk over the colliding entries, checking each
with hashcmp(). The main cost of lookup is in these
hashcmp() calls; finding our item in the first slot is
cheaper than finding it in the second slot, which is cheaper
than the third, and so on.

If we assume that there is some locality to the object
lookups (e.g., if X and Y collide, and we have just looked
up X, the next lookup is more likely to be for X than for
Y), then we can improve our average lookup speed by checking
X before Y.

This patch does so by swapping a found item to the front of
the collision chain. The p0001 perf test reveals that this
does indeed exploit locality in the case of "rev-list --all
--objects":

Test                               origin          this tree
-------------------------------------------------------------------------
0001.1: rev-list --all             0.40(0.38+0.02) 0.40(0.36+0.03) +0.0%
0001.2: rev-list --all --objects   2.24(2.17+0.05) 1.86(1.79+0.05) -17.0%

This is not surprising, as the full object traversal will
hit the same tree entries over and over (e.g., for every
commit that doesn't change "Documentation/", we will have to
look up the same sha1 just to find out that we already
processed it).

The reason why this technique works (and does not violate
any properties of the hash table) is subtle and bears some
explanation. Let's imagine we get a lookup for sha1 `X`, and
it hashes to bucket `i` in our table. That stretch of the
table may look like:

index       | i-1 |  i  | i+1 | i+2 |
       -----------------------------------
entry   ... |  A  |  B  |  C  |  X  | ...
       -----------------------------------

We start our probe at i, see that B does not match, nor does
C, and finally find X. There may be multiple C's in the
middle, but we know that there are no empty slots (or else
we would not find X at all).

We do not know the original index of B; it may be `i`, or it
may be less than i (e.g., if it were `i-1`, it would collide
with A and spill over into the `i` bucket). So it is
acceptable for us to move it to the right of a contiguous
stretch of entries (because we will find it from a linear
walk starting anywhere at `i` or before), but never to the
left (if we moved it to `i-1`, we would miss it when
starting our walk at `i`).

We do know the original index of X; it is `i`, so it is safe
to place it anywhere in the contiguous stretch between `i`
and where we found it (`i+2` in the this case).

This patch does a pure swap; after finding X in the
situation above, we would end with:

index       | i-1 |  i  | i+1 | i+2 |
       -----------------------------------
entry   ... |  A  |  X  |  C  |  B  | ...
       -----------------------------------

We could instead bump X into the `i` slot, and then shift
the whole contiguous chain down by one, resulting in:

index       | i-1 |  i  | i+1 | i+2 |
       -----------------------------------
entry   ... |  A  |  X  |  B  |  C  | ...
       -----------------------------------

That puts our chain in true most-recently-used order.
However, experiments show that it is not any faster (and in
fact, is slightly slower due to the extra manipulation).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Add new @ shortcut for HEAD

Even though we often can do without having to type "HEAD", e.g. "git
log origin.." substitutes missing side of the range with "HEAD",
typing 'HEAD' is still sometimes necessary and tedious.

Make "@" usable as its synonym.  The reason for choosing '@' is that
it follows naturally from the ref@op syntax (e.g. HEAD@{u}), except
we have no ref, and no operation, and when we don't have those, it
makes sens to assume 'HEAD'.

With the change, we can use 'git show @~1', for example.

Until now '@' was a valid name, but it conflicts with this idea, so
make it invalid.  Probably very few people, if any, used this name.

Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'fc/transport-helper-error-reporting' into jch

Update transport helper to report errors and maintain ref hierarchy
used to keep track of remote helper state better.

* fc/transport-helper-error-reporting:
  t5801: "VAR=VAL shell_func args" is forbidden
  transport-helper: update remote helper namespace
  transport-helper: trivial code shuffle
  transport-helper: warn when refspec is not used
  transport-helper: clarify pushing without refspecs
  transport-helper: update refspec documentation
  transport-helper: clarify *:* refspec
  transport-helper: improve push messages
  transport-helper: mention helper name when it dies
  transport-helper: report errors properly

# Conflicts:
# 	t/t5801-remote-helpers.sh
Merge branch 'js/transport-helper-error-reporting-fix' into jch

Finishing touches to fc/transport-helper-error-reporting topic.

* js/transport-helper-error-reporting-fix:
  git-remote-testgit: build it to run under $SHELL_PATH
  git-remote-testgit: further remove some bashisms
  git-remote-testgit: avoid process substitution
Merge branch 'mh/fetch-into-shallow' into jch

* mh/fetch-into-shallow:
  t5500: add test for fetching with an unknown 'shallow'
  upload-pack: ignore 'shallow' lines with unknown obj-ids
Merge branch 'tr/line-log' into jch

* tr/line-log:
  git-log(1): remove --full-line-diff description
  line-log: fix documentation formatting
  log -L: improve comments in process_all_files()
  log -L: store the path instead of a diff_filespec
  log -L: test merge of parallel modify/rename
  t4211: pass -M to 'git log -M -L...' test
  log -L: fix overlapping input ranges
  log -L: check range set invariants when we look it up
  Speed up log -L... -M
  log -L: :pattern:file syntax to find by funcname
  Implement line-history search (git log -L)
  Export rewrite_parents() for 'log -L'
  Refactor parse_loc

# Conflicts:
# 	Documentation/git-log.txt
# 	log-tree.c
Merge branch 'jc/prune-all' into jch

We used the approxidate() parser for "--expire=<timestamp>" options
of various commands, but it is better to treat --expire=all and
--expire=now a bit more specially than using the current timestamp.
Update "git gc" and "git reflog" with a new parsing function for
expiry dates.

* jc/prune-all:
  prune: introduce OPT_EXPIRY_DATE() and use it
  api-parse-options.txt: document "no-" for non-boolean options
  git-gc.txt, git-reflog.txt: document new expiry options
  date.c: add parse_expiry_date()
Merge branch 'jl/submodule-mv' into jch

"git mv A B" when moving a submodule A does "the right thing",
inclusing relocating its working tree and adjusting the paths in
the .gitmodules file.

* jl/submodule-mv:
  submodule.c: duplicate real_path's return value
  rm: delete .gitmodules entry of submodules removed from the work tree
  Teach mv to update the path entry in .gitmodules for moved submodules
  Teach mv to move submodules using a gitfile
  Teach mv to move submodules together with their work trees
Merge branch 'jk/submodule-subdirectory-ok' into jch

Allow various subcommands of "git submodule" to be run not from the
top of the working tree of the superproject.

* jk/submodule-subdirectory-ok:
  submodule: fix quoting in relative_path()
  submodule: drop the top-level requirement
  rev-parse: add --prefix option
Merge branch 'jh/checkout-auto-tracking' into jch

Updates "git checkout foo" that DWIMs the intended "upstream" and
turns it into "git checkout -t -b foo remotes/origin/foo" to
correctly take existing remote definitions into account.  The
remote "origin" may be what uniquely map its own branch to
remotes/some/where/foo but that some/where may not be "origin".

* jh/checkout-auto-tracking:
  glossary: Update and rephrase the definition of a remote-tracking branch
  branch.c: Validate tracking branches with refspecs instead of refs/remotes/*
  t9114.2: Don't use --track option against "svn-remote"-tracking branches
  t7201.24: Add refspec to keep --track working
  t3200.39: tracking setup should fail if there is no matching refspec.
  checkout: Use remote refspecs when DWIMming tracking branches
  t2024: Show failure to use refspec when DWIMming remote branch names
  t2024: Add tests verifying current DWIM behavior of 'git checkout <branch>'
Merge branch 'as/check-ignore' into jch

Enhance "check-ignore" (1.8.2 update) to work more like "check-attr"
over bidi-pipes.

* as/check-ignore:
  t0008: use named pipe (FIFO) to test check-ignore streaming
  Documentation: add caveats about I/O buffering for check-{attr,ignore}
  check-ignore: allow incremental streaming of queries via --stdin
  check-ignore: move setup into cmd_check_ignore()
  check-ignore: add -n / --non-matching option
  t0008: remove duplicated test fixture data

# Conflicts:
# 	builtin/check-ignore.c
Merge branch 'mh/packed-refs-various' into jch

Updates reading and updating packed-refs file, correcting corner
case bugs.

* mh/packed-refs-various: (33 commits)
  refs: handle the main ref_cache specially
  refs: change do_for_each_*() functions to take ref_cache arguments
  pack_one_ref(): do some cheap tests before a more expensive one
  pack_one_ref(): use write_packed_entry() to do the writing
  pack_one_ref(): use function peel_entry()
  refs: inline function do_not_prune()
  pack_refs(): change to use do_for_each_entry()
  refs: use same lock_file object for both ref-packing functions
  pack_one_ref(): rename "path" parameter to "refname"
  pack-refs: merge code from pack-refs.{c,h} into refs.{c,h}
  pack-refs: rename handle_one_ref() to pack_one_ref()
  refs: extract a function write_packed_entry()
  repack_without_ref(): write peeled refs in the rewritten file
  t3211: demonstrate loss of peeled refs if a packed ref is deleted
  refs: change how packed refs are deleted
  search_ref_dir(): return an index rather than a pointer
  repack_without_ref(): silence errors for dangling packed refs
  t3210: test for spurious error messages for dangling packed refs
  refs: change the internal reference-iteration API
  refs: extract a function peel_entry()
  ...
Merge branch 'rj/sparse' into jch

* rj/sparse:
  sparse: Fix mingw_main() argument number/type errors
  compat/mingw.c: Fix some sparse warnings
  compat/win32mmap.c: Fix some sparse warnings
  compat/poll/poll.c: Fix a sparse warning
  compat/win32/pthread.c: Fix a sparse warning
  compat/unsetenv.c: Fix a sparse warning
  compat/nedmalloc: Fix compiler warnings on linux
  compat/nedmalloc: Fix some sparse warnings
  compat/fnmatch/fnmatch.c: Fix a sparse error
  compat/regex/regexec.c: Fix some sparse warnings
Merge branch 'jk/test-output' into jch

When TEST_OUTPUT_DIRECTORY setting is used, it was handled somewhat
inconsistently between the test framework and t/Makefile, and logic
to summarize the results looked at a wrong place.

* jk/test-output:
  test output: respect $TEST_OUTPUT_DIRECTORY
  t/Makefile: fix result handling with TEST_OUTPUT_DIRECTORY
### match next
Merge branch 'fc/completion' into jch

I saw this discussed somewhat. Is everybody happy with this
version?  This is its v2, in the $gmane/222682 thread.

* fc/completion:
  completion: remove __git_index_file_list_filter()
  completion: add space after completed filename
  completion: add hack to enable file mode in bash < 4
  completion: refactor __git_complete_index_file()
  completion: refactor diff_index wrappers
  completion: use __gitcompadd for __gitcomp_file
  completion; remove unuseful comments
  completion: document tilde expansion failure in tests
  completion: add file completion tests
Merge branch 'rj/mingw-cygwin' into jch

Cygwin portability; both were reviewed by Jonathan, and the tip one
seems to want a bit further explanation.  Needs positive report
from Cygwin 1.7 users who have been on 1.7 to make sure it does not
regress for them.

* rj/mingw-cygwin:
  cygwin: Remove the CYGWIN_V15_WIN32API build variable
  mingw: rename WIN32 cpp macro to GIT_WINDOWS_NATIVE
Merge branch 'fc/remote-bzr' into jch

* fc/remote-bzr:
  remote-bzr: access branches only when needed
  remote-bzr: delay peer branch usage
  remote-bzr: iterate revisions properly
  remote-bzr: improve progress reporting
  remote-bzr: add option to specify branches
  remote-bzr: add custom method to find branches
  remote-bzr: improve author sanitazion
  remote-bzr: add support for shared repo
  remote-bzr: fix branch names
  remote-bzr: add support for bzr repos
  remote-bzr: use branch variable when appropriate
  remote-bzr: fix partially pushed merge
  remote-bzr: fixes for branch diverge
  remote-bzr: add support to push merges
  remote-bzr: always try to update the worktree
  remote-bzr: fix order of locking in CustomTree
  remote-bzr: delay blob fetching until the very end
  remote-bzr: cleanup CustomTree
Merge branch 'jk/lookup-object-prefer-latest' into jch

* jk/lookup-object-prefer-latest:
  lookup_object: prioritize recently found objects
Merge branch 'jk/subtree-do-not-push-if-split-fails' into jch

* jk/subtree-do-not-push-if-split-fails:
  contrib/subtree: don't delete remote branches if split fails