[PATCH v1 0/4] Speed up index load through parallelization

[PATCH v1 0/4] Speed up index load through parallelization

[Ben Peart]

This patch will help address the CPU cost of loading the index by adding
a table of contents extension to the index that will allow us to
multi-thread the loading and conversion of cache entries from the on-disk
format, to the in-memory format.  This is particularly beneficial
with large indexes and V4 indexes which have more CPU cost due to the
prefix-encoding.

I wanted to get feedback on the concept as the way I'm adding the table
of contents information via an extension that can be read before the
variable length section of cache entries and other extensions is a bit
of a clever hack (see below) as is the resetting of the prefix encoding
for V4 indexes. Both, however, are entirely backwards compatible with
older versions of git which can still properly read and use the index.

I'm not particularly fond of the names "fastindex" and "IEOT." I've
wondered if "indextoc" and "Index Table of Contents (ITOC)" would be
better names but I'm open to suggestions.

As there is overhead to spinning up a thread, there is logic to only
do the index loading in parallel when there are enough entries for it
to help (currently set at 7,500 per thread with a minimum of 2 threads).

The impact of the change can be seen using t/helper/test-read-cache:

                                fastindex
test            count   files   TRUE    FALSE     Savings
------------------------------------------------------------------------
test-read-cache 500     100K    6.39	8.33      23.36%
test-read-cache 100     1M      12.49   18.68     33.12%

The on-disk format looks like this:

Index header
Cache entry 1
Cache entry 2
.
.
.
Extension 1
Extension 2
.
.
Index Entry Offset Table Extension (must be written last!)
IEOT signature bytes
32-bit size
32-bit version
32-bit Cache Entry Offset 1
32-bit Cache Entry count
32-bit Cache Entry Offset 2
32-bit Cache Entry count
.
.
.
32-bit version
32-bit size
IEOT signature bytes
SHA1

Signed-off-by: Ben Peart <benpeart@microsoft.com>

Base Ref: master
Web-Diff: https://github.com/benpeart/git/commit/1146d38932
Checkout: git fetch https://github.com/benpeart/git fastindex-v1 && git checkout 1146d38932

Ben Peart (4):
  fastindex: speed up index load through parallelization
  update-index: add fastindex support to update-index
  fastindex: add test tools and a test script
  fastindex: add documentation for the fastindex extension

 Documentation/config.txt                 |   8 +
 Documentation/git-update-index.txt       |  11 +
 Documentation/technical/index-format.txt |  26 +++
 Makefile                                 |   2 +
 builtin/update-index.c                   |  22 ++
 cache.h                                  |  25 +++
 config.c                                 |  20 ++
 config.h                                 |   1 +
 environment.c                            |   3 +
 read-cache.c                             | 343 +++++++++++++++++++++++++++++--
 t/helper/test-dump-fast-index.c          |  68 ++++++
 t/helper/test-fast-index.c               |  84 ++++++++
 t/t1800-fast-index.sh                    |  55 +++++
 13 files changed, 647 insertions(+), 21 deletions(-)
 create mode 100644 t/helper/test-dump-fast-index.c
 create mode 100644 t/helper/test-fast-index.c
 create mode 100644 t/t1800-fast-index.sh


base-commit: 7668cbc60578f99a4c048f8f8f38787930b8147b
-- 
2.15.0.windows.1

[PATCH v1 1/4] fastindex: speed up index load through parallelization

[Ben Peart]

This patch helps address the CPU cost of loading the index by adding
additional data to the index that will allow us to multi-thread the
loading and conversion of cache entries.

It accomplishes this by adding an (optional) index extension that is a
table of offsets to blocks of cache entries in the index file.  With
version 2, 3 or even 4 indexes, we can utilize the Index Entry Offset Table
(IEOT) to parallelize the loading and conversion of the cache entries
across all available CPU cores.

To make this work for V4 indexes, when writing the index, it periodically
"resets" the prefix-compression by encoding the current entry as if the
path name for the previous entry is completely different and saves the
offset of that entry in the IEOT.  Basically, with V4 indexes, it
generates offsets into blocks of prefix-compressed entries.

To enable reading the IEOT extension before reading all the variable
length cache entries and other extensions, the IEOT is written last,
right before the trailing SHA1.

The format of that extension has the signature bytes and size at the
beginning (like a normal extension) as well as at the end in reverse
order to enable parsing the extension by seeking back from the end of
the file.

During index load, read the index header then seek to the end of the
index, back up past the trailing SHA1 and look for the IEOT extension
signature bytes.  If they exist, read the 32-bit size and seek back to
the extension header and verify the leading header and size bits.  If
they all match, we can be assured we have a valid IEOT extension.

If the IEOT extension is available, create multiple threads to divide
the work of loading and converting the cache entries across all
available CPU cores.  Once the cache entries are loaded, the rest of the
extensions can be loaded and processed normally (skipping the IEOT entry
as it has already been processed).  If the IEOT extension is not
available then parsing the index will proceed as usual with a single thread.

Signed-off-by: Ben Peart <benpeart@microsoft.com>
---
 cache.h       |  25 +++++
 config.c      |  20 ++++
 config.h      |   1 +
 environment.c |   3 +
 read-cache.c  | 343 ++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 5 files changed, 371 insertions(+), 21 deletions(-)

diff --git a/cache.h b/cache.h
index d74f00d8db..ea0c4b4b97 100644
--- a/cache.h
+++ b/cache.h
@@ -794,6 +794,7 @@ extern char *git_replace_ref_base;
 
 extern int fsync_object_files;
 extern int core_preload_index;
+extern int core_fast_index;
 extern int core_apply_sparse_checkout;
 extern int precomposed_unicode;
 extern int protect_hfs;
@@ -1942,4 +1943,28 @@ void sleep_millisec(int millisec);
  */
 void safe_create_dir(const char *dir, int share);
 
+
+#ifndef NO_PTHREADS
+struct index_entry_offset
+{
+	/* starting byte offset into index file, count of index entries in this block */
+	int offset, nr;
+};
+
+struct index_entry_offset_table
+{
+	int nr;
+	struct index_entry_offset entries[0];
+};
+
+extern struct index_entry_offset_table *read_ieot_extension(void *mmap, size_t mmap_size);
+
+struct ondisk_cache_entry;
+extern struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,
+	unsigned long *ent_size,
+	struct strbuf *previous_name,
+	int use_length);
+
+#endif
+
 #endif /* CACHE_H */
diff --git a/config.c b/config.c
index 903abf9533..44b08f57eb 100644
--- a/config.c
+++ b/config.c
@@ -1203,6 +1203,11 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.fastindex")) {
+		core_fast_index = git_config_bool(var, value);
+		return 0;
+	}
+
 	if (!strcmp(var, "core.createobject")) {
 		if (!strcmp(value, "rename"))
 			object_creation_mode = OBJECT_CREATION_USES_RENAMES;
@@ -2156,6 +2161,21 @@ int git_config_get_max_percent_split_change(void)
 	return -1; /* default value */
 }
 
