{"thread":{"id":"7965","subject":"Re: [RFC] Optimize diff-delta.c","startedAt":"2007-05-04T06:40:24Z","lastAt":"2007-05-04T13:35:47Z","messageCount":2,"participants":["Martin Koegler","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"41008","messageId":"20070504064024.GA11788@auto.tuwien.ac.at","threadId":"7965","inReplyTo":null,"subject":"Re: [RFC] Optimize diff-delta.c","fromName":"Martin Koegler","fromEmail":"mkoegler@auto.tuwien.ac.at","sentAt":"2007-05-04T06:40:24Z","receivedAt":"2007-05-04T06:40:24Z","isPatch":false,"sender":{"key":"mkoegler@auto.tuwien.ac.at","avatar":null},"body":"On 2007-05-01 16:05:24, Nicolas Pitre wrote:\n> > On Tue, 1 May 2007, Martin Koegler wrote:\n> Right.  I think it would be a good idea to extend the delta format as \n> well to allow for larger offsets in pack v4.\n\nIs git://repo.or.cz/git/fastimport.git#sp/pack4 the current version of\npack v4 efforts?\n\n> > The delta index has approximately the same size in memory as the\n> > uncompressed blob ((blob size)/16*(sizeof(index_entry)).\n> \n> One thing that could be done with really large blobs is to create a \n> sparser index, i.e. have a larger step than 16.  Because the delta match \n> loop scans backward after a match the sparse index shouldn't affect \n> compression that much on large blobs and the index could be \n> significantly smaller.\n\nIn the long term, I think, that the delta generation code needs to get\ntunable.\n\nI would add a init_delta function for reading the configuration\noptions. In create_delta and create_delta_index, different delta\nheuristics can be selected based on the blob size and the\nconfiguration options. As patch_delta is not affected by this, it\nshould be easy to integrate new stragegies.\n\n> > I tried to speed up the delta generation by searching for a common \n> > prefix, as my blobs are mostly append only. I tested it with about \n> > less than 1000 big blobs. The time for finding the deltas decreased \n> > from 17 to 14 minutes cpu time.\n> \n> I'm surprised that your patch makes so much of a difference.  Normally \n> the first window should always match in the case you're trying to \n> optimize and the current code should already perform more or less the \n> same as your common prefix match does.\n\nA block is limited to 64k. If the file has some hundred MBs, it has to\nmatch many blocks.\n\nMy patch can process everything except the few last thousand lines by\ndoing a memcmp.\n\nAdditionally, nearly every line starts with the same, longer than 16\nbyte prefix. So its likely, that many blocks map to the same hash\nvalue.\n\n> Ah, no, actually what your patch does is a pessimisation of the matching \n> code by not considering other and possibly better matches elsewhere in \n> the reference buffer whenever there is a match at the beginning of both \n> buffers.  I don't think this is a good idea in general.\n\nFor small files, I agree with you.\n\n> What you should try instead if you want to make the process faster is to \n> lower the treshold used to consider a match sufficiently large to stop \n> searching.  That has the potential for even faster processing as the \n> \"optimization\" would then be effective throughout the buffer and not \n> only at the beginning.\n> \n[...]\n> \n> You could experiment with that value to determine the best speed vs size \n> compromize.\n\nI will do some experiments.\n\nmfg Martin Kögler\nPS: Sorry for break threading, as you did not CC me.\n"},{"id":"41054","messageId":"alpine.LFD.0.99.0705040905040.24220@xanadu.home","threadId":"7965","inReplyTo":"20070504064024.GA11788@auto.tuwien.ac.at","subject":"Re: [RFC] Optimize diff-delta.c","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-04T13:35:47Z","receivedAt":"2007-05-04T13:35:47Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 4 May 2007, Martin Koegler wrote:\n\n> On 2007-05-01 16:05:24, Nicolas Pitre wrote:\n> > > On Tue, 1 May 2007, Martin Koegler wrote:\n> > Right.  I think it would be a good idea to extend the delta format as \n> > well to allow for larger offsets in pack v4.\n> \n> Is git://repo.or.cz/git/fastimport.git#sp/pack4 the current version of\n> pack v4 efforts?\n\nYes.  It is lagging behind current git though, and not usable yet.\n\n> > > The delta index has approximately the same size in memory as the\n> > > uncompressed blob ((blob size)/16*(sizeof(index_entry)).\n> > \n> > One thing that could be done with really large blobs is to create a \n> > sparser index, i.e. have a larger step than 16.  Because the delta match \n> > loop scans backward after a match the sparse index shouldn't affect \n> > compression that much on large blobs and the index could be \n> > significantly smaller.\n> \n> In the long term, I think, that the delta generation code needs to get\n> tunable.\n\nNo.  It should be self-tunable certainly, but there are way too many \nconfig options already, and another one for the inner working of the \ndelta algorithm would be a bit too esoteric for most users and they \nwon't get advantage of it.  This thing really has to self tune itself.\n\n> > > I tried to speed up the delta generation by searching for a common \n> > > prefix, as my blobs are mostly append only. I tested it with about \n> > > less than 1000 big blobs. The time for finding the deltas decreased \n> > > from 17 to 14 minutes cpu time.\n> > \n> > I'm surprised that your patch makes so much of a difference.  Normally \n> > the first window should always match in the case you're trying to \n> > optimize and the current code should already perform more or less the \n> > same as your common prefix match does.\n> \n> A block is limited to 64k. If the file has some hundred MBs, it has to\n> match many blocks.\n\nOnly if the first match is smaller than 64K.  If the first match is 64K \nin size then the rest of the file is not considered at all.\n\n> My patch can process everything except the few last thousand lines by\n> doing a memcmp.\n> \n> Additionally, nearly every line starts with the same, longer than 16\n> byte prefix. So its likely, that many blocks map to the same hash\n> value.\n\nThe hash index only remembers the lowest of consecutive identical blocks \nso repeated blocks are indexed only with the first one.  If however you \nhappen to have many identical blocks interlaced between other blocks \nthen there is not much that can be done.  What the code does in that \ncase is to trim those hash buckets that gets too large by keeping only a \nfew entries across the reference buffer to avoid a O(n^2) behavior. But \nthat happens only when your line beginnings are located on the same \nblock boundary (but with a block size of 16 this is rather likely in the \npresence of lots of lines I suppose).\n\nI'll be very interested in the results you get with my suggested patch.\n\n\nNicolas\n"}]}