{"thread":{"id":"29551","subject":"[PATCH 0/3] On compresing large index","startedAt":"2012-02-05T08:30:02Z","lastAt":"2012-02-06T15:54:39Z","messageCount":7,"participants":["Nguyễn Thái Ngọc Duy","Thomas Rast","Nguyen Thai Ngoc Duy","Joshua Redstone"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"183889","messageId":"1328430605-4566-1-git-send-email-pclouds@gmail.com","threadId":"29551","inReplyTo":null,"subject":"[PATCH 0/3] On compresing large index","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-02-05T08:30:02Z","receivedAt":"2012-02-05T08:30:02Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"I was thinking whether compressing index might help when it contained\n~2M files. It turns out that only makes the situation worse. Anyway, I\npost the code and some numbers here.\n\nThe index is created artifically with the program [1]\n\n$ git init\n$ touch foo\n$ git hash-object -w foo\n$ ./a.out 256 256 32 | git update-index --index-info\n\nThat gives ~2M files in index, 209 MB in size.\n\n$ time ~/w/git/git ls-files | head >/dev/null\nreal    0m4.635s\nuser    0m4.258s\nsys     0m0.329s\n\n$ time ~/w/git/git update-index level-0-0000/foo\nreal    0m4.593s\nuser    0m4.264s\nsys     0m0.323s\n\nIndex is compressed with GIT_ZCACHE=1.\n\n$ GIT_ZCACHE=1 ~/w/git/git update-index level-0-0000/foo\n\nwhich gives 6.8 MB index (the true number may be less impressive\nbecause compressing rate in my artificial tree is really high). The\nonly problem with this is git uses more time, not less\n\n$ time ~/w/git/git ls-files | head >/dev/null\nreal    0m4.970s\nuser    0m4.675s\nsys     0m0.289s\n\n$ time GIT_ZCACHE=1 ~/w/git/git update-index level-0-0000/foo\nreal    0m4.959s\nuser    0m4.682s\nsys     0m0.273s\n\nMy guess is Linux caches the whole index in memory already so I/O time\ndoes not really matter, while we still have to pay for zlib's time. We\nneed to figure out what git uses 4s user time for.\n\nThis series may be useful on OSes that do not cache heavily. Though\nI'm not sure if there is any out there nowadays.\n\nNguyễn Thái Ngọc Duy (3):\n  read-cache: factor out cache entries reading code\n  read-cache: reduce malloc/free during writing index\n  Support compressing index when GIT_ZCACHE=1\n\n cache.h      |    1 +\n read-cache.c |  172 +++++++++++++++++++++++++++++++++++++++++++++++++---------\n 2 files changed, 148 insertions(+), 25 deletions(-)\n\n[1]\n-- 8< --\n#include <stdio.h>\n#include <string.h>\n\nint main(int argc, char **argv)\n{\n\tconst char *prefix = \"100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 0\\t\";\n\tint l1, l2, l3;\n\tint m1, m2, m3;\n\n\tm1 = atoi(argv[1]);\n\tm2 = atoi(argv[2]);\n\tm3 = atoi(argv[3]);\n\n\tfor (l1 = 0; l1 < m1; l1++) {\n\t\tprintf(\"%slevel-0-%04d/foo\\n\", prefix, l1);\n\t\tfor (l2 = 0; l2 < m2; l2++)\n\t\t\tfor (l3 = 0; l3 < m3; l3++)\n\t\t\t\tprintf(\"%slevel-0-%04d/level-1-%04d/foo-%04d\\n\",\n\t\t\t\t       prefix, l1, l2, l3);\n\t}\n\treturn 0;\n}\n-- 8< --\n-- \n1.7.8.36.g69ee2\n"},{"id":"183891","messageId":"1328430605-4566-2-git-send-email-pclouds@gmail.com","threadId":"29551","inReplyTo":"1328430605-4566-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 1/3] read-cache: factor out cache entries reading code","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-02-05T08:30:03Z","receivedAt":"2012-02-05T08:30:03Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n read-cache.c |   32 ++++++++++++++++++++------------\n 1 files changed, 20 insertions(+), 12 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex a51bba1..2dbf923 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1273,10 +1273,28 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk)\n \treturn ce;\n }\n \n+static int read_cache_entries(struct index_state *istate,\n+\t\t\t      const char *mmap, unsigned long src_offset)\n+{\n+\tconst char *buf = mmap + src_offset;\n+\tint i;\n+\n+\tfor (i = 0; i < istate->cache_nr; i++) {\n+\t\tstruct ondisk_cache_entry *disk_ce;\n+\t\tstruct cache_entry *ce;\n+\n+\t\tdisk_ce = (struct ondisk_cache_entry *)buf;\n+\t\tce = create_from_disk(disk_ce);\n+\t\tset_index_entry(istate, i, ce);\n+\t\tbuf += ondisk_ce_size(ce);\n+\t}\n+\treturn buf - mmap;\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-\tint fd, i;\n+\tint fd;\n \tstruct stat st;\n \tunsigned long src_offset;\n \tstruct cache_header *hdr;\n@@ -1319,17 +1337,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-\tsrc_offset = sizeof(*hdr);\n-\tfor (i = 0; i < istate->cache_nr; i++) {\n-\t\tstruct ondisk_cache_entry *disk_ce;\n-\t\tstruct cache_entry *ce;\n-\n-\t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);\n-\t\tce = create_from_disk(disk_ce);\n-\t\tset_index_entry(istate, i, ce);\n-\n-\t\tsrc_offset += ondisk_ce_size(ce);\n-\t}\n+\tsrc_offset = read_cache_entries(istate, mmap, sizeof(*hdr));\n \tistate->timestamp.sec = st.st_mtime;\n \tistate->timestamp.nsec = ST_MTIME_NSEC(st);\n \n-- \n1.7.8.36.g69ee2\n"},{"id":"183890","messageId":"1328430605-4566-3-git-send-email-pclouds@gmail.com","threadId":"29551","inReplyTo":"1328430605-4566-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 2/3] read-cache: reduce malloc/free during writing index","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-02-05T08:30:04Z","receivedAt":"2012-02-05T08:30:04Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n read-cache.c |   26 ++++++++++++++++++--------\n 1 files changed, 18 insertions(+), 8 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 2dbf923..7b9a989 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1521,12 +1521,19 @@ 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+static int ce_prepare_ondisk_entry(struct cache_entry *ce,\n+\t\t\t\t    void **ondisk_p, int *ondisk_size)\n {\n \tint size = ondisk_ce_size(ce);\n-\tstruct ondisk_cache_entry *ondisk = xcalloc(1, size);\n+\tstruct ondisk_cache_entry *ondisk;\n \tchar *name;\n-\tint result;\n+\n+\tif (size <= *ondisk_size)\n+\t\tondisk = *ondisk_p;\n+\telse {\n+\t\tondisk = *ondisk_p = xrealloc(*ondisk_p, size);\n+\t\t*ondisk_size = size;\n+\t}\n \n \tondisk->ctime.sec = htonl(ce->ce_ctime.sec);\n \tondisk->mtime.sec = htonl(ce->ce_mtime.sec);\n@@ -1549,10 +1556,7 @@ static int ce_write_entry(git_SHA_CTX *c, int fd, struct cache_entry *ce)\n \telse\n \t\tname = ondisk->name;\n \tmemcpy(name, ce->name, ce_namelen(ce));\n-\n-\tresult = ce_write(c, fd, ondisk, size);\n-\tfree(ondisk);\n-\treturn result;\n+\treturn size;\n }\n \n static int has_racy_timestamp(struct index_state *istate)\n@@ -1588,6 +1592,8 @@ int write_index(struct index_state *istate, int newfd)\n \tstruct cache_entry **cache = istate->cache;\n \tint entries = istate->cache_nr;\n \tstruct stat st;\n+\tvoid *ce_ondisk = NULL;\n+\tint ce_ondisk_size = 0;\n \n \tfor (i = removed = extended = 0; i < entries; i++) {\n \t\tif (cache[i]->ce_flags & CE_REMOVE)\n@@ -1612,13 +1618,17 @@ int write_index(struct index_state *istate, int newfd)\n \n \tfor (i = 0; i < entries; i++) {\n \t\tstruct cache_entry *ce = cache[i];\n+\t\tint size;\n+\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\tsize = ce_prepare_ondisk_entry(ce, &ce_ondisk, &ce_ondisk_size);\n+\t\tif (ce_write(&c, newfd, ce_ondisk, size) < 0)\n \t\t\treturn -1;\n \t}\n+\tfree(ce_ondisk);\n \n \t/* Write extension data here */\n \tif (istate->cache_tree) {\n-- \n1.7.8.36.g69ee2\n"},{"id":"183892","messageId":"1328430605-4566-4-git-send-email-pclouds@gmail.com","threadId":"29551","inReplyTo":"1328430605-4566-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 3/3] Support compressing index when GIT_ZCACHE=1","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-02-05T08:30:05Z","receivedAt":"2012-02-05T08:30:05Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n cache.h      |    1 +\n read-cache.c |  118 ++++++++++++++++++++++++++++++++++++++++++++++++++++++---\n 2 files changed, 112 insertions(+), 7 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 10afd71..112bc52 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -99,6 +99,7 @@ unsigned long git_deflate_bound(git_zstream *, unsigned long);\n  */\n \n #define CACHE_SIGNATURE 0x44495243\t/* \"DIRC\" */\n+#define ZCACHE_SIGNATURE 0x4452435A\t/* \"DRCZ\" */\n struct cache_header {\n \tunsigned int hdr_signature;\n \tunsigned int hdr_version;\ndiff --git a/read-cache.c b/read-cache.c\nindex 7b9a989..45c1712 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1182,12 +1182,17 @@ 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-static int verify_hdr(struct cache_header *hdr, unsigned long size)\n+static int verify_hdr(struct cache_header *hdr, unsigned long size,\n+\t\t      int *deflated)\n {\n \tgit_SHA_CTX c;\n \tunsigned char sha1[20];\n \n-\tif (hdr->hdr_signature != htonl(CACHE_SIGNATURE))\n+\tif (hdr->hdr_signature == htonl(CACHE_SIGNATURE))\n+\t\t*deflated = 0;\n+\telse if (hdr->hdr_signature == htonl(ZCACHE_SIGNATURE))\n+\t\t*deflated = 1;\n+\telse\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@@ -1273,6 +1278,43 @@ static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk)\n \treturn ce;\n }\n \n+static int inflate_cache_entries(struct index_state *istate,\n+\t\t\t\t const unsigned char *mmap, size_t mmap_size,\n+\t\t\t\t unsigned long src_offset)\n+{\n+\tunsigned char buf[sizeof(struct ondisk_cache_entry) + PATH_MAX];\n+\tstruct ondisk_cache_entry *disk_ce;\n+\tstruct cache_entry *ce;\n+\tstruct git_zstream stream;\n+\tint i, status;\n+\n+\tmemset(&stream, 0, sizeof(stream));\n+\tstream.next_in = (unsigned char*)mmap + src_offset;\n+\tstream.avail_in = mmap_size - src_offset;\n+\tstream.next_out = buf;\n+\tstream.avail_out = sizeof(buf);\n+\tgit_inflate_init(&stream);\n+\n+\tfor (i = 0; i < istate->cache_nr; i++) {\n+\t\tint remaining;\n+\t\tdo {\n+\t\t\tstatus = git_inflate(&stream, Z_FINISH);\n+\t\t} while (status == Z_OK);\n+\n+\t\tdisk_ce = (struct ondisk_cache_entry *)buf;\n+\t\tce = create_from_disk(disk_ce);\n+\t\tset_index_entry(istate, i, ce);\n+\n+\t\tremaining = stream.next_out - (buf + ondisk_ce_size(ce));\n+\t\tmemmove(buf, buf + ondisk_ce_size(ce), remaining);\n+\t\tstream.next_out = buf + remaining;\n+\t\tstream.avail_out = sizeof(buf) - remaining;\n+\t}\n+\tassert(status == Z_STREAM_END);\n+\tgit_inflate_end(&stream);\n+\treturn stream.next_in - mmap;\n+}\n+\n static int read_cache_entries(struct index_state *istate,\n \t\t\t      const char *mmap, unsigned long src_offset)\n {\n@@ -1300,6 +1342,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+\tint deflated;\n \n \terrno = EBUSY;\n \tif (istate->initialized)\n@@ -1329,7 +1372,7 @@ int read_index_from(struct index_state *istate, const char *path)\n \t\tdie_errno(\"unable to map index file\");\n \n \thdr = mmap;\n-\tif (verify_hdr(hdr, mmap_size) < 0)\n+\tif (verify_hdr(hdr, mmap_size, &deflated) < 0)\n \t\tgoto unmap;\n \n \tistate->cache_nr = ntohl(hdr->hdr_entries);\n@@ -1337,7 +1380,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-\tsrc_offset = read_cache_entries(istate, mmap, sizeof(*hdr));\n+\tif (deflated)\n+\t\tsrc_offset = inflate_cache_entries(istate, mmap, mmap_size,\n+\t\t\t\t\t\t   sizeof(*hdr));\n+\telse\n+\t\tsrc_offset = read_cache_entries(istate, mmap, sizeof(*hdr));\n \tistate->timestamp.sec = st.st_mtime;\n \tistate->timestamp.nsec = ST_MTIME_NSEC(st);\n \n@@ -1594,6 +1641,10 @@ int write_index(struct index_state *istate, int newfd)\n \tstruct stat st;\n \tvoid *ce_ondisk = NULL;\n \tint ce_ondisk_size = 0;\n+\tstruct git_zstream stream;\n+\tint deflate, status;\n+\tunsigned char *dbuf_out;\n+\tunsigned char *dbuf_in;\n \n \tfor (i = removed = extended = 0; i < entries; i++) {\n \t\tif (cache[i]->ce_flags & CE_REMOVE)\n@@ -1607,7 +1658,8 @@ int write_index(struct index_state *istate, int newfd)\n \t\t}\n \t}\n \n-\thdr.hdr_signature = htonl(CACHE_SIGNATURE);\n+\tdeflate = getenv(\"GIT_ZCACHE\") != NULL;\n+\thdr.hdr_signature = htonl(deflate ? ZCACHE_SIGNATURE : 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_entries = htonl(entries - removed);\n@@ -1616,6 +1668,17 @@ 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+\tif (deflate) {\n+\t\tdbuf_out = xmalloc(WRITE_BUFFER_SIZE);\n+\t\tdbuf_in = xmalloc(WRITE_BUFFER_SIZE);\n+\t\tmemset(&stream, 0, sizeof(stream));\n+\t\tstream.next_out = dbuf_out;\n+\t\tstream.avail_out = WRITE_BUFFER_SIZE;\n+\t\tstream.next_in = dbuf_in;\n+\t\tstream.avail_in = 0;\n+\t\tgit_deflate_init(&stream, zlib_compression_level);\n+\t}\n+\n \tfor (i = 0; i < entries; i++) {\n \t\tstruct cache_entry *ce = cache[i];\n \t\tint size;\n@@ -1625,11 +1688,52 @@ int write_index(struct index_state *istate, int newfd)\n \t\tif (!ce_uptodate(ce) && is_racy_timestamp(istate, ce))\n \t\t\tce_smudge_racily_clean_entry(ce);\n \t\tsize = ce_prepare_ondisk_entry(ce, &ce_ondisk, &ce_ondisk_size);\n-\t\tif (ce_write(&c, newfd, ce_ondisk, size) < 0)\n-\t\t\treturn -1;\n+\t\tif (!deflate) {\n+\t\t\tif (ce_write(&c, newfd, ce_ondisk, size) < 0)\n+\t\t\t\treturn -1;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tif (stream.avail_in)\n+\t\t\tmemmove(dbuf_in, stream.next_in, stream.avail_in);\n+\t\tmemcpy(dbuf_in + stream.avail_in, ce_ondisk, size);\n+\t\tstream.next_in = dbuf_in;\n+\t\tstream.avail_in += size;\n+\t\tdo {\n+\t\t\tstatus = git_deflate(&stream, 0);\n+\t\t\tif (stream.next_out > dbuf_out) {\n+\t\t\t\tsize = stream.next_out - dbuf_out;\n+\t\t\t\tif (ce_write(&c, newfd, dbuf_out, size) < 0)\n+\t\t\t\t\treturn -1;\n+\t\t\t\tstream.next_out = dbuf_out;\n+\t\t\t\tstream.avail_out = WRITE_BUFFER_SIZE;\n+\t\t\t}\n+\t\t} while (status == Z_OK);\n \t}\n \tfree(ce_ondisk);\n \n+\tif (deflate) {\n+\t\tdo {\n+\t\t\tstatus = git_deflate(&stream, Z_FINISH);\n+\t\t\tif (stream.next_out > dbuf_out) {\n+\t\t\t\tint size = stream.next_out - dbuf_out;\n+\t\t\t\tif (ce_write(&c, newfd, dbuf_out, size) < 0)\n+\t\t\t\t\treturn -1;\n+\t\t\t\tstream.next_out = dbuf_out;\n+\t\t\t\tstream.avail_out = WRITE_BUFFER_SIZE;\n+\t\t\t}\n+\t\t} while (status == Z_OK);\n+\n+\t\tgit_deflate_end(&stream);\n+\t\tif (stream.next_out > dbuf_out) {\n+\t\t\tint size = stream.next_out - dbuf_out;\n+\t\t\tif (ce_write(&c, newfd, dbuf_out, size) < 0)\n+\t\t\t\treturn -1;\n+\t\t}\n+\t\tfree(dbuf_in);\n+\t\tfree(dbuf_out);\n+\t}\n+\n \t/* Write extension data here */\n \tif (istate->cache_tree) {\n \t\tstruct strbuf sb = STRBUF_INIT;\n-- \n1.7.8.36.g69ee2\n"},{"id":"183922","messageId":"87ehu9ug9i.fsf@thomas.inf.ethz.ch","threadId":"29551","inReplyTo":"1328430605-4566-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH 0/3] On compresing large index","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-02-05T21:22:49Z","receivedAt":"2012-02-05T21:22:49Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:\n\n> $ time ~/w/git/git ls-files | head >/dev/null\n> real    0m4.635s\n> user    0m4.258s\n> sys     0m0.329s\n>\n> $ time ~/w/git/git update-index level-0-0000/foo\n> real    0m4.593s\n> user    0m4.264s\n> sys     0m0.323s\n[...]\n> We need to figure out what git uses 4s user time for.\n\nWhen I worked on the cache-tree stuff, my observation (based on\nprofiling, so I had actual data :-) was that computing SHA1s absolutely\ndominates everything in such operations.  It does that when writing the\nindex to write the trailing checksum, and also when loading it to verify\nthat the index is valid.\n\nls-files shouldn't be so slow though.  A quick run with callgrind in a\nlinux-2.6.git tells me it spends about 45% of its time on SHA1s and a\nwhopping 25% in quote_c_style().  I wonder what's so hard about\nquoting...\n\n> This series may be useful on OSes that do not cache heavily. Though\n> I'm not sure if there is any out there nowadays.\n\nI think you could make a case that they should not be called \"OS\" ;-)\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"183952","messageId":"CACsJy8AnGg11PeCGFs_BxOM3wAjwzs2tOCWJV31_2_KMFTxhDA@mail.gmail.com","threadId":"29551","inReplyTo":"87ehu9ug9i.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH 0/3] On compresing large index","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-02-06T01:35:29Z","receivedAt":"2012-02-06T01:35:29Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"2012/2/6 Thomas Rast <trast@inf.ethz.ch>:\n>> We need to figure out what git uses 4s user time for.\n>\n> When I worked on the cache-tree stuff, my observation (based on\n> profiling, so I had actual data :-) was that computing SHA1s absolutely\n> dominates everything in such operations.  It does that when writing the\n> index to write the trailing checksum, and also when loading it to verify\n> that the index is valid.\n\nYou're right. This is on another machine but with same index (2M\nfiles), without SHA1 checksum:\n\n$ time ~/w/git/git ls-files --stage|head > /dev/null\nreal    0m1.533s\nuser    0m1.228s\nsys     0m0.306s\n\nand with SHA-1 checksum:\n\n$ time git ls-files --stage|head > /dev/null\nreal     0m7.525s\nuser    0m7.257s\nsys     0m0.268s\n\nI guess we could fall back to cheaper digests for such a large index.\nStill more than one second for doing nothing but reading index is too\nslow to me.\n\n> ls-files shouldn't be so slow though.  A quick run with callgrind in a\n> linux-2.6.git tells me it spends about 45% of its time on SHA1s and a\n> whopping 25% in quote_c_style().  I wonder what's so hard about\n> quoting...\n\nThat's why I put \"| head\" there, to cut output processing overhead (hopefully).\n-- \nDuy\n"},{"id":"184029","messageId":"CB555FF2.40859%joshua.redstone@fb.com","threadId":"29551","inReplyTo":"CACsJy8AnGg11PeCGFs_BxOM3wAjwzs2tOCWJV31_2_KMFTxhDA@mail.gmail.com","subject":"Re: [PATCH 0/3] On compresing large index","fromName":"Joshua Redstone","fromEmail":"joshua.redstone@fb.com","sentAt":"2012-02-06T15:54:39Z","receivedAt":"2012-02-06T15:54:39Z","isPatch":true,"sender":{"key":"joshua.redstone@fb.com","avatar":null},"body":"Fwiw, specifically related to 'git ls-files', since it is a relatively\nrare operation, it's probably ok if it's a bit slow.  I know you chose it\nas a good benchmark of index reading performance.  I just mention it\nbecause, in some hypothetical wild-and-crazy world in which we had a\ngit-aware file system layer, one could imagine doing away with most of the\nindex file and querying the file system for info on what's changed, SHA1\nof subtrees, etc.\n\nDo you have a sense of which operations on the index are high-value pain\npoints for large repositories?  I can imagine things like 'git-add' and\n'git-commit', but I'm not super familiar with other common operations it\nhas a role in.\n\nJosh\n\n\nOn 2/5/12 8:35 PM, \"Nguyen Thai Ngoc Duy\" <pclouds@gmail.com> wrote:\n\n>2012/2/6 Thomas Rast <trast@inf.ethz.ch>:\n>>> We need to figure out what git uses 4s user time for.\n>>\n>> When I worked on the cache-tree stuff, my observation (based on\n>> profiling, so I had actual data :-) was that computing SHA1s absolutely\n>> dominates everything in such operations.  It does that when writing the\n>> index to write the trailing checksum, and also when loading it to verify\n>> that the index is valid.\n>\n>You're right. This is on another machine but with same index (2M\n>files), without SHA1 checksum:\n>\n>$ time ~/w/git/git ls-files --stage|head > /dev/null\n>real    0m1.533s\n>user    0m1.228s\n>sys     0m0.306s\n>\n>and with SHA-1 checksum:\n>\n>$ time git ls-files --stage|head > /dev/null\n>real     0m7.525s\n>user    0m7.257s\n>sys     0m0.268s\n>\n>I guess we could fall back to cheaper digests for such a large index.\n>Still more than one second for doing nothing but reading index is too\n>slow to me.\n>\n>> ls-files shouldn't be so slow though.  A quick run with callgrind in a\n>> linux-2.6.git tells me it spends about 45% of its time on SHA1s and a\n>> whopping 25% in quote_c_style().  I wonder what's so hard about\n>> quoting...\n>\n>That's why I put \"| head\" there, to cut output processing overhead\n>(hopefully).\n>-- \n>Duy\n"}]}