+int ignore_fast_index_config;
+int git_config_get_fast_index(void)
+{
+	int val;
+
+	/* Hack for test programs like test-ieot */
+	if (ignore_fast_index_config)
+		return core_fast_index;
+
+	if (!git_config_get_maybe_bool("core.fastindex", &val))
+		return val;
+
+	return -1; /* default value */
+}
+
 NORETURN
 void git_die_config_linenr(const char *key, const char *filename, int linenr)
 {
diff --git a/config.h b/config.h
index a49d264416..3f78b1d262 100644
--- a/config.h
+++ b/config.h
@@ -212,6 +212,7 @@ extern int git_config_get_pathname(const char *key, const char **dest);
 extern int git_config_get_untracked_cache(void);
 extern int git_config_get_split_index(void);
 extern int git_config_get_max_percent_split_change(void);
+extern int git_config_get_fast_index(void);
 
 /* This dies if the configured or default date is in the future */
 extern int git_config_get_expiry(const char *key, const char **output);
diff --git a/environment.c b/environment.c
index 8289c25b44..492ef9c741 100644
--- a/environment.c
+++ b/environment.c
@@ -87,6 +87,9 @@ int auto_comment_line_char;
 /* Parallel index stat data preload? */
 int core_preload_index = 1;
 
+/* Parallel index cache entry loading? */
+int core_fast_index;
+
 /*
  * This is a hack for test programs like test-dump-untracked-cache to
  * ensure that they do not modify the untracked cache when reading it.
diff --git a/read-cache.c b/read-cache.c
index f3d125c114..174be0da38 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -19,6 +19,7 @@
 #include "varint.h"
 #include "split-index.h"
 #include "utf8.h"
+#include "thread-utils.h"
 
 /* Mask for the name length in ce_flags in the on-disk index */
 
@@ -38,6 +39,7 @@
 #define CACHE_EXT_RESOLVE_UNDO 0x52455543 /* "REUC" */
 #define CACHE_EXT_LINK 0x6c696e6b	  /* "link" */
 #define CACHE_EXT_UNTRACKED 0x554E5452	  /* "UNTR" */
+#define CACHE_EXT_FASTINDEX 0x49454F54	  /* "IEOT" */
 
 /* changes that can be kept in $GIT_DIR/index (basically all extensions) */
 #define EXTMASK (RESOLVE_UNDO_CHANGED | CACHE_TREE_CHANGED | \
@@ -1551,6 +1553,9 @@ static int read_index_extension(struct index_state *istate,
 	case CACHE_EXT_UNTRACKED:
 		istate->untracked = read_untracked_extension(data, sz);
 		break;
+	case CACHE_EXT_FASTINDEX:
+		/* already handled in do_read_index() */
+		break;
 	default:
 		if (*ext < 'A' || 'Z' < *ext)
 			return error("index uses %.4s extension, which we do not understand",
@@ -1604,10 +1609,12 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on
  * number of bytes to be stripped from the end of the previous name,
  * and the bytes to append to the result, to come up with its name.
  */
-static unsigned long expand_name_field(struct strbuf *name, const char *cp_)
+static unsigned long expand_name_field(struct strbuf *name, const char *cp_, int use_length)
 {
 	const unsigned char *ep, *cp = (const unsigned char *)cp_;
 	size_t len = decode_varint(&cp);
+	if (!use_length)
+		len = name->len;
 
 	if (name->len < len)
 		die("malformed name field in the index");
@@ -1618,9 +1625,10 @@ static unsigned long expand_name_field(struct strbuf *name, const char *cp_)
 	return (const char *)ep + 1 - cp_;
 }
 
-static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,
+struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,
 					    unsigned long *ent_size,
-					    struct strbuf *previous_name)
+					    struct strbuf *previous_name,
+						int use_length)
 {
 	struct cache_entry *ce;
 	size_t len;
@@ -1654,7 +1662,7 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,
 		*ent_size = ondisk_ce_size(ce);
 	} else {
 		unsigned long consumed;
-		consumed = expand_name_field(previous_name, name);
+		consumed = expand_name_field(previous_name, name, use_length);
 		ce = cache_entry_from_ondisk(ondisk, flags,
 					     previous_name->buf,
 					     previous_name->len);
@@ -1725,16 +1733,208 @@ static void post_read_index_from(struct index_state *istate)
 	tweak_split_index(istate);
 }
 
+static unsigned long load_cache_entries(struct index_state *istate, int offset, int nr, void *mmap, unsigned long start_offset)
+{
+	int i;
+	unsigned long src_offset = start_offset;
+	struct strbuf previous_name_buf = STRBUF_INIT, *previous_name;
+
+	if (istate->version == 4)
+		previous_name = &previous_name_buf;
+	else
+		previous_name = NULL;
+
+	for (i = offset; i < offset + nr; i++) {
+		struct ondisk_cache_entry *disk_ce;
+		struct cache_entry *ce;
+		unsigned long consumed;
+
+		disk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);
+		ce = create_from_disk(disk_ce, &consumed, previous_name, i == offset ? 0 : 1);
+		set_index_entry(istate, i, ce);
+
+		src_offset += consumed;
+	}
+	strbuf_release(&previous_name_buf);
+	return src_offset - start_offset;
+}
+
+#ifndef NO_PTHREADS
+
+/*
+ * Mostly randomly chosen cache entries per thread (it works on my machine):
+ * we want to have at least 7500 cache entries per thread for it to
+ * be worth starting a thread.
+ */
+#define THREAD_COST		(7500)
+#define IEOT_VERSION	(1)
+
+static int ce_write(git_SHA_CTX *context, int fd, void *data, unsigned int len);
+
+static int write_index_ext_header(git_SHA_CTX *context, int fd,
+	unsigned int ext, unsigned int sz);
+
+struct load_cache_entries_thread_data
+{
+	pthread_t pthread;
+	struct index_state *istate;
+	int offset;			/* starting index into the istate->cache array */
+	void *mmap;
+	unsigned long consumed;	/* return # of bytes in index file processed */
+	struct index_entry_offset_table *ieot;
+	int ieot_offset;	/* starting index into the ieot array */
+	int ieot_work;		/* count of ieot entries to process */
+};
+
+/*
+ * A thread proc to run the load_cache_entries() computation
+ * across multiple background threads.
+ */
+static void *load_cache_entries_thread(void *_data)
+{
+	struct load_cache_entries_thread_data *p = _data;
+	int i;
+
+	/* itterate across all ieot blocks assigned to this thread */
+	for (i = p->ieot_offset; i < p->ieot_offset + p->ieot_work; i++) {
+		p->consumed += load_cache_entries(p->istate, p->offset, p->ieot->entries[i].nr, p->mmap, p->ieot->entries[i].offset);
+		p->offset += p->ieot->entries[i].nr;
+	}
+	return NULL;
+}
+
+struct index_entry_offset_table *read_ieot_extension(void *mmap, size_t mmap_size)
+{
+	/*
+	 * The IEOT extension is guaranteed to be last so that it can be found
+	 * by scanning backwards from the EOF.  In addition to the regular 4-byte
+	 * extension name and 4-byte section length is network byte order, it
+	 * also stores the 4-byte extension name and section length in reverse order
+	 * at the end of the extension.
+	 *
+	 * IEOT
+	 * 4-byte length
+	 * 4-byte version
+	 * variable length extension data...
+	 * 4-byte version
+	 * 4-byte length
+	 * IEOT
+	 * <SHA1>
+	 *
+	 * If names, lengths and versions match, the extension is assumed to be valid.
+	 */
+	const char *index;
+	uint32_t extsize_leading, extsize_trailing, ext_version;
+	struct index_entry_offset_table *ieot;
+	int i, nr;
+
+	/* validate the trailing extension signature */
+	index = (const char *)mmap + mmap_size - GIT_SHA1_RAWSZ - 4;
+	if (CACHE_EXT(index) != CACHE_EXT_FASTINDEX)
+		return NULL;
+	index -= sizeof(uint32_t);
+
+	/*
+	 * Validate the offset we're going to look for the leading extension
+	 * signature is past the index header.
+	 */
+	extsize_trailing = get_be32(index);
+	if ((index - extsize_trailing) < ((const char *)mmap + 12))
+		return NULL;
+	index -= sizeof(uint32_t);
+
+	/* validate the trailing version is IEOT_VERSION */
+	ext_version = get_be32(index);
+	if (ext_version != IEOT_VERSION)
+		return NULL;
+	index -= (extsize_trailing - sizeof(uint32_t));
+
+	/* validate the leading extension signature */
+	if (CACHE_EXT(index) != CACHE_EXT_FASTINDEX)
+		return NULL;
+	index += sizeof(uint32_t);
+
+	/* validate the leading extension size */
+	extsize_leading = get_be32(index);
+	if (extsize_leading != extsize_trailing)
+		return NULL;
+	index += sizeof(uint32_t);
+
+	/* validate the leading version is IEOT_VERSION */
+	ext_version = get_be32(index);
+	if (ext_version != IEOT_VERSION)
+		return NULL;
+	index += sizeof(uint32_t);
+
+	/* extension size - leading/trailing version bytes - trailing size - trailing signature / bytes per entry */
+	nr = (extsize_leading - sizeof(uint32_t) - sizeof(uint32_t) - sizeof(uint32_t) - 4) / (sizeof(uint32_t) + sizeof(uint32_t));
+	assert(nr);
+	ieot = xmalloc(sizeof(struct index_entry_offset_table)
+		+ (nr * sizeof(struct index_entry_offset)));
+	ieot->nr = nr;
+	for (i = 0; i < nr; i++) {
+		ieot->entries[i].offset = get_be32(index);
+		index += sizeof(uint32_t);
+		ieot->entries[i].nr = get_be32(index);
+		index += sizeof(uint32_t);
+	}
+
+	return ieot;
+}
+
+static int write_ieot_extension(git_SHA_CTX *context, int fd, struct index_entry_offset_table *ieot)
+{
+	struct strbuf sb = STRBUF_INIT;
+	uint32_t buffer;
+	int i, err;
+
+	/* version */
+	put_be32(&buffer, IEOT_VERSION);
+	strbuf_add(&sb, &buffer, sizeof(uint32_t));
+
+	/* ieot */
+	for (i = 0; i < ieot->nr; i++) {
+
+		/* offset */
+		put_be32(&buffer, ieot->entries[i].offset);
+		strbuf_add(&sb, &buffer, sizeof(uint32_t));
+
+		/* count */
+		put_be32(&buffer, ieot->entries[i].nr);
+		strbuf_add(&sb, &buffer, sizeof(uint32_t));
+	}
+
+	/* version */
+	put_be32(&buffer, IEOT_VERSION);
+	strbuf_add(&sb, &buffer, sizeof(uint32_t));
+
+	/* size */
+	put_be32(&buffer, sb.len + sizeof(uint32_t) + 4);
+	strbuf_add(&sb, &buffer, sizeof(uint32_t));
+
+	/* signature */
+	put_be32(&buffer, CACHE_EXT_FASTINDEX);
+	strbuf_add(&sb, &buffer, 4);
+
+	/* leading signature and size + extension data */
+	err = write_index_ext_header(context, fd, CACHE_EXT_FASTINDEX, sb.len) < 0
+		|| ce_write(context, fd, sb.buf, sb.len) < 0;
+	strbuf_release(&sb);
+
+	return err;
+}
+
+#endif
+
 /* remember to discard_cache() before reading a different cache! */
 int do_read_index(struct index_state *istate, const char *path, int must_exist)
 {
-	int fd, i;
+	int fd;
 	struct stat st;
 	unsigned long src_offset;
 	struct cache_header *hdr;
 	void *mmap;
 	size_t mmap_size;
-	struct strbuf previous_name_buf = STRBUF_INIT, *previous_name;
 
 	if (istate->initialized)
 		return istate->cache_nr;
@@ -1771,24 +1971,75 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist)
 	istate->cache = xcalloc(istate->cache_alloc, sizeof(*istate->cache));
 	istate->initialized = 1;
 
