Allocate cache entries from memory pool

This patch series improves the performance of loading indexes by reducing the number of malloc() calls. Loading the index from disk is partly dominated by the time in malloc(), which is called for each index entry. This patch series reduces the number of times malloc() is called as part of loading the index, and instead allocates a block of memory upfront that is large enough to hold all of the cache entries, and chunks this memory itself. This change builds on [1], which is a prerequisite for this change.

Git previously allocated block of memory for the index cache entries until [2].

This 5 part patch series is broken up as follows:

1/5, 2/5 - Move cache entry lifecycle methods behind an API

3/5 - Fill out memory pool API to include lifecycle and other
methods used in later patches

4/5 - Allocate cache entry structs from memory pool

5/5 - Add extra optional validation

Performance Benchmarks:

To evaluate the performance of this approach, the p0002-read-cache.sh test was run with several combinations of allocators (glibc default, tcmalloc, jemalloc), with and without block allocation, and across several different index sized (100K, 1M, 2M entries). The details on how these repositories were constructed can be found in [3].The p0002-read-cache.sh was run with the iteration count set to 1 and $GIT_PERF_REPEAT_COUNT=10.

The tests were run with iteration count set to 1 because this best approximates the real behavior. The read_cache/discard_cache test will load / free the index N times, and the performance of this logic is different between N = 1 and N > 1. As the production code does not read / discard the index in a loop, a better approximation is when N = 1.

100K

Test baseline [4] block_allocation
------------------------------------------------------------------------------------
0002.1: read_cache/discard_cache 1 times 0.03(0.01+0.01) 0.02(0.01+0.01) -33.3%

1M:

Test baseline block_allocation
------------------------------------------------------------------------------------
0002.1: read_cache/discard_cache 1 times 0.23(0.12+0.11) 0.17(0.07+0.09) -26.1%

2M:

Test baseline block_allocation
------------------------------------------------------------------------------------
0002.1: read_cache/discard_cache 1 times 0.45(0.26+0.19) 0.39(0.17+0.20) -13.3%

100K is not a large enough sample size to show the perf impact of this change, but we can see a perf improvement with 1M and 2M entries. For completeness, here is the p0002-read-cache tests for git.git and linux.git:

git.git:

Test baseline block_allocation
---------------------------------------------------------------------------------------------
0002.1: read_cache/discard_cache 1000 times 0.30(0.26+0.03) 0.17(0.13+0.03) -43.3%

linux.git:

Test baseline block_allocation
---------------------------------------------------------------------------------------------
0002.1: read_cache/discard_cache 1000 times 7.05(6.01+0.84) 4.61(3.74+0.66) -34.6%

We also investigated the performance of just using different allocators. We can see that there is not a consistent performance gain.

100K

Test baseline [4] tcmalloc jemalloc
------------------------------------------------------------------------------------------------------------------
0002.1: read_cache/discard_cache 1 times 0.03(0.01+0.01) 0.03(0.01+0.01) +0.0% 0.03(0.02+0.01) +0.0%

1M:

Test baseline tcmalloc jemalloc
------------------------------------------------------------------------------------------------------------------
0002.1: read_cache/discard_cache 1 times 0.23(0.12+0.11) 0.21(0.10+0.10) -8.7% 0.27(0.16+0.10) +17.4%

2M:

Test baseline tcmalloc jemalloc
------------------------------------------------------------------------------------------------------------------
0002.1: read_cache/discard_cache 1 times 0.45(0.26+0.19) 0.46(0.25+0.21) +2.2% 0.57(0.36+0.21) +26.7%

[1] https://public-inbox.org/git/[email protected]/

[2] debed2a629 (read-cache.c: allocate index entries individually - 2011-10-24)

[3] Constructing test repositories:

The test repositories were constructed with t/perf/repos/many_files.sh with the following parameters:

100K: many-files.sh 4 10 9
1M: many-files.sh 5 10 9
2M: many-files.sh 6 8 7

[4] baseline commit: 8b026eda Revert "Merge branch 'en/rename-directory-detection'"

Jameson Miller (5):
read-cache: teach refresh_cache_entry to take istate Add an API creating / discarding cache_entry structs
mem-pool: fill out functionality
Allocate cache entries from memory pools
Add optional memory validations around cache_entry lifecyle

 apply.c                |  26 +++---
 blame.c                |   5 +-
 builtin/checkout.c     |   8 +-
 builtin/difftool.c     |   8 +-
 builtin/reset.c        |   6 +-
 builtin/update-index.c |  26 +++---
 cache.h                |  40 ++++++++-
 git.c                  |   3 +
 mem-pool.c             | 136 ++++++++++++++++++++++++++++-
 mem-pool.h             |  34 ++++++++
 merge-recursive.c      |   4 +-
 read-cache.c           | 229 +++++++++++++++++++++++++++++++++++++++----------
 resolve-undo.c         |   6 +-
 split-index.c          |  31 +++++--
 tree.c                 |   4 +-
 unpack-trees.c         |  27 +++---
 16 files changed, 476 insertions(+), 117 deletions(-)

base-commit: cafaccae98f749ebf33495aec42ea25060de8682

2.14.3