On Wed, Aug 15, 2012 at 10:42 PM, Junio C Hamano <gitster@xxxxxxxxx> wrote: > Shawn Pearce <spearce@xxxxxxxxxxx> writes: > >> ... But I think its worth giving >> him a few weeks to finish getting the code ready, vs. rushing >> something in that someone else thinks might help. We have waited more >> than 6 years or whatever to improve packing. Colby's experiments are >> showing massive improvements (40s enumeration cut to 100ms) with low >> disk usage increase (<10%) and no pack file format changes. > > No matter what you do, you would be saving the bitmap somewhere > outside the *.pack file, yes? Will it be in some extended section > of the new *.idx file? Yes, because it is derived from the pack stream its stored external from it. We have chosen to append it as a new section below the CRC-32 table in the *.idx file. It could also go into a new file stream (*.bdx?) but I don't think this is worthwhile. Its a bikeshed that can be painted once the algorithm has proven its value. If it can't do that, its irrelevant where its stored. > With the bitmap, your object enumeration phase may go very fast, and > you would be able to figure out, in response to a fetch request "I > have these tips of refs; please update me with these refs of yours", > the set of objects you would need to pack (i.e. the ones that are > reachable from your refs that were asked for, but that are not > reachable from the refs the requestor has). Yes. Not only that, but we are finding that the number of objects to send is fewer, resulting in a much smaller data stream. The bitmap gives us near perfect knowledge of everything the client has, not just the objects on the edge of the graph cut expressed by the ACKed have lines. Objects that existed earlier than the cut don't have to be reset. So the object enumeration phase goes very fast. The compressing objects phase is also time reduced, as fewer objects are needed to be considered, as fewer objects are being sent. With more complete knowledge of the have side, more deltas can be reused as-is, rather than re-encoded on the fly. This reduces the compressing objects phase time even further. And with fewer objects to send, we have easily seen trivial cases of a Linux kernel fetch that is 1 week behind Linus' tip save like 200K on an 800K transfer. Its hard to hate having all of the phases go faster, and transmit less data to the client. > Among these objects, there will be ones that are expressed as a > delta against what you are going to send, or as a delta against what > you know the recipient must already have (if you are using thin pack > transfer) in the packfiles you have, and you can send these deltas > as-is without recomputation. Yes. I point that out above before even reading this far in your message. :-( > But there will be ones that are either expressed as a base in your > packfile, or as a delta against something you are not going to send > and you know that the recipient does not have. In order to turn > these objects into deltas, it may be necessary to have a way to > record which "delta chain" each object belongs to Excellent observation. Instead of performing a hacky delta base search by looking at identical path names in the have set, finding another candidate in the same cluster of deltas that the object is currently encoded against would yield a pretty efficient delta on the wire. It doesn't have to be another object in the same chain, it could also be a sibling object that shares a similar transitive delta base. >, and if you are > introducing the mechanism to have extended sections in the new *.idx > file, that may be a good place to do so. Thus far we haven't done an extended sections modification to the *.idx format. Its just a 'E003' version that requires the bitmaps to be present below the CRC-32 table. But I can see how framing this as a group of optional extensions would be worthwhile. > When you need to express > an object that your bitmap told you to send (as opposed to rev-list > walking told you with the paths to the objects), you can find other > objects that belong to the same "delta chain" and that you know are > available to the recipient when it starts to fixing the thin pack > using that extra piece of information, in order to find the optimal > delta base to encode such an object against. Yes. > Just for fun, I applied the attached patch and repacked the history > leading to v1.7.12-rc3 with the default depth/window: > > git rev-list --objects --all | > git pack-objects \ > --no-reuse-delta --no-reuse-object --delta-base-offset \ > [--no-namehash] pack > > with and without the experimental --no-namehash option. The result > is staggering. With name-hash to group objects from the same path > close together in the delta window, the resulting pack is 33M. > Without the name-hash hint, the same pack is 163M! Needless to say, > keeping the objects that should be hashed together inside a delta > window is really important. Cute experiment. Yes that name hash works as a decent predictor of which objects should go near each other in the delta window. So does the descending size sort. > An obvious way to record the "delta chain" is to simply keep the > name_hash of each object in the pack, which would need 2 bytes per > object in the pack, that would bloat pack_idx_entry size from 32 > bytes to 34 bytes per entry. That way, after your bitmap discovers > an object that cannot reuse existing deltas, you can throw it, other > such objects with the same name-hash, and then objects that you know > will be available to the recipient (you mark the last category of > objects as "preferred base"), into the delta_list so that they are > close together in the delta window. Yes, this is one thought I had. Inside of JGit I think the name hash is 32 bits, not 16 bits. Storing the name hash into the *.idx file means we need to codify what the name hash algorithm is for a given *.idx file version, and compatible implementations of Git must use the same hash function. Thus far the name hash has been an in-memory transient concept that doesn't need to be persisted across runs of the packer. Storing it means we have to do that. Another alternative is to try and group objects by delta clusters. Tag each object with some marker for the non-delta base object the delta chain it builds on top of. Delta groups are supposed to tend to be bushy and not long, so many many objects should share the same common base object. Most of them have the same name hash, but even when they don't their contents were near enough together that the prior packer run chose to combine these together. This avoids the need to encode the name-hash function into the *.idx file format, and instead lets us work with something that any implementation can easily observe from the file's contents. Tagging each object with its base could cost 4 bytes per entry, so 32->36 bytes... a 12% increase in file size. It may be possible to organize these as bitmaps and get really good compression from deltas that are located near each other in the pack stream, but doing the lookup to identify which base would be more expensive. We would probably have to walk the object's delta chain backwards to identify the base, then inflate the bitmap to identify the candidate siblings. -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html