-	if (istate->version == 4)
-		previous_name = &previous_name_buf;
-	else
-		previous_name = NULL;
-
 	src_offset = sizeof(*hdr);
-	for (i = 0; i < istate->cache_nr; i++) {
-		struct ondisk_cache_entry *disk_ce;
-		struct cache_entry *ce;
-		unsigned long consumed;
+#ifdef NO_PTHREADS
+	src_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);
+#else
+	if (git_config_get_fast_index() != 1) {
+		src_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);
+	} else {
+		struct index_entry_offset_table *ieot;
+		int threads, cpus = online_cpus();
 
-		disk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);
-		ce = create_from_disk(disk_ce, &consumed, previous_name);
-		set_index_entry(istate, i, ce);
+		threads = istate->cache_nr / THREAD_COST;
+		if (threads > cpus)
+			threads = cpus;
 
-		src_offset += consumed;
+		/* enable testing with fewer than default minimum of entries */
+		if (threads < 2 && getenv("GIT_FASTINDEX_TEST"))
+			threads = 2;
+
+		/*
+		 * Locate and read the fast index extension so that we can use it
+		 * to multi-thread the reading of the cache entries.
+		 */
+		ieot = read_ieot_extension(mmap, mmap_size);
+		if (threads < 2 || !ieot) {
+			src_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);
+		} else {
+			int i, offset, ieot_work, ieot_offset;
+			struct load_cache_entries_thread_data *data;
+
+			/* ensure we have no more threads than we have blocks to process */
+			if (threads > ieot->nr)
+				threads = ieot->nr;
+			data = xcalloc(threads, sizeof(struct load_cache_entries_thread_data));
+
+			offset = ieot_offset = 0;
+			ieot_work = DIV_ROUND_UP(ieot->nr, threads);
+			for (i = 0; i < threads; i++) {
+				struct load_cache_entries_thread_data *p = &data[i];
+				int j;
+
+				if (ieot_offset + ieot_work > ieot->nr)
+					ieot_work = ieot->nr - ieot_offset;
+
+				p->istate = istate;
+				p->offset = offset;
+				p->mmap = mmap;
+				p->ieot = ieot;
+				p->ieot_offset = ieot_offset;
+				p->ieot_work = ieot_work;
+				if (pthread_create(&p->pthread, NULL, load_cache_entries_thread, p))
+					die("unable to create threaded load_cache_entries");
+
+				/* increment by the number of cache entries in the ieot block being processed */
+				for (j = 0; j < ieot_work; j++)
+					offset += ieot->entries[ieot_offset + j].nr;
+				ieot_offset += ieot_work;
+			}
+			for (i = 0; i < threads; i++) {
+				struct load_cache_entries_thread_data *p = data + i;
+				if (pthread_join(p->pthread, NULL))
+					die("unable to join threaded load_cache_entries");
+				src_offset += p->consumed;
+			}
+			free(data);
+		}
+		free(ieot);
 	}
-	strbuf_release(&previous_name_buf);
+#endif
+
 	istate->timestamp.sec = st.st_mtime;
 	istate->timestamp.nsec = ST_MTIME_NSEC(st);
 
@@ -2205,6 +2456,9 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,
 	struct ondisk_cache_entry_extended ondisk;
 	struct strbuf previous_name_buf = STRBUF_INIT, *previous_name;
 	int drop_cache_tree = 0;
+	int ieot_work = 1;
+	struct index_entry_offset_table *ieot = NULL;
+	int offset, nr;
 
 	for (i = removed = extended = 0; i < entries; i++) {
 		if (cache[i]->ce_flags & CE_REMOVE)
@@ -2238,6 +2492,22 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,
 	if (ce_write(&c, newfd, &hdr, sizeof(hdr)) < 0)
 		return -1;
 
+	if (!strip_extensions && core_fast_index) {
+		int ieot_blocks, cpus = online_cpus();
+
+		ieot_blocks = istate->cache_nr / THREAD_COST;
+		if (ieot_blocks < 1)
+			ieot_blocks = 1;
+		if (ieot_blocks > cpus)
+			ieot_blocks = cpus;
+		ieot = xcalloc(1, sizeof(struct index_entry_offset_table)
+			+ (ieot_blocks * sizeof(struct index_entry_offset)));
+		ieot->nr = 0;
+		ieot_work = DIV_ROUND_UP(entries, ieot_blocks);
+	}
+
+	offset = lseek(newfd, 0, SEEK_CUR) + write_buffer_len;
+	nr = 0;
 	previous_name = (hdr_version == 4) ? &previous_name_buf : NULL;
 
 	for (i = 0; i < entries; i++) {
@@ -2259,11 +2529,30 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,
 
 			drop_cache_tree = 1;
 		}
+		if (ieot && i && (i % ieot_work == 0)) {
+			ieot->entries[ieot->nr].nr = nr;
+			ieot->entries[ieot->nr].offset = offset;
+			ieot->nr++;
+			/*
+			 * If we have a V4 index, set the first byte to an invalid
+			 * character to ensure there is nothing common with the previous
+			 * entry
+			 */
+			if (previous_name)
+				previous_name->buf[0] = 0;
+			nr = 0;
+			offset = lseek(newfd, 0, SEEK_CUR) + write_buffer_len;
+		}
 		if (ce_write_entry(&c, newfd, ce, previous_name, (struct ondisk_cache_entry *)&ondisk) < 0)
 			err = -1;
-
 		if (err)
 			break;
+		nr++;
+	}
+	if (ieot && nr) {
+		ieot->entries[ieot->nr].nr = nr;
+		ieot->entries[ieot->nr].offset = offset;
+		ieot->nr++;
 	}
 	strbuf_release(&previous_name_buf);
 
@@ -2315,6 +2604,18 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,
 			return -1;
 	}
 
+	/*
+	 * CACHE_EXT_FASTINDEX must be written as the last entry before the SHA1
+	 * so that it can be found and processed before all the index entries are
+	 * read.
+	 */
+	if (!strip_extensions && ieot) {
+		err = write_ieot_extension(&c, newfd, ieot);
+		free(ieot);
+		if (err)
+			return -1;
+	}
+
 	if (ce_flush(&c, newfd, istate->sha1))
 		return -1;
 	if (close_tempfile_gently(tempfile)) {
-- 
2.15.0.windows.1

[PATCH v1 2/4] update-index: add fastindex support to update-index

[Ben Peart]

Add support in update-index to manually add/remove the fastindex
extension via --[no-]fastindex flags.

Signed-off-by: Ben Peart <benpeart@microsoft.com>
---
 builtin/update-index.c | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/builtin/update-index.c b/builtin/update-index.c
index fefbe60167..63b7f18807 100644
--- a/builtin/update-index.c
+++ b/builtin/update-index.c
@@ -917,6 +917,7 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)
 	struct refresh_params refresh_args = {0, &has_errors};
 	int lock_error = 0;
 	int split_index = -1;
+	int fast_index = -1;
 	struct lock_file lock_file = LOCK_INIT;
 	struct parse_opt_ctx_t ctx;
 	strbuf_getline_fn getline_fn;
@@ -1008,6 +1009,8 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)
 			    N_("test if the filesystem supports untracked cache"), UC_TEST),
 		OPT_SET_INT(0, "force-untracked-cache", &untracked_cache,
 			    N_("enable untracked cache without testing the filesystem"), UC_FORCE),
+		OPT_BOOL(0, "fastindex", &fast_index,
+			N_("enable or disable fast index parsing")),
 		OPT_END()
 	};
 
@@ -1146,6 +1149,25 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)
 		die("BUG: bad untracked_cache value: %d", untracked_cache);
 	}
 
