{"thread":{"id":"47145","subject":"[PATCH v1 0/4] Speed up index load through parallelization","startedAt":"2017-11-09T14:18:10Z","lastAt":"2017-11-21T00:45:16Z","messageCount":19,"participants":["Ben Peart","Junio C Hamano","Jeff King","Ramsay Jones"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"332118","messageId":"20171109141737.47976-1-benpeart@microsoft.com","threadId":"47145","inReplyTo":null,"subject":"[PATCH v1 0/4] Speed up index load through parallelization","fromName":"Ben Peart","fromEmail":"benpeart@microsoft.com","sentAt":"2017-11-09T14:17:33Z","receivedAt":"2017-11-09T14:18:10Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"This patch will help address the CPU cost of loading the index by adding\na table of contents extension to the index that will allow us to\nmulti-thread the loading and conversion of cache entries from the on-disk\nformat, to the in-memory format.  This is particularly beneficial\nwith large indexes and V4 indexes which have more CPU cost due to the\nprefix-encoding.\n\nI wanted to get feedback on the concept as the way I'm adding the table\nof contents information via an extension that can be read before the\nvariable length section of cache entries and other extensions is a bit\nof a clever hack (see below) as is the resetting of the prefix encoding\nfor V4 indexes. Both, however, are entirely backwards compatible with\nolder versions of git which can still properly read and use the index.\n\nI'm not particularly fond of the names \"fastindex\" and \"IEOT.\" I've\nwondered if \"indextoc\" and \"Index Table of Contents (ITOC)\" would be\nbetter names but I'm open to suggestions.\n\nAs there is overhead to spinning up a thread, there is logic to only\ndo the index loading in parallel when there are enough entries for it\nto help (currently set at 7,500 per thread with a minimum of 2 threads).\n\nThe impact of the change can be seen using t/helper/test-read-cache:\n\n                                fastindex\ntest            count   files   TRUE    FALSE     Savings\n------------------------------------------------------------------------\ntest-read-cache 500     100K    6.39\t8.33      23.36%\ntest-read-cache 100     1M      12.49   18.68     33.12%\n\nThe on-disk format looks like this:\n\nIndex header\nCache entry 1\nCache entry 2\n.\n.\n.\nExtension 1\nExtension 2\n.\n.\nIndex Entry Offset Table Extension (must be written last!)\nIEOT signature bytes\n32-bit size\n32-bit version\n32-bit Cache Entry Offset 1\n32-bit Cache Entry count\n32-bit Cache Entry Offset 2\n32-bit Cache Entry count\n.\n.\n.\n32-bit version\n32-bit size\nIEOT signature bytes\nSHA1\n\nSigned-off-by: Ben Peart <benpeart@microsoft.com>\n\nBase Ref: master\nWeb-Diff: https://github.com/benpeart/git/commit/1146d38932\nCheckout: git fetch https://github.com/benpeart/git fastindex-v1 && git checkout 1146d38932\n\nBen Peart (4):\n  fastindex: speed up index load through parallelization\n  update-index: add fastindex support to update-index\n  fastindex: add test tools and a test script\n  fastindex: add documentation for the fastindex extension\n\n Documentation/config.txt                 |   8 +\n Documentation/git-update-index.txt       |  11 +\n Documentation/technical/index-format.txt |  26 +++\n Makefile                                 |   2 +\n builtin/update-index.c                   |  22 ++\n cache.h                                  |  25 +++\n config.c                                 |  20 ++\n config.h                                 |   1 +\n environment.c                            |   3 +\n read-cache.c                             | 343 +++++++++++++++++++++++++++++--\n t/helper/test-dump-fast-index.c          |  68 ++++++\n t/helper/test-fast-index.c               |  84 ++++++++\n t/t1800-fast-index.sh                    |  55 +++++\n 13 files changed, 647 insertions(+), 21 deletions(-)\n create mode 100644 t/helper/test-dump-fast-index.c\n create mode 100644 t/helper/test-fast-index.c\n create mode 100644 t/t1800-fast-index.sh\n\n\nbase-commit: 7668cbc60578f99a4c048f8f8f38787930b8147b\n-- \n2.15.0.windows.1\n\n\n"},{"id":"332119","messageId":"20171109141737.47976-2-benpeart@microsoft.com","threadId":"47145","inReplyTo":"20171109141737.47976-1-benpeart@microsoft.com","subject":"[PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Ben Peart","fromEmail":"benpeart@microsoft.com","sentAt":"2017-11-09T14:17:34Z","receivedAt":"2017-11-09T14:18:17Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"This patch helps address the CPU cost of loading the index by adding\nadditional data to the index that will allow us to multi-thread the\nloading and conversion of cache entries.\n\nIt accomplishes this by adding an (optional) index extension that is a\ntable of offsets to blocks of cache entries in the index file.  With\nversion 2, 3 or even 4 indexes, we can utilize the Index Entry Offset Table\n(IEOT) to parallelize the loading and conversion of the cache entries\nacross all available CPU cores.\n\nTo make this work for V4 indexes, when writing the index, it periodically\n\"resets\" the prefix-compression by encoding the current entry as if the\npath name for the previous entry is completely different and saves the\noffset of that entry in the IEOT.  Basically, with V4 indexes, it\ngenerates offsets into blocks of prefix-compressed entries.\n\nTo enable reading the IEOT extension before reading all the variable\nlength cache entries and other extensions, the IEOT is written last,\nright before the trailing SHA1.\n\nThe format of that extension has the signature bytes and size at the\nbeginning (like a normal extension) as well as at the end in reverse\norder to enable parsing the extension by seeking back from the end of\nthe file.\n\nDuring index load, read the index header then seek to the end of the\nindex, back up past the trailing SHA1 and look for the IEOT extension\nsignature bytes.  If they exist, read the 32-bit size and seek back to\nthe extension header and verify the leading header and size bits.  If\nthey all match, we can be assured we have a valid IEOT extension.\n\nIf the IEOT extension is available, create multiple threads to divide\nthe work of loading and converting the cache entries across all\navailable CPU cores.  Once the cache entries are loaded, the rest of the\nextensions can be loaded and processed normally (skipping the IEOT entry\nas it has already been processed).  If the IEOT extension is not\navailable then parsing the index will proceed as usual with a single thread.\n\nSigned-off-by: Ben Peart <benpeart@microsoft.com>\n---\n cache.h       |  25 +++++\n config.c      |  20 ++++\n config.h      |   1 +\n environment.c |   3 +\n read-cache.c  | 343 ++++++++++++++++++++++++++++++++++++++++++++++++++++++----\n 5 files changed, 371 insertions(+), 21 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex d74f00d8db..ea0c4b4b97 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -794,6 +794,7 @@ extern char *git_replace_ref_base;\n \n extern int fsync_object_files;\n extern int core_preload_index;\n+extern int core_fast_index;\n extern int core_apply_sparse_checkout;\n extern int precomposed_unicode;\n extern int protect_hfs;\n@@ -1942,4 +1943,28 @@ void sleep_millisec(int millisec);\n  */\n void safe_create_dir(const char *dir, int share);\n \n+\n+#ifndef NO_PTHREADS\n+struct index_entry_offset\n+{\n+\t/* starting byte offset into index file, count of index entries in this block */\n+\tint offset, nr;\n+};\n+\n+struct index_entry_offset_table\n+{\n+\tint nr;\n+\tstruct index_entry_offset entries[0];\n+};\n+\n+extern struct index_entry_offset_table *read_ieot_extension(void *mmap, size_t mmap_size);\n+\n+struct ondisk_cache_entry;\n+extern struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n+\tunsigned long *ent_size,\n+\tstruct strbuf *previous_name,\n+\tint use_length);\n+\n+#endif\n+\n #endif /* CACHE_H */\ndiff --git a/config.c b/config.c\nindex 903abf9533..44b08f57eb 100644\n--- a/config.c\n+++ b/config.c\n@@ -1203,6 +1203,11 @@ static int git_default_core_config(const char *var, const char *value)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.fastindex\")) {\n+\t\tcore_fast_index = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n+\n \tif (!strcmp(var, \"core.createobject\")) {\n \t\tif (!strcmp(value, \"rename\"))\n \t\t\tobject_creation_mode = OBJECT_CREATION_USES_RENAMES;\n@@ -2156,6 +2161,21 @@ int git_config_get_max_percent_split_change(void)\n \treturn -1; /* default value */\n }\n \n+int ignore_fast_index_config;\n+int git_config_get_fast_index(void)\n+{\n+\tint val;\n+\n+\t/* Hack for test programs like test-ieot */\n+\tif (ignore_fast_index_config)\n+\t\treturn core_fast_index;\n+\n+\tif (!git_config_get_maybe_bool(\"core.fastindex\", &val))\n+\t\treturn val;\n+\n+\treturn -1; /* default value */\n+}\n+\n NORETURN\n void git_die_config_linenr(const char *key, const char *filename, int linenr)\n {\ndiff --git a/config.h b/config.h\nindex a49d264416..3f78b1d262 100644\n--- a/config.h\n+++ b/config.h\n@@ -212,6 +212,7 @@ extern int git_config_get_pathname(const char *key, const char **dest);\n extern int git_config_get_untracked_cache(void);\n extern int git_config_get_split_index(void);\n extern int git_config_get_max_percent_split_change(void);\n+extern int git_config_get_fast_index(void);\n \n /* This dies if the configured or default date is in the future */\n extern int git_config_get_expiry(const char *key, const char **output);\ndiff --git a/environment.c b/environment.c\nindex 8289c25b44..492ef9c741 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -87,6 +87,9 @@ int auto_comment_line_char;\n /* Parallel index stat data preload? */\n int core_preload_index = 1;\n \n+/* Parallel index cache entry loading? */\n+int core_fast_index;\n+\n /*\n  * This is a hack for test programs like test-dump-untracked-cache to\n  * ensure that they do not modify the untracked cache when reading it.\ndiff --git a/read-cache.c b/read-cache.c\nindex f3d125c114..174be0da38 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -19,6 +19,7 @@\n #include \"varint.h\"\n #include \"split-index.h\"\n #include \"utf8.h\"\n+#include \"thread-utils.h\"\n \n /* Mask for the name length in ce_flags in the on-disk index */\n \n@@ -38,6 +39,7 @@\n #define CACHE_EXT_RESOLVE_UNDO 0x52455543 /* \"REUC\" */\n #define CACHE_EXT_LINK 0x6c696e6b\t  /* \"link\" */\n #define CACHE_EXT_UNTRACKED 0x554E5452\t  /* \"UNTR\" */\n+#define CACHE_EXT_FASTINDEX 0x49454F54\t  /* \"IEOT\" */\n \n /* changes that can be kept in $GIT_DIR/index (basically all extensions) */\n #define EXTMASK (RESOLVE_UNDO_CHANGED | CACHE_TREE_CHANGED | \\\n@@ -1551,6 +1553,9 @@ static int read_index_extension(struct index_state *istate,\n \tcase CACHE_EXT_UNTRACKED:\n \t\tistate->untracked = read_untracked_extension(data, sz);\n \t\tbreak;\n+\tcase CACHE_EXT_FASTINDEX:\n+\t\t/* already handled in do_read_index() */\n+\t\tbreak;\n \tdefault:\n \t\tif (*ext < 'A' || 'Z' < *ext)\n \t\t\treturn error(\"index uses %.4s extension, which we do not understand\",\n@@ -1604,10 +1609,12 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on\n  * number of bytes to be stripped from the end of the previous name,\n  * and the bytes to append to the result, to come up with its name.\n  */\n-static unsigned long expand_name_field(struct strbuf *name, const char *cp_)\n+static unsigned long expand_name_field(struct strbuf *name, const char *cp_, int use_length)\n {\n \tconst unsigned char *ep, *cp = (const unsigned char *)cp_;\n \tsize_t len = decode_varint(&cp);\n+\tif (!use_length)\n+\t\tlen = name->len;\n \n \tif (name->len < len)\n \t\tdie(\"malformed name field in the index\");\n@@ -1618,9 +1625,10 @@ static unsigned long expand_name_field(struct strbuf *name, const char *cp_)\n \treturn (const char *)ep + 1 - cp_;\n }\n \n-static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n+struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n \t\t\t\t\t    unsigned long *ent_size,\n-\t\t\t\t\t    struct strbuf *previous_name)\n+\t\t\t\t\t    struct strbuf *previous_name,\n+\t\t\t\t\t\tint use_length)\n {\n \tstruct cache_entry *ce;\n \tsize_t len;\n@@ -1654,7 +1662,7 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n \t\t*ent_size = ondisk_ce_size(ce);\n \t} else {\n \t\tunsigned long consumed;\n-\t\tconsumed = expand_name_field(previous_name, name);\n+\t\tconsumed = expand_name_field(previous_name, name, use_length);\n \t\tce = cache_entry_from_ondisk(ondisk, flags,\n \t\t\t\t\t     previous_name->buf,\n \t\t\t\t\t     previous_name->len);\n@@ -1725,16 +1733,208 @@ static void post_read_index_from(struct index_state *istate)\n \ttweak_split_index(istate);\n }\n \n+static unsigned long load_cache_entries(struct index_state *istate, int offset, int nr, void *mmap, unsigned long start_offset)\n+{\n+\tint i;\n+\tunsigned long src_offset = start_offset;\n+\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n+\n+\tif (istate->version == 4)\n+\t\tprevious_name = &previous_name_buf;\n+\telse\n+\t\tprevious_name = NULL;\n+\n+\tfor (i = offset; i < offset + nr; i++) {\n+\t\tstruct ondisk_cache_entry *disk_ce;\n+\t\tstruct cache_entry *ce;\n+\t\tunsigned long consumed;\n+\n+\t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);\n+\t\tce = create_from_disk(disk_ce, &consumed, previous_name, i == offset ? 0 : 1);\n+\t\tset_index_entry(istate, i, ce);\n+\n+\t\tsrc_offset += consumed;\n+\t}\n+\tstrbuf_release(&previous_name_buf);\n+\treturn src_offset - start_offset;\n+}\n+\n+#ifndef NO_PTHREADS\n+\n+/*\n+ * Mostly randomly chosen cache entries per thread (it works on my machine):\n+ * we want to have at least 7500 cache entries per thread for it to\n+ * be worth starting a thread.\n+ */\n+#define THREAD_COST\t\t(7500)\n+#define IEOT_VERSION\t(1)\n+\n+static int ce_write(git_SHA_CTX *context, int fd, void *data, unsigned int len);\n+\n+static int write_index_ext_header(git_SHA_CTX *context, int fd,\n+\tunsigned int ext, unsigned int sz);\n+\n+struct load_cache_entries_thread_data\n+{\n+\tpthread_t pthread;\n+\tstruct index_state *istate;\n+\tint offset;\t\t\t/* starting index into the istate->cache array */\n+\tvoid *mmap;\n+\tunsigned long consumed;\t/* return # of bytes in index file processed */\n+\tstruct index_entry_offset_table *ieot;\n+\tint ieot_offset;\t/* starting index into the ieot array */\n+\tint ieot_work;\t\t/* count of ieot entries to process */\n+};\n+\n+/*\n+ * A thread proc to run the load_cache_entries() computation\n+ * across multiple background threads.\n+ */\n+static void *load_cache_entries_thread(void *_data)\n+{\n+\tstruct load_cache_entries_thread_data *p = _data;\n+\tint i;\n+\n+\t/* itterate across all ieot blocks assigned to this thread */\n+\tfor (i = p->ieot_offset; i < p->ieot_offset + p->ieot_work; i++) {\n+\t\tp->consumed += load_cache_entries(p->istate, p->offset, p->ieot->entries[i].nr, p->mmap, p->ieot->entries[i].offset);\n+\t\tp->offset += p->ieot->entries[i].nr;\n+\t}\n+\treturn NULL;\n+}\n+\n+struct index_entry_offset_table *read_ieot_extension(void *mmap, size_t mmap_size)\n+{\n+\t/*\n+\t * The IEOT extension is guaranteed to be last so that it can be found\n+\t * by scanning backwards from the EOF.  In addition to the regular 4-byte\n+\t * extension name and 4-byte section length is network byte order, it\n+\t * also stores the 4-byte extension name and section length in reverse order\n+\t * at the end of the extension.\n+\t *\n+\t * IEOT\n+\t * 4-byte length\n+\t * 4-byte version\n+\t * variable length extension data...\n+\t * 4-byte version\n+\t * 4-byte length\n+\t * IEOT\n+\t * <SHA1>\n+\t *\n+\t * If names, lengths and versions match, the extension is assumed to be valid.\n+\t */\n+\tconst char *index;\n+\tuint32_t extsize_leading, extsize_trailing, ext_version;\n+\tstruct index_entry_offset_table *ieot;\n+\tint i, nr;\n+\n+\t/* validate the trailing extension signature */\n+\tindex = (const char *)mmap + mmap_size - GIT_SHA1_RAWSZ - 4;\n+\tif (CACHE_EXT(index) != CACHE_EXT_FASTINDEX)\n+\t\treturn NULL;\n+\tindex -= sizeof(uint32_t);\n+\n+\t/*\n+\t * Validate the offset we're going to look for the leading extension\n+\t * signature is past the index header.\n+\t */\n+\textsize_trailing = get_be32(index);\n+\tif ((index - extsize_trailing) < ((const char *)mmap + 12))\n+\t\treturn NULL;\n+\tindex -= sizeof(uint32_t);\n+\n+\t/* validate the trailing version is IEOT_VERSION */\n+\text_version = get_be32(index);\n+\tif (ext_version != IEOT_VERSION)\n+\t\treturn NULL;\n+\tindex -= (extsize_trailing - sizeof(uint32_t));\n+\n+\t/* validate the leading extension signature */\n+\tif (CACHE_EXT(index) != CACHE_EXT_FASTINDEX)\n+\t\treturn NULL;\n+\tindex += sizeof(uint32_t);\n+\n+\t/* validate the leading extension size */\n+\textsize_leading = get_be32(index);\n+\tif (extsize_leading != extsize_trailing)\n+\t\treturn NULL;\n+\tindex += sizeof(uint32_t);\n+\n+\t/* validate the leading version is IEOT_VERSION */\n+\text_version = get_be32(index);\n+\tif (ext_version != IEOT_VERSION)\n+\t\treturn NULL;\n+\tindex += sizeof(uint32_t);\n+\n+\t/* extension size - leading/trailing version bytes - trailing size - trailing signature / bytes per entry */\n+\tnr = (extsize_leading - sizeof(uint32_t) - sizeof(uint32_t) - sizeof(uint32_t) - 4) / (sizeof(uint32_t) + sizeof(uint32_t));\n+\tassert(nr);\n+\tieot = xmalloc(sizeof(struct index_entry_offset_table)\n+\t\t+ (nr * sizeof(struct index_entry_offset)));\n+\tieot->nr = nr;\n+\tfor (i = 0; i < nr; i++) {\n+\t\tieot->entries[i].offset = get_be32(index);\n+\t\tindex += sizeof(uint32_t);\n+\t\tieot->entries[i].nr = get_be32(index);\n+\t\tindex += sizeof(uint32_t);\n+\t}\n+\n+\treturn ieot;\n+}\n+\n+static int write_ieot_extension(git_SHA_CTX *context, int fd, struct index_entry_offset_table *ieot)\n+{\n+\tstruct strbuf sb = STRBUF_INIT;\n+\tuint32_t buffer;\n+\tint i, err;\n+\n+\t/* version */\n+\tput_be32(&buffer, IEOT_VERSION);\n+\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n+\n+\t/* ieot */\n+\tfor (i = 0; i < ieot->nr; i++) {\n+\n+\t\t/* offset */\n+\t\tput_be32(&buffer, ieot->entries[i].offset);\n+\t\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n+\n+\t\t/* count */\n+\t\tput_be32(&buffer, ieot->entries[i].nr);\n+\t\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n+\t}\n+\n+\t/* version */\n+\tput_be32(&buffer, IEOT_VERSION);\n+\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n+\n+\t/* size */\n+\tput_be32(&buffer, sb.len + sizeof(uint32_t) + 4);\n+\tstrbuf_add(&sb, &buffer, sizeof(uint32_t));\n+\n+\t/* signature */\n+\tput_be32(&buffer, CACHE_EXT_FASTINDEX);\n+\tstrbuf_add(&sb, &buffer, 4);\n+\n+\t/* leading signature and size + extension data */\n+\terr = write_index_ext_header(context, fd, CACHE_EXT_FASTINDEX, sb.len) < 0\n+\t\t|| ce_write(context, fd, sb.buf, sb.len) < 0;\n+\tstrbuf_release(&sb);\n+\n+\treturn err;\n+}\n+\n+#endif\n+\n /* remember to discard_cache() before reading a different cache! */\n int do_read_index(struct index_state *istate, const char *path, int must_exist)\n {\n-\tint fd, i;\n+\tint fd;\n \tstruct stat st;\n \tunsigned long src_offset;\n \tstruct cache_header *hdr;\n \tvoid *mmap;\n \tsize_t mmap_size;\n-\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n \n \tif (istate->initialized)\n \t\treturn istate->cache_nr;\n@@ -1771,24 +1971,75 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist)\n \tistate->cache = xcalloc(istate->cache_alloc, sizeof(*istate->cache));\n \tistate->initialized = 1;\n \n-\tif (istate->version == 4)\n-\t\tprevious_name = &previous_name_buf;\n-\telse\n-\t\tprevious_name = NULL;\n-\n \tsrc_offset = sizeof(*hdr);\n-\tfor (i = 0; i < istate->cache_nr; i++) {\n-\t\tstruct ondisk_cache_entry *disk_ce;\n-\t\tstruct cache_entry *ce;\n-\t\tunsigned long consumed;\n+#ifdef NO_PTHREADS\n+\tsrc_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);\n+#else\n+\tif (git_config_get_fast_index() != 1) {\n+\t\tsrc_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);\n+\t} else {\n+\t\tstruct index_entry_offset_table *ieot;\n+\t\tint threads, cpus = online_cpus();\n \n-\t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);\n-\t\tce = create_from_disk(disk_ce, &consumed, previous_name);\n-\t\tset_index_entry(istate, i, ce);\n+\t\tthreads = istate->cache_nr / THREAD_COST;\n+\t\tif (threads > cpus)\n+\t\t\tthreads = cpus;\n \n-\t\tsrc_offset += consumed;\n+\t\t/* enable testing with fewer than default minimum of entries */\n+\t\tif (threads < 2 && getenv(\"GIT_FASTINDEX_TEST\"))\n+\t\t\tthreads = 2;\n+\n+\t\t/*\n+\t\t * Locate and read the fast index extension so that we can use it\n+\t\t * to multi-thread the reading of the cache entries.\n+\t\t */\n+\t\tieot = read_ieot_extension(mmap, mmap_size);\n+\t\tif (threads < 2 || !ieot) {\n+\t\t\tsrc_offset += load_cache_entries(istate, 0, istate->cache_nr, mmap, src_offset);\n+\t\t} else {\n+\t\t\tint i, offset, ieot_work, ieot_offset;\n+\t\t\tstruct load_cache_entries_thread_data *data;\n+\n+\t\t\t/* ensure we have no more threads than we have blocks to process */\n+\t\t\tif (threads > ieot->nr)\n+\t\t\t\tthreads = ieot->nr;\n+\t\t\tdata = xcalloc(threads, sizeof(struct load_cache_entries_thread_data));\n+\n+\t\t\toffset = ieot_offset = 0;\n+\t\t\tieot_work = DIV_ROUND_UP(ieot->nr, threads);\n+\t\t\tfor (i = 0; i < threads; i++) {\n+\t\t\t\tstruct load_cache_entries_thread_data *p = &data[i];\n+\t\t\t\tint j;\n+\n+\t\t\t\tif (ieot_offset + ieot_work > ieot->nr)\n+\t\t\t\t\tieot_work = ieot->nr - ieot_offset;\n+\n+\t\t\t\tp->istate = istate;\n+\t\t\t\tp->offset = offset;\n+\t\t\t\tp->mmap = mmap;\n+\t\t\t\tp->ieot = ieot;\n+\t\t\t\tp->ieot_offset = ieot_offset;\n+\t\t\t\tp->ieot_work = ieot_work;\n+\t\t\t\tif (pthread_create(&p->pthread, NULL, load_cache_entries_thread, p))\n+\t\t\t\t\tdie(\"unable to create threaded load_cache_entries\");\n+\n+\t\t\t\t/* increment by the number of cache entries in the ieot block being processed */\n+\t\t\t\tfor (j = 0; j < ieot_work; j++)\n+\t\t\t\t\toffset += ieot->entries[ieot_offset + j].nr;\n+\t\t\t\tieot_offset += ieot_work;\n+\t\t\t}\n+\t\t\tfor (i = 0; i < threads; i++) {\n+\t\t\t\tstruct load_cache_entries_thread_data *p = data + i;\n+\t\t\t\tif (pthread_join(p->pthread, NULL))\n+\t\t\t\t\tdie(\"unable to join threaded load_cache_entries\");\n+\t\t\t\tsrc_offset += p->consumed;\n+\t\t\t}\n+\t\t\tfree(data);\n+\t\t}\n+\t\tfree(ieot);\n \t}\n-\tstrbuf_release(&previous_name_buf);\n+#endif\n+\n \tistate->timestamp.sec = st.st_mtime;\n \tistate->timestamp.nsec = ST_MTIME_NSEC(st);\n \n@@ -2205,6 +2456,9 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \tstruct ondisk_cache_entry_extended ondisk;\n \tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n \tint drop_cache_tree = 0;\n+\tint ieot_work = 1;\n+\tstruct index_entry_offset_table *ieot = NULL;\n+\tint offset, nr;\n \n \tfor (i = removed = extended = 0; i < entries; i++) {\n \t\tif (cache[i]->ce_flags & CE_REMOVE)\n@@ -2238,6 +2492,22 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \tif (ce_write(&c, newfd, &hdr, sizeof(hdr)) < 0)\n \t\treturn -1;\n \n+\tif (!strip_extensions && core_fast_index) {\n+\t\tint ieot_blocks, cpus = online_cpus();\n+\n+\t\tieot_blocks = istate->cache_nr / THREAD_COST;\n+\t\tif (ieot_blocks < 1)\n+\t\t\tieot_blocks = 1;\n+\t\tif (ieot_blocks > cpus)\n+\t\t\tieot_blocks = cpus;\n+\t\tieot = xcalloc(1, sizeof(struct index_entry_offset_table)\n+\t\t\t+ (ieot_blocks * sizeof(struct index_entry_offset)));\n+\t\tieot->nr = 0;\n+\t\tieot_work = DIV_ROUND_UP(entries, ieot_blocks);\n+\t}\n+\n+\toffset = lseek(newfd, 0, SEEK_CUR) + write_buffer_len;\n+\tnr = 0;\n \tprevious_name = (hdr_version == 4) ? &previous_name_buf : NULL;\n \n \tfor (i = 0; i < entries; i++) {\n@@ -2259,11 +2529,30 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \n \t\t\tdrop_cache_tree = 1;\n \t\t}\n+\t\tif (ieot && i && (i % ieot_work == 0)) {\n+\t\t\tieot->entries[ieot->nr].nr = nr;\n+\t\t\tieot->entries[ieot->nr].offset = offset;\n+\t\t\tieot->nr++;\n+\t\t\t/*\n+\t\t\t * If we have a V4 index, set the first byte to an invalid\n+\t\t\t * character to ensure there is nothing common with the previous\n+\t\t\t * entry\n+\t\t\t */\n+\t\t\tif (previous_name)\n+\t\t\t\tprevious_name->buf[0] = 0;\n+\t\t\tnr = 0;\n+\t\t\toffset = lseek(newfd, 0, SEEK_CUR) + write_buffer_len;\n+\t\t}\n \t\tif (ce_write_entry(&c, newfd, ce, previous_name, (struct ondisk_cache_entry *)&ondisk) < 0)\n \t\t\terr = -1;\n-\n \t\tif (err)\n \t\t\tbreak;\n+\t\tnr++;\n+\t}\n+\tif (ieot && nr) {\n+\t\tieot->entries[ieot->nr].nr = nr;\n+\t\tieot->entries[ieot->nr].offset = offset;\n+\t\tieot->nr++;\n \t}\n \tstrbuf_release(&previous_name_buf);\n \n@@ -2315,6 +2604,18 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \t\t\treturn -1;\n \t}\n \n+\t/*\n+\t * CACHE_EXT_FASTINDEX must be written as the last entry before the SHA1\n+\t * so that it can be found and processed before all the index entries are\n+\t * read.\n+\t */\n+\tif (!strip_extensions && ieot) {\n+\t\terr = write_ieot_extension(&c, newfd, ieot);\n+\t\tfree(ieot);\n+\t\tif (err)\n+\t\t\treturn -1;\n+\t}\n+\n \tif (ce_flush(&c, newfd, istate->sha1))\n \t\treturn -1;\n \tif (close_tempfile_gently(tempfile)) {\n-- \n2.15.0.windows.1\n\n"},{"id":"332120","messageId":"20171109141737.47976-3-benpeart@microsoft.com","threadId":"47145","inReplyTo":"20171109141737.47976-1-benpeart@microsoft.com","subject":"[PATCH v1 2/4] update-index: add fastindex support to update-index","fromName":"Ben Peart","fromEmail":"benpeart@microsoft.com","sentAt":"2017-11-09T14:17:35Z","receivedAt":"2017-11-09T14:18:21Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"Add support in update-index to manually add/remove the fastindex\nextension via --[no-]fastindex flags.\n\nSigned-off-by: Ben Peart <benpeart@microsoft.com>\n---\n builtin/update-index.c | 22 ++++++++++++++++++++++\n 1 file changed, 22 insertions(+)\n\ndiff --git a/builtin/update-index.c b/builtin/update-index.c\nindex fefbe60167..63b7f18807 100644\n--- a/builtin/update-index.c\n+++ b/builtin/update-index.c\n@@ -917,6 +917,7 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)\n \tstruct refresh_params refresh_args = {0, &has_errors};\n \tint lock_error = 0;\n \tint split_index = -1;\n+\tint fast_index = -1;\n \tstruct lock_file lock_file = LOCK_INIT;\n \tstruct parse_opt_ctx_t ctx;\n \tstrbuf_getline_fn getline_fn;\n@@ -1008,6 +1009,8 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)\n \t\t\t    N_(\"test if the filesystem supports untracked cache\"), UC_TEST),\n \t\tOPT_SET_INT(0, \"force-untracked-cache\", &untracked_cache,\n \t\t\t    N_(\"enable untracked cache without testing the filesystem\"), UC_FORCE),\n+\t\tOPT_BOOL(0, \"fastindex\", &fast_index,\n+\t\t\tN_(\"enable or disable fast index parsing\")),\n \t\tOPT_END()\n \t};\n \n@@ -1146,6 +1149,25 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)\n \t\tdie(\"BUG: bad untracked_cache value: %d\", untracked_cache);\n \t}\n \n+\tif (fast_index > 0) {\n+\t\tif (git_config_get_fast_index() == 0)\n+\t\t\twarning(_(\"core.fastindex is unset; \"\n+\t\t\t\t\"set it if you really want to \"\n+\t\t\t\t\"enable fastindex\"));\n+\t\tcore_fast_index = 1;\n+\t\tactive_cache_changed |= SOMETHING_CHANGED;\n+\t\treport(_(\"fastindex enabled\"));\n+\t}\n+\telse if (!fast_index) {\n+\t\tif (git_config_get_fast_index() == 1)\n+\t\t\twarning(_(\"core.fastindex is set; \"\n+\t\t\t\t\"remove it if you really want to \"\n+\t\t\t\t\"disable fastindex\"));\n+\t\tcore_fast_index = 0;\n+\t\tactive_cache_changed |= SOMETHING_CHANGED;\n+\t\treport(_(\"fastindex disabled\"));\n+\t}\n+\n \tif (active_cache_changed) {\n \t\tif (newfd < 0) {\n \t\t\tif (refresh_args.flags & REFRESH_QUIET)\n-- \n2.15.0.windows.1\n\n"},{"id":"332121","messageId":"20171109141737.47976-4-benpeart@microsoft.com","threadId":"47145","inReplyTo":"20171109141737.47976-1-benpeart@microsoft.com","subject":"[PATCH v1 3/4] fastindex: add test tools and a test script","fromName":"Ben Peart","fromEmail":"benpeart@microsoft.com","sentAt":"2017-11-09T14:17:36Z","receivedAt":"2017-11-09T14:18:23Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"Add a test utility (test-dump-fast-index) that dumps the contents of the\nIEOT to stdout.  This enables checking the existance of the extension\nand the ability to parse and output its contents.\n\nAdd a test utility (test-fast-index) that loads the index using the\nfastindex logic then loads it using the regular logic and compares the\nresults of the two.  Any differences are reported and an error is returned.\n\nAdd a test script (t1800-fast-index.sh) to:\n\nTest the ability to add/remove the fastindex index extension via\nupdate-index.\n\nVerify that loading the index with and without the fastindex extension\nreturn the same results with both V2 and V4 indexes.\n\nSigned-off-by: Ben Peart <benpeart@microsoft.com>\n---\n Makefile                        |  2 +\n t/helper/test-dump-fast-index.c | 68 +++++++++++++++++++++++++++++++++\n t/helper/test-fast-index.c      | 84 +++++++++++++++++++++++++++++++++++++++++\n t/t1800-fast-index.sh           | 55 +++++++++++++++++++++++++++\n 4 files changed, 209 insertions(+)\n create mode 100644 t/helper/test-dump-fast-index.c\n create mode 100644 t/helper/test-fast-index.c\n create mode 100644 t/t1800-fast-index.sh\n\ndiff --git a/Makefile b/Makefile\nindex cd75985991..a7df82721e 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -647,9 +647,11 @@ TEST_PROGRAMS_NEED_X += test-config\n TEST_PROGRAMS_NEED_X += test-date\n TEST_PROGRAMS_NEED_X += test-delta\n TEST_PROGRAMS_NEED_X += test-dump-cache-tree\n+TEST_PROGRAMS_NEED_X += test-dump-fast-index\n TEST_PROGRAMS_NEED_X += test-dump-split-index\n TEST_PROGRAMS_NEED_X += test-dump-untracked-cache\n TEST_PROGRAMS_NEED_X += test-fake-ssh\n+TEST_PROGRAMS_NEED_X += test-fast-index\n TEST_PROGRAMS_NEED_X += test-genrandom\n TEST_PROGRAMS_NEED_X += test-hashmap\n TEST_PROGRAMS_NEED_X += test-index-version\ndiff --git a/t/helper/test-dump-fast-index.c b/t/helper/test-dump-fast-index.c\nnew file mode 100644\nindex 0000000000..4e6d28d660\n--- /dev/null\n+++ b/t/helper/test-dump-fast-index.c\n@@ -0,0 +1,68 @@\n+#include \"cache.h\"\n+\n+int cmd_main(int ac, const char **av)\n+{\n+#ifndef NO_PTHREADS\n+\tconst char *path;\n+\tint fd, i;\n+\tstruct stat st;\n+\tvoid *mmap;\n+\tsize_t mmap_size;\n+\tstruct cache_header *hdr;\n+\tstruct index_entry_offset_table *ieot;\n+\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n+\tint err = 0;\n+\n+\tsetup_git_directory();\n+\tpath = get_index_file();\n+\tfd = open(path, O_RDONLY);\n+\tif (fd < 0) {\n+\t\tdie(\"%s: index file open failed\", path);\n+\t}\n+\n+\tif (fstat(fd, &st))\n+\t\tdie(\"cannot stat the open index\");\n+\n+\tmmap_size = xsize_t(st.st_size);\n+\tif (mmap_size < sizeof(struct cache_header) + GIT_SHA1_RAWSZ)\n+\t\tdie(\"index file smaller than expected\");\n+\n+\tmmap = xmmap(NULL, mmap_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tif (mmap == MAP_FAILED)\n+\t\tdie(\"unable to map index file\");\n+\tclose(fd);\n+\n+\thdr = mmap;\n+\tif (ntohl(hdr->hdr_version) == 4)\n+\t\tprevious_name = &previous_name_buf;\n+\telse\n+\t\tprevious_name = NULL;\n+\n+\tieot = read_ieot_extension(mmap, mmap_size);\n+\tif (ieot) {\n+\t\tprintf(\"IEOT with %d entries\\n\", ieot->nr);\n+\t\tprintf(\"  Offset    Count Name\\n\");\n+\t\tprintf(\"-------- -------- ------------------------\\n\");\n+\t\tfor (i = 0; i < ieot->nr; i++) {\n+\t\t\tstruct ondisk_cache_entry *disk_ce;\n+\t\t\tstruct cache_entry *ce;\n+\t\t\tunsigned long consumed;\n+\n+\t\t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + ieot->entries[i].offset);\n+\t\t\tce = create_from_disk(disk_ce, &consumed, previous_name, 0);\n+\t\t\tprintf(\"%8d %8d %.*s\\n\", ieot->entries[i].offset, ieot->entries[i].nr, ce->ce_namelen, ce->name);\n+\t\t\tfree(ce);\n+\t\t}\n+\t} else {\n+\t\tprintf(\"missing or invalid extension\");\n+\t\terr = 1;\n+\t}\n+\n+\tfree(ieot);\n+\tmunmap(mmap, mmap_size);\n+\treturn err;\n+#else\n+\tdie(\"ieot only supported with PTHREADS\");\n+\treturn -1;\n+#endif\n+}\ndiff --git a/t/helper/test-fast-index.c b/t/helper/test-fast-index.c\nnew file mode 100644\nindex 0000000000..fe63130ba0\n--- /dev/null\n+++ b/t/helper/test-fast-index.c\n@@ -0,0 +1,84 @@\n+#include \"cache.h\"\n+\n+int compare_ce(const struct cache_entry *ce1, const struct cache_entry *ce2)\n+{\n+\t/*\tstruct hashmap_entry ent; */\n+\t/*\tstruct stat_data ce_stat_data; */\n+\n+\tif (ce1->ce_mode != ce2->ce_mode) {\n+\t\tprintf(\"ce_mode: %d:%d\\n\", ce1->ce_mode, ce2->ce_mode);\n+\t\treturn 1;\n+\t}\n+\n+\tif (ce1->ce_flags != ce2->ce_flags) {\n+\t\tprintf(\"ce_flags: %d:%d\\n\", ce1->ce_flags, ce2->ce_flags);\n+\t\treturn 1;\n+\t}\n+\n+\tif (ce1->ce_namelen != ce2->ce_namelen) {\n+\t\tprintf(\"namelen: %d:%d\\n\", ce1->ce_namelen, ce2->ce_namelen);\n+\t\treturn 1;\n+\t}\n+\n+\tif (ce1->index != ce2->index) {\n+\t\tprintf(\"index: %d:%d\\n\", ce1->index, ce2->index);\n+\t\treturn 1;\n+\t}\n+\n+\tif (oidcmp(&ce1->oid, &ce2->oid)) {\n+\t\tprintf(\"oid: %s:%s\\n\", oid_to_hex(&ce1->oid), oid_to_hex(&ce2->oid));\n+\t\treturn 1;\n+\t}\n+\n+\tif (strcmp(ce1->name, ce2->name)) {\n+\t\tprintf(\"name: %s:%s\\n\", ce1->name, ce2->name);\n+\t\treturn 1;\n+\t}\n+\n+\n+\treturn 0;\n+}\n+\n+extern int ignore_fast_index_config;\n+\n+int cmd_main(int ac, const char **av)\n+{\n+#ifndef NO_PTHREADS\n+\tstatic struct index_state index;\n+\tstatic struct index_state ieot;\n+\tint i, err = 0;\n+\n+\tsetup_git_directory();\n+\tignore_fast_index_config = 1;\n+\tcore_fast_index = 0;\n+\tread_index(&index);\n+\tcore_fast_index = 1;\n+\tread_index(&ieot);\n+\n+\tfor (i = 0; i < index.cache_nr; i++) {\n+\t\tif (compare_ce(index.cache[i], ieot.cache[i])) {\n+\t\t\tstruct cache_entry *ce;\n+\n+\t\t\tce = index.cache[i];\n+\t\t\tprintf(\"%06o %s %d\\t%s\\n\", ce->ce_mode,\n+\t\t\t\toid_to_hex(&ce->oid), ce_stage(ce), ce->name);\n+\t\t\tce = ieot.cache[i];\n+\t\t\tprintf(\"%06o %s %d\\t%s\\n\", ce->ce_mode,\n+\t\t\t\toid_to_hex(&ce->oid), ce_stage(ce), ce->name);\n+\n+\t\t\tprintf(\"cache entry %d does not match\", i);\n+\t\t\terr = 1;\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n+\tdiscard_index(&ieot);\n+\tdiscard_index(&index);\n+\tif (!err)\n+\t\tprintf(\"Cache entires are the same\\n\");\n+\treturn err;\n+#else\n+\tdie(\"ieot only supported with PTHREADS\");\n+\treturn -1;\n+#endif\n+}\ndiff --git a/t/t1800-fast-index.sh b/t/t1800-fast-index.sh\nnew file mode 100644\nindex 0000000000..b3460f1698\n--- /dev/null\n+++ b/t/t1800-fast-index.sh\n@@ -0,0 +1,55 @@\n+#!/bin/sh\n+\n+test_description='git fast index tests'\n+\n+. ./test-lib.sh\n+\n+GIT_FASTINDEX_TEST=1; export GIT_FASTINDEX_TEST\n+\n+test_expect_success 'setup' '\n+\t: >tracked &&\n+\t: >modified &&\n+\tmkdir dir1 &&\n+\t: >dir1/tracked &&\n+\t: >dir1/modified &&\n+\tmkdir dir2 &&\n+\t: >dir2/tracked &&\n+\t: >dir2/modified &&\n+\tgit add . &&\n+\tgit commit -m initial &&\n+\tcat >.gitignore <<-\\EOF\n+\t.gitignore\n+\texpect*\n+\tactual*\n+\tEOF\n+'\n+\n+test_expect_success 'fastindex extension is off by default' '\n+\ttest_must_fail test-dump-fast-index >actual 2>&1 &&\n+\tgrep \"^missing or invalid extension\" actual\n+'\n+\n+test_expect_success 'update-index --fastindex\" adds the fsmonitor extension' '\n+\tgit update-index --fastindex &&\n+\ttest-dump-fast-index >actual &&\n+\tgrep \"^IEOT with\" actual\n+'\n+\n+test_expect_success 'update-index --no-fastindex\" removes the fastindex extension' '\n+\tgit update-index --no-fastindex &&\n+\ttest_must_fail test-dump-fast-index >actual &&\n+\tgrep \"^missing or invalid extension\" actual\n+'\n+\n+test_expect_success 'verify with and without fastindex returns same result' '\n+\tgit update-index --fastindex &&\n+\ttest-fast-index\n+'\n+\n+test_expect_success 'test with V4 index' '\n+\tgit config core.fastindex 1 &&\n+\tgit update-index --index-version 4 &&\n+\ttest-fast-index\n+'\n+\n+test_done\n-- \n2.15.0.windows.1\n\n"},{"id":"332122","messageId":"20171109141737.47976-5-benpeart@microsoft.com","threadId":"47145","inReplyTo":"20171109141737.47976-1-benpeart@microsoft.com","subject":"[PATCH v1 4/4] fastindex: add documentation for the fastindex extension","fromName":"Ben Peart","fromEmail":"benpeart@microsoft.com","sentAt":"2017-11-09T14:17:37Z","receivedAt":"2017-11-09T14:18:25Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"This includes the core.fastindex setting, the update-index additions,\nand the fastindex index extension.\n\nSigned-off-by: Ben Peart <benpeart@microsoft.com>\n---\n Documentation/config.txt                 |  8 ++++++++\n Documentation/git-update-index.txt       | 11 +++++++++++\n Documentation/technical/index-format.txt | 26 ++++++++++++++++++++++++++\n 3 files changed, 45 insertions(+)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 5f0d62753d..269ff97c8c 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -868,6 +868,14 @@ relatively high IO latencies.  When enabled, Git will do the\n index comparison to the filesystem data in parallel, allowing\n overlapping IO's.  Defaults to true.\n \n+core.fastIndex::\n+\tEnable parallel index loading\n++\n+This can speed up operations like 'git diff' and 'git status' especially\n+when the index is very large.  When enabled, Git will do the index\n+loading from the on disk format to the in-memory format in parallel.\n+Defaults to false.\n+\n core.createObject::\n \tYou can set this to 'link', in which case a hardlink followed by\n \ta delete of the source are used to make sure that object creation\ndiff --git a/Documentation/git-update-index.txt b/Documentation/git-update-index.txt\nindex 75c7dd9dea..7ffd285c94 100644\n--- a/Documentation/git-update-index.txt\n+++ b/Documentation/git-update-index.txt\n@@ -19,6 +19,7 @@ SYNOPSIS\n \t     [--ignore-submodules]\n \t     [--[no-]split-index]\n \t     [--[no-|test-|force-]untracked-cache]\n+\t     [--[no-]fastindex]\n \t     [--really-refresh] [--unresolve] [--again | -g]\n \t     [--info-only] [--index-info]\n \t     [-z] [--stdin] [--index-version <n>]\n@@ -201,6 +202,16 @@ will remove the intended effect of the option.\n \t`--untracked-cache` used to imply `--test-untracked-cache` but\n \tthis option would enable the extension unconditionally.\n \n+--fastindex::\n+--no-fastindex::\n+\tEnable or disable the fast index feature. These options\n+\ttake effect whatever the value of the `core.fastindex`\n+\tconfiguration variable (see linkgit:git-config[1]). But a warning\n+\tis emitted when the change goes against the configured value, as\n+\tthe configured value will take effect next time the index is\n+\tread and this will remove the intended effect of the option.\n+\n+\n \\--::\n \tDo not interpret any more arguments as options.\n \ndiff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt\nindex ade0b0c445..e37b4cf874 100644\n--- a/Documentation/technical/index-format.txt\n+++ b/Documentation/technical/index-format.txt\n@@ -295,3 +295,29 @@ The remaining data of each directory block is grouped by type:\n     in the previous ewah bitmap.\n \n   - One NUL.\n+\n+== Index Entry Offset Table\n+\n+  The Index Entry Offset Table (IEOT) is used to help address the CPU\n+  cost of loading the index by enabling multi-threading the process of\n+  converting cache entries from the on-disk format to the in-memory format.\n+  Because it must be able to be loaded before the variable length cache\n+  entries and other index extensions, this extension must be written last.\n+  The signature for this extension is { 'I', 'E', 'O', 'T' }.\n+\n+  The extension consists of:\n+\n+  - 32-bit version (currently 1)\n+\n+  - A number of index offset entries each consisting of:\n+\n+    - 32-bit offset from the begining of the file to the first cache entry\n+\t  in this block of entries.\n+\n+    - 32-bit count of cache entries in this block\n+\n+  - 32-bit version (currently 1)\n+\n+  - 32-bit size of the extension\n+\n+  - 4-byte extension signature\n-- \n2.15.0.windows.1\n\n"},{"id":"332148","messageId":"xmqqbmkahhar.fsf@gitster.mtv.corp.google.com","threadId":"47145","inReplyTo":"20171109141737.47976-2-benpeart@microsoft.com","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-11-10T04:46:36Z","receivedAt":"2017-11-10T04:46:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ben Peart <benpeart@microsoft.com> writes:\n\n> To make this work for V4 indexes, when writing the index, it periodically\n> \"resets\" the prefix-compression by encoding the current entry as if the\n> path name for the previous entry is completely different and saves the\n> offset of that entry in the IEOT.  Basically, with V4 indexes, it\n> generates offsets into blocks of prefix-compressed entries.\n\nYou specifically mentioned about this change in your earlier\ncorrespondence on this series, and it reminds me of Shawn's reftable\nproposal that also is heavily depended on prefix compression with\noccasional reset to allow scanning from an entry in the middle.  I\nfind it a totally sensible design choice.\n\n> To enable reading the IEOT extension before reading all the variable\n> length cache entries and other extensions, the IEOT is written last,\n> right before the trailing SHA1.\n\nOK, we have already closed the door for further enhancements to\nplace something other than the index extensions after this block by\nmistakenly made it the rule that the end of the series of extended\nsections must coincide with the beginning of the trailing checksum,\nso it does not sound all that bad to insist on this particular one\nto be the last, I guess.  But see below...\n\n> The format of that extension has the signature bytes and size at the\n> beginning (like a normal extension) as well as at the end in reverse\n> order to enable parsing the extension by seeking back from the end of\n> the file.\n\nI think this is a reasonable workaround to allow a single extension\nthat needs to be read before the main index is loaded.  \n\nBut I'd suggest taking this approach one step further.  Instead,\nwhat if we introduce a new extension EOIE (\"end of index entries\")\nwhose sole purpose is to sit at the end of the series of extensions\nand point at the beginning of the index extension section of the\nfile, to tell you where to seek in order to skip the main index?\n\nThat way, you can\n\n - seek to the end of the index file;\n\n - go backward skiping the trailing file checksum;\n\n - now you might be at the end of the EOIE extension.  seek back\n   necessary number of bytes and verify EOIE header, pick up the\n   recorded file offset of the beginning of the extensions section.\n\n - The 4-byte sequence you found may happen to match EOIE but that\n   is not enough to be sure that you indeed have such an extension.\n   So the following must be done carefully, allowing the possibility\n   that there wasn't any EOIE extension at the end.\n   Seek back to that offset, and repeat these three steps to skip\n   over all extensions:\n\n   - read the (possible) 4-byte header\n   - read the (possible) extsize (validate that this is a sane value)\n   - skip that many bytes\n\n   until you come back to the location you assumed that you found\n   your EOIE header, to make sure you did not get fooled by bytes\n   that happened to look like one.  Some \"extsize\" you picked up\n   during that process may lead you beyond the end of the index\n   file, which would be a sure sign that what you found at the end\n   of the index file was *not* the EOIE extension but a part of\n   some other extension who happened to have these four bytes at the\n   right place.\n\nwhich would be a lot more robust way to allow any extensions to be\nread before the main body of the index.\n\nAnd a lot more importantly, we will leave the door open to allow\nmore than one index extensions that we would prefer to read before\nreading the main body if we do it this way, because we can easily\nskip things over without spending cycles once we have a robust way\nto find where the end of the main index is.  After all, the reason\nyou placed IEOT at the end is not because you wanted to have it at\nthe very end.  You only wanted to be able to find where it is\nwithout having to parse the variable-length records of the main\nindex.  And there may be other index extensions that wants to be\nreadable without reading the main part just like IEOT, and we do not\nwant to close the door for them.\n\nHmm?\n"},{"id":"332420","messageId":"7e5a9fde-67fc-2bb9-51b6-54bdaed162db@gmail.com","threadId":"47145","inReplyTo":"xmqqbmkahhar.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-11-13T16:42:07Z","receivedAt":"2017-11-13T16:42:16Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 11/9/2017 11:46 PM, Junio C Hamano wrote:\n> Ben Peart <benpeart@microsoft.com> writes:\n> \n>> To make this work for V4 indexes, when writing the index, it periodically\n>> \"resets\" the prefix-compression by encoding the current entry as if the\n>> path name for the previous entry is completely different and saves the\n>> offset of that entry in the IEOT.  Basically, with V4 indexes, it\n>> generates offsets into blocks of prefix-compressed entries.\n> \n> You specifically mentioned about this change in your earlier\n> correspondence on this series, and it reminds me of Shawn's reftable\n> proposal that also is heavily depended on prefix compression with\n> occasional reset to allow scanning from an entry in the middle.  I\n> find it a totally sensible design choice.\n> \n\nGreat! I didn't realize there was already precedent for this in other \npatches.  I guess good minds think alike... :)\n\n>> To enable reading the IEOT extension before reading all the variable\n>> length cache entries and other extensions, the IEOT is written last,\n>> right before the trailing SHA1.\n> \n> OK, we have already closed the door for further enhancements to\n> place something other than the index extensions after this block by\n> mistakenly made it the rule that the end of the series of extended\n> sections must coincide with the beginning of the trailing checksum,\n> so it does not sound all that bad to insist on this particular one\n> to be the last, I guess.  But see below...\n> \n>> The format of that extension has the signature bytes and size at the\n>> beginning (like a normal extension) as well as at the end in reverse\n>> order to enable parsing the extension by seeking back from the end of\n>> the file.\n> \n> I think this is a reasonable workaround to allow a single extension\n> that needs to be read before the main index is loaded.\n> \n> But I'd suggest taking this approach one step further.  Instead,\n> what if we introduce a new extension EOIE (\"end of index entries\")\n> whose sole purpose is to sit at the end of the series of extensions\n> and point at the beginning of the index extension section of the\n> file, to tell you where to seek in order to skip the main index?\n> \n> That way, you can\n> \n>   - seek to the end of the index file;\n> \n>   - go backward skiping the trailing file checksum;\n> \n>   - now you might be at the end of the EOIE extension.  seek back\n>     necessary number of bytes and verify EOIE header, pick up the\n>     recorded file offset of the beginning of the extensions section.\n> \n>   - The 4-byte sequence you found may happen to match EOIE but that\n>     is not enough to be sure that you indeed have such an extension.\n>     So the following must be done carefully, allowing the possibility\n>     that there wasn't any EOIE extension at the end.\n>     Seek back to that offset, and repeat these three steps to skip\n>     over all extensions:\n> \n>     - read the (possible) 4-byte header\n>     - read the (possible) extsize (validate that this is a sane value)\n>     - skip that many bytes\n> \n>     until you come back to the location you assumed that you found\n>     your EOIE header, to make sure you did not get fooled by bytes\n>     that happened to look like one.  Some \"extsize\" you picked up\n>     during that process may lead you beyond the end of the index\n>     file, which would be a sure sign that what you found at the end\n>     of the index file was *not* the EOIE extension but a part of\n>     some other extension who happened to have these four bytes at the\n>     right place.\n> \n\nI'm doing this careful examination and verification in the patch \nalready.  Please look closely at read_ieot_extension() to make sure \nthere isn't a test I should be doing but missed.\n\n> which would be a lot more robust way to allow any extensions to be\n> read before the main body of the index.\n> \n> And a lot more importantly, we will leave the door open to allow\n> more than one index extensions that we would prefer to read before\n> reading the main body if we do it this way, because we can easily\n> skip things over without spending cycles once we have a robust way\n> to find where the end of the main index is.  After all, the reason\n> you placed IEOT at the end is not because you wanted to have it at\n> the very end.  You only wanted to be able to find where it is\n> without having to parse the variable-length records of the main\n> index.  And there may be other index extensions that wants to be\n> readable without reading the main part just like IEOT, and we do not\n> want to close the door for them.\n> \n\nThe proposed format for extensions (ie having both a header and a footer \nwith name and size) in the current patch already enables having multiple \nextensions that can be parsed forward or backward.  Any extensions that \nwould want to be parse-able in reverse would just all need to be written \none after the other after right before the trailing SHA1 (and of course, \ninclude the proper footer).  The same logic that parses the IEOT \nextension could be extended to continue looking backwards through the \nfile parsing extensions until it encounters an unknown signature, \ninvalid size, etc.\n\nThat said, the IEOT is essentially a table of contents into the index (I \nhesitate to call it an index of the index as that could get confusing \n:)).  While in the current iteration of this patch it only contains \noffsets into blocks of cache entries that are independently parse-able, \nI had initially considered including an offset into the index where the \nextensions start just as you suggest above.\n\nWhen I looked at the existing extensions to see if they could be sped up \nby loading them on parallel threads I found that some of them \nassume/require they are processed in a specific order so there was no \nreal benefit to loading them in parallel threads.\n\nI ended up removing the offset to the first extension because I've found \nthat trying to speculatively design a feature for a potential future \nneed often doesn't result in what you actually need once you get there. \n:)  Instead, I made sure there was a version number in the IEOT \nstructure so if we actually needed a way to extend the table of contents \nat some point in the future (like to include an offset to the \nextensions), we could easily add it and increment the IEOT version.\n\nI could add the offset back in but currently nothing would use it so \nwe're just adding additional complexity to calculate and parse it with \nwith no (current) benefit.\n\nHow about I rename this the \"Index Table of Contents\" (ITOC) to make \nit's potential more clear and if/when we need to enhance it with an \noffset to the extensions, we do so at that point in time?\n\n> Hmm?\n> \n"},{"id":"332482","messageId":"xmqq7eut8y36.fsf@gitster.mtv.corp.google.com","threadId":"47145","inReplyTo":"7e5a9fde-67fc-2bb9-51b6-54bdaed162db@gmail.com","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-11-14T01:10:05Z","receivedAt":"2017-11-14T01:10:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ben Peart <peartben@gmail.com> writes:\n\n> The proposed format for extensions (ie having both a header and a\n> footer with name and size) in the current patch already enables having\n> multiple extensions that can be parsed forward or backward.  Any\n> extensions that would want to be parse-able in reverse would just all\n> need to be written one after the other after right before the trailing\n> SHA1 (and of course, include the proper footer).\n\nIn other words, anything that wants to be scannable from the tail is\nwelcome to reimplement the same validation structure used by IEOT to\ncheck the section specific sanity constraint, and this series is not\ninterested in introducing a more general infrastructure to make it\neasy for code that want to find where each extension section in the\nfile begins without pasing the body of the index.\n\nI find it somewhat unsatisfactory in that it is a fundamental change\nto allow jumping to the start of an extension section from the tail\nthat can benefit any future codepath, and have expected a feature\nneutral extension whose sole purpose is to do so [*1*].\n\nThat way, extension sections whose names are all-caps can stay to be\noptional, even if they allow locating from the tail of the file.  If\nyou require them to implement the same validation struture as IEOT\nto perform section specific sanity constraint and also require them\nto be placed consecutively at the end, the reader MUST know about\nall such extensions---otherwise they cannot scan backwards and find\nones that appear before an unknown but optional one.  If you keep an\nextension section at the end whose sole purpose is to point at the\nbeginning of extension sections, the reader can then scan forward as\nusual, skipping over unknown but optional ones, and reading your\nIEOT can merely be an user (and the first user) of that more generic\nfeature that is futureproof, no?\n\n\n"},{"id":"332538","messageId":"7428e41e-b705-f377-1951-b11af851c4d5@gmail.com","threadId":"47145","inReplyTo":"xmqq7eut8y36.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-11-14T14:31:03Z","receivedAt":"2017-11-14T14:31:14Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 11/13/2017 8:10 PM, Junio C Hamano wrote:\n> Ben Peart <peartben@gmail.com> writes:\n> \n>> The proposed format for extensions (ie having both a header and a\n>> footer with name and size) in the current patch already enables having\n>> multiple extensions that can be parsed forward or backward.  Any\n>> extensions that would want to be parse-able in reverse would just all\n>> need to be written one after the other after right before the trailing\n>> SHA1 (and of course, include the proper footer).\n> \n> In other words, anything that wants to be scannable from the tail is\n> welcome to reimplement the same validation structure used by IEOT to\n> check the section specific sanity constraint, and this series is not\n> interested in introducing a more general infrastructure to make it\n> easy for code that want to find where each extension section in the\n> file begins without pasing the body of the index.\n> \n> I find it somewhat unsatisfactory in that it is a fundamental change\n> to allow jumping to the start of an extension section from the tail\n> that can benefit any future codepath, and have expected a feature\n> neutral extension whose sole purpose is to do so [*1*].\n> \n> That way, extension sections whose names are all-caps can stay to be\n> optional, even if they allow locating from the tail of the file.  If\n> you require them to implement the same validation struture as IEOT\n> to perform section specific sanity constraint and also require them\n> to be placed consecutively at the end, the reader MUST know about\n> all such extensions---otherwise they cannot scan backwards and find\n> ones that appear before an unknown but optional one.  If you keep an\n> extension section at the end whose sole purpose is to point at the\n> beginning of extension sections, the reader can then scan forward as\n> usual, skipping over unknown but optional ones, and reading your\n> IEOT can merely be an user (and the first user) of that more generic\n> feature that is futureproof, no?\n> \n> \n\nHow about I add the logic to write out a special extension right before \nthe SHA1 that contains an offset to the beginning of the extensions \nsection.  I will also add the logic in do_read_index() to search for and \nload this special extension if it exists.\n\nThis will provide a common framework for any future extension to take \nadvantage of if it wants to be loaded/processed before or in parallel \nwith the cache entries or other extensions.\n\nFor all existing extensions that assume they are loaded _after_ the \ncache entries, in do_read_index() I'll add the logic to use the offset \n(if it exists) to adjust the src_offset and then load them normally.\n\nGiven the IEOT extension is just another list of offsets into the index \nto enable out of order processing, I'll add those offsets into the same \nextension so that it is a more generic \"table of contents\" for the \nentire index.  This enables us to have common/reusable way to have \nrandom access to _all_ sections in the index while maintaining backwards \ncomparability with the existing index formats and code.\n\nThese additional offsets will initially only be used to parallelize the \nloading of cache entries and only if the user explicitly enables that \noption but I can think of other interesting uses for them in the future.\n"},{"id":"332542","messageId":"xmqq7eus3nr2.fsf@gitster.mtv.corp.google.com","threadId":"47145","inReplyTo":"7428e41e-b705-f377-1951-b11af851c4d5@gmail.com","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-11-14T15:04:33Z","receivedAt":"2017-11-14T15:04:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ben Peart <peartben@gmail.com> writes:\n\n> How about I add the logic to write out a special extension right\n> before the SHA1 that contains an offset to the beginning of the\n> extensions section.  I will also add the logic in do_read_index() to\n> search for and load this special extension if it exists.\n>\n> This will provide a common framework for any future extension to take\n> advantage of if it wants to be loaded/processed before or in parallel\n> with the cache entries or other extensions.\n>\n> For all existing extensions that assume they are loaded _after_ the\n> cache entries, in do_read_index() I'll add the logic to use the offset\n> (if it exists) to adjust the src_offset and then load them normally.\n>\n> Given the IEOT extension is just another list of offsets into the\n> index to enable out of order processing, I'll add those offsets into\n> the same extension so that it is a more generic \"table of contents\"\n> for the entire index.  This enables us to have common/reusable way to\n> have random access to _all_ sections in the index while maintaining\n> backwards comparability with the existing index formats and code.\n>\n> These additional offsets will initially only be used to parallelize\n> the loading of cache entries and only if the user explicitly enables\n> that option but I can think of other interesting uses for them in the\n> future.\n\nIf we freeze the format of IEOT extension so that we can guarantee\nthat the very first version of Git that understands IEOT can always\nfind the beginning of extension section in an index file that was\nwritten by future versions of Git, then I'm all for that plan, but\nmy impression was that you are planning to make incompatible change\nin the future to IEOT, judging from the waythat IEOT records its own\nversion number in the section and the reader uses it to reject an\nunknown one.\n\nWith that plan, what I suspect would happen is that a version of Git\nthat understands another optional extension section that wants to be\nfindable without scanning the main table and the then-current\nversion of IEOT would not be able to use an index file written by a\nnew version of Git that enhances the format of the IEOT extension\nbumps its extension version.\n\nAnd if that is the case I would have to say that I strongly suspect\nthat you would regret the design decision to mix it into IEOT.  That\nis why I keep suggesting that the back pointer extension should be\non its own, minimizing what it does and minimizing the need to be\nupdated across versions of Git.\n\n\n"},{"id":"332547","messageId":"73fd93cd-91f4-1286-732c-cd8185fe2027@gmail.com","threadId":"47145","inReplyTo":"xmqq7eus3nr2.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-11-14T15:40:00Z","receivedAt":"2017-11-14T15:40:09Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 11/14/2017 10:04 AM, Junio C Hamano wrote:\n> Ben Peart <peartben@gmail.com> writes:\n> \n>> How about I add the logic to write out a special extension right\n>> before the SHA1 that contains an offset to the beginning of the\n>> extensions section.  I will also add the logic in do_read_index() to\n>> search for and load this special extension if it exists.\n>>\n>> This will provide a common framework for any future extension to take\n>> advantage of if it wants to be loaded/processed before or in parallel\n>> with the cache entries or other extensions.\n>>\n>> For all existing extensions that assume they are loaded _after_ the\n>> cache entries, in do_read_index() I'll add the logic to use the offset\n>> (if it exists) to adjust the src_offset and then load them normally.\n>>\n>> Given the IEOT extension is just another list of offsets into the\n>> index to enable out of order processing, I'll add those offsets into\n>> the same extension so that it is a more generic \"table of contents\"\n>> for the entire index.  This enables us to have common/reusable way to\n>> have random access to _all_ sections in the index while maintaining\n>> backwards comparability with the existing index formats and code.\n>>\n>> These additional offsets will initially only be used to parallelize\n>> the loading of cache entries and only if the user explicitly enables\n>> that option but I can think of other interesting uses for them in the\n>> future.\n> \n> If we freeze the format of IEOT extension so that we can guarantee\n> that the very first version of Git that understands IEOT can always\n> find the beginning of extension section in an index file that was\n> written by future versions of Git, then I'm all for that plan, but\n> my impression was that you are planning to make incompatible change\n> in the future to IEOT, judging from the way that IEOT records its own\n> version number in the section and the reader uses it to reject an\n> unknown one.\n\nI have no thoughts or plans for changes in the future of IEOT (which I \nplan to rename ITOC).  At this point in time, I can't even imagine what \nelse we'd want as the index only contains cache entries, extensions and \nthe trailing SHA1 and with the TOC we have random access to each of \nthose.  If nothing else, it gives another signature to verify to ensure \nwe actually have a valid trailing extension. :)\n\nI only added the version because I've learned my ability to predict the \nfuture is pretty bad and it leaves us that option _if_ something ever \ncomes up that we need it _and_ are willing to live with the significant \nnegative trade-offs you correctly point out.\n\n> \n> With that plan, what I suspect would happen is that a version of Git\n> that understands another optional extension section that wants to be\n> findable without scanning the main table and the then-current\n> version of IEOT would not be able to use an index file written by a\n> new version of Git that enhances the format of the IEOT extension\n> bumps its extension version.\n> \n> And if that is the case I would have to say that I strongly suspect\n> that you would regret the design decision to mix it into IEOT.  That\n> is why I keep suggesting that the back pointer extension should be\n> on its own, minimizing what it does and minimizing the need to be\n> updated across versions of Git.\n> \n\nI understand the risk but the list of offsets into the cache entries is \npretty simple as well. I prefer the simplicity of a single TOC extension \nthat gives us random access to the entire index rather than having to \npiece one together using multiple extensions.  That model has its own \nset of risks and tradeoffs.\n"},{"id":"332588","messageId":"xmqqwp2s1h1x.fsf@gitster.mtv.corp.google.com","threadId":"47145","inReplyTo":"73fd93cd-91f4-1286-732c-cd8185fe2027@gmail.com","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-11-15T01:12:10Z","receivedAt":"2017-11-15T01:12:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ben Peart <peartben@gmail.com> writes:\n\n> I have no thoughts or plans for changes in the future of IEOT (which I\n> plan to rename ITOC).  At this point in time, I can't even imagine\n> what else we'd want as the index only contains cache entries, ...\n\nYeah, but the thing is that this is open source, and the imagination\nof the originator of the initial idea does not limit how the code\nand data structure evolves.\n\nBack when I added the index extensions to the system, I didn't have\nperfect foresight, and I didn't have specific plans to add anything\nbeyond \"TREE\" to optimize \"write-tree\" and \"diff-index --cached\".\n\nIn hindsight, I got one thing right and one thing wrong.\n\nEven though I didn't have any plan to add a mandatory extension, I\nmade the code to ignore optional ones and error out on mandatory\nones if an index extension section is not understood.  It turns out\nthat later (in fact much later---the \"TREE\" extension dates back to\nApril 2006, while \"link\" came in June 2014) we could add the\nsplit-index mode without having to worry about older versions of Git\ndoing random wrong things when they see this new extension, thanks\nto that design decision.  That went well.\n\nOn the other hand, I didn't think things through to realize that\nsome operations may want to peek only the extensions without ever\nusing the main table, that some other operations may want to read\nsome extensions first before reading the main table, or more\nimportantly, that these limitations would start mattering once Git\nbecomes popular enough and starts housing a project tree with very\nmany paths in the main table.  \n\nI really wish somebody had brought it up as a potential issue during\nthe review---I would have defined the extended index format to have\nthe simple extension at the end that points back to the tail end of\nthe main table back then, and we wouldn't be having this back and\nforth now.  But I was just too happy and excited that I have found a\nroom to squeeze extension sections into the index file format\nwithout breaking existing implementations of Git (which checked the\ntrailer checksum matches to the result of hashing the whole thing,\nand read the recorded number of entries from the main table, without\neven noticing that there is a gap in between), and that excitement\nblinded me.\n\n> I understand the risk but the list of offsets into the cache entries\n> is pretty simple as well. I prefer the simplicity of a single TOC\n> extension that gives us random access to the entire index rather than\n> having to piece one together using multiple extensions.  That model\n> has its own set of risks and tradeoffs.\n\nI thought that you are not using the \"where does the series of\nextensions begin\" information in the first place, no?  That piece of\ninformation is useful independent of the usefulness of \"index into\nthe main table to list entries where the prefix-compression is\nreset\".  So if anything, I'd prefer the simplicity of introducing\nthat \"where does the series of extensions begin\" that does not say\nanything else, and build on other things like ITOC as mere users of\nthe mechanism.\n\n"},{"id":"332594","messageId":"9ba23d2c-2198-55d7-5a02-69879fbbb3cb@gmail.com","threadId":"47145","inReplyTo":"xmqqwp2s1h1x.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-11-15T04:16:39Z","receivedAt":"2017-11-15T04:16:53Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 11/14/2017 8:12 PM, Junio C Hamano wrote:\n> Ben Peart <peartben@gmail.com> writes:\n> \n>> I have no thoughts or plans for changes in the future of IEOT (which I\n>> plan to rename ITOC).  At this point in time, I can't even imagine\n>> what else we'd want as the index only contains cache entries, ...\n> \n> Yeah, but the thing is that this is open source, and the imagination\n> of the originator of the initial idea does not limit how the code\n> and data structure evolves.\n> \n> Back when I added the index extensions to the system, I didn't have\n> perfect foresight, and I didn't have specific plans to add anything\n> beyond \"TREE\" to optimize \"write-tree\" and \"diff-index --cached\".\n> \n> In hindsight, I got one thing right and one thing wrong.\n> \n> Even though I didn't have any plan to add a mandatory extension, I\n> made the code to ignore optional ones and error out on mandatory\n> ones if an index extension section is not understood.  It turns out\n> that later (in fact much later---the \"TREE\" extension dates back to\n> April 2006, while \"link\" came in June 2014) we could add the\n> split-index mode without having to worry about older versions of Git\n> doing random wrong things when they see this new extension, thanks\n> to that design decision.  That went well.\n> \n> On the other hand, I didn't think things through to realize that\n> some operations may want to peek only the extensions without ever\n> using the main table, that some other operations may want to read\n> some extensions first before reading the main table, or more\n> importantly, that these limitations would start mattering once Git\n> becomes popular enough and starts housing a project tree with very\n> many paths in the main table.\n> \n> I really wish somebody had brought it up as a potential issue during\n> the review---I would have defined the extended index format to have\n> the simple extension at the end that points back to the tail end of\n> the main table back then, and we wouldn't be having this back and\n> forth now.  But I was just too happy and excited that I have found a\n> room to squeeze extension sections into the index file format\n> without breaking existing implementations of Git (which checked the\n> trailer checksum matches to the result of hashing the whole thing,\n> and read the recorded number of entries from the main table, without\n> even noticing that there is a gap in between), and that excitement\n> blinded me.\n> \n>> I understand the risk but the list of offsets into the cache entries\n>> is pretty simple as well. I prefer the simplicity of a single TOC\n>> extension that gives us random access to the entire index rather than\n>> having to piece one together using multiple extensions.  That model\n>> has its own set of risks and tradeoffs.\n> \n> I thought that you are not using the \"where does the series of\n> extensions begin\" information in the first place, no?  That piece of\n> information is useful independent of the usefulness of \"index into\n> the main table to list entries where the prefix-compression is\n> reset\".  So if anything, I'd prefer the simplicity of introducing\n> that \"where does the series of extensions begin\" that does not say\n> anything else, and build on other things like ITOC as mere users of\n> the mechanism.\n> \n\nOK.  I'll call this new extension \"EOIE\" (\"end of index entries\"). Other \nthan the standard header/footer, it will only contain a 32 bit offset to \nthe beginning of the extension entries.  I'll always write out that \nextension unless you would prefer it be behind a setting (if so, what do \nyou want it called and what should the default be)?  I won't add support \nin update-index for this extension.\n\nSince the goal was to find a way to load the IEOT extension before the \ncache entries, I'll also refactor the extension reading loop into a \nfunction that takes a function pointer and add a \npreread_index_extension() function that can be passed in when that loop \nis run before the cache entries are loaded.  When the loop is run again \nafter the cache entries are loaded, it will pass in the existing \nread_index_extension() function.  Extensions can then choose which \nfunction they want to be loaded in.\n\nThe code to read/write/use the IEOT to parallelize the cache entry \nloading will stay behind a config setting that defaults to false (at \nleast for now).  I'll stick with \"core.fastindex\" until someone can \n(please) propose a better name.\n"},{"id":"332596","messageId":"xmqq1sl017dw.fsf@gitster.mtv.corp.google.com","threadId":"47145","inReplyTo":"9ba23d2c-2198-55d7-5a02-69879fbbb3cb@gmail.com","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-11-15T04:40:59Z","receivedAt":"2017-11-15T04:41:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ben Peart <peartben@gmail.com> writes:\n\n> OK.  I'll call this new extension \"EOIE\" (\"end of index\n> entries\"). Other than the standard header/footer, it will only contain\n> a 32 bit offset to the beginning of the extension entries.  I'll\n> always write out that extension unless you would prefer it be behind a\n> setting (if so, what do you want it called and what should the default\n> be)?  I won't add support in update-index for this extension.\n\nTo make it robust, if I were doing this, I would at least add a checksum\nof some sort.  \n\nAs each extension section consists of 4-byte extension type, 4-byte\nsize, followed by that many bytes of the \"meat\" of the section, what\nI had in mind when I suggested this backpointer was something like:\n\n    \"EOIE\" <32-bit size> <32-bit offset> <20-byte hash>\n\nwhere the size of the extension section is obviously 24-byte to\ncover the offset plus hash, and the hash is computed over extension\ntypes and their sizes (but not their contents---this is not about\nprotecting against file corruption and not worth wasting the cycles\nfor hashing) for all the extension sections this index file has\n(except for \"EOIE\" at the end, for obvious reasons).  E.g. if we\nhave \"TREE\" extension that is N-bytes long, \"REUC\" extension that is\nM-bytes long, followed by \"EOIE\", then the hash would be\n\n\tSHA-1(\"TREE\" + <binary representation of N> +\n\t      \"REUC\" + <binary representation of M>)\n\nThen the reader would\n\n - Seek back 32-byte from the trailer to ensure it sees \"EOIE\"\n   followed by a correct size (24?)\n\n - Jump to the offset and find 4-bytes that presumably is the type\n   of the first extension, followed by its size.  \n\n - Feed these 8-bytes to the hash, skip that section based on its\n   size (while making sure we won't run off the end of the file,\n   which is a sign that we thought EOIE exists when there wasn't).\n   Repeat this until we hit where we found \"EOIE\" (or we notice our\n   mistake by overrunning it).\n\n - Check the hash to make sure we got it right.\n\n> Since the goal was to find a way to load the IEOT extension before the\n> cache entries, I'll also refactor the extension reading loop into a\n> function that takes a function pointer and add a\n> preread_index_extension() function that can be passed in when that\n> loop is run before the cache entries are loaded.  When the loop is run\n> again after the cache entries are loaded, it will pass in the existing\n> read_index_extension() function.  Extensions can then choose which\n> function they want to be loaded in.\n>\n> The code to read/write/use the IEOT to parallelize the cache entry\n> loading will stay behind a config setting that defaults to false (at\n> least for now).  I'll stick with \"core.fastindex\" until someone can\n> (please) propose a better name.\n\nSounds good.\n"},{"id":"332904","messageId":"92b0b0ff-6878-003a-b26f-3b4c2c857be3@gmail.com","threadId":"47145","inReplyTo":"xmqq1sl017dw.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-11-20T14:01:45Z","receivedAt":"2017-11-20T14:01:59Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"Further testing has revealed that switching from the regular heap to a \nrefactored version of the mem_pool in fast-import.c produces similar \ngains as parallelizing do_index_load().  This appears to be a much \nsimpler patch for similar gains so we will be pursuing that path.\n\nCombining the two patches resulted in a further 25% reduction of \ndo_index_load() but with index load times getting smaller, that only \nresulted in a 3% improvement in total git command time.  Given the \ngreater complexity of this patch, we've decided to put it on hold for \nnow.  We'll keep it in our back pocket in case we need it in the future.\n\n"},{"id":"332905","messageId":"20171120142035.bfwu24oegw27ucs3@sigill.intra.peff.net","threadId":"47145","inReplyTo":"92b0b0ff-6878-003a-b26f-3b4c2c857be3@gmail.com","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-11-20T14:20:35Z","receivedAt":"2017-11-20T14:20:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 20, 2017 at 09:01:45AM -0500, Ben Peart wrote:\n\n> Further testing has revealed that switching from the regular heap to a\n> refactored version of the mem_pool in fast-import.c produces similar gains\n> as parallelizing do_index_load().  This appears to be a much simpler patch\n> for similar gains so we will be pursuing that path.\n\nThat sounds like a pretty easy win for index entries, which tend to\nstick around in big clumps.\n\nOut of curiosity, have you tried experimenting with any high-performance\n3rd-party allocator libraries? I've often wondered if we could get a\nperformance improvement from dropping in a new allocator, but was never\nable to measure any real benefit over glibc's ptmalloc2. The situation\nmight be different on Windows, though (i.e., if the libc allocator isn't\nthat great).\n\nMost of the high-performance allocators are focused on concurrency,\nwhich usually isn't a big deal for git. But tcmalloc, at least, claims\nto be about 6x faster than glibc.\n\nThe reason I ask is that we could possibly get the same wins without\nwriting a single line of code. And it could apply across the whole\ncode-base, not just the index code. I don't know how close a general\npurpose allocator could come to a pooled implementation, though. You're\ninherently making a tradeoff with a pool in not being able to free\nindividual entries.\n\n-Peff\n"},{"id":"332912","messageId":"20171120153846.v5b7ho42yzrznqoh@sigill.intra.peff.net","threadId":"47145","inReplyTo":"20171120142035.bfwu24oegw27ucs3@sigill.intra.peff.net","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-11-20T15:38:46Z","receivedAt":"2017-11-20T15:38:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 20, 2017 at 09:20:35AM -0500, Jeff King wrote:\n\n> Out of curiosity, have you tried experimenting with any high-performance\n> 3rd-party allocator libraries? I've often wondered if we could get a\n> performance improvement from dropping in a new allocator, but was never\n> able to measure any real benefit over glibc's ptmalloc2. The situation\n> might be different on Windows, though (i.e., if the libc allocator isn't\n> that great).\n\nJust linking with tcmalloc, like:\n\ndiff --git a/Makefile b/Makefile\nindex ee9d5eb11e..4f299cd914 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1018,7 +1018,7 @@ BUILTIN_OBJS += builtin/worktree.o\n BUILTIN_OBJS += builtin/write-tree.o\n \n GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB)\n-EXTLIBS =\n+EXTLIBS = -ltcmalloc\n \n GIT_USER_AGENT = git/$(GIT_VERSION)\n \n\nseems to consistently show about 30% speedup on p0002:\n\nTest                                          HEAD^             HEAD                  \n--------------------------------------------------------------------------------------\n0002.1: read_cache/discard_cache 1000 times   0.19(0.18+0.01)   0.13(0.12+0.01) -31.6%\n\nI don't think we really even need a patch for it. You should be able to\njust build with:\n\n  make EXT_LIBS=-ltcmalloc\n\nI can't think of any real advantage to a Makefile knob except\ndiscoverability.\n\n-Peff\n"},{"id":"333022","messageId":"63053f5d-0089-4165-0470-ed0d88a87e9e@ramsayjones.plus.com","threadId":"47145","inReplyTo":"92b0b0ff-6878-003a-b26f-3b4c2c857be3@gmail.com","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2017-11-20T23:51:26Z","receivedAt":"2017-11-20T23:51:33Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 20/11/17 14:01, Ben Peart wrote:\n> 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.\n> \n> 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.\n\nSince you are withdrawing the 'bp/fastindex' branch, I won't send the\npatch to fix up the sparse warnings (unless you would like to see it\nbefore you put it in your back pocket). ;-)\n\nATB,\nRamsay Jones\n\n\n"},{"id":"333033","messageId":"2a8d9ce6-0821-4dc0-92d8-fb736119bd6b@gmail.com","threadId":"47145","inReplyTo":"63053f5d-0089-4165-0470-ed0d88a87e9e@ramsayjones.plus.com","subject":"Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-11-21T00:45:06Z","receivedAt":"2017-11-21T00:45:16Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 11/20/2017 6:51 PM, Ramsay Jones wrote:\n> \n> \n> On 20/11/17 14:01, Ben Peart wrote:\n>> 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.\n>>\n>> 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.\n> \n> Since you are withdrawing the 'bp/fastindex' branch, I won't send the\n> patch to fix up the sparse warnings (unless you would like to see it\n> before you put it in your back pocket). ;-)\n> \n> ATB,\n> Ramsay Jones\n> \n> \n\nI'm happy to take your patches as I am keeping a copy just in case we \nneed to revisit it.\n\nI'm actually interested to see how Peff's suggestion to use tcmalloc \nhelps because nearly 90% of the remaining execution time was spent \nwaiting for a lock in malloc due to all contention from the multi-threading.\n"}]}