{"thread":{"id":"32830","subject":"On (re)packing","startedAt":"2013-02-05T06:35:48Z","lastAt":"2013-02-05T06:35:48Z","messageCount":1,"participants":["Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"208688","messageId":"7vbobzw9mj.fsf@alter.siamese.dyndns.org","threadId":"32830","inReplyTo":null,"subject":"On (re)packing","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-02-05T06:35:48Z","receivedAt":"2013-02-05T06:35:48Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Just a random thought...\n\n\"git pack-objects\" runs \"rev-list --objects\" to obtain three\ndifferent kinds of information about objects:\n\n * Reachability.  Objects that appear in the output of rev-list are\n   relevant, and those that do not are not;\n\n * Recency, aka closeness in the time dimension.  Objects that\n   appear in the output of rev-list close together appear in the\n   history nearby (a commit and its parents, a commit and its tree,\n   a tree and its subtree and blob);\n\n * Paths, aka closeness in the space dimension.  Trees and blobs are\n   labelled with paths they are first discovered at.\n\nAll of these are necessary for reasonable packing.  We choose only\nthe reachable objects to pack.  We place objects close in the time\ndimension together in the output pack stream.  And we delta objects\nclose in the space dimension against each other.\n\nNow, we are planning to use object reachability bitmap to speed up\nthe object enumeration phase of repacking.  This primarily gives us\nthe reachability information.  Placing objects that are packed close\nin existing packs close to each other in the output stream hopefully\nmay give us good enough approximation of the recency order.  And\nreusing the delta will keep good existing delta if both deltified\nobject and its delta base object are included in the output.\n\nWhat should happen when we repack two or more packs?  Placing an\nobject that appears near the beginning of one pack close to another\nobject that appears near the beginning of the other pack would\nprobably not make much sense, so the natural extension of emulating\nrecency order by pack offset would be to place all objects from one\npack together (in their original in-pack offset orde) and then\nobjects from the other pack together.\n\nMore problematic is how to coalesce one delta chain from one pack\nwith another delta chain from the other pack.  Without having the\npath information, we cannot efficiently do this.  Especially if we\nare to repack 50 small packs into one, it would be desirable if we\ncan avoid packing 50 similar objects in their undeltified form.\n\nAssuming that we would want some extra information, in addition to\nthe bitmaps, to help repacking, and also with the recent \"commit\nmetadata\" topic in mind, lets do a back-of-the-envelope enumeration\nof what we would want.  Here is a list off the top of my head.\n\n* commits\n\n  99.9% of all commits have no more than two parents.  Assuming that\n  we keep this information per-pack, and we will not be packing more\n  than 2^32 objects in a pack, we can represent up to two parent\n  commits by two int32s to represent their position in the table of\n  SHA-1's in the .idx file.  Also we can store another uint32 for\n  the commit timestamp (compute the timestamp of the oldest commit\n  in the pack and store it as uint64, and represent the commmit\n  timestamp of each commit with uint32 (we can represent a pack that\n  spans 68 years with this scheme).  Give up storing metainformation\n  for any commit whose information cannot fit this scheme (e.g. an\n  octopus, or a commit with timestamp way out of line).\n\n  That costs 12 bytes per commit (plus 8-byte for the oldest\n  timestamp in the pack).\n\n* tags\n\n  The timestamp can be expressed with a uint32 in the same way as\n  commit's timestamp, and the tagged object can be expressed with a\n  uint32 in the same way as commit's parent.  Two uint32s\n\n* trees and blobs\n\n  The name hash value is uint32.\n\nIf we have other information that are needed for trees and blobs\nthat fit in two more uint32s, then we can just build a table of\n12-byte entries for all objects in the pack.  \n\nOtherwise, we would need a way to have separate table that can be\nquickly accessed, going from an object name to either 3 uint32 tuple\n(if it is a commit), 2 uint32 tuple (if it is a tag), or a uint32\n(others).\n\nWhether we can do a table with uniform entry size or split tables,\nonce we locate an entry, we can find out the object number in the\nSHA-1 table the object refers to (e.g. parents, or tagged) so I do\nnot think it is a good idea to express object pointer with an\nabbreviated SHA-1.  But if we have to build commit-only table, we\nmay need to use a table with 16-byte entry size, that has 8\nhexdigits (i.e. 4-bytes) abbreviated object name of a commit,\nfollowed by the 12 byte commit metainformation, and sort it by the\nabbreviated object name.  With the same scheme, another table for\ntrees and blobs will cost 4-bytes for abbreviated object name as key\nand 4-bytes for name-hash payload.  That sounds a bit too wasteful\nto my taste.\n"}]}