+	if (fast_index > 0) {
+		if (git_config_get_fast_index() == 0)
+			warning(_("core.fastindex is unset; "
+				"set it if you really want to "
+				"enable fastindex"));
+		core_fast_index = 1;
+		active_cache_changed |= SOMETHING_CHANGED;
+		report(_("fastindex enabled"));
+	}
+	else if (!fast_index) {
+		if (git_config_get_fast_index() == 1)
+			warning(_("core.fastindex is set; "
+				"remove it if you really want to "
+				"disable fastindex"));
+		core_fast_index = 0;
+		active_cache_changed |= SOMETHING_CHANGED;
+		report(_("fastindex disabled"));
+	}
+
 	if (active_cache_changed) {
 		if (newfd < 0) {
 			if (refresh_args.flags & REFRESH_QUIET)
-- 
2.15.0.windows.1

[PATCH v1 3/4] fastindex: add test tools and a test script

[Ben Peart]

Add a test utility (test-dump-fast-index) that dumps the contents of the
IEOT to stdout.  This enables checking the existance of the extension
and the ability to parse and output its contents.

Add a test utility (test-fast-index) that loads the index using the
fastindex logic then loads it using the regular logic and compares the
results of the two.  Any differences are reported and an error is returned.

Add a test script (t1800-fast-index.sh) to:

Test the ability to add/remove the fastindex index extension via
update-index.

Verify that loading the index with and without the fastindex extension
return the same results with both V2 and V4 indexes.

Signed-off-by: Ben Peart <benpeart@microsoft.com>
---
 Makefile                        |  2 +
 t/helper/test-dump-fast-index.c | 68 +++++++++++++++++++++++++++++++++
 t/helper/test-fast-index.c      | 84 +++++++++++++++++++++++++++++++++++++++++
 t/t1800-fast-index.sh           | 55 +++++++++++++++++++++++++++
 4 files changed, 209 insertions(+)
 create mode 100644 t/helper/test-dump-fast-index.c
 create mode 100644 t/helper/test-fast-index.c
 create mode 100644 t/t1800-fast-index.sh

diff --git a/Makefile b/Makefile
index cd75985991..a7df82721e 100644
--- a/Makefile
+++ b/Makefile
@@ -647,9 +647,11 @@ TEST_PROGRAMS_NEED_X += test-config
 TEST_PROGRAMS_NEED_X += test-date
 TEST_PROGRAMS_NEED_X += test-delta
 TEST_PROGRAMS_NEED_X += test-dump-cache-tree
+TEST_PROGRAMS_NEED_X += test-dump-fast-index
 TEST_PROGRAMS_NEED_X += test-dump-split-index
 TEST_PROGRAMS_NEED_X += test-dump-untracked-cache
 TEST_PROGRAMS_NEED_X += test-fake-ssh
+TEST_PROGRAMS_NEED_X += test-fast-index
 TEST_PROGRAMS_NEED_X += test-genrandom
 TEST_PROGRAMS_NEED_X += test-hashmap
 TEST_PROGRAMS_NEED_X += test-index-version
diff --git a/t/helper/test-dump-fast-index.c b/t/helper/test-dump-fast-index.c
new file mode 100644
index 0000000000..4e6d28d660
--- /dev/null
+++ b/t/helper/test-dump-fast-index.c
@@ -0,0 +1,68 @@
+#include "cache.h"
+
+int cmd_main(int ac, const char **av)
+{
+#ifndef NO_PTHREADS
+	const char *path;
+	int fd, i;
+	struct stat st;
+	void *mmap;
+	size_t mmap_size;
+	struct cache_header *hdr;
+	struct index_entry_offset_table *ieot;
+	struct strbuf previous_name_buf = STRBUF_INIT, *previous_name;
+	int err = 0;
+
+	setup_git_directory();
+	path = get_index_file();
+	fd = open(path, O_RDONLY);
+	if (fd < 0) {
+		die("%s: index file open failed", path);
+	}
+
+	if (fstat(fd, &st))
+		die("cannot stat the open index");
+
+	mmap_size = xsize_t(st.st_size);
+	if (mmap_size < sizeof(struct cache_header) + GIT_SHA1_RAWSZ)
+		die("index file smaller than expected");
+
+	mmap = xmmap(NULL, mmap_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	if (mmap == MAP_FAILED)
+		die("unable to map index file");
+	close(fd);
+
+	hdr = mmap;
+	if (ntohl(hdr->hdr_version) == 4)
+		previous_name = &previous_name_buf;
+	else
+		previous_name = NULL;
+
+	ieot = read_ieot_extension(mmap, mmap_size);
+	if (ieot) {
+		printf("IEOT with %d entries\n", ieot->nr);
+		printf("  Offset    Count Name\n");
+		printf("-------- -------- ------------------------\n");
+		for (i = 0; i < ieot->nr; i++) {
+			struct ondisk_cache_entry *disk_ce;
+			struct cache_entry *ce;
+			unsigned long consumed;
+
+			disk_ce = (struct ondisk_cache_entry *)((char *)mmap + ieot->entries[i].offset);
+			ce = create_from_disk(disk_ce, &consumed, previous_name, 0);
+			printf("%8d %8d %.*s\n", ieot->entries[i].offset, ieot->entries[i].nr, ce->ce_namelen, ce->name);
+			free(ce);
+		}
+	} else {
+		printf("missing or invalid extension");
+		err = 1;
+	}
+
+	free(ieot);
+	munmap(mmap, mmap_size);
+	return err;
+#else
+	die("ieot only supported with PTHREADS");
+	return -1;
+#endif
+}
diff --git a/t/helper/test-fast-index.c b/t/helper/test-fast-index.c
new file mode 100644
index 0000000000..fe63130ba0
--- /dev/null
+++ b/t/helper/test-fast-index.c
@@ -0,0 +1,84 @@
+#include "cache.h"
+
+int compare_ce(const struct cache_entry *ce1, const struct cache_entry *ce2)
+{
+	/*	struct hashmap_entry ent; */
+	/*	struct stat_data ce_stat_data; */
+
+	if (ce1->ce_mode != ce2->ce_mode) {
+		printf("ce_mode: %d:%d\n", ce1->ce_mode, ce2->ce_mode);
+		return 1;
+	}
+
+	if (ce1->ce_flags != ce2->ce_flags) {
+		printf("ce_flags: %d:%d\n", ce1->ce_flags, ce2->ce_flags);
+		return 1;
+	}
+
+	if (ce1->ce_namelen != ce2->ce_namelen) {
+		printf("namelen: %d:%d\n", ce1->ce_namelen, ce2->ce_namelen);
+		return 1;
+	}
+
+	if (ce1->index != ce2->index) {
+		printf("index: %d:%d\n", ce1->index, ce2->index);
+		return 1;
+	}
+
+	if (oidcmp(&ce1->oid, &ce2->oid)) {
+		printf("oid: %s:%s\n", oid_to_hex(&ce1->oid), oid_to_hex(&ce2->oid));
+		return 1;
+	}
+
+	if (strcmp(ce1->name, ce2->name)) {
+		printf("name: %s:%s\n", ce1->name, ce2->name);
+		return 1;
+	}
+
+
+	return 0;
+}
+
+extern int ignore_fast_index_config;
+
+int cmd_main(int ac, const char **av)
+{
+#ifndef NO_PTHREADS
+	static struct index_state index;
+	static struct index_state ieot;
+	int i, err = 0;
+
+	setup_git_directory();
+	ignore_fast_index_config = 1;
+	core_fast_index = 0;
+	read_index(&index);
+	core_fast_index = 1;
+	read_index(&ieot);
+
+	for (i = 0; i < index.cache_nr; i++) {
+		if (compare_ce(index.cache[i], ieot.cache[i])) {
+			struct cache_entry *ce;
+
+			ce = index.cache[i];
+			printf("%06o %s %d\t%s\n", ce->ce_mode,
+				oid_to_hex(&ce->oid), ce_stage(ce), ce->name);
+			ce = ieot.cache[i];
+			printf("%06o %s %d\t%s\n", ce->ce_mode,
+				oid_to_hex(&ce->oid), ce_stage(ce), ce->name);
+
+			printf("cache entry %d does not match", i);
+			err = 1;
+			break;
+		}
+	}
+
+	discard_index(&ieot);
+	discard_index(&index);
+	if (!err)
+		printf("Cache entires are the same\n");
+	return err;
+#else
+	die("ieot only supported with PTHREADS");
+	return -1;
+#endif
+}
diff --git a/t/t1800-fast-index.sh b/t/t1800-fast-index.sh
new file mode 100644
index 0000000000..b3460f1698
--- /dev/null
+++ b/t/t1800-fast-index.sh
@@ -0,0 +1,55 @@
+#!/bin/sh
+
+test_description='git fast index tests'
+
+. ./test-lib.sh
+
+GIT_FASTINDEX_TEST=1; export GIT_FASTINDEX_TEST
+
+test_expect_success 'setup' '
+	: >tracked &&
+	: >modified &&
+	mkdir dir1 &&
+	: >dir1/tracked &&
+	: >dir1/modified &&
+	mkdir dir2 &&
+	: >dir2/tracked &&
+	: >dir2/modified &&
+	git add . &&
+	git commit -m initial &&
+	cat >.gitignore <<-\EOF
+	.gitignore
+	expect*
+	actual*
+	EOF
+'
+
+test_expect_success 'fastindex extension is off by default' '
+	test_must_fail test-dump-fast-index >actual 2>&1 &&
+	grep "^missing or invalid extension" actual
+'
+
+test_expect_success 'update-index --fastindex" adds the fsmonitor extension' '
+	git update-index --fastindex &&
+	test-dump-fast-index >actual &&
+	grep "^IEOT with" actual
+'
+
+test_expect_success 'update-index --no-fastindex" removes the fastindex extension' '
+	git update-index --no-fastindex &&
+	test_must_fail test-dump-fast-index >actual &&
+	grep "^missing or invalid extension" actual
+'
+
+test_expect_success 'verify with and without fastindex returns same result' '
+	git update-index --fastindex &&
+	test-fast-index
+'
+
+test_expect_success 'test with V4 index' '
+	git config core.fastindex 1 &&
+	git update-index --index-version 4 &&
+	test-fast-index
+'
+
+test_done
-- 
2.15.0.windows.1

[PATCH v1 4/4] fastindex: add documentation for the fastindex extension

[Ben Peart]

This includes the core.fastindex setting, the update-index additions,
and the fastindex index extension.

Signed-off-by: Ben Peart <benpeart@microsoft.com>
---
 Documentation/config.txt                 |  8 ++++++++
 Documentation/git-update-index.txt       | 11 +++++++++++
 Documentation/technical/index-format.txt | 26 ++++++++++++++++++++++++++
 3 files changed, 45 insertions(+)

diff --git a/Documentation/config.txt b/Documentation/config.txt
index 5f0d62753d..269ff97c8c 100644
--- a/Documentation/config.txt
+++ b/Documentation/config.txt
@@ -868,6 +868,14 @@ relatively high IO latencies.  When enabled, Git will do the
 index comparison to the filesystem data in parallel, allowing
 overlapping IO's.  Defaults to true.
 
+core.fastIndex::
+	Enable parallel index loading
++
+This can speed up operations like 'git diff' and 'git status' especially
+when the index is very large.  When enabled, Git will do the index
+loading from the on disk format to the in-memory format in parallel.
+Defaults to false.
+
 core.createObject::
 	You can set this to 'link', in which case a hardlink followed by
 	a delete of the source are used to make sure that object creation
diff --git a/Documentation/git-update-index.txt b/Documentation/git-update-index.txt
index 75c7dd9dea..7ffd285c94 100644
--- a/Documentation/git-update-index.txt
+++ b/Documentation/git-update-index.txt
@@ -19,6 +19,7 @@ SYNOPSIS
 	     [--ignore-submodules]
 	     [--[no-]split-index]
 	     [--[no-|test-|force-]untracked-cache]
+	     [--[no-]fastindex]
 	     [--really-refresh] [--unresolve] [--again | -g]
 	     [--info-only] [--index-info]
 	     [-z] [--stdin] [--index-version <n>]
@@ -201,6 +202,16 @@ will remove the intended effect of the option.
 	`--untracked-cache` used to imply `--test-untracked-cache` but
 	this option would enable the extension unconditionally.
 
+--fastindex::
+--no-fastindex::
+	Enable or disable the fast index feature. These options
+	take effect whatever the value of the `core.fastindex`
+	configuration variable (see linkgit:git-config[1]). But a warning
+	is emitted when the change goes against the configured value, as
+	the configured value will take effect next time the index is
+	read and this will remove the intended effect of the option.
+
+
 \--::
 	Do not interpret any more arguments as options.
 
diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt
index ade0b0c445..e37b4cf874 100644
--- a/Documentation/technical/index-format.txt
+++ b/Documentation/technical/index-format.txt
@@ -295,3 +295,29 @@ The remaining data of each directory block is grouped by type:
     in the previous ewah bitmap.
 
   - One NUL.
+
+== Index Entry Offset Table
+
+  The Index Entry Offset Table (IEOT) is used to help address the CPU
+  cost of loading the index by enabling multi-threading the process of
+  converting cache entries from the on-disk format to the in-memory format.
+  Because it must be able to be loaded before the variable length cache
+  entries and other index extensions, this extension must be written last.
+  The signature for this extension is { 'I', 'E', 'O', 'T' }.
+
+  The extension consists of:
+
+  - 32-bit version (currently 1)
+
+  - A number of index offset entries each consisting of:
+
+    - 32-bit offset from the begining of the file to the first cache entry
+	  in this block of entries.
+
+    - 32-bit count of cache entries in this block
+
+  - 32-bit version (currently 1)
+
+  - 32-bit size of the extension
+
+  - 4-byte extension signature
-- 
2.15.0.windows.1

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Junio C Hamano]

Ben Peart <benpeart@microsoft.com> writes:

> To make this work for V4 indexes, when writing the index, it periodically
> "resets" the prefix-compression by encoding the current entry as if the
> path name for the previous entry is completely different and saves the
> offset of that entry in the IEOT.  Basically, with V4 indexes, it
> generates offsets into blocks of prefix-compressed entries.

You specifically mentioned about this change in your earlier
correspondence on this series, and it reminds me of Shawn's reftable
proposal that also is heavily depended on prefix compression with
occasional reset to allow scanning from an entry in the middle.  I
find it a totally sensible design choice.

> To enable reading the IEOT extension before reading all the variable
> length cache entries and other extensions, the IEOT is written last,
> right before the trailing SHA1.

OK, we have already closed the door for further enhancements to
place something other than the index extensions after this block by
mistakenly made it the rule that the end of the series of extended
sections must coincide with the beginning of the trailing checksum,
so it does not sound all that bad to insist on this particular one
to be the last, I guess.  But see below...

> The format of that extension has the signature bytes and size at the
> beginning (like a normal extension) as well as at the end in reverse
> order to enable parsing the extension by seeking back from the end of
> the file.

I think this is a reasonable workaround to allow a single extension
that needs to be read before the main index is loaded.  

But I'd suggest taking this approach one step further.  Instead,
what if we introduce a new extension EOIE ("end of index entries")
whose sole purpose is to sit at the end of the series of extensions
and point at the beginning of the index extension section of the
file, to tell you where to seek in order to skip the main index?

That way, you can

 - seek to the end of the index file;

 - go backward skiping the trailing file checksum;

 - now you might be at the end of the EOIE extension.  seek back
   necessary number of bytes and verify EOIE header, pick up the
   recorded file offset of the beginning of the extensions section.

 - The 4-byte sequence you found may happen to match EOIE but that
   is not enough to be sure that you indeed have such an extension.
   So the following must be done carefully, allowing the possibility
   that there wasn't any EOIE extension at the end.
   Seek back to that offset, and repeat these three steps to skip
   over all extensions:

   - read the (possible) 4-byte header
   - read the (possible) extsize (validate that this is a sane value)
   - skip that many bytes

   until you come back to the location you assumed that you found
   your EOIE header, to make sure you did not get fooled by bytes
   that happened to look like one.  Some "extsize" you picked up
   during that process may lead you beyond the end of the index
   file, which would be a sure sign that what you found at the end
   of the index file was *not* the EOIE extension but a part of
   some other extension who happened to have these four bytes at the
   right place.

which would be a lot more robust way to allow any extensions to be
read before the main body of the index.

And a lot more importantly, we will leave the door open to allow
more than one index extensions that we would prefer to read before
reading the main body if we do it this way, because we can easily
skip things over without spending cycles once we have a robust way
to find where the end of the main index is.  After all, the reason
you placed IEOT at the end is not because you wanted to have it at
the very end.  You only wanted to be able to find where it is
without having to parse the variable-length records of the main
index.  And there may be other index extensions that wants to be
readable without reading the main part just like IEOT, and we do not
want to close the door for them.

Hmm?

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Ben Peart]

On 11/9/2017 11:46 PM, Junio C Hamano wrote:
> Ben Peart <benpeart@microsoft.com> writes:
> 
>> To make this work for V4 indexes, when writing the index, it periodically
>> "resets" the prefix-compression by encoding the current entry as if the
>> path name for the previous entry is completely different and saves the
>> offset of that entry in the IEOT.  Basically, with V4 indexes, it
>> generates offsets into blocks of prefix-compressed entries.
> 
> You specifically mentioned about this change in your earlier
> correspondence on this series, and it reminds me of Shawn's reftable
> proposal that also is heavily depended on prefix compression with
> occasional reset to allow scanning from an entry in the middle.  I
> find it a totally sensible design choice.
> 

Great! I didn't realize there was already precedent for this in other 
patches.  I guess good minds think alike... :)

