{"thread":{"id":"55380","subject":"[PATCH] csum-file: flush less often","startedAt":"2021-03-24T17:51:16Z","lastAt":"2021-03-28T08:45:12Z","messageCount":8,"participants":["Derrick Stolee via GitGitGadget","Derrick Stolee","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"420122","messageId":"pull.914.git.1616608219602.gitgitgadget@gmail.com","threadId":"55380","inReplyTo":null,"subject":"[PATCH] csum-file: flush less often","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-24T17:50:18Z","receivedAt":"2021-03-24T17:51:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <dstolee@microsoft.com>\n\nIn an independent investigation, I noticed that do_write_index() in\nread-cache.c has its own hashing logic and buffering mechanism.\nSpecifically, the ce_write() method was introduced by 4990aadc (Speed up\nindex file writing by chunking it nicely, 2005-04-20) and similar\nmechanisms were introduced a few months later in c38138cd\n(git-pack-objects: write the pack files with a SHA1 csum, 2005-06-26).\nBased on the timing, in the early days of the Git codebase, I figured\nthat these roughly equivalent code paths were never unified only because\nit got lost in the shuffle. The hashfile API has since been used\nextensively in other file formats, such as pack-indexes,\nmult-pack-indexes, and commit-graphs. Therefore, it seems prudent to\nunify the index writing code to use the same mechanism.\n\nHowever, upon doing that refactoring process, I noticed that this caused\nsome commands that write the index to slow down by 1-2%! I then looked\nfor a reason why this could be.\n\nFirst, I noticed that the mechanisms use different buffer sizes. The\nhashfile uses an 8KB buffer while the index uses an 128KB buffer.\nTesting with a variety of different buffer sizes made little difference.\n\nNext, I inspected the buffering code itself, and found an important\ndifference. Specifically, every call to hashwrite() was causing a flush\nof the filestream, even if it was a very small write. With many callers\nusing helpers like hashwrite_be32() to write integers in network-byte\norder, this was leading to many more file flushes than necessary.\n\nThis change modifies hashwrite() to always populate the hashfile buffer,\nand only flush when that buffer is full. This is safe to do because all\nconsumers of a hashfile must call finalize_hashfile(), which flushes the\nbuffer at the start.\n\nIt is worth noting that this is modifying logic introduced by a8032d12\n(sha1write: don't copy full sized buffers, 2008-09-02) which reduces\nmemcpy() calls when the input buffer is sufficiently longer than the\nhashfile's buffer, causing nr to be the length of the full buffer. Use\nthe input buffer directly in these cases. Since we don't guarantee that\nthe buffer is flushed by the end of hashwrite(), we need to group some\noffset logic into the condition that memcpy() is necessary. Note that nr\nis equal to sizeof(f->buffer) only when f->offset is zero, so that\ncondition does not need to be added here.\n\nAs for performance, I focused on known commands that spend a significant\namount of time writing through the hashfile API, especially if using\nsmall buffers as in hashwrite_be32(). 'git multi-pack-index write' was\nan excellent example (deleting the multi-pack-index file between runs)\nand demonstrated this performance change in the Linux kernal repo:\n\nBenchmark #1: old\n  Time (mean ± σ):      2.229 s ±  0.143 s    [User: 1.409 s, System: 0.327 s]\n  Range (min … max):    2.160 s …  2.636 s    10 runs\n\nBenchmark #2: new\n  Time (mean ± σ):      2.162 s ±  0.005 s    [User: 1.392 s, System: 0.323 s]\n  Range (min … max):    2.152 s …  2.172 s    10 runs\n\nSummary\n  'new' ran\n    1.03 ± 0.07 times faster than 'old'\n\nSimilarly, the same command on the Git repository gave these numbers:\n\nBenchmark #1: old\n  Time (mean ± σ):     230.5 ms ±   6.3 ms    [User: 140.5 ms, System: 42.9 ms]\n  Range (min … max):   221.7 ms … 240.6 ms    12 runs\n\nBenchmark #2: new\n  Time (mean ± σ):     220.6 ms ±   5.1 ms    [User: 139.5 ms, System: 34.1 ms]\n  Range (min … max):   214.0 ms … 229.0 ms    13 runs\n\nSummary\n  'new' ran\n    1.05 ± 0.04 times faster than 'old'\n\nFinally, to demonstrate that performance holds when frequently using\nlarge buffers, the numbers below are for 'git pack-objects' packing all\nobjects in the Git repository between v2.30.0 and v2.31.1:\n\nBenchmark #1: old\n  Time (mean ± σ):      1.003 s ±  0.045 s    [User: 1.877 s, System: 0.167 s]\n  Range (min … max):    0.931 s …  1.044 s    10 runs\n\nBenchmark #2: new\n  Time (mean ± σ):     976.4 ms ±  42.2 ms    [User: 1.854 s, System: 0.192 s]\n  Range (min … max):   940.1 ms … 1049.3 ms    10 runs\n\nSummary\n  'new' ran\n    1.03 ± 0.06 times faster than 'old'\n\nWith these consistent improvements of 3-5%, it will be possible to move\nthe index writing logic over to hashfile without performance\ndegradation.\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n    csum-file: flush less often\n    \n    I found this while poking around the index.\n    \n    Thanks, -Stolee\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-914%2Fderrickstolee%2Fhashfile-flush-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-914/derrickstolee/hashfile-flush-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/914\n\n csum-file.c | 22 ++++++++--------------\n 1 file changed, 8 insertions(+), 14 deletions(-)\n\ndiff --git a/csum-file.c b/csum-file.c\nindex 0f35fa5ee47c..39644af590a5 100644\n--- a/csum-file.c\n+++ b/csum-file.c\n@@ -89,32 +89,26 @@ int finalize_hashfile(struct hashfile *f, unsigned char *result, unsigned int fl\n void hashwrite(struct hashfile *f, const void *buf, unsigned int count)\n {\n \twhile (count) {\n-\t\tunsigned offset = f->offset;\n-\t\tunsigned left = sizeof(f->buffer) - offset;\n+\t\tunsigned left = sizeof(f->buffer) - f->offset;\n \t\tunsigned nr = count > left ? left : count;\n-\t\tconst void *data;\n \n \t\tif (f->do_crc)\n \t\t\tf->crc32 = crc32(f->crc32, buf, nr);\n \n \t\tif (nr == sizeof(f->buffer)) {\n \t\t\t/* process full buffer directly without copy */\n-\t\t\tdata = buf;\n+\t\t\tthe_hash_algo->update_fn(&f->ctx, buf, nr);\n+\t\t\tflush(f, buf, nr);\n \t\t} else {\n-\t\t\tmemcpy(f->buffer + offset, buf, nr);\n-\t\t\tdata = f->buffer;\n+\t\t\tmemcpy(f->buffer + f->offset, buf, nr);\n+\t\t\tf->offset += nr;\n+\t\t\tleft -= nr;\n+\t\t\tif (!left)\n+\t\t\t\thashflush(f);\n \t\t}\n \n \t\tcount -= nr;\n-\t\toffset += nr;\n \t\tbuf = (char *) buf + nr;\n-\t\tleft -= nr;\n-\t\tif (!left) {\n-\t\t\tthe_hash_algo->update_fn(&f->ctx, data, offset);\n-\t\t\tflush(f, data, offset);\n-\t\t\toffset = 0;\n-\t\t}\n-\t\tf->offset = offset;\n \t}\n }\n \n\nbase-commit: 142430338477d9d1bb25be66267225fb58498d92\n-- \ngitgitgadget\n"},{"id":"420189","messageId":"84ccabca-0bd3-d0cb-6b38-f96d75c0bbd6@gmail.com","threadId":"55380","inReplyTo":"pull.914.git.1616608219602.gitgitgadget@gmail.com","subject":"Re: [PATCH] csum-file: flush less often","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-03-25T11:55:55Z","receivedAt":"2021-03-25T11:56:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/24/2021 1:50 PM, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee <dstolee@microsoft.com>\n\nLet me walk this back a bit.\n\n> Next, I inspected the buffering code itself, and found an important\n> difference. Specifically, every call to hashwrite() was causing a flush\n> of the filestream, even if it was a very small write. With many callers\n> using helpers like hashwrite_be32() to write integers in network-byte\n> order, this was leading to many more file flushes than necessary.\n\nThis is incorrect. I misinterpreted the logic inside the loop, and I\nlater confirmed using trace2 that the number of flushes is the same\nbetween versions.\n\nSo, what happened with my performance tests?\n\n> As for performance, I focused on known commands that spend a significant\n> amount of time writing through the hashfile API, especially if using\n> small buffers as in hashwrite_be32(). 'git multi-pack-index write' was\n> an excellent example (deleting the multi-pack-index file between runs)\n> and demonstrated this performance change in the Linux kernal repo:\n...\n> Summary\n>   'new' ran\n>     1.03 ± 0.07 times faster than 'old'\n> \n> Similarly, the same command on the Git repository gave these numbers:\n...\n> Summary\n>   'new' ran\n>     1.05 ± 0.04 times faster than 'old'\n> \n> Finally, to demonstrate that performance holds when frequently using\n> large buffers, the numbers below are for 'git pack-objects' packing all\n> objects in the Git repository between v2.30.0 and v2.31.1:\n...\n> Summary\n>   'new' ran\n>     1.03 ± 0.06 times faster than 'old'\n>\n> With these consistent improvements of 3-5%, ...\n\nThese numbers seems consistent, across repos and test commands. They\nseem to be the inverse of the slowdown I was seeing in the index\nrefactor. These caused me to use confirmation bias to assume I had\ndone something clever.\n\nI was using hyperfine to run these numbers, with the hope that it\nprovides a consistent scenario worthy of testing. I used this command,\nroughly (in a script):\n\nhyperfine \\\n        -n \"old\" \"$1 && $OLD_GIT $2 <input\" \\\n        -n \"new\" \"$1 && $NEW_GIT $2 <input\" \\\n        --warmup=3 \\\n        --min-runs=20\n\nwhere I would pass some preparatory step as \"$1\" and the Git commands\nto run as \"$2\", and have an input file (necessary for the pack-objects\ncommand).\n\nThe first thing I did when confronted with the flush problem was swap\nthe order of the \"old\" and \"new\" lines, and that caused the performance\ndifference to go away, hinting that the number of warmups needed to\nincrease. Changing to \"--warmup=20\" and \"--min-runs=50\", the change in\ntiming went away entirely.\n\nI did the same with my draft changes to the index write code, and that\ncaused the 1-2% performance drop go away, too. So, this whole adventure\nwas based on a faulty performance test.\n\nBut...is there something we could still do here?\n\nMy confusion about flushing is mostly due to my error, but upon\nreflection the loop is doing a lot of different things, but most of\nthe time we know which behavior we need at the start, in the middle,\nand at the end:\n\n     1. Fill the existing buffer with the beginning of 'buf'. If the\n        hashfile's buffer is full, then flush.\n    \n     2. Flush sizeof(f->buffer) chunks directly out of 'buf' as long as\n        possible.\n    \n     3. Copy the remaining byes out of 'buf' into the hashfile's buffer.\n\nHere is a rewrite that more explicitly follows this flow:\n\nvoid hashwrite(struct hashfile *f, const void *buf, unsigned int count)\n{\n\tconst int full_buffer = sizeof(f->buffer);\n\tunsigned left = full_buffer - f->offset;\n\tunsigned nr = count > left ? left : count;\n\n\t/*\n\t * Initially fill the buffer in a batch until it\n\t * is full, then flush.\n\t */\n\tif (f->do_crc)\n\t\tf->crc32 = crc32(f->crc32, buf, nr);\n\n\tmemcpy(f->buffer + f->offset, buf, nr);\n\tf->offset += nr;\n\tcount -= nr;\n\tbuf = (char *) buf + nr;\n\n\tif (left == nr)\n\t\thashflush(f);\n\n\t/*\n\t * After filling the hashfile's buffer and flushing, take\n\t * batches of full_buffer bytes directly from the input\n\t * buffer.\n\t */\n\twhile (count >= full_buffer) {\n\t\tif (f->do_crc)\n\t\t\tf->crc32 = crc32(f->crc32, buf, full_buffer);\n\n\t\tthe_hash_algo->update_fn(&f->ctx, buf, full_buffer);\n\t\tflush(f, buf, full_buffer);\n\n\t\tcount -= full_buffer;\n\t\tbuf = (char *) buf + full_buffer;\n\t}\n\n\t/*\n\t * Capture any remaining bytes at the end of the input buffer\n\t * into the hashfile's buffer. We do not need to flush because\n\t * count is strictly less than full_buffer here.\n\t */\n\tif (count) {\n\t\tif (f->do_crc)\n\t\t\tf->crc32 = crc32(f->crc32, buf, count);\n\n\t\tmemcpy(f->buffer + f->offset, buf, count);\n\t\tf->offset = count;\n\t}\n\t\n\tif (f->base)\n\t\thashwrite(f->base, buf, count);\n}\n\nWith this implementation (and the more robust performance test), the\nperformance for pack-objects and index-pack remains constant, but\nthere is a slight improvement for 'git multi-pack-index write', which\nis mostly translating data from the pack-indexes into a multi-pack-\nindex:\n\n    Using the Git repository:\n    \n    Benchmark #1: old\n      Time (mean ± σ):     270.4 ms ±   6.9 ms    [User: 184.6 ms, System: 38.6 ms]\n      Range (min … max):   258.6 ms … 283.2 ms    50 runs\n    \n    Benchmark #2: new\n      Time (mean ± σ):     265.3 ms ±   6.0 ms    [User: 180.9 ms, System: 37.8 ms]\n      Range (min … max):   257.4 ms … 282.0 ms    50 runs\n    \n    Summary\n      'new' ran\n        1.02 ± 0.03 times faster than 'old'\n    \n    Using the Linux kernel repository:\n    \n    Benchmark #1: old\n      Time (mean ± σ):      2.321 s ±  0.011 s    [User: 1.538 s, System: 0.335 s]\n      Range (min … max):    2.301 s …  2.353 s    50 runs\n    \n    Benchmark #2: new\n      Time (mean ± σ):      2.290 s ±  0.011 s    [User: 1.513 s, System: 0.329 s]\n      Range (min … max):    2.273 s …  2.318 s    50 runs\n    \n    Summary\n      'new' ran\n        1.01 ± 0.01 times faster than 'old'\n\nAgain, variance might be at play here, but after running this\ntest multiple times, I was never able to see less than 1% reported\nhere.\n\nSo, I'm of two minds here:\n\n 1. This is embarassing. I wasted everyone's time for nothing. I can retract\n    this patch.\n\n 2. This is embarassing. I overstated the problem here. But we might be able\n    to eke out a tiny performance boost here.\n\nI'm open to either. I think we should default to dropping this patch unless\nsomeone thinks the rewrite above is a better organization of the logic. (I\ncan then send a v2 including that version and an updated commit message.)\n\nThanks,\n-Stolee\n\nP.S. Special thanks to Peff who pointed out my error in private.\n"},{"id":"420199","messageId":"xmqq8s6bvzpf.fsf@gitster.g","threadId":"55380","inReplyTo":"84ccabca-0bd3-d0cb-6b38-f96d75c0bbd6@gmail.com","subject":"Re: [PATCH] csum-file: flush less often","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-03-25T18:46:20Z","receivedAt":"2021-03-25T18:47:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n\n> But...is there something we could still do here?\n>\n> My confusion about flushing is mostly due to my error, but upon\n> reflection the loop is doing a lot of different things, but most of\n> the time we know which behavior we need at the start, in the middle,\n> and at the end:\n>\n>      1. Fill the existing buffer with the beginning of 'buf'. If the\n>         hashfile's buffer is full, then flush.\n\n\"But do not do this if f->buffer is empty, and we are writing out\nmore than sizeof(f->buffer).\" is missing, isn't it?\n\n>      2. Flush sizeof(f->buffer) chunks directly out of 'buf' as long as\n>         possible.\n>     \n>      3. Copy the remaining bytes out of 'buf' into the hashfile's buffer.\n\nIt is debatable if the existing loop, which came mostly from Nico's\na8032d12 (sha1write: don't copy full sized buffers, 2008-09-02), is\ntoo clever; I personally find it concise and readable enough, but my\nreading is tainted.\n\nIf you use a couple of helpers to reduce the repeated \"crc and hash\"\npattern in your variant, it may become easier to follow than the\noriginal, but I dunno.\n\n> Here is a rewrite that more explicitly follows this flow:\n>\n> void hashwrite(struct hashfile *f, const void *buf, unsigned int count)\n> {\n> \tconst int full_buffer = sizeof(f->buffer);\n> \tunsigned left = full_buffer - f->offset;\n> \tunsigned nr = count > left ? left : count;\n>\n> \t/*\n> \t * Initially fill the buffer in a batch until it\n> \t * is full, then flush.\n> \t */\n> \tif (f->do_crc)\n> \t\tf->crc32 = crc32(f->crc32, buf, nr);\n>\n> \tmemcpy(f->buffer + f->offset, buf, nr);\n\nHere, if the f->buffer was empty, we end up memcpy a full bufferful\nunconditionally.  Nico's original cleverly takes advantage of the\nfact that 'nr' would be the full buffer size only when the f->buffer\nwas empty upon entry to the function and we have more byte than the\nsize of the buffer to copy out directly from 'buf'.\n\n> \tf->offset += nr;\n> \tcount -= nr;\n> \tbuf = (char *) buf + nr;\n>\n> \tif (left == nr)\n> \t\thashflush(f);\n>\n> \t/*\n> \t * After filling the hashfile's buffer and flushing, take\n> \t * batches of full_buffer bytes directly from the input\n> \t * buffer.\n> \t */\n> \twhile (count >= full_buffer) {\n> \t\tif (f->do_crc)\n> \t\t\tf->crc32 = crc32(f->crc32, buf, full_buffer);\n>\n> \t\tthe_hash_algo->update_fn(&f->ctx, buf, full_buffer);\n> \t\tflush(f, buf, full_buffer);\n>\n> \t\tcount -= full_buffer;\n> \t\tbuf = (char *) buf + full_buffer;\n> \t}\n>\n> \t/*\n> \t * Capture any remaining bytes at the end of the input buffer\n> \t * into the hashfile's buffer. We do not need to flush because\n> \t * count is strictly less than full_buffer here.\n> \t */\n> \tif (count) {\n> \t\tif (f->do_crc)\n> \t\t\tf->crc32 = crc32(f->crc32, buf, count);\n>\n> \t\tmemcpy(f->buffer + f->offset, buf, count);\n> \t\tf->offset = count;\n> \t}\n> \t\n> \tif (f->base)\n> \t\thashwrite(f->base, buf, count);\n> }\n> ...\n> So, I'm of two minds here:\n>\n>  1. This is embarassing. I wasted everyone's time for nothing. I can retract\n>     this patch.\n>\n>  2. This is embarassing. I overstated the problem here. But we might be able\n>     to eke out a tiny performance boost here.\n>\n> I'm open to either. I think we should default to dropping this patch unless\n> someone thinks the rewrite above is a better organization of the logic. (I\n> can then send a v2 including that version and an updated commit message.)\n\n3. The current code around \"if (nr == sizeof(f->buffer))\" might be a\n   bit too clever for readers who try to understand what is going\n   on, and the whole \"while\" loop may deserve a comment based on\n   what you wrote before your replacement implementation.\n"},{"id":"420200","messageId":"xmqq4kgzvzf6.fsf@gitster.g","threadId":"55380","inReplyTo":"xmqq8s6bvzpf.fsf@gitster.g","subject":"Re: [PATCH] csum-file: flush less often","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-03-25T18:52:29Z","receivedAt":"2021-03-25T18:53:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n>> So, I'm of two minds here:\n>>\n>>  1. This is embarassing. I wasted everyone's time for nothing. I can retract\n>>     this patch.\n>>\n>>  2. This is embarassing. I overstated the problem here. But we might be able\n>>     to eke out a tiny performance boost here.\n>>\n>> I'm open to either. I think we should default to dropping this patch unless\n>> someone thinks the rewrite above is a better organization of the logic. (I\n>> can then send a v2 including that version and an updated commit message.)\n>\n> 3. The current code around \"if (nr == sizeof(f->buffer))\" might be a\n>    bit too clever for readers who try to understand what is going\n>    on, and the whole \"while\" loop may deserve a comment based on\n>    what you wrote before your replacement implementation.\n\nHaving said all that, comparing the original and the version updated\nwith your \"flush less often\" patch, I find the latter quite easier\nto read, so as long as the update does not give us 1% slowdown, it\nmay be worth adopting for the readability improvement alone.\n\nOf course, if we were to go that route, the sales pitch in the log\nmessage needs to be updated.\n\nThanks.\n"},{"id":"420224","messageId":"YF1SJRhb8hz7NP0/@coredump.intra.peff.net","threadId":"55380","inReplyTo":"xmqq4kgzvzf6.fsf@gitster.g","subject":"Re: [PATCH] csum-file: flush less often","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-03-26T03:16:53Z","receivedAt":"2021-03-26T03:17:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Mar 25, 2021 at 11:52:29AM -0700, Junio C Hamano wrote:\n\n> Junio C Hamano <gitster@pobox.com> writes:\n> \n> >> So, I'm of two minds here:\n> >>\n> >>  1. This is embarassing. I wasted everyone's time for nothing. I can retract\n> >>     this patch.\n> >>\n> >>  2. This is embarassing. I overstated the problem here. But we might be able\n> >>     to eke out a tiny performance boost here.\n> >>\n> >> I'm open to either. I think we should default to dropping this patch unless\n> >> someone thinks the rewrite above is a better organization of the logic. (I\n> >> can then send a v2 including that version and an updated commit message.)\n> >\n> > 3. The current code around \"if (nr == sizeof(f->buffer))\" might be a\n> >    bit too clever for readers who try to understand what is going\n> >    on, and the whole \"while\" loop may deserve a comment based on\n> >    what you wrote before your replacement implementation.\n\nYes, my first thought on reading Stolee's post-image was: wait, how do\nwe know when data needed flushed from the buffer? But that is not new in\nhis patch. It is confusing before and after. :)\n\n> Having said all that, comparing the original and the version updated\n> with your \"flush less often\" patch, I find the latter quite easier\n> to read, so as long as the update does not give us 1% slowdown, it\n> may be worth adopting for the readability improvement alone.\n> \n> Of course, if we were to go that route, the sales pitch in the log\n> message needs to be updated.\n\nYeah, I am OK with either version, as long as it is justified correctly\nin the commit message. IMHO the big difference is that the original is\nusing local data/offset variables in order to provide a layer of\nindirection when we get to the hash+flush code. And Stolee's patch is\ncalling the same code in the two places instead.\n\nIt's quite possible that gives the compiler slightly more opportunity to\nmicro-optimize (which doesn't matter if you are feeding big blocks, but\nmay if you are feeding 4 bytes at a time as in the midx code; though in\nthat case it is entirely possible that the caller allocating a single\narray, writing it, and then feeding it to hashwrite() would be faster\nstill, though a little more cumbersome).\n\n-Peff\n"},{"id":"420258","messageId":"pull.914.v2.git.1616762291574.gitgitgadget@gmail.com","threadId":"55380","inReplyTo":"pull.914.git.1616608219602.gitgitgadget@gmail.com","subject":"[PATCH v2] csum-file: make hashwrite() more readable","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-26T12:38:11Z","receivedAt":"2021-03-26T12:39:32Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <dstolee@microsoft.com>\n\nThe hashwrite() method takes an input buffer and updates a hashfile's\nhash function while writing the data to a file. To avoid overuse of\nflushes, the hashfile has an internal buffer and most writes will use\nmemcpy() to transfer data from the input 'buf' to the hashfile's buffer\nof size 8 * 1024 bytes.\n\nLogic introduced by a8032d12 (sha1write: don't copy full sized buffers,\n2008-09-02) reduces the number of memcpy() calls when the input buffer\nis sufficiently longer than the hashfile's buffer, causing nr to be the\nlength of the full buffer. In these cases, the input buffer is used\ndirectly in chunks equal to the hashfile's buffer size.\n\nThis method caught my attention while investigating some performance\nissues, but it turns out that these performance issues were noise within\nthe variance of the experiment.\n\nHowever, during this investigation, I inspected hashwrite() and\nmisunderstood it, even after looking closely and trying to make it\nfaster. This change simply reorganizes some parts of the loop within\nhashwrite() to make it clear that each batch either uses memcpy() to the\nhashfile's buffer or writes directly from the input buffer. The previous\ncode relied on indirection through local variables and essentially\ninlined the implementation of hashflush() to reduce lines of code.\n\nHelped-by: Jeff King <peff@peff.net>\nHelped-by: Junio C Hamano <gitster@pobox.com>\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n    csum-file: make hashwrite() more readable\n    \n    v2 adds comments to the implementation to make some assumptions very\n    clear about what is happening in each case.\n    \n    The commit message is almost completely rewritten based on the\n    discussion on-list.\n    \n    Thanks, -Stolee\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-914%2Fderrickstolee%2Fhashfile-flush-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-914/derrickstolee/hashfile-flush-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/914\n\nRange-diff vs v1:\n\n 1:  91995baaaa42 ! 1:  68a429b0ba7e csum-file: flush less often\n     @@ Metadata\n      Author: Derrick Stolee <dstolee@microsoft.com>\n      \n       ## Commit message ##\n     -    csum-file: flush less often\n     -\n     -    In an independent investigation, I noticed that do_write_index() in\n     -    read-cache.c has its own hashing logic and buffering mechanism.\n     -    Specifically, the ce_write() method was introduced by 4990aadc (Speed up\n     -    index file writing by chunking it nicely, 2005-04-20) and similar\n     -    mechanisms were introduced a few months later in c38138cd\n     -    (git-pack-objects: write the pack files with a SHA1 csum, 2005-06-26).\n     -    Based on the timing, in the early days of the Git codebase, I figured\n     -    that these roughly equivalent code paths were never unified only because\n     -    it got lost in the shuffle. The hashfile API has since been used\n     -    extensively in other file formats, such as pack-indexes,\n     -    mult-pack-indexes, and commit-graphs. Therefore, it seems prudent to\n     -    unify the index writing code to use the same mechanism.\n     -\n     -    However, upon doing that refactoring process, I noticed that this caused\n     -    some commands that write the index to slow down by 1-2%! I then looked\n     -    for a reason why this could be.\n     -\n     -    First, I noticed that the mechanisms use different buffer sizes. The\n     -    hashfile uses an 8KB buffer while the index uses an 128KB buffer.\n     -    Testing with a variety of different buffer sizes made little difference.\n     -\n     -    Next, I inspected the buffering code itself, and found an important\n     -    difference. Specifically, every call to hashwrite() was causing a flush\n     -    of the filestream, even if it was a very small write. With many callers\n     -    using helpers like hashwrite_be32() to write integers in network-byte\n     -    order, this was leading to many more file flushes than necessary.\n     -\n     -    This change modifies hashwrite() to always populate the hashfile buffer,\n     -    and only flush when that buffer is full. This is safe to do because all\n     -    consumers of a hashfile must call finalize_hashfile(), which flushes the\n     -    buffer at the start.\n     -\n     -    It is worth noting that this is modifying logic introduced by a8032d12\n     -    (sha1write: don't copy full sized buffers, 2008-09-02) which reduces\n     -    memcpy() calls when the input buffer is sufficiently longer than the\n     -    hashfile's buffer, causing nr to be the length of the full buffer. Use\n     -    the input buffer directly in these cases. Since we don't guarantee that\n     -    the buffer is flushed by the end of hashwrite(), we need to group some\n     -    offset logic into the condition that memcpy() is necessary. Note that nr\n     -    is equal to sizeof(f->buffer) only when f->offset is zero, so that\n     -    condition does not need to be added here.\n     -\n     -    As for performance, I focused on known commands that spend a significant\n     -    amount of time writing through the hashfile API, especially if using\n     -    small buffers as in hashwrite_be32(). 'git multi-pack-index write' was\n     -    an excellent example (deleting the multi-pack-index file between runs)\n     -    and demonstrated this performance change in the Linux kernal repo:\n     -\n     -    Benchmark #1: old\n     -      Time (mean ± σ):      2.229 s ±  0.143 s    [User: 1.409 s, System: 0.327 s]\n     -      Range (min … max):    2.160 s …  2.636 s    10 runs\n     -\n     -    Benchmark #2: new\n     -      Time (mean ± σ):      2.162 s ±  0.005 s    [User: 1.392 s, System: 0.323 s]\n     -      Range (min … max):    2.152 s …  2.172 s    10 runs\n     -\n     -    Summary\n     -      'new' ran\n     -        1.03 ± 0.07 times faster than 'old'\n     -\n     -    Similarly, the same command on the Git repository gave these numbers:\n     -\n     -    Benchmark #1: old\n     -      Time (mean ± σ):     230.5 ms ±   6.3 ms    [User: 140.5 ms, System: 42.9 ms]\n     -      Range (min … max):   221.7 ms … 240.6 ms    12 runs\n     -\n     -    Benchmark #2: new\n     -      Time (mean ± σ):     220.6 ms ±   5.1 ms    [User: 139.5 ms, System: 34.1 ms]\n     -      Range (min … max):   214.0 ms … 229.0 ms    13 runs\n     -\n     -    Summary\n     -      'new' ran\n     -        1.05 ± 0.04 times faster than 'old'\n     -\n     -    Finally, to demonstrate that performance holds when frequently using\n     -    large buffers, the numbers below are for 'git pack-objects' packing all\n     -    objects in the Git repository between v2.30.0 and v2.31.1:\n     -\n     -    Benchmark #1: old\n     -      Time (mean ± σ):      1.003 s ±  0.045 s    [User: 1.877 s, System: 0.167 s]\n     -      Range (min … max):    0.931 s …  1.044 s    10 runs\n     -\n     -    Benchmark #2: new\n     -      Time (mean ± σ):     976.4 ms ±  42.2 ms    [User: 1.854 s, System: 0.192 s]\n     -      Range (min … max):   940.1 ms … 1049.3 ms    10 runs\n     -\n     -    Summary\n     -      'new' ran\n     -        1.03 ± 0.06 times faster than 'old'\n     -\n     -    With these consistent improvements of 3-5%, it will be possible to move\n     -    the index writing logic over to hashfile without performance\n     -    degradation.\n     -\n     +    csum-file: make hashwrite() more readable\n     +\n     +    The hashwrite() method takes an input buffer and updates a hashfile's\n     +    hash function while writing the data to a file. To avoid overuse of\n     +    flushes, the hashfile has an internal buffer and most writes will use\n     +    memcpy() to transfer data from the input 'buf' to the hashfile's buffer\n     +    of size 8 * 1024 bytes.\n     +\n     +    Logic introduced by a8032d12 (sha1write: don't copy full sized buffers,\n     +    2008-09-02) reduces the number of memcpy() calls when the input buffer\n     +    is sufficiently longer than the hashfile's buffer, causing nr to be the\n     +    length of the full buffer. In these cases, the input buffer is used\n     +    directly in chunks equal to the hashfile's buffer size.\n     +\n     +    This method caught my attention while investigating some performance\n     +    issues, but it turns out that these performance issues were noise within\n     +    the variance of the experiment.\n     +\n     +    However, during this investigation, I inspected hashwrite() and\n     +    misunderstood it, even after looking closely and trying to make it\n     +    faster. This change simply reorganizes some parts of the loop within\n     +    hashwrite() to make it clear that each batch either uses memcpy() to the\n     +    hashfile's buffer or writes directly from the input buffer. The previous\n     +    code relied on indirection through local variables and essentially\n     +    inlined the implementation of hashflush() to reduce lines of code.\n     +\n     +    Helped-by: Jeff King <peff@peff.net>\n     +    Helped-by: Junio C Hamano <gitster@pobox.com>\n          Signed-off-by: Derrick Stolee <dstolee@microsoft.com>\n      \n       ## csum-file.c ##\n     @@ csum-file.c: int finalize_hashfile(struct hashfile *f, unsigned char *result, un\n       \t\t\tf->crc32 = crc32(f->crc32, buf, nr);\n       \n       \t\tif (nr == sizeof(f->buffer)) {\n     - \t\t\t/* process full buffer directly without copy */\n     +-\t\t\t/* process full buffer directly without copy */\n      -\t\t\tdata = buf;\n     ++\t\t\t/*\n     ++\t\t\t * Flush a full batch worth of data directly\n     ++\t\t\t * from the input, skipping the memcpy() to\n     ++\t\t\t * the hashfile's buffer. In this block,\n     ++\t\t\t * f->offset is necessarily zero.\n     ++\t\t\t */\n      +\t\t\tthe_hash_algo->update_fn(&f->ctx, buf, nr);\n      +\t\t\tflush(f, buf, nr);\n       \t\t} else {\n      -\t\t\tmemcpy(f->buffer + offset, buf, nr);\n      -\t\t\tdata = f->buffer;\n     ++\t\t\t/*\n     ++\t\t\t * Copy to the hashfile's buffer, flushing only\n     ++\t\t\t * if it became full.\n     ++\t\t\t */\n      +\t\t\tmemcpy(f->buffer + f->offset, buf, nr);\n      +\t\t\tf->offset += nr;\n      +\t\t\tleft -= nr;\n\n\n csum-file.c | 33 ++++++++++++++++++---------------\n 1 file changed, 18 insertions(+), 15 deletions(-)\n\ndiff --git a/csum-file.c b/csum-file.c\nindex 0f35fa5ee47c..7510950fa3e9 100644\n--- a/csum-file.c\n+++ b/csum-file.c\n@@ -89,32 +89,35 @@ int finalize_hashfile(struct hashfile *f, unsigned char *result, unsigned int fl\n void hashwrite(struct hashfile *f, const void *buf, unsigned int count)\n {\n \twhile (count) {\n-\t\tunsigned offset = f->offset;\n-\t\tunsigned left = sizeof(f->buffer) - offset;\n+\t\tunsigned left = sizeof(f->buffer) - f->offset;\n \t\tunsigned nr = count > left ? left : count;\n-\t\tconst void *data;\n \n \t\tif (f->do_crc)\n \t\t\tf->crc32 = crc32(f->crc32, buf, nr);\n \n \t\tif (nr == sizeof(f->buffer)) {\n-\t\t\t/* process full buffer directly without copy */\n-\t\t\tdata = buf;\n+\t\t\t/*\n+\t\t\t * Flush a full batch worth of data directly\n+\t\t\t * from the input, skipping the memcpy() to\n+\t\t\t * the hashfile's buffer. In this block,\n+\t\t\t * f->offset is necessarily zero.\n+\t\t\t */\n+\t\t\tthe_hash_algo->update_fn(&f->ctx, buf, nr);\n+\t\t\tflush(f, buf, nr);\n \t\t} else {\n-\t\t\tmemcpy(f->buffer + offset, buf, nr);\n-\t\t\tdata = f->buffer;\n+\t\t\t/*\n+\t\t\t * Copy to the hashfile's buffer, flushing only\n+\t\t\t * if it became full.\n+\t\t\t */\n+\t\t\tmemcpy(f->buffer + f->offset, buf, nr);\n+\t\t\tf->offset += nr;\n+\t\t\tleft -= nr;\n+\t\t\tif (!left)\n+\t\t\t\thashflush(f);\n \t\t}\n \n \t\tcount -= nr;\n-\t\toffset += nr;\n \t\tbuf = (char *) buf + nr;\n-\t\tleft -= nr;\n-\t\tif (!left) {\n-\t\t\tthe_hash_algo->update_fn(&f->ctx, data, offset);\n-\t\t\tflush(f, data, offset);\n-\t\t\toffset = 0;\n-\t\t}\n-\t\tf->offset = offset;\n \t}\n }\n \n\nbase-commit: 142430338477d9d1bb25be66267225fb58498d92\n-- \ngitgitgadget\n"},{"id":"420283","messageId":"xmqqlfa9siis.fsf@gitster.g","threadId":"55380","inReplyTo":"pull.914.v2.git.1616762291574.gitgitgadget@gmail.com","subject":"Re: [PATCH v2] csum-file: make hashwrite() more readable","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-03-26T21:38:03Z","receivedAt":"2021-03-26T21:39:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n>  \t\tif (nr == sizeof(f->buffer)) {\n> -\t\t\t/* process full buffer directly without copy */\n> -\t\t\tdata = buf;\n> +\t\t\t/*\n> +\t\t\t * Flush a full batch worth of data directly\n> +\t\t\t * from the input, skipping the memcpy() to\n> +\t\t\t * the hashfile's buffer. In this block,\n> +\t\t\t * f->offset is necessarily zero.\n> +\t\t\t */\n\nWhat made me a bit confused was the fact that, in order to exercise\nthe \"bypass memcpy and take a full bufferful from the incoming data\ndirectly\" optimization, there are two preconditions.  The incoming\ndata must be large enough, and we do not have anything kept in the\nbuffer that needs to be emitted before the incoming data.  And the\ncleverness of the original code was that both are checked by this\nsingle \"nr == sizeof(f->buffer)\" condition.\n\nSo I do appreciate this extra comment, and I think future readers of\nthe code will, too.\n\n> +\t\t\tthe_hash_algo->update_fn(&f->ctx, buf, nr);\n> +\t\t\tflush(f, buf, nr);\n>  \t\t} else {\n> -\t\t\tmemcpy(f->buffer + offset, buf, nr);\n> -\t\t\tdata = f->buffer;\n> +\t\t\t/*\n> +\t\t\t * Copy to the hashfile's buffer, flushing only\n> +\t\t\t * if it became full.\n> +\t\t\t */\n> +\t\t\tmemcpy(f->buffer + f->offset, buf, nr);\n> +\t\t\tf->offset += nr;\n> +\t\t\tleft -= nr;\n> +\t\t\tif (!left)\n> +\t\t\t\thashflush(f);\n>  \t\t}\n>  \n>  \t\tcount -= nr;\n> -\t\toffset += nr;\n>  \t\tbuf = (char *) buf + nr;\n> -\t\tleft -= nr;\n> -\t\tif (!left) {\n> -\t\t\tthe_hash_algo->update_fn(&f->ctx, data, offset);\n> -\t\t\tflush(f, data, offset);\n> -\t\t\toffset = 0;\n> -\t\t}\n> -\t\tf->offset = offset;\n>  \t}\n>  }\n>  \n>\n> base-commit: 142430338477d9d1bb25be66267225fb58498d92\n"},{"id":"420373","messageId":"YGBAm9qNdn4elbKF@coredump.intra.peff.net","threadId":"55380","inReplyTo":"pull.914.v2.git.1616762291574.gitgitgadget@gmail.com","subject":"Re: [PATCH v2] csum-file: make hashwrite() more readable","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-03-28T08:38:51Z","receivedAt":"2021-03-28T08:45:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 26, 2021 at 12:38:11PM +0000, Derrick Stolee via GitGitGadget wrote:\n\n> However, during this investigation, I inspected hashwrite() and\n> misunderstood it, even after looking closely and trying to make it\n> faster. This change simply reorganizes some parts of the loop within\n> hashwrite() to make it clear that each batch either uses memcpy() to the\n> hashfile's buffer or writes directly from the input buffer. The previous\n> code relied on indirection through local variables and essentially\n> inlined the implementation of hashflush() to reduce lines of code.\n\nThanks, I think this nicely argues for the change here (and I agree the\nresult, especially with the comments, is much easier to understand).\n\n-Peff\n"}]}