{"thread":{"id":"32955","subject":"Another slash at index size","startedAt":"2013-02-21T09:45:21Z","lastAt":"2013-02-21T09:45:21Z","messageCount":1,"participants":["Nguyễn Thái Ngọc Duy"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"209961","messageId":"1361439921-13270-1-git-send-email-pclouds@gmail.com","threadId":"32955","inReplyTo":null,"subject":"Another slash at index size","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-02-21T09:45:21Z","receivedAt":"2013-02-21T09:45:21Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"I noticed that even with v4, we still duplicate a lot of info in the\nremaining fields. ce_uid and ce_guid for instance are unlikely to\nchange ever between entries. So I attempt to store offsets between the\nprevious entry instead. The result looks good. This is webkit index:\n\n 25M index-v2\n 14M index-v4\n7.7M index-v5\n4.5M index-v5.gz\n\ngzip beats me naturally, we still have a lot of spare bits and we\ndon't use dictionaries. But the code is simpler and should run faster\nthan gzip.\n\nPerformance is improved too:\n\n$ time GIT_INDEX_FILE=index-v2 ./git ls-files |head -n1 >/dev/null\n\nreal    0m0.437s\nuser    0m0.385s\nsys     0m0.048s\n$ time GIT_INDEX_FILE=index-v4 ./git ls-files |head -n1 >/dev/null\n\nreal    0m0.319s\nuser    0m0.277s\nsys     0m0.040s\n$ time GIT_INDEX_FILE=index-v5 ./git ls-files |head -n1 >/dev/null\n\nreal    0m0.250s\nuser    0m0.213s\nsys     0m0.036s\n\nSome details on the new format:\n\n - in general varint is used to store numbers, unless we know the\n   numbers are really big.\n - flags is the first field on disk, it has extra bits to let git know\n   what to do with the rest of the fields\n - Many fields like ctime, mtime, uid, gid, dev, ino are stored as\n   offsets\n - ce_mode's special values 100644 and 100755 are stored in flags. So\n   unless you use gitlinks or something else, ce_mode will not be\n   stored.\n - ce_namelen is no longer stored on disk\n - pathname is compressed just like in v4\n\n---\n cache.h      |   2 +-\n read-cache.c | 273 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++--\n 2 files changed, 269 insertions(+), 6 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex e493563..6ab53e7 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -106,7 +106,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 827ae55..147ace1 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1260,7 +1260,7 @@ static int verify_hdr(struct cache_header *hdr, unsigned long size)\n \tif (hdr->hdr_signature != htonl(CACHE_SIGNATURE))\n \t\treturn error(\"bad signature\");\n \thdr_version = ntohl(hdr->hdr_version);\n-\tif (hdr_version < 2 || 4 < hdr_version)\n+\tif (hdr_version < 2 || 5 < hdr_version)\n \t\treturn error(\"bad index version %d\", hdr_version);\n \tgit_SHA1_Init(&c);\n \tgit_SHA1_Update(&c, hdr, size - 20);\n@@ -1407,6 +1407,137 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n \treturn ce;\n }\n \n+/*\n+ * Often used flags come first to keep flags in common case small so\n+ * that encode_varint() produces fewer bytes\n+ */\n+#define CE5_OFS_MTIME\t\t(1 << 0)\n+#define CE5_MODEMASK\t\t(3 << 1)\n+#define CE5_MODE_644\t\t 0\n+#define CE5_MODE_755\t\t(1 << 1)\n+#define CE5_MODE_FULL\t\t(2 << 1)\n+#define CE5_FULL_INO\t\t(1 << 3)\n+#define CE5_STAGESHIFT\t\t 4\n+#define CE5_STAGEMASK\t\t(3 << CE5_STAGESHIFT)\n+#define CE5_ITA\t\t\t(1 << 6)\n+#define CE5_VALID\t\t(1 << 7)\n+#define CE5_SWT\t\t\t(1 << 8)\n+#define CE5_FULL_UID\t\t(1 << 9)\n+#define CE5_FULL_GID\t\t(1 << 10)\n+#define CE5_FULL_TIME\t\t(1 << 11)\n+#define CE5_FULL_DEV\t\t(1 << 12)\n+\n+static uintmax_t decode_offset(const unsigned char **bufp, uintmax_t base)\n+{\n+\tuintmax_t offset = decode_varint(bufp);\n+\tif (offset & 1)\t/* negative */\n+\t\treturn base - (offset >> 1);\n+\telse\n+\t\treturn base + (offset >> 1);\n+\n+}\n+\n+static struct cache_entry *create_from_disk_v5(const unsigned char *data,\n+\t\t\t\t\t       unsigned long *consumed,\n+\t\t\t\t\t       struct strbuf *previous_name,\n+\t\t\t\t\t       const struct cache_entry *previous_ce)\n+{\n+\tconst unsigned char *orig = data;\n+\tstruct cache_entry ce_tmp;\n+\tstruct cache_entry *ce;\n+\tunsigned int flags;\n+\n+\tflags = decode_varint(&data);\n+\tce_tmp.ce_flags = ((flags & CE5_STAGEMASK) >> CE5_STAGESHIFT) << CE_STAGESHIFT;\n+\tif (flags & CE5_ITA)\n+\t\tce_tmp.ce_flags |= CE_INTENT_TO_ADD;\n+\tif (flags & CE5_VALID)\n+\t\tce_tmp.ce_flags |= CE_VALID;\n+\tif (flags & CE5_SWT)\n+\t\tce_tmp.ce_flags |= CE_SKIP_WORKTREE;\n+\n+\tif (flags & CE5_FULL_TIME) { /* full format, 16 bytes */\n+\t\tce_tmp.ce_ctime.sec = ntoh_l(*(uint32_t*)data);\n+\t\tdata += sizeof(uint32_t);\n+\t\tce_tmp.ce_ctime.nsec = ntoh_l(*(uint32_t*)data);\n+\t\tdata += sizeof(uint32_t);\n+\n+\t\tce_tmp.ce_mtime.sec = ntoh_l(*(uint32_t*)data);\n+\t\tdata += sizeof(uint32_t);\n+\t\tce_tmp.ce_mtime.nsec = ntoh_l(*(uint32_t*)data);\n+\t\tdata += sizeof(uint32_t);\n+\t} else {\n+\t\t/* offset from previous ce */\n+\t\tce_tmp.ce_ctime.sec = decode_offset(&data, previous_ce->ce_ctime.sec);\n+\t\tce_tmp.ce_ctime.nsec = decode_offset(&data, previous_ce->ce_ctime.nsec);\n+\n+\t\tif (flags & CE5_OFS_MTIME) {\n+\t\t\t/* offset from previous ce */\n+\t\t\tce_tmp.ce_mtime.sec = decode_offset(&data, previous_ce->ce_mtime.sec);\n+\t\t\tce_tmp.ce_mtime.nsec = decode_offset(&data, previous_ce->ce_mtime.nsec);\n+\t\t} else\n+\t\t\tce_tmp.ce_mtime = ce_tmp.ce_ctime;\n+\t}\n+\n+\n+\tif (flags & CE5_FULL_DEV)\n+\t\tce_tmp.ce_dev = decode_varint(&data);\n+\telse\n+\t\tce_tmp.ce_dev = previous_ce->ce_dev;\n+\tif (flags & CE5_FULL_INO) {\n+\t\tce_tmp.ce_ino = ntoh_l(*(uint32_t*)data);\n+\t\tdata += sizeof(uint32_t);\n+\t} else {\n+\t\tuintmax_t offset = decode_varint(&data);\n+\t\tif (offset & 1)\t/* negative */\n+\t\t\tce_tmp.ce_ino = previous_ce->ce_ino - (offset >> 1);\n+\t\telse\n+\t\t\tce_tmp.ce_ino = previous_ce->ce_ino + (offset >> 1);\n+\t}\n+\tswitch (flags & CE5_MODEMASK) {\n+\tcase CE5_MODE_644:\n+\t\tce_tmp.ce_mode = 0100644;\n+\t\tbreak;\n+\tcase CE5_MODE_755:\n+\t\tce_tmp.ce_mode = 0100755;\n+\t\tbreak;\n+\tcase CE5_MODE_FULL:\n+\t\tce_tmp.ce_mode = decode_varint(&data);\n+\t\tbreak;\n+\tdefault:\n+\t\tdie(\"Huh?\");\n+\t}\n+\tif (flags & CE5_FULL_UID)\n+\t\tce_tmp.ce_uid = decode_varint(&data);\n+\telse\n+\t\tce_tmp.ce_uid = previous_ce->ce_uid;\n+\tif (flags & CE5_FULL_GID)\n+\t\tce_tmp.ce_gid = decode_varint(&data);\n+\telse\n+\t\tce_tmp.ce_gid = previous_ce->ce_gid;\n+\tce_tmp.ce_size = decode_varint(&data);\n+\thashcpy(ce_tmp.sha1, data);\n+\tdata += 20;\n+\n+\t*consumed = data - orig;\n+\t*consumed += expand_name_field(previous_name, (const char *)data);\n+\n+\tce = xmalloc(cache_entry_size(previous_name->len));\n+\tce->ce_ctime = ce_tmp.ce_ctime;\n+\tce->ce_mtime = ce_tmp.ce_mtime;\n+\tce->ce_dev   = ce_tmp.ce_dev;\n+\tce->ce_ino   = ce_tmp.ce_ino;\n+\tce->ce_mode  = ce_tmp.ce_mode;\n+\tce->ce_uid   = ce_tmp.ce_uid;\n+\tce->ce_gid   = ce_tmp.ce_gid;\n+\tce->ce_size  = ce_tmp.ce_size;\n+\tce->ce_flags = ce_tmp.ce_flags;\n+\tce->ce_namelen = previous_name->len;\n+\thashcpy(ce->sha1, ce_tmp.sha1);\n+\tmemcpy(ce->name, previous_name->buf, previous_name->len + 1);\n+\treturn ce;\n+}\n+\n /* remember to discard_cache() before reading a different cache! */\n int read_index_from(struct index_state *istate, const char *path)\n {\n@@ -1452,7 +1583,7 @@ int read_index_from(struct index_state *istate, const char *path)\n \tistate->cache = xcalloc(istate->cache_alloc, sizeof(struct cache_entry *));\n \tistate->initialized = 1;\n \n-\tif (istate->version == 4)\n+\tif (istate->version >= 4)\n \t\tprevious_name = &previous_name_buf;\n \telse\n \t\tprevious_name = NULL;\n@@ -1464,7 +1595,13 @@ int read_index_from(struct index_state *istate, const char *path)\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);\n+\t\tif (istate->version == 5)\n+\t\t\tce = create_from_disk_v5((const unsigned char*)disk_ce,\n+\t\t\t\t\t\t &consumed,\n+\t\t\t\t\t\t previous_name,\n+\t\t\t\t\t\t i > 0 ? istate->cache[i - 1] : NULL);\n+\t\telse\n+\t\t\tce = create_from_disk(disk_ce, &consumed, previous_name);\n \t\tset_index_entry(istate, i, ce);\n \n \t\tsrc_offset += consumed;\n@@ -1652,6 +1789,125 @@ static void ce_smudge_racily_clean_entry(struct cache_entry *ce)\n \t}\n }\n \n+static void strbuf_encode_varint(struct strbuf *sb, uintmax_t value)\n+{\n+\tstatic unsigned char varint[16];\n+\tint varint_len = encode_varint(value, varint);\n+\tstrbuf_add(sb, varint, varint_len);\n+}\n+\n+static void strbuf_encode_offset(struct strbuf *sb, unsigned int v1, unsigned int v2)\n+{\n+\tif (v1 < v2)\n+\t\tstrbuf_encode_varint(sb, (v2 - v1) << 1);\n+\telse\n+\t\tstrbuf_encode_varint(sb, 1 | ((v1 - v2) << 1));\n+}\n+\n+static int ce_write_entry_v5(git_SHA_CTX *c, int fd,\n+\t\t\t     struct cache_entry *ce,\n+\t\t\t     struct strbuf *previous_name,\n+\t\t\t     struct cache_entry *previous_ce)\n+{\n+\tuint32_t data[4];\n+\tunsigned int flags = 0;\n+\tstruct strbuf sb = STRBUF_INIT;\n+\tint result;\n+\n+\tif (ce->ce_flags & CE_INTENT_TO_ADD)\n+\t\tflags |= CE5_ITA;\n+\tif (ce->ce_flags & CE_VALID)\n+\t\tflags |= CE5_VALID;\n+\tif (ce->ce_flags & CE_SKIP_WORKTREE)\n+\t\tflags |= CE5_SWT;\n+\tflags |= ce_stage(ce) << CE5_STAGESHIFT;\n+\n+\tif (previous_ce) {\n+\t\tif (ce->ce_ctime.sec != ce->ce_mtime.sec ||\n+\t\t    ce->ce_ctime.nsec != ce->ce_mtime.nsec)\n+\t\t\tflags |= CE5_OFS_MTIME;\n+\t\tif (ce->ce_uid != previous_ce->ce_uid)\n+\t\t\tflags |= CE5_FULL_UID;\n+\t\tif (ce->ce_gid != previous_ce->ce_gid)\n+\t\t\tflags |= CE5_FULL_GID;\n+\t\tif (ce->ce_dev != previous_ce->ce_dev)\n+\t\t\tflags |= CE5_FULL_DEV;\n+\t} else\n+\t\tflags |= CE5_FULL_TIME | CE5_FULL_UID | CE5_FULL_GID | CE5_FULL_DEV;\n+\tif (ce->ce_mode == 0100644)\n+\t\tflags |= CE5_MODE_644; /* no bit sets actually */\n+\telse if (ce->ce_mode == 0100755)\n+\t\tflags |= CE5_MODE_755;\n+\telse\n+\t\tflags |= CE5_MODE_FULL;\n+\tif (previous_ce &&\n+\t    (ce->ce_ino - previous_ce->ce_ino < 16000 ||\n+\t     previous_ce->ce_ino - ce->ce_ino < 16000))\n+\t\t;\t\t/* inode offset */\n+\telse\n+\t\tflags |= CE5_FULL_INO;\n+\n+\tstrbuf_encode_varint(&sb, flags);\n+\n+\tif (flags & CE5_FULL_TIME) { /* full format, 16 bytes */\n+\t\tdata[0] = htonl(ce->ce_ctime.sec);\n+\t\tdata[1] = htonl(ce->ce_ctime.nsec);\n+\t\tdata[2] = htonl(ce->ce_mtime.sec);\n+\t\tdata[3] = htonl(ce->ce_mtime.nsec);\n+\t\tstrbuf_add(&sb, data, sizeof(data));\n+\t} else {\n+\t\t/* offset from previous ce */\n+\t\tstrbuf_encode_offset(&sb, previous_ce->ce_ctime.sec, ce->ce_ctime.sec);\n+\t\tstrbuf_encode_offset(&sb, previous_ce->ce_ctime.nsec, ce->ce_ctime.nsec);\n+\n+\t\tif (flags & CE5_OFS_MTIME) {\n+\t\t\t/* offset from previous ce */\n+\t\t\tstrbuf_encode_offset(&sb, previous_ce->ce_mtime.sec, ce->ce_mtime.sec);\n+\t\t\tstrbuf_encode_offset(&sb, previous_ce->ce_mtime.nsec, ce->ce_mtime.nsec);\n+\t\t}\n+\t}\n+\n+\tif (flags & CE5_FULL_DEV)\n+\t\tstrbuf_encode_varint(&sb, ce->ce_dev);\n+\tif (flags & CE5_FULL_INO) {\n+\t\tdata[0] =  htonl(ce->ce_ino);\n+\t\tstrbuf_add(&sb, data, sizeof(*data));\n+\t} else\n+\t\tstrbuf_encode_offset(&sb, previous_ce->ce_ino, ce->ce_ino);\n+\tif (flags & CE5_MODE_FULL)\n+\t\tstrbuf_encode_varint(&sb, ce->ce_mode);\n+\tif (flags & CE5_FULL_UID)\n+\t\tstrbuf_encode_varint(&sb, ce->ce_uid);\n+\tif (flags & CE5_FULL_GID)\n+\t\tstrbuf_encode_varint(&sb, ce->ce_gid);\n+\tstrbuf_encode_varint(&sb, ce->ce_size);\n+\tstrbuf_add(&sb, ce->sha1, 20);\n+\n+\tif (previous_name) {\n+\t\tint common, to_remove, prefix_size;\n+\t\tunsigned char to_remove_vi[16];\n+\t\tfor (common = 0;\n+\t\t     (ce->name[common] &&\n+\t\t      common < previous_name->len &&\n+\t\t      ce->name[common] == previous_name->buf[common]);\n+\t\t     common++)\n+\t\t\t; /* still matching */\n+\t\tto_remove = previous_name->len - common;\n+\t\tprefix_size = encode_varint(to_remove, to_remove_vi);\n+\n+\t\tstrbuf_add(&sb, to_remove_vi, prefix_size);\n+\t\tstrbuf_add(&sb, ce->name + common, ce_namelen(ce) - common);\n+\n+\t\tstrbuf_splice(previous_name, common, to_remove,\n+\t\t\t      ce->name + common, ce_namelen(ce) - common);\n+\t} else\n+\t\tstrbuf_add(&sb, ce->name, ce_namelen(ce));\n+\n+\tresult = ce_write(c, fd, sb.buf, sb.len + 1);\n+\tstrbuf_release(&sb);\n+\treturn result;\n+}\n+\n /* Copy miscellaneous fields but not the name */\n static char *copy_cache_entry_to_ondisk(struct ondisk_cache_entry *ondisk,\n \t\t\t\t       struct cache_entry *ce)\n@@ -1793,16 +2049,23 @@ int write_index(struct index_state *istate, int newfd)\n \tif (ce_write(&c, newfd, &hdr, sizeof(hdr)) < 0)\n \t\treturn -1;\n \n-\tprevious_name = (hdr_version == 4) ? &previous_name_buf : NULL;\n+\tprevious_name = (hdr_version >= 4) ? &previous_name_buf : NULL;\n \tfor (i = 0; i < entries; i++) {\n \t\tstruct cache_entry *ce = cache[i];\n+\t\tint ret;\n \t\tif (ce->ce_flags & CE_REMOVE)\n \t\t\tcontinue;\n \t\tif (!ce_uptodate(ce) && is_racy_timestamp(istate, ce))\n \t\t\tce_smudge_racily_clean_entry(ce);\n \t\tif (is_null_sha1(ce->sha1))\n \t\t\treturn error(\"cache entry has null sha1: %s\", ce->name);\n-\t\tif (ce_write_entry(&c, newfd, ce, previous_name) < 0)\n+\t\tif (hdr_version == 5)\n+\t\t\tret = ce_write_entry_v5(&c, newfd, ce,\n+\t\t\t\t\t\tprevious_name,\n+\t\t\t\t\t\ti > 0 ? cache[i-1] : NULL);\n+\t\telse\n+\t\t\tret = ce_write_entry(&c, newfd, ce, previous_name);\n+\t\tif (ret < 0)\n \t\t\treturn -1;\n \t}\n \tstrbuf_release(&previous_name_buf);\n-- \n1.8.1.2.495.g3fdf5d5.dirty\n"}]}