>> To enable reading the IEOT extension before reading all the variable
>> length cache entries and other extensions, the IEOT is written last,
>> right before the trailing SHA1.
> 
> OK, we have already closed the door for further enhancements to
> place something other than the index extensions after this block by
> mistakenly made it the rule that the end of the series of extended
> sections must coincide with the beginning of the trailing checksum,
> so it does not sound all that bad to insist on this particular one
> to be the last, I guess.  But see below...
> 
>> The format of that extension has the signature bytes and size at the
>> beginning (like a normal extension) as well as at the end in reverse
>> order to enable parsing the extension by seeking back from the end of
>> the file.
> 
> I think this is a reasonable workaround to allow a single extension
> that needs to be read before the main index is loaded.
> 
> But I'd suggest taking this approach one step further.  Instead,
> what if we introduce a new extension EOIE ("end of index entries")
> whose sole purpose is to sit at the end of the series of extensions
> and point at the beginning of the index extension section of the
> file, to tell you where to seek in order to skip the main index?
> 
> That way, you can
> 
>   - seek to the end of the index file;
> 
>   - go backward skiping the trailing file checksum;
> 
>   - now you might be at the end of the EOIE extension.  seek back
>     necessary number of bytes and verify EOIE header, pick up the
>     recorded file offset of the beginning of the extensions section.
> 
>   - The 4-byte sequence you found may happen to match EOIE but that
>     is not enough to be sure that you indeed have such an extension.
>     So the following must be done carefully, allowing the possibility
>     that there wasn't any EOIE extension at the end.
>     Seek back to that offset, and repeat these three steps to skip
>     over all extensions:
> 
>     - read the (possible) 4-byte header
>     - read the (possible) extsize (validate that this is a sane value)
>     - skip that many bytes
> 
>     until you come back to the location you assumed that you found
>     your EOIE header, to make sure you did not get fooled by bytes
>     that happened to look like one.  Some "extsize" you picked up
>     during that process may lead you beyond the end of the index
>     file, which would be a sure sign that what you found at the end
>     of the index file was *not* the EOIE extension but a part of
>     some other extension who happened to have these four bytes at the
>     right place.
> 

