[PATCH v6 0/7] speed up index load through parallelization

[Ben Peart <peartben@gmail.com>]

Base Ref: master
Web-Diff: https://github.com/benpeart/git/commit/a0300882d4
Checkout: git fetch https://github.com/benpeart/git read-index-multithread-v6 && git checkout a0300882d4


This iteration brings back the Index Entry Offset Table (IEOT) extension
which enables us to multi-thread the cache entry parsing without having
the primary thread have to scan all the entries first.  In cases where the
cache entry parsing is the most expensive part, this yields some additional
savings.

Using p0002-read-cache.sh to generate some performance numbers shows how
each of the various patches contribute to the overall performance win.


Test w/100,000 files    Baseline  Optimize V4    Extensions     Entries
----------------------------------------------------------------------------
0002.1: read_cache      22.36     18.74 -16.2%   18.64 -16.6%   12.63 -43.5%

Test w/1,000,000 files  Baseline  Optimize V4    Extensions     Entries
-----------------------------------------------------------------------------
0002.1: read_cache      304.40    270.70 -11.1%  195.50 -35.8%  204.82 -32.7%

Note that on the 1,000,000 files case, multi-threading the cache entry parsing
does not yield a performance win.  This is because the cost to parse the
index extensions in this repo, far outweigh the cost of loading the cache
entries.

Name                            First    Last	  Elapsed	
load_index_extensions()		629.001  870.244  241.243	
load_cache_entries_thread()	683.911  723.199  39.288	
load_cache_entries_thread()	686.206  723.512  37.306	
load_cache_entries_thread()	686.43   722.596  36.166	
load_cache_entries_thread()	684.998  718.74   33.742	
load_cache_entries_thread()	685.035  718.698  33.663	
load_cache_entries_thread()	686.557  709.545  22.988	
load_cache_entries_thread()	684.533  703.536  19.003	
load_cache_entries_thread()	684.537  703.521  18.984	
load_cache_entries_thread()	685.062  703.774  18.712	
load_cache_entries_thread()	685.42   703.416  17.996	
load_cache_entries_thread()	648.604  664.496  15.892	
				
293.74 Total load_cache_entries_thread()

The high cost of parsing the index extensions is driven by the cache tree
and the untracked cache extensions. As this is currently the longest pole,
any reduction in this time will reduce the overall index load times so is
worth further investigation in another patch series.

Name                                    First    Last     Elapsed
|   + git!read_index_extension     	684.052  870.244  186.192
|    + git!cache_tree_read         	684.052  797.801  113.749
|    + git!read_untracked_extension	797.801  870.244  72.443

One option would be to load each extension on a separate thread but I
believe that is overkill for the vast majority of repos.  Instead, some
optimization of the loading code for these two extensions is probably worth
looking into as a quick examination shows that the bulk of the time for both
of them is spent in xcalloc().


### Patches

Ben Peart (6):
  read-cache: clean up casting and byte decoding
  eoie: add End of Index Entry (EOIE) extension
  config: add new index.threads config setting
  read-cache: load cache extensions on a worker thread
  ieot: add Index Entry Offset Table (IEOT) extension
  read-cache: load cache entries on worker threads

Nguyễn Thái Ngọc Duy (1):
  read-cache.c: optimize reading index format v4

 Documentation/config.txt                 |   7 +
 Documentation/technical/index-format.txt |  41 ++
 config.c                                 |  18 +
 config.h                                 |   1 +
 read-cache.c                             | 741 +++++++++++++++++++----
 t/README                                 |  10 +
 t/t1700-split-index.sh                   |   2 +
 7 files changed, 705 insertions(+), 115 deletions(-)


base-commit: fe8321ec057f9231c26c29b364721568e58040f7
-- 
2.18.0.windows.1