{"thread":{"id":"30142","subject":"[PATCH 0/9] Prefix-compress on-disk index entries","startedAt":"2012-04-03T22:53:07Z","lastAt":"2012-05-02T17:13:44Z","messageCount":27,"participants":["Junio C Hamano","David Barr","Nguyen Thai Ngoc Duy","Thomas Rast","Shawn Pearce"],"isPatch":true,"patchVersion":1,"patchTotal":9},"messages":[{"id":"188449","messageId":"1333493596-14202-1-git-send-email-gitster@pobox.com","threadId":"30142","inReplyTo":null,"subject":"[PATCH 0/9] Prefix-compress on-disk index entries","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-03T22:53:07Z","receivedAt":"2012-04-03T22:53:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This is still rough, but with this patch I am getting:\n\n $ ls -l .git/index*\n -rw-r----- 1 jch eng 25586488 2012-04-03 15:27 .git/index\n -rw-r----- 1 jch eng 14654328 2012-04-03 15:38 .git/index-4\n\nin a clone of WebKit repository that has 183175 paths.\n\nWith hot-cache with no local modification:\n\n $ time sh -c 'GIT_INDEX_FILE=.git/index-4 git diff'\n real 0m0.469s\n user 0m0.130s\n sys 0m0.330s\n\n $ time sh -c 'git diff'\n real 0m0.677s\n user 0m0.290s\n sys 0m0.370s\n\nwhich is mesuring the time needed to read of the index into in-core\nstructure and comparing the cached stat information taken from lstat(2).\n\nThe updated format is not documented yet, as I didn't intend (and I still\nam not committed) to declare a change along this line the official \"v4\"\nformat; I was merely being curious to see how much improvements we can get\nfrom a trivial approach like this.\n\nThe saving of the on-disk index size comes from two factors:\n\n - Not padding the on-disk index entries to 8-byte boundary;\n\n - Not storing the full pathname for each entry in the on-disk format.\n\nBecause the entries are sorted by path, adjacent entries in the index tend\nto share the leading components of them, and it makes sense to only store\nthe differences in later entries. In the v4 on-disk format of the index,\neach on-disk cache entry stores the number of bytes to be stripped from\nthe end of the previous name, and the bytes to append to the result, to\ncome up with its name.\n\nThe \"to-remove\" count is encoded in the varint format used in the\npackfiles, and the \"bytes-to-append\" is a simple NUL-terminated string.\n\nJunio C Hamano (9):\n varint: make it available outside the context of pack\n cache.h: hide on-disk index details\n read-cache.c: allow unaligned mapping of the index file\n read-cache.c: make create_from_disk() report number of bytes it consumed\n read-cache.c: report the header version we do not understand\n read-cache.c: move code to copy ondisk to incore cache to a helper function\n read-cache.c: move code to copy incore to ondisk cache to a helper function\n read-cache.c: read prefix-compressed names in index on-disk version v4\n read-cache.c: write index v4 format\n\n Makefile | 2 +\n builtin/update-index.c | 2 +\n cache.h | 52 +---------\n config.c | 11 ++\n environment.c | 1 +\n read-cache.c | 259 ++++++++++++++++++++++++++++++++++++++++--------\n varint.c | 29 ++++++\n varint.h | 9 ++\n 8 files changed, 275 insertions(+), 90 deletions(-)\n create mode 100644 varint.c\n create mode 100644 varint.h\n\n-- \n1.7.10.rc4.54.g1d5dd3\n"},{"id":"188450","messageId":"1333493596-14202-2-git-send-email-gitster@pobox.com","threadId":"30142","inReplyTo":"1333493596-14202-1-git-send-email-gitster@pobox.com","subject":"[PATCH 1/9] varint: make it available outside the context of pack","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-03T22:53:08Z","receivedAt":"2012-04-03T22:53:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Signed-off-by: Junio C Hamano \n---\n\n * This was taken from the bottom of my jc/split-blob topic, which made it\n available across \"pack\" related machinery, but it is useful outside the\n context of \"pack\".\n\n Makefile | 2 ++\n varint.c | 29 +++++++++++++++++++++++++++++\n varint.h | 9 +++++++++\n 3 files changed, 40 insertions(+)\n create mode 100644 varint.c\n create mode 100644 varint.h\n\ndiff --git a/Makefile b/Makefile\nindex be1957a..0f26c87 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -627,6 +627,7 @@ LIB_H += tree-walk.h\n LIB_H += unpack-trees.h\n LIB_H += userdiff.h\n LIB_H += utf8.h\n+LIB_H += varint.h\n LIB_H += xdiff-interface.h\n LIB_H += xdiff/xdiff.h\n \n@@ -752,6 +753,7 @@ LIB_OBJS += url.o\n LIB_OBJS += usage.o\n LIB_OBJS += userdiff.o\n LIB_OBJS += utf8.o\n+LIB_OBJS += varint.o\n LIB_OBJS += walker.o\n LIB_OBJS += wrapper.o\n LIB_OBJS += write_or_die.o\ndiff --git a/varint.c b/varint.c\nnew file mode 100644\nindex 0000000..4ed7729\n--- /dev/null\n+++ b/varint.c\n@@ -0,0 +1,29 @@\n+#include \"varint.h\"\n+\n+uintmax_t decode_varint(const unsigned char **bufp)\n+{\n+\tconst unsigned char *buf = *bufp;\n+\tunsigned char c = *buf++;\n+\tuintmax_t val = c & 127;\n+\twhile (c & 128) {\n+\t\tval += 1;\n+\t\tif (!val || MSB(val, 7))\n+\t\t\treturn 0; /* overflow */\n+\t\tc = *buf++;\n+\t\tval = (val << 7) + (c & 127);\n+\t}\n+\t*bufp = buf;\n+\treturn val;\n+}\n+\n+int encode_varint(uintmax_t value, unsigned char *buf)\n+{\n+\tunsigned char varint[16];\n+\tunsigned pos = sizeof(varint) - 1;\n+\tvarint[pos] = value & 127;\n+\twhile (value >>= 7)\n+\t\tvarint[--pos] = 128 | (--value & 127);\n+\tif (buf)\n+\t\tmemcpy(buf, varint + pos, sizeof(varint) - pos);\n+\treturn sizeof(varint) - pos;\n+}\ndiff --git a/varint.h b/varint.h\nnew file mode 100644\nindex 0000000..0321195\n--- /dev/null\n+++ b/varint.h\n@@ -0,0 +1,9 @@\n+#ifndef VARINT_H\n+#define VARINT_H\n+\n+#include \"git-compat-util.h\"\n+\n+extern int encode_varint(uintmax_t, unsigned char *);\n+extern uintmax_t decode_varint(const unsigned char **);\n+\n+#endif /* VARINT_H */\n-- \n1.7.10.rc4.54.g1d5dd3\n"},{"id":"188452","messageId":"1333493596-14202-3-git-send-email-gitster@pobox.com","threadId":"30142","inReplyTo":"1333493596-14202-1-git-send-email-gitster@pobox.com","subject":"[PATCH 2/9] cache.h: hide on-disk index details","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-03T22:53:09Z","receivedAt":"2012-04-03T22:53:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The on-disk format of the index file is a detail whose implementation is\nneatly encapsulated in read-cache.c; there is no need to expose it to the\ngeneral public that include the cache.h header file.\n\nAlso add a prominent mark to read-cache.c to delineate the parts that deal\nwith the index file I/O routines from the remainder of the file.\n\nSigned-off-by: Junio C Hamano \n---\n cache.h | 48 ------------------------------------------------\n read-cache.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 54 insertions(+), 48 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex e5e1aa4..65a7aba 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -115,48 +115,6 @@ struct cache_time {\n \tunsigned int nsec;\n };\n \n-/*\n- * dev/ino/uid/gid/size are also just tracked to the low 32 bits\n- * Again - this is just a (very strong in practice) heuristic that\n- * the inode hasn't changed.\n- *\n- * We save the fields in big-endian order to allow using the\n- * index file over NFS transparently.\n- */\n-struct ondisk_cache_entry {\n-\tstruct cache_time ctime;\n-\tstruct cache_time mtime;\n-\tunsigned int dev;\n-\tunsigned int ino;\n-\tunsigned int mode;\n-\tunsigned int uid;\n-\tunsigned int gid;\n-\tunsigned int size;\n-\tunsigned char sha1[20];\n-\tunsigned short flags;\n-\tchar name[FLEX_ARRAY]; /* more */\n-};\n-\n-/*\n- * This struct is used when CE_EXTENDED bit is 1\n- * The struct must match ondisk_cache_entry exactly from\n- * ctime till flags\n- */\n-struct ondisk_cache_entry_extended {\n-\tstruct cache_time ctime;\n-\tstruct cache_time mtime;\n-\tunsigned int dev;\n-\tunsigned int ino;\n-\tunsigned int mode;\n-\tunsigned int uid;\n-\tunsigned int gid;\n-\tunsigned int size;\n-\tunsigned char sha1[20];\n-\tunsigned short flags;\n-\tunsigned short flags2;\n-\tchar name[FLEX_ARRAY]; /* more */\n-};\n-\n struct cache_entry {\n \tstruct cache_time ce_ctime;\n \tstruct cache_time ce_mtime;\n@@ -253,9 +211,6 @@ static inline size_t ce_namelen(const struct cache_entry *ce)\n }\n \n #define ce_size(ce) cache_entry_size(ce_namelen(ce))\n-#define ondisk_ce_size(ce) (((ce)->ce_flags & CE_EXTENDED) ? \\\n-\t\t\t ondisk_cache_entry_extended_size(ce_namelen(ce)) : \\\n-\t\t\t ondisk_cache_entry_size(ce_namelen(ce)))\n #define ce_stage(ce) ((CE_STAGEMASK & (ce)->ce_flags) >> CE_STAGESHIFT)\n #define ce_uptodate(ce) ((ce)->ce_flags & CE_UPTODATE)\n #define ce_skip_worktree(ce) ((ce)->ce_flags & CE_SKIP_WORKTREE)\n@@ -306,10 +261,7 @@ static inline unsigned int canon_mode(unsigned int mode)\n \treturn S_IFGITLINK;\n }\n \n-#define flexible_size(STRUCT,len) ((offsetof(struct STRUCT,name) + (len) + 8) & ~7)\n #define cache_entry_size(len) (offsetof(struct cache_entry,name) + (len) + 1)\n-#define ondisk_cache_entry_size(len) flexible_size(ondisk_cache_entry,len)\n-#define ondisk_cache_entry_extended_size(len) flexible_size(ondisk_cache_entry_extended,len)\n \n struct index_state {\n \tstruct cache_entry **cache;\ndiff --git a/read-cache.c b/read-cache.c\nindex 274e54b..fa8aa73 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1189,6 +1189,60 @@ static struct cache_entry *refresh_cache_entry(struct cache_entry *ce, int reall\n \treturn refresh_cache_ent(&the_index, ce, really, NULL, NULL);\n }\n \n+\n+/*****************************************************************\n+ * Index File I/O\n+ *****************************************************************/\n+\n+/*\n+ * dev/ino/uid/gid/size are also just tracked to the low 32 bits\n+ * Again - this is just a (very strong in practice) heuristic that\n+ * the inode hasn't changed.\n+ *\n+ * We save the fields in big-endian order to allow using the\n+ * index file over NFS transparently.\n+ */\n+struct ondisk_cache_entry {\n+\tstruct cache_time ctime;\n+\tstruct cache_time mtime;\n+\tunsigned int dev;\n+\tunsigned int ino;\n+\tunsigned int mode;\n+\tunsigned int uid;\n+\tunsigned int gid;\n+\tunsigned int size;\n+\tunsigned char sha1[20];\n+\tunsigned short flags;\n+\tchar name[FLEX_ARRAY]; /* more */\n+};\n+\n+/*\n+ * This struct is used when CE_EXTENDED bit is 1\n+ * The struct must match ondisk_cache_entry exactly from\n+ * ctime till flags\n+ */\n+struct ondisk_cache_entry_extended {\n+\tstruct cache_time ctime;\n+\tstruct cache_time mtime;\n+\tunsigned int dev;\n+\tunsigned int ino;\n+\tunsigned int mode;\n+\tunsigned int uid;\n+\tunsigned int gid;\n+\tunsigned int size;\n+\tunsigned char sha1[20];\n+\tunsigned short flags;\n+\tunsigned short flags2;\n+\tchar name[FLEX_ARRAY]; /* more */\n+};\n+\n+#define align_flex_name(STRUCT,len) ((offsetof(struct STRUCT,name) + (len) + 8) & ~7)\n+#define ondisk_cache_entry_size(len) align_flex_name(ondisk_cache_entry,len)\n+#define ondisk_cache_entry_extended_size(len) align_flex_name(ondisk_cache_entry_extended,len)\n+#define ondisk_ce_size(ce) (((ce)->ce_flags & CE_EXTENDED) ? \\\n+\t\t\t ondisk_cache_entry_extended_size(ce_namelen(ce)) : \\\n+\t\t\t ondisk_cache_entry_size(ce_namelen(ce)))\n+\n static int verify_hdr(struct cache_header *hdr, unsigned long size)\n {\n \tgit_SHA_CTX c;\n-- \n1.7.10.rc4.54.g1d5dd3\n"},{"id":"188451","messageId":"1333493596-14202-4-git-send-email-gitster@pobox.com","threadId":"30142","inReplyTo":"1333493596-14202-1-git-send-email-gitster@pobox.com","subject":"[PATCH 3/9] read-cache.c: allow unaligned mapping of the index file","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-03T22:53:10Z","receivedAt":"2012-04-03T22:53:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Both the on-disk format v2 and v3 pads the \"name\" field to the multiple of\neight to make sure that various quantities in network long/short type can\nbe accessed with ntohl/ntohs without having to worry about alignment, but\nthis forces us to waste disk I/O bandwidth.\n\nIntroduce ntoh_s()/ntoh_l() macros that the callers can use as if they were\nthe regular ntohs()/ntohl() on a field that may not be aligned correctly.\n\nSigned-off-by: Junio C Hamano \n---\n read-cache.c | 44 ++++++++++++++++++++++++++++++++------------\n 1 file changed, 32 insertions(+), 12 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex fa8aa73..d8865f5 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1285,6 +1285,26 @@ int read_index(struct index_state *istate)\n \treturn read_index_from(istate, get_index_file());\n }\n \n+#ifndef NEEDS_ALIGNED_ACCESS\n+#define ntoh_s(var) ntohs(var)\n+#define ntoh_l(var) ntohl(var)\n+#else\n+static inline uint16_t ntoh_s_force_align(void *p)\n+{\n+\tuint16_t x;\n+\tmemcpy(&x, p, sizeof(x));\n+\treturn ntohs(x);\n+}\n+static inline uint32_t ntoh_l_force_align(void *p)\n+{\n+\tuint32_t x;\n+\tmemcpy(&x, p, sizeof(x));\n+\treturn ntohl(x);\n+}\n+#define ntoh_s(var) ntoh_s_force_align(&(var))\n+#define ntoh_l(var) ntoh_l_force_align(&(var))\n+#endif\n+\n static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk)\n {\n \tstruct cache_entry *ce;\n@@ -1293,14 +1313,14 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk)\n \tunsigned int flags;\n \n \t/* On-disk flags are just 16 bits */\n-\tflags = ntohs(ondisk->flags);\n+\tflags = ntoh_s(ondisk->flags);\n \tlen = flags & CE_NAMEMASK;\n \n \tif (flags & CE_EXTENDED) {\n \t\tstruct ondisk_cache_entry_extended *ondisk2;\n \t\tint extended_flags;\n \t\tondisk2 = (struct ondisk_cache_entry_extended *)ondisk;\n-\t\textended_flags = ntohs(ondisk2->flags2) << 16;\n+\t\textended_flags = ntoh_s(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 \t\t\tdie(\"Unknown index entry format %08x\", extended_flags);\n@@ -1315,16 +1335,16 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk)\n \n \tce = xmalloc(cache_entry_size(len));\n \n-\tce->ce_ctime.sec = ntohl(ondisk->ctime.sec);\n-\tce->ce_mtime.sec = ntohl(ondisk->mtime.sec);\n-\tce->ce_ctime.nsec = ntohl(ondisk->ctime.nsec);\n-\tce->ce_mtime.nsec = ntohl(ondisk->mtime.nsec);\n-\tce->ce_dev = ntohl(ondisk->dev);\n-\tce->ce_ino = ntohl(ondisk->ino);\n-\tce->ce_mode = ntohl(ondisk->mode);\n-\tce->ce_uid = ntohl(ondisk->uid);\n-\tce->ce_gid = ntohl(ondisk->gid);\n-\tce->ce_size = ntohl(ondisk->size);\n+\tce->ce_ctime.sec = ntoh_l(ondisk->ctime.sec);\n+\tce->ce_mtime.sec = ntoh_l(ondisk->mtime.sec);\n+\tce->ce_ctime.nsec = ntoh_l(ondisk->ctime.nsec);\n+\tce->ce_mtime.nsec = ntoh_l(ondisk->mtime.nsec);\n+\tce->ce_dev = ntoh_l(ondisk->dev);\n+\tce->ce_ino = ntoh_l(ondisk->ino);\n+\tce->ce_mode = ntoh_l(ondisk->mode);\n+\tce->ce_uid = ntoh_l(ondisk->uid);\n+\tce->ce_gid = ntoh_l(ondisk->gid);\n+\tce->ce_size = ntoh_l(ondisk->size);\n \tce->ce_flags = flags;\n \n \thashcpy(ce->sha1, ondisk->sha1);\n-- \n1.7.10.rc4.54.g1d5dd3\n"},{"id":"188453","messageId":"1333493596-14202-5-git-send-email-gitster@pobox.com","threadId":"30142","inReplyTo":"1333493596-14202-1-git-send-email-gitster@pobox.com","subject":"[PATCH 4/9] read-cache.c: make create_from_disk() report number of bytes it consumed","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-03T22:53:11Z","receivedAt":"2012-04-03T22:53:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The function is the one that is reading from the data stream. It only is\nnatural to make it responsible for reporting this number, not the caller.\n\nSigned-off-by: Junio C Hamano \n---\n read-cache.c | 9 ++++++---\n 1 file changed, 6 insertions(+), 3 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex d8865f5..58bfb24 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1305,7 +1305,8 @@ static inline uint32_t ntoh_l_force_align(void *p)\n #define ntoh_l(var) ntoh_l_force_align(&(var))\n #endif\n \n-static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk)\n+static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n+\t\t\t\t\t unsigned long *ent_size)\n {\n \tstruct cache_entry *ce;\n \tsize_t len;\n@@ -1351,6 +1352,7 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk)\n \n \tmemcpy(ce->name, name, len);\n \tce->name[len] = '\\0';\n+\t*ent_size = ondisk_ce_size(ce);\n \treturn ce;\n }\n \n@@ -1404,12 +1406,13 @@ int read_index_from(struct index_state *istate, const char *path)\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 \n \t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);\n-\t\tce = create_from_disk(disk_ce);\n+\t\tce = create_from_disk(disk_ce, &consumed);\n \t\tset_index_entry(istate, i, ce);\n \n-\t\tsrc_offset += ondisk_ce_size(ce);\n+\t\tsrc_offset += consumed;\n \t}\n \tistate->timestamp.sec = st.st_mtime;\n \tistate->timestamp.nsec = ST_MTIME_NSEC(st);\n-- \n1.7.10.rc4.54.g1d5dd3\n"},{"id":"188456","messageId":"1333493596-14202-6-git-send-email-gitster@pobox.com","threadId":"30142","inReplyTo":"1333493596-14202-1-git-send-email-gitster@pobox.com","subject":"[PATCH 5/9] read-cache.c: report the header version we do not understand","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-03T22:53:12Z","receivedAt":"2012-04-03T22:53:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Instead of just saying \"bad index version\", report the value we read\nfrom the disk.\n\nSigned-off-by: Junio C Hamano \n---\n read-cache.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 58bfb24..2d93826 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1247,11 +1247,13 @@ static int verify_hdr(struct cache_header *hdr, unsigned long size)\n {\n \tgit_SHA_CTX c;\n \tunsigned char sha1[20];\n+\tint hdr_version;\n \n \tif (hdr->hdr_signature != htonl(CACHE_SIGNATURE))\n \t\treturn error(\"bad signature\");\n-\tif (hdr->hdr_version != htonl(2) && hdr->hdr_version != htonl(3))\n-\t\treturn error(\"bad index version\");\n+\thdr_version = ntohl(hdr->hdr_version);\n+\tif (hdr_version < 2 || 3 < 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 \tgit_SHA1_Final(sha1, &c);\n-- \n1.7.10.rc4.54.g1d5dd3\n"},{"id":"188454","messageId":"1333493596-14202-7-git-send-email-gitster@pobox.com","threadId":"30142","inReplyTo":"1333493596-14202-1-git-send-email-gitster@pobox.com","subject":"[PATCH 6/9] read-cache.c: move code to copy ondisk to incore cache to a helper function","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-03T22:53:13Z","receivedAt":"2012-04-03T22:53:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This makes the change in a later patch look less scary.\n\nSigned-off-by: Junio C Hamano \n---\n read-cache.c | 44 +++++++++++++++++++++++++-------------------\n 1 file changed, 25 insertions(+), 19 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 2d93826..82711c2 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1307,6 +1307,30 @@ static inline uint32_t ntoh_l_force_align(void *p)\n #define ntoh_l(var) ntoh_l_force_align(&(var))\n #endif\n \n+static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *ondisk,\n+\t\t\t\t\t\t unsigned int flags,\n+\t\t\t\t\t\t const char *name,\n+\t\t\t\t\t\t size_t len)\n+{\n+\tstruct cache_entry *ce = xmalloc(cache_entry_size(len));\n+\n+\tce->ce_ctime.sec = ntoh_l(ondisk->ctime.sec);\n+\tce->ce_mtime.sec = ntoh_l(ondisk->mtime.sec);\n+\tce->ce_ctime.nsec = ntoh_l(ondisk->ctime.nsec);\n+\tce->ce_mtime.nsec = ntoh_l(ondisk->mtime.nsec);\n+\tce->ce_dev = ntoh_l(ondisk->dev);\n+\tce->ce_ino = ntoh_l(ondisk->ino);\n+\tce->ce_mode = ntoh_l(ondisk->mode);\n+\tce->ce_uid = ntoh_l(ondisk->uid);\n+\tce->ce_gid = ntoh_l(ondisk->gid);\n+\tce->ce_size = ntoh_l(ondisk->size);\n+\tce->ce_flags = flags;\n+\thashcpy(ce->sha1, ondisk->sha1);\n+\tmemcpy(ce->name, name, len);\n+\tce->name[len] = '\\0';\n+\treturn ce;\n+}\n+\n static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n \t\t\t\t\t unsigned long *ent_size)\n {\n@@ -1335,25 +1359,7 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n \n \tif (len == CE_NAMEMASK)\n \t\tlen = strlen(name);\n-\n-\tce = xmalloc(cache_entry_size(len));\n-\n-\tce->ce_ctime.sec = ntoh_l(ondisk->ctime.sec);\n-\tce->ce_mtime.sec = ntoh_l(ondisk->mtime.sec);\n-\tce->ce_ctime.nsec = ntoh_l(ondisk->ctime.nsec);\n-\tce->ce_mtime.nsec = ntoh_l(ondisk->mtime.nsec);\n-\tce->ce_dev = ntoh_l(ondisk->dev);\n-\tce->ce_ino = ntoh_l(ondisk->ino);\n-\tce->ce_mode = ntoh_l(ondisk->mode);\n-\tce->ce_uid = ntoh_l(ondisk->uid);\n-\tce->ce_gid = ntoh_l(ondisk->gid);\n-\tce->ce_size = ntoh_l(ondisk->size);\n-\tce->ce_flags = flags;\n-\n-\thashcpy(ce->sha1, ondisk->sha1);\n-\n-\tmemcpy(ce->name, name, len);\n-\tce->name[len] = '\\0';\n+\tce = cache_entry_from_ondisk(ondisk, flags, name, len);\n \t*ent_size = ondisk_ce_size(ce);\n \treturn ce;\n }\n-- \n1.7.10.rc4.54.g1d5dd3\n"},{"id":"188457","messageId":"1333493596-14202-8-git-send-email-gitster@pobox.com","threadId":"30142","inReplyTo":"1333493596-14202-1-git-send-email-gitster@pobox.com","subject":"[PATCH 7/9] read-cache.c: move code to copy incore to ondisk cache to a helper function","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-03T22:53:14Z","receivedAt":"2012-04-03T22:53:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This makes the change in a later patch look less scary.\n\nSigned-off-by: Junio C Hamano \n---\n read-cache.c | 26 +++++++++++++++++---------\n 1 file changed, 17 insertions(+), 9 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 82711c2..c159351 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1605,13 +1605,10 @@ static void ce_smudge_racily_clean_entry(struct cache_entry *ce)\n \t}\n }\n \n-static int ce_write_entry(git_SHA_CTX *c, int fd, struct cache_entry *ce)\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 {\n-\tint size = ondisk_ce_size(ce);\n-\tstruct ondisk_cache_entry *ondisk = xcalloc(1, size);\n-\tchar *name;\n-\tint result;\n-\n \tondisk->ctime.sec = htonl(ce->ce_ctime.sec);\n \tondisk->mtime.sec = htonl(ce->ce_mtime.sec);\n \tondisk->ctime.nsec = htonl(ce->ce_ctime.nsec);\n@@ -1628,10 +1625,21 @@ static int ce_write_entry(git_SHA_CTX *c, int fd, struct cache_entry *ce)\n \t\tstruct ondisk_cache_entry_extended *ondisk2;\n \t\tondisk2 = (struct ondisk_cache_entry_extended *)ondisk;\n \t\tondisk2->flags2 = htons((ce->ce_flags & CE_EXTENDED_FLAGS) >> 16);\n-\t\tname = ondisk2->name;\n+\t\treturn ondisk2->name;\n \t}\n-\telse\n-\t\tname = ondisk->name;\n+\telse {\n+\t\treturn ondisk->name;\n+\t}\n+}\n+\n+static int ce_write_entry(git_SHA_CTX *c, int fd, struct cache_entry *ce)\n+{\n+\tint size = ondisk_ce_size(ce);\n+\tstruct ondisk_cache_entry *ondisk = xcalloc(1, size);\n+\tchar *name;\n+\tint result;\n+\n+\tname = copy_cache_entry_to_ondisk(ondisk, ce);\n \tmemcpy(name, ce->name, ce_namelen(ce));\n \n \tresult = ce_write(c, fd, ondisk, size);\n-- \n1.7.10.rc4.54.g1d5dd3\n"},{"id":"188458","messageId":"1333493596-14202-9-git-send-email-gitster@pobox.com","threadId":"30142","inReplyTo":"1333493596-14202-1-git-send-email-gitster@pobox.com","subject":"[PATCH 8/9] read-cache.c: read prefix-compressed names in index on-disk version v4","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-03T22:53:15Z","receivedAt":"2012-04-03T22:53:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Because the entries are sorted by path, adjacent entries in the index tend\nto share the leading components of them, and it makes sense to only store\nthe differences in later entries. In the v4 on-disk format of the index,\neach on-disk cache entry stores the number of bytes to be stripped from\nthe end of the previous name, and the bytes to append to the result, to\ncome up with its name.\n\nSigned-off-by: Junio C Hamano \n---\n read-cache.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++-------\n 1 file changed, 51 insertions(+), 7 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex c159351..1c173f7 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -12,6 +12,8 @@\n #include \"commit.h\"\n #include \"blob.h\"\n #include \"resolve-undo.h\"\n+#include \"strbuf.h\"\n+#include \"varint.h\"\n \n static struct cache_entry *refresh_cache_entry(struct cache_entry *ce, int really);\n \n@@ -1236,6 +1238,7 @@ struct ondisk_cache_entry_extended {\n \tchar name[FLEX_ARRAY]; /* more */\n };\n \n+/* These are only used for v3 or lower */\n #define align_flex_name(STRUCT,len) ((offsetof(struct STRUCT,name) + (len) + 8) & ~7)\n #define ondisk_cache_entry_size(len) align_flex_name(ondisk_cache_entry,len)\n #define ondisk_cache_entry_extended_size(len) align_flex_name(ondisk_cache_entry_extended,len)\n@@ -1252,7 +1255,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 || 3 < hdr_version)\n+\tif (hdr_version < 2 || 4 < 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@@ -1331,8 +1334,30 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on\n \treturn ce;\n }\n \n+/*\n+ * Adjacent cache entries tend to share the leading paths, so it makes\n+ * sense to only store the differences in later entries. In the v4\n+ * on-disk format of the index, each on-disk cache entry stores the\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+{\n+\tconst unsigned char *ep, *cp = (const unsigned char *)cp_;\n+\tsize_t len = decode_varint(&cp);\n+\n+\tif (name->len < len)\n+\t\tdie(\"malformed name field in the index\");\n+\tstrbuf_remove(name, name->len - len, len);\n+\tfor (ep = cp; *ep; ep++)\n+\t\t; /* find the end */\n+\tstrbuf_add(name, cp, ep - cp);\n+\treturn (const char *)ep + 1 - cp_;\n+}\n+\n static 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 unsigned long *ent_size,\n+\t\t\t\t\t struct strbuf *previous_name)\n {\n \tstruct cache_entry *ce;\n \tsize_t len;\n@@ -1357,10 +1382,22 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk,\n \telse\n \t\tname = ondisk->name;\n \n-\tif (len == CE_NAMEMASK)\n-\t\tlen = strlen(name);\n-\tce = cache_entry_from_ondisk(ondisk, flags, name, len);\n-\t*ent_size = ondisk_ce_size(ce);\n+\tif (!previous_name) {\n+\t\t/* v3 and earlier */\n+\t\tif (len == CE_NAMEMASK)\n+\t\t\tlen = strlen(name);\n+\t\tce = cache_entry_from_ondisk(ondisk, flags, name, len);\n+\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\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+\n+\t\t*ent_size = (name - ((char *)ondisk)) + consumed;\n+\t}\n \treturn ce;\n }\n \n@@ -1373,6 +1410,7 @@ int read_index_from(struct index_state *istate, const char *path)\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 \terrno = EBUSY;\n \tif (istate->initialized)\n@@ -1410,6 +1448,11 @@ 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 (hdr->hdr_version == htonl(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@@ -1417,11 +1460,12 @@ 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);\n+\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 \t}\n+\tstrbuf_release(&previous_name_buf);\n \tistate->timestamp.sec = st.st_mtime;\n \tistate->timestamp.nsec = ST_MTIME_NSEC(st);\n \n-- \n1.7.10.rc4.54.g1d5dd3\n"},{"id":"188455","messageId":"1333493596-14202-10-git-send-email-gitster@pobox.com","threadId":"30142","inReplyTo":"1333493596-14202-1-git-send-email-gitster@pobox.com","subject":"[PATCH 9/9] read-cache.c: write index v4 format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-03T22:53:16Z","receivedAt":"2012-04-03T22:53:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Signed-off-by: Junio C Hamano \n---\n builtin/update-index.c | 2 ++\n cache.h | 4 ++++\n config.c | 11 ++++++++++\n environment.c | 1 +\n read-cache.c | 56 ++++++++++++++++++++++++++++++++++++++++--------\n 5 files changed, 65 insertions(+), 9 deletions(-)\n\ndiff --git a/builtin/update-index.c b/builtin/update-index.c\nindex a6a23fa..b663f45 100644\n--- a/builtin/update-index.c\n+++ b/builtin/update-index.c\n@@ -791,6 +791,8 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)\n \t\t\t\"(for porcelains) forget saved unresolved conflicts\",\n \t\t\tPARSE_OPT_NOARG | PARSE_OPT_NONEG,\n \t\t\tresolve_undo_clear_callback},\n+\t\tOPT_INTEGER(0, \"index-format\", &preferred_index_format,\n+\t\t\t \"write index in this format\"),\n \t\tOPT_END()\n \t};\n \ndiff --git a/cache.h b/cache.h\nindex 65a7aba..bdec32c 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -105,6 +105,9 @@ struct cache_header {\n \tunsigned int hdr_entries;\n };\n \n+#define SUPPORTED_INDEX_FORMAT_LB 2\n+#define SUPPORTED_INDEX_FORMAT_UB 4\n+\n /*\n * The \"cache_time\" is just the low 32 bits of the\n * time. It doesn't matter if it overflows - we only\n@@ -537,6 +540,7 @@ extern int has_symlinks;\n extern int minimum_abbrev, default_abbrev;\n extern int ignore_case;\n extern int assume_unchanged;\n+extern int preferred_index_format;\n extern int prefer_symlink_refs;\n extern int log_all_ref_updates;\n extern int warn_ambiguous_refs;\ndiff --git a/config.c b/config.c\nindex 68d3294..0244a85 100644\n--- a/config.c\n+++ b/config.c\n@@ -564,6 +564,17 @@ static int git_default_core_config(const char *var, const char *value)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.indexformat\")) {\n+\t\tint val = git_config_int(var, value);\n+\t\tif (val < SUPPORTED_INDEX_FORMAT_LB ||\n+\t\t SUPPORTED_INDEX_FORMAT_UB < val)\n+\t\t\treturn error(\"%s not in supported range: %d..%d\",\n+\t\t\t\t var, SUPPORTED_INDEX_FORMAT_LB,\n+\t\t\t\t SUPPORTED_INDEX_FORMAT_UB);\n+\t\tpreferred_index_format = val;\n+\t\treturn 0;\n+\t}\n+\n \tif (!strcmp(var, \"core.quotepath\")) {\n \t\tquote_path_fully = git_config_bool(var, value);\n \t\treturn 0;\ndiff --git a/environment.c b/environment.c\nindex c93b8f4..4ecf8e6 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -20,6 +20,7 @@ int has_symlinks = 1;\n int minimum_abbrev = 4, default_abbrev = 7;\n int ignore_case;\n int assume_unchanged;\n+int preferred_index_format;\n int prefer_symlink_refs;\n int is_bare_repository_cfg = -1; /* unspecified */\n int log_all_ref_updates = -1; /* unspecified */\ndiff --git a/read-cache.c b/read-cache.c\nindex 1c173f7..fdac89a 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1676,15 +1676,45 @@ static char *copy_cache_entry_to_ondisk(struct ondisk_cache_entry *ondisk,\n \t}\n }\n \n-static int ce_write_entry(git_SHA_CTX *c, int fd, struct cache_entry *ce)\n+static int ce_write_entry(git_SHA_CTX *c, int fd, struct cache_entry *ce,\n+\t\t\t struct strbuf *previous_name)\n {\n-\tint size = ondisk_ce_size(ce);\n-\tstruct ondisk_cache_entry *ondisk = xcalloc(1, size);\n+\tint size;\n+\tstruct ondisk_cache_entry *ondisk;\n \tchar *name;\n \tint result;\n \n-\tname = copy_cache_entry_to_ondisk(ondisk, ce);\n-\tmemcpy(name, ce->name, ce_namelen(ce));\n+\tif (!previous_name) {\n+\t\tsize = ondisk_ce_size(ce);\n+\t\tondisk = xcalloc(1, size);\n+\t\tname = copy_cache_entry_to_ondisk(ondisk, ce);\n+\t\tmemcpy(name, ce->name, ce_namelen(ce));\n+\t} else {\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\tif (ce->ce_flags & CE_EXTENDED)\n+\t\t\tsize = offsetof(struct ondisk_cache_entry_extended, name);\n+\t\telse\n+\t\t\tsize = offsetof(struct ondisk_cache_entry, name);\n+\t\tsize += prefix_size + (ce_namelen(ce) - common + 1);\n+\n+\t\tondisk = xcalloc(1, size);\n+\t\tname = copy_cache_entry_to_ondisk(ondisk, ce);\n+\t\tmemcpy(name, to_remove_vi, prefix_size);\n+\t\tmemcpy(name + prefix_size, 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}\n \n \tresult = ce_write(c, fd, ondisk, size);\n \tfree(ondisk);\n@@ -1720,10 +1750,11 @@ int write_index(struct index_state *istate, int newfd)\n {\n \tgit_SHA_CTX c;\n \tstruct cache_header hdr;\n-\tint i, err, removed, extended;\n+\tint i, err, removed, extended, hdr_version;\n \tstruct cache_entry **cache = istate->cache;\n \tint entries = istate->cache_nr;\n \tstruct stat st;\n+\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n \n \tfor (i = removed = extended = 0; i < entries; i++) {\n \t\tif (cache[i]->ce_flags & CE_REMOVE)\n@@ -1737,24 +1768,31 @@ int write_index(struct index_state *istate, int newfd)\n \t\t}\n \t}\n \n+\tif (preferred_index_format)\n+\t\thdr_version = preferred_index_format;\n+\telse\n+\t\thdr_version = extended ? 3 : 2;\n+\n+\n \thdr.hdr_signature = htonl(CACHE_SIGNATURE);\n-\t/* for extended format, increase version so older git won't try to read it */\n-\thdr.hdr_version = htonl(extended ? 3 : 2);\n+\thdr.hdr_version = htonl(hdr_version);\n \thdr.hdr_entries = htonl(entries - removed);\n \n \tgit_SHA1_Init(&c);\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 \tfor (i = 0; i < entries; i++) {\n \t\tstruct cache_entry *ce = cache[i];\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 (ce_write_entry(&c, newfd, ce) < 0)\n+\t\tif (ce_write_entry(&c, newfd, ce, previous_name) < 0)\n \t\t\treturn -1;\n \t}\n+\tstrbuf_release(&previous_name_buf);\n \n \t/* Write extension data here */\n \tif (istate->cache_tree) {\n-- \n1.7.10.rc4.54.g1d5dd3\n"},{"id":"188465","messageId":"CAFfmPPOqb8Kn-LERyiLKL838DKw=X6=CTV1x0s8coPgAvNLUdw@mail.gmail.com","threadId":"30142","inReplyTo":"1333493596-14202-1-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 0/9] Prefix-compress on-disk index entries","fromName":"David Barr","fromEmail":"davidbarr@google.com","sentAt":"2012-04-04T01:44:24Z","receivedAt":"2012-04-04T01:44:24Z","isPatch":true,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"On Wed, Apr 4, 2012 at 8:53 AM, Junio C Hamano wrote:\n> This is still rough, but with this patch I am getting:\n>\n>    $ ls -l .git/index*\n>    -rw-r----- 1 jch eng 25586488 2012-04-03 15:27 .git/index\n>    -rw-r----- 1 jch eng 14654328 2012-04-03 15:38 .git/index-4\n>\n> in a clone of WebKit repository that has 183175 paths.\n>\n> With hot-cache with no local modification:\n>\n>    $ time sh -c 'GIT_INDEX_FILE=.git/index-4 git diff'\n>    real  0m0.469s\n>    user  0m0.130s\n>    sys   0m0.330s\n>\n>    $ time sh -c 'git diff'\n>    real  0m0.677s\n>    user  0m0.290s\n>    sys   0m0.370s\n>\n> which is mesuring the time needed to read of the index into in-core\n> structure and comparing the cached stat information taken from lstat(2).\n>\n> The updated format is not documented yet, as I didn't intend (and I still\n> am not committed) to declare a change along this line the official \"v4\"\n> format; I was merely being curious to see how much improvements we can get\n> from a trivial approach like this.\n\nAs I am hacking on WebKit daily, I'll try out this series and give feedback.\n\n--\nDavid Barr\n"},{"id":"188485","messageId":"CACsJy8A+cJtzKdqJSWbmjT1LgP10LB69-NHfOv8S6BusGcMeFw@mail.gmail.com","threadId":"30142","inReplyTo":"1333493596-14202-1-git-send-email-gitster@pobox.com","subject":"Re: [PATCH 0/9] Prefix-compress on-disk index entries","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-04T12:34:20Z","receivedAt":"2012-04-04T12:34:20Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Apr 4, 2012 at 5:53 AM, Junio C Hamano wrote:\n> This is still rough,\n\nbut nice cleanups\n\n> but with this patch I am getting:\n>\n>    $ ls -l .git/index*\n>    -rw-r----- 1 jch eng 25586488 2012-04-03 15:27 .git/index\n>    -rw-r----- 1 jch eng 14654328 2012-04-03 15:38 .git/index-4\n>\n> in a clone of WebKit repository that has 183175 paths.\n>\n> With hot-cache with no local modification:\n>\n>    $ time sh -c 'GIT_INDEX_FILE=.git/index-4 git diff'\n>    real  0m0.469s\n>    user  0m0.130s\n>    sys   0m0.330s\n>\n>    $ time sh -c 'git diff'\n>    real  0m0.677s\n>    user  0m0.290s\n>    sys   0m0.370s\n\nI wonder what causes user time drop from .29s to .13s here. I think\nthe main patch should increase computation, even only slightly, not\nless. Or is it noise?\n\n> The updated format is not documented yet, as I didn't intend (and I still\n> am not committed) to declare a change along this line the official \"v4\"\n> format; I was merely being curious to see how much improvements we can get\n> from a trivial approach like this.\n\nAnything else you have in mind for v4? Any chance we can adopt crc32\ninstead of sha-1? We could divide the index into many smaller parts\nfor checksum, for example one crc32 every 100 entries, and one (or\nsha-1) for each extension. It should not complicate the code too much.\n-- \nDuy\n"},{"id":"188490","messageId":"7v7gxvbjfy.fsf@alter.siamese.dyndns.org","threadId":"30142","inReplyTo":"CAFfmPPOqb8Kn-LERyiLKL838DKw=X6=CTV1x0s8coPgAvNLUdw@mail.gmail.com","subject":"Re: [PATCH 0/9] Prefix-compress on-disk index entries","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-04T15:33:37Z","receivedAt":"2012-04-04T15:33:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Barr writes:\n\n> As I am hacking on WebKit daily, I'll try out this series and give feedback.\n\nThanks; the write-out codepath needs to learn to keep the format of the\nindex it originally read from when there is no preferred format defined, I\nthink, as I do not think core.indexformat configuration is particularly a\ngood idea, by the way.\n"},{"id":"188496","messageId":"7vy5qba10j.fsf@alter.siamese.dyndns.org","threadId":"30142","inReplyTo":"7v7gxvbjfy.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 0/9] Prefix-compress on-disk index entries","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-04T16:57:00Z","receivedAt":"2012-04-04T16:57:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> David Barr writes:\n>\n>> As I am hacking on WebKit daily, I'll try out this series and give feedback.\n>\n> Thanks; the write-out codepath needs to learn to keep the format of the\n> index it originally read from when there is no preferred format defined, I\n> think, as I do not think core.indexformat configuration is particularly a\n> good idea, by the way.\n\nHere is the first of two patches that should replace 9/9 (write index v4 format)\nof the yesterday's 9-patch series.\n\n-- >8 --\nSubject: [PATCH 1/2] read-cache.c: write prefix-compressed names in the index\n\nTeach the code to write the index in the v4 on-disk format.\n\nRecord the format version of the on-disk index we read from in the\nindex_state, and use the format when writing the new index out.\n\nSigned-off-by: Junio C Hamano \n---\n cache.h | 4 ++++\n read-cache.c | 64 +++++++++++++++++++++++++++++++++++++++++++++++++---------\n 2 files changed, 58 insertions(+), 10 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 65a7aba..a3f1279 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -105,6 +105,9 @@ struct cache_header {\n \tunsigned int hdr_entries;\n };\n \n+#define INDEX_FORMAT_LB 2\n+#define INDEX_FORMAT_UB 4\n+\n /*\n * The \"cache_time\" is just the low 32 bits of the\n * time. It doesn't matter if it overflows - we only\n@@ -265,6 +268,7 @@ static inline unsigned int canon_mode(unsigned int mode)\n \n struct index_state {\n \tstruct cache_entry **cache;\n+\tunsigned int version;\n \tunsigned int cache_nr, cache_alloc, cache_changed;\n \tstruct string_list *resolve_undo;\n \tstruct cache_tree *cache_tree;\ndiff --git a/read-cache.c b/read-cache.c\nindex 1c173f7..adda1da 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1196,6 +1196,8 @@ static struct cache_entry *refresh_cache_entry(struct cache_entry *ce, int reall\n * Index File I/O\n *****************************************************************/\n \n+#define INDEX_FORMAT_DEFAULT 3\n+\n /*\n * dev/ino/uid/gid/size are also just tracked to the low 32 bits\n * Again - this is just a (very strong in practice) heuristic that\n@@ -1443,12 +1445,13 @@ int read_index_from(struct index_state *istate, const char *path)\n \tif (verify_hdr(hdr, mmap_size) < 0)\n \t\tgoto unmap;\n \n+\tistate->version = ntohl(hdr->hdr_version);\n \tistate->cache_nr = ntohl(hdr->hdr_entries);\n \tistate->cache_alloc = alloc_nr(istate->cache_nr);\n \tistate->cache = xcalloc(istate->cache_alloc, sizeof(struct cache_entry *));\n \tistate->initialized = 1;\n \n-\tif (hdr->hdr_version == htonl(4))\n+\tif (istate->version == 4)\n \t\tprevious_name = &previous_name_buf;\n \telse\n \t\tprevious_name = NULL;\n@@ -1676,15 +1679,45 @@ static char *copy_cache_entry_to_ondisk(struct ondisk_cache_entry *ondisk,\n \t}\n }\n \n-static int ce_write_entry(git_SHA_CTX *c, int fd, struct cache_entry *ce)\n+static int ce_write_entry(git_SHA_CTX *c, int fd, struct cache_entry *ce,\n+\t\t\t struct strbuf *previous_name)\n {\n-\tint size = ondisk_ce_size(ce);\n-\tstruct ondisk_cache_entry *ondisk = xcalloc(1, size);\n+\tint size;\n+\tstruct ondisk_cache_entry *ondisk;\n \tchar *name;\n \tint result;\n \n-\tname = copy_cache_entry_to_ondisk(ondisk, ce);\n-\tmemcpy(name, ce->name, ce_namelen(ce));\n+\tif (!previous_name) {\n+\t\tsize = ondisk_ce_size(ce);\n+\t\tondisk = xcalloc(1, size);\n+\t\tname = copy_cache_entry_to_ondisk(ondisk, ce);\n+\t\tmemcpy(name, ce->name, ce_namelen(ce));\n+\t} else {\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\tif (ce->ce_flags & CE_EXTENDED)\n+\t\t\tsize = offsetof(struct ondisk_cache_entry_extended, name);\n+\t\telse\n+\t\t\tsize = offsetof(struct ondisk_cache_entry, name);\n+\t\tsize += prefix_size + (ce_namelen(ce) - common + 1);\n+\n+\t\tondisk = xcalloc(1, size);\n+\t\tname = copy_cache_entry_to_ondisk(ondisk, ce);\n+\t\tmemcpy(name, to_remove_vi, prefix_size);\n+\t\tmemcpy(name + prefix_size, 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}\n \n \tresult = ce_write(c, fd, ondisk, size);\n \tfree(ondisk);\n@@ -1720,10 +1753,11 @@ int write_index(struct index_state *istate, int newfd)\n {\n \tgit_SHA_CTX c;\n \tstruct cache_header hdr;\n-\tint i, err, removed, extended;\n+\tint i, err, removed, extended, hdr_version;\n \tstruct cache_entry **cache = istate->cache;\n \tint entries = istate->cache_nr;\n \tstruct stat st;\n+\tstruct strbuf previous_name_buf = STRBUF_INIT, *previous_name;\n \n \tfor (i = removed = extended = 0; i < entries; i++) {\n \t\tif (cache[i]->ce_flags & CE_REMOVE)\n@@ -1737,24 +1771,34 @@ int write_index(struct index_state *istate, int newfd)\n \t\t}\n \t}\n \n+\tif (!istate->version)\n+\t\tistate->version = INDEX_FORMAT_DEFAULT;\n+\n+\t/* demote version 3 to version 2 when the latter suffices */\n+\tif (istate->version == 3 || istate->version == 2)\n+\t\tistate->version = extended ? 3 : 2;\n+\n+\thdr_version = istate->version;\n+\n \thdr.hdr_signature = htonl(CACHE_SIGNATURE);\n-\t/* for extended format, increase version so older git won't try to read it */\n-\thdr.hdr_version = htonl(extended ? 3 : 2);\n+\thdr.hdr_version = htonl(hdr_version);\n \thdr.hdr_entries = htonl(entries - removed);\n \n \tgit_SHA1_Init(&c);\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 \tfor (i = 0; i < entries; i++) {\n \t\tstruct cache_entry *ce = cache[i];\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 (ce_write_entry(&c, newfd, ce) < 0)\n+\t\tif (ce_write_entry(&c, newfd, ce, previous_name) < 0)\n \t\t\treturn -1;\n \t}\n+\tstrbuf_release(&previous_name_buf);\n \n \t/* Write extension data here */\n \tif (istate->cache_tree) {\n-- \n1.7.10.rc4.54.g1d5dd3\n\n \n"},{"id":"188497","messageId":"7vty0za0xn.fsf_-_@alter.siamese.dyndns.org","threadId":"30142","inReplyTo":"7vy5qba10j.fsf@alter.siamese.dyndns.org","subject":"[PATCH 2/2] update-index: upgrade/downgrade on-disk index version","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-04T16:58:44Z","receivedAt":"2012-04-04T16:58:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"With the \"--index-version \" parameter, write the index out in the\nspecified version. With this, an index file that is written in newer\nformat (say v4) can be downgraded to be read by older versions of Git.\n\nSigned-off-by: Junio C Hamano \n---\n * And this is the second of the two-patch series to replace 9/9 from\n yesterday's series.\n\n Documentation/git-update-index.txt | 6 +++++-\n builtin/update-index.c | 14 ++++++++++++++\n 2 files changed, 19 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/git-update-index.txt b/Documentation/git-update-index.txt\nindex a3081f4..fd9103b 100644\n--- a/Documentation/git-update-index.txt\n+++ b/Documentation/git-update-index.txt\n@@ -19,7 +19,7 @@ SYNOPSIS\n \t [--ignore-submodules]\n \t [--really-refresh] [--unresolve] [--again | -g]\n \t [--info-only] [--index-info]\n-\t [-z] [--stdin]\n+\t [-z] [--stdin] [--index-version ]\n \t [--verbose]\n \t [--] [...]\n \n@@ -143,6 +143,10 @@ you will need to handle the situation manually.\n --verbose::\n Report what is being added and removed from index.\n \n+--index-version ::\n+\tWrite the resulting index out in the named on-disk format version.\n+\tThe current default version is 2.\n+\n -z::\n \tOnly meaningful with `--stdin` or `--index-info`; paths are\n \tseparated with NUL character instead of LF.\ndiff --git a/builtin/update-index.c b/builtin/update-index.c\nindex a6a23fa..5f038d6 100644\n--- a/builtin/update-index.c\n+++ b/builtin/update-index.c\n@@ -708,6 +708,7 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)\n \tint newfd, entries, has_errors = 0, line_termination = '\\n';\n \tint read_from_stdin = 0;\n \tint prefix_length = prefix ? strlen(prefix) : 0;\n+\tint preferred_index_format = 0;\n \tchar set_executable_bit = 0;\n \tstruct refresh_params refresh_args = {0, &has_errors};\n \tint lock_error = 0;\n@@ -791,6 +792,8 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)\n \t\t\t\"(for porcelains) forget saved unresolved conflicts\",\n \t\t\tPARSE_OPT_NOARG | PARSE_OPT_NONEG,\n \t\t\tresolve_undo_clear_callback},\n+\t\tOPT_INTEGER(0, \"index-version\", &preferred_index_format,\n+\t\t\t \"write index in this format\"),\n \t\tOPT_END()\n \t};\n \n@@ -851,6 +854,17 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)\n \t\t}\n \t}\n \targc = parse_options_end(&ctx);\n+\tif (preferred_index_format) {\n+\t\tif (preferred_index_format < INDEX_FORMAT_LB ||\n+\t\t INDEX_FORMAT_UB < preferred_index_format)\n+\t\t\tdie(\"index-version %d not in range: %d..%d\",\n+\t\t\t preferred_index_format,\n+\t\t\t INDEX_FORMAT_LB, INDEX_FORMAT_UB);\n+\n+\t\tif (the_index.version != preferred_index_format)\n+\t\t\tactive_cache_changed = 1;\n+\t\tthe_index.version = preferred_index_format;\n+\t}\n \n \tif (read_from_stdin) {\n \t\tstruct strbuf buf = STRBUF_INIT, nbuf = STRBUF_INIT;\n-- \n1.7.10.rc4.54.g1d5dd3\n"},{"id":"188508","messageId":"7vpqbn8hgr.fsf@alter.siamese.dyndns.org","threadId":"30142","inReplyTo":"CACsJy8A+cJtzKdqJSWbmjT1LgP10LB69-NHfOv8S6BusGcMeFw@mail.gmail.com","subject":"Re: [PATCH 0/9] Prefix-compress on-disk index entries","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-04T18:44:36Z","receivedAt":"2012-04-04T18:44:36Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyen Thai Ngoc Duy writes:\n\n> On Wed, Apr 4, 2012 at 5:53 AM, Junio C Hamano wrote:\n> ...\n> I wonder what causes user time drop from .29s to .13s here. I think\n> the main patch should increase computation, even only slightly, not\n> less.\n\nThe main patch reduced the amount of the data needs to be sent to the\nmachinery to checksum and write to disk by about 45%, saving both I/O\nand computation.\n\nThis is a tangent, but I wonder why we are not using csum-file API to do\nthis (I know the dircache code came first way before csum-file; I am\nwondering why we haven't rewritten the codepath using it later).\n\n> Anything else you have in mind for v4? Any chance we can adopt crc32\n> instead of sha-1?\n\nI am not interested in sacrificing integrity over unproven/unmeasured\nperformance \"issues\" on SHA-1, so I am not planning to experiment with\nsuch a change myself. The choice of hashing algorithm from my point of\nview is the least interesting part.\n"},{"id":"188646","messageId":"CAFfmPPNHkK3SB8cGjfJiVoQoSg2OLL8B5--mwH8HShhJ1WGy2g@mail.gmail.com","threadId":"30142","inReplyTo":"7vpqbn8hgr.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 0/9] Prefix-compress on-disk index entries","fromName":"David Barr","fromEmail":"davidbarr@google.com","sentAt":"2012-04-06T08:41:46Z","receivedAt":"2012-04-06T08:41:46Z","isPatch":true,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"On Thu, Apr 5, 2012 at 4:44 AM, Junio C Hamano wrote:\n> Nguyen Thai Ngoc Duy writes:\n>\n>> On Wed, Apr 4, 2012 at 5:53 AM, Junio C Hamano wrote:\n>> ...\n>> I wonder what causes user time drop from .29s to .13s here. I think\n>> the main patch should increase computation, even only slightly, not\n>> less.\n>\n> The main patch reduced the amount of the data needs to be sent to the\n> machinery to checksum and write to disk by about 45%, saving both I/O\n> and computation.\n\nI hacked together a quick patch to try predictive coding the other\nfields of the index. I got a further 34% improvement in size over\nthis series. Patches to come. I just used the previous cache entry as\nthe predictor and reused varint.h together with zigzag encoding[1].\n\nThat's a total improvement in size over v2 of 62%.\n\n[1] https://developers.google.com/protocol-buffers/docs/encoding#types\n"},{"id":"190228","messageId":"xmqqzk9w93zu.fsf@junio.mtv.corp.google.com","threadId":"30142","inReplyTo":"1333493596-14202-1-git-send-email-gitster@pobox.com","subject":"[PATCH 1/2] unpack-trees: preserve the index file version of original","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-27T22:58:13Z","receivedAt":"2012-04-27T22:58:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Otherwise \"git checkout $other_branch\" (or even \"git checkout HEAD\")\nwould end up writing the index out in the default format.\n\nSigned-off-by: Junio C Hamano \n---\n * The first of a two patch series to update the jc/index-v4 series:\n http://thread.gmane.org/gmane.comp.version-control.git/194660\n\n unpack-trees.c | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 7c9ecf6..2a037d6 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -1020,6 +1020,7 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \to->result.initialized = 1;\n \to->result.timestamp.sec = o->src_index->timestamp.sec;\n \to->result.timestamp.nsec = o->src_index->timestamp.nsec;\n+\to->result.version = o->src_index->version;\n \to->merge_size = len;\n \tmark_all_ce_unused(o->src_index);\n \n-- \n1.7.10.526.gb0571\n"},{"id":"190230","messageId":"xmqqpqas93sa.fsf_-_@junio.mtv.corp.google.com","threadId":"30142","inReplyTo":"xmqqzk9w93zu.fsf@junio.mtv.corp.google.com","subject":"[PATCH 2/2] index-v4: document the entry format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-27T23:02:45Z","receivedAt":"2012-04-27T23:02:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Document the format so that others can learn from and build on top of\nthe series.\n\nSigned-off-by: Junio C Hamano \n---\n Documentation/technical/index-format.txt | 13 +++++++++++++\n 1 file changed, 13 insertions(+)\n\ndiff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt\nindex 8930b3f..9d25b30 100644\n--- a/Documentation/technical/index-format.txt\n+++ b/Documentation/technical/index-format.txt\n@@ -113,9 +113,22 @@ GIT index format\n are encoded in 7-bit ASCII and the encoding cannot contain a NUL\n byte (iow, this is a UNIX pathname).\n \n+ (Version 4) In version 4, the entry path name is prefix-compressed\n+ relative to the path name for the previous entry (the very first\n+ entry is encoded as if the path name for the previous entry is an\n+ empty string). At the beginning of an entry, an integer N in the\n+ variable width encoding (the same encoding as the offset is encoded\n+ for OFS_DELTA pack entries; see pack-format.txt) is stored, followed\n+ by a NUL-terminated string S. Removing N bytes from the end of the\n+ path name for the previous entry, and replacing it with the string S\n+ yields the path name for this entry.\n+\n 1-8 nul bytes as necessary to pad the entry to a multiple of eight bytes\n while keeping the name NUL-terminated.\n \n+ (Version 4) In version 4, the padding after the pathname does not\n+ exist.\n+\n == Extensions\n \n === Cached tree\n-- \n1.7.10.526.gb0571\n"},{"id":"190318","messageId":"87vckhuofj.fsf@thomas.inf.ethz.ch","threadId":"30142","inReplyTo":"xmqqpqas93sa.fsf_-_@junio.mtv.corp.google.com","subject":"Re: [PATCH 2/2] index-v4: document the entry format","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-04-30T17:20:16Z","receivedAt":"2012-04-30T17:20:16Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Hi Junio,\n\nI seem to have completely missed the earlier series at\n\n http://thread.gmane.org/gmane.comp.version-control.git/194660\n\nMy bad.\n\nThomas has been working on a prototype converter over the past few days,\nwith results similar to (but not quite as good as) your numbers\n\n $ ls -l .git/index*\n -rw-r----- 1 jch eng 25586488 2012-04-03 15:27 .git/index\n -rw-r----- 1 jch eng 14654328 2012-04-03 15:38 .git/index-4\n\nwhile taking a different approach with different tradeoffs.\n\nNevertheless...\n\n> + (Version 4) In version 4, the entry path name is prefix-compressed\n> + relative to the path name for the previous entry (the very first\n> + entry is encoded as if the path name for the previous entry is an\n> + empty string). At the beginning of an entry, an integer N in the\n> + variable width encoding (the same encoding as the offset is encoded\n> + for OFS_DELTA pack entries; see pack-format.txt) is stored, followed\n> + by a NUL-terminated string S. Removing N bytes from the end of the\n> + path name for the previous entry, and replacing it with the string S\n> + yields the path name for this entry.\n[..]\n> + (Version 4) In version 4, the padding after the pathname does not\n> + exist.\n\nI think there are actually several separate ideas here:\n\n* The prefix compression. Thomas is not using this idea; we've been\n toying with making the index bisectable (within each directory) for\n fast single-entry lookups, which inherently conflicts with this. The\n directory-like layout partially achieves the same (elides common path\n components).\n\n* The varint encoding (or offset encoding, but \"varint\" is something you\n can google :-). David suggested using it on stat() data, combined\n with zigzag encoding and delta against the first entry in the\n directory, which gives some good compression results. Profiling will\n have to say whether the extra decoding effort is worth the space\n savings.\n\n* The lack of variable padding, which is a good idea -- in any case I\n seem to remember Shawn complaining about it.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"190390","messageId":"7vlilcczzb.fsf@alter.siamese.dyndns.org","threadId":"30142","inReplyTo":"87vckhuofj.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH 2/2] index-v4: document the entry format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-01T04:00:24Z","receivedAt":"2012-05-01T04:00:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> I seem to have completely missed the earlier series at\n>\n> http://thread.gmane.org/gmane.comp.version-control.git/194660\n>\n> My bad.\n>\n> Thomas has been working on a prototype converter over the past few days,\n> with results similar to (but not quite as good as) your numbers\n\nThe \"entry-shrinkage\" v4 itself is an afternoon hack (even though it is a\ngood hack), and any design that would not come close to its result is not\nworth considering. It is good to hear that the student is making progress\nlearning.\n\n> I think there are actually several separate ideas here:\n>\n> * The prefix compression. Thomas is not using this idea; we've been\n> toying with making the index bisectable (within each directory) for\n> fast single-entry lookups, which inherently conflicts with this. The\n> directory-like layout partially achieves the same (elides common path\n> components).\n>\n> * The varint encoding (or offset encoding, but \"varint\" is something you\n> can google :-). David suggested using it on stat() data, combined\n> with zigzag encoding and delta against the first entry in the\n> directory, which gives some good compression results. Profiling will\n> have to say whether the extra decoding effort is worth the space\n> savings.\n>\n> * The lack of variable padding, which is a good idea -- in any case I\n> seem to remember Shawn complaining about it.\n\nI am planning to merge this series early to 'master', before the GSoC\nstudent really starts working on the code, perhaps by this Wednesday. The\nearlier parts of this series refactor code to make things easier to\nmodify, and the later parts of it demonstrate by example both:\n\n (1) how the backward compatibility must be handled at the design level\n [*1*]; and\n\n (2) how such a design can be coded cleanly at the implementation level.\n\nThe hope is that this will give a solidified base to build whatever new\nwork on top of (perhaps call it v5). I do not mind David's further work\nbuilt on top of this series, but I think the entry-shrinkage design for v4\nis good enough as-is. I am afraid that letting the code slushy again at\nthis point may make your student's work unnecessarily more cumbersome.\n\nHow do you want to proceed?\n\n\n[Footnote]\n\n*1* Here are the minimum requirements.\n\n - you can read both old and new formats (obviously);\n\n - by default you write out in the same version you read the original;\n\n - have a single simple command to explicitly specify what format to\n write out; and\n\n - make sure that the new format is something older readers can\n reliably notice is new and beyond the version they support\n"},{"id":"190494","messageId":"87ipgfd1c7.fsf@thomas.inf.ethz.ch","threadId":"30142","inReplyTo":"7vlilcczzb.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/2] index-v4: document the entry format","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-05-01T21:43:20Z","receivedAt":"2012-05-01T21:43:20Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> I am planning to merge this series early to 'master', before the GSoC\n> student really starts working on the code, perhaps by this Wednesday. The\n> earlier parts of this series refactor code to make things easier to\n> modify, and the later parts of it demonstrate by example both:\n>\n> (1) how the backward compatibility must be handled at the design level\n> [*1*]; and\n>\n> (2) how such a design can be coded cleanly at the implementation level.\n>\n> The hope is that this will give a solidified base to build whatever new\n> work on top of (perhaps call it v5).\n[...]\n> How do you want to proceed?\n\nI was initially a bit reluctant to add this complexity so shortly before\nthe GSoC starts in earnest. But the cleanups are really worth it, and\nthen it's not *that* much code for a quite substantial speedup for\nwebkit.\n\nSo go ahead and merge it. Thomas can build on top, though I'm still\nhoping he'll start before you complete the merge, and learn a bit about\nbasing work on top of unmerged topics ;-)\n\n> I do not mind David's further work built on top of this series, but I\n> think the entry-shrinkage design for v4 is good enough as-is.\n\nMy impression was that David just tossed around ideas (very\nwell-researched and tested ones, but still ideas) to help Thomas.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"190512","messageId":"CACsJy8DZ4t0f_mdDJTUZvz_pBPrPTsEBxHEkYREowWm6D1ikkw@mail.gmail.com","threadId":"30142","inReplyTo":"CAFfmPPNHkK3SB8cGjfJiVoQoSg2OLL8B5--mwH8HShhJ1WGy2g@mail.gmail.com","subject":"Re: [PATCH 0/9] Prefix-compress on-disk index entries","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-05-02T01:58:50Z","receivedAt":"2012-05-02T01:58:50Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Apr 6, 2012 at 3:41 PM, David Barr wrote:\n> On Thu, Apr 5, 2012 at 4:44 AM, Junio C Hamano wrote:\n>> Nguyen Thai Ngoc Duy writes:\n>>\n>>> On Wed, Apr 4, 2012 at 5:53 AM, Junio C Hamano wrote:\n>>> ...\n>>> I wonder what causes user time drop from .29s to .13s here. I think\n>>> the main patch should increase computation, even only slightly, not\n>>> less.\n>>\n>> The main patch reduced the amount of the data needs to be sent to the\n>> machinery to checksum and write to disk by about 45%, saving both I/O\n>> and computation.\n>\n> I hacked together a quick patch to try predictive coding the other\n> fields of the index. I got a further 34% improvement in size over\n> this series. Patches to come. I just used the previous cache entry as\n> the predictor and reused varint.h together with zigzag encoding[1].\n>\n> That's a total improvement in size over v2 of 62%.\n\nHave you posted (and I missed) the patches? I'm interested in seeing\nwhat changes you made.\n\n> [1] https://developers.google.com/protocol-buffers/docs/encoding#types\n-- \nDuy\n"},{"id":"190519","messageId":"CAFfmPPOPWkUcuWRFYGk9LHCAJAbvNYK=Xk+pvSa8fbffpRDppQ@mail.gmail.com","threadId":"30142","inReplyTo":"CACsJy8DZ4t0f_mdDJTUZvz_pBPrPTsEBxHEkYREowWm6D1ikkw@mail.gmail.com","subject":"Re: [PATCH 0/9] Prefix-compress on-disk index entries","fromName":"David Barr","fromEmail":"davidbarr@google.com","sentAt":"2012-05-02T04:26:15Z","receivedAt":"2012-05-02T04:26:15Z","isPatch":true,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"On Wed, May 2, 2012 at 11:58 AM, Nguyen Thai Ngoc Duy wrote:\n> On Fri, Apr 6, 2012 at 3:41 PM, David Barr wrote:\n>> On Thu, Apr 5, 2012 at 4:44 AM, Junio C Hamano wrote:\n>>> Nguyen Thai Ngoc Duy writes:\n>>>\n>>>> On Wed, Apr 4, 2012 at 5:53 AM, Junio C Hamano wrote:\n>>>> ...\n>>>> I wonder what causes user time drop from .29s to .13s here. I think\n>>>> the main patch should increase computation, even only slightly, not\n>>>> less.\n>>>\n>>> The main patch reduced the amount of the data needs to be sent to the\n>>> machinery to checksum and write to disk by about 45%, saving both I/O\n>>> and computation.\n>>\n>> I hacked together a quick patch to try predictive coding the other\n>> fields of the index. I got a further 34% improvement in size over\n>> this series. Patches to come. I just used the previous cache entry as\n>> the predictor and reused varint.h together with zigzag encoding[1].\n>>\n>> That's a total improvement in size over v2 of 62%.\n>\n> Have you posted (and I missed) the patches? I'm interested in seeing\n> what changes you made.\n\nI haven't posted anything - my proof of concept was write-only and slow.\n\nI added a prelude with a bitmask that describes which fields differ\nwith the previous entry.\n\nFor each differing field, I encoded something like:\ndiff := this - prev;\nzigzag := (diff << 1) ^ (diff >> 31)\nraw := zigzag - 1 /* zero impossible because of mask */\nwrite_varint(raw)\n\nI also experimented with using unique sha1 prefixes but it was slow\nand probably introduces race conditions.\n\n>> [1] https://developers.google.com/protocol-buffers/docs/encoding#types\n--\nDavid Barr\n"},{"id":"190568","messageId":"CAJo=hJvFfVbYRKtPDJbd8MXKFDAyk==Sbm8oTgypbpE2O4o1=w@mail.gmail.com","threadId":"30142","inReplyTo":"7vlilcczzb.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/2] index-v4: document the entry format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-05-02T15:12:13Z","receivedAt":"2012-05-02T15:12:13Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Apr 30, 2012 at 9:00 PM, Junio C Hamano wrote:\n>> * The prefix compression.  Thomas is not using this idea; we've been\n>>   toying with making the index bisectable (within each directory) for\n>>   fast single-entry lookups, which inherently conflicts with this.  The\n>>   directory-like layout partially achieves the same (elides common path\n>>   components).\n>>\n>> * The varint encoding (or offset encoding, but \"varint\" is something you\n>>   can google :-).  David suggested using it on stat() data, combined\n>>   with zigzag encoding and delta against the first entry in the\n>>   directory, which gives some good compression results.  Profiling will\n>>   have to say whether the extra decoding effort is worth the space\n>>   savings.\n>>\n>> * The lack of variable padding, which is a good idea -- in any case I\n>>   seem to remember Shawn complaining about it.\n\nI complain about a lot of things. Here is another...\n\n> I am planning to merge this series early to 'master', before the GSoC\n> student really starts working on the code, perhaps by this Wednesday. The\n> earlier parts of this series refactor code to make things easier to\n> modify, and the later parts of it demonstrate by example both:\n\nI think this is a bad idea.\n\nFor sake of argument, lets say the GSoC project goes really well, and\nthe student creates a great implementation of (what is now) index v5.\nLets say we all agree its a great evolution of the format, the\nimplementation is sane, and there is no reason not to merge it and\nmake it the default.\n\nIf this v4 thing merges to master and you make a release from master,\nwe are potentially stuck supporting this new v4 format for the next 2\nyears, along with v5 which we want to immediately replace it. If any\nOS distro picks up a release Git that supports v4 but not v5, and\nparks it into their stable tree, the rest of the Git ecosystem (e.g.\nlibgit2, JGit) will be supporting v4 until that OS distro release dies\nand all of its users are able to move to a newer distro with a newer\nGit version.\n\nConsider my case at $DAY_JOB where we still have Git 1.7.7.3 as the\nstandard Git. Upstream has already shipped 1.7.10 and is well on its\nway to 1.7.11, but the distro choose to freeze on 1.7.7 rather\narbitrarily because that was the latest stable release version at the\ntime the distro was freezing its package sets for its own release.\nYay.\n\n\nIMHO, keep this in next to avoid releasing it until we know the\noutcome of the GSoC project. The handful of WebKit developers that use\nGit that really benefit from index v4 can use it by building and\ninstalling their own next. If they can't work `make install\nprefix=$HOME/git`, they might want to reconsider their career and\nhobby activities. And we can be sure it won't show up in a distro\nrelease, thereby avoiding us needing us to support what may turn out\nto be a dead-end index v4. The GSoC student can build on this topic\nuntil their own work arrives in your tree.\n\nIts only a few months to wait and see where \"v5\" goes. If v5 is\nsuccessful, v4 will just be a minor footnote in the history of Git,\nand other tools won't need to support v4, they can go straight to v5.\nIf v5 fails and we choose to ship and commit to supporting v4, its\nonly a few months delay. We have had index v2/v3 for years. We (and\nour users) can wait a couple of additional months for a format we can\nsupport.\n"},{"id":"190577","messageId":"7vlilaikfo.fsf@alter.siamese.dyndns.org","threadId":"30142","inReplyTo":"CAJo=hJvFfVbYRKtPDJbd8MXKFDAyk==Sbm8oTgypbpE2O4o1=w@mail.gmail.com","subject":"Re: [PATCH 2/2] index-v4: document the entry format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-05-02T17:04:11Z","receivedAt":"2012-05-02T17:04:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> IMHO, keep this in next to avoid releasing it until we know the\n> outcome of the GSoC project. The handful of WebKit developers that use\n> Git that really benefit from index v4 can use it by building and\n> installing their own next.\n> ...\n> Its only a few months to wait and see where \"v5\" goes. If v5 is\n> successful, v4 will just be a minor footnote in the history of Git,\n> and other tools won't need to support v4, they can go straight to v5.\n\nYou may not have noticed this, but there is no practical difference\nbetween keeping it in 'next' and releasing it to 'master' from the\nthird-party tool's point of view.\n\nThere is _only_ one way to end up with v4 version of index: running \"git\nupdate-index --index-version 4\". When creating a new index, or working in\na repository, starting from an index written in the current version, you\nwill get v2 (or v3) index (this gentle handling of backward compatibility\ncomes from later parts of the series). It is either running that command\nor running 'next' version *and* running that command---either way, the\nuser deliberately has to ask for it, and if a third-party tool like jgit\nchooses to ignore v4, it is not the end of the world. The user opted-in\ncan run \"git update-index --index-version 2\" to revert it before using\nsuch a tool.\n\nFor a third-party tool, lack of support of v4 is similar to not supporting\na config file that does not record the core.repositoryformatversion, which\nthe user can manually add it with the editor, and much less serious than\nnot supporting the v3 version of the index, which the user cannot do much\nabout it.\n\nI would say that the cost of not merging the refactoring in the earlier\nparts of the series and the gentler handling of backward compatibility in\nthe later parts of the series is much higher.\n"},{"id":"190580","messageId":"CAJo=hJukfmnfvuU5TWk6ftJ9pG+bSMa2t1ETH=0v=ZKwsbQ2wA@mail.gmail.com","threadId":"30142","inReplyTo":"7vlilaikfo.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/2] index-v4: document the entry format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-05-02T17:13:44Z","receivedAt":"2012-05-02T17:13:44Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Wed, May 2, 2012 at 10:04 AM, Junio C Hamano wrote:\n> Shawn Pearce writes:\n>\n>> IMHO, keep this in next to avoid releasing it until we know the\n>> outcome of the GSoC project. The handful of WebKit developers that use\n>> Git that really benefit from index v4 can use it by building and\n>> installing their own next.\n>> ...\n>> Its only a few months to wait and see where \"v5\" goes. If v5 is\n>> successful, v4 will just be a minor footnote in the history of Git,\n>> and other tools won't need to support v4, they can go straight to v5.\n>\n> You may not have noticed this, but there is no practical difference\n> between keeping it in 'next' and releasing it to 'master' from the\n> third-party tool's point of view.\n>\n> There is _only_ one way to end up with v4 version of index: running \"git\n> update-index --index-version 4\".\n\nThanks, I did miss this in the series. I hereby retract my complaint. :-)\n"}]}