I'm doing this careful examination and verification in the patch 
already.  Please look closely at read_ieot_extension() to make sure 
there isn't a test I should be doing but missed.

> which would be a lot more robust way to allow any extensions to be
> read before the main body of the index.
> 
> And a lot more importantly, we will leave the door open to allow
> more than one index extensions that we would prefer to read before
> reading the main body if we do it this way, because we can easily
> skip things over without spending cycles once we have a robust way
> to find where the end of the main index is.  After all, the reason
> you placed IEOT at the end is not because you wanted to have it at
> the very end.  You only wanted to be able to find where it is
> without having to parse the variable-length records of the main
> index.  And there may be other index extensions that wants to be
> readable without reading the main part just like IEOT, and we do not
> want to close the door for them.
> 

The proposed format for extensions (ie having both a header and a footer 
with name and size) in the current patch already enables having multiple 
extensions that can be parsed forward or backward.  Any extensions that 
would want to be parse-able in reverse would just all need to be written 
one after the other after right before the trailing SHA1 (and of course, 
include the proper footer).  The same logic that parses the IEOT 
extension could be extended to continue looking backwards through the 
file parsing extensions until it encounters an unknown signature, 
invalid size, etc.

That said, the IEOT is essentially a table of contents into the index (I 
hesitate to call it an index of the index as that could get confusing 
:)).  While in the current iteration of this patch it only contains 
offsets into blocks of cache entries that are independently parse-able, 
I had initially considered including an offset into the index where the 
extensions start just as you suggest above.

When I looked at the existing extensions to see if they could be sped up 
by loading them on parallel threads I found that some of them 
assume/require they are processed in a specific order so there was no 
real benefit to loading them in parallel threads.

I ended up removing the offset to the first extension because I've found 
that trying to speculatively design a feature for a potential future 
need often doesn't result in what you actually need once you get there. 
:)  Instead, I made sure there was a version number in the IEOT 
structure so if we actually needed a way to extend the table of contents 
at some point in the future (like to include an offset to the 
extensions), we could easily add it and increment the IEOT version.

I could add the offset back in but currently nothing would use it so 
we're just adding additional complexity to calculate and parse it with 
with no (current) benefit.

How about I rename this the "Index Table of Contents" (ITOC) to make 
it's potential more clear and if/when we need to enhance it with an 
offset to the extensions, we do so at that point in time?

> Hmm?
> 

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Junio C Hamano]

Ben Peart <peartben@gmail.com> writes:

> The proposed format for extensions (ie having both a header and a
> footer with name and size) in the current patch already enables having
> multiple extensions that can be parsed forward or backward.  Any
> extensions that would want to be parse-able in reverse would just all
> need to be written one after the other after right before the trailing
> SHA1 (and of course, include the proper footer).

In other words, anything that wants to be scannable from the tail is
welcome to reimplement the same validation structure used by IEOT to
check the section specific sanity constraint, and this series is not
interested in introducing a more general infrastructure to make it
easy for code that want to find where each extension section in the
file begins without pasing the body of the index.

I find it somewhat unsatisfactory in that it is a fundamental change
to allow jumping to the start of an extension section from the tail
that can benefit any future codepath, and have expected a feature
neutral extension whose sole purpose is to do so [*1*].

That way, extension sections whose names are all-caps can stay to be
optional, even if they allow locating from the tail of the file.  If
you require them to implement the same validation struture as IEOT
to perform section specific sanity constraint and also require them
to be placed consecutively at the end, the reader MUST know about
all such extensions---otherwise they cannot scan backwards and find
ones that appear before an unknown but optional one.  If you keep an
extension section at the end whose sole purpose is to point at the
beginning of extension sections, the reader can then scan forward as
usual, skipping over unknown but optional ones, and reading your
IEOT can merely be an user (and the first user) of that more generic
feature that is futureproof, no?

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Ben Peart]

On 11/13/2017 8:10 PM, Junio C Hamano wrote:
> Ben Peart <peartben@gmail.com> writes:
> 
>> The proposed format for extensions (ie having both a header and a
>> footer with name and size) in the current patch already enables having
>> multiple extensions that can be parsed forward or backward.  Any
>> extensions that would want to be parse-able in reverse would just all
>> need to be written one after the other after right before the trailing
>> SHA1 (and of course, include the proper footer).
> 
> In other words, anything that wants to be scannable from the tail is
> welcome to reimplement the same validation structure used by IEOT to
> check the section specific sanity constraint, and this series is not
> interested in introducing a more general infrastructure to make it
> easy for code that want to find where each extension section in the
> file begins without pasing the body of the index.
> 
> I find it somewhat unsatisfactory in that it is a fundamental change
> to allow jumping to the start of an extension section from the tail
> that can benefit any future codepath, and have expected a feature
> neutral extension whose sole purpose is to do so [*1*].
> 
> That way, extension sections whose names are all-caps can stay to be
> optional, even if they allow locating from the tail of the file.  If
> you require them to implement the same validation struture as IEOT
> to perform section specific sanity constraint and also require them
> to be placed consecutively at the end, the reader MUST know about
> all such extensions---otherwise they cannot scan backwards and find
> ones that appear before an unknown but optional one.  If you keep an
> extension section at the end whose sole purpose is to point at the
> beginning of extension sections, the reader can then scan forward as
> usual, skipping over unknown but optional ones, and reading your
> IEOT can merely be an user (and the first user) of that more generic
> feature that is futureproof, no?
> 
> 

How about I add the logic to write out a special extension right before 
the SHA1 that contains an offset to the beginning of the extensions 
section.  I will also add the logic in do_read_index() to search for and 
load this special extension if it exists.

This will provide a common framework for any future extension to take 
advantage of if it wants to be loaded/processed before or in parallel 
with the cache entries or other extensions.

For all existing extensions that assume they are loaded _after_ the 
cache entries, in do_read_index() I'll add the logic to use the offset 
(if it exists) to adjust the src_offset and then load them normally.

Given the IEOT extension is just another list of offsets into the index 
to enable out of order processing, I'll add those offsets into the same 
extension so that it is a more generic "table of contents" for the 
entire index.  This enables us to have common/reusable way to have 
random access to _all_ sections in the index while maintaining backwards 
comparability with the existing index formats and code.

These additional offsets will initially only be used to parallelize the 
loading of cache entries and only if the user explicitly enables that 
option but I can think of other interesting uses for them in the future.

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Junio C Hamano]

Ben Peart <peartben@gmail.com> writes:

