{"thread":{"id":"8935","subject":"[RFC] Dynamic window size on repack?","startedAt":"2007-07-08T21:16:06Z","lastAt":"2007-07-08T21:39:45Z","messageCount":4,"participants":["Brian Downing","Linus Torvalds","Dana How"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"46793","messageId":"20070708211606.GF4087@lavos.net","threadId":"8935","inReplyTo":null,"subject":"[RFC] Dynamic window size on repack?","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2007-07-08T21:16:06Z","receivedAt":"2007-07-08T21:16:06Z","isPatch":false,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"I have a CVS repository which is mostly sane, but has an approximately\n20MB RTF file that has two hundred revisions or so. (Thank you, Windows\nhelp.)\n\nNow, since this is old history, I want to make it as small as possible.\nThe only problem is that when I use high --window values for repack,\nit goes along swimmingly until it gets to this file, at which point\nmemory usage quickly rises to the point where I'm well into my swap file.\n\nI think what I'd like is an extra option to repack to limit window\nmemory usage. This would dynamically scale the window size down if it\ncan't fit within the limit, then scale it back up once you're off of the\nnasty file. This would let me repack my repository with --window=100\nand have it actually finish someday on the machines I have access to.\nThe big file may not be as efficiently packed as possible, but I can\nlive with that.\n\nMy question is, is this sane? Does the repack algorithm depend on having\na fixed window size to work? I'd rather not look into implementing this\nif it's silly on the face of it.\n\nThanks,\n-bcd\n"},{"id":"46795","messageId":"56b7f5510707081435h60c1787br16cf389161d7143@mail.gmail.com","threadId":"8935","inReplyTo":"20070708211606.GF4087@lavos.net","subject":"Re: [RFC] Dynamic window size on repack?","fromName":"Dana How","fromEmail":"danahow@gmail.com","sentAt":"2007-07-08T21:35:05Z","receivedAt":"2007-07-08T21:35:05Z","isPatch":false,"sender":{"key":"danahow@gmail.com","avatar":null},"body":"On 7/8/07, Brian Downing wrote:\n> I have a CVS repository which is mostly sane, but has an approximately\n> 20MB RTF file that has two hundred revisions or so. (Thank you, Windows\n> help.)\n>\n> Now, since this is old history, I want to make it as small as possible.\n> The only problem is that when I use high --window values for repack,\n> it goes along swimmingly until it gets to this file, at which point\n> memory usage quickly rises to the point where I'm well into my swap file.\n>\n> I think what I'd like is an extra option to repack to limit window\n> memory usage. This would dynamically scale the window size down if it\n> can't fit within the limit, then scale it back up once you're off of the\n> nasty file. This would let me repack my repository with --window=100\n> and have it actually finish someday on the machines I have access to.\n> The big file may not be as efficiently packed as possible, but I can\n> live with that.\n>\n> My question is, is this sane? Does the repack algorithm depend on having\n> a fixed window size to work? I'd rather not look into implementing this\n> if it's silly on the face of it.\n\nSounds very sane to me.\n\nIt seems like you want something like this\n(I've not referred to the code, but there is a loop\n that could be modifed to include something like this):\n /* build list of delta candidates */\n tot = 0;\n for (i = 0; i < window; ++i ) {\n obj = objects_sorted_for_delta[here + i];\n tot += SIZE(obj);\n if ( tot > window_limit )\n break;\n /* insert obj in list of things to delta, or just try it here */\n ...\n }\n if ( i <= 1 )\n break/return;\n\nwindow_limit could be set automatically like the variables\nfor the mmap windows are (no new options).\nSIZE() should be defined to return the actual bytes consumed\nby the object (I think for this it's uncompressed and undeltified,\nbut as I said I haven't looked at the code).\n\nIt would be better if the current list of objects in the window\nwere a FIFO. Before each deltification attempt, add objects\nfrom the sort list until #objects > window or tot > window_limit.\nAfter each attempt, drop off the object we were trying to delta.\n\nI like your idea and think you should look into implementing it.\n-- \nDana L. How danahow@gmail.com +1 650 804 5991 cell\n"},{"id":"46794","messageId":"alpine.LFD.0.999.0707081429500.31544@woody.linux-foundation.org","threadId":"8935","inReplyTo":"20070708211606.GF4087@lavos.net","subject":"Re: [RFC] Dynamic window size on repack?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-07-08T21:35:06Z","receivedAt":"2007-07-08T21:35:06Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 8 Jul 2007, Brian Downing wrote:\n> \n> I think what I'd like is an extra option to repack to limit window\n> memory usage. This would dynamically scale the window size down if it\n> can't fit within the limit, then scale it back up once you're off of the\n> nasty file. This would let me repack my repository with --window=100\n> and have it actually finish someday on the machines I have access to.\n> The big file may not be as efficiently packed as possible, but I can\n> live with that.\n> \n> My question is, is this sane? Does the repack algorithm depend on having\n> a fixed window size to work? I'd rather not look into implementing this\n> if it's silly on the face of it.\n\nIt doesn't sound silly, and it should even be fairly easy. The window code \nis all in builtin-pack-objects.c (find_deltas()) and while it's currently \ncoded for a constant-sized window, it shouldn't be too hard to free more \nold entries if you allocate one big one to make sure that the \"array\" \nthing doesn't grow to contain too much data.\n\nIn other words, just look at how the variables \"struct unpacked *array\" \n(the whole window array) and the \"struct unpacked *n\" (the \"next entry\" in \nthe array using a simple circular queue using \"idx\") are accessed.\n\n\t\tLinus\n"},{"id":"46797","messageId":"alpine.LFD.0.999.0707081437590.31544@woody.linux-foundation.org","threadId":"8935","inReplyTo":"alpine.LFD.0.999.0707081429500.31544@woody.linux-foundation.org","subject":"Re: [RFC] Dynamic window size on repack?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-07-08T21:39:45Z","receivedAt":"2007-07-08T21:39:45Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 8 Jul 2007, Linus Torvalds wrote:\n>\n> In other words, just look at how the variables \"struct unpacked *array\" \n> (the whole window array) and the \"struct unpacked *n\" (the \"next entry\" in \n> the array using a simple circular queue using \"idx\") are accessed.\n\nSide note: a limit based on object sizes is likely a much better way to \nhandle the window than just a \"number of objects\" thing ever was. Doing \nthe size in number of objects was easier, and is fine for source code that \ntends to have a reasonably normal distribution of sized, but yeah, if you \nhave a few really big objects with lots of history, then it's likely the \nwrong thing to do just because it can get really expensive.\n\n\t\tLinus\n"}]}