[PATCH v10 0/3] read-cache: speed up add_index_entry

From: Jeff Hostetler <jeffhost@microsoft.com>

Version 10 addresses mailing list comments on coding style in read-cache.c and in p0006. I've also adjusted the speed-up algorithm and more thoroughly documented the cases in the code.

We skip the binary searches whenever we can prove that the new entry (and every sub-directory prefix of the entry) clearly FOLLOWS the last entry in the index. Otherwise, we fall through to the existing search algorithm -- which handles stages and CE_REMOVE entries.

Jeff Hostetler (3):
  read-cache: add strcmp_offset function
  p0006-read-tree-checkout: perf test to time read-tree
  read-cache: speed up add_index_entry during checkout

 Makefile                           |   1 +
 cache.h                            |   1 +
 read-cache.c                       | 138 ++++++++++++++++++++++++++++++++++++-
 t/helper/.gitignore                |   1 +
 t/helper/test-strcmp-offset.c      |  22 ++++++
 t/perf/p0006-read-tree-checkout.sh |  67 ++++++++++++++++++
 t/perf/repos/.gitignore            |   1 +
 t/perf/repos/many-files.sh         | 110 +++++++++++++++++++++++++++++
 t/t0065-strcmp-offset.sh           |  21 ++++++
 9 files changed, 360 insertions(+), 2 deletions(-)
 create mode 100644 t/helper/test-strcmp-offset.c
 create mode 100755 t/perf/p0006-read-tree-checkout.sh
 create mode 100644 t/perf/repos/.gitignore
 create mode 100755 t/perf/repos/many-files.sh
 create mode 100755 t/t0065-strcmp-offset.sh