{"thread":{"id":"17857","subject":"[RFC/PATCH] Proof-of-concept streamed hashing, demoed in `git hash-object`","startedAt":"2009-02-17T14:31:35Z","lastAt":"2009-02-17T17:33:03Z","messageCount":3,"participants":["Ben Hoskings","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"105156","messageId":"0984029E-57D0-4EFA-A060-E0B6FFA77D58@hoskings.net","threadId":"17857","inReplyTo":null,"subject":"[RFC/PATCH] Proof-of-concept streamed hashing, demoed in `git hash-object`","fromName":"Ben Hoskings","fromEmail":"ben@hoskings.net","sentAt":"2009-02-17T14:31:35Z","receivedAt":"2009-02-17T14:31:35Z","isPatch":true,"sender":{"key":"ben@hoskings.net","avatar":"https://gravatar.com/avatar/60ea3deb2865e547491ebef040a31093bb940fe1556da3bd1540a56bae2ca5a5?d=mp&s=160"},"body":"Hi folks,\n\nThis patch adds a proof-of-concept implementation of streaming SHA1  \ncalculation in sha1_file.c, as demoed with `git hash-object <large  \ninput file>`. Instead of the command's memory footprint being equal to  \nthe input file's size, this caps it at SHA1_CHUNK_SIZE (currently 64MB).\n\nCapping memory use this easily seems like a win, but then all this  \ncode does is stream-calculate a SHA1 and print it to stdout. There  \nseem to be a lot of disparate places throughout the codebase where  \nobjects have their SHA1 calculated.\n\nThen again, I presume most of these are working with blobs and not  \nentire files, and hence wouldn't require streaming anyway. (I'm  \nassuming blobs don't grow large enough to warrant it - is that  \nnecessarily true?)\n\nThe memory usage can be verified by running\nwhile true; do ps aux | grep hash-object | grep -v grep; sleep 0.2; done\n\nand then running `git hash-object <large input file>` in a second  \nterminal. The memory use stays at or below SHA1_CHUNK_SIZE until the  \nstreamed hash is printed on the terminal and the non-streamed hash is  \nsubsequently calculated.\n\nOn my machine, the original implementation hashed a 700MB file in  \n5.8sec. My patch does it in 6.2sec with SHA1_CHUNK_SIZE set to 64MB.\n\nCheers\nBen Hoskings\n\n---\n  sha1_file.c |   47 +++++++++++++++++++++++++++++++++++++++++++++++\n  1 files changed, 47 insertions(+), 0 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 5b6e0f6..59f0adb 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -33,6 +33,8 @@ static unsigned long sz_fmt(size_t s) { return  \n(unsigned long)s; }\n  static size_t sz_fmt(size_t s) { return s; }\n  #endif\n\n+#define SHA1_CHUNK_SIZE (size_t)(1024*1024*64)\n+\n  const unsigned char null_sha1[20];\n\n  const signed char hexval_table[256] = {\n@@ -2242,6 +2244,39 @@ static void write_sha1_file_prepare(const void  \n*buf, unsigned long len,\n  \tgit_SHA1_Final(sha1, &c);\n  }\n\n+inline void write_sha1_fd_process_chunk(int fd, unsigned long len,\n+                                        unsigned long offset,  \ngit_SHA_CTX *c,\n+                                        void *buf)\n+{\n+  buf = xmmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, offset);\n+  git_SHA1_Update(c, buf, len);\n+  munmap(buf, len);\n+}\n+\n+static void write_sha1_fd_prepare(int fd, unsigned long len,\n+                                  const char *type, unsigned char  \n*sha1,\n+                                  char *hdr, int *hdrlen)\n+{\n+\tgit_SHA_CTX c;\n+\tvoid *buf = NULL;\n+\tunsigned long offset = 0;\n+\n+\t*hdrlen = sprintf(hdr, \"%s %lu\", type, len)+1;\n+\n+\tgit_SHA1_Init(&c);\n+\tgit_SHA1_Update(&c, hdr, *hdrlen);\n+\n+\tfor (; offset + SHA1_CHUNK_SIZE <= len; offset += SHA1_CHUNK_SIZE) {\n+\t\twrite_sha1_fd_process_chunk(fd, SHA1_CHUNK_SIZE, offset, &c, buf);\n+\t}\n+\n+\tif (len % SHA1_CHUNK_SIZE) {\n+\t\twrite_sha1_fd_process_chunk(fd, len % SHA1_CHUNK_SIZE, offset, &c,  \nbuf);\n+\t}\n+\n+\tgit_SHA1_Final(sha1, &c);\n+}\n+\n  /*\n   * Move the just written object into its final resting place\n   */\n@@ -2294,6 +2329,15 @@ int hash_sha1_file(const void *buf, unsigned  \nlong len, const char *type,\n  \treturn 0;\n  }\n\n+int hash_sha1_fd(int fd, unsigned long len, const char *type,\n+                 unsigned char *sha1)\n+{\n+\tchar hdr[32];\n+\tint hdrlen;\n+\twrite_sha1_fd_prepare(fd, len, type, sha1, hdr, &hdrlen);\n+\treturn 0;\n+}\n+\n  /* Finalize a file on disk, and close it. */\n  static void close_sha1_file(int fd)\n  {\n@@ -2523,6 +2567,9 @@ int index_fd(unsigned char *sha1, int fd, struct  \nstat *st, int write_object,\n  \t\t\tret = -1;\n  \t\tstrbuf_release(&sbuf);\n  \t} else if (size) {\n+\t\thash_sha1_fd(fd, size, typename(type), sha1);\n+\t\tprintf(\"%s <- chunked hash\\n\", sha1_to_hex(sha1));\n+\n  \t\tvoid *buf = xmmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n  \t\tret = index_mem(sha1, buf, size, write_object, type, path);\n  \t\tmunmap(buf, size);\n-- \n1.6.1.2\n"},{"id":"105159","messageId":"35E0E6CA-22F0-4995-B942-46B630146506@hoskings.net","threadId":"17857","inReplyTo":"0984029E-57D0-4EFA-A060-E0B6FFA77D58@hoskings.net","subject":"Re: [RFC/PATCH] Proof-of-concept streamed hashing, demoed in `git hash-object`","fromName":"Ben Hoskings","fromEmail":"ben@hoskings.net","sentAt":"2009-02-17T15:03:19Z","receivedAt":"2009-02-17T15:03:19Z","isPatch":true,"sender":{"key":"ben@hoskings.net","avatar":"https://gravatar.com/avatar/60ea3deb2865e547491ebef040a31093bb940fe1556da3bd1540a56bae2ca5a5?d=mp&s=160"},"body":"On 18/02/2009, at 12:31 AM, Ben Hoskings wrote:\n\n> Hi folks,\n>\n> This patch adds a proof-of-concept implementation of streaming SHA1  \n> calculation in sha1_file.c, as demoed with `git hash-object <large  \n> input file>`. Instead of the command's memory footprint being equal  \n> to the input file's size, this caps it at SHA1_CHUNK_SIZE (currently  \n> 64MB).\n\nArgh, sorry—the patch was somehow corrupted; the single spaces at the  \nstart of the surrounding lines of each hunk became double spaces. I'm  \nnot sure what's happening there.\n\nHere's the commit on GitHub for anyone who would like to apply the  \npatch.\n\nhttp://github.com/benhoskings/git/commit/33b3d26ca40becf00f57008ef9d215d9287fb8e8\n\nCheers\nBen\n"},{"id":"105184","messageId":"20090217173302.GC31297@sigill.intra.peff.net","threadId":"17857","inReplyTo":"0984029E-57D0-4EFA-A060-E0B6FFA77D58@hoskings.net","subject":"Re: [RFC/PATCH] Proof-of-concept streamed hashing, demoed in `git hash-object`","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-02-17T17:33:03Z","receivedAt":"2009-02-17T17:33:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Feb 18, 2009 at 12:31:35AM +1000, Ben Hoskings wrote:\n\n> This patch adds a proof-of-concept implementation of streaming SHA1  \n> calculation in sha1_file.c, as demoed with `git hash-object <large input \n> file>`. Instead of the command's memory footprint being equal to the input \n> file's size, this caps it at SHA1_CHUNK_SIZE (currently 64MB).\n\nThis might be nice to reduce the memory footprint for _some_ operations\nthat only need to look at the data once, but...\n\n> Capping memory use this easily seems like a win, but then all this code \n> does is stream-calculate a SHA1 and print it to stdout. There seem to be a \n> lot of disparate places throughout the codebase where objects have their \n> SHA1 calculated.\n\n...as you noticed, there are a lot of other places where we need the\nwhole object. So you are not suddenly making git not suck with a 700MB\nfile on a 512MB system.\n\nBut more importantly, hash-object (via index_fd) already mmaps the input\nwhen it is possible to do so. So on memory-tight systems, won't the OS\nalready release memory when appropriate (i.e., your virtual size is\nlarge, but the OS is free to optimize what is actually paged in as\nappropriate).\n\nI suppose this is an extra hint to the OS that we don't care about past\nchunks. On systems which support it, perhaps using madvise with\nMADV_SEQUENTIAL would be another useful hint.\n\n> Then again, I presume most of these are working with blobs and not entire \n> files, and hence wouldn't require streaming anyway. (I'm assuming blobs \n> don't grow large enough to warrant it - is that necessarily true?)\n\nEither I don't understand what you are saying here, or you are missing\nsomething fundamental about hwo git works: blobs _are_ entire files.\n\n> On my machine, the original implementation hashed a 700MB file in 5.8sec. \n> My patch does it in 6.2sec with SHA1_CHUNK_SIZE set to 64MB.\n\nHmph. So it's slower? I'm not sure what the advantage is, then. On a\nlow-memory machine, the OS's paging strategy should be reasonable,\nespecially with MADV_SEQUENTIAL (though I haven't tested it). And on a\nmachine with enough memory, it's slower.\n\nI guess you are evicting fewer pages from other processes on the system\nin the meantime.\n\n> +inline void write_sha1_fd_process_chunk(int fd, unsigned long len,\n> +                                        unsigned long offset,  \n> git_SHA_CTX *c,\n> +                                        void *buf)\n> +{\n> +  buf = xmmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, offset);\n> +  git_SHA1_Update(c, buf, len);\n> +  munmap(buf, len);\n> +}\n\nWhat is the point of the buf input parameter, which is promptly\noverwritten?\n\n> +int hash_sha1_fd(int fd, unsigned long len, const char *type,\n> +                 unsigned char *sha1)\n> +{\n> +\tchar hdr[32];\n> +\tint hdrlen;\n> +\twrite_sha1_fd_prepare(fd, len, type, sha1, hdr, &hdrlen);\n> +\treturn 0;\n> +}\n\nWhat is the point of the hdr and hdrlen variables being passed in to\nreceive values, when we never actually look at them? I would think you\nare conforming to an existing interface except that you just added the\nfunction earlier in the patch.\n\n-Peff\n"}]}