{"thread":{"id":"7262","subject":"cleaner/better zlib sources?","startedAt":"2007-03-16T01:04:14Z","lastAt":"2007-03-21T02:54:26Z","messageCount":79,"participants":["Linus Torvalds","Shawn O. Pearce","Jeff Garzik","Matt Mackall","Davide Libenzi","Nicolas Pitre","Junio C Hamano","Jon Smirl","Morten Welinder","Julian Phillips","Avi Kivity","Robin Rosenberg","David Brodsky","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"37187","messageId":"Pine.LNX.4.64.0703151747110.3816@woody.linux-foundation.org","threadId":"7262","inReplyTo":null,"subject":"cleaner/better zlib sources?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-16T01:04:14Z","receivedAt":"2007-03-16T01:04:14Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nI looked at git profiles yesterday, and some of them are pretty scary. We \nspend about 50% of the time under some loads in just zlib uncompression, \nand when I actually looked closer at the zlib sources I can kind of \nunderstand why. That thing is horrid.\n\nThe sad part is that it looks like it should be quite possible to make \nzlib simply just perform better. The profiles seem to say that a lot of \nthe cost is literally in the \"inflate()\" state machine code (and by that I \nmean *not* the code itself, but literally in the indirect jump generated \nby the case-statement).\n\nNow, on any high-performance CPU, doing state-machines by having\n\n\tfor (;;)\n\t\tswitch (data->state) {\n\t\t\t...\n\t\t\tdata->state = NEW_STATE;\n\t\t\tcontinue;\n\t\t}\n\n(which is what zlib seems to be doing) is just about the worst possible \nway to code things.\n\nNow, it's possible that I'm just wrong, but the instruction-level profile \nreally did pinpoint the \"look up state branch pointer and jump to it\" as \nsome of the hottest part of that function. Which is just *evil*. You can \nmost likely use direct jumps within the loop (zero cost at all on most OoO \nCPU's) most of the time, and the entry condition is likely quite \npredictable too, so a lot of that overhead seems to be just sad and \nunnecessary.\n\nNow, I'm just wondering if anybody knows if there are better zlib \nimplementations out there? This really looks like it could be a noticeable \nperformance issue, but I'm lazy and would be much happier to hear that \nsomebody has already played with optimizing zlib. Especially since I'm not \n100% sure it's really going to be noticeable..\n\n\t\tLinus\n"},{"id":"37188","messageId":"20070316011029.GG29547@spearce.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703151747110.3816@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-16T01:10:29Z","receivedAt":"2007-03-16T01:10:29Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Linus Torvalds wrote:\n> I looked at git profiles yesterday, and some of them are pretty scary. We \n> spend about 50% of the time under some loads in just zlib uncompression, \n> and when I actually looked closer at the zlib sources I can kind of \n> understand why. That thing is horrid.\n\nYes. This is actually one of the motivations behind pack v4.\nWe don't store the \"important bits\" of commits and trees in zlib\ncompressed format at all; allowing us to completely bypass the\ninflate() penalty you describe.\n\nWe're already much faster on the linux-2.6 kernel tree, and that's\n*with* converting the pack raw data into text, then reparsing\nthat text into a struct commit* or a struct name_entry using the\ncurrent code. We're also planning on reworking those parsers to\nparse the raw pack data, allowing us to save some very unnecessary\nraw->string->raw conversion time.\n\nBut Nico and I still looking to use zlib for commit messages and\nblob content, so any improvements to inflate (or its replacement)\nwould still be most helpful.\n\n-- \nShawn.\n"},{"id":"37189","messageId":"45F9EED5.3070706@garzik.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703151747110.3816@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Jeff Garzik","fromEmail":"jeff@garzik.org","sentAt":"2007-03-16T01:11:49Z","receivedAt":"2007-03-16T01:11:49Z","isPatch":false,"sender":{"key":"jeff@garzik.org","avatar":null},"body":"Linus Torvalds wrote:\n> Now, it's possible that I'm just wrong, but the instruction-level profile \n> really did pinpoint the \"look up state branch pointer and jump to it\" as \n> some of the hottest part of that function. Which is just *evil*. You can \n\nISTR there are a bunch of state transitions per byte, which would make \nsense that it shows up on profiles.\n\n\n> Now, I'm just wondering if anybody knows if there are better zlib \n> implementations out there? This really looks like it could be a noticeable \n> performance issue, but I'm lazy and would be much happier to hear that \n> somebody has already played with optimizing zlib. Especially since I'm not \n> 100% sure it's really going to be noticeable..\n\nI could have sworn that either Matt Mackall or Ben LaHaise had cleaned \nup the existing zlib so much that it was practically a new \nimplementation. I'm not aware of any open source implementations \nindependent of zlib (except maybe that C++ behemoth, 7zip).\n\n\tJeff\n"},{"id":"37190","messageId":"20070316011457.GA4892@waste.org","threadId":"7262","inReplyTo":"45F9EED5.3070706@garzik.org","subject":"Re: cleaner/better zlib sources?","fromName":"Matt Mackall","fromEmail":"mpm@selenic.com","sentAt":"2007-03-16T01:14:57Z","receivedAt":"2007-03-16T01:14:57Z","isPatch":false,"sender":{"key":"mpm@selenic.com","avatar":null},"body":"On Thu, Mar 15, 2007 at 09:11:49PM -0400, Jeff Garzik wrote:\n> Linus Torvalds wrote:\n> >Now, it's possible that I'm just wrong, but the instruction-level profile \n> >really did pinpoint the \"look up state branch pointer and jump to it\" as \n> >some of the hottest part of that function. Which is just *evil*. You can \n> \n> ISTR there are a bunch of state transitions per byte, which would make \n> sense that it shows up on profiles.\n\nYep, not surprising.\n\n> >Now, I'm just wondering if anybody knows if there are better zlib \n> >implementations out there? This really looks like it could be a noticeable \n> >performance issue, but I'm lazy and would be much happier to hear that \n> >somebody has already played with optimizing zlib. Especially since I'm not \n> >100% sure it's really going to be noticeable..\n> \n> I could have sworn that either Matt Mackall or Ben LaHaise had cleaned \n> up the existing zlib so much that it was practically a new \n> implementation. I'm not aware of any open source implementations \n> independent of zlib (except maybe that C++ behemoth, 7zip).\n\nI cleaned up the version in lib/ that's used for boot on most systems.\nIt's quite a bit simpler and cleaner than the code lib/zlib (and\nelsewhere!). But making it faster is another matter entirely - I don't\nknow off-hand how the two compare.\n\n-- \nMathematics is the supreme nostalgia of our time.\n"},{"id":"37191","messageId":"Pine.LNX.4.64.0703151807010.4998@alien.or.mcafeemobile.com","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703151747110.3816@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2007-03-16T01:33:44Z","receivedAt":"2007-03-16T01:33:44Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Thu, 15 Mar 2007, Linus Torvalds wrote:\n\n> \n> I looked at git profiles yesterday, and some of them are pretty scary. We \n> spend about 50% of the time under some loads in just zlib uncompression, \n> and when I actually looked closer at the zlib sources I can kind of \n> understand why. That thing is horrid.\n> \n> The sad part is that it looks like it should be quite possible to make \n> zlib simply just perform better. The profiles seem to say that a lot of \n> the cost is literally in the \"inflate()\" state machine code (and by that I \n> mean *not* the code itself, but literally in the indirect jump generated \n> by the case-statement).\n> \n> Now, on any high-performance CPU, doing state-machines by having\n> \n> \tfor (;;)\n> \t\tswitch (data->state) {\n> \t\t\t...\n> \t\t\tdata->state = NEW_STATE;\n> \t\t\tcontinue;\n> \t\t}\n> \n> (which is what zlib seems to be doing) is just about the worst possible \n> way to code things.\n\nA quick hack would be to just define:\n\n#define SWITCH_LBL(n) \\\n\tcase n: \\\n\tlbl_##n:\n\n#define STATE_CHANGE(s) \\\n\tstate->mode = s; \\\n\tgoto lbl_##s;\n\nThen replace all the \"state->mode = STATE; break;\" into STATE_CHANGE(STATE);\nI'm giving it a try as we speak ...\n\n\n\n\n- Davide\n"},{"id":"37192","messageId":"Pine.LNX.4.64.0703151822490.3816@woody.linux-foundation.org","threadId":"7262","inReplyTo":"45F9EED5.3070706@garzik.org","subject":"Re: cleaner/better zlib sources?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-16T01:46:17Z","receivedAt":"2007-03-16T01:46:17Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 15 Mar 2007, Jeff Garzik wrote:\n> \n> ISTR there are a bunch of state transitions per byte, which would make sense\n> that it shows up on profiles.\n\nYeah. I only looked at the kernel sources (which include a cleaned-up \nolder version of zlib), but they seemed to match the disassembly that I \nsaw when doing the instruction-level profiling.\n\nThe code *sometimes* falls through from one state to another, ie there's a \ncase where zlib does:\n\n\t...\n case DICTID:\n NEEDBITS(32);\n strm->adler = state->check = REVERSE(hold);\n INITBITS();\n state->mode = DICT;\n case DICT:\n\t...\n\nwhich will obviously generate fine code. There's a few other examples of \nthat, *BUT* most of the stuff is just horrid, like\n\n case HEAD:\n if (state->wrap == 0) {\n state->mode = TYPEDO;\n break;\n }\n\nwhere the \"break\" (which simply breaks out of the case-statement, and thus \njust loops back to it:\n\n for (;;)\n switch (state->mode) {\n\nthing is nasty nasty nasty).\n\nA trivial thing to do is to just replace such\n\n\tstate->mode = xxx;\n\tbreak;\n\nwith\n\n\tstate->mode = xxx;\n\tgoto xxx_mode;\n\nand all of that complicated run-time code *just*goes*away* and is replaced \nby a relative no-op (ie an unconditional direct jump).\n\nSome of them are slightly more complex, like\n\n\tstate->mode = hold & 0x200 ? DICTID : TYPE;\n\tINITBITS();\n\tbreak;\n\nwhich would need to be rewritten as\n\n\told_hold = hold;\n\tINITBITS();\n\tif (old_hold & 0x200) {\n\t\tstate->mode = DICTID;\n\t\tgoto dictid_mode;\n\t}\n\tstate->mode = TYPE;\n\tgoto dictid_mode;\n\nbut while that looks more complicated on a source code level it's a *lot* \neasier for a CPU to actually execute.\n\nSame obvious performance problems go for\n\n\tcase STORED:\n\t ...\n case COPY:\n copy = state->length;\n if (copy) {\n\t\t...\n\t\tstate->length -= copy;\n\t\tbreak;\n\t }\n\t Tracev((stderr, \"inflate: stored end\\n\"));\n\t state->mode = TYPE;\n\t break;\n\nnotice how when you get to the COPY state it will actually have nicely \nfallen through from STORED (one of the places where it does that), but \nthen it will go through the expensive indirect jump not just once, but at \nleast *TWICE* just to get to the TYPE thing, because you'll first have to \nre-enter COPY with a count of zero to get to the place where it sets TYPE, \nand then does the indirect jump immediately again!\n\nIn other words, the code is *incredibly* badly written from a performance \nangle.\n\nYeah, a perfect compiler could do this all for us even with unchanged zlib \nsource code, but (a) gcc isn't perfect and (b) I don't really think \nanything else is either, although if things like this happen as part of \ngzip in SpecInt, I wouldn't be surprised by compilers doing things like \nthis just to look good ;)\n\nEspecially with something like git, where we know that most of the time we \nhave the full input buffer (so inflate() generally won't be called in the \n\"middle\" of a inflate event), we probably have a very well-defined start \nstate too, so we'd actually predict perfectlyon the *first* indirect jump \nif we just never did any more of them.\n\n> I could have sworn that either Matt Mackall or Ben LaHaise had cleaned up the\n> existing zlib so much that it was practically a new implementation. I'm not\n> aware of any open source implementations independent of zlib (except maybe\n> that C++ behemoth, 7zip).\n\nI looked at the latest release (1.2.3), so either Matt/Ben hasn't been \nmerged, or this wasn't part of the thing they looked at.\n\n\t\t\tLinus\n"},{"id":"37193","messageId":"Pine.LNX.4.64.0703151848090.3816@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703151822490.3816@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-16T01:54:23Z","receivedAt":"2007-03-16T01:54:23Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 15 Mar 2007, Linus Torvalds wrote:\n> \n> Same obvious performance problems go for\n>\n> case COPY:\n\nAs an example, I *think* this patch to zlib-1.2.3 not only generates \nbetter code, but is (a) shorter and (b) more logical anyway.\n\nTogether with Davide's suggestion on using C macro expansion to make most \nof the mode switches simple branches, it might get rid of most of the \nindirect branches (to get rid of them all, you'd have to also find the \nplaces where we *don't* set a new state, because it stays the same like \nthis one, and the ones where we have conditionals on what the mode is \ngoing to be..\n\nOf course, the zlib sources are pretty horrid for other reasons (K&R \nsource code meant to be compiled on 16-bit architectures too). But that's \na separate issue, and at least shouldn't affect the resulting code \nquality..\n\n\t\tLinus\n\n---\n inflate.c | 3 +--\n 1 files changed, 1 insertions(+), 2 deletions(-)\n\ndiff --git a/inflate.c b/inflate.c\nindex 792fdee..fb26f39 100644\n--- a/inflate.c\n+++ b/inflate.c\n@@ -819,7 +819,7 @@ int flush;\n state->mode = COPY;\n case COPY:\n copy = state->length;\n- if (copy) {\n+ while (copy) {\n if (copy > have) copy = have;\n if (copy > left) copy = left;\n if (copy == 0) goto inf_leave;\n@@ -829,7 +829,6 @@ int flush;\n left -= copy;\n put += copy;\n state->length -= copy;\n- break;\n }\n Tracev((stderr, \"inflate: stored end\\n\"));\n state->mode = TYPE;\n"},{"id":"37194","messageId":"Pine.LNX.4.64.0703151906050.4998@alien.or.mcafeemobile.com","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703151807010.4998@alien.or.mcafeemobile.com","subject":"Re: cleaner/better zlib sources?","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2007-03-16T02:06:53Z","receivedAt":"2007-03-16T02:06:53Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Thu, 15 Mar 2007, Davide Libenzi wrote:\n\n> On Thu, 15 Mar 2007, Linus Torvalds wrote:\n> \n> > \n> > I looked at git profiles yesterday, and some of them are pretty scary. We \n> > spend about 50% of the time under some loads in just zlib uncompression, \n> > and when I actually looked closer at the zlib sources I can kind of \n> > understand why. That thing is horrid.\n> > \n> > The sad part is that it looks like it should be quite possible to make \n> > zlib simply just perform better. The profiles seem to say that a lot of \n> > the cost is literally in the \"inflate()\" state machine code (and by that I \n> > mean *not* the code itself, but literally in the indirect jump generated \n> > by the case-statement).\n> > \n> > Now, on any high-performance CPU, doing state-machines by having\n> > \n> > \tfor (;;)\n> > \t\tswitch (data->state) {\n> > \t\t\t...\n> > \t\t\tdata->state = NEW_STATE;\n> > \t\t\tcontinue;\n> > \t\t}\n> > \n> > (which is what zlib seems to be doing) is just about the worst possible \n> > way to code things.\n> \n> A quick hack would be to just define:\n> \n> #define SWITCH_LBL(n) \\\n> \tcase n: \\\n> \tlbl_##n:\n> \n> #define STATE_CHANGE(s) \\\n> \tstate->mode = s; \\\n> \tgoto lbl_##s;\n> \n> Then replace all the \"state->mode = STATE; break;\" into STATE_CHANGE(STATE);\n> I'm giving it a try as we speak ...\n\nI get about 5-6% boost with it AFAICS ...\n\n\n\n- Davide\n"},{"id":"37195","messageId":"Pine.LNX.4.64.0703151941090.4998@alien.or.mcafeemobile.com","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703151848090.3816@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2007-03-16T02:43:17Z","receivedAt":"2007-03-16T02:43:17Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Thu, 15 Mar 2007, Linus Torvalds wrote:\n\n> \n> \n> On Thu, 15 Mar 2007, Linus Torvalds wrote:\n> > \n> > Same obvious performance problems go for\n> >\n> > case COPY:\n> \n> As an example, I *think* this patch to zlib-1.2.3 not only generates \n> better code, but is (a) shorter and (b) more logical anyway.\n> \n> Together with Davide's suggestion on using C macro expansion to make most \n> of the mode switches simple branches, it might get rid of most of the \n> indirect branches (to get rid of them all, you'd have to also find the \n> places where we *don't* set a new state, because it stays the same like \n> this one, and the ones where we have conditionals on what the mode is \n> going to be..\n\nThat's the diff against 1.2.3, but it does not seem to make an substantial \ndifference in my Opteron ...\n\n\n\n\n- Davide\n\n\n\nIndex: zlib-1.2.3.quilt/inflate.c\n===================================================================\n--- zlib-1.2.3.quilt.orig/inflate.c\t2007-03-15 18:17:19.000000000 -0700\n+++ zlib-1.2.3.quilt/inflate.c\t2007-03-15 18:31:14.000000000 -0700\n@@ -551,6 +551,15 @@\n will return Z_BUF_ERROR if it has not reached the end of the stream.\n */\n \n+#define CASE_DECL(n) \\\n+\tcase n: \\\n+\tlbl_##n:\n+\n+#define STATE_CHANGE(s) do { \\\n+\tstate->mode = s; \\\n+\tgoto lbl_##s; \\\n+} while (0)\n+\n int ZEXPORT inflate(strm, flush)\n z_streamp strm;\n int flush;\n@@ -586,10 +595,9 @@\n ret = Z_OK;\n for (;;)\n switch (state->mode) {\n- case HEAD:\n+ CASE_DECL(HEAD)\n if (state->wrap == 0) {\n- state->mode = TYPEDO;\n- break;\n+\t\tSTATE_CHANGE(TYPEDO);\n }\n NEEDBITS(16);\n #ifdef GUNZIP\n@@ -597,8 +605,7 @@\n state->check = crc32(0L, Z_NULL, 0);\n CRC2(state->check, hold);\n INITBITS();\n- state->mode = FLAGS;\n- break;\n+\t\tSTATE_CHANGE(FLAGS);\n }\n state->flags = 0; /* expect zlib header */\n if (state->head != Z_NULL)\n@@ -609,20 +616,17 @@\n #endif\n ((BITS(8) << 8) + (hold >> 8)) % 31) {\n strm->msg = (char *)\"incorrect header check\";\n- state->mode = BAD;\n- break;\n+\t STATE_CHANGE(BAD);\n }\n if (BITS(4) != Z_DEFLATED) {\n strm->msg = (char *)\"unknown compression method\";\n- state->mode = BAD;\n- break;\n+\t STATE_CHANGE(BAD);\n }\n DROPBITS(4);\n len = BITS(4) + 8;\n if (len > state->wbits) {\n strm->msg = (char *)\"invalid window size\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n state->dmax = 1U << len;\n Tracev((stderr, \"inflate: zlib header ok\\n\"));\n@@ -631,32 +635,30 @@\n INITBITS();\n break;\n #ifdef GUNZIP\n- case FLAGS:\n+ CASE_DECL(FLAGS)\n NEEDBITS(16);\n state->flags = (int)(hold);\n if ((state->flags & 0xff) != Z_DEFLATED) {\n strm->msg = (char *)\"unknown compression method\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n if (state->flags & 0xe000) {\n strm->msg = (char *)\"unknown header flags set\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n if (state->head != Z_NULL)\n state->head->text = (int)((hold >> 8) & 1);\n if (state->flags & 0x0200) CRC2(state->check, hold);\n INITBITS();\n state->mode = TIME;\n- case TIME:\n+ CASE_DECL(TIME)\n NEEDBITS(32);\n if (state->head != Z_NULL)\n state->head->time = hold;\n if (state->flags & 0x0200) CRC4(state->check, hold);\n INITBITS();\n state->mode = OS;\n- case OS:\n+ CASE_DECL(OS)\n NEEDBITS(16);\n if (state->head != Z_NULL) {\n state->head->xflags = (int)(hold & 0xff);\n@@ -665,7 +667,7 @@\n if (state->flags & 0x0200) CRC2(state->check, hold);\n INITBITS();\n state->mode = EXLEN;\n- case EXLEN:\n+ CASE_DECL(EXLEN)\n if (state->flags & 0x0400) {\n NEEDBITS(16);\n state->length = (unsigned)(hold);\n@@ -677,7 +679,7 @@\n else if (state->head != Z_NULL)\n state->head->extra = Z_NULL;\n state->mode = EXTRA;\n- case EXTRA:\n+ CASE_DECL(EXTRA)\n if (state->flags & 0x0400) {\n copy = state->length;\n if (copy > have) copy = have;\n@@ -699,7 +701,7 @@\n }\n state->length = 0;\n state->mode = NAME;\n- case NAME:\n+ CASE_DECL(NAME)\n if (state->flags & 0x0800) {\n if (have == 0) goto inf_leave;\n copy = 0;\n@@ -720,7 +722,7 @@\n state->head->name = Z_NULL;\n state->length = 0;\n state->mode = COMMENT;\n- case COMMENT:\n+ CASE_DECL(COMMENT)\n if (state->flags & 0x1000) {\n if (have == 0) goto inf_leave;\n copy = 0;\n@@ -740,13 +742,12 @@\n else if (state->head != Z_NULL)\n state->head->comment = Z_NULL;\n state->mode = HCRC;\n- case HCRC:\n+ CASE_DECL(HCRC)\n if (state->flags & 0x0200) {\n NEEDBITS(16);\n if (hold != (state->check & 0xffff)) {\n strm->msg = (char *)\"header crc mismatch\";\n- state->mode = BAD;\n- break;\n+\t\t STATE_CHANGE(BAD);\n }\n INITBITS();\n }\n@@ -755,28 +756,26 @@\n state->head->done = 1;\n }\n strm->adler = state->check = crc32(0L, Z_NULL, 0);\n- state->mode = TYPE;\n- break;\n+\t STATE_CHANGE(TYPE);\n #endif\n- case DICTID:\n+ CASE_DECL(DICTID)\n NEEDBITS(32);\n strm->adler = state->check = REVERSE(hold);\n INITBITS();\n state->mode = DICT;\n- case DICT:\n+ CASE_DECL(DICT)\n if (state->havedict == 0) {\n RESTORE();\n return Z_NEED_DICT;\n }\n strm->adler = state->check = adler32(0L, Z_NULL, 0);\n state->mode = TYPE;\n- case TYPE:\n+ CASE_DECL(TYPE)\n if (flush == Z_BLOCK) goto inf_leave;\n- case TYPEDO:\n+ CASE_DECL(TYPEDO)\n if (state->last) {\n BYTEBITS();\n- state->mode = CHECK;\n- break;\n+\t\tSTATE_CHANGE(CHECK);\n }\n NEEDBITS(3);\n state->last = BITS(1);\n@@ -785,39 +784,38 @@\n case 0: /* stored block */\n Tracev((stderr, \"inflate: stored block%s\\n\",\n state->last ? \" (last)\" : \"\"));\n- state->mode = STORED;\n- break;\n+\t\tDROPBITS(2);\n+\t\tSTATE_CHANGE(STORED);\n case 1: /* fixed block */\n fixedtables(state);\n Tracev((stderr, \"inflate: fixed codes block%s\\n\",\n state->last ? \" (last)\" : \"\"));\n- state->mode = LEN; /* decode codes */\n- break;\n+\t\tDROPBITS(2);\n+\t\tSTATE_CHANGE(LEN);\n case 2: /* dynamic block */\n Tracev((stderr, \"inflate: dynamic codes block%s\\n\",\n state->last ? \" (last)\" : \"\"));\n- state->mode = TABLE;\n- break;\n+\t\tDROPBITS(2);\n+\t\tSTATE_CHANGE(TABLE);\n case 3:\n+\t\tDROPBITS(2);\n strm->msg = (char *)\"invalid block type\";\n- state->mode = BAD;\n+\t\tSTATE_CHANGE(BAD);\n }\n- DROPBITS(2);\n break;\n- case STORED:\n+ CASE_DECL(STORED)\n BYTEBITS(); /* go to byte boundary */\n NEEDBITS(32);\n if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {\n strm->msg = (char *)\"invalid stored block lengths\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n state->length = (unsigned)hold & 0xffff;\n Tracev((stderr, \"inflate: stored length %u\\n\",\n state->length));\n INITBITS();\n state->mode = COPY;\n- case COPY:\n+ CASE_DECL(COPY)\n copy = state->length;\n if (copy) {\n if (copy > have) copy = have;\n@@ -832,9 +830,8 @@\n break;\n }\n Tracev((stderr, \"inflate: stored end\\n\"));\n- state->mode = TYPE;\n- break;\n- case TABLE:\n+\t STATE_CHANGE(TYPE);\n+ CASE_DECL(TABLE)\n NEEDBITS(14);\n state->nlen = BITS(5) + 257;\n DROPBITS(5);\n@@ -845,14 +842,13 @@\n #ifndef PKZIP_BUG_WORKAROUND\n if (state->nlen > 286 || state->ndist > 30) {\n strm->msg = (char *)\"too many length or distance symbols\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n #endif\n Tracev((stderr, \"inflate: table sizes ok\\n\"));\n state->have = 0;\n state->mode = LENLENS;\n- case LENLENS:\n+ CASE_DECL(LENLENS)\n while (state->have < state->ncode) {\n NEEDBITS(3);\n state->lens[order[state->have++]] = (unsigned short)BITS(3);\n@@ -867,13 +863,12 @@\n &(state->lenbits), state->work);\n if (ret) {\n strm->msg = (char *)\"invalid code lengths set\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n Tracev((stderr, \"inflate: code lengths ok\\n\"));\n state->have = 0;\n state->mode = CODELENS;\n- case CODELENS:\n+ CASE_DECL(CODELENS)\n while (state->have < state->nlen + state->ndist) {\n for (;;) {\n this = state->lencode[BITS(state->lenbits)];\n@@ -891,8 +886,7 @@\n DROPBITS(this.bits);\n if (state->have == 0) {\n strm->msg = (char *)\"invalid bit length repeat\";\n- state->mode = BAD;\n- break;\n+\t\t\t STATE_CHANGE(BAD);\n }\n len = state->lens[state->have - 1];\n copy = 3 + BITS(2);\n@@ -914,17 +908,13 @@\n }\n if (state->have + copy > state->nlen + state->ndist) {\n strm->msg = (char *)\"invalid bit length repeat\";\n- state->mode = BAD;\n- break;\n+\t\t\tSTATE_CHANGE(BAD);\n }\n while (copy--)\n state->lens[state->have++] = (unsigned short)len;\n }\n }\n \n- /* handle error breaks in while */\n- if (state->mode == BAD) break;\n-\n /* build code tables */\n state->next = state->codes;\n state->lencode = (code const FAR *)(state->next);\n@@ -933,8 +923,7 @@\n &(state->lenbits), state->work);\n if (ret) {\n strm->msg = (char *)\"invalid literal/lengths set\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n state->distcode = (code const FAR *)(state->next);\n state->distbits = 6;\n@@ -942,12 +931,11 @@\n &(state->next), &(state->distbits), state->work);\n if (ret) {\n strm->msg = (char *)\"invalid distances set\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n Tracev((stderr, \"inflate: codes ok\\n\"));\n state->mode = LEN;\n- case LEN:\n+ CASE_DECL(LEN)\n if (have >= 6 && left >= 258) {\n RESTORE();\n inflate_fast(strm, out);\n@@ -975,22 +963,19 @@\n Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?\n \"inflate: literal '%c'\\n\" :\n \"inflate: literal 0x%02x\\n\", this.val));\n- state->mode = LIT;\n- break;\n+\t\tSTATE_CHANGE(LIT);\n }\n if (this.op & 32) {\n Tracevv((stderr, \"inflate: end of block\\n\"));\n- state->mode = TYPE;\n- break;\n+\t\tSTATE_CHANGE(TYPE);\n }\n if (this.op & 64) {\n strm->msg = (char *)\"invalid literal/length code\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n state->extra = (unsigned)(this.op) & 15;\n state->mode = LENEXT;\n- case LENEXT:\n+ CASE_DECL(LENEXT)\n if (state->extra) {\n NEEDBITS(state->extra);\n state->length += BITS(state->extra);\n@@ -998,7 +983,7 @@\n }\n Tracevv((stderr, \"inflate: length %u\\n\", state->length));\n state->mode = DIST;\n- case DIST:\n+ CASE_DECL(DIST)\n for (;;) {\n this = state->distcode[BITS(state->distbits)];\n if ((unsigned)(this.bits) <= bits) break;\n@@ -1017,13 +1002,12 @@\n DROPBITS(this.bits);\n if (this.op & 64) {\n strm->msg = (char *)\"invalid distance code\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n state->offset = (unsigned)this.val;\n state->extra = (unsigned)(this.op) & 15;\n state->mode = DISTEXT;\n- case DISTEXT:\n+ CASE_DECL(DISTEXT)\n if (state->extra) {\n NEEDBITS(state->extra);\n state->offset += BITS(state->extra);\n@@ -1032,18 +1016,16 @@\n #ifdef INFLATE_STRICT\n if (state->offset > state->dmax) {\n strm->msg = (char *)\"invalid distance too far back\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n #endif\n if (state->offset > state->whave + out - left) {\n strm->msg = (char *)\"invalid distance too far back\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n Tracevv((stderr, \"inflate: distance %u\\n\", state->offset));\n state->mode = MATCH;\n- case MATCH:\n+ CASE_DECL(MATCH)\n if (left == 0) goto inf_leave;\n copy = out - left;\n if (state->offset > copy) { /* copy from window */\n@@ -1066,15 +1048,15 @@\n do {\n *put++ = *from++;\n } while (--copy);\n- if (state->length == 0) state->mode = LEN;\n+ if (state->length == 0)\n+\t\tSTATE_CHANGE(LEN);\n break;\n- case LIT:\n+ CASE_DECL(LIT)\n if (left == 0) goto inf_leave;\n *put++ = (unsigned char)(state->length);\n left--;\n- state->mode = LEN;\n- break;\n- case CHECK:\n+\t STATE_CHANGE(LEN);\n+ CASE_DECL(CHECK)\n if (state->wrap) {\n NEEDBITS(32);\n out -= left;\n@@ -1090,36 +1072,34 @@\n #endif\n REVERSE(hold)) != state->check) {\n strm->msg = (char *)\"incorrect data check\";\n- state->mode = BAD;\n- break;\n+\t\t STATE_CHANGE(BAD);\n }\n INITBITS();\n Tracev((stderr, \"inflate: check matches trailer\\n\"));\n }\n #ifdef GUNZIP\n state->mode = LENGTH;\n- case LENGTH:\n+ CASE_DECL(LENGTH)\n if (state->wrap && state->flags) {\n NEEDBITS(32);\n if (hold != (state->total & 0xffffffffUL)) {\n strm->msg = (char *)\"incorrect length check\";\n- state->mode = BAD;\n- break;\n+\t\t STATE_CHANGE(BAD);\n }\n INITBITS();\n Tracev((stderr, \"inflate: length matches trailer\\n\"));\n }\n #endif\n state->mode = DONE;\n- case DONE:\n+ CASE_DECL(DONE)\n ret = Z_STREAM_END;\n goto inf_leave;\n- case BAD:\n+ CASE_DECL(BAD)\n ret = Z_DATA_ERROR;\n goto inf_leave;\n- case MEM:\n+ CASE_DECL(MEM)\n return Z_MEM_ERROR;\n- case SYNC:\n+ CASE_DECL(SYNC)\n default:\n return Z_STREAM_ERROR;\n }\n"},{"id":"37196","messageId":"Pine.LNX.4.64.0703151955440.3816@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703151941090.4998@alien.or.mcafeemobile.com","subject":"Re: cleaner/better zlib sources?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-16T02:56:19Z","receivedAt":"2007-03-16T02:56:19Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 15 Mar 2007, Davide Libenzi wrote:\n> \n> That's the diff against 1.2.3, but it does not seem to make an substantial \n> difference in my Opteron ...\n\nBut the \"goto\" stuff you did is 5-6%? \n\nIs that 5-6% of total git costs, or just of inflate() itself?\n\n\t\tLinus\n"},{"id":"37197","messageId":"Pine.LNX.4.64.0703151955150.4998@alien.or.mcafeemobile.com","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703151955440.3816@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2007-03-16T03:16:00Z","receivedAt":"2007-03-16T03:16:00Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Thu, 15 Mar 2007, Linus Torvalds wrote:\n\n> \n> \n> On Thu, 15 Mar 2007, Davide Libenzi wrote:\n> > \n> > That's the diff against 1.2.3, but it does not seem to make an substantial \n> > difference in my Opteron ...\n> \n> But the \"goto\" stuff you did is 5-6%? \n> \n> Is that 5-6% of total git costs, or just of inflate() itself?\n\nDidn't do proper cache warmup and test time was fairly short. Now I'm not \nable to notice substantial differences.\nHacked up test case below ...\n\n\n\n\n- Davide\n\n\n\n/* example.c -- usage example of the zlib compression library\n * Copyright (C) 1995-2004 Jean-loup Gailly.\n * For conditions of distribution and use, see copyright notice in zlib.h\n */\n\n/* @(#) $Id$ */\n\n#include \n#include \n#include \n#include \n#include \n#include \"zlib.h\"\n\n\n\n#define CHECK_ERR(err, msg) do { \\\n\tif (err != Z_OK) { \\\n\t\tfprintf(stderr, \"%s error: %d\\n\", msg, err); \\\n\t\texit(1); \\\n\t} \\\n} while (0)\n\n\n\n\nunsigned long long getustime(void) {\n\tstruct timeval tm;\n\n\tgettimeofday(&tm, NULL);\n\treturn tm.tv_sec * 1000000ULL + tm.tv_usec;\n}\n\n\n/* ===========================================================================\n * Test deflate() with large buffers and dynamic change of compression level\n */\nvoid do_defl(Byte *compr, uLong *comprLen,\n\t Byte *uncompr, uLong uncomprLen) {\n\tz_stream c_stream; /* compression stream */\n\tint err;\n\n\tc_stream.zalloc = (alloc_func)0;\n\tc_stream.zfree = (free_func)0;\n\tc_stream.opaque = (voidpf)0;\n\n\terr = deflateInit(&c_stream, Z_BEST_SPEED);\n\tCHECK_ERR(err, \"deflateInit\");\n\n\tc_stream.next_out = compr;\n\tc_stream.avail_out = (uInt) *comprLen;\n\n\t/* At this point, uncompr is still mostly zeroes, so it should compress\n\t * very well:\n\t */\n\tc_stream.next_in = uncompr;\n\tc_stream.avail_in = (uInt) uncomprLen;\n\terr = deflate(&c_stream, Z_FINISH);\n\tif (err != Z_STREAM_END) {\n\t\tfprintf(stderr, \"whoops, got %d instead of Z_STREAM_END\\n\", err);\n\t\texit(1);\n\t}\n\n\terr = deflateEnd(&c_stream);\n\tCHECK_ERR(err, \"deflateEnd\");\n\n\t*comprLen = c_stream.next_out - compr;\n}\n\n/* ===========================================================================\n * Test inflate() with large buffers\n */\nvoid do_infl(Byte *compr, uLong comprLen,\n\t Byte *uncompr, uLong *uncomprLen) {\n\tint err;\n\tz_stream d_stream; /* decompression stream */\n\n\td_stream.zalloc = (alloc_func)0;\n\td_stream.zfree = (free_func)0;\n\td_stream.opaque = (voidpf)0;\n\n\td_stream.next_in = compr;\n\td_stream.avail_in = (uInt)comprLen;\n\n\terr = inflateInit(&d_stream);\n\tCHECK_ERR(err, \"inflateInit\");\n\n\td_stream.next_out = uncompr; /* discard the output */\n\td_stream.avail_out = (uInt) *uncomprLen;\n\terr = inflate(&d_stream, Z_FULL_FLUSH);\n\tif (err != Z_STREAM_END) {\n\t\tfprintf(stderr, \"deflate should report Z_STREAM_END\\n\");\n\t\texit(1);\n\t}\n\n\terr = inflateEnd(&d_stream);\n\tCHECK_ERR(err, \"inflateEnd\");\n\n\t*uncomprLen = d_stream.next_out - uncompr;\n}\n\n\nint main(int ac, char **av) {\n\tuLong i, n, clen, ulen, size = 8 * 1024 * 1024, range = 256;\n\tByte *ubuf, *cbuf, *tbuf;\n\tunsigned long long ts, te;\n\n\tsrand(1);\n\tulen = size;\n\tclen = 2 * ulen;\n\tubuf = malloc(ulen);\n\ttbuf = malloc(ulen);\n\tcbuf = malloc(clen);\n\tfor (i = 0; i < ulen; i++)\n\t\tubuf[i] = (Byte) (rand() % range);\n\n\t/* Warming up ... */\n\tdo_defl(cbuf, &clen, ubuf, ulen);\n\tdo_infl(cbuf, clen, tbuf, &ulen);\n\tif (ulen != size) {\n\t\tfprintf(stderr, \"size mismatch %lu instead of %lu\\n\",\n\t\t\t(unsigned long) ulen, (unsigned long) size);\n\t\treturn 1;\n\t}\n\tif (memcmp(tbuf, ubuf, size)) {\n\t\tfprintf(stderr, \"whoops! we did not get back the same data\\n\");\n\t\treturn 2;\n\t}\n\t/* Test ... */\n\tts = getustime();\n\tn = 0;\n\tdo {\n\t\tfor (i = 0; i < 16; i++) {\n\t\t\tulen = size;\n\t\t\tdo_infl(cbuf, clen, ubuf, &ulen);\n\t\t}\n\t\tn += i;\n\t\tte = getustime();\n\t} while (te - ts < 2 * 1000000);\n\n\tfprintf(stdout, \"us time / cycle = %llu\\n\", (te - ts) / n);\n\n\treturn 0;\n}\n"},{"id":"37252","messageId":"Pine.LNX.4.64.0703160913361.3816@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703151955150.4998@alien.or.mcafeemobile.com","subject":"Re: cleaner/better zlib sources?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-16T16:21:29Z","receivedAt":"2007-03-16T16:21:29Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 15 Mar 2007, Davide Libenzi wrote:\n>\n> Hacked up test case below ...\n\nThis one seems to do benchmarking with 8MB buffers if I read it right \n(didn't try).\n\nThe normal size for the performance-critical git objects are in the couple \nof *hundred* bytes. Not kilobytes, and not megabytes.\n\nThe most performance-critical objects for uncompression are commits and \ntrees. At least for the kernel, the average size of a tree object is 678\nbytes. And that's ignoring the fact that most of them are then deltified, \nso about 80% of them are likely just a ~60-byte delta.\n\n\t\tLinus\n"},{"id":"37254","messageId":"Pine.LNX.4.64.0703160920030.13402@alien.or.mcafeemobile.com","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703160913361.3816@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2007-03-16T16:24:38Z","receivedAt":"2007-03-16T16:24:38Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Fri, 16 Mar 2007, Linus Torvalds wrote:\n\n> On Thu, 15 Mar 2007, Davide Libenzi wrote:\n> >\n> > Hacked up test case below ...\n> \n> This one seems to do benchmarking with 8MB buffers if I read it right \n> (didn't try).\n\nYes, I just wanted to have the biggest time spent in inflate(). That why I \nuse a big buffer.\n\n\n> The normal size for the performance-critical git objects are in the couple \n> of *hundred* bytes. Not kilobytes, and not megabytes.\n> \n> The most performance-critical objects for uncompression are commits and \n> trees. At least for the kernel, the average size of a tree object is 678\n> bytes. And that's ignoring the fact that most of them are then deltified, \n> so about 80% of them are likely just a ~60-byte delta.\n\nDefinitely. The nature of the data matters.\nDid you try to make a zlib with my patch and oprofile git on real data \nwith that?\n\n\n\n- Davide\n"},{"id":"37255","messageId":"45FAC75B.3030902@garzik.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703160913361.3816@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Jeff Garzik","fromEmail":"jeff@garzik.org","sentAt":"2007-03-16T16:35:39Z","receivedAt":"2007-03-16T16:35:39Z","isPatch":false,"sender":{"key":"jeff@garzik.org","avatar":null},"body":"Linus Torvalds wrote:\n> The normal size for the performance-critical git objects are in the couple \n> of *hundred* bytes. Not kilobytes, and not megabytes.\n> \n> The most performance-critical objects for uncompression are commits and \n> trees. At least for the kernel, the average size of a tree object is 678\n> bytes. And that's ignoring the fact that most of them are then deltified, \n> so about 80% of them are likely just a ~60-byte delta.\n\n\nAhhh. At least for me, that explains a lot. Rather than spending all \nits time in inflate_fast(), git is dealing with lots of zlib \nstartup/shutdown overhead.\n\nAlthough it sounds like zlib could indeed be optimized to reduce its \nstartup and shutdown overhead, I wonder if switching compression \nalgorithms to a pure Huffman or even RLE compression (with associated \nlower startup/shutdown costs) would perform better in the face of all \nthose small objects.\n\nAnd another random thought, though it may be useless in this thread: I \nbet using a pre-built (compiled into git) static zlib dictionary for git \ncommit and tree objects might improve things a bit.\n\n\tJeff\n"},{"id":"37256","messageId":"Pine.LNX.4.64.0703160934070.3816@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703160920030.13402@alien.or.mcafeemobile.com","subject":"Re: cleaner/better zlib sources?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-16T16:35:51Z","receivedAt":"2007-03-16T16:35:51Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 16 Mar 2007, Davide Libenzi wrote:\n>\n> > This one seems to do benchmarking with 8MB buffers if I read it right \n> > (didn't try).\n> \n> Yes, I just wanted to have the biggest time spent in inflate(). That why I \n> use a big buffer.\n\nRight. But if the biggest time is spent in setup, the big-buffer thing \nends up being exactly the wrong thing to test ;)\n\n> Definitely. The nature of the data matters.\n> Did you try to make a zlib with my patch and oprofile git on real data \n> with that?\n\nI haven't actually set it up so that I can build against my own zlib yet. \nExactly because I was hoping that somebody would already have a solution \n;)\n\nWill try to do later today, although since it's the kids school \nconferences today I'll effectively be in and out all day long.\n\n\t\tLinus\n"},{"id":"37258","messageId":"20070316164241.GC4892@waste.org","threadId":"7262","inReplyTo":"45FAC75B.3030902@garzik.org","subject":"Re: cleaner/better zlib sources?","fromName":"Matt Mackall","fromEmail":"mpm@selenic.com","sentAt":"2007-03-16T16:42:41Z","receivedAt":"2007-03-16T16:42:41Z","isPatch":false,"sender":{"key":"mpm@selenic.com","avatar":null},"body":"On Fri, Mar 16, 2007 at 12:35:39PM -0400, Jeff Garzik wrote:\n> Linus Torvalds wrote:\n> >The normal size for the performance-critical git objects are in the couple \n> >of *hundred* bytes. Not kilobytes, and not megabytes.\n> >\n> >The most performance-critical objects for uncompression are commits and \n> >trees. At least for the kernel, the average size of a tree object is 678\n> >bytes. And that's ignoring the fact that most of them are then deltified, \n> >so about 80% of them are likely just a ~60-byte delta.\n> \n> \n> Ahhh. At least for me, that explains a lot. Rather than spending all \n> its time in inflate_fast(), git is dealing with lots of zlib \n> startup/shutdown overhead.\n> \n> Although it sounds like zlib could indeed be optimized to reduce its \n> startup and shutdown overhead, I wonder if switching compression \n> algorithms to a pure Huffman or even RLE compression (with associated \n> lower startup/shutdown costs) would perform better in the face of all \n> those small objects.\n\nMercurial simply stores uncompressed objects below a threshold of 44\nbytes, based on benchmarks I did in April 2005. I'd probably up that\nnumber if I redid my measurements today. There's just not a whole lot\nzlib can do at these small sizes. Given that a SHA hash is an\nuncompressible 20 bytes already, you're well into the domain of\ndiminishing returns.\n\n> And another random thought, though it may be useless in this thread: I \n> bet using a pre-built (compiled into git) static zlib dictionary for git \n> commit and tree objects might improve things a bit.\n\nIdeally, you'd compress all deltas in a chain with the same context.\nYou've got to decompress the delta base to do the delta\ncalculation, so this should allow you to recover the context up to\nthat point. Zlib isn't really set up for this sort of thing though.\n\n-- \nMathematics is the supreme nostalgia of our time.\n"},{"id":"37257","messageId":"Pine.LNX.4.64.0703160946060.3816@woody.linux-foundation.org","threadId":"7262","inReplyTo":"45FAC75B.3030902@garzik.org","subject":"Re: cleaner/better zlib sources?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-16T16:51:13Z","receivedAt":"2007-03-16T16:51:13Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 16 Mar 2007, Jeff Garzik wrote:\n>\n> Although it sounds like zlib could indeed be optimized to reduce its startup\n> and shutdown overhead, I wonder if switching compression algorithms to a pure\n> Huffman or even RLE compression (with associated lower startup/shutdown costs)\n> would perform better in the face of all those small objects.\n\nWell, the thing is, I personally much prefer to have just a single \ncompression algorithm and object layout. Most of the performance-critical \nobjects from a decompression standpoint during commit traversal are all \nsmall (especially if you do pathname limiting), but when you do something \nlike a \"git add .\" most objects are actually random blob objects and you \nneed to have a compression algorithm that works in the general case too.\n\nOf course, pack-v4 may (likely will) end up using different strategies for \ndifferent objects (delta's in particular), but the \"one single object \ncompression type\" was a big deal for initial implementation.\n\nIt's may not be fundamental to git operation (so we can fairly easily \nchange it and make it more complex without any higher-level stuff even \nnoticing), but it was definitely fundamental to \"get something stable and \nworking\" up and running quickly..\n\n> And another random thought, though it may be useless in this thread: I bet\n> using a pre-built (compiled into git) static zlib dictionary for git commit\n> and tree objects might improve things a bit.\n\nThat's kind of pack-v4 area. It will happen, but I'd actually like to see \nif we can just avoid stupid performance problems with zlib, independently \nof trying to make more tuned formats.\n\n\t\tLinus\n"},{"id":"37260","messageId":"alpine.LFD.0.83.0703161236180.5518@xanadu.home","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703160913361.3816@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-16T17:06:44Z","receivedAt":"2007-03-16T17:06:44Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 16 Mar 2007, Linus Torvalds wrote:\n\n> The most performance-critical objects for uncompression are commits and \n> trees. At least for the kernel, the average size of a tree object is 678\n> bytes. And that's ignoring the fact that most of them are then deltified, \n> so about 80% of them are likely just a ~60-byte delta.\n\nThis is why in pack v4 there will be an alternate tree object \nrepresentation which is not deflated at all.\n\nIn short we intend to have 3 tables where common things are factored \nout:\n\n 1) the path component string table (deflated)\n\n 2) author/committer string table (deflated)\n\n 3) sorted SHA1 table (obviously not deflated)\n\nThe sorted SHA1 table will be part of the pack instead of being in the \npack index. The idea is that most SHA1's are already duplicated in the \npack already anyway within commit and tree objects. With a single table \nthen commit and tree objects can index into that SHA1 table rather than \nproviding the SHA1 value inline for the objects they refer to.\n\nThis means that a tree object record would be only 6 bytes according to \nthe current design: 2 bytes to index into the path component string \ntable (which also include the mode information), and 4 bytes to index \ninto the sorted SHA1 table. And similarly for commit objects.\n\nThis means that the pack index will only have a table of offsets \ncorresponding to the table of sorted SHA1's.\n\nSo... walking revisions will become only a matter of picking the first \ncommit object, using the tree index value (which is not deflated), but \ninstead of using it in the SHA1 table it could be used in the offset \ntable to find the location of the corresponding tree object directly. \nSame goes for tree entries, or for locating the parent's commit object.\n\nNo deflating, no binary searching, no SHA1 comparisons. Plain straight \npointer dereference.\n\nThen, if you want to filter tree walking on path spec, you only need to \nlocate the path component in the path table once and use the \ncorresponding index to filter tree entries instead of repeated strcmp(). \nSame thing if you want to filter commits based on author/committer. \nOne side effect of this is that you can tell straight away that a path \ndoesn't exist in the whole pack if one of its components cannot be found \nin the table (that works only if no legacy tree representations are \npresent of course). That should make history walking blazingly fast.\n\nThe only thing that gets deflated is the commit message which needs to \nbe inflated only when displaying it.\n\nAnd so far that makes for quite smaller packs too!\n\n\nNicolas\n"},{"id":"37261","messageId":"alpine.LFD.0.83.0703161308070.18328@xanadu.home","threadId":"7262","inReplyTo":"45FAC75B.3030902@garzik.org","subject":"Re: cleaner/better zlib sources?","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-16T17:12:46Z","receivedAt":"2007-03-16T17:12:46Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 16 Mar 2007, Jeff Garzik wrote:\n\n> Although it sounds like zlib could indeed be optimized to reduce its startup\n> and shutdown overhead, I wonder if switching compression algorithms to a pure\n> Huffman or even RLE compression (with associated lower startup/shutdown costs)\n> would perform better in the face of all those small objects.\n> \n> And another random thought, though it may be useless in this thread: I bet\n> using a pre-built (compiled into git) static zlib dictionary for git commit\n> and tree objects might improve things a bit.\n\nSee my last post. We'll do even better with special object \nencoding altogether. Those representations are so dense that \ncompression provides no gain at all making the point moot.\n\n\nNicolas\n"},{"id":"37266","messageId":"Pine.LNX.4.64.0703161026220.3816@woody.linux-foundation.org","threadId":"7262","inReplyTo":"alpine.LFD.0.83.0703161236180.5518@xanadu.home","subject":"Re: cleaner/better zlib sources?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-16T17:51:24Z","receivedAt":"2007-03-16T17:51:24Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 16 Mar 2007, Nicolas Pitre wrote:\n\n> On Fri, 16 Mar 2007, Linus Torvalds wrote:\n> \n> > The most performance-critical objects for uncompression are commits and \n> > trees. At least for the kernel, the average size of a tree object is 678\n> > bytes. And that's ignoring the fact that most of them are then deltified, \n> > so about 80% of them are likely just a ~60-byte delta.\n> \n> This is why in pack v4 there will be an alternate tree object \n> representation which is not deflated at all.\n\nWell, the thing is, for things that really don't compress, zlib shouldn't \nadd much of an overhead on uncompression. It *should* just end up being a \nsingle \"memcpy()\" after you've done:\n - check the header for size and mode (\"plain data\")\n - check the adler checksum (which is *really* nice - we've found real \n corruption this way!).\n\nThe adler32 checksumming may sound unnecessary when you already have the \nSHA1 checksum, but the thing is, we normally don't actually *check* the \nSHA1 except when doing a full fsck. So I actually like the fact that \nobject unpacking always checks at least the adler32 checksum at each \nstage, which you get \"for free\" when you use zlib.\n\nSo not using compression at all actually not only gets rid of the \ncompression, it gets rid of a good safety valve - something that may not \nbe immediately obvious when you don't think about what all zlib entails. \n\nPeople think of zlib as just compressing, but I think the checksumming is \nalmost as important, which is why it isn't an obviously good thing to not \ncompress small objects just because you don't win on size!\n\nRemember: stability and safety of the data is *the* #1 objective here. The \ngit SHA1 checksums guarantees that we can find any corruption, but in \nevery-day git usage, the adler32 checksum is the one that generally would \n*notice* the corruption and cause us to say \"uhhuh, need to fsck\".\n\nEverything else is totally secondary to the goal of \"your data is secure\". \nYes, performance is a primary goal too, but it's always \"performance with \ncorrectness guarantees\"!\n\nBut I just traced through a simple 60-byte incompressible zlib thing. It's \npainful. This should be *the* simplest case, and it should really just be \nthe memcpy and the adler32 check. But:\n\n\t[torvalds@woody ~]$ grep ' On Fri, 16 Mar 2007, Nicolas Pitre wrote:\n> \n> > This is why in pack v4 there will be an alternate tree object \n> > representation which is not deflated at all.\n> \n> Well, the thing is, for things that really don't compress, zlib shouldn't \n> add much of an overhead on uncompression. It *should* just end up being a \n> single \"memcpy()\" after you've done:\n> - check the header for size and mode (\"plain data\")\n> - check the adler checksum (which is *really* nice - we've found real \n> corruption this way!).\n\nBut the thing is that with tree objects which records are 6 fairly \nrandom bytes we already know that compression will never be worth it \nsize wise, so it is not worth it even if the header overhead was zero. \nIn that case it is preferable to do without compression entirely.\n\n> The adler32 checksumming may sound unnecessary when you already have the \n> SHA1 checksum, but the thing is, we normally don't actually *check* the \n> SHA1 except when doing a full fsck. So I actually like the fact that \n> object unpacking always checks at least the adler32 checksum at each \n> stage, which you get \"for free\" when you use zlib.\n\nWe still can perform adler32 on undeflated objects directly though. But \nthey need no be stored in the pack. I'd store the adler32 checksum for \neach object in the pack index as it can be recomputed by index-pack \n(which will do the full SHA1 validation anyway).\n\n\nNicolas\n"},{"id":"37275","messageId":"Pine.LNX.4.64.0703161216510.13732@alien.or.mcafeemobile.com","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703160934070.3816@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2007-03-16T19:21:36Z","receivedAt":"2007-03-16T19:21:36Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Fri, 16 Mar 2007, Linus Torvalds wrote:\n\n> \n> \n> On Fri, 16 Mar 2007, Davide Libenzi wrote:\n> >\n> > > This one seems to do benchmarking with 8MB buffers if I read it right \n> > > (didn't try).\n> > \n> > Yes, I just wanted to have the biggest time spent in inflate(). That why I \n> > use a big buffer.\n> \n> Right. But if the biggest time is spent in setup, the big-buffer thing \n> ends up being exactly the wrong thing to test ;)\n\nI modified ztest.c to be able to bench on various data files (you list \nthem on the command line), but result are pretty much same.\nI cannot measure any sensible difference between the two.\nAttached there's ztest.c and the diff, in case you want to try on your \nown.\n\n\n\n> > Definitely. The nature of the data matters.\n> > Did you try to make a zlib with my patch and oprofile git on real data \n> > with that?\n> \n> I haven't actually set it up so that I can build against my own zlib yet. \n> Exactly because I was hoping that somebody would already have a solution \n> ;)\n\nAn LD_PRELOAD pointing to your own build should do it.\n\n\n\n\n- Davide\n\n\n\n\n#include \n#include \n#include \n#include \n#include \n#include \n#include \n#include \n#include \n#include \"zlib.h\"\n\n\n#define MIN_TESTIME (2 * 1000000)\n#define INNER_CYCLES 32\n\n\n\n#define CHECK_ERR(err, msg) do { \\\n\tif (err != Z_OK) { \\\n\t\tfprintf(stderr, \"%s error: %d\\n\", msg, err); \\\n\t\texit(1); \\\n\t} \\\n} while (0)\n\n\n\nstatic unsigned long long mintt = MIN_TESTIME;\nstatic uLong incycles = INNER_CYCLES;\n\n\n\nstatic unsigned long long getustime(void) {\n\tstruct timeval tm;\n\n\tgettimeofday(&tm, NULL);\n\treturn tm.tv_sec * 1000000ULL + tm.tv_usec;\n}\n\nstatic void do_defl(Byte *cdata, uLong *clen,\n\t\t Byte *udata, uLong uclen) {\n\tz_stream c_stream; /* compression stream */\n\tint err;\n\n\tc_stream.zalloc = (alloc_func) NULL;\n\tc_stream.zfree = (free_func) NULL;\n\tc_stream.opaque = (voidpf) NULL;\n\n\terr = deflateInit(&c_stream, Z_BEST_SPEED);\n\tCHECK_ERR(err, \"deflateInit\");\n\n\tc_stream.next_out = cdata;\n\tc_stream.avail_out = (uInt) *clen;\n\n\t/* At this point, udata is still mostly zeroes, so it should compress\n\t * very well:\n\t */\n\tc_stream.next_in = udata;\n\tc_stream.avail_in = (uInt) uclen;\n\terr = deflate(&c_stream, Z_FINISH);\n\tif (err != Z_STREAM_END) {\n\t\tfprintf(stderr, \"whoops, got %d instead of Z_STREAM_END\\n\", err);\n\t\texit(1);\n\t}\n\n\terr = deflateEnd(&c_stream);\n\tCHECK_ERR(err, \"deflateEnd\");\n\n\t*clen = c_stream.next_out - cdata;\n}\n\nstatic void do_infl(Byte *cdata, uLong clen,\n\t\t Byte *udata, uLong *uclen) {\n\tint err;\n\tz_stream d_stream; /* decompression stream */\n\n\td_stream.zalloc = (alloc_func) NULL;\n\td_stream.zfree = (free_func) NULL;\n\td_stream.opaque = (voidpf) NULL;\n\n\td_stream.next_in = cdata;\n\td_stream.avail_in = (uInt) clen;\n\n\terr = inflateInit(&d_stream);\n\tCHECK_ERR(err, \"inflateInit\");\n\n\td_stream.next_out = udata; /* discard the output */\n\td_stream.avail_out = (uInt) *uclen;\n\terr = inflate(&d_stream, Z_FULL_FLUSH);\n\tif (err != Z_STREAM_END) {\n\t\tfprintf(stderr, \"deflate should report Z_STREAM_END\\n\");\n\t\texit(1);\n\t}\n\n\terr = inflateEnd(&d_stream);\n\tCHECK_ERR(err, \"inflateEnd\");\n\n\t*uclen = d_stream.next_out - udata;\n}\n\nstatic int do_filebench(char const *fpath) {\n\tint fd, err = -1;\n\tuLong i, n, clen, ulen, size;\n\tByte *ubuf, *cbuf, *tbuf;\n\tunsigned long long ts, te;\n\tvoid *addr;\n\tstruct stat stb;\n\n\tif ((fd = open(fpath, O_RDONLY)) == -1 ||\n\t fstat(fd, &stb)) {\n\t\tperror(fpath);\n\t\tclose(fd);\n\t\treturn -1;\n\t}\n\tsize = stb.st_size;\n\taddr = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n\tclose(fd);\n\tif (addr == (void *) -1L) {\n\t\tperror(\"mmap\");\n\t\treturn -1;\n\t}\n\tulen = size;\n\tclen = size + 4096;\n\tubuf = addr;\n\tif ((tbuf = malloc(ulen + clen)) == NULL) {\n\t\tperror(\"malloc\");\n\t\tgoto err_exit;\n\t}\n\tcbuf = tbuf + ulen;\n\n\t/* Warming up ... */\n\tdo_defl(cbuf, &clen, ubuf, ulen);\n\tdo_infl(cbuf, clen, tbuf, &ulen);\n\tif (ulen != size) {\n\t\tfprintf(stderr, \"size mismatch %lu instead of %lu\\n\",\n\t\t\t(unsigned long) ulen, (unsigned long) size);\n\t\tgoto err_exit;\n\t}\n\tif (memcmp(tbuf, ubuf, size)) {\n\t\tfprintf(stderr, \"whoops! we did not get back the same data\\n\");\n\t\tgoto err_exit;\n\t}\n\n\t/* Test ... */\n\tfprintf(stdout, \"testing: %s\\n\", fpath);\n\tts = getustime();\n\tn = 0;\n\tdo {\n\t\tfor (i = 0; i < incycles; i++) {\n\t\t\tulen = size;\n\t\t\tdo_infl(cbuf, clen, tbuf, &ulen);\n\t\t}\n\t\tn += i;\n\t\tte = getustime();\n\t} while (te - ts < mintt);\n\n\tfprintf(stdout, \"\\tus time / cycle = %llu\\n\", (te - ts) / n);\n\terr = 0;\n\nerr_exit:\n\tfree(tbuf);\n\tmunmap(addr, size);\n\n\treturn err;\n}\n\nint main(int ac, char **av) {\n\tint i;\n\n\tfor (i = 1; i < ac; i++)\n\t\tdo_filebench(av[i]);\n\n\treturn 0;\n}\n\n\n\nIndex: zlib-1.2.3.quilt/inflate.c\n===================================================================\n--- zlib-1.2.3.quilt.orig/inflate.c\t2007-03-15 18:17:19.000000000 -0700\n+++ zlib-1.2.3.quilt/inflate.c\t2007-03-15 18:31:14.000000000 -0700\n@@ -551,6 +551,15 @@\n will return Z_BUF_ERROR if it has not reached the end of the stream.\n */\n \n+#define CASE_DECL(n) \\\n+\tcase n: \\\n+\tlbl_##n:\n+\n+#define STATE_CHANGE(s) do { \\\n+\tstate->mode = s; \\\n+\tgoto lbl_##s; \\\n+} while (0)\n+\n int ZEXPORT inflate(strm, flush)\n z_streamp strm;\n int flush;\n@@ -586,10 +595,9 @@\n ret = Z_OK;\n for (;;)\n switch (state->mode) {\n- case HEAD:\n+ CASE_DECL(HEAD)\n if (state->wrap == 0) {\n- state->mode = TYPEDO;\n- break;\n+\t\tSTATE_CHANGE(TYPEDO);\n }\n NEEDBITS(16);\n #ifdef GUNZIP\n@@ -597,8 +605,7 @@\n state->check = crc32(0L, Z_NULL, 0);\n CRC2(state->check, hold);\n INITBITS();\n- state->mode = FLAGS;\n- break;\n+\t\tSTATE_CHANGE(FLAGS);\n }\n state->flags = 0; /* expect zlib header */\n if (state->head != Z_NULL)\n@@ -609,20 +616,17 @@\n #endif\n ((BITS(8) << 8) + (hold >> 8)) % 31) {\n strm->msg = (char *)\"incorrect header check\";\n- state->mode = BAD;\n- break;\n+\t STATE_CHANGE(BAD);\n }\n if (BITS(4) != Z_DEFLATED) {\n strm->msg = (char *)\"unknown compression method\";\n- state->mode = BAD;\n- break;\n+\t STATE_CHANGE(BAD);\n }\n DROPBITS(4);\n len = BITS(4) + 8;\n if (len > state->wbits) {\n strm->msg = (char *)\"invalid window size\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n state->dmax = 1U << len;\n Tracev((stderr, \"inflate: zlib header ok\\n\"));\n@@ -631,32 +635,30 @@\n INITBITS();\n break;\n #ifdef GUNZIP\n- case FLAGS:\n+ CASE_DECL(FLAGS)\n NEEDBITS(16);\n state->flags = (int)(hold);\n if ((state->flags & 0xff) != Z_DEFLATED) {\n strm->msg = (char *)\"unknown compression method\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n if (state->flags & 0xe000) {\n strm->msg = (char *)\"unknown header flags set\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n if (state->head != Z_NULL)\n state->head->text = (int)((hold >> 8) & 1);\n if (state->flags & 0x0200) CRC2(state->check, hold);\n INITBITS();\n state->mode = TIME;\n- case TIME:\n+ CASE_DECL(TIME)\n NEEDBITS(32);\n if (state->head != Z_NULL)\n state->head->time = hold;\n if (state->flags & 0x0200) CRC4(state->check, hold);\n INITBITS();\n state->mode = OS;\n- case OS:\n+ CASE_DECL(OS)\n NEEDBITS(16);\n if (state->head != Z_NULL) {\n state->head->xflags = (int)(hold & 0xff);\n@@ -665,7 +667,7 @@\n if (state->flags & 0x0200) CRC2(state->check, hold);\n INITBITS();\n state->mode = EXLEN;\n- case EXLEN:\n+ CASE_DECL(EXLEN)\n if (state->flags & 0x0400) {\n NEEDBITS(16);\n state->length = (unsigned)(hold);\n@@ -677,7 +679,7 @@\n else if (state->head != Z_NULL)\n state->head->extra = Z_NULL;\n state->mode = EXTRA;\n- case EXTRA:\n+ CASE_DECL(EXTRA)\n if (state->flags & 0x0400) {\n copy = state->length;\n if (copy > have) copy = have;\n@@ -699,7 +701,7 @@\n }\n state->length = 0;\n state->mode = NAME;\n- case NAME:\n+ CASE_DECL(NAME)\n if (state->flags & 0x0800) {\n if (have == 0) goto inf_leave;\n copy = 0;\n@@ -720,7 +722,7 @@\n state->head->name = Z_NULL;\n state->length = 0;\n state->mode = COMMENT;\n- case COMMENT:\n+ CASE_DECL(COMMENT)\n if (state->flags & 0x1000) {\n if (have == 0) goto inf_leave;\n copy = 0;\n@@ -740,13 +742,12 @@\n else if (state->head != Z_NULL)\n state->head->comment = Z_NULL;\n state->mode = HCRC;\n- case HCRC:\n+ CASE_DECL(HCRC)\n if (state->flags & 0x0200) {\n NEEDBITS(16);\n if (hold != (state->check & 0xffff)) {\n strm->msg = (char *)\"header crc mismatch\";\n- state->mode = BAD;\n- break;\n+\t\t STATE_CHANGE(BAD);\n }\n INITBITS();\n }\n@@ -755,28 +756,26 @@\n state->head->done = 1;\n }\n strm->adler = state->check = crc32(0L, Z_NULL, 0);\n- state->mode = TYPE;\n- break;\n+\t STATE_CHANGE(TYPE);\n #endif\n- case DICTID:\n+ CASE_DECL(DICTID)\n NEEDBITS(32);\n strm->adler = state->check = REVERSE(hold);\n INITBITS();\n state->mode = DICT;\n- case DICT:\n+ CASE_DECL(DICT)\n if (state->havedict == 0) {\n RESTORE();\n return Z_NEED_DICT;\n }\n strm->adler = state->check = adler32(0L, Z_NULL, 0);\n state->mode = TYPE;\n- case TYPE:\n+ CASE_DECL(TYPE)\n if (flush == Z_BLOCK) goto inf_leave;\n- case TYPEDO:\n+ CASE_DECL(TYPEDO)\n if (state->last) {\n BYTEBITS();\n- state->mode = CHECK;\n- break;\n+\t\tSTATE_CHANGE(CHECK);\n }\n NEEDBITS(3);\n state->last = BITS(1);\n@@ -785,39 +784,38 @@\n case 0: /* stored block */\n Tracev((stderr, \"inflate: stored block%s\\n\",\n state->last ? \" (last)\" : \"\"));\n- state->mode = STORED;\n- break;\n+\t\tDROPBITS(2);\n+\t\tSTATE_CHANGE(STORED);\n case 1: /* fixed block */\n fixedtables(state);\n Tracev((stderr, \"inflate: fixed codes block%s\\n\",\n state->last ? \" (last)\" : \"\"));\n- state->mode = LEN; /* decode codes */\n- break;\n+\t\tDROPBITS(2);\n+\t\tSTATE_CHANGE(LEN);\n case 2: /* dynamic block */\n Tracev((stderr, \"inflate: dynamic codes block%s\\n\",\n state->last ? \" (last)\" : \"\"));\n- state->mode = TABLE;\n- break;\n+\t\tDROPBITS(2);\n+\t\tSTATE_CHANGE(TABLE);\n case 3:\n+\t\tDROPBITS(2);\n strm->msg = (char *)\"invalid block type\";\n- state->mode = BAD;\n+\t\tSTATE_CHANGE(BAD);\n }\n- DROPBITS(2);\n break;\n- case STORED:\n+ CASE_DECL(STORED)\n BYTEBITS(); /* go to byte boundary */\n NEEDBITS(32);\n if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {\n strm->msg = (char *)\"invalid stored block lengths\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n state->length = (unsigned)hold & 0xffff;\n Tracev((stderr, \"inflate: stored length %u\\n\",\n state->length));\n INITBITS();\n state->mode = COPY;\n- case COPY:\n+ CASE_DECL(COPY)\n copy = state->length;\n if (copy) {\n if (copy > have) copy = have;\n@@ -832,9 +830,8 @@\n break;\n }\n Tracev((stderr, \"inflate: stored end\\n\"));\n- state->mode = TYPE;\n- break;\n- case TABLE:\n+\t STATE_CHANGE(TYPE);\n+ CASE_DECL(TABLE)\n NEEDBITS(14);\n state->nlen = BITS(5) + 257;\n DROPBITS(5);\n@@ -845,14 +842,13 @@\n #ifndef PKZIP_BUG_WORKAROUND\n if (state->nlen > 286 || state->ndist > 30) {\n strm->msg = (char *)\"too many length or distance symbols\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n #endif\n Tracev((stderr, \"inflate: table sizes ok\\n\"));\n state->have = 0;\n state->mode = LENLENS;\n- case LENLENS:\n+ CASE_DECL(LENLENS)\n while (state->have < state->ncode) {\n NEEDBITS(3);\n state->lens[order[state->have++]] = (unsigned short)BITS(3);\n@@ -867,13 +863,12 @@\n &(state->lenbits), state->work);\n if (ret) {\n strm->msg = (char *)\"invalid code lengths set\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n Tracev((stderr, \"inflate: code lengths ok\\n\"));\n state->have = 0;\n state->mode = CODELENS;\n- case CODELENS:\n+ CASE_DECL(CODELENS)\n while (state->have < state->nlen + state->ndist) {\n for (;;) {\n this = state->lencode[BITS(state->lenbits)];\n@@ -891,8 +886,7 @@\n DROPBITS(this.bits);\n if (state->have == 0) {\n strm->msg = (char *)\"invalid bit length repeat\";\n- state->mode = BAD;\n- break;\n+\t\t\t STATE_CHANGE(BAD);\n }\n len = state->lens[state->have - 1];\n copy = 3 + BITS(2);\n@@ -914,17 +908,13 @@\n }\n if (state->have + copy > state->nlen + state->ndist) {\n strm->msg = (char *)\"invalid bit length repeat\";\n- state->mode = BAD;\n- break;\n+\t\t\tSTATE_CHANGE(BAD);\n }\n while (copy--)\n state->lens[state->have++] = (unsigned short)len;\n }\n }\n \n- /* handle error breaks in while */\n- if (state->mode == BAD) break;\n-\n /* build code tables */\n state->next = state->codes;\n state->lencode = (code const FAR *)(state->next);\n@@ -933,8 +923,7 @@\n &(state->lenbits), state->work);\n if (ret) {\n strm->msg = (char *)\"invalid literal/lengths set\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n state->distcode = (code const FAR *)(state->next);\n state->distbits = 6;\n@@ -942,12 +931,11 @@\n &(state->next), &(state->distbits), state->work);\n if (ret) {\n strm->msg = (char *)\"invalid distances set\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n Tracev((stderr, \"inflate: codes ok\\n\"));\n state->mode = LEN;\n- case LEN:\n+ CASE_DECL(LEN)\n if (have >= 6 && left >= 258) {\n RESTORE();\n inflate_fast(strm, out);\n@@ -975,22 +963,19 @@\n Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?\n \"inflate: literal '%c'\\n\" :\n \"inflate: literal 0x%02x\\n\", this.val));\n- state->mode = LIT;\n- break;\n+\t\tSTATE_CHANGE(LIT);\n }\n if (this.op & 32) {\n Tracevv((stderr, \"inflate: end of block\\n\"));\n- state->mode = TYPE;\n- break;\n+\t\tSTATE_CHANGE(TYPE);\n }\n if (this.op & 64) {\n strm->msg = (char *)\"invalid literal/length code\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n state->extra = (unsigned)(this.op) & 15;\n state->mode = LENEXT;\n- case LENEXT:\n+ CASE_DECL(LENEXT)\n if (state->extra) {\n NEEDBITS(state->extra);\n state->length += BITS(state->extra);\n@@ -998,7 +983,7 @@\n }\n Tracevv((stderr, \"inflate: length %u\\n\", state->length));\n state->mode = DIST;\n- case DIST:\n+ CASE_DECL(DIST)\n for (;;) {\n this = state->distcode[BITS(state->distbits)];\n if ((unsigned)(this.bits) <= bits) break;\n@@ -1017,13 +1002,12 @@\n DROPBITS(this.bits);\n if (this.op & 64) {\n strm->msg = (char *)\"invalid distance code\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n state->offset = (unsigned)this.val;\n state->extra = (unsigned)(this.op) & 15;\n state->mode = DISTEXT;\n- case DISTEXT:\n+ CASE_DECL(DISTEXT)\n if (state->extra) {\n NEEDBITS(state->extra);\n state->offset += BITS(state->extra);\n@@ -1032,18 +1016,16 @@\n #ifdef INFLATE_STRICT\n if (state->offset > state->dmax) {\n strm->msg = (char *)\"invalid distance too far back\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n #endif\n if (state->offset > state->whave + out - left) {\n strm->msg = (char *)\"invalid distance too far back\";\n- state->mode = BAD;\n- break;\n+\t\tSTATE_CHANGE(BAD);\n }\n Tracevv((stderr, \"inflate: distance %u\\n\", state->offset));\n state->mode = MATCH;\n- case MATCH:\n+ CASE_DECL(MATCH)\n if (left == 0) goto inf_leave;\n copy = out - left;\n if (state->offset > copy) { /* copy from window */\n@@ -1066,15 +1048,15 @@\n do {\n *put++ = *from++;\n } while (--copy);\n- if (state->length == 0) state->mode = LEN;\n+ if (state->length == 0)\n+\t\tSTATE_CHANGE(LEN);\n break;\n- case LIT:\n+ CASE_DECL(LIT)\n if (left == 0) goto inf_leave;\n *put++ = (unsigned char)(state->length);\n left--;\n- state->mode = LEN;\n- break;\n- case CHECK:\n+\t STATE_CHANGE(LEN);\n+ CASE_DECL(CHECK)\n if (state->wrap) {\n NEEDBITS(32);\n out -= left;\n@@ -1090,36 +1072,34 @@\n #endif\n REVERSE(hold)) != state->check) {\n strm->msg = (char *)\"incorrect data check\";\n- state->mode = BAD;\n- break;\n+\t\t STATE_CHANGE(BAD);\n }\n INITBITS();\n Tracev((stderr, \"inflate: check matches trailer\\n\"));\n }\n #ifdef GUNZIP\n state->mode = LENGTH;\n- case LENGTH:\n+ CASE_DECL(LENGTH)\n if (state->wrap && state->flags) {\n NEEDBITS(32);\n if (hold != (state->total & 0xffffffffUL)) {\n strm->msg = (char *)\"incorrect length check\";\n- state->mode = BAD;\n- break;\n+\t\t STATE_CHANGE(BAD);\n }\n INITBITS();\n Tracev((stderr, \"inflate: length matches trailer\\n\"));\n }\n #endif\n state->mode = DONE;\n- case DONE:\n+ CASE_DECL(DONE)\n ret = Z_STREAM_END;\n goto inf_leave;\n- case BAD:\n+ CASE_DECL(BAD)\n ret = Z_DATA_ERROR;\n goto inf_leave;\n- case MEM:\n+ CASE_DECL(MEM)\n return Z_MEM_ERROR;\n- case SYNC:\n+ CASE_DECL(SYNC)\n default:\n return Z_STREAM_ERROR;\n }\n"},{"id":"37286","messageId":"20070316232244.GC4508@spearce.org","threadId":"7262","inReplyTo":"45FAC75B.3030902@garzik.org","subject":"Re: cleaner/better zlib sources?","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-16T23:22:44Z","receivedAt":"2007-03-16T23:22:44Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jeff Garzik wrote:\n> Although it sounds like zlib could indeed be optimized to reduce its \n> startup and shutdown overhead, I wonder if switching compression \n> algorithms to a pure Huffman or even RLE compression (with associated \n> lower startup/shutdown costs) would perform better in the face of all \n> those small objects.\n\nAs Nico already stated, for pack v4 we are probably heading in a\ndirection where these really small (except for blobs anyway) objects\naren't compressed at all by zlib. They are smaller in disk space,\nand are faster to reconstruct to their raw format.\n \n> And another random thought, though it may be useless in this thread: I \n> bet using a pre-built (compiled into git) static zlib dictionary for git \n> commit and tree objects might improve things a bit.\n\nI've actually tried this with the Mozilla project. The improvement\nwas under 2% on disk space usage and no runtime performance gains.\nNot worth the pain involved. We are seeing much higher disk\nspace improvements and much better performance gains in the pack\nv4 prototype.\n\nOh, and that was *with* a dictionary that was customized to Mozilla.\nNot a static one. A lot of keywords in the dictionary were Mozilla\nproject specific, and would actually *hurt* compression for the\nLinux kernel, Git, X.org, etc...\n\n-- \nShawn.\n"},{"id":"37291","messageId":"Pine.LNX.4.64.0703161636520.3910@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703161216510.13732@alien.or.mcafeemobile.com","subject":"Re: cleaner/better zlib sources?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-17T00:01:14Z","receivedAt":"2007-03-17T00:01:14Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 16 Mar 2007, Davide Libenzi wrote:\n>\n> I cannot measure any sensible difference between the two.\n\nI'm using your previous patch (is it the same?) along with the additional \npatch appended.\n\nAnd yes, it's not hugely faster, but I seem to see *some* difference: this \nis the real-time of ten runs of \n\n\ttime git log drivers/usb/ > /dev/null\n\nBefore:\n\n\t0m2.673s\n\t0m2.476s\n\t0m2.603s\n\t0m2.576s\n\t0m2.625s\n\t0m2.628s\n\t0m2.493s\n\t0m2.696s\n\t0m2.525s\n\t0m2.575s\n\nAfter:\n\n\t0m2.639s\n\t0m2.519s\n\t0m2.454s\n\t0m2.604s\n\t0m2.499s\n\t0m2.497s\n\t0m2.506s\n\t0m2.394s\n\t0m2.409s\n\t0m2.562s\n\nie after I actually get under 2.4s once, and under 2.5s most of the time, \nwhile before it was under 2.5s just twice, and mostly in the 2.6s..\n\n(I did end up adding the \"-g\", but I trust that doesn't make things \n*faster*. Generally gcc is good at not actually changing code generation \nbased on -g)\n\nBut yeah, not very impressive changes. We're talking *maybe* 0.1s out of \n2.5, so potentially about 4% of total time but more likely about 2-3%, and \nit's clearly mostly in the noise. And inflate() is still at 16%, and \ninflate_fast obviously got no faster.\n\nThe nice part is that the instruction-level profile for inflate() got more \ninteresting. Instead of clearly peaking at the silly indirect jump, the \npeak now seems to be a specific path through the thing. I've not decoded \nit fully yet, but it seems to be mostly the LEN/LIT cases:\n\n file inflate.c, line 942.\n file inflate.c, line 942.\n file inflate.c, line 949.\n file inflate.c, line 949.\n file inflate.c, line 949.\n file inflate.c, line 949.\n file inflate.c, line 949.\n file inflate.c, line 950.\n file inflate.c, line 950.\n file inflate.c, line 951.\n file inflate.c, line 951.\n file inflate.c, line 951.\n file inflate.c, line 951.\n file inflate.c, line 951.\n file inflate.c, line 949.\n file inflate.c, line 949.\n file inflate.c, line 950.\n file inflate.c, line 950.\n file inflate.c, line 953.\n file inflate.c, line 953.\n file inflate.c, line 953.\n file inflate.c, line 969.\n file inflate.c, line 1058.\n file inflate.c, line 1059.\n file inflate.c, line 1061.\n file inflate.c, line 884.\n file inflate.c, line 963.\n file inflate.c, line 964.\n\n(those are the line numbers *after* applying my patch for where the \nhotpoints are: the same line-number showing up multiple times is just \nbecause several hot instructions came from there and got spread out)\n\n\t\t\tLinus\n\n---\ndiff --git a/Makefile b/Makefile\nindex 2fd6e45..d8e9ff4 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -18,7 +18,7 @@\n \n CC=cc\n \n-CFLAGS=-O\n+CFLAGS=-O -g\n #CFLAGS=-O -DMAX_WBITS=14 -DMAX_MEM_LEVEL=7\n #CFLAGS=-g -DDEBUG\n #CFLAGS=-O3 -Wall -Wwrite-strings -Wpointer-arith -Wconversion \\\ndiff --git a/inflate.c b/inflate.c\nindex 190c642..3d41d6f 100644\n--- a/inflate.c\n+++ b/inflate.c\n@@ -568,7 +568,7 @@ int flush;\n unsigned char FAR *next; /* next input */\n unsigned char FAR *put; /* next output */\n unsigned have, left; /* available input and output */\n- unsigned long hold; /* bit buffer */\n+ unsigned long hold, old_hold;/* bit buffer */\n unsigned bits; /* bits in bit buffer */\n unsigned in, out; /* save starting available input and output */\n unsigned copy; /* number of stored or match bytes to copy */\n@@ -631,8 +631,11 @@ int flush;\n state->dmax = 1U << len;\n Tracev((stderr, \"inflate: zlib header ok\\n\"));\n strm->adler = state->check = adler32(0L, Z_NULL, 0);\n- state->mode = hold & 0x200 ? DICTID : TYPE;\n+ old_hold = hold;\n INITBITS();\n+ if (old_hold & 0x200)\n+ \tSTATE_CHANGE(DICTID);\n+ STATE_CHANGE(TYPE);\n break;\n #ifdef GUNZIP\n CASE_DECL(FLAGS)\n@@ -817,7 +820,7 @@ int flush;\n state->mode = COPY;\n CASE_DECL(COPY)\n copy = state->length;\n- if (copy) {\n+ while (copy) {\n if (copy > have) copy = have;\n if (copy > left) copy = left;\n if (copy == 0) goto inf_leave;\n@@ -826,8 +829,8 @@ int flush;\n next += copy;\n left -= copy;\n put += copy;\n- state->length -= copy;\n- break;\n+ copy = state->length - copy;\n+ state->length = copy;\n }\n Tracev((stderr, \"inflate: stored end\\n\"));\n \t STATE_CHANGE(TYPE);\n"},{"id":"37293","messageId":"Pine.LNX.4.64.0703161722360.3910@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703161636520.3910@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-17T01:11:50Z","receivedAt":"2007-03-17T01:11:50Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 16 Mar 2007, Linus Torvalds wrote:\n> \n> And yes, it's not hugely faster, but I seem to see *some* difference: this \n> is the real-time of ten runs of \n> \n> \ttime git log drivers/usb/ > /dev/null\n\nDamn. I think I know why it's happening, and I'm an idiot. I think it's \nactually an issue I wondered about a *loong* time ago, and then forgot all \nabout. And later or Nico made it almost impossible to fix with his \"pack \noffset\" changes.\n\nThe thing that made me realize was one of the callchains into inflate() \nthat I looked at:\n\n (gdb) where\n #0 inflate (strm=0x7fff10d83810, flush=4) at inflate.c:566\n #1 0x000000000044c165 in unpack_compressed_entry (p=0x6d52e0, w_curs=0x7fff10d838e0, curpos=94941911,\n size=) at sha1_file.c:1348\n #2 0x000000000044c2b6 in unpack_entry (p=0x6d52e0, obj_offset=94941909, type=0x7fff10d85d8c, sizep=0x7fff10d83928)\n at sha1_file.c:1408\n #3 0x000000000044c32e in unpack_entry (p=0x6d52e0, obj_offset=94942707, type=0x7fff10d85d8c, sizep=0x7fff10d83988)\n at sha1_file.c:1373\n #4 0x000000000044c32e in unpack_entry (p=0x6d52e0, obj_offset=94943021, type=0x7fff10d85d8c, sizep=0x7fff10d839e8)\n at sha1_file.c:1373\n #5 0x000000000044c32e in unpack_entry (p=0x6d52e0, obj_offset=94943382, type=0x7fff10d85d8c, sizep=0x7fff10d83a48)\n at sha1_file.c:1373\n #6 0x000000000044c32e in unpack_entry (p=0x6d52e0, obj_offset=94943531, type=0x7fff10d85d8c, sizep=0x7fff10d83aa8)\n at sha1_file.c:1373\n #7 0x000000000044c32e in unpack_entry (p=0x6d52e0, obj_offset=94943622, type=0x7fff10d85d8c, sizep=0x7fff10d83b08)\n at sha1_file.c:1373\n #8 0x000000000044c32e in unpack_entry (p=0x6d52e0, obj_offset=94945357, type=0x7fff10d85d8c, sizep=0x7fff10d83b68)\n at sha1_file.c:1373\n #9 0x000000000044c32e in unpack_entry (p=0x6d52e0, obj_offset=94945447, type=0x7fff10d85d8c, sizep=0x7fff10d83bc8)\n at sha1_file.c:1373\n #10 0x000000000044c32e in unpack_entry (p=0x6d52e0, obj_offset=94945571, type=0x7fff10d85d8c, sizep=0x7fff10d85d80)\n at sha1_file.c:1373\n #11 0x000000000044c3f8 in read_packed_sha1 (sha1=, type=0x7fff10d85d8c, size=0x7fff10d85d80)\n at sha1_file.c:1567\n #12 0x000000000044c741 in read_sha1_file (sha1=0x7fff10d85d60 \"�Ab\\217��236���031\", type=0x7fff10d85d8c,\n size=0x7fff10d85d80) at sha1_file.c:1636\n ....\n\nand notice the deep recursion in sha1_file.\n\nThe way we unpack delta chains is that we do\n\n - find a delta\n - we apply it to \"recursively unpack the thing it's a delta to\"\n\nwhich sounds totally obvious and straightforward, right?\n\nEXCEPT it's actually O(n**2) in the delta depth, because we never save the \nintermediate results, so when we have a delta depth of 10 (our default), \nand we decode a lot of these things, we basically will look up the base \nobject 10 times, apply the first delta 9 times, apply the second delta 8 \ntimes, etc etc.. \n\nI didn't worry about it, because it never actually hit as much of a\nperformance problem (and when you do a *single* tree operation you'd\nnever see it anyway: you apply the deltas you need, and nothing else),\nbut what it means is that we actually call inflate on the chain entries\n55 times instead of just doing it 10 times. \n\nIt's also somewhat limited by the delta depth that we enforce anyway (I \nsay \"somewhat\", because we only limit the maximum depth, not the number of \ntimes an object can be used as a base, and if you use an object as a base \na thousand times, it will literally be unpacked a thousand times too!\n\nI also didn't worry about it, because I felt that if it became a problem, \nit would be easy to just add a cache of base objects (we probably do *not* \nwant to keep the whole unpacked object info in memory all the time just \nbecause of memory pressure issues, so \"cache of base objects\" is better). \nHowever, the \"pack file + offset\" thing makes it harder to do, since we \nnow don't even have the SHA1 of the base object before we unpack it.\n\nBut I guess we could just index this by a tuple.\n\nAnyway, I bet that this is a much bigger issue than the pack format \nitself (and is largely independent).\n\n\t\tLinus"},{"id":"37298","messageId":"alpine.LFD.0.83.0703162257560.18328@xanadu.home","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703161722360.3910@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-17T03:28:33Z","receivedAt":"2007-03-17T03:28:33Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 16 Mar 2007, Linus Torvalds wrote:\n\n> The way we unpack delta chains is that we do\n> \n> - find a delta\n> - we apply it to \"recursively unpack the thing it's a delta to\"\n> \n> which sounds totally obvious and straightforward, right?\n> \n> EXCEPT it's actually O(n**2) in the delta depth, because we never save the \n> intermediate results, so when we have a delta depth of 10 (our default), \n> and we decode a lot of these things, we basically will look up the base \n> object 10 times, apply the first delta 9 times, apply the second delta 8 \n> times, etc etc.. \n\nIn the worst case, yes. And if you're walking history then the \nprobability of hitting the worst case eventually is rather high.\n\n> I also didn't worry about it, because I felt that if it became a problem, \n> it would be easy to just add a cache of base objects (we probably do *not* \n> want to keep the whole unpacked object info in memory all the time just \n> because of memory pressure issues, so \"cache of base objects\" is better). \n> However, the \"pack file + offset\" thing makes it harder to do, since we \n> now don't even have the SHA1 of the base object before we unpack it.\n> \n> But I guess we could just index this by a tuple.\n\nRight. Should be really trivial to hook into unpack_delta_entry() \nactually replacing the call to unpack_entry() with a wrapper function \nthat returns cached data, or populates the cache with unpack_entry() \nwhen no match is found.\n\nThen it would only be a matter of coming up with a clever cache \neviction algorithm.\n\n> Anyway, I bet that this is a much bigger issue than the pack format \n> itself (and is largely independent).\n\nWell, I think the pack format issue is significant too. But because \nthose are independent issues the gain in performance will be additive.\n\n\nNicolas\n"},{"id":"37302","messageId":"20070317051921.GA5731@spearce.org","threadId":"7262","inReplyTo":"alpine.LFD.0.83.0703162257560.18328@xanadu.home","subject":"Re: cleaner/better zlib sources?","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-17T05:19:21Z","receivedAt":"2007-03-17T05:19:21Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Fri, 16 Mar 2007, Linus Torvalds wrote:\n> > I also didn't worry about it, because I felt that if it became a problem, \n> > it would be easy to just add a cache of base objects (we probably do *not* \n> > want to keep the whole unpacked object info in memory all the time just \n> > because of memory pressure issues, so \"cache of base objects\" is better). \n> > However, the \"pack file + offset\" thing makes it harder to do, since we \n> > now don't even have the SHA1 of the base object before we unpack it.\n> > \n> > But I guess we could just index this by a tuple.\n...\n> Then it would only be a matter of coming up with a clever cache \n> eviction algorithm.\n\nYes. Linus above seems to imply (at least to me) that we wouldn't\nwant to cache the original object requested by read_sha1_file(), as\nits not the delta base. But given our packing rules, we should be\n(in general anyway) first asking for the most recent revision of\na file, which is stored whole, then for an older revision, which\nwill be a delta of the more recent revision we just saw.\n\nHence we probably would want to cache an object. Well, at least\nanything that had been packed as a delta. Caching a deflated\nOBJ_BLOB may not be worth it.\n \n> > Anyway, I bet that this is a much bigger issue than the pack format \n> > itself (and is largely independent).\n> \n> Well, I think the pack format issue is significant too. But because \n> those are independent issues the gain in performance will be additive.\n\nI'm torn there.\n\nThere's two places that we do lots of unpacks of objects where we\nrun into this difficult case of unpacking the same base object many\ntimes: git-blame and a rev-list with a path limiter.\n\nNow the git-blame case is obvious: we are constantly unpacking\nvarious revisions of the same file, and these are probably delta'd\nagainst each other, so the unpacking gets really brutal after a\nwhile. A blob cache here would probably *really* help out git-blame.\n\nWhat's slightly less obvious about git-blame is we are probably also\ntraversing the different versions of the same trees over and over, as\nwe resolve the path to the correct blob in each commit we traverse.\nSo again here we are hitting lots of the same trees multiple times.\n\nThat last part about git-blame also obviously applies to the rev-list\nwith a path limiter.\n\nBut most other operations don't seem like they would benefit from a\nbase object cache; actually they might slow down from having such\na cache present!\n\nCommits tend not to delta well; if they delta it is a very rare\noccurrance. So we aren't getting huge unpacking benefits there\nby caching them. Scratch any benefit of the cache for any sort of\nrev-list operation that doesn't require tree access.\n\nAs for the other common operations (diff, read-tree, checkout-index,\nmerge-recursive): I don't think these will benefit from a cache\neither. Their data access patterns are pretty spread out over\nthe tree. With the exception of rename detection we hit everything\nonly once. After touching a path, we tend to not go back to it.\nSo unless we are really lucky and one blob acts as a base object\nfor many others at different paths (possible, but I suspect not\nvery likely) its not worth caching the base.\n\nIf we do hit something twice, its probably because we are doing two\ndistinct passes over the data. In this case the passes are probably\nbecause we either don't want to hold all of the data in memory (too\nbig of a set for some projects) or because we tried one algorithm,\nfailed, and are now trying a different one (internal read-tree\nin merge-recursive).\n\nCaching in merge-recursive may help, but just making the dirty\ncache (index) that resulted from the internal read-tree available\nfor the remainder of the merge-recursive process might be faster;\nespecially if we only have one base and don't need to recursively\nmerge multiple bases.\n\n\nSo where does that leave us? The only places I see a base object\ncache really helping is in git-blame for blob access, repeated\ntree access (git-blame and path limiting), and maybe we could do\nbetter with the common cases in merge-recursive by being smarter\nwith the cache.\n\nBut with pack v4 I don't think I need a tree object cache.\nWith a 6 byte fixed record format, a strict ordering requirement,\na finite delta depth within a packfile, a stricter tree-specific\ndelta encoder, and a minor API change to tree-walk.h, I think we\ncan unpack the delta at the same time that we are walking the tree.\nNo upfront unpack required. Hence no reason to cache.\n\n\nSo yea, a base object cache may help us today. It will most\ndefinately help in git-blame. But I doubt it will help with trees\nin pack v4, and I think it will just hurt in most cases. So maybe\nit should be local to git-blame only.\n\n-- \nShawn.\n"},{"id":"37324","messageId":"Pine.LNX.4.64.0703171044550.4964@woody.linux-foundation.org","threadId":"7262","inReplyTo":"alpine.LFD.0.83.0703162257560.18328@xanadu.home","subject":"Re: cleaner/better zlib sources?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-17T17:55:02Z","receivedAt":"2007-03-17T17:55:02Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 16 Mar 2007, Nicolas Pitre wrote:\n> \n> In the worst case, yes. And if you're walking history then the \n> probability of hitting the worst case eventually is rather high.\n\nActually, it's even better than that.\n\nIf we're walking a certain pathspec (which is reall ythe only thing that \nis expensive), we're pretty much *guaranteed* that we'll hit exactly this \ncase. Doing some instrumentation on the test-case I've been using (which \nis just \"git log drivers/usb/ > /dev/null\") shows:\n\n\t[torvalds@woody linux]$ grep Needs delta-base-trace | wc -l\n\t469334\n\t[torvalds@woody linux]$ grep Needs delta-base-trace | sort -u | wc -l\n\t21933\n\nwhere that delta-base-trace is just a trace of which delta bases were \nneeded. Look how we currently generate almost half a million of them, but \nonly 22000 are actually unique objects - we just generate many of them \nover and over again. In fact, the top delta bases with counts looks like:\n\n 558 Needs 102398354\n 556 Needs 161353360\n 554 Needs 161354852\n 552 Needs 161354916\n 550 Needs 161354980\n 526 Needs 161355044\n 524 Needs 161355108\n 522 Needs 161355174\n 520 Needs 161355238\n 508 Needs 161445724\n 446 Needs 119712387\n 425 Needs 133406737\n 420 Needs 161513997\n 387 Needs 120784913\n 331 Needs 127094253\n 321 Needs 95694853\n 319 Needs 125888524\n 303 Needs 155109487\n 301 Needs 155627964\n 299 Needs 155628028\n .....\n\nie the top twenty objects were all generated hundreds of times each.\n\nMore importantly, the trace also shows that it actually has very good \nlocality too - exactly as you'd expect, since when we traverse the trees, \nwe'd generally see a particular delta base used as a base when that thing \nis slowly changing, so of the half-million \"needs\" entries in my trace, if \nI pick the top delta_base (102398354), and use \"cat -n\" to give them all \nline numbers (from 1 to half a million), and grep for that particular \ndelta:\n\n\tgrep Needs delta-base-trace | cat -n | grep 102398354 | less -S\n\nthey are *all* at lines 61624..89352, with the bulk of them being very \nclose together (the bulk of those are all around 88k line mark).\n\nIn other words, it's not \"spread out\" over time. It's very clustered, \nwhich I'd expect anyway, which means that even a simple cache of just a \nfew hundred entries (statically sized) will be very effective.\n\nSo the cache doesn't need to be \"complete\". It will get good hit-rates \neven from being very simple. I think I have a very simple and cunning \nplan, I'll try it out asap.\n\n\t\tLinus\n"},{"id":"37327","messageId":"Pine.LNX.4.64.0703171232180.4964@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171044550.4964@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-17T19:40:14Z","receivedAt":"2007-03-17T19:40:14Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 17 Mar 2007, Linus Torvalds wrote:\n> \n> So the cache doesn't need to be \"complete\". It will get good hit-rates \n> even from being very simple. I think I have a very simple and cunning \n> plan, I'll try it out asap.\n\nOk, got distracted by guests coming to look at the new puppy, so it took \nlonger than it should have, but the following is a simple two-patch series \nthat improves path-following by a factor of almost 2.5 for me.\n\nThe cache is *really* simple. It's just a 256-entry hashed cache of the \nlast few base entries, and it brings down my test-case of\n\n\tgit log drivers/usb/ > /dev/null\n\nfrom 2.5s to just over 1s. I have *not* tuned or tweaked this at all, and \nmaybe there are better ways to do this, but this was simple as hell and \nobviously quite effective.\n\nIt also speeds up \"git blame\", for all the same reasons. Before (best \ntimes out of a run of five):\n\n\t[torvalds@woody linux]$ time git blame drivers/char/Makefile > /dev/null\n\treal 0m1.585s\n\tuser 0m1.576s\n\tsys 0m0.004s\n\nafter:\n\n\t[torvalds@woody linux]$ time ~/git/git blame drivers/char/Makefile > /dev/null\n\treal 0m0.763s\n\tuser 0m0.644s\n\tsys 0m0.120s\n\nso it's a factor of two there too (just a random file, I'm not at all \ngoing to guarantee that this is really consistent - it should get more \ntesting etc).\n\nThe first patch just does some obvious re-factoring and setting up (no \nreal code changes). The second patch just uses the new functions to \nactually add a cache.\n\n\t\tLinus\n"},{"id":"37328","messageId":"Pine.LNX.4.64.0703171240210.4964@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171232180.4964@woody.linux-foundation.org","subject":"[PATCH 1/2] Make trivial wrapper functions around delta base generation and freeing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-17T19:42:15Z","receivedAt":"2007-03-17T19:42:15Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis doesn't change any code, it just creates a point for where we'd\nactually do the caching of delta bases that have been generated.\n \nSigned-off-by: Linus Torvalds \n---\n\nDone this way to make all the changes as obvious as possible.\n\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 110d696..f11ca3f 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1352,6 +1352,18 @@ static void *unpack_compressed_entry(struct packed_git *p,\n \treturn buffer;\n }\n \n+static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n+\tunsigned long *base_size, enum object_type *type)\n+{\n+\treturn unpack_entry(p, base_offset, type, base_size);\n+}\n+\n+static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n+\tvoid *base, unsigned long base_size, enum object_type type)\n+{\n+\tfree(base);\n+}\n+\n static void *unpack_delta_entry(struct packed_git *p,\n \t\t\t\tstruct pack_window **w_curs,\n \t\t\t\toff_t curpos,\n@@ -1365,7 +1377,7 @@ static void *unpack_delta_entry(struct packed_git *p,\n \toff_t base_offset;\n \n \tbase_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);\n-\tbase = unpack_entry(p, base_offset, type, &base_size);\n+\tbase = cache_or_unpack_entry(p, base_offset, &base_size, type);\n \tif (!base)\n \t\tdie(\"failed to read delta base object\"\n \t\t \" at %\"PRIuMAX\" from %s\",\n@@ -1378,7 +1390,7 @@ static void *unpack_delta_entry(struct packed_git *p,\n \tif (!result)\n \t\tdie(\"failed to apply delta\");\n \tfree(delta_data);\n-\tfree(base);\n+\tadd_delta_base_cache(p, base_offset, base, base_size, *type);\n \treturn result;\n }\n \n"},{"id":"37329","messageId":"Pine.LNX.4.64.0703171242180.4964@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171232180.4964@woody.linux-foundation.org","subject":"[PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-17T19:44:06Z","receivedAt":"2007-03-17T19:44:06Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis trivial 256-entry delta_base cache improves performance for some \nloads by a factor of 2.5 or so.\n\nInstead of always re-generating the delta bases (possibly over and over \nand over again), just cache the last few ones. They often can get re-used.\n\nSigned-off-by: Linus Torvalds \n---\n\nThis should have some other people doing performance testing too, since \nit's fairly core. But *dang*, it's really simple.\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex f11ca3f..a7e3a2a 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1352,16 +1352,57 @@ static void *unpack_compressed_entry(struct packed_git *p,\n \treturn buffer;\n }\n \n+#define MAX_DELTA_CACHE (256)\n+\n+static struct delta_base_cache_entry {\n+\tstruct packed_git *p;\n+\toff_t base_offset;\n+\tunsigned long size;\n+\tvoid *data;\n+\tenum object_type type;\n+} delta_base_cache[MAX_DELTA_CACHE];\n+\n+static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)\n+{\n+\tunsigned long hash;\n+\n+\thash = (unsigned long)p + (unsigned long)base_offset;\n+\thash += (hash >> 8) + (hash >> 16);\n+\treturn hash & 0xff;\n+}\n+\n static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n \tunsigned long *base_size, enum object_type *type)\n {\n+\tvoid *ret;\n+\tunsigned long hash = pack_entry_hash(p, base_offset);\n+\tstruct delta_base_cache_entry *ent = delta_base_cache + hash;\n+\n+\tret = ent->data;\n+\tif (ret && ent->p == p && ent->base_offset == base_offset)\n+\t\tgoto found_cache_entry;\n \treturn unpack_entry(p, base_offset, type, base_size);\n+\n+found_cache_entry:\n+\tent->data = NULL;\n+\t*type = ent->type;\n+\t*base_size = ent->size;\n+\treturn ret;\n }\n \n static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \tvoid *base, unsigned long base_size, enum object_type type)\n {\n-\tfree(base);\n+\tunsigned long hash = pack_entry_hash(p, base_offset);\n+\tstruct delta_base_cache_entry *ent = delta_base_cache + hash;\n+\n+\tif (ent->data)\n+\t\tfree(ent->data);\n+\tent->p = p;\n+\tent->base_offset = base_offset;\n+\tent->type = type;\n+\tent->data = base;\n+\tent->size = base_size;\n }\n \n static void *unpack_delta_entry(struct packed_git *p,\n"},{"id":"37332","messageId":"Pine.LNX.4.64.0703171420420.4964@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171242180.4964@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-17T21:45:49Z","receivedAt":"2007-03-17T21:45:49Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 17 Mar 2007, Linus Torvalds wrote:\n> \n> Instead of always re-generating the delta bases (possibly over and over \n> and over again), just cache the last few ones. They often can get re-used.\n\nNot just to compare actual timings, this shows the difference in the \ntraces I did. Remember, before we had:\n\n\t[torvalds@woody linux]$ grep Needs delta-base-trace | wc -l\n\t469334\n\t[torvalds@woody linux]$ grep Needs delta-base-trace |sort -u | wc -l\n\t21933\n\nand now with the simple cache, I get:\n\n\t[torvalds@woody linux]$ grep Needs delta-base-trace-new | wc -l\n\t28688\n\t[torvalds@woody linux]$ grep Needs delta-base-trace-new | sort -u | wc -l\n\t21933\n\nie, we still re-generate some of the objects multiple times, but now, \nrather than generating them (on average) 20+ times each, we now generate \nthem an average of just 1.3 times each. Which explains why the wall-time \ngoes down by over a factor of two.\n\nChanging the (statically sized) cache from 256 entries to 1024 (and \nupdating the hash function appropriately of course) gets the number down \nto 23953 delta-base lookups (the number of unique ones obviously stays the \nsame), for an average of just 1.1 object generates per unique object, and \nalso means that you occasionally get sub-second times for my test-case of \nlogging drivers/usb/.\n\nIt all also means that libz isn't really even the top entry in the \nprofiles any more, although it's still pretty high. But the profile now \nsays:\n\n\tsamples % app name symbol name\n\t41527 15.6550 git strlen\n\t30215 11.3905 git inflate\n\t27504 10.3685 git inflate_table\n\t20321 7.6607 git find_pack_entry_one\n\t16892 6.3680 git interesting\n\t16259 6.1294 vmlinux __copy_user_nocache\n\t16010 6.0355 git inflate_fast\n\t9240 3.4833 git get_mode\n\t8863 3.3412 git tree_entry_extract\n\t7145 2.6935 git strncmp\n\t7131 2.6883 git memcpy\n\t6863 2.5872 git diff_tree\n\t6113 2.3045 git adler32\n\t4515 1.7021 git _int_malloc\n\t3022 1.1392 git update_tree_entry\n\t...\n\n(Adding up all of libz is still ~31%, but it's lower as a percentage *and* \nit's obviously a smaller percentage of a much lower absolute time, so the \nzlib overhead went down much more than any other git overheads did)\n\nIn general, this all seems very cool. The patches are simple enough that I \nthink this is very safe to merge indeed: the only question I have is that \nsomebody should verify that the \"struct packed_git *p\" is stable over the \nwhole lifetime of a process - so that we can use it as a hash key without \nhaving to invalidate hashes if we unmap a pack (I *think* we just unmap \nthe virtual mapping, and \"struct packed_git *\" stays valid, but Junio \nshould ack that for me).\n\nHere's the trivial patch to extend the caching to 1k entries if somebody \ncares. I don't know if the small added performance is worth it.\n\n\t\tLinus\n---\ndiff --git a/sha1_file.c b/sha1_file.c\nindex a7e3a2a..372af60 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1352,7 +1352,7 @@ static void *unpack_compressed_entry(struct packed_git *p,\n \treturn buffer;\n }\n \n-#define MAX_DELTA_CACHE (256)\n+#define MAX_DELTA_CACHE (1024)\n \n static struct delta_base_cache_entry {\n \tstruct packed_git *p;\n@@ -1367,8 +1367,8 @@ static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)\n \tunsigned long hash;\n \n \thash = (unsigned long)p + (unsigned long)base_offset;\n-\thash += (hash >> 8) + (hash >> 16);\n-\treturn hash & 0xff;\n+\thash += (hash >> 10) + (hash >> 20);\n+\treturn hash & (MAX_DELTA_CACHE-1);\n }\n \n static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n"},{"id":"37334","messageId":"7vfy83qyxh.fsf@assigned-by-dhcp.cox.net","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171420420.4964@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-17T22:37:30Z","receivedAt":"2007-03-17T22:37:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> ie, we still re-generate some of the objects multiple times, but now, \n> rather than generating them (on average) 20+ times each, we now generate \n> them an average of just 1.3 times each. Which explains why the wall-time \n> goes down by over a factor of two.\n\nThis is beautiful. You only cache what we were about to discard\nanyway, and when giving a cached one out, you invalidate the\ncached entry, so there is no way the patch can introduce leaks\nnor double-frees and it is absolutely safe (as long as we can\npin the packed_git structure, which I think is the case --- even\nwhen we re-read the packs, I do not think we discard old ones).\n\nI've thought about possible ways to improve on it, but came up\nalmost empty.\n\nWhen unpacking a depth-3 deltified object A, the code finds the\ntarget object A (which is a delta), ask for its base B and put B\nin the cache after using it to reconstitute A. While doing so,\nthe first-generation base B is also a delta so its base C (which\nis a non-delta) is found and placed in the cache. When A is\nreturned, the cache has B and C. If you ask for B at this\npoint, we read the delta, pick up its base C from the cache,\napply, and return while putting C back in the cache. If you ask\nfor A after that, we do not read from the cache, although it is\navailable.\n\nWhich feels a bit wasteful at first sight, and we *could* make\nread_packed_sha1() also steal from the cache, but after thinking\nabout it a bit, I am not sure if it is worth it. The contract\nbetween read_packed_sha1() and read_sha1_file() and its callers\nis that the returned data belongs to the caller and it is a\nresponsibility for the caller to free the buffer, and also the\ncaller is free to modify it, so stealing from the cache from\nthat codepath means an extra allocation and memcpy. If the\nobject stolen from the cache is of sufficient depth, it might be\nworth it, but to decide it we somehow need to compute and store\nwhich delta depth the cached one is at.\n\nIn any way, your code makes a deeply delitified packfiles a lot\nmore practical. As long as the working set of delta chains fits\nin the cache, after unpacking the longuest delta, the objects on\nthe chain can be had by one lookup and one delta application.\n\nVery good job.\n\n> In general, this all seems very cool. The patches are simple enough that I \n> think this is very safe to merge indeed: the only question I have is that \n> somebody should verify that the \"struct packed_git *p\" is stable over the \n> whole lifetime of a process - so that we can use it as a hash key without \n> having to invalidate hashes if we unmap a pack (I *think* we just unmap \n> the virtual mapping, and \"struct packed_git *\" stays valid, but Junio \n> should ack that for me).\n\nAck ;-)\n"},{"id":"37335","messageId":"Pine.LNX.4.64.0703171521180.4964@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171242180.4964@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-17T22:44:54Z","receivedAt":"2007-03-17T22:44:54Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 17 Mar 2007, Linus Torvalds wrote:\n> \n> This trivial 256-entry delta_base cache improves performance for some \n> loads by a factor of 2.5 or so.\n\nBtw, final comment on this issue:\n\nI was initially a bit worried about optimizing for just the \"git log\" with \npathspec or \"git blame\" kind of behaviour, and possibly pessimizing some \nother load.\n\nBut the way the caching works, this is likely to be faster (or at least \nnot slower) even for something that doesn't ever need the cache (which in \nturn is likely to be because it's a smaller footprint query and only works \non one version).\n\nBecause the way the cache works, it doesn't really do any extra work: it \nbasically just delays the \"free()\" on the buffer we allocated. So for \nreally small footprints it just avoids the overhead of free() (let the OS \nreap the pages for it at exit), and for bigger footprints (that end up \nreplacing the cache entries) it will just do the same work a bit later.\n\nBecause it's a simple direct-mapped cache, the only cost is the (trivial) \nhash of a few instructions, and possibly the slightly bigger D$ footprint. \nI would strongly suspect that even on loads where it doesn't help by \nreusing the cached objects, the delayed free'ing on its own is as likely \nto help as it is to hurt.\n\nSo there really shouldn't be any downsides.\n\nTesting on some other loads (for example, drivers/scsi/ has more activity \nthan drivers/usb/), the 2x performance win seems to happen for other \nthings too. For drivers/scsi, the log generating went down from 3.582s \n(best) to 1.448s.\n\n\"git blame Makefile\" went from 1.802s to 1.243s (both best-case numbers \nagain: a smaller win, but still a win), but there the issue seems to be \nthat with a file like that, we actually spend most of our time comparing \ndifferent versions.\n\nFor the \"git blame Makefile\" case *all* of zlib combined is just 18%, \nwhile the ostensibly trivial \"cmp_suspect()\" is 23% and another 11% is \nfrom \"assign_blame()\" - so for top-level entries the costs would seem to \ntend to be in the blame algorithm itself, rather than in the actual object \nhandling.\n\n(I'm sure that could be improved too, but the take-home message from this \nis that zlib wasn't really the problem, and our stupid re-generation of \nthe same delta base was.\n\n\t\t\tLinus\n"},{"id":"37336","messageId":"Pine.LNX.4.64.0703171557360.4964@woody.linux-foundation.org","threadId":"7262","inReplyTo":"7vfy83qyxh.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-17T23:09:57Z","receivedAt":"2007-03-17T23:09:57Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 17 Mar 2007, Junio C Hamano wrote:\n> \n> When unpacking a depth-3 deltified object A, the code finds the\n> target object A (which is a delta), ask for its base B and put B\n> in the cache after using it to reconstitute A. While doing so,\n> the first-generation base B is also a delta so its base C (which\n> is a non-delta) is found and placed in the cache. When A is\n> returned, the cache has B and C. If you ask for B at this\n> point, we read the delta, pick up its base C from the cache,\n> apply, and return while putting C back in the cache. If you ask\n> for A after that, we do not read from the cache, although it is\n> available.\n\nYes.\n\nI debated that a bit with myself, but decided that:\n\n (a) it probably doesn't really matter a lot (but I don't have the \n numbers)\n\n (b) trying to *also* fill non-delta-base queries from the delta-base \n cache actually complicates things a lot. Surprisingly much so (the \n current logic of removing the entry from the cache only to re-insert \n it after being used made the memory management totally trivial, as \n you noticed)\n\n (c) and regardless, we could decide to do a more extensive caching layer \n later if we really wanted to, and at that point it probably makes \n more sense to integrate it with the delta-base cache.\n\n Most git objects are use-once, which is why we really *just* save the \n flag bits and the SHA1 hash name itself in \"struct object\", but doing \n a generic caching layer for object content would likely obviate the \n need for the current logic to do \"save_commit_buffer\".\n\nThat (c) in particular was what made me think that it's better to keep it \nsimple and obvious for now, since even the simple thing largely fixes the \nperformance issue. Almost three seconds I felt bad about, while just over \na second for something as complex as \"git log drivers/usb/\" I just cannot \nmake myself worry about.\n\n> In any way, your code makes a deeply delitified packfiles a lot\n> more practical. As long as the working set of delta chains fits\n> in the cache, after unpacking the longuest delta, the objects on\n> the chain can be had by one lookup and one delta application.\n\nYeah. I think it would be good to probably (separately and as \"further \ntweaks\"):\n\n - have somebody actually look at hit-rates for different repositories and \n hash sizes.\n\n - possibly allow people to set the hash size as a config option, if it \n turns out that certain repository layouts or usage scenarios end up \n preferring bigger caches.\n\n For example, it may be that for historical archives you might want to \n have deeper delta queues to make the repository smaller, and if they \n are big anyway maybe they would prefer to have a larger-than-normal \n cache as a result. On the other hand, if you are memory-constrained, \n maybe you'd prefer to re-generate the objects and waste a bit of CPU \n rather than cache the results.\n\nBut neither of the above is really an argument against the patch, just a \n\"there's certainly room for more work here if anybody cares\".\n\n> Very good job.\n\nI'm pretty happy with the results myself. Partly because the patches just \nended up looking so *nice*.\n\n\t\tLinus\n"},{"id":"37337","messageId":"7vabybqxaj.fsf@assigned-by-dhcp.cox.net","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171420420.4964@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-17T23:12:52Z","receivedAt":"2007-03-17T23:12:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Here's the trivial patch to extend the caching to 1k entries if somebody \n> cares. I don't know if the small added performance is worth it.\n\nThis largely would depend on the project, but if a blob that is\ncached is 20kB each, a 1024-entry cache would grow to 20MB. We\nmay need to introduce early eviction of cached objects with\ntotal cache size limit, configurable per repository.\n"},{"id":"37338","messageId":"Pine.LNX.4.64.0703171619440.4964@woody.linux-foundation.org","threadId":"7262","inReplyTo":"7vabybqxaj.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-17T23:24:23Z","receivedAt":"2007-03-17T23:24:23Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 17 Mar 2007, Junio C Hamano wrote:\n> \n> This largely would depend on the project, but if a blob that is\n> cached is 20kB each, a 1024-entry cache would grow to 20MB. We\n> may need to introduce early eviction of cached objects with\n> total cache size limit, configurable per repository.\n\nOne thing that I considered was to limit the delta-base cache to just tree \nentries. Those tend to be the really performance-sensitive ones - by the \ntime you actually unpack blob entries, you're going to do something with \nthat *single* entry anyway (like compare it to another blob), and the cost \nof unpacking the entry is likely to not be really all that noticeable.\n\nThat said, it was just simpler to do it unconditionally, and it obviously \n*works* fine regardless of the object type, so limiting it to trees is a \nbit sad. And since the intensive tree operations tend to be in a separate \nphase (ie the commit simplification phase) from the the blob operations \n(say, doing \"git log -p \"), I suspect that the cache locality \nwould still remain good.\n\nSo I didn't do anything along the lines of \"only cache for case Xyzzy\".\n\nBut yes, especially if a project has big blobs, it might make sense to \nlimit by full size of the cached entries some way.\n\n\t\t\tLinus\n"},{"id":"37339","messageId":"9e4733910703171652n61c08814td78ee5fc7bc5957b@mail.gmail.com","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171619440.4964@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-03-17T23:52:23Z","receivedAt":"2007-03-17T23:52:23Z","isPatch":true,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"If you still have a Mozilla pack file around it would be a good test\ncase. It has delta chains thousands of entries long. If I remember\ncorrectly one had over 4,000 deltas.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"37340","messageId":"Pine.LNX.4.64.0703171638000.4964@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171557360.4964@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-17T23:54:18Z","receivedAt":"2007-03-17T23:54:18Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 17 Mar 2007, Linus Torvalds wrote:\n> \n> (a) it probably doesn't really matter a lot (but I don't have the \n> numbers)\n\nWell, to some degree I obviously *do* have the numbers.\n\nI have the numbers that we used to re-generate the object data over five \n*hundred* times per object for some cases, and that I got the average \nsuch delta-base usage down from 20x to 1.1-1.3x depending on cache size.\n\nIn contrast, the \"use delta-base also for non-delta queries\" fairly \nobviously cannot touch those kinds of numbers. We migth avoid a *few* \nobject generation cases, but we're not looking at factors of 20 for any \nkind of sane cases.\n\nSo I do think that a higher-level caching approach can work too, but it's \ngoing to be more effective in other areas:\n\n - get rid of some ugly hacks (like the \"save_commit_buffer\" thing I \n mentioned)\n - possibly help some insane loads (eg cases where we really *do* end up \n seeing the same object over and over again, perhaps simply because some \n idiotic automated commit system ends up switching between a few states \n back-and-forth).\n\nI really think the \"insane loads\" thing is unlikely, but I could construct \nsome crazy usage scenario where a cache of objects in general (and not \njust delta bases) would work. I don't think it's a very realistic case, \nbut who knows - people sometimes do really stupid things.\n\n\t\tLinus\n"},{"id":"37341","messageId":"alpine.LFD.0.83.0703172053020.18328@xanadu.home","threadId":"7262","inReplyTo":"7vfy83qyxh.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-18T01:13:57Z","receivedAt":"2007-03-18T01:13:57Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 17 Mar 2007, Junio C Hamano wrote:\n\n> When unpacking a depth-3 deltified object A, the code finds the\n> target object A (which is a delta), ask for its base B and put B\n> in the cache after using it to reconstitute A. While doing so,\n> the first-generation base B is also a delta so its base C (which\n> is a non-delta) is found and placed in the cache. When A is\n> returned, the cache has B and C. If you ask for B at this\n> point, we read the delta, pick up its base C from the cache,\n> apply, and return while putting C back in the cache. If you ask\n> for A after that, we do not read from the cache, although it is\n> available.\n> \n> Which feels a bit wasteful at first sight, and we *could* make\n> read_packed_sha1() also steal from the cache, but after thinking\n> about it a bit, I am not sure if it is worth it. The contract\n> between read_packed_sha1() and read_sha1_file() and its callers\n> is that the returned data belongs to the caller and it is a\n> responsibility for the caller to free the buffer, and also the\n> caller is free to modify it, so stealing from the cache from\n> that codepath means an extra allocation and memcpy.\n\nSo?\n\nA malloc() + memcpy() will always be faster than mmap() + malloc() + \ninflate(). If the data is already there it is certainly better to copy \nit straight away.\n\nWith the patch below I can do 'git log drivers/scsi/ > /dev/null' about \n7% faster. I bet it might be even more on those platforms with bad \nmmap() support.\n\nSigned-off-by: Nicolas Pitre \n---\ndiff --git a/sha1_file.c b/sha1_file.c\nindex a7e3a2a..ee64865 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1372,7 +1372,7 @@ static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)\n }\n \n static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n-\tunsigned long *base_size, enum object_type *type)\n+\tunsigned long *base_size, enum object_type *type, int keep_cache)\n {\n \tvoid *ret;\n \tunsigned long hash = pack_entry_hash(p, base_offset);\n@@ -1384,7 +1384,13 @@ static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n \treturn unpack_entry(p, base_offset, type, base_size);\n \n found_cache_entry:\n-\tent->data = NULL;\n+\tif (!keep_cache)\n+\t\tent->data = NULL;\n+\telse {\n+\t\tret = xmalloc(ent->size + 1);\n+\t\tmemcpy(ret, ent->data, ent->size);\n+\t\t((char *)ret)[ent->size] = 0;\n+\t}\n \t*type = ent->type;\n \t*base_size = ent->size;\n \treturn ret;\n@@ -1418,7 +1424,7 @@ static void *unpack_delta_entry(struct packed_git *p,\n \toff_t base_offset;\n \n \tbase_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);\n-\tbase = cache_or_unpack_entry(p, base_offset, &base_size, type);\n+\tbase = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);\n \tif (!base)\n \t\tdie(\"failed to read delta base object\"\n \t\t \" at %\"PRIuMAX\" from %s\",\n@@ -1615,7 +1621,7 @@ static void *read_packed_sha1(const unsigned char *sha1,\n \tif (!find_pack_entry(sha1, &e, NULL))\n \t\treturn NULL;\n \telse\n-\t\treturn unpack_entry(e.p, e.offset, type, size);\n+\t\treturn cache_or_unpack_entry(e.p, e.offset, size, type, 1);\n }\n \n /*\n"},{"id":"37342","messageId":"118833cc0703171814n4e56ab9fwfaaea81c903ae235@mail.gmail.com","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171420420.4964@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Morten Welinder","fromEmail":"mwelinder@gmail.com","sentAt":"2007-03-18T01:14:16Z","receivedAt":"2007-03-18T01:14:16Z","isPatch":true,"sender":{"key":"mwelinder@gmail.com","avatar":null},"body":"> samples % app name symbol name\n> 41527 15.6550 git strlen\n\nAlmost 16% in strlen? Ugh!\n\nThat's a lot of strings, or perhaps very long strings. Or a profiling bug.\n\nM.\n"},{"id":"37343","messageId":"Pine.LNX.4.64.0703171822280.4964@woody.linux-foundation.org","threadId":"7262","inReplyTo":"118833cc0703171814n4e56ab9fwfaaea81c903ae235@mail.gmail.com","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-18T01:29:38Z","receivedAt":"2007-03-18T01:29:38Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 17 Mar 2007, Morten Welinder wrote:\n>\n> > samples % app name symbol name\n> > 41527 15.6550 git strlen\n> \n> Almost 16% in strlen? Ugh!\n> \n> That's a lot of strings, or perhaps very long strings. Or a profiling bug.\n\nIt's likely real, and the problem is likely lots of small strings.\n\nEach git tree entry is:\n\n\t\" name\\0\" <20-byte sha1>\n\nso you do have a *lot* of strlen() calls when doing any tree parsing. And \nfor some inexplicable reason, glibc thinks strings are long on average, so \nit has a fancy algorithm to do 8 bytes at a time and tries to do things \naligned etc.\n\nThe size of strlen() on x86-64 with glibc is 232 bytes. I'm not kidding.\n\n\t\t\tLinus\n"},{"id":"37344","messageId":"alpine.LFD.0.83.0703172136440.18328@xanadu.home","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171822280.4964@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-18T01:38:16Z","receivedAt":"2007-03-18T01:38:16Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 17 Mar 2007, Linus Torvalds wrote:\n\n> \n> \n> On Sat, 17 Mar 2007, Morten Welinder wrote:\n> >\n> > > samples % app name symbol name\n> > > 41527 15.6550 git strlen\n> > \n> > Almost 16% in strlen? Ugh!\n> > \n> > That's a lot of strings, or perhaps very long strings. Or a profiling bug.\n> \n> It's likely real, and the problem is likely lots of small strings.\n> \n> Each git tree entry is:\n> \n> \t\" name\\0\" <20-byte sha1>\n> \n> so you do have a *lot* of strlen() calls when doing any tree parsing.\n\nThis is definitely an area where pack v4 will bring that cost down to \nzero.\n\n\nNicolas\n"},{"id":"37345","messageId":"Pine.LNX.4.64.0703171833420.21612@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171822280.4964@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-18T01:44:05Z","receivedAt":"2007-03-18T01:44:05Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 17 Mar 2007, Linus Torvalds wrote:\n> > \n> > That's a lot of strings, or perhaps very long strings. Or a profiling bug.\n\nBtw, the reason I'm pretty sure that it's not a profiling bug is that\n (a) the rest of the profile looks fine\n (b) it actually matches the rest of the profile.\n\nIn particular, while you reacted to\n\n\tsamples % app name symbol name\n\t41527 15.6550 git strlen\n\nyou didn't bat an eye on\n\n\t9240 3.4833 git get_mode\n\t8863 3.3412 git tree_entry_extract\n\nie over 3% of time spent in tree entry extract and get_mode. But take \nanother look at that tree_entry_extract() function in particular and look \nwhat it does, and ask yourself: if *that* function takes up 3% of time, \nwhat does it tell you about strlen()?\n\n(Side note: we could probably improve \"strlen()\" in particular. We \nsometimes call it twice: look at \"entry_extract()\", which calls strlen() \non the tree entry extract, but then *also* calls strlen on the resulting \npath.\n\nI suspect the\n\n\ta->pathlen = strlen(a->path);\n\ncould be written as\n\n\ta->pathlen = (char *)a->sha1 - (char *)a->path - 1;\n\nbut somebody should check that I didn't off-by-one or something. Also, it \nmigt be better to make that part of \"tree_entry_extract()\" itself, because \nother callers do the same thing (see \"find_tree_entry()\": doing a \n\"strlen()\" on the path return of tree_entry_extract() seems to be a common \npattern).\n\nHOWEVER!\n\nOnce we get to *that* level of optimizations, we're doing pretty damn \nwell. I'm sure we could probably cut down that strlen() from 16% to 8% by \nbeing smart about it, but still - this is a \"good kind of problem\" to \nhave, if these things are your lowest-hanging fruit!\n\nMaybe it all boils down to the same thing: I just can't seem to be really \nupset about \"git log drivers/usb/ > /dev/null\" taking all of a second. It \njust doesn't strike me as a performance problem ;)\n\n\t\t\tLinus\n"},{"id":"37346","messageId":"Pine.LNX.4.64.0703171854270.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"alpine.LFD.0.83.0703172136440.18328@xanadu.home","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-18T01:55:37Z","receivedAt":"2007-03-18T01:55:37Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 17 Mar 2007, Nicolas Pitre wrote:\n> \n> This is definitely an area where pack v4 will bring that cost down to \n> zero.\n\nHeh. I believe that when I see it. The thing is, unless you re-generate \nthe tree object data structures, you'll have to have totally different \ntree walkers for different tree types, and it will all be quite ugly and \ncomplex. And \"ugly and complex\" seldom translates into \"zero cost\".\n\n\t\tLinus\n"},{"id":"37347","messageId":"alpine.LFD.0.83.0703172200060.18328@xanadu.home","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171854270.6730@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-18T02:03:36Z","receivedAt":"2007-03-18T02:03:36Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 17 Mar 2007, Linus Torvalds wrote:\n\n> \n> \n> On Sat, 17 Mar 2007, Nicolas Pitre wrote:\n> > \n> > This is definitely an area where pack v4 will bring that cost down to \n> > zero.\n> \n> Heh. I believe that when I see it. The thing is, unless you re-generate \n> the tree object data structures, you'll have to have totally different \n> tree walkers for different tree types, and it will all be quite ugly and \n> complex. And \"ugly and complex\" seldom translates into \"zero cost\".\n\nWell... in my opinion it is the _current_ tree walker that is quite ugly \nand complex. It is always messier to parse strings than fixed width \nbinary fields.\n\n\nNicolas\n"},{"id":"37349","messageId":"Pine.LNX.4.64.0703171911120.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"alpine.LFD.0.83.0703172200060.18328@xanadu.home","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-18T02:20:41Z","receivedAt":"2007-03-18T02:20:41Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 17 Mar 2007, Nicolas Pitre wrote:\n> \n> Well... in my opinion it is the _current_ tree walker that is quite ugly \n> and complex. It is always messier to parse strings than fixed width \n> binary fields.\n\nSure. On the other hand, text is what made things easy to do initially, \nand you're missing one *BIG* clue: you cannot remote the support without \nlosing compatibility with all traditional object formats.\n\nSo you have no choice. You need to support the text representation. As a \nresult, *your* code will now be way more ugly and messy.\n\nThe thing is, parsing some little text may sound expensive, but if the \nexpense is in finding the end of the string, we're doing really well.\n\nIn other words: the data structures are both simple and straightforward, \nand the only reason strlen() shows up at all is:\n\n - we pass strings around as just C strings, even when we know their \n lengths. Prime example: look at tree-diff.c. And when you look at it, \n realize that *for*every*single*strlen* in that file except for the very \n last one (which is only used once per process for setup) we actually \n know the string length from before, but we (well, *I*) decided that it \n wasn't worth passing down as a parameter all the time.\n\n - the simple parsing of the tree itself (which really isn't that \n expensive - the real expense is bringing the data into the CPU cache, \n but that's something we'd need to do *anyway*).\n\nSo I seriously suspect that you could get the strlen() overhead down from \nthat 16% pretty easily, but you'd have to pass the length of the \"base\" \nstring along all the time (and in the tree_entry cases you'd replace the \n\"strlen()\" calls with a call to something like\n\n\tstatic inline int tree_entry_len(const char *name, const unsigned char *sha1)\n\t{\n\t\treturn (char *)sha1 - (char *)name - 1;\n\t}\n\nwhich will do it for you).\n\nBut what you're ignoring here is that \"16%\" may sound like a huge deal, \nbut it's 16% of somethng that takes 1 second, and that other SCM's cannot \ndo AT ALL.\n\n\t\tLinus\n"},{"id":"37350","messageId":"alpine.LFD.0.83.0703172228220.18328@xanadu.home","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171911120.6730@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-18T03:00:10Z","receivedAt":"2007-03-18T03:00:10Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 17 Mar 2007, Linus Torvalds wrote:\n\n> \n> \n> On Sat, 17 Mar 2007, Nicolas Pitre wrote:\n> > \n> > Well... in my opinion it is the _current_ tree walker that is quite ugly \n> > and complex. It is always messier to parse strings than fixed width \n> > binary fields.\n> \n> Sure. On the other hand, text is what made things easy to do initially,\n\nOh indeed. No argument there.\n\n> and you're missing one *BIG* clue: you cannot remote the support without \n> losing compatibility with all traditional object formats.\n> \n> So you have no choice. You need to support the text representation. As a \n> result, *your* code will now be way more ugly and messy.\n\nDepends. We currently have separate parsers for trees, commits, tags, \netc. That should be easy enough to add another (separate) parser for \nnew tree objects while still having a common higher level accessor \ninterface like tree_entry().\n\nBut right now we only regenerate the text representation whenever the \nbinary representation is encountered just to make things easy to do, and \nyet we still have a performance gain already in _addition_ to a net \nsaving in disk footprint.\n\n> The thing is, parsing some little text may sound expensive, but if the \n> expense is in finding the end of the string, we're doing really well.\n\nOf course the current tree parser will remain, probably forever. And it \nis always a good thing to optimize it further when ever possible.\n\n> But what you're ignoring here is that \"16%\" may sound like a huge deal, \n> but it's 16% of somethng that takes 1 second, and that other SCM's cannot \n> do AT ALL.\n\nSure. But at this point the reference to compare GIT performance \nagainst might be GIT itself. And while 1 second is really nice in this \ncase, there are some repos where it could be (and has already been \nreported to be) much more.\n\nI still have a feeling that we can do even better than we do now. Much \nmuch better than 16% actually. But that require a new data format that \nis designed for speed.\n\nWe'll see.\n\n\nNicolas\n"},{"id":"37351","messageId":"Pine.LNX.4.64.0703171949190.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171911120.6730@woody.linux-foundation.org","subject":"[PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-18T03:06:24Z","receivedAt":"2007-03-18T03:06:24Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis is a micro-optimization that grew out of the mailing list discussion \nabout \"strlen()\" showing up in profiles. \n\nWe used to pass regular C strings around to the low-level tree walking \nroutines, and while this worked fine, it meant that we needed to call \nstrlen() on strings that the caller always actually knew the size of \nanyway.\n\nSo pass the length of the string down wih the string, and avoid \nunnecessary calls to strlen(). Also, when extracting a pathname from a \ntree entry, use \"tree_entry_len()\" instead of strlen(), since the length \nof the pathname is directly calculable from the decoded tree entry itself \nwithout having to actually do another strlen().\n\nThis shaves off another ~5-10% from some loads that are very tree \nintensive (notably doing commit filtering by a pathspec).\n\nSigned-off-by: Linus Torvalds \"\n---\n\nOn Sat, 17 Mar 2007, Linus Torvalds wrote:\n>\n> - we pass strings around as just C strings, even when we know their \n> lengths. Prime example: look at tree-diff.c. And when you look at it, \n> realize that *for*every*single*strlen* in that file except for the very \n> last one (which is only used once per process for setup) we actually \n> know the string length from before, but we (well, *I*) decided that it \n> wasn't worth passing down as a parameter all the time.\n\nSo here's the patch.\n\nIt definitely cuts down on CPU usage, and I actually left one extra \n\"strlen()\" around, simply because I didn't want to mess with the exported \ninterface of \"diff_tree()\".\n\nBut that other strlen() is also one that is done *once* for the whole \ntree, so from a performance standpoint it doesn't matter (we *could* have \npassed in that length too, but that would have involved more changes that \nsimply aren't really useful).\n\nDoes it help? Yes it does. It takes another 5-10% off my test-case. \n\"strlen()\" still exists, but it's basically half of what it used to be \nbecause we now basically only call it when literally parsing the tree data \nitself (ie now it's ~8% of the total, and no longer the hottest entry.\n\nIs it worth it? If it was just a random micro-optimization I might not \ncare, but I guess it's not that ugly to pass an extra \"baselen\" around all \nthe time. And that \"tree_entry_len()\" helper function is actually quite \nnice. So yeah, I'd suggest applying this one just because it's actually a \nperfectly fine patch and it does speed things up.\n\nSo it *is* very much a micro-optimization, but one that doesn't really \nmake the code any uglier, so why not..\n\nI still think that if we do these kinds of optimizations and they matter, \nthat shows just how *well* we're actually doing here!\n\nAnyway, Junio, it passes all the tests, as well as passing my \"looks \nobviously correct\" filter, so..\n\n\t\tLinus\n\n---\ndiff --git a/tree-diff.c b/tree-diff.c\nindex c827582..f89b9d3 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -5,9 +5,8 @@\n #include \"diff.h\"\n #include \"tree.h\"\n \n-static char *malloc_base(const char *base, const char *path, int pathlen)\n+static char *malloc_base(const char *base, int baselen, const char *path, int pathlen)\n {\n-\tint baselen = strlen(base);\n \tchar *newbase = xmalloc(baselen + pathlen + 2);\n \tmemcpy(newbase, base, baselen);\n \tmemcpy(newbase + baselen, path, pathlen);\n@@ -16,9 +15,9 @@ static char *malloc_base(const char *base, const char *path, int pathlen)\n }\n \n static void show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc,\n-\t\t const char *base);\n+\t\t const char *base, int baselen);\n \n-static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)\n+static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const char *base, int baselen, struct diff_options *opt)\n {\n \tunsigned mode1, mode2;\n \tconst char *path1, *path2;\n@@ -28,15 +27,15 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const\n \tsha1 = tree_entry_extract(t1, &path1, &mode1);\n \tsha2 = tree_entry_extract(t2, &path2, &mode2);\n \n-\tpathlen1 = strlen(path1);\n-\tpathlen2 = strlen(path2);\n+\tpathlen1 = tree_entry_len(path1, sha1);\n+\tpathlen2 = tree_entry_len(path2, sha2);\n \tcmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);\n \tif (cmp < 0) {\n-\t\tshow_entry(opt, \"-\", t1, base);\n+\t\tshow_entry(opt, \"-\", t1, base, baselen);\n \t\treturn -1;\n \t}\n \tif (cmp > 0) {\n-\t\tshow_entry(opt, \"+\", t2, base);\n+\t\tshow_entry(opt, \"+\", t2, base, baselen);\n \t\treturn 1;\n \t}\n \tif (!opt->find_copies_harder && !hashcmp(sha1, sha2) && mode1 == mode2)\n@@ -47,14 +46,14 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const\n \t * file, we need to consider it a remove and an add.\n \t */\n \tif (S_ISDIR(mode1) != S_ISDIR(mode2)) {\n-\t\tshow_entry(opt, \"-\", t1, base);\n-\t\tshow_entry(opt, \"+\", t2, base);\n+\t\tshow_entry(opt, \"-\", t1, base, baselen);\n+\t\tshow_entry(opt, \"+\", t2, base, baselen);\n \t\treturn 0;\n \t}\n \n \tif (opt->recursive && S_ISDIR(mode1)) {\n \t\tint retval;\n-\t\tchar *newbase = malloc_base(base, path1, pathlen1);\n+\t\tchar *newbase = malloc_base(base, baselen, path1, pathlen1);\n \t\tif (opt->tree_in_recursive)\n \t\t\topt->change(opt, mode1, mode2,\n \t\t\t\t sha1, sha2, base, path1);\n@@ -67,20 +66,20 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const\n \treturn 0;\n }\n \n-static int interesting(struct tree_desc *desc, const char *base, struct diff_options *opt)\n+static int interesting(struct tree_desc *desc, const char *base, int baselen, struct diff_options *opt)\n {\n \tconst char *path;\n+\tconst unsigned char *sha1;\n \tunsigned mode;\n \tint i;\n-\tint baselen, pathlen;\n+\tint pathlen;\n \n \tif (!opt->nr_paths)\n \t\treturn 1;\n \n-\t(void)tree_entry_extract(desc, &path, &mode);\n+\tsha1 = tree_entry_extract(desc, &path, &mode);\n \n-\tpathlen = strlen(path);\n-\tbaselen = strlen(base);\n+\tpathlen = tree_entry_len(path, sha1);\n \n \tfor (i=0; i < opt->nr_paths; i++) {\n \t\tconst char *match = opt->paths[i];\n@@ -121,18 +120,18 @@ static int interesting(struct tree_desc *desc, const char *base, struct diff_opt\n }\n \n /* A whole sub-tree went away or appeared */\n-static void show_tree(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base)\n+static void show_tree(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base, int baselen)\n {\n \twhile (desc->size) {\n-\t\tif (interesting(desc, base, opt))\n-\t\t\tshow_entry(opt, prefix, desc, base);\n+\t\tif (interesting(desc, base, baselen, opt))\n+\t\t\tshow_entry(opt, prefix, desc, base, baselen);\n \t\tupdate_tree_entry(desc);\n \t}\n }\n \n /* A file entry went away or appeared */\n static void show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc,\n-\t\t const char *base)\n+\t\t const char *base, int baselen)\n {\n \tunsigned mode;\n \tconst char *path;\n@@ -140,7 +139,8 @@ static void show_entry(struct diff_options *opt, const char *prefix, struct tree\n \n \tif (opt->recursive && S_ISDIR(mode)) {\n \t\tenum object_type type;\n-\t\tchar *newbase = malloc_base(base, path, strlen(path));\n+\t\tint pathlen = tree_entry_len(path, sha1);\n+\t\tchar *newbase = malloc_base(base, baselen, path, pathlen);\n \t\tstruct tree_desc inner;\n \t\tvoid *tree;\n \n@@ -149,7 +149,7 @@ static void show_entry(struct diff_options *opt, const char *prefix, struct tree\n \t\t\tdie(\"corrupt tree sha %s\", sha1_to_hex(sha1));\n \n \t\tinner.buf = tree;\n-\t\tshow_tree(opt, prefix, &inner, newbase);\n+\t\tshow_tree(opt, prefix, &inner, newbase, baselen + 1 + pathlen);\n \n \t\tfree(tree);\n \t\tfree(newbase);\n@@ -160,26 +160,28 @@ static void show_entry(struct diff_options *opt, const char *prefix, struct tree\n \n int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)\n {\n+\tint baselen = strlen(base);\n+\n \twhile (t1->size | t2->size) {\n-\t\tif (opt->nr_paths && t1->size && !interesting(t1, base, opt)) {\n+\t\tif (opt->nr_paths && t1->size && !interesting(t1, base, baselen, opt)) {\n \t\t\tupdate_tree_entry(t1);\n \t\t\tcontinue;\n \t\t}\n-\t\tif (opt->nr_paths && t2->size && !interesting(t2, base, opt)) {\n+\t\tif (opt->nr_paths && t2->size && !interesting(t2, base, baselen, opt)) {\n \t\t\tupdate_tree_entry(t2);\n \t\t\tcontinue;\n \t\t}\n \t\tif (!t1->size) {\n-\t\t\tshow_entry(opt, \"+\", t2, base);\n+\t\t\tshow_entry(opt, \"+\", t2, base, baselen);\n \t\t\tupdate_tree_entry(t2);\n \t\t\tcontinue;\n \t\t}\n \t\tif (!t2->size) {\n-\t\t\tshow_entry(opt, \"-\", t1, base);\n+\t\t\tshow_entry(opt, \"-\", t1, base, baselen);\n \t\t\tupdate_tree_entry(t1);\n \t\t\tcontinue;\n \t\t}\n-\t\tswitch (compare_tree_entry(t1, t2, base, opt)) {\n+\t\tswitch (compare_tree_entry(t1, t2, base, baselen, opt)) {\n \t\tcase -1:\n \t\t\tupdate_tree_entry(t1);\n \t\t\tcontinue;\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 70f8999..a4a4e2a 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -32,7 +32,7 @@ static void entry_clear(struct name_entry *a)\n static void entry_extract(struct tree_desc *t, struct name_entry *a)\n {\n \ta->sha1 = tree_entry_extract(t, &a->path, &a->mode);\n-\ta->pathlen = strlen(a->path);\n+\ta->pathlen = tree_entry_len(a->path, a->sha1);\n }\n \n void update_tree_entry(struct tree_desc *desc)\n@@ -169,7 +169,7 @@ static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char\n \n \t\tsha1 = tree_entry_extract(t, &entry, mode);\n \t\tupdate_tree_entry(t);\n-\t\tentrylen = strlen(entry);\n+\t\tentrylen = tree_entry_len(entry, sha1);\n \t\tif (entrylen > namelen)\n \t\t\tcontinue;\n \t\tcmp = memcmp(name, entry, entrylen);\ndiff --git a/tree-walk.h b/tree-walk.h\nindex e57befa..a0d7afd 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -13,6 +13,11 @@ struct name_entry {\n \tint pathlen;\n };\n \n+static inline int tree_entry_len(const char *name, const unsigned char *sha1)\n+{\n+\treturn (char *)sha1 - (char *)name - 1;\n+}\n+\n void update_tree_entry(struct tree_desc *);\n const unsigned char *tree_entry_extract(struct tree_desc *, const char **, unsigned int *);\n \n"},{"id":"37352","messageId":"Pine.LNX.4.64.0703172013340.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"alpine.LFD.0.83.0703172228220.18328@xanadu.home","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-18T03:31:12Z","receivedAt":"2007-03-18T03:31:12Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 17 Mar 2007, Nicolas Pitre wrote:\n> \n> Sure. But at this point the reference to compare GIT performance \n> against might be GIT itself. And while 1 second is really nice in this \n> case, there are some repos where it could be (and has already been \n> reported to be) much more.\n\nI'd still like to see the KDE repo, that thing went quiet after it was \nsupposed to hit sneaker-net..\n\nIf it was 30 seconds before to do a \"git log\" for some individual file, \nafter the recent optimizations it should hopefully be down to 10. And I \nagree that I might be more motivated to try to get it down further if I \ncould just find a repository where it's that much. \n\nRight now I can can do a \"git log\" on any file in the kernel archive in \nunder a second (well, when I say \"any file\", I started with a script, but \nwith 22 thousand files I didn't bother to run it for all that long, so I \nended up testing a few random files in addition to the first few hundred \nfiles of \"git ls-files\", and they are all well under a second).\n\nAnd that's without the \"git diff --quiet\" thing that is still in \"next\", \nand that cut down some of the overhead for other reasons (although I \nsuspect the effect of that will be less when combined with my patches \nsince the stuff it cut down I probably cut down even more).\n\nI really suspect you'll have a hard time beating \"normal\" git with the \npatches I sent out. I'm sure it's quite possible - don't get me wrong - I \njust suspect it won't be spectacular, and it will be a lot of work.\n\n\t\tLinus\n"},{"id":"37354","messageId":"Pine.LNX.4.64.0703180517360.24626@beast.quantumfyre.co.uk","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703172013340.6730@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2007-03-18T05:30:01Z","receivedAt":"2007-03-18T05:30:01Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Sat, 17 Mar 2007, Linus Torvalds wrote:\n\n> On Sat, 17 Mar 2007, Nicolas Pitre wrote:\n>>\n>> Sure. But at this point the reference to compare GIT performance\n>> against might be GIT itself. And while 1 second is really nice in this\n>> case, there are some repos where it could be (and has already been\n>> reported to be) much more.\n>\n> I'd still like to see the KDE repo, that thing went quiet after it was\n> supposed to hit sneaker-net..\n>\n> If it was 30 seconds before to do a \"git log\" for some individual file,\n> after the recent optimizations it should hopefully be down to 10. And I\n> agree that I might be more motivated to try to get it down further if I\n> could just find a repository where it's that much.\n\nIn my test repository (which emulates a real repository in terms of \napproximate size in terms of commits, branches and tags) \"git log f12000\" \ntakes about 15m (using 1.5.0.4). After applying patches 1/2 and 2/2 on \ntop of master I get ~3m50s. With 3/2 as well it goes down a bit more to \n~3m20s.\n\nI've attached the script that generated the repository in case you feel \nthe urge to try some move time shaving exercises ... ;)\n\n(This is a rather unrealistic repository consisting of a long series of \ncommits of new binary files, but I don't have access to the repository \nthat is being approximated until I get back to work on Monday ...)\n\n-- \nJulian\n\n ---\nThat must be wonderful: I don't understand it at all.\n \t\t-- Moliere\n\n#!/bin/bash\n\n# no. of commits branches and tags to make\ncommits=25000;\nbranches=900;\ntags=8000;\n\n# create a new file of this size (kb) for each commit\ncommit_size=102;\nbs=1024;\n\nlarge=$1;\n\n((bg = $commits / $branches));\n((tg = $commits / $tags));\n\necho \"creating $large\";\nmkdir $large;\ncd $large;\n\ngit init-db;\n\ni=0\nwhile [ $i -lt $commits ]; do\n dd if=/dev/urandom of=f$i bs=${bs} count=${commit_size} > /dev/null 2>&1\n\n git add f$i;\n git commit -m \"add t$i\";\n\n ((ig = $i % $tg));\n if [ $ig -eq 0 ]; then\n git tag t$i;\n echo -n \"t\";\n fi\n\n ((ig = $i % $bg));\n if [ $ig -eq 0 ]; then\n git branch b$i;\n echo -n \"b\";\n fi\n\n echo -n \"$i \";\n ((i = $i + 1))\ndone\n\necho;\necho \"complete.\";\n\n"},{"id":"37356","messageId":"45FCDC0B.1090506@qumranet.com","threadId":"7262","inReplyTo":"118833cc0703171814n4e56ab9fwfaaea81c903ae235@mail.gmail.com","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Avi Kivity","fromEmail":"avi@qumranet.com","sentAt":"2007-03-18T06:28:27Z","receivedAt":"2007-03-18T06:28:27Z","isPatch":true,"sender":{"key":"avi@qumranet.com","avatar":null},"body":"Morten Welinder wrote:\n>> samples % app name symbol name\n>> 41527 15.6550 git strlen\n>\n> Almost 16% in strlen? Ugh!\n>\n> That's a lot of strings, or perhaps very long strings. Or a profiling \n> bug.\n>\n\nOr maybe strlen() is the first function to touch the page/cacheline.\n\n\n-- \nDo not meddle in the internals of kernels, for they are subtle and quick to panic.\n"},{"id":"37359","messageId":"7vps77ngcd.fsf@assigned-by-dhcp.cox.net","threadId":"7262","inReplyTo":"alpine.LFD.0.83.0703172053020.18328@xanadu.home","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-18T07:47:14Z","receivedAt":"2007-03-18T07:47:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> A malloc() + memcpy() will always be faster than mmap() + malloc() + \n> inflate(). If the data is already there it is certainly better to copy \n> it straight away.\n\nI do not know if there is mmap() cost involved, but you are\ncorrect to point out that my aversion to malloc() cost was\nunfounded. We need to allocate anyway, and memcpy() should of\ncourse be cheaper than inflate().\n\n> With the patch below I can do 'git log drivers/scsi/ > /dev/null' about \n> 7% faster. I bet it might be even more on those platforms with bad \n> mmap() support.\n\nWonderful. I was going to nitpick but you even took care of the\nconvention of returning a buffer with one extra byte that\nterminates the contents with NUL. Perfect.\n"},{"id":"37363","messageId":"7v8xdunavr.fsf@assigned-by-dhcp.cox.net","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703171949190.6730@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-18T09:45:12Z","receivedAt":"2007-03-18T09:45:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> This shaves off another ~5-10% from some loads that are very tree \n> intensive (notably doing commit filtering by a pathspec).\n>\n> Signed-off-by: Linus Torvalds \"\n\nWith your 256-entry cache, Nico's reusing objects out of delta\nbase cache, and this strlen() patch\n\n\tgit blame -C block/ll_rw_blk.c\n\ngets these numbers:\n\n(v1.5.0)\n14.71user 0.26system 0:15.07elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+93622minor)pagefaults 0swaps\n\n(master + three patches)\n8.94user 0.14system 0:09.10elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+40075minor)pagefaults 0swaps\n\nJust for fun, these are the same for the kernel history with tglx-history \nrepository's history grafted behind it, i.e. with this grafts file:\n\n$ cat .git/info/grafts\n1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 e7e173af42dbf37b1d946f9ee00219cb3b2bea6a\n\n(v1.5.0)\n73.80user 2.57system 1:16.40elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+773077minor)pagefaults 0swaps\n\n(master + three patches)\n65.14user 0.40system 1:05.55elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+125052minor)pagefaults 0swaps\n\nIn either case, it is showing drastic reduction of minor faults.\n"},{"id":"37367","messageId":"200703181153.59768.robin.rosenberg.lists@dewire.com","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703172013340.6730@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg.lists@dewire.com","sentAt":"2007-03-18T10:53:58Z","receivedAt":"2007-03-18T10:53:58Z","isPatch":true,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"söndag 18 mars 2007 04:31 skrev Linus Torvalds:\n> I'd still like to see the KDE repo, that thing went quiet after it was \n> supposed to hit sneaker-net..\n> \n> If it was 30 seconds before to do a \"git log\" for some individual file, \n> after the recent optimizations it should hopefully be down to 10. And I \n> agree that I might be more motivated to try to get it down further if I \n> could just find a repository where it's that much. \n\nI don't have the KDE repo, but I do have an Eclipse import. Without your\npatches I get (hot cache)\n\n# time git log -- org.eclipse.core.resources/src/org/eclipse/core/resources/ >/dev/null\n65.10user 0.50system 1:12.44elapsed 90%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+80242minor)pagefaults 0swaps\n\nWith patch 1&2 (hot cache)\n\n# time ~/SW/GIT/git-log -- org.eclipse.core.resources/src/org/eclipse/core/resources/ >/dev/null\n27.51user 0.21system 0:28.23elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+80266minor)pagefaults 0swaps\n\nThat's quite an improvement The eclipse repo is about 140k commits in the master branch and \nhas a 3GB pack file (fromcvs import). \n\n-- robin\n"},{"id":"37378","messageId":"Pine.LNX.4.64.0703180848580.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"7v8xdunavr.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-18T15:54:03Z","receivedAt":"2007-03-18T15:54:03Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 18 Mar 2007, Junio C Hamano wrote:\n> \n> \tgit blame -C block/ll_rw_blk.c\n> \n> Just for fun, these are the same for the kernel history with tglx-history \n> repository's history grafted behind it, i.e. with this grafts file:\n> \n> $ cat .git/info/grafts\n> 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 e7e173af42dbf37b1d946f9ee00219cb3b2bea6a\n> \n> (v1.5.0)\n> 73.80user 2.57system 1:16.40elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n> 0inputs+0outputs (0major+773077minor)pagefaults 0swaps\n> \n> (master + three patches)\n> 65.14user 0.40system 1:05.55elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n> 0inputs+0outputs (0major+125052minor)pagefaults 0swaps\n> \n> In either case, it is showing drastic reduction of minor faults.\n\nThat's an interesting test-case (and I get 53 seconds, nyaah, nyaah ;)\n\nHowever, it's almost totally *not* about object access any more with my \npatches. All the top profiling hits are about generating the patches and \nassigning blame:\n\n\tsamples % image name app name symbol name\n\t470352 15.5813 git git xdl_hash_record\n\t298683 9.8944 git git cmp_suspect\n\t225156 7.4587 git git assign_blame\n\t221308 7.3312 libc-2.5.so libc-2.5.so memcpy\n\t177621 5.8840 libc-2.5.so libc-2.5.so memchr\n\t163571 5.4186 vmlinux vmlinux __copy_user_nocache\n\t129301 4.2833 git git xdl_prepare_ctx\n\t99009 3.2799 libc-2.5.so libc-2.5.so _int_malloc\n\t83899 2.7793 git git xdiff_outf\n\t80588 2.6696 libz.so.1.2.3 libz.so.1.2.3 (no symbols)\n\t..\n\nso as you can see, libz is down in the 2.5% range, and strlen and the tree \naccessor functions are totally un the noise. \n\nSo it looks like it *used* to be somewhat of a problem (the object access \nitself must have been about 10 seconds, since that got shaved off the \ntime), but realistically, if you want to speed up \"git blame\", we can \ntotally ignore the git object data structures, an dconcentrate on xdiff \nand on blame itself (cmp_suspect and assign_blame probably have some nasty \nO(n^2) behaviour or something like that, that could hopefully be fixed \nfairly easily. The xdl hashing is a different thing, and I don't think \nit's necessarily easy to fix that one..)\n\n\t\t\tLinus\n"},{"id":"37379","messageId":"Pine.LNX.4.64.0703180854470.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703180848580.6730@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-18T15:57:33Z","receivedAt":"2007-03-18T15:57:33Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 18 Mar 2007, Linus Torvalds wrote:\n> \n> That's an interesting test-case (and I get 53 seconds, nyaah, nyaah ;)\n\nBtw, it's also an example of why the incremental blame is so much nicer.\n\nNo way would I want to wait 53 seconds to get the whole blame. But doing\n\n\tgit gui blame HEAD block/ll_rw_blk.c\n\n(the \"git gui\" command line is a bit unwieldly) you get something quite \nusable!\n\nOf course, the git gui blame colorization is clearly done by somebody who \nis still actively popping LSD with both fists and didn't realize that the \n60's are long done, but that's another issue.\n\n\t\tLinus\n"},{"id":"37384","messageId":"Pine.LNX.4.64.0703181012520.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703180517360.24626@beast.quantumfyre.co.uk","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-18T17:23:27Z","receivedAt":"2007-03-18T17:23:27Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 18 Mar 2007, Julian Phillips wrote:\n> \n> (This is a rather unrealistic repository consisting of a long series of\n> commits of new binary files, but I don't have access to the repository that is\n> being approximated until I get back to work on Monday ...)\n\nThis is a *horrible* test repo.\n\nIs this actually really trying to approximate anything you work with? If \nso, please check whether you have cyanide or some other effective poison \nto kill all your cow-orkers - it's really doing them a favor - and then do \nthe honorable thing yourself? Use something especially painful on whoever \ncame up with the idea to track 25000 files in a single directory.\n\nI'll see what the profile is, but even without the repo full generated \nyet, I can already tell you that you should *not* put tens of thousands of \nfiles in a single directory like this.\n\nIt's not only usually horribly bad quite independently of any SCM issues \n(ie most filesystems will have some bad performance behaviour with things \nlike this - if only because \"readdir()\" will inevitably be slow).\n\nAnd for git it means that you lose all ability to efficiently prune away \nthe parts of the tree that you don't care about. git will always end up \nworking with a full linear filemanifest instead of a nice collection of \nrecursive trees, and a lot of the nice tree-walking optimizations that git \nhas will just end up being no-ops: each tree is always one *huge* \nmanifest.\n\nSo it's not that git cannot handle it, it's that a lot of the nice things \nthat make git really efficient simply won't trigger for your repository.\n\nIn short: avoiding tens of thousands of files in a single directory is \n*always* a good idea. With or without git.\n\n(Again, SCM's that are really just \"one file at a time\" like CVS, \nwon't care as much. They never really track all files anyway, so while \nthey are limited by potential filesystem performance bottlenecks, they \nwon't have the fundamental issue of tracking 25,000 files..)\n\n\t\tLinus\n"},{"id":"37386","messageId":"Pine.LNX.4.64.0703181033060.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"200703181153.59768.robin.rosenberg.lists@dewire.com","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-18T17:34:51Z","receivedAt":"2007-03-18T17:34:51Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 18 Mar 2007, Robin Rosenberg wrote:\n> \n> I don't have the KDE repo, but I do have an Eclipse import. \n> \n> The eclipse repo is about 140k commits in the master branch and \n> has a 3GB pack file (fromcvs import). \n\nDo you happen to have a fast internet connection that you can expose this \nthing on?\n\n3GB will take me a while to download, but it sounds like a great \ntest-case. A 3GB pack-file is what we're supposed to be able to handle \nfairly comfortably right now, so it sounds like the ideal project to do \nperformance testing on. \n\n\t\tLinus\n"},{"id":"37388","messageId":"200703181929.58278.robin.rosenberg.lists@dewire.com","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703181033060.6730@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg.lists@dewire.com","sentAt":"2007-03-18T18:29:57Z","receivedAt":"2007-03-18T18:29:57Z","isPatch":true,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"söndag 18 mars 2007 18:34 skrev Linus Torvalds:\n> \n> On Sun, 18 Mar 2007, Robin Rosenberg wrote:\n> > \n> > I don't have the KDE repo, but I do have an Eclipse import. \n> > \n> > The eclipse repo is about 140k commits in the master branch and \n> > has a 3GB pack file (fromcvs import). \n> \n> Do you happen to have a fast internet connection that you can expose this \n> thing on?\n\nNot that fast and it would take me quite a time to move the files to a public\nlocation (it's on my laptop). I'd rather dump it somewhere directly if someone can\nprovide me with some suitable coordinates.\n\n-- robin\n"},{"id":"37402","messageId":"20070318212540.GA20658@spearce.org","threadId":"7262","inReplyTo":"200703181929.58278.robin.rosenberg.lists@dewire.com","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-18T21:25:40Z","receivedAt":"2007-03-18T21:25:40Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Robin Rosenberg wrote:\n> söndag 18 mars 2007 18:34 skrev Linus Torvalds:\n> > \n> > On Sun, 18 Mar 2007, Robin Rosenberg wrote:\n> > > \n> > > I don't have the KDE repo, but I do have an Eclipse import. \n> > > \n> > > The eclipse repo is about 140k commits in the master branch and \n> > > has a 3GB pack file (fromcvs import). \n> > \n> > Do you happen to have a fast internet connection that you can expose this \n> > thing on?\n> \n> Not that fast and it would take me quite a time to move the files to a public\n> location (it's on my laptop). I'd rather dump it somewhere directly if someone can\n> provide me with some suitable coordinates.\n\nI'd like to get a copy of one of these big repos too (KDE, Eclipse).\n\nI probably could get a DVD onto both Internet and Internet2 from a\nfast enough pipe that a few folks (e.g. Linus, Nico, Junio) could\npull it down, but I can't offer a public distribution point for\nthe world.\n\n-- \nShawn.\n"},{"id":"37403","messageId":"20070318213807.GB20658@spearce.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703180854470.6730@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-18T21:38:07Z","receivedAt":"2007-03-18T21:38:07Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Linus Torvalds wrote:\n> Btw, it's also an example of why the incremental blame is so much nicer.\n> \n> No way would I want to wait 53 seconds to get the whole blame. But doing\n> \n> \tgit gui blame HEAD block/ll_rw_blk.c\n> \n> (the \"git gui\" command line is a bit unwieldly) you get something quite \n> usable!\n> \n> Of course, the git gui blame colorization is clearly done by somebody who \n> is still actively popping LSD with both fists and didn't realize that the \n> 60's are long done, but that's another issue.\n\n:-)\n\ngit-gui is open source. I'd be happy to take a patch. Or,\nsince that is horribly messy Tcl/Tk code, just a better color\nsuggestion. :-)\n\n-- \nShawn.\n"},{"id":"37406","messageId":"Pine.LNX.4.64.0703181440140.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"20070318213807.GB20658@spearce.org","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-18T21:48:17Z","receivedAt":"2007-03-18T21:48:17Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 18 Mar 2007, Shawn O. Pearce wrote:\n> Linus Torvalds wrote:\n> > \n> > Of course, the git gui blame colorization is clearly done by somebody who \n> > is still actively popping LSD with both fists and didn't realize that the \n> > 60's are long done, but that's another issue.\n> \n> :-)\n> \n> git-gui is open source. I'd be happy to take a patch. Or,\n> since that is horribly messy Tcl/Tk code, just a better color\n> suggestion. :-)\n\nYeah, the Tcl/Tk part means that I take one look and decide that I have \nabsolutely zero clue..\n\nAlso, I'm not entirely sure what the \"right\" color is, but the changing \ncolors do confuse me. Also, maybe I'm some kind of white suburban \nhouse-wife or something, but I prefer calmer pastel colors over the bright \nones you've selected.\n\nI would suggest:\n\n - some special color for \"currently selected\" (which defaults to being \n the first one coming out of the blame thing, of course). \n\n I'd suggest \"black text on pale green background\", but that may be just \n me. Patricia calls the current color \"hot pink\", and maybe that's \n appropriate for a certain segment of the population, but I'm not sure I \n want to even *meet* that segment ;)\n\n - some *stable* graduated color for the rest. I don't think it \n necessarily needs to be \"older\" vs \"newer\", and in fact I'd suggest \n just two slightly different shades of gray for the background - just \n pick alternating shades for each blame entry that comes in (and leave \n un-blamed lines white).\n\nThe flickering just makes me go \"ooh, I'm really happy I don't have \nepilepsy, because otherwise I'd be writhing on the floor every time I \ntried to use this tool\".\n\n\t\t\tLinus\n"},{"id":"37494","messageId":"45FE8D1E.6040408@sinister.cz","threadId":"7262","inReplyTo":"200703181929.58278.robin.rosenberg.lists@dewire.com","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"David Brodsky","fromEmail":"trekie@sinister.cz","sentAt":"2007-03-19T13:16:14Z","receivedAt":"2007-03-19T13:16:14Z","isPatch":true,"sender":{"key":"trekie@sinister.cz","avatar":null},"body":"Robin Rosenberg wrote:\n> söndag 18 mars 2007 18:34 skrev Linus Torvalds:\n>> On Sun, 18 Mar 2007, Robin Rosenberg wrote:\n>>> I don't have the KDE repo, but I do have an Eclipse import. \n>>>\n>>> The eclipse repo is about 140k commits in the master branch and \n>>> has a 3GB pack file (fromcvs import). \n>> Do you happen to have a fast internet connection that you can expose this \n>> thing on?\n> \n> Not that fast and it would take me quite a time to move the files to a public\n> location (it's on my laptop). I'd rather dump it somewhere directly if someone can\n> provide me with some suitable coordinates.\n\nI have access to a server with enough disk space and its internet\nconnection should be something like 10 Mbps (or even faster). I can\nprovide you anonymous ftp access for upload/download (temporarily) and\nhttp for download (permanent).\n\nOr you can send me a dvd, but that would take some time (at least 1 week\nbecause I'm in the Czech Republic and I don't expect that you are\nanywhere near...) and I don't know if postal service can handle such\nfragile things like dvds.\n\nThis is the smallest thing I can do for you...\n\n\nDavid Brodsky\n"},{"id":"37574","messageId":"Pine.LNX.4.63.0703200400230.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703180848580.6730@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-20T03:05:10Z","receivedAt":"2007-03-20T03:05:10Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 18 Mar 2007, Linus Torvalds wrote:\n\n> All the top profiling hits are about generating the patches and \n> assigning blame:\n> \n> \tsamples % image name app name symbol name\n> \t470352 15.5813 git git xdl_hash_record\n\nI felt a little left out in all that performance slashing, and so I \nthought maybe, just maybe, a small change in xdl_hash_record() can do \nwonders (since it _is_ really simple, but still takes almost a 6th of the \nCPU time). I don't have a proper test case setup, so maybe you want to try \nthis:\n\n-- snipsnap --\n[PATCH] xdiff/xutils.c(xdl_hash_record): factor out whitespace handling\n\nSince in at least one use case, xdl_hash_record() takes over 15% of the\nCPU time, it makes sense to even micro-optimize it. For many cases, no\nwhitespace special handling is needed, and in these cases we should not\neven bother to check for whitespace in _every_ iteration of the loop.\n\nSigned-off-by: Johannes Schindelin \n\n---\n\n\tPlease do not consider this patch _unless_ it is proven to enhance \n\tthe profile statistics substantially.\n\n xdiff/xutils.c | 22 ++++++++++++++++++++--\n 1 files changed, 20 insertions(+), 2 deletions(-)\n\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex 3653864..bf91c0f 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -236,12 +236,13 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)\n \treturn 0;\n }\n \n-unsigned long xdl_hash_record(char const **data, char const *top, long flags) {\n+static unsigned long xdl_hash_record_with_whitespace(char const **data,\n+\t\tchar const *top, long flags) {\n \tunsigned long ha = 5381;\n \tchar const *ptr = *data;\n \n \tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n-\t\tif (isspace(*ptr) && (flags & XDF_WHITESPACE_FLAGS)) {\n+\t\tif (isspace(*ptr)) {\n \t\t\tconst char *ptr2 = ptr;\n \t\t\twhile (ptr + 1 < top && isspace(ptr[1])\n \t\t\t\t\t&& ptr[1] != '\\n')\n@@ -270,6 +271,23 @@ unsigned long xdl_hash_record(char const **data, char const *top, long flags) {\n }\n \n \n+unsigned long xdl_hash_record(char const **data, char const *top, long flags) {\n+\tunsigned long ha = 5381;\n+\tchar const *ptr = *data;\n+\n+\tif (flags & XDF_WHITESPACE_FLAGS)\n+\t\treturn xdl_hash_record_with_whitespace(data, top, flags);\n+\n+\tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n+\t\tha += (ha << 5);\n+\t\tha ^= (unsigned long) *ptr;\n+\t}\n+\t*data = ptr < top ? ptr + 1: ptr;\n+\n+\treturn ha;\n+}\n+\n+\n unsigned int xdl_hashbits(unsigned int size) {\n \tunsigned int val = 1, bits = 0;\n \n"},{"id":"37575","messageId":"7v3b40d2os.fsf@assigned-by-dhcp.cox.net","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703180848580.6730@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-20T03:16:51Z","receivedAt":"2007-03-20T03:16:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> So it looks like it *used* to be somewhat of a problem (the object access \n> itself must have been about 10 seconds, since that got shaved off the \n> time), but realistically, if you want to speed up \"git blame\", we can \n> totally ignore the git object data structures, an dconcentrate on xdiff \n> and on blame itself (cmp_suspect and assign_blame probably have some nasty \n> O(n^2) behaviour or something like that,...\n\nWith this stupidity-removal patch, it gets down to 7.80user from\n8.72user (comparable number of minor faults) for blaming\nblock/ll_rw_blk.c (without tglx grafts)\n\ndiff --git a/builtin-blame.c b/builtin-blame.c\nindex b51cdc7..104521e 100644\n--- a/builtin-blame.c\n+++ b/builtin-blame.c\n@@ -182,9 +182,8 @@ struct scoreboard {\n \n static int cmp_suspect(struct origin *a, struct origin *b)\n {\n-\tint cmp = hashcmp(a->commit->object.sha1, b->commit->object.sha1);\n-\tif (cmp)\n-\t\treturn cmp;\n+\tif (a->commit != b->commit)\n+\t\treturn 1;\n \treturn strcmp(a->path, b->path);\n }\n \n"},{"id":"37576","messageId":"20070320032947.GA29145@spearce.org","threadId":"7262","inReplyTo":"Pine.LNX.4.63.0703200400230.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-20T03:29:47Z","receivedAt":"2007-03-20T03:29:47Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Johannes Schindelin wrote:\n> On Sun, 18 Mar 2007, Linus Torvalds wrote:\n> \n> > All the top profiling hits are about generating the patches and \n> > assigning blame:\n> > \n> > \tsamples % image name app name symbol name\n> > \t470352 15.5813 git git xdl_hash_record\n> \n> I felt a little left out in all that performance slashing, and so I \n> thought maybe, just maybe, a small change in xdl_hash_record() can do \n> wonders (since it _is_ really simple, but still takes almost a 6th of the \n> CPU time). I don't have a proper test case setup, so maybe you want to try \n> this:\n> \n> -- snipsnap --\n> [PATCH] xdiff/xutils.c(xdl_hash_record): factor out whitespace handling\n> \n> Since in at least one use case, xdl_hash_record() takes over 15% of the\n> CPU time, it makes sense to even micro-optimize it. For many cases, no\n> whitespace special handling is needed, and in these cases we should not\n> even bother to check for whitespace in _every_ iteration of the loop.\n> \n> Signed-off-by: Johannes Schindelin \n> \n> ---\n> \n> \tPlease do not consider this patch _unless_ it is proven to enhance \n> \tthe profile statistics substantially.\n\nThis is a massive difference for me. I ran it on git-gui.sh in\nthe git-gui repository - this is a 6000 line file that has a lot of\nrevisions, and has been renamed a few times. I applied the patch on\ntop of current 'master' (v1.5.1-rc1), so I was testing with Linus'\ndelta_base_cache.\n\n# stock v1.5.1-rc1\n$ for a in 1 2 3 4 5;do /usr/bin/time ../lt-blame blame --incremental HEAD git-gui.sh >/dev/null;done\n 6.27 real 5.31 user 0.55 sys\n 6.40 real 5.32 user 0.55 sys\n 6.33 real 5.33 user 0.53 sys\n 6.67 real 5.32 user 0.55 sys\n 6.18 real 5.31 user 0.53 sys\n\n# with the above patch\n$ for a in 1 2 3 4 5;do /usr/bin/time ../js-blame blame --incremental HEAD git-gui.sh >/dev/null;done\n 3.57 real 2.87 user 0.51 sys\n 3.58 real 2.87 user 0.51 sys\n 3.53 real 2.86 user 0.52 sys\n 3.61 real 2.86 user 0.51 sys\n 3.64 real 2.87 user 0.52 sys\n\nFor the record, both versions did produce identical output.\n\nGiven how small of a change it is, and how much of an improvement\nit made, I say apply it.\n\n-- \nShawn.\n"},{"id":"37578","messageId":"20070320034020.GB29145@spearce.org","threadId":"7262","inReplyTo":"20070320032947.GA29145@spearce.org","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-20T03:40:20Z","receivedAt":"2007-03-20T03:40:20Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"\"Shawn O. Pearce\" wrote:\n> Johannes Schindelin wrote:\n> > -- snipsnap --\n> > [PATCH] xdiff/xutils.c(xdl_hash_record): factor out whitespace handling\n...\n> > ---\n> > \n> > \tPlease do not consider this patch _unless_ it is proven to enhance \n> > \tthe profile statistics substantially.\n> \n> This is a massive difference for me.\n...\n> # stock v1.5.1-rc1\n> $ for a in 1 2 3 4 5;do /usr/bin/time ../lt-blame blame --incremental HEAD git-gui.sh >/dev/null;done\n> 6.27 real 5.31 user 0.55 sys\n> 6.40 real 5.32 user 0.55 sys\n> 6.33 real 5.33 user 0.53 sys\n> 6.67 real 5.32 user 0.55 sys\n> 6.18 real 5.31 user 0.53 sys\n> \n> # with the above patch\n> $ for a in 1 2 3 4 5;do /usr/bin/time ../js-blame blame --incremental HEAD git-gui.sh >/dev/null;done\n> 3.57 real 2.87 user 0.51 sys\n> 3.58 real 2.87 user 0.51 sys\n> 3.53 real 2.86 user 0.52 sys\n> 3.61 real 2.86 user 0.51 sys\n> 3.64 real 2.87 user 0.52 sys\n\nDrNick suggested on #git to try flipping the isspace test around.\nThis is a smaller change and generated the same ~3.60 seconds run\nas Dscho's patch. I like DrNick's version better. ;-)\n\n-->8--\n[PATCH] xdiff/xutils.c(xdl_hash_record): factor out whitespace handling\n\nSince in at least one use case, xdl_hash_record() takes over 15%\nof the CPU time, it makes sense to even micro-optimize it. For\nmany cases, no whitespace special handling is needed, and in these\ncases we should not even bother to check for whitespace in _every_\niteration of the loop.\n\nSigned-off-by: Johannes Schindelin \nSigned-off-by: Shawn O. Pearce \n---\n xdiff/xutils.c | 2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex 3653864..7b1f213 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -241,7 +241,7 @@ unsigned long xdl_hash_record(char const **data, char const *top, long flags) {\n \tchar const *ptr = *data;\n \n \tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n-\t\tif (isspace(*ptr) && (flags & XDF_WHITESPACE_FLAGS)) {\n+\t\tif ((flags & XDF_WHITESPACE_FLAGS) && isspace(*ptr)) {\n \t\t\tconst char *ptr2 = ptr;\n \t\t\twhile (ptr + 1 < top && isspace(ptr[1])\n \t\t\t\t\t&& ptr[1] != '\\n')\n-- \n1.5.1.rc1.595.gd1206\n\n-- \nShawn.\n"},{"id":"37579","messageId":"Pine.LNX.4.64.0703192052380.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"20070320034020.GB29145@spearce.org","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-20T04:11:08Z","receivedAt":"2007-03-20T04:11:08Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 19 Mar 2007, Shawn O. Pearce wrote:\n>\n> DrNick suggested on #git to try flipping the isspace test around.\n> This is a smaller change and generated the same ~3.60 seconds run\n> as Dscho's patch. I like DrNick's version better. ;-)\n\nFor me, the result seems to be in the noise.\n\nIt may be due to running on Core 2. It's not very sensitive to \nmicro-optimizations like this. It definitely makes sense to test the \n*stable* test first, since that will help branch prediction (the \n\"isspace()\" test is *not* very predictable), so I don't disagree with the \npatch, but I suspect it depends a lot on the microarchitecture just how \nmuch it matters.\n\nDo you perhaps have a P4? It has a very bad branch mispredict penalty, so \nputting the predictable branch first could explain the big difference you \nsee..\n\nDscho's bigger patch probably helps more on an in-order architecture, and \nshould be equally good on a P4 (or Opteron). On Core 2, neither of the \npatches seem to make a huge difference.\n\n\t\t\tLinus\n"},{"id":"37580","messageId":"20070320041843.GA29288@spearce.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703192052380.6730@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-20T04:18:43Z","receivedAt":"2007-03-20T04:18:43Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Linus Torvalds wrote:\n> On Mon, 19 Mar 2007, Shawn O. Pearce wrote:\n> >\n> > DrNick suggested on #git to try flipping the isspace test around.\n> > This is a smaller change and generated the same ~3.60 seconds run\n> > as Dscho's patch. I like DrNick's version better. ;-)\n> \n> For me, the result seems to be in the noise.\n> \n> It may be due to running on Core 2. It's not very sensitive to \n> micro-optimizations like this. It definitely makes sense to test the \n> *stable* test first, since that will help branch prediction (the \n> \"isspace()\" test is *not* very predictable), so I don't disagree with the \n> patch, but I suspect it depends a lot on the microarchitecture just how \n> much it matters.\n> \n> Do you perhaps have a P4? It has a very bad branch mispredict penalty, so \n> putting the predictable branch first could explain the big difference you \n> see..\n\nI tested both patches on a PowerPC G4. (Apple PowerBook, 1.5 GHz)\nRunning on Mac OS X 10.4.8.\n\nMight be more of a Linux<->Darwin thing; perhaps my isspace is\nsignificantly slower than yours is... after all my mmap runs\nlike a PC from the 1980s... ;-)\n\n-- \nShawn.\n"},{"id":"37581","messageId":"Pine.LNX.4.64.0703192116020.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"7v3b40d2os.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-20T04:31:57Z","receivedAt":"2007-03-20T04:31:57Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 19 Mar 2007, Junio C Hamano wrote:\n> \n> With this stupidity-removal patch, it gets down to 7.80user from\n> 8.72user (comparable number of minor faults) for blaming\n> block/ll_rw_blk.c (without tglx grafts)\n\nYeah, this one works for me too. Even more than for you. For me, \n\n\tgit blame --incremental -C HEAD block/ll_rw_blk.c\n\ntakes 6.71s (best of ten) normally, and 4.85 (best of ten again) with your \npatch and Nico's one-liner. In fact, that's a much bigger improvement than \nI would have expected from the profile, but it may be that you just cut \nthe data cache footprint down a lot, and thus made other things more \nefficient.\n\n(I just double-checked. Nico's one-liner does help, but not nearly as \nradically as it did for Nico. The \"best of ten\" with *just* Nico's \none-liner is 6.22 for me - better than before, but the combination of \nNico's patch and yours is much more dramatic).\n\nBtw, Dscho's slightly more invasive patch seems to *just* edge out Nico's \none-liner for me, with best-of-ten being 6.17s.\n\nThe winner is your patch *with* Dscho's slightly more invasive one: 4.69s.\n\nBut the difference between the numbers of Dscho's bigger patch and Nico's \none-liner really are totally in the noise. Dscho *just* wins the \nbest-of-ten both with and without your patch, but in both cases it's \n*way* in the noise. For example, while 4.69s was the best for your+Dscho \nin my testing, the full series was\n\n\t0:05.69\n\t0:04.69\n\t0:04.82\n\t0:04.97\n\t0:04.85\n\t0:05.88\n\t0:04.77\n\t0:04.69\n\t0:05.12\n\t0:04.98\n\nso the variability was big enough that I wouldn't say that 0.1s is really \nall that meaningful even for \"best of ten\". I didn't try to make the \nmachine totally quiescent, I've got xmms playing in the background etc..\n\nBut these kinds of things will definitely vary from machine to machine. \nIt's all good, though.\n\n\t\t\tLinus\n"},{"id":"37583","messageId":"20070320043902.GB29288@spearce.org","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703192116020.6730@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-20T04:39:02Z","receivedAt":"2007-03-20T04:39:02Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Linus Torvalds wrote:\n> Btw, Dscho's slightly more invasive patch seems to *just* edge out Nico's \n> one-liner for me, with best-of-ten being 6.17s.\n\nUh, instead of Nico here don't you mean DrNick on #git? He is in\nreal life Nicholas Miell. Google says he's somewhat active in the\nkernel world, so maybe you know him? ;-)\n\n-- \nShawn.\n"},{"id":"37584","messageId":"Pine.LNX.4.64.0703192132540.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"20070320041843.GA29288@spearce.org","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-20T04:45:38Z","receivedAt":"2007-03-20T04:45:38Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 20 Mar 2007, Shawn O. Pearce wrote:\n> \n> I tested both patches on a PowerPC G4. (Apple PowerBook, 1.5 GHz)\n> Running on Mac OS X 10.4.8.\n> \n> Might be more of a Linux<->Darwin thing; perhaps my isspace is\n> significantly slower than yours is... after all my mmap runs\n> like a PC from the 1980s... ;-)\n\nNo, we do a git-specific isspace().\n\nBut yeah, a G4 will explain the thing even more than a P4 would. The G4 \nreally isn't a very good uarch compared to the modern x86 ones. Not \naggressively out-of-order with deep instruction queues and I don't think \nit does basically any memop re-ordering at all. I know Apple used to claim \nthat they were the fastest PC around (both with the G4 and the G5), but \nlet's face it, they lied.\n\nThe closer to in-order you are, the more instruction scheduling in sw \ntends to matter.\n\n\t\tLinus\n"},{"id":"37587","messageId":"Pine.LNX.4.64.0703192154390.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"20070320043902.GB29288@spearce.org","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-20T04:57:02Z","receivedAt":"2007-03-20T04:57:02Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 20 Mar 2007, Shawn O. Pearce wrote:\n\n> Linus Torvalds wrote:\n> > Btw, Dscho's slightly more invasive patch seems to *just* edge out Nico's \n> > one-liner for me, with best-of-ten being 6.17s.\n> \n> Uh, instead of Nico here don't you mean DrNick on #git? He is in\n> real life Nicholas Miell. Google says he's somewhat active in the\n> kernel world, so maybe you know him? ;-)\n\nI actually meant you.\n\nFor some reason, I confuse you and Nico. I've done it several times, and \neven without any DrNick mention.\n\nTime to take my meds, \n\n\t\tLinus\n"},{"id":"37593","messageId":"7vhcsgbhav.fsf@assigned-by-dhcp.cox.net","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703192052380.6730@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Avoid unnecessary strlen() calls","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-20T05:44:08Z","receivedAt":"2007-03-20T05:44:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Dscho's bigger patch probably helps more on an in-order architecture, and \n> should be equally good on a P4 (or Opteron). On Core 2, neither of the \n> patches seem to make a huge difference.\n\nBecause hoisting stable test outside loop is always better for\nany architecture, I thought picking between Gitte and Gitney\npatches is a no brainer, and I didn't bother to compare-bench,\nbut I got curious.\n\n(plain)\n7.89user 0.15system 0:08.08elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+41608minor)pagefaults 0swaps\n7.93user 0.18system 0:08.14elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+41608minor)pagefaults 0swaps\n\n(gitte -- separate function for slow path)\n6.98user 0.18system 0:07.17elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+41606minor)pagefaults 0swaps\n7.14user 0.12system 0:07.26elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+41607minor)pagefaults 0swaps\n\n(gitney -- cheap test first before isspace)\n7.23user 0.18system 0:07.42elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+41608minor)pagefaults 0swaps\n7.32user 0.14system 0:07.48elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+41607minor)pagefaults 0swaps\n\nSo it does not seem to make much difference on Athlon 64x2 either.\n\nWill apply the \"stupid hashcmp() removal\" and Dscho's patch and\ncall it a day.\n"},{"id":"37600","messageId":"200703200735.41234.robin.rosenberg.lists@dewire.com","threadId":"7262","inReplyTo":"45FE8D1E.6040408@sinister.cz","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg.lists@dewire.com","sentAt":"2007-03-20T06:35:40Z","receivedAt":"2007-03-20T06:35:40Z","isPatch":true,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"Uploaded now.\n\nDavid Brodsky provides the final location.\n\nLinus: I noted a large extra file that I don't know where it is from. Seems to\nbe form the first convetsion. Perhaps you wont' need to download it: \n\nECLIPSE.git/.git/objects/pack_sETUPg\n\n-- robin\n"},{"id":"37610","messageId":"45FFA5CB.1060700@sinister.cz","threadId":"7262","inReplyTo":"200703200735.41234.robin.rosenberg.lists@dewire.com","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"David Brodsky","fromEmail":"trekie@sinister.cz","sentAt":"2007-03-20T09:13:47Z","receivedAt":"2007-03-20T09:13:47Z","isPatch":true,"sender":{"key":"trekie@sinister.cz","avatar":null},"body":"Robin Rosenberg wrote:\n> Uploaded now.\n> \n> David Brodsky provides the final location.\n\nAnonymous ftp at agnes.kajka.koleje.cuni.cz:10000 - it will stay up for\na while, but since it my desktop machine, I don't guarantee anything.\n\nAnd (hopefully) permanent http://steamer.kajka.koleje.cuni.cz/Eclipse\n\nEnjoy\n\nDavid\n"},{"id":"37653","messageId":"Pine.LNX.4.64.0703201922160.6730@woody.linux-foundation.org","threadId":"7262","inReplyTo":"45FFA5CB.1060700@sinister.cz","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-21T02:37:41Z","receivedAt":"2007-03-21T02:37:41Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 20 Mar 2007, David Brodsky wrote:\n> \n> And (hopefully) permanent http://steamer.kajka.koleje.cuni.cz/Eclipse\n\nOk, thanks, downloaded. Although the pack-file is just 1.7GB for me, not \n3.7 like somebody said.\n\nAnyway, doing a\n\n\tgit blame --incremental HEAD -- org.eclipse.debug.ui/plugin.xml > /dev/null\n\non that thing (picked a random file that got modified in a recent commit) \ntook something like 12 seconds, so this is certainly a perfectly fine \ntest-case.\n\nSadly, \"git-gui blame\" doesn't work in a bare git repository, so I had to \ndo an ugly\n\n\tln -s . .git\n\nto make git-gui happy, and that worked, and was pretty usable. Still, \n12seconds should be something we can improve on.\n\nAnd yeah, the profile is pretty horrid:\n\n\tsamples % app name symbol name\n\t70307 20.9412 libc-2.5.so strlen\n\t50925 15.1682 libz.so.1.2.3 (no symbols)\n\t24295 7.2364 git tree_entry_interesting\n\t19816 5.9023 libc-2.5.so memcpy\n\t19569 5.8287 git tree_entry_extract\n\t17693 5.2699 vmlinux memcpy_c\n\t17032 5.0730 git assign_blame\n\t16956 5.0504 git get_mode\n\t12401 3.6937 git get_origin\n\t11815 3.5191 git skip_uninteresting\n\t10449 3.1123 git update_tree_entry\n\t10359 3.0855 git find_pack_entry_one\n\t7946 2.3667 git cmp_suspect\n\t4572 1.3618 libc-2.5.so strncmp\n\t...\n\nso I guess we need to find some more strlen's to remove ;)\n\n\t\t\tLinus\n"},{"id":"37654","messageId":"alpine.LFD.0.83.0703202243530.18328@xanadu.home","threadId":"7262","inReplyTo":"Pine.LNX.4.64.0703201922160.6730@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Implement a simple delta_base cache","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-21T02:54:26Z","receivedAt":"2007-03-21T02:54:26Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 20 Mar 2007, Linus Torvalds wrote:\n\n> \n> \n> On Tue, 20 Mar 2007, David Brodsky wrote:\n> > \n> > And (hopefully) permanent http://steamer.kajka.koleje.cuni.cz/Eclipse\n> \n> Ok, thanks, downloaded. Although the pack-file is just 1.7GB for me, not \n> 3.7 like somebody said.\n\nThere is a 1.3GB garbage pack_sETUPg file in eclipse.git/objects/ laying \nthere, probably resulting from an interrupted index-pack, making the \nrepository needlessly bigger. It can be safely deleted.\n\nWe probably should make git-prune get rid of those automatically.\n\n\nNicolas\n"}]}