{"thread":{"id":"26950","subject":"Indexing Zlib deflated streams for pseudo-random-access to reduce delta-resolution memory requirements","startedAt":"2011-03-31T20:26:45Z","lastAt":"2011-04-01T13:59:51Z","messageCount":2,"participants":["Sebastian Thiel"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"164830","messageId":"4D94E385.7090903@googlemail.com","threadId":"26950","inReplyTo":null,"subject":"Indexing Zlib deflated streams for pseudo-random-access to reduce delta-resolution memory requirements","fromName":"Sebastian Thiel","fromEmail":"byronimo@googlemail.com","sentAt":"2011-03-31T20:26:45Z","receivedAt":"2011-03-31T20:26:45Z","isPatch":false,"sender":{"key":"byronimo@googlemail.com","avatar":null},"body":"Hi,\n\nWhy would one have big files delta compressed anyway ? From my \nexperience, this can save a lot of space, even though the process of \ngenerating the deltas will definitely take up a lot of memory. In my \nuse-case the packs are generated on a server with plenty of RAM. And \neven though the most recent version of an object tends to be a base \nwhich wouldn't need delta resolution, querying older revisions will \nrequire it. As this is done client side most of the time, it would be \ngreat to reduce the memory footprint,  at the cost of some additional \npreprocessing time.\n\nCurrently, when reapplying deltas on rather big files, assumed that one \ndidn't exclude them for delta compression in the first place, the \ncurrent algorithm requires the base-buffer, the target buffer as well as \nthe inflated delta stream itself in memory concurrently. Then the \nalgorithm works its way up recursively from the first base object to the \nlast delta until it is done. This causes plenty of possibly large memory \nallocations, as well as high memory demands.\n\nIn my current python and c++ implementation of pack reading, I try to \nstream all objects. Base objects can already be very efficiently \nstreamed as a plain (streamed) inflate will do. This is different for \ndelta objects. Even though the delta resolution machinery is hidden \nbehind a stream interface, it still produces a big buffer to hold the \nresolved object.\n\nMy current research went far enough to allow delta streams to be merged \ntogether at first, so the last delta to be applied gets merged down onto \nits base delta, and so forth, until all deltas were merged into one big \ndelta which just applies to the base buffer. This delta will have only \ncopy operations which refer to the base object's data, as well as copy \noperations. Currently,  the merged delta stream is kept in memory \ndeflated, and could be streamed  more or less easily. The problem I have \nis that the base object's data still needs to be available for random \naccess, i.e. inflated in memory.\n\nAlthough this technique safes some memory during processing, as it will \nnever allocate two possibly large base and target buffers, in the end it \nturns out to be more expensive memory wise as it needs the base buffer \nas well as the merged delta to be allocated as long as the streaming is \nin progress, compared to just the possibly smaller target buffer in case \nof the default recursive algorithm.\n\nHere comes the link to the subject line: If it was possible to index the \nzip deflated stream somehow, it wouldn't be required to keep an inflated \nversion of the base buffer in memory all the time. Instead, the required \nportions can be decompressed on demand, using the said zip stream index. \nThen we would only need the merged delta stream in memory, which should \n(ideally) be smaller than the target buffer itself.\n\nDo you think it is feasible to burn these extra cycles to reduce the \nmemory footprint ? Do you know whether or how it is possible to index a \nzip deflated stream for pseudo-random access or can provide hints ?\nSo far, from studying the zlib manual, there seems to be some way of \ndetermining zip blocks which can then possibly be linked to the \nuncompressed data positions, but ... I am absolutely not sure. Ideally, \nthis whole indexing process works by quickly skipping through the zlib \nstream without actually decompressing it.\n\nMaybe, all this is too much effort, and maybe the merged delta stream's \nsize ends up being larger than the target buffer so it was all for \nnothing (which one would only know once the preprocessing time was \nalready spent), but maybe it could really help truly 'stream' deltified \nobjects (which has been something like my holy grail for quite some time \nnow).\n\nThanks,\nSebastian\n"},{"id":"164887","messageId":"4D95DA57.9010304@gmail.com","threadId":"26950","inReplyTo":"4D959B56.7040508@peralex.com","subject":"Re: Indexing Zlib deflated streams for pseudo-random-access to reduce delta-resolution memory requirements","fromName":"Sebastian Thiel","fromEmail":"byronimo@googlemail.com","sentAt":"2011-04-01T13:59:51Z","receivedAt":"2011-04-01T13:59:51Z","isPatch":false,"sender":{"key":"byronimo@googlemail.com","avatar":null},"body":"Hi Noel,\n\nThanks for your input ! Except for (a), I understand what you mean. In\ncase of (a), this would also mean that the delta stream gets resized and\nbecomes larger, which could be a bottleneck depending on how many\nresizes you need. Yet, I didn't understand what (a) would mean.\n\nEverything else makes sense, and should work well and fast assuming that\nhard disk is large enough to possibly hold the temporary destination\nfile. If the system runs out of memory, it will just swap the memory out\nonto the temporary file.\n\nI definitely consider this an alternative to indexing the zip stream,\nwhich might even be impossible or not viable performance wise.\n\nThanks,\nSebastian\n\nOn 01.04.11 11:31, Noel Grandin wrote:\n> Nice work!\n>\n> Suggestion:\n> (a) walk the merged delta stream, creating additional delta entries to\n> fill in the bits that did not change i.e. create entries that look like\n> copy from position 500, len 20 to position 500\n> (b) sort the merged delta stream by base buffer file position\n> (c) create the destination file (with zero contents)\n> (d) mmap the destination file\n> (e) stream the base buffer, applying the deltas to the mmap'ed file.\n>\n> -- Noel Grandin.\n>\n> Sebastian Thiel wrote:\n>> Hi,\n>>\n>> Why would one have big files delta compressed anyway ? From my\n>> experience, this can save a lot of space, even though the process of\n>> generating the deltas will definitely take up a lot of memory. In my\n>> use-case the packs are generated on a server with plenty of RAM. And\n>> even though the most recent version of an object tends to be a base\n>> which wouldn't need delta resolution, querying older revisions will\n>> require it. As this is done client side most of the time, it would be\n>> great to reduce the memory footprint,  at the cost of some additional\n>> preprocessing time.\n>>\n>> Currently, when reapplying deltas on rather big files, assumed that\n>> one didn't exclude them for delta compression in the first place, the\n>> current algorithm requires the base-buffer, the target buffer as well\n>> as the inflated delta stream itself in memory concurrently. Then the\n>> algorithm works its way up recursively from the first base object to\n>> the last delta until it is done. This causes plenty of possibly large\n>> memory allocations, as well as high memory demands.\n>>\n>> In my current python and c++ implementation of pack reading, I try to\n>> stream all objects. Base objects can already be very efficiently\n>> streamed as a plain (streamed) inflate will do. This is different for\n>> delta objects. Even though the delta resolution machinery is hidden\n>> behind a stream interface, it still produces a big buffer to hold the\n>> resolved object.\n>>\n>> My current research went far enough to allow delta streams to be\n>> merged together at first, so the last delta to be applied gets merged\n>> down onto its base delta, and so forth, until all deltas were merged\n>> into one big delta which just applies to the base buffer. This delta\n>> will have only copy operations which refer to the base object's data,\n>> as well as copy operations. Currently,  the merged delta stream is\n>> kept in memory deflated, and could be streamed  more or less easily.\n>> The problem I have is that the base object's data still needs to be\n>> available for random access, i.e. inflated in memory.\n>>\n>> Although this technique safes some memory during processing, as it\n>> will never allocate two possibly large base and target buffers, in\n>> the end it turns out to be more expensive memory wise as it needs the\n>> base buffer as well as the merged delta to be allocated as long as\n>> the streaming is in progress, compared to just the possibly smaller\n>> target buffer in case of the default recursive algorithm.\n>>\n>> Here comes the link to the subject line: If it was possible to index\n>> the zip deflated stream somehow, it wouldn't be required to keep an\n>> inflated version of the base buffer in memory all the time. Instead,\n>> the required portions can be decompressed on demand, using the said\n>> zip stream index. Then we would only need the merged delta stream in\n>> memory, which should (ideally) be smaller than the target buffer itself.\n>>\n>> Do you think it is feasible to burn these extra cycles to reduce the\n>> memory footprint ? Do you know whether or how it is possible to index\n>> a zip deflated stream for pseudo-random access or can provide hints ?\n>> So far, from studying the zlib manual, there seems to be some way of\n>> determining zip blocks which can then possibly be linked to the\n>> uncompressed data positions, but ... I am absolutely not sure.\n>> Ideally, this whole indexing process works by quickly skipping\n>> through the zlib stream without actually decompressing it.\n>>\n>> Maybe, all this is too much effort, and maybe the merged delta\n>> stream's size ends up being larger than the target buffer so it was\n>> all for nothing (which one would only know once the preprocessing\n>> time was already spent), but maybe it could really help truly\n>> 'stream' deltified objects (which has been something like my holy\n>> grail for quite some time now).\n>>\n>> Thanks,\n>> Sebastian\n>>\n>> -- \n>> To unsubscribe from this list: send the line \"unsubscribe git\" in\n>> the body of a message to majordomo@vger.kernel.org\n>> More majordomo info at  http://vger.kernel.org/majordomo-info.html\n>>\n>\n>\n>\n> ------------------------------------------------------------------------\n> Disclaimer: http://www.peralex.com/disclaimer.html\n>\n"}]}