> How about I add the logic to write out a special extension right
> before the SHA1 that contains an offset to the beginning of the
> extensions section.  I will also add the logic in do_read_index() to
> search for and load this special extension if it exists.
>
> This will provide a common framework for any future extension to take
> advantage of if it wants to be loaded/processed before or in parallel
> with the cache entries or other extensions.
>
> For all existing extensions that assume they are loaded _after_ the
> cache entries, in do_read_index() I'll add the logic to use the offset
> (if it exists) to adjust the src_offset and then load them normally.
>
> Given the IEOT extension is just another list of offsets into the
> index to enable out of order processing, I'll add those offsets into
> the same extension so that it is a more generic "table of contents"
> for the entire index.  This enables us to have common/reusable way to
> have random access to _all_ sections in the index while maintaining
> backwards comparability with the existing index formats and code.
>
> These additional offsets will initially only be used to parallelize
> the loading of cache entries and only if the user explicitly enables
> that option but I can think of other interesting uses for them in the
> future.

If we freeze the format of IEOT extension so that we can guarantee
that the very first version of Git that understands IEOT can always
find the beginning of extension section in an index file that was
written by future versions of Git, then I'm all for that plan, but
my impression was that you are planning to make incompatible change
in the future to IEOT, judging from the waythat IEOT records its own
version number in the section and the reader uses it to reject an
unknown one.

With that plan, what I suspect would happen is that a version of Git
that understands another optional extension section that wants to be
findable without scanning the main table and the then-current
version of IEOT would not be able to use an index file written by a
new version of Git that enhances the format of the IEOT extension
bumps its extension version.

And if that is the case I would have to say that I strongly suspect
that you would regret the design decision to mix it into IEOT.  That
is why I keep suggesting that the back pointer extension should be
on its own, minimizing what it does and minimizing the need to be
updated across versions of Git.

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Ben Peart]

On 11/14/2017 10:04 AM, Junio C Hamano wrote:
> Ben Peart <peartben@gmail.com> writes:
> 
>> How about I add the logic to write out a special extension right
>> before the SHA1 that contains an offset to the beginning of the
>> extensions section.  I will also add the logic in do_read_index() to
>> search for and load this special extension if it exists.
>>
>> This will provide a common framework for any future extension to take
>> advantage of if it wants to be loaded/processed before or in parallel
>> with the cache entries or other extensions.
>>
>> For all existing extensions that assume they are loaded _after_ the
>> cache entries, in do_read_index() I'll add the logic to use the offset
>> (if it exists) to adjust the src_offset and then load them normally.
>>
>> Given the IEOT extension is just another list of offsets into the
>> index to enable out of order processing, I'll add those offsets into
>> the same extension so that it is a more generic "table of contents"
>> for the entire index.  This enables us to have common/reusable way to
>> have random access to _all_ sections in the index while maintaining
>> backwards comparability with the existing index formats and code.
>>
>> These additional offsets will initially only be used to parallelize
>> the loading of cache entries and only if the user explicitly enables
>> that option but I can think of other interesting uses for them in the
>> future.
> 
> If we freeze the format of IEOT extension so that we can guarantee
> that the very first version of Git that understands IEOT can always
> find the beginning of extension section in an index file that was
> written by future versions of Git, then I'm all for that plan, but
> my impression was that you are planning to make incompatible change
> in the future to IEOT, judging from the way that IEOT records its own
> version number in the section and the reader uses it to reject an
> unknown one.

I have no thoughts or plans for changes in the future of IEOT (which I 
plan to rename ITOC).  At this point in time, I can't even imagine what 
else we'd want as the index only contains cache entries, extensions and 
the trailing SHA1 and with the TOC we have random access to each of 
those.  If nothing else, it gives another signature to verify to ensure 
we actually have a valid trailing extension. :)

I only added the version because I've learned my ability to predict the 
future is pretty bad and it leaves us that option _if_ something ever 
comes up that we need it _and_ are willing to live with the significant 
negative trade-offs you correctly point out.

> 
> With that plan, what I suspect would happen is that a version of Git
> that understands another optional extension section that wants to be
> findable without scanning the main table and the then-current
> version of IEOT would not be able to use an index file written by a
> new version of Git that enhances the format of the IEOT extension
> bumps its extension version.
> 
> And if that is the case I would have to say that I strongly suspect
> that you would regret the design decision to mix it into IEOT.  That
> is why I keep suggesting that the back pointer extension should be
> on its own, minimizing what it does and minimizing the need to be
> updated across versions of Git.
> 

I understand the risk but the list of offsets into the cache entries is 
pretty simple as well. I prefer the simplicity of a single TOC extension 
that gives us random access to the entire index rather than having to 
piece one together using multiple extensions.  That model has its own 
set of risks and tradeoffs.

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Junio C Hamano]

Ben Peart <peartben@gmail.com> writes:

> I have no thoughts or plans for changes in the future of IEOT (which I
> plan to rename ITOC).  At this point in time, I can't even imagine
> what else we'd want as the index only contains cache entries, ...

Yeah, but the thing is that this is open source, and the imagination
of the originator of the initial idea does not limit how the code
and data structure evolves.

Back when I added the index extensions to the system, I didn't have
perfect foresight, and I didn't have specific plans to add anything
beyond "TREE" to optimize "write-tree" and "diff-index --cached".

In hindsight, I got one thing right and one thing wrong.

Even though I didn't have any plan to add a mandatory extension, I
made the code to ignore optional ones and error out on mandatory
ones if an index extension section is not understood.  It turns out
that later (in fact much later---the "TREE" extension dates back to
April 2006, while "link" came in June 2014) we could add the
split-index mode without having to worry about older versions of Git
doing random wrong things when they see this new extension, thanks
to that design decision.  That went well.

On the other hand, I didn't think things through to realize that
some operations may want to peek only the extensions without ever
using the main table, that some other operations may want to read
some extensions first before reading the main table, or more
importantly, that these limitations would start mattering once Git
becomes popular enough and starts housing a project tree with very
many paths in the main table.  

I really wish somebody had brought it up as a potential issue during
the review---I would have defined the extended index format to have
the simple extension at the end that points back to the tail end of
the main table back then, and we wouldn't be having this back and
forth now.  But I was just too happy and excited that I have found a
room to squeeze extension sections into the index file format
without breaking existing implementations of Git (which checked the
trailer checksum matches to the result of hashing the whole thing,
and read the recorded number of entries from the main table, without
even noticing that there is a gap in between), and that excitement
blinded me.

> I understand the risk but the list of offsets into the cache entries
> is pretty simple as well. I prefer the simplicity of a single TOC
> extension that gives us random access to the entire index rather than
> having to piece one together using multiple extensions.  That model
> has its own set of risks and tradeoffs.

I thought that you are not using the "where does the series of
extensions begin" information in the first place, no?  That piece of
information is useful independent of the usefulness of "index into
the main table to list entries where the prefix-compression is
reset".  So if anything, I'd prefer the simplicity of introducing
that "where does the series of extensions begin" that does not say
anything else, and build on other things like ITOC as mere users of
the mechanism.

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Ben Peart]

On 11/14/2017 8:12 PM, Junio C Hamano wrote:
> Ben Peart <peartben@gmail.com> writes:
> 
>> I have no thoughts or plans for changes in the future of IEOT (which I
>> plan to rename ITOC).  At this point in time, I can't even imagine
>> what else we'd want as the index only contains cache entries, ...
> 
> Yeah, but the thing is that this is open source, and the imagination
> of the originator of the initial idea does not limit how the code
> and data structure evolves.
> 
> Back when I added the index extensions to the system, I didn't have
> perfect foresight, and I didn't have specific plans to add anything
> beyond "TREE" to optimize "write-tree" and "diff-index --cached".
> 
> In hindsight, I got one thing right and one thing wrong.
> 
> Even though I didn't have any plan to add a mandatory extension, I
> made the code to ignore optional ones and error out on mandatory
> ones if an index extension section is not understood.  It turns out
> that later (in fact much later---the "TREE" extension dates back to
> April 2006, while "link" came in June 2014) we could add the
> split-index mode without having to worry about older versions of Git
> doing random wrong things when they see this new extension, thanks
> to that design decision.  That went well.
> 
> On the other hand, I didn't think things through to realize that
> some operations may want to peek only the extensions without ever
> using the main table, that some other operations may want to read
> some extensions first before reading the main table, or more
> importantly, that these limitations would start mattering once Git
> becomes popular enough and starts housing a project tree with very
> many paths in the main table.
> 
> I really wish somebody had brought it up as a potential issue during
> the review---I would have defined the extended index format to have
> the simple extension at the end that points back to the tail end of
> the main table back then, and we wouldn't be having this back and
> forth now.  But I was just too happy and excited that I have found a
> room to squeeze extension sections into the index file format
> without breaking existing implementations of Git (which checked the
> trailer checksum matches to the result of hashing the whole thing,
> and read the recorded number of entries from the main table, without
> even noticing that there is a gap in between), and that excitement
> blinded me.
> 
>> I understand the risk but the list of offsets into the cache entries
>> is pretty simple as well. I prefer the simplicity of a single TOC
>> extension that gives us random access to the entire index rather than
>> having to piece one together using multiple extensions.  That model
>> has its own set of risks and tradeoffs.
> 
> I thought that you are not using the "where does the series of
> extensions begin" information in the first place, no?  That piece of
> information is useful independent of the usefulness of "index into
> the main table to list entries where the prefix-compression is
> reset".  So if anything, I'd prefer the simplicity of introducing
> that "where does the series of extensions begin" that does not say
> anything else, and build on other things like ITOC as mere users of
> the mechanism.
> 

OK.  I'll call this new extension "EOIE" ("end of index entries"). Other 
than the standard header/footer, it will only contain a 32 bit offset to 
the beginning of the extension entries.  I'll always write out that 
extension unless you would prefer it be behind a setting (if so, what do 
you want it called and what should the default be)?  I won't add support 
in update-index for this extension.

Since the goal was to find a way to load the IEOT extension before the 
cache entries, I'll also refactor the extension reading loop into a 
function that takes a function pointer and add a 
preread_index_extension() function that can be passed in when that loop 
is run before the cache entries are loaded.  When the loop is run again 
after the cache entries are loaded, it will pass in the existing 
read_index_extension() function.  Extensions can then choose which 
function they want to be loaded in.

The code to read/write/use the IEOT to parallelize the cache entry 
loading will stay behind a config setting that defaults to false (at 
least for now).  I'll stick with "core.fastindex" until someone can 
(please) propose a better name.

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Junio C Hamano]

Ben Peart <peartben@gmail.com> writes:

> OK.  I'll call this new extension "EOIE" ("end of index
> entries"). Other than the standard header/footer, it will only contain
> a 32 bit offset to the beginning of the extension entries.  I'll
> always write out that extension unless you would prefer it be behind a
> setting (if so, what do you want it called and what should the default
> be)?  I won't add support in update-index for this extension.

To make it robust, if I were doing this, I would at least add a checksum
of some sort.  

As each extension section consists of 4-byte extension type, 4-byte
size, followed by that many bytes of the "meat" of the section, what
I had in mind when I suggested this backpointer was something like:

    "EOIE" <32-bit size> <32-bit offset> <20-byte hash>

where the size of the extension section is obviously 24-byte to
cover the offset plus hash, and the hash is computed over extension
types and their sizes (but not their contents---this is not about
protecting against file corruption and not worth wasting the cycles
for hashing) for all the extension sections this index file has
(except for "EOIE" at the end, for obvious reasons).  E.g. if we
have "TREE" extension that is N-bytes long, "REUC" extension that is
M-bytes long, followed by "EOIE", then the hash would be

	SHA-1("TREE" + <binary representation of N> +
	      "REUC" + <binary representation of M>)

Then the reader would

 - Seek back 32-byte from the trailer to ensure it sees "EOIE"
   followed by a correct size (24?)

 - Jump to the offset and find 4-bytes that presumably is the type
   of the first extension, followed by its size.  

 - Feed these 8-bytes to the hash, skip that section based on its
   size (while making sure we won't run off the end of the file,
   which is a sign that we thought EOIE exists when there wasn't).
   Repeat this until we hit where we found "EOIE" (or we notice our
   mistake by overrunning it).

 - Check the hash to make sure we got it right.

> Since the goal was to find a way to load the IEOT extension before the
> cache entries, I'll also refactor the extension reading loop into a
> function that takes a function pointer and add a
> preread_index_extension() function that can be passed in when that
> loop is run before the cache entries are loaded.  When the loop is run
> again after the cache entries are loaded, it will pass in the existing
> read_index_extension() function.  Extensions can then choose which
> function they want to be loaded in.
>
> The code to read/write/use the IEOT to parallelize the cache entry
> loading will stay behind a config setting that defaults to false (at
> least for now).  I'll stick with "core.fastindex" until someone can
> (please) propose a better name.

Sounds good.

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Ben Peart]

Further testing has revealed that switching from the regular heap to a 
refactored version of the mem_pool in fast-import.c produces similar 
gains as parallelizing do_index_load().  This appears to be a much 
simpler patch for similar gains so we will be pursuing that path.

Combining the two patches resulted in a further 25% reduction of 
do_index_load() but with index load times getting smaller, that only 
resulted in a 3% improvement in total git command time.  Given the 
greater complexity of this patch, we've decided to put it on hold for 
now.  We'll keep it in our back pocket in case we need it in the future.

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Jeff King]

On Mon, Nov 20, 2017 at 09:01:45AM -0500, Ben Peart wrote:

> Further testing has revealed that switching from the regular heap to a
> refactored version of the mem_pool in fast-import.c produces similar gains
> as parallelizing do_index_load().  This appears to be a much simpler patch
> for similar gains so we will be pursuing that path.

That sounds like a pretty easy win for index entries, which tend to
stick around in big clumps.

Out of curiosity, have you tried experimenting with any high-performance
3rd-party allocator libraries? I've often wondered if we could get a
performance improvement from dropping in a new allocator, but was never
able to measure any real benefit over glibc's ptmalloc2. The situation
might be different on Windows, though (i.e., if the libc allocator isn't
that great).

Most of the high-performance allocators are focused on concurrency,
which usually isn't a big deal for git. But tcmalloc, at least, claims
to be about 6x faster than glibc.

The reason I ask is that we could possibly get the same wins without
writing a single line of code. And it could apply across the whole
code-base, not just the index code. I don't know how close a general
purpose allocator could come to a pooled implementation, though. You're
inherently making a tradeoff with a pool in not being able to free
individual entries.

-Peff

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Jeff King]

On Mon, Nov 20, 2017 at 09:20:35AM -0500, Jeff King wrote:

> Out of curiosity, have you tried experimenting with any high-performance
> 3rd-party allocator libraries? I've often wondered if we could get a
> performance improvement from dropping in a new allocator, but was never
> able to measure any real benefit over glibc's ptmalloc2. The situation
> might be different on Windows, though (i.e., if the libc allocator isn't
> that great).

Just linking with tcmalloc, like:

diff --git a/Makefile b/Makefile
index ee9d5eb11e..4f299cd914 100644
--- a/Makefile
+++ b/Makefile
@@ -1018,7 +1018,7 @@ BUILTIN_OBJS += builtin/worktree.o
 BUILTIN_OBJS += builtin/write-tree.o
 
 GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB)
-EXTLIBS =
+EXTLIBS = -ltcmalloc
 
 GIT_USER_AGENT = git/$(GIT_VERSION)
 

seems to consistently show about 30% speedup on p0002:

Test                                          HEAD^             HEAD                  
--------------------------------------------------------------------------------------
0002.1: read_cache/discard_cache 1000 times   0.19(0.18+0.01)   0.13(0.12+0.01) -31.6%

I don't think we really even need a patch for it. You should be able to
just build with:

  make EXT_LIBS=-ltcmalloc

I can't think of any real advantage to a Makefile knob except
discoverability.

-Peff

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Ramsay Jones]

On 20/11/17 14:01, Ben Peart wrote:
> Further testing has revealed that switching from the regular heap to a refactored version of the mem_pool in fast-import.c produces similar gains as parallelizing do_index_load().  This appears to be a much simpler patch for similar gains so we will be pursuing that path.
> 
> Combining the two patches resulted in a further 25% reduction of do_index_load() but with index load times getting smaller, that only resulted in a 3% improvement in total git command time.  Given the greater complexity of this patch, we've decided to put it on hold for now.  We'll keep it in our back pocket in case we need it in the future.

Since you are withdrawing the 'bp/fastindex' branch, I won't send the
patch to fix up the sparse warnings (unless you would like to see it
before you put it in your back pocket). ;-)

ATB,
Ramsay Jones

Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

[Ben Peart]

On 11/20/2017 6:51 PM, Ramsay Jones wrote:
> 
> 
> On 20/11/17 14:01, Ben Peart wrote:
>> Further testing has revealed that switching from the regular heap to a refactored version of the mem_pool in fast-import.c produces similar gains as parallelizing do_index_load().  This appears to be a much simpler patch for similar gains so we will be pursuing that path.
>>
>> Combining the two patches resulted in a further 25% reduction of do_index_load() but with index load times getting smaller, that only resulted in a 3% improvement in total git command time.  Given the greater complexity of this patch, we've decided to put it on hold for now.  We'll keep it in our back pocket in case we need it in the future.
> 
> Since you are withdrawing the 'bp/fastindex' branch, I won't send the
> patch to fix up the sparse warnings (unless you would like to see it
> before you put it in your back pocket). ;-)
> 
> ATB,
> Ramsay Jones
> 
> 

I'm happy to take your patches as I am keeping a copy just in case we 
need to revisit it.

I'm actually interested to see how Peff's suggestion to use tcmalloc 
helps because nearly 90% of the remaining execution time was spent 
waiting for a lock in malloc due to all contention from the multi-threading.