{"thread":{"id":"50491","subject":"[PATCH] read-cache.c: index format v5 -- 30% smaller/faster than v4","startedAt":"2019-02-13T12:08:17Z","lastAt":"2019-02-15T20:22:17Z","messageCount":5,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano","Ævar Arnfjörð Bjarmason","Duy Nguyen","Ben Peart"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"369228","messageId":"20190213120807.25326-1-pclouds@gmail.com","threadId":"50491","inReplyTo":null,"subject":"[PATCH] read-cache.c: index format v5 -- 30% smaller/faster than v4","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2019-02-13T12:08:07Z","receivedAt":"2019-02-13T12:08:17Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Index file size more or less translates to write time because we hash\nthe entire file every time we update the index. And we update the index\nquite often (automatically index refresh is done everywhere). This means\nsmaller index files are faster, especially true for very large\nworktrees.\n\nIndex v4 attempts to reduce file size by \"prefix compressing\"\npaths. This reduces file size from 17% (git.git) to 41% (webkit.git,\ndeep hierarchy).\n\nIndex v5 takes the same idea to the next level. Instead of compressing\njust paths, based on the previous entry, we \"compress\" a lot more\nfields.\n\nTake a look at stat data, st_dev, st_uid, st_gid and st_mode are the\nsame most of the time. ctime should often be the same (or differs just\nslightly). And sometimes mtime is the same as well. st_ino is also\nalways zero on Windows. We're storing a lot of duplicate values.\n\nIndex v5 handles this\n\n - by adding a \"same mask\" per entry. If st_dev is the same as previous\n   entry, for instance, we set \"st_dev is the same\" flag and will not\n   store it at all, saving 31 bits per entry.\n\n - even when we store it, \"varint\" encoding is used. We should rarely\n   need to write out 4 bytes\n\n - for ctime and mtime, even if we have to store it, we store the offset\n   instead of absolute numbers. This often leads to smaller numbers,\n   which also means fewer bytes to encode.\n\nAs a result of this, v5 reduces file size from 30% (git.git) to\n36% (webkit.git) compared to v4. Comparing to v2, webkit.git index file\nsize is reduced by 63%! A 8.4MB index file is _almost_ acceptable.\n\nOf course we trade off storage with cpu. We now need to spend more\ncycles writing or even reading (but still plenty fast compared to\nzlib). For reading, I'm counting on multi thread to hide away all this\neven if it becomes significant.\n\nFor writing, I believe the extra cycles spent in writing is still\nnothing compared to hashing code and this should still result in faster\nindex update (numbers needed). On webkit.git, updating one entry on v5\nis 30% faster than v4.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n I forgot why I started on this again. Something from the mailing\n list... Anyway this looks exciting!\n\n cache.h      |   2 +-\n read-cache.c | 245 ++++++++++++++++++++++++++++++++++++++++++++++++---\n 2 files changed, 234 insertions(+), 13 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 27fe635f62..fb5175fbb2 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -140,7 +140,7 @@ struct cache_header {\n };\n \n #define INDEX_FORMAT_LB 2\n-#define INDEX_FORMAT_UB 4\n+#define INDEX_FORMAT_UB 5\n \n /*\n  * The \"cache_time\" is just the low 32 bits of the\ndiff --git a/read-cache.c b/read-cache.c\nindex 0e0c93edc9..48c8d24d14 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1733,10 +1733,11 @@ static int read_index_extension(struct index_state *istate,\n \n static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool,\n \t\t\t\t\t    unsigned int version,\n-\t\t\t\t\t    struct ondisk_cache_entry *ondisk,\n+\t\t\t\t\t    const void *mmap,\n \t\t\t\t\t    unsigned long *ent_size,\n \t\t\t\t\t    const struct cache_entry *previous_ce)\n {\n+\tconst struct ondisk_cache_entry *ondisk = mmap;\n \tstruct cache_entry *ce;\n \tsize_t len;\n \tconst char *name;\n@@ -1749,16 +1750,16 @@ static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool,\n \t * number of bytes to be stripped from the end of the previous name,\n \t * and the bytes to append to the result, to come up with its name.\n \t */\n-\tint expand_name_field = version == 4;\n+\tint expand_name_field = version >= 4;\n \n \t/* On-disk flags are just 16 bits */\n \tflags = get_be16(&ondisk->flags);\n \tlen = flags & CE_NAMEMASK;\n \n \tif (flags & CE_EXTENDED) {\n-\t\tstruct ondisk_cache_entry_extended *ondisk2;\n+\t\tconst struct ondisk_cache_entry_extended *ondisk2 = mmap;\n \t\tint extended_flags;\n-\t\tondisk2 = (struct ondisk_cache_entry_extended *)ondisk;\n+\n \t\textended_flags = get_be16(&ondisk2->flags2) << 16;\n \t\t/* We do not yet understand any bit out of CE_EXTENDED_FLAGS */\n \t\tif (extended_flags & ~CE_EXTENDED_FLAGS)\n@@ -1820,6 +1821,113 @@ static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool,\n \treturn ce;\n }\n \n+enum same_value_bit {\n+\tDELTA_FORMAT = 1 << 0,\n+\tSAME_CTIME   = 1 << 1, /* only covers sec, not nsec */\n+\tSAME_MTIME   = 1 << 2, /* only covers sec, not nsec */\n+\tSAME_DEV     = 1 << 3,\n+\tSAME_INO     = 1 << 4,\n+\tSAME_MODE    = 1 << 5,\n+\tSAME_UID     = 1 << 6,\n+\tSAME_GID     = 1 << 7,\n+\tSAME_FLAGS   = 1 << 7\n+};\n+\n+static struct cache_entry no_previous_ce;\n+\n+static uintmax_t decode_varoffset(const unsigned char **bufp, uintmax_t prev)\n+{\n+\tuintmax_t val = decode_varint(bufp);\n+\n+\treturn val & 1 ? prev - (val >> 1) : prev + (val >> 1);\n+}\n+\n+static uintmax_t decode_varoffset_same(const unsigned char **bufp, uintmax_t prev,\n+\t\t\t\t       int same_flag)\n+{\n+\treturn same_flag ? prev : decode_varoffset(bufp, prev);\n+}\n+\n+static uintmax_t decode_varint_same(const unsigned char **bufp, uintmax_t prev,\n+\t\t\t\t    int same_flag)\n+{\n+\treturn same_flag ? prev : decode_varint(bufp);\n+}\n+\n+static struct cache_entry *create_from_disk_v5(struct mem_pool *ce_mem_pool,\n+\t\t\t\t\t       const void *mmap,\n+\t\t\t\t\t       unsigned long *ent_size,\n+\t\t\t\t\t       const struct cache_entry *previous_ce)\n+{\n+\tconst unsigned char *p = mmap;\n+\tuintmax_t same_mask = decode_varint(&p);\n+\tconst struct stat_data *old = &previous_ce->ce_stat_data;\n+\tstruct cache_entry tmp;\n+\tstruct stat_data *new = &tmp.ce_stat_data;\n+\tsize_t copy_len = 0;\n+\tstruct cache_entry *ce;\n+\tsize_t len;\n+\tconst char *name;\n+\tsize_t strip_len;\n+\n+\tif (same_mask == 0) {\n+\t\tunsigned long consumed;\n+\t\tce = create_from_disk(ce_mem_pool, 5, p, &consumed,\n+\t\t\t\t      previous_ce == &no_previous_ce ? NULL : previous_ce);\n+\t\t*ent_size = consumed + (p - (const unsigned char *)mmap);\n+\t\treturn ce;\n+\t}\n+\n+\tif (!(same_mask & DELTA_FORMAT))\n+\t\tdie(_(\"bad index file, same_mask must have flag DELTA_FORMAT set\"));\n+\n+\n+\tnew->sd_ctime.sec = decode_varoffset_same(&p, old->sd_ctime.sec,\n+\t\t\t\t\t\t  same_mask & SAME_CTIME);\n+\tnew->sd_ctime.nsec = decode_varoffset(&p, old->sd_ctime.nsec);\n+\tnew->sd_mtime.sec = decode_varoffset_same(&p, old->sd_mtime.sec,\n+\t\t\t\t\t\t  same_mask & SAME_MTIME);\n+\tnew->sd_mtime.nsec = decode_varoffset(&p, old->sd_mtime.nsec);\n+\tnew->sd_dev = decode_varint_same(&p, old->sd_dev,\n+\t\t\t\t\t same_mask & SAME_DEV);\n+\tnew->sd_ino = decode_varint_same(&p, old->sd_ino,\n+\t\t\t\t\t same_mask & SAME_INO);\n+\ttmp.ce_mode = decode_varint_same(&p, previous_ce->ce_mode,\n+\t\t\t\t\t same_mask & SAME_MODE);\n+\tnew->sd_uid = decode_varint_same(&p, old->sd_uid,\n+\t\t\t\t\t same_mask & SAME_UID);\n+\tnew->sd_gid = decode_varint_same(&p, old->sd_gid,\n+\t\t\t\t\t same_mask & SAME_GID);\n+\tnew->sd_size = decode_varint(&p);\n+\tmemcpy(&tmp.oid.hash, p, GIT_SHA1_RAWSZ);\n+\tp += GIT_SHA1_RAWSZ;\n+\ttmp.ce_flags = decode_varint(&p); /* fixme */\n+\n+\tstrip_len = decode_varint(&p);\n+\tif (previous_ce != &no_previous_ce) {\n+\t\tsize_t previous_len = previous_ce->ce_namelen;\n+\t\tif (previous_len < strip_len)\n+\t\t\tdie(_(\"malformed name field in the index, near path '%s'\"),\n+\t\t\t    previous_ce->name);\n+\t\tcopy_len = previous_len - strip_len;\n+\t}\n+\tname = (const char *)p;\n+\n+\tlen = strlen(name) + copy_len;\n+\n+\tce = mem_pool__ce_alloc(ce_mem_pool, len);\n+\tmemcpy(ce, &tmp, offsetof(struct cache_entry, name));\n+\tce->ce_namelen = len;\n+\tce->index = 0;\n+\n+\tif (copy_len)\n+\t\tmemcpy(ce->name, previous_ce->name, copy_len);\n+\tmemcpy(ce->name + copy_len, name, len + 1 - copy_len);\n+\t*ent_size = (p - (const unsigned char *)mmap) + len + 1 - copy_len;\n+\n+\treturn ce;\n+}\n+\n static void check_ce_order(struct index_state *istate)\n {\n \tunsigned int i;\n@@ -1967,12 +2075,18 @@ static unsigned long load_cache_entry_block(struct index_state *istate,\n \tunsigned long src_offset = start_offset;\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 *)(mmap + src_offset);\n-\t\tce = create_from_disk(ce_mem_pool, istate->version, disk_ce, &consumed, previous_ce);\n+\t\tif (istate->version <= 4)\n+\t\t\tce = create_from_disk(ce_mem_pool, istate->version,\n+\t\t\t\t\t      mmap + src_offset, &consumed,\n+\t\t\t\t\t      previous_ce);\n+\t\telse\n+\t\t\tce = create_from_disk_v5(ce_mem_pool,\n+\t\t\t\t\t\t mmap + src_offset,\n+\t\t\t\t\t\t &consumed,\n+\t\t\t\t\t\t previous_ce);\n \t\tset_index_entry(istate, i, ce);\n \n \t\tsrc_offset += consumed;\n@@ -2551,8 +2665,103 @@ static void copy_cache_entry_to_ondisk(struct ondisk_cache_entry *ondisk,\n \t}\n }\n \n+static int ce_write_varint(git_hash_ctx *c, int fd, uintmax_t value)\n+{\n+\tunsigned char varint[16];\n+\tint len = encode_varint(value, varint);\n+\tce_write(c, fd, varint, len);\n+\treturn len;\n+}\n+\n+static int ce_write_varoffset(git_hash_ctx *c, int fd, uintmax_t next, uintmax_t prev)\n+{\n+\tunsigned char varint[16];\n+\tuintmax_t value;\n+\tint len;\n+\n+\tif (prev < next)\n+\t\tvalue = (next - prev) << 1;\n+\telse\n+\t\tvalue = ((prev - next) << 1) | 1;\n+\tlen = encode_varint(value, varint);\n+\tce_write(c, fd, varint, len);\n+\treturn len;\n+}\n+\n+static int ce_write_entry_v5(git_hash_ctx *c, int fd,\n+\t\t\t     struct cache_entry *ce,\n+\t\t\t     const struct cache_entry *previous_ce,\n+\t\t\t     struct ondisk_cache_entry *ondisk,\n+\t\t\t     int size)\n+{\n+\tconst struct stat_data *old = &previous_ce->ce_stat_data;\n+\tstruct stat_data *new = &ce->ce_stat_data;\n+\tconst uint32_t flags_mask = 0xf000 | CE_EXTENDED_FLAGS;\n+\tuint32_t flags;\n+\tuint32_t same_mask = 0;\n+\tuint32_t written = 0;\n+\n+\tif (previous_ce == &no_previous_ce) {\n+\t\tce_write(c, fd, &same_mask, 1);\n+\t\tcopy_cache_entry_to_ondisk(ondisk, ce);\n+\t\treturn ce_write(c, fd, ondisk, size);\n+\t}\n+\n+\tsame_mask |= DELTA_FORMAT;\n+\tif (old->sd_ctime.sec == new->sd_ctime.sec)\n+\t\tsame_mask |= SAME_CTIME;\n+\tif (old->sd_mtime.sec == new->sd_mtime.sec)\n+\t\tsame_mask |= SAME_MTIME;\n+\tif (old->sd_dev == new->sd_dev)\n+\t\tsame_mask |= SAME_DEV;\n+\tif (old->sd_ino == new->sd_ino)\n+\t\tsame_mask |= SAME_INO;\n+\tif (previous_ce->ce_mode == ce->ce_mode)\n+\t\tsame_mask |= SAME_MODE;\n+\tif (old->sd_uid == new->sd_uid)\n+\t\tsame_mask |= SAME_UID;\n+\tif (old->sd_gid == new->sd_gid)\n+\t\tsame_mask |= SAME_GID;\n+\tif ((previous_ce->ce_flags & flags_mask) == (ce->ce_flags & flags_mask))\n+\t\tsame_mask |= SAME_FLAGS;\n+\n+\twritten += ce_write_varint(c, fd, same_mask);\n+\tif (!(same_mask & SAME_CTIME))\n+\t\twritten += ce_write_varoffset(c, fd,\n+\t\t\t\t\t      new->sd_ctime.sec,\n+\t\t\t\t\t      old->sd_ctime.sec);\n+\twritten += ce_write_varoffset(c, fd,\n+\t\t\t\t      new->sd_ctime.nsec,\n+\t\t\t\t      old->sd_ctime.nsec);\n+\tif (!(same_mask & SAME_MTIME))\n+\t\twritten += ce_write_varoffset(c, fd,\n+\t\t\t\t\t      new->sd_mtime.sec,\n+\t\t\t\t\t      old->sd_mtime.sec);\n+\twritten += ce_write_varoffset(c, fd,\n+\t\t\t\t      new->sd_mtime.nsec,\n+\t\t\t\t      old->sd_mtime.nsec);\n+\tif (!(same_mask & SAME_DEV))\n+\t\twritten += ce_write_varint(c, fd, new->sd_dev);\n+\tif (!(same_mask & SAME_INO))\n+\t\twritten += ce_write_varint(c, fd, new->sd_ino);\n+\tif (!(same_mask & SAME_MODE))\n+\t\twritten += ce_write_varint(c, fd, ce->ce_mode);\n+\tif (!(same_mask & SAME_UID))\n+\t\twritten += ce_write_varint(c, fd, new->sd_uid);\n+\tif (!(same_mask & SAME_GID))\n+\t\twritten += ce_write_varint(c, fd, new->sd_gid);\n+\twritten += ce_write_varint(c, fd, new->sd_size);\n+\twritten += ce_write(c, fd, &ce->oid.hash, GIT_SHA1_RAWSZ);\n+\tflags = (ce->ce_flags & 0xf000) >> 12;\n+\tflags |= (ce->ce_flags & CE_EXTENDED_FLAGS) >> 25;\n+\twritten += ce_write_varint(c, fd, flags);\n+\treturn written;\n+}\n+\n static int ce_write_entry(git_hash_ctx *c, int fd, struct cache_entry *ce,\n-\t\t\t  struct strbuf *previous_name, struct ondisk_cache_entry *ondisk)\n+\t\t\t  const struct cache_entry *previous_ce,\n+\t\t\t  struct strbuf *previous_name,\n+\t\t\t  struct ondisk_cache_entry *ondisk)\n {\n \tint size;\n \tint result;\n@@ -2591,8 +2800,13 @@ static int ce_write_entry(git_hash_ctx *c, int fd, struct cache_entry *ce,\n \t\tto_remove = previous_name->len - common;\n \t\tprefix_size = encode_varint(to_remove, to_remove_vi);\n \n-\t\tcopy_cache_entry_to_ondisk(ondisk, ce);\n-\t\tresult = ce_write(c, fd, ondisk, size);\n+\t\tif (previous_ce)\n+\t\t\tsize = ce_write_entry_v5(c, fd, ce, previous_ce,\n+\t\t\t\t\t\t ondisk, size);\n+\t\telse {\n+\t\t\tcopy_cache_entry_to_ondisk(ondisk, ce);\n+\t\t\tresult = ce_write(c, fd, ondisk, size);\n+\t\t}\n \t\tif (!result)\n \t\t\tresult = ce_write(c, fd, to_remove_vi, prefix_size);\n \t\tif (!result)\n@@ -2729,6 +2943,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \tstruct stat st;\n \tstruct ondisk_cache_entry_extended ondisk;\n \tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n+\tconst struct cache_entry *previous_ce;\n \tint drop_cache_tree = istate->drop_cache_tree;\n \toff_t offset;\n \tint ieot_entries = 1;\n@@ -2807,7 +3022,8 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \t}\n \toffset += write_buffer_len;\n \tnr = 0;\n-\tprevious_name = (hdr_version == 4) ? &previous_name_buf : NULL;\n+\tprevious_name = (hdr_version >= 4) ? &previous_name_buf : NULL;\n+\tprevious_ce = hdr_version >= 5 ? &no_previous_ce : NULL;\n \n \tfor (i = 0; i < entries; i++) {\n \t\tstruct cache_entry *ce = cache[i];\n@@ -2839,6 +3055,8 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \t\t\t */\n \t\t\tif (previous_name)\n \t\t\t\tprevious_name->buf[0] = 0;\n+\t\t\tif (previous_ce)\n+\t\t\t\tprevious_ce = &no_previous_ce;\n \t\t\tnr = 0;\n \t\t\toffset = lseek(newfd, 0, SEEK_CUR);\n \t\t\tif (offset < 0) {\n@@ -2847,11 +3065,14 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile,\n \t\t\t}\n \t\t\toffset += 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\tif (ce_write_entry(&c, newfd, ce, previous_ce, previous_name,\n+\t\t\t\t   (struct ondisk_cache_entry *)&ondisk) < 0)\n \t\t\terr = -1;\n \n \t\tif (err)\n \t\t\tbreak;\n+\t\tif (previous_ce)\n+\t\t\tprevious_ce = ce;\n \t\tnr++;\n \t}\n \tif (ieot && nr) {\n-- \n2.21.0.rc0.328.g0e39304f8d\n\n"},{"id":"369262","messageId":"xmqq1s4bb9y5.fsf@gitster-ct.c.googlers.com","threadId":"50491","inReplyTo":"20190213120807.25326-1-pclouds@gmail.com","subject":"Re: [PATCH] read-cache.c: index format v5 -- 30% smaller/faster than v4","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-02-13T22:27:46Z","receivedAt":"2019-02-13T22:27:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n\n> @@ -1749,16 +1750,16 @@ static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool,\n>  \t * number of bytes to be stripped from the end of the previous name,\n>  \t * and the bytes to append to the result, to come up with its name.\n>  \t */\n> -\tint expand_name_field = version == 4;\n> +\tint expand_name_field = version >= 4;\n\nThe code can be lazy like this, insteasd of being more descriptive\nto say \"version 4 or 5\", because we won't accept version 6 or later\nanyway.  Which is OK, I guess.\n\n>  \tif (flags & CE_EXTENDED) {\n> -\t\tstruct ondisk_cache_entry_extended *ondisk2;\n> +\t\tconst struct ondisk_cache_entry_extended *ondisk2 = mmap;\n>  \t\tint extended_flags;\n> -\t\tondisk2 = (struct ondisk_cache_entry_extended *)ondisk;\n> +\n>  \t\textended_flags = get_be16(&ondisk2->flags2) << 16;\n>  \t\t/* We do not yet understand any bit out of CE_EXTENDED_FLAGS */\n>  \t\tif (extended_flags & ~CE_EXTENDED_FLAGS)\n\nThis part may be a good clean-up regardless.\n\n> @@ -1820,6 +1821,113 @@ static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool,\n>  \treturn ce;\n>  }\n>  \n> +enum same_value_bit {\n> +\tDELTA_FORMAT = 1 << 0,\n> +\tSAME_CTIME   = 1 << 1, /* only covers sec, not nsec */\n> +\tSAME_MTIME   = 1 << 2, /* only covers sec, not nsec */\n> +\tSAME_DEV     = 1 << 3,\n> +\tSAME_INO     = 1 << 4,\n> +\tSAME_MODE    = 1 << 5,\n> +\tSAME_UID     = 1 << 6,\n> +\tSAME_GID     = 1 << 7,\n> +\tSAME_FLAGS   = 1 << 7\n> +};\n\nHmph, really?\n\n> +static struct cache_entry no_previous_ce;\n> +\n> +static uintmax_t decode_varoffset(const unsigned char **bufp, uintmax_t prev)\n> +{\n> +\tuintmax_t val = decode_varint(bufp);\n\nYou'd need to make sure (1) !val, which indicates an overflow of the\nvarint, and (2) bufp after decoding haven't over-read the mmapped\nindex file.  We may want to improve decode_varint() API so that we\ncan detect truncated data (i.e. (2)) more reliably without first\nreading too much.  Loose error checking like these would make good\ntargets for fuzz tests, I suspect.\n\n> +\treturn val & 1 ? prev - (val >> 1) : prev + (val >> 1);\n> +}\n\nSo, the LSB is used for sign, and the magnitude is shifted by one?\nOK.\n\n> +static uintmax_t decode_varoffset_same(const unsigned char **bufp, uintmax_t prev,\n> +\t\t\t\t       int same_flag)\n> +{\n> +\treturn same_flag ? prev : decode_varoffset(bufp, prev);\n> +}\n> +\n> +static uintmax_t decode_varint_same(const unsigned char **bufp, uintmax_t prev,\n> +\t\t\t\t    int same_flag)\n> +{\n> +\treturn same_flag ? prev : decode_varint(bufp);\n> +}\n\nLikewise about two error conditions.\n\n> @@ -1967,12 +2075,18 @@ static unsigned long load_cache_entry_block(struct index_state *istate,\n>  \tunsigned long src_offset = start_offset;\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 *)(mmap + src_offset);\n> -\t\tce = create_from_disk(ce_mem_pool, istate->version, disk_ce, &consumed, previous_ce);\n> +\t\tif (istate->version <= 4)\n> +\t\t\tce = create_from_disk(ce_mem_pool, istate->version,\n> +\t\t\t\t\t      mmap + src_offset, &consumed,\n> +\t\t\t\t\t      previous_ce);\n> +\t\telse\n> +\t\t\tce = create_from_disk_v5(ce_mem_pool,\n> +\t\t\t\t\t\t mmap + src_offset,\n> +\t\t\t\t\t\t &consumed,\n> +\t\t\t\t\t\t previous_ce);\n\nThis goes directly against the spirit of \"create_from_disk()\"\ninternal API, doesn't it?  It takes istate->version because it is an\nimplementation detail of that function how bytes at\n&mmap[src_offset] are consumed, possibly using previous_ce\ninformation.\n\nIOW, I think the version dependent switch should go inside that\nfunction and not in this loop.\n\n\n> +static int ce_write_varint(git_hash_ctx *c, int fd, uintmax_t value)\n> +{\n> +\tunsigned char varint[16];\n\nWe may want to do something about these \"16\".\n\n> +static int ce_write_varoffset(git_hash_ctx *c, int fd, uintmax_t next, uintmax_t prev)\n> +{\n> +\tunsigned char varint[16];\n\n"},{"id":"369304","messageId":"87bm3ek7qr.fsf@evledraar.gmail.com","threadId":"50491","inReplyTo":"20190213120807.25326-1-pclouds@gmail.com","subject":"Re: [PATCH] read-cache.c: index format v5 -- 30% smaller/faster than v4","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-02-14T10:02:52Z","receivedAt":"2019-02-14T10:02:57Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Wed, Feb 13 2019, Nguyễn Thái Ngọc Duy wrote:\n\n> Index file size more or less translates to write time because we hash\n> the entire file every time we update the index. And we update the index\n> quite often (automatically index refresh is done everywhere). This means\n> smaller index files are faster, especially true for very large\n> worktrees.\n>\n> Index v4 attempts to reduce file size by \"prefix compressing\"\n> paths. This reduces file size from 17% (git.git) to 41% (webkit.git,\n> deep hierarchy).\n>\n> Index v5 takes the same idea to the next level. Instead of compressing\n> just paths, based on the previous entry, we \"compress\" a lot more\n> fields.\n>\n> Take a look at stat data, st_dev, st_uid, st_gid and st_mode are the\n> same most of the time. ctime should often be the same (or differs just\n> slightly). And sometimes mtime is the same as well. st_ino is also\n> always zero on Windows. We're storing a lot of duplicate values.\n>\n> Index v5 handles this\n\nThis looks really promising.\n\n>  - by adding a \"same mask\" per entry. If st_dev is the same as previous\n>    entry, for instance, we set \"st_dev is the same\" flag and will not\n>    store it at all, saving 31 bits per entry.\n>\n>  - even when we store it, \"varint\" encoding is used. We should rarely\n>    need to write out 4 bytes\n>\n>  - for ctime and mtime, even if we have to store it, we store the offset\n>    instead of absolute numbers. This often leads to smaller numbers,\n>    which also means fewer bytes to encode.\n\nSounds good. I wonder if you've thought about/considered a couple of\noptimizations on top of this, or if they're possible. Both share the\nsame theme:\n\n* Instead of adding a \"same as last mask\" adding \"same as Nth\n  mask\". Something similar exists in the Sereal format (which also has\n  other techniques you use, e.g. varint\n  https://github.com/Sereal/Sereal/blob/master/sereal_spec.pod#the-copy-tag)\n\n  So instead of:\n\n      <mask1><same><mask2><same><mask1><same> etc.\n\n   You'd have:\n\n      <mask1 (mark1)><same><mask2 (mark2)><same><insert: mark1><same> etc.\n\n   I.e. when you have data that flip-flops a lot you can save space by\n   saying \"it's the same as existing earlier value at offset N\". Maybe\n   it doesn't make sense for this data, I don't know...\n\n* For ctime/mtime presumably for dir paths, are these paths tolerant to\n  or already out of glob() order? Then perhaps they can be pre-sorted so\n  the compression or ctime/mtime offset compression is more effective.\n\n> As a result of this, v5 reduces file size from 30% (git.git) to\n> 36% (webkit.git) compared to v4. Comparing to v2, webkit.git index file\n> size is reduced by 63%! A 8.4MB index file is _almost_ acceptable.\n>\n> Of course we trade off storage with cpu. We now need to spend more\n> cycles writing or even reading (but still plenty fast compared to\n> zlib). For reading, I'm counting on multi thread to hide away all this\n> even if it becomes significant.\n\nThis would be a bigger change, but have we/you ever done a POC\nexperiment to see how much of this time is eaten up by zlib that\nwouldn't be eaten up with some of the newer \"fast but good enough\"\ncompression algorithms, e.g. Snappy and Zstandard?\n"},{"id":"369305","messageId":"CACsJy8DWXcBk3f3heZp5J7dhTM3JL4MeVco56j4WtJNeskz9pw@mail.gmail.com","threadId":"50491","inReplyTo":"87bm3ek7qr.fsf@evledraar.gmail.com","subject":"Re: [PATCH] read-cache.c: index format v5 -- 30% smaller/faster than v4","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-02-14T10:14:18Z","receivedAt":"2019-02-14T10:14:47Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Feb 14, 2019 at 5:02 PM Ævar Arnfjörð Bjarmason\n<avarab@gmail.com> wrote:\n> > Take a look at stat data, st_dev, st_uid, st_gid and st_mode are the\n> > same most of the time. ctime should often be the same (or differs just\n> > slightly). And sometimes mtime is the same as well. st_ino is also\n> > always zero on Windows. We're storing a lot of duplicate values.\n> >\n> > Index v5 handles this\n>\n> This looks really promising.\n\nI was going to reply to Junio. But it turns out I underestimated\n\"varint\" encoding overhead and it increases read time too much. I\nmight get back and try some optimization when I'm bored, but until\nthen this is yet another failed experiment.\n\n> > As a result of this, v5 reduces file size from 30% (git.git) to\n> > 36% (webkit.git) compared to v4. Comparing to v2, webkit.git index file\n> > size is reduced by 63%! A 8.4MB index file is _almost_ acceptable.\n> >\n> > Of course we trade off storage with cpu. We now need to spend more\n> > cycles writing or even reading (but still plenty fast compared to\n> > zlib). For reading, I'm counting on multi thread to hide away all this\n> > even if it becomes significant.\n>\n> This would be a bigger change, but have we/you ever done a POC\n> experiment to see how much of this time is eaten up by zlib that\n> wouldn't be eaten up with some of the newer \"fast but good enough\"\n> compression algorithms, e.g. Snappy and Zstandard?\n\nI'm quite sure I tried zlib at some point, the only lasting impression\nI have is \"not good enough\". Other algorithms might improve a bit,\nperhaps on the uncompress/read side, but I find it unlikely we could\nreasonably compress like a hundred megabytes in a few dozen\nmilliseconds (a quick google says Snappy compresses 250MB/s, so about\n400ms per 100MB, too long). Splitting the files and compressing in\nparallel might help. But I will probably focus on \"sparse index\"\napproach before going that direction.\n-- \nDuy\n"},{"id":"369416","messageId":"11875ebb-5a40-4c87-dce7-b337cc922100@gmail.com","threadId":"50491","inReplyTo":"CACsJy8DWXcBk3f3heZp5J7dhTM3JL4MeVco56j4WtJNeskz9pw@mail.gmail.com","subject":"Re: [PATCH] read-cache.c: index format v5 -- 30% smaller/faster than v4","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2019-02-15T20:22:12Z","receivedAt":"2019-02-15T20:22:17Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 2/14/2019 5:14 AM, Duy Nguyen wrote:\n> On Thu, Feb 14, 2019 at 5:02 PM Ævar Arnfjörð Bjarmason\n> <avarab@gmail.com> wrote:\n>>> Take a look at stat data, st_dev, st_uid, st_gid and st_mode are the\n>>> same most of the time. ctime should often be the same (or differs just\n>>> slightly). And sometimes mtime is the same as well. st_ino is also\n>>> always zero on Windows. We're storing a lot of duplicate values.\n>>>\n>>> Index v5 handles this\n>>\n>> This looks really promising.\n> \n> I was going to reply to Junio. But it turns out I underestimated\n> \"varint\" encoding overhead and it increases read time too much. I\n> might get back and try some optimization when I'm bored, but until\n> then this is yet another failed experiment.\n> \n>>> As a result of this, v5 reduces file size from 30% (git.git) to\n>>> 36% (webkit.git) compared to v4. Comparing to v2, webkit.git index file\n>>> size is reduced by 63%! A 8.4MB index file is _almost_ acceptable.\n>>>\n\nJust for kicks, I tried this out on a couple of repos I have handy.\n\nfiles\tversion\tindex size\t%savings\n200k\t2\t25,033,758\t0.00%\n\t3\t25,033,758\t0.00%\n\t4\t15,269,923\t39.00%\n\t5\t9,759,844\t61.01%\n\t\t\t\n3m\t2\t446,123,848\t0.00%\n\t3\t446,123,848\t0.00%\n\t4\t249,631,640\t44.04%\n\t5\t82,147,981\t81.59%\n\nThe 81% savings is very impressive.  I didn't measure performance but \nnot writing out an extra 167MB to disk has to help.\n\nI'm definitely also interested in your 'sparse index' format ideas as in \nour 3M repos, there are typically only a few thousand that don't have \nthe skip-worktree bit set.  I'm not sure if that is the same 'sparse' \nyou had in mind but it would sure be nice!\n\n\n\nI've also contemplated multi-threading the index write code path.  My \nthought was in the primary thread to allocate a buffer and when it is \nfull have a background thread compute the SHA and write it to disk while \nthe primary thread fills the next buffer.\n\nI'm not sure how much it will buy us as I don't know the relative cost \nof computing the SHA/writing to disk vs filling the buffer.  I've \nsuspected the filling the buffer thread would end up blocked on the \nbackground thread most of the time which is why I haven't tried it yet.\n\n>>> Of course we trade off storage with cpu. We now need to spend more\n>>> cycles writing or even reading (but still plenty fast compared to\n>>> zlib). For reading, I'm counting on multi thread to hide away all this\n>>> even if it becomes significant.\n>>\n>> This would be a bigger change, but have we/you ever done a POC\n>> experiment to see how much of this time is eaten up by zlib that\n>> wouldn't be eaten up with some of the newer \"fast but good enough\"\n>> compression algorithms, e.g. Snappy and Zstandard?\n> \n> I'm quite sure I tried zlib at some point, the only lasting impression\n> I have is \"not good enough\". Other algorithms might improve a bit,\n> perhaps on the uncompress/read side, but I find it unlikely we could\n> reasonably compress like a hundred megabytes in a few dozen\n> milliseconds (a quick google says Snappy compresses 250MB/s, so about\n> 400ms per 100MB, too long). Splitting the files and compressing in\n> parallel might help. But I will probably focus on \"sparse index\"\n> approach before going that direction.\n> \n"}]}