{"thread":{"id":"19671","subject":"[PATCH 7/7] revision cache: be even stricter with sort order","startedAt":"2009-06-04T14:05:12Z","lastAt":"2009-06-07T05:43:58Z","messageCount":14,"participants":["Sam Vilain","Jakub Narebski","Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"115477","messageId":"25e92985a657be1d7ea3dd8486cbe404b072a2a2.1244125127.git.sam@vilain.net","threadId":"19671","inReplyTo":"cover.1244125127.git.sam@vilain.net","subject":"[PATCH 2/7] rev-cache: add on-disk format for fast reachability lookup","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-06-04T14:05:12Z","receivedAt":"2009-06-04T14:05:12Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"As well as storing the sorted list of objects, store a hash table for\nfaster lookup.\n\nSigned-off-by: Sam Vilain \n---\n Documentation/technical/revision-cache.txt | 24 ++++++++++++++++++++----\n 1 files changed, 20 insertions(+), 4 deletions(-)\n\ndiff --git a/Documentation/technical/revision-cache.txt b/Documentation/technical/revision-cache.txt\nindex cc18535..8349cfe 100644\n--- a/Documentation/technical/revision-cache.txt\n+++ b/Documentation/technical/revision-cache.txt\n@@ -14,6 +14,9 @@ A revision cache contains;\n \n * object ID\n \n+ - A hash table from an (abbreviated) object ID to a position into\n+ the above list\n+\n \n Start Object\n ------------\n@@ -35,6 +38,18 @@ objects are sorted as if they were commit objects with a single\n parent, the object they tag.\n \n \n+Included object hash table\n+--------------------------\n+\n+This index is used to quickly determine if an object exists in the\n+index without scanning the entire topological list.\n+\n+Entries in the object hash table can be shortened, eg to 3 or 4 bytes;\n+basically they just need to be long enough to avoid collisions within\n+the objects which exist in the list. Any match must be confirmed by\n+checking the full SHA1 in the topological list.\n+\n+\n Use Cases\n ---------\n In this section, the key functions and operations that this index is\n@@ -131,7 +146,8 @@ passed, or any 'uninteresting' objects were passed.\n \n This function must revision walk the commit graph, sorting in\n --date-order along the way, and may emit revisions as they are\n-discovered to the topological object list.\n+discovered to the topological object list. It must also build a hash\n+table of object IDs and emit it at the end.\n \n \n receive-pack/pack-objects\n@@ -186,9 +202,9 @@ emitted, the delta from the packfile is re-used. If a loop is\n detected or the delta base is not in the returned set of objects, then\n the delta is first resolved.\n \n-This implies that the list of objects is first loaded into a hash\n-table prior to returning any objects; however this is probably\n-acceptable as the entire list is in one stream and will load quickly.\n+This implies that each delta base must be looked up in the on-disk\n+hash table as they are written, which is both low impact and memory\n+efficient.\n \n For later fetches, the revision cache is not appropriate as they will\n have 'uninteresting' objects set.\n-- \ndebian.1.5.6.1\n"},{"id":"115479","messageId":"a3798f6363249996f03771bd286bb2b1db10ea24.1244125128.git.sam@vilain.net","threadId":"19671","inReplyTo":"cover.1244125127.git.sam@vilain.net","subject":"[PATCH 5/7] revision cache: maps of 'new' objects","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-06-04T14:05:12Z","receivedAt":"2009-06-04T14:05:12Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"When making a pack, it is useful to know if an object is already\nreachable from any of the objects that the receiving party is known to\nhave; it allows the object to be excluded from the pack. Allow\noptional bitmaps for 'start' objects which permit storage of this\ninformation.\n\nSigned-off-by: Sam Vilain \n---\n Documentation/technical/revision-cache.txt | 24 +++++++++++++++++++++++-\n 1 files changed, 23 insertions(+), 1 deletions(-)\n\ndiff --git a/Documentation/technical/revision-cache.txt b/Documentation/technical/revision-cache.txt\nindex 198c33a..e0adb26 100644\n--- a/Documentation/technical/revision-cache.txt\n+++ b/Documentation/technical/revision-cache.txt\n@@ -28,6 +28,11 @@ A revision cache contains;\n space. A count of how many bits are '1' is included. A separate\n bitmap is included for the 'start' objects.\n \n+ - Optionally, for any 'end' object, a 'newness' bitmap indicating\n+ which of the objects in the object list are reachable from that\n+ 'end' object, but not reachable from the 'start' objects reachable\n+ from that 'end' object.\n+\n \n Start Objects and End Objects\n -----------------------------\n@@ -120,6 +125,9 @@ generating a newer one which covers objects created after it. This\n approach will be able to answer many questions, but not topological\n ordering between objects which appeared in different caches.\n \n+Stacking revision caches is essential for being able to generate the\n+'newness' bitmaps efficiently.\n+\n \n Revision Walker\n ~~~~~~~~~~~~~~~\n@@ -144,7 +152,7 @@ required. Some API exists to do this, and the return value from\n 'rev_cache_ok' is true if suitable caches were found for the\n information required, and false if it would require a graph traversal:\n \n- rev_cache_options( ordered? )\n+ rev_cache_options( ordered?, new? )\n rev_cache_ok( ) : Bool\n \n The rev_cache_ok() function must open all available revision caches,\n@@ -163,6 +171,11 @@ If any 'uninteresting' objects were passed, then the return value is\n true if the suitability function passes for all of the revision caches\n which are used.\n \n+If the 'new' flag is set to true, then the return value is only true\n+if the 'uninteresting' objects also have suitable revision caches\n+leading back to the start of history (or last 'shallow' point), or the\n+'newness' bitmaps are present for all of the 'start' references used.\n+\n \n Returning objects\n ^^^^^^^^^^^^^^^^^\n@@ -208,6 +221,10 @@ Then, it must repeat the topological walk for each of the 'start'\n objects, looking up each object in the contents hash for a sequence\n number, set a bit in the bitmap for that 'start' object, and finally\n RLE compress it.\n+If there are suitable other revision caches available, then the\n+'newness' bitmaps are built by checking with the stacked revision\n+caches whether the object exists and is reachable from the 'start'\n+objects which connect to those stacked caches.\n \n \n receive-pack/pack-objects\n@@ -250,6 +267,11 @@ If multiple 'start' objects were used, then the count can be returned\n by decompressing and OR'ing the bitmaps together, counting the total\n number of '1's in the bitmap.\n \n+If the 'newness' bitmaps are available, then these can be used to\n+avoid sending objects which the other end will already have.\n+When applicable the 'newness' bitmaps will be masked against the\n+combined reachability bitmaps to derive a shorter list of objects.\n+\n If multiple revision caches were used, but not in single file, then\n the number of objects can be obtained by building a hash table of all\n the objects in all of the caches, and returning the number of hash\n-- \ndebian.1.5.6.1\n"},{"id":"115480","messageId":"008619a339292ab96f7f64fe5f4437f0f3ad0b86.1244125128.git.sam@vilain.net","threadId":"19671","inReplyTo":"cover.1244125127.git.sam@vilain.net","subject":"[PATCH 4/7] rev-cache: allow multiple 'start' objects per index","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-06-04T14:05:12Z","receivedAt":"2009-06-04T14:05:12Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"We can re-use the index for multiple 'start' objects sharing the same\n'end' objects, using one list and a reachability bitmap for each\n'start' object.\n\nSigned-off-by: Sam Vilain \n---\n Documentation/technical/revision-cache.txt | 106 +++++++++++++++++++---------\n 1 files changed, 73 insertions(+), 33 deletions(-)\n\ndiff --git a/Documentation/technical/revision-cache.txt b/Documentation/technical/revision-cache.txt\nindex 759d78d..198c33a 100644\n--- a/Documentation/technical/revision-cache.txt\n+++ b/Documentation/technical/revision-cache.txt\n@@ -6,12 +6,13 @@ reachability operations to be answered quickly.\n \n A revision cache contains;\n \n- - A 'start' object (ie, 'interesting' object ID)\n+ - A list of 'start' objects (ie, 'interesting' object IDs)\n \n - A list of 'end' objects, which may be empty (ie, 'uninteresting'\n object IDs)\n \n- - A list of objects which are referred to by the 'start' object\n+ - A list of objects which are referred to by any 'start' object, but\n+ not by crossing 'end' objects, including:\n \n * position when sorted in --date-order\n \n@@ -20,13 +21,25 @@ A revision cache contains;\n - A hash table from an (abbreviated) object ID to a position into\n the above list\n \n+ - For each 'end' object, a bit sequence indicating which of the\n+ objects in the object list are reachable from that 'end' object.\n+ These bitmaps are stored in the same order as the object list and\n+ then RLE-compressed, so in many cases will not take much on-disk\n+ space. A count of how many bits are '1' is included. A separate\n+ bitmap is included for the 'start' objects.\n \n-Start Objects and End Object\n-----------------------------\n+\n+Start Objects and End Objects\n+-----------------------------\n \n The 'start' object, and 'end' objects are the identifying key of the\n revision cache.\n \n+Revision caches for multiple 'start' objects can re-use the same\n+object list, conserving space and adding flexibility to the index. As\n+such, a single revision cache is logically considered to be multiple\n+indexes, unless it is of benefit to consider it a single index.\n+\n The 'end' objects must be reachable from the 'start' objects, and none\n of the 'end' objects may be reachable from other 'end' objects.\n \n@@ -71,27 +84,36 @@ Determining Cache Suitability - rev_cache_suitable()\n This is an auxiliary function used by the other use cases.\n \n A revision cache is suitable whenever the walker encounters the single\n-object which is the 'end' object of the revision cache, and none of\n-the 'uninteresting' revisions to the walker are in the revision cache.\n+object which is any of the 'end' objects of the revision cache, and\n+none of the 'uninteresting' revisions to the walker are in the\n+revision cache.\n \n The function is:\n \n rev_cache_suitable( rev_cache, interesting, uninteresting [] )\n \n The check is simple and fast - it first compares the 'interesting'\n-object to the 'start' object in the revision cache, then the\n+object to the 'start' object list in the revision cache, then the\n 'uninteresting' objects that the walker is using are looked up in the\n contents hash table.\n-Only if none of them are found is the revision cache suitable.\n+If they are found, then the reachability bitmap for the matching\n+'start' objects are consulted for whether the object was actually\n+reachable from those 'start' objects.\n+Only if none of them are reachable is the revision cache suitable.\n \n \n Revision cache stacking\n ^^^^^^^^^^^^^^^^^^^^^^^\n \n-If there are 'end' objects in the revision cache used, which do not\n+If there are 'end' objects in the revision cache used, which are\n+reachable from the 'start' objects in use, and do not\n match the 'uninteresting' objects in the walker, the function may\n recurse, looking for other revision caches which have the unwanted\n-'end' object as their 'start' object.\n+'end' object in their 'start' object list.\n+\n+Allowing multiple 'start' objects allows for more instances of 'single\n+file' stacking, where at no point is the stack wider than one revision\n+cache.\n \n Stacking revision caches is a way to re-use an older index by just\n generating a newer one which covers objects created after it. This\n@@ -126,18 +148,20 @@ information required, and false if it would require a graph traversal:\n rev_cache_ok( ) : Bool\n \n The rev_cache_ok() function must open all available revision caches,\n-and see if their 'interesting' object matches the single 'interesting'\n-object passed to rev_cache_add(). If it matches, it returns true. If\n-multiple 'interesting' objects were specified and 'ordered' is true,\n-then the function returns false.\n+and see if all of the 'interesting' objects passed to rev_cache_add()\n+can be found as 'start' objects in available revision caches.\n+If they cannot, the function returns false.\n+If multiple 'interesting' objects were specified and 'ordered' is\n+true, then the function returns false, unless all of the 'interesting'\n+objects were found in a single revision cache and no stacking is\n+required.\n \n-If the ordering flag was set to false, then all of the 'interesting'\n-objects must be found in separate revision caches for the function to\n-return true.\n+If the ordering flag was set to false, then this restriction is\n+relaxed. Objects may be found in separate revision caches.\n \n If any 'uninteresting' objects were passed, then the return value is\n-true if the suitability function passes for the revision caches which\n-are used.\n+true if the suitability function passes for all of the revision caches\n+which are used.\n \n \n Returning objects\n@@ -176,13 +200,14 @@ an 'interesting' object added, then call:\n \n rev_cache_create( )\n \n-This function will not work, if multiple 'interesting' objects are\n-passed.\n-\n This function must revision walk the commit graph, sorting in\n --date-order along the way, and may emit revisions as they are\n-discovered to the topological object list. It must also build a hash\n-table of object IDs and emit it at the end.\n+discovered to the topological object list.\n+It must also build a hash table of object IDs and emit it at the end.\n+Then, it must repeat the topological walk for each of the 'start'\n+objects, looking up each object in the contents hash for a sequence\n+number, set a bit in the bitmap for that 'start' object, and finally\n+RLE compress it.\n \n \n receive-pack/pack-objects\n@@ -215,13 +240,23 @@ Returning object counts\n If the revision cache was suitable, eg for a complete fetch, then the\n number of objects can be obtained by counting the size of the object\n list.\n-\n-If multiple revision caches were used for multiple 'interesting'\n-objects, then the number of objects can be obtained by building a hash\n-table of all the objects in all of the caches, and returning the\n-number of hash table entries. In the single-file stacked revision\n-cache case, the total can be found by adding up the total lengths of\n-the object lists.\n+If the revision cache was entirely suitable, with all 'start' objects\n+matching all 'interesting' objects in the walker, then the total\n+number of objects in the cache is the number of objects to be\n+returned.\n+If a single 'start' object was used, then the count of '1's in the\n+bitmap can be used.\n+If multiple 'start' objects were used, then the count can be returned\n+by decompressing and OR'ing the bitmaps together, counting the total\n+number of '1's in the bitmap.\n+\n+If multiple revision caches were used, but not in single file, then\n+the number of objects can be obtained by building a hash table of all\n+the objects in all of the caches, and returning the number of hash\n+table entries.\n+In the single-file stacked revision cache case, the total can be found\n+by adding up the total lengths of the object lists that apply to each\n+single-file section.\n \n If 'uninteresting' objects were passed, the caches used must be\n suitable according to the cache suitability function.\n@@ -241,8 +276,13 @@ detected or the delta base is not in the returned set of objects, then\n the delta is first resolved.\n \n This implies that each delta base must be looked up in the on-disk\n-hash table as they are written, which is both low impact and memory\n-efficient.\n+hash table as they are written to the network, which is both low\n+impact and memory efficient.\n+In the case where not all of the 'start' objects are used, then the\n+bitmaps for the 'start' objects in use will need to be kept in memory\n+to supplement the results of this hash lookup.\n+This is a small extra indirection likely to have only a minimal\n+performance penalty.\n \n For later fetches, the revision cache will only be appropriate if the\n 'have' objects sent by the remote are not found in the revision\n-- \ndebian.1.5.6.1\n"},{"id":"115482","messageId":"b054cddea58213268b872cf43c725960e6e2dc5b.1244125127.git.sam@vilain.net","threadId":"19671","inReplyTo":"cover.1244125127.git.sam@vilain.net","subject":"[PATCH 1/7] revision-cache: define revision cache as simple list of revisions","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-06-04T14:05:12Z","receivedAt":"2009-06-04T14:05:12Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"The very first thing that we want out of the revision cache is to be\nable to go from a commit to all of its referred objects. Define a\nrevision cache that includes just that.\n\nSigned-off-by: Sam Vilain \n---\n Documentation/technical/revision-cache.txt | 260 ++++++++++++++++++++++++++++\n 1 files changed, 260 insertions(+), 0 deletions(-)\n create mode 100644 Documentation/technical/revision-cache.txt\n\ndiff --git a/Documentation/technical/revision-cache.txt b/Documentation/technical/revision-cache.txt\nnew file mode 100644\nindex 0000000..cc18535\n--- /dev/null\n+++ b/Documentation/technical/revision-cache.txt\n@@ -0,0 +1,260 @@\n+Revision Cache Format\n+=====================\n+\n+The revision cache is an on-disk format which allows for certain graph\n+reachability operations to be answered quickly.\n+\n+A revision cache contains;\n+\n+ - A 'start' object (ie, 'interesting' object ID)\n+\n+ - A list of objects which are referred to by the 'start' object\n+\n+ * position when sorted in --date-order\n+\n+ * object ID\n+\n+\n+Start Object\n+------------\n+\n+The 'start' object is the identifying key of the revision cache.\n+\n+\n+Topological contents list\n+-------------------------\n+\n+This list has fixed-length records, so the topological position into\n+the list does not need to be stored in each record - it is implicit\n+from the offset.\n+\n+--date-order is used as it is the strictest sort order available, but\n+this still only specifies an ordering for commit objects. Other\n+objects will appear after the object which first refers to them. Tag\n+objects are sorted as if they were commit objects with a single\n+parent, the object they tag.\n+\n+\n+Use Cases\n+---------\n+In this section, the key functions and operations that this index is\n+designed to answer are explored. For each, their efficiency is\n+considered in terms of what must be carried out to calculate the\n+answer.\n+\n+\n+Determining Cache Suitability - rev_cache_suitable()\n+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n+\n+This is an auxiliary function used by the other use cases, when \n+\n+The function is:\n+\n+ rev_cache_suitable( rev_cache, object )\n+\n+The check is simple and fast - it just compares the object to the\n+'start' object in the revision cache.\n+\n+\n+Revision Walker\n+~~~~~~~~~~~~~~~\n+\n+The revision walker is the main user of this cache; there is the\n+generic function of revision walking, as well as commands that want\n+specific information which they normally derive from the revision\n+walker output.\n+\n+\n+Setting up the walker\n+^^^^^^^^^^^^^^^^^^^^^\n+\n+The functions for this are (intentionally resembling the current\n+revision walker API):\n+\n+ rev_cache_init()\n+ rev_cache_add( interesting?, oid )\n+\n+As well as this setup, it is necessary to specify which options are\n+required. Some API exists to do this, and the return value from\n+'rev_cache_ok' is true if suitable caches were found for the\n+information required, and false if it would require a graph traversal:\n+\n+ rev_cache_options( ordered? )\n+ rev_cache_ok( ) : Bool\n+\n+The rev_cache_ok() function must open all available revision caches,\n+and see if their 'interesting' object matches the single 'interesting'\n+object passed to rev_cache_add(). If it matches, it returns true. If\n+multiple 'interesting' objects were specified and 'ordered' is true,\n+then the function returns false.\n+\n+If the ordering flag was set to false, then all of the 'interesting'\n+objects must be found in separate revision caches.\n+\n+If any 'uninteresting' objects were passed, then the return value is\n+always false.\n+\n+\n+Returning objects\n+^^^^^^^^^^^^^^^^^\n+\n+The 'rev_cache_fetch()' iterator returns entries from the topological\n+list.\n+\n+ rev_cache_fetch() : oid\n+\n+If returning objects from a single revision cache, it opens the \n+\n+\n+Accelerating in-progress walking\n+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n+\n+It is possible that during a revision iteration operation, a revision\n+is discovered that may mean the rest of the revision walking can be\n+achieved faster.\n+\n+In practice, this is likely to be implemented by making in-core cache\n+entries for objects with revision caches prior to walking; then when\n+encountered the special action can be taken.\n+\n+\n+Creating Revision Caches\n+~~~~~~~~~~~~~~~~~~~~~~~~\n+\n+Once the revision cache is setup via rev_cache_init() and\n+an 'interesting' object added, then call:\n+\n+ rev_cache_create( )\n+\n+This function will not work, if multiple 'interesting' objects are\n+passed, or any 'uninteresting' objects were passed.\n+\n+This function must revision walk the commit graph, sorting in\n+--date-order along the way, and may emit revisions as they are\n+discovered to the topological object list.\n+\n+\n+receive-pack/pack-objects\n+~~~~~~~~~~~~~~~~~~~~~~~~~\n+\n+pack-objects when called from pack-objects is a special user of the\n+revision cache; it has the extra requirements of wanting to know;\n+\n+* how many objects are between 'interesting' and 'uninteresting'\n+ objects, at the beginning of the run, to emit the pack header\n+\n+* for checking re-usability of deltas, whether the delta base object\n+ in the pack is in the received set of objects.\n+\n+* for 'thin' pack generation, whether the delta base object is in the\n+ received set of objects, -or- reachable from any 'uninteresting'\n+ objects\n+\n+* for 'shallow' clone, whether the delta base object is reachable\n+ without passing any of the 'uninteresting' objects\n+\n+The aim is for 'pack-objects' to be able to start returning objects\n+immediately in the case where a suitable revision cache is returned,\n+without waiting for revision counting or repacking.\n+\n+\n+Returning object counts\n+^^^^^^^^^^^^^^^^^^^^^^^\n+\n+If the revision cache was suitable, eg for a complete fetch, then the\n+number of objects can be obtained by counting the size of the object\n+list.\n+\n+If multiple revision caches were used for multiple 'interesting'\n+objects, then the number of objects can be obtained by building a hash\n+table of all the objects in all of the caches, and returning the\n+number of hash table entries.\n+\n+If 'uninteresting' objects were passed, no cache can be suitable.\n+\n+\n+Re-using deltas\n+^^^^^^^^^^^^^^^\n+\n+This applies to the 'Compressing Objects' phase, previously known as\n+the 'Deltafying Objects' phase. Instead of searching for deltas, if\n+we can be sure that the existing delta can be resolved on the remote,\n+then we can re-use it.\n+\n+For the initial clone, this operation is simple - as objects are\n+emitted, the delta from the packfile is re-used. If a loop is\n+detected or the delta base is not in the returned set of objects, then\n+the delta is first resolved.\n+\n+This implies that the list of objects is first loaded into a hash\n+table prior to returning any objects; however this is probably\n+acceptable as the entire list is in one stream and will load quickly.\n+\n+For later fetches, the revision cache is not appropriate as they will\n+have 'uninteresting' objects set.\n+\n+\n+Re-using deltas - 'thin' pack\n+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n+\n+This case is much like the normal re-using deltas case, except there\n+is the complete set of objects that the remote has claimed to have to\n+consider.\n+\n+The cache is not yet sophisticated enough to assist with this use\n+case.\n+\n+\n+'shallow' clone considerations\n+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n+\n+For enumerating objects, the list of objects between the\n+'uninteresting' and the 'shallow' commits must first be enumerated,\n+and then subtracted from the objects between the 'interesting' and the\n+'uninteresting' list.\n+\n+For re-using deltas for 'thin' packs, the list of objects between\n+'uninteresting' and 'shallow' commits are enumerated and marked as\n+valid for delta bases.\n+\n+The cache is not yet sophisticated enough to assist with this case.\n+\n+\n+creating bundles\n+~~~~~~~~~~~~~~~~\n+\n+So long as a bundle has no 'uninteresting' commits, then the revision\n+cache is completely appropriate; with the length of the object list it\n+can write a header and continue with the 'pack-objects' use case.\n+\n+\n+slicing bundles (mirror-sync)\n+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n+\n+For 'slicing' bundles, a deterministic method is required for chopping\n+up the list of objects, which can be calculated by any node which has\n+the 'interesting' commits.\n+\n+To determine the objects which fall within a given slice, the object\n+list must be enumerated and then divided evenly. As the compressed\n+size on one node cannot be reproduced on another node, the\n+uncompressed size of the object is used instead, with the hope that\n+slices will generally end up of roughly even size once compressed.\n+\n+To calculate the object boundaries, the list of objects in\n+--date-order must first be tie-broken, eg for commits with the same\n+commitdate and topological order. If slices are allowed to be\n+sub-commit level, then objects between commits (ie blobs and trees)\n+are also sorted. Once this deterministic list has been built, then\n+all of the objects must be accessed to determine their length. The\n+objects which start within a given range are the ones in the slice.\n+\n+For re-using deltas in sliced bundles, the delta base is looked up in\n+the deterministic list. If it has an earlier sequence, then the delta\n+can be safely re-used. If it has a later sequence, then the delta\n+must be resolved and then the object re-deltified/compressed, using\n+only objects with an earlier sequence (or in the returned pack) as a\n+base.\n+\n+This requirement is so that a collection of 'sliced' bundles can\n+successfully re-assemble, while still allowing them to be 'thin'.\n-- \ndebian.1.5.6.1\n"},{"id":"115483","messageId":"0648597b2ac9438e5f0c669720b130c787b6fd92.1244125127.git.sam@vilain.net","threadId":"19671","inReplyTo":"cover.1244125127.git.sam@vilain.net","subject":"[PATCH 3/7] rev-cache: add 'end' objects for caching 'uninteresting' lookups","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-06-04T14:05:12Z","receivedAt":"2009-06-04T14:05:12Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"If we want to be able to accelerate lookups which contain\n'uninteresting' revisions, we must be able to specify what those\nrevisions are.\n\nSigned-off-by: Sam Vilain \n---\n Documentation/technical/revision-cache.txt | 85 +++++++++++++++++++++-------\n 1 files changed, 65 insertions(+), 20 deletions(-)\n\ndiff --git a/Documentation/technical/revision-cache.txt b/Documentation/technical/revision-cache.txt\nindex 8349cfe..759d78d 100644\n--- a/Documentation/technical/revision-cache.txt\n+++ b/Documentation/technical/revision-cache.txt\n@@ -8,6 +8,9 @@ A revision cache contains;\n \n - A 'start' object (ie, 'interesting' object ID)\n \n+ - A list of 'end' objects, which may be empty (ie, 'uninteresting'\n+ object IDs)\n+\n - A list of objects which are referred to by the 'start' object\n \n * position when sorted in --date-order\n@@ -18,10 +21,14 @@ A revision cache contains;\n the above list\n \n \n-Start Object\n-------------\n+Start Objects and End Object\n+----------------------------\n+\n+The 'start' object, and 'end' objects are the identifying key of the\n+revision cache.\n \n-The 'start' object is the identifying key of the revision cache.\n+The 'end' objects must be reachable from the 'start' objects, and none\n+of the 'end' objects may be reachable from other 'end' objects.\n \n \n Topological contents list\n@@ -61,14 +68,35 @@ answer.\n Determining Cache Suitability - rev_cache_suitable()\n ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n \n-This is an auxiliary function used by the other use cases, when \n+This is an auxiliary function used by the other use cases.\n+\n+A revision cache is suitable whenever the walker encounters the single\n+object which is the 'end' object of the revision cache, and none of\n+the 'uninteresting' revisions to the walker are in the revision cache.\n \n The function is:\n \n- rev_cache_suitable( rev_cache, object )\n+ rev_cache_suitable( rev_cache, interesting, uninteresting [] )\n+\n+The check is simple and fast - it first compares the 'interesting'\n+object to the 'start' object in the revision cache, then the\n+'uninteresting' objects that the walker is using are looked up in the\n+contents hash table.\n+Only if none of them are found is the revision cache suitable.\n+\n+\n+Revision cache stacking\n+^^^^^^^^^^^^^^^^^^^^^^^\n+\n+If there are 'end' objects in the revision cache used, which do not\n+match the 'uninteresting' objects in the walker, the function may\n+recurse, looking for other revision caches which have the unwanted\n+'end' object as their 'start' object.\n \n-The check is simple and fast - it just compares the object to the\n-'start' object in the revision cache.\n+Stacking revision caches is a way to re-use an older index by just\n+generating a newer one which covers objects created after it. This\n+approach will be able to answer many questions, but not topological\n+ordering between objects which appeared in different caches.\n \n \n Revision Walker\n@@ -104,10 +132,12 @@ multiple 'interesting' objects were specified and 'ordered' is true,\n then the function returns false.\n \n If the ordering flag was set to false, then all of the 'interesting'\n-objects must be found in separate revision caches.\n+objects must be found in separate revision caches for the function to\n+return true.\n \n If any 'uninteresting' objects were passed, then the return value is\n-always false.\n+true if the suitability function passes for the revision caches which\n+are used.\n \n \n Returning objects\n@@ -118,7 +148,12 @@ list.\n \n rev_cache_fetch() : oid\n \n-If returning objects from a single revision cache, it opens the \n+If returning objects from a single or stacked set of revision caches,\n+it opens the caches and returns objects from them. If combining\n+results from multiple caches (where topological ordering of returned\n+objects is not important) then an in-memory object hash table must be\n+built, or the on-disk tables for all of the caches consulted along the\n+way.\n \n \n Accelerating in-progress walking\n@@ -142,7 +177,7 @@ an 'interesting' object added, then call:\n rev_cache_create( )\n \n This function will not work, if multiple 'interesting' objects are\n-passed, or any 'uninteresting' objects were passed.\n+passed.\n \n This function must revision walk the commit graph, sorting in\n --date-order along the way, and may emit revisions as they are\n@@ -184,9 +219,12 @@ list.\n If multiple revision caches were used for multiple 'interesting'\n objects, then the number of objects can be obtained by building a hash\n table of all the objects in all of the caches, and returning the\n-number of hash table entries.\n+number of hash table entries. In the single-file stacked revision\n+cache case, the total can be found by adding up the total lengths of\n+the object lists.\n \n-If 'uninteresting' objects were passed, no cache can be suitable.\n+If 'uninteresting' objects were passed, the caches used must be\n+suitable according to the cache suitability function.\n \n \n Re-using deltas\n@@ -206,8 +244,9 @@ This implies that each delta base must be looked up in the on-disk\n hash table as they are written, which is both low impact and memory\n efficient.\n \n-For later fetches, the revision cache is not appropriate as they will\n-have 'uninteresting' objects set.\n+For later fetches, the revision cache will only be appropriate if the\n+'have' objects sent by the remote are not found in the revision\n+caches' object hash table.\n \n \n Re-using deltas - 'thin' pack\n@@ -217,8 +256,13 @@ This case is much like the normal re-using deltas case, except there\n is the complete set of objects that the remote has claimed to have to\n consider.\n \n-The cache is not yet sophisticated enough to assist with this use\n-case.\n+The revision cache can assist with this case only if the 'have'\n+objects sent by the remote match the 'uninteresting' objects in the\n+revision cache (or are not found in the object list), and another\n+revision cache exists which uses that 'uninteresting' object as its\n+'start' object. In this case, the lower stacked revision cache serves\n+as a handy lookup table as to whether the object is known to the\n+remote.\n \n \n 'shallow' clone considerations\n@@ -239,9 +283,10 @@ The cache is not yet sophisticated enough to assist with this case.\n creating bundles\n ~~~~~~~~~~~~~~~~\n \n-So long as a bundle has no 'uninteresting' commits, then the revision\n-cache is completely appropriate; with the length of the object list it\n-can write a header and continue with the 'pack-objects' use case.\n+So long as a bundle's 'uninteresting' commits match that of the\n+revision cache, then the revision cache is completely appropriate;\n+with the length of the object list it can write a header and continue\n+with the 'pack-objects' use case.\n \n \n slicing bundles (mirror-sync)\n-- \ndebian.1.5.6.1\n"},{"id":"115475","messageId":"00f8798ca56481f207983f6f26fc5fda1f12f337.1244125128.git.sam@vilain.net","threadId":"19671","inReplyTo":"cover.1244125127.git.sam@vilain.net","subject":"[PATCH 7/7] revision cache: be even stricter with sort order","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-06-04T14:05:13Z","receivedAt":"2009-06-04T14:05:13Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"For sliced bundles, there must be absolutely no ambiguity at all about\nthe sort order. Define how to break ties, and describe why this\naffects mirror-sync.\n\nSigned-off-by: Sam Vilain \n---\n Documentation/technical/revision-cache.txt | 79 +++++++++++++++++++---------\n 1 files changed, 54 insertions(+), 25 deletions(-)\n\ndiff --git a/Documentation/technical/revision-cache.txt b/Documentation/technical/revision-cache.txt\nindex 0cd7b08..7aaab38 100644\n--- a/Documentation/technical/revision-cache.txt\n+++ b/Documentation/technical/revision-cache.txt\n@@ -14,7 +14,7 @@ A revision cache contains;\n - A list of objects which are referred to by any 'start' object, but\n not by crossing 'end' objects, including:\n \n- * position when sorted in --date-order\n+ * position when sorted in --date-order, with ties broken by SHA1\n \n * object ID\n \n@@ -33,9 +33,15 @@ A revision cache contains;\n 'end' object, but not reachable from the 'start' objects reachable\n from that 'end' object.\n \n- - a list of 'foreign end' objects, for which not all reachable\n- objects are in the object list, but can have reachability or a\n- 'newness' bitmap.\n+ - a list of 'foreign start' objects, for which not all reachable\n+ objects are in the object list, but can have reachability and\n+ 'newness' bitmaps.\n+\n+ - a list of object types for each object, in the order they appear\n+ in the object list.\n+\n+ - a list of object lengths for each object, in the order they appear\n+ in the object list.\n \n \n Start Objects and End Objects\n@@ -64,7 +70,9 @@ from the offset.\n this still only specifies an ordering for commit objects. Other\n objects will appear after the object which first refers to them. Tag\n objects are sorted as if they were commit objects with a single\n-parent, the object they tag.\n+parent, the object they tag. No object is allowed to appear before\n+another object which refers to it, unless it is a 'start' object.\n+Ties in the order are broken by SHA1.\n \n \n Included object hash table\n@@ -231,6 +239,23 @@ caches whether the object exists and is reachable from the 'start'\n objects which connect to those stacked caches.\n \n \n+Extending Revision Caches\n+^^^^^^^^^^^^^^^^^^^^^^^^^\n+\n+ rev_cache_extend( rev_cache, quasi_interesting[] )\n+\n+The function works on an existing revision cache, and calculates just\n+the 'reachability' and 'newness' bitmaps.\n+\n+These are calculated by marking the quasi_interesting[] commits as\n+interesting, the 'end' objects in the revision cache as\n+'uninteresting', and walking.\n+Objects which are encountered which exist in the revision cache are\n+converted to bits in the emitted bitmap, and the 'newness' bitmap is\n+built as with the normal case once the reachable 'end' objects are\n+known.\n+\n+\n receive-pack/pack-objects\n ~~~~~~~~~~~~~~~~~~~~~~~~~\n \n@@ -360,28 +385,32 @@ slicing bundles (mirror-sync)\n \n For 'slicing' bundles, a deterministic method is required for chopping\n up the list of objects, which can be calculated by any node which has\n-the 'interesting' commits.\n-\n-To determine the objects which fall within a given slice, the object\n-list must be enumerated and then divided evenly. As the compressed\n-size on one node cannot be reproduced on another node, the\n-uncompressed size of the object is used instead, with the hope that\n-slices will generally end up of roughly even size once compressed.\n-\n-To calculate the object boundaries, the list of objects in\n---date-order must first be tie-broken, eg for commits with the same\n-commitdate and topological order. If slices are allowed to be\n-sub-commit level, then objects between commits (ie blobs and trees)\n-are also sorted. Once this deterministic list has been built, then\n-all of the objects must be accessed to determine their length. The\n-objects which start within a given range are the ones in the slice.\n+the 'interesting' commits. As topological order is important, bundles\n+must only consist of objects from a single revision cache to be sliced\n+in this manner.\n+\n+To determine the objects which fall within a given slice, the new\n+object list in the bundle must be enumerated (such as by decompressing\n+and masking bitmaps) and then divided evenly, using the (masked)\n+object lengths list. As the compressed size on one node cannot be\n+reproduced on another node, the uncompressed size of the object is\n+used instead, with the hope that slices will generally end up of\n+roughly even size once compressed.\n+\n+The objects which start within a given range in this list of objects\n+are the ones in the slice. If slices are not allowed at the\n+sub-commit level, then the requirement to tie-break ordering of\n+non-commit/tag objects is relaxed, however the list of per-object\n+types is required to know where the boundaries are.\n \n For re-using deltas in sliced bundles, the delta base is looked up in\n-the deterministic list. If it has an earlier sequence, then the delta\n-can be safely re-used. If it has a later sequence, then the delta\n-must be resolved and then the object re-deltified/compressed, using\n-only objects with an earlier sequence (or in the returned pack) as a\n-base.\n+the deterministic list of objects. If it has an earlier sequence,\n+then the delta can be safely re-used. If it has a later sequence,\n+then the delta must be resolved and then the object\n+re-deltified/compressed, using only objects with an earlier sequence\n+(or in the returned pack) as a base.\n \n This requirement is so that a collection of 'sliced' bundles can\n successfully re-assemble, while still allowing them to be 'thin'.\n+Without thin packs, download spreading from multiple mirrors will\n+result in a much larger download.\n-- \ndebian.1.5.6.1\n"},{"id":"115476","messageId":"14c3b1136cea650af9a3274b260c0a708456a554.1244125128.git.sam@vilain.net","threadId":"19671","inReplyTo":"cover.1244125127.git.sam@vilain.net","subject":"[PATCH 6/7] revision cache: allow foreign 'start' commits","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-06-04T14:05:13Z","receivedAt":"2009-06-04T14:05:13Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"Usually the 'start' commits are always 'interesting' commits in a\nrevision query, however with the 'newness' bitmaps we can also use\nthem to mask out objects, ie 'uninteresting' commits. An index which\nwas useless, due to an unknown object existing in the 'uninteresting'\ncommit list can be converted to a useful one by building the bitmap of\n'reachable' and 'new' objects for that commit - without having to\ninsert new objects in the middle of the list, which would require\nrebuilding the entire index. So, there is a use case for storing\ninformation on 'start' objects which aren't actually in the object\nlist. Permit this case.\n\nThis is currently a work in progress; extension to how this affects\nthe use cases is not there yet.\n\nSigned-off-by: Sam Vilain \n---\n Documentation/technical/revision-cache.txt | 4 ++++\n 1 files changed, 4 insertions(+), 0 deletions(-)\n\ndiff --git a/Documentation/technical/revision-cache.txt b/Documentation/technical/revision-cache.txt\nindex e0adb26..0cd7b08 100644\n--- a/Documentation/technical/revision-cache.txt\n+++ b/Documentation/technical/revision-cache.txt\n@@ -33,6 +33,10 @@ A revision cache contains;\n 'end' object, but not reachable from the 'start' objects reachable\n from that 'end' object.\n \n+ - a list of 'foreign end' objects, for which not all reachable\n+ objects are in the object list, but can have reachability or a\n+ 'newness' bitmap.\n+\n \n Start Objects and End Objects\n -----------------------------\n-- \ndebian.1.5.6.1\n"},{"id":"115484","messageId":"cover.1244125127.git.sam@vilain.net","threadId":"19671","inReplyTo":null,"subject":"[PATCH 0/7] [GSoC2009] Revision cache / git-daemon caching plan","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-06-04T14:18:47Z","receivedAt":"2009-06-04T14:18:47Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"This patch series describes the structure of the object list cache\non-disk format. It is built successively from a very simple design -\njust an object list - to a version that allows for as many rev-list\noperations to be accelerated as possible, and potentially immediate\nstartup of full clone operations in the common case; ie skipping the\n\"Counting Objects\" and \"Compressing Objects\" phase once a matching\nindex is found.\n\nThe plan will be to implement each step incrementally, with a test-*.c\nfile along the way which tests the API provided by the revision cache\nAPI. While the revision cache format will change along the way, this\nwill not require an index format deprecation cycle, as integration with\nthe rest of git will not happen until the format is settled.\n\nThe plan is to aim for one of these API milestones completed per week.\nWhen complete, each commit will contain tests for the level of cache\nthat it delivers. Later milestones include joining the dots -\nintegrating with the 'rev-list' machinery and most importantly,\n'pack-objects'.\n\nErrata: the 'object list' and 'contents hash' will probably be\nre-worked to keep a separate SHA-1 and topological index list, to\nre-use existing fan-out code. This will be incorporated into the next\nversion.\n\nSam Vilain (7):\n revision-cache: define revision cache as simple list of revisions\n rev-cache: add on-disk format for fast reachability lookup\n rev-cache: add 'end' objects for caching 'uninteresting' lookups\n rev-cache: allow multiple 'start' objects per index\n revision cache: maps of 'new' objects\n revision cache: allow foreign 'start' commits\n revision cache: be even stricter with sort order\n\n Documentation/technical/revision-cache.txt | 416 ++++++++++++++++++++++++++++\n 1 files changed, 416 insertions(+), 0 deletions(-)\n create mode 100644 Documentation/technical/revision-cache.txt\n"},{"id":"115542","messageId":"m34ouu7h70.fsf@localhost.localdomain","threadId":"19671","inReplyTo":"cover.1244125127.git.sam@vilain.net","subject":"Re: [PATCH 0/7] [GSoC2009] Revision cache / git-daemon caching plan","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2009-06-05T16:56:27Z","receivedAt":"2009-06-05T16:56:27Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Sam Vilain writes:\n\n> This patch series describes the structure of the object list cache\n> on-disk format. It is built successively from a very simple design -\n> just an object list - to a version that allows for as many rev-list\n> operations to be accelerated as possible, and potentially immediate\n> startup of full clone operations in the common case; ie skipping the\n> \"Counting Objects\" and \"Compressing Objects\" phase once a matching\n> index is found.\n> \n> The plan will be to implement each step incrementally, with a test-*.c\n> file along the way which tests the API provided by the revision cache\n> API. While the revision cache format will change along the way, this\n> will not require an index format deprecation cycle, as integration with\n> the rest of git will not happen until the format is settled.\n> \n> The plan is to aim for one of these API milestones completed per week.\n> When complete, each commit will contain tests for the level of cache\n> that it delivers. Later milestones include joining the dots -\n> integrating with the 'rev-list' machinery and most importantly,\n> 'pack-objects'.\n\nI like this sharing not only completed code, but plans, designs (and\nstatus reports) with Git Development Community (i.e. git mailing\nlist). I like this very much.\n\n\nI'd like to ask if there any results of profiling git server\n(git-daemon) code: how much is spend on object enumeration this GSoC\nproject tries to make faster by the means of caching?\n\nAre there prepared benchmarks and tests to check if the code gives\ncorrect results, and to measure improvements brought by caching?\nWould it be possible to get some real-life statistics of git-daemon\nusage, so that you optimize against real scenarios?\n\n\nI wish you good work on git-daemon caching...\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"115553","messageId":"alpine.LFD.2.00.0906051406330.3906@xanadu.home","threadId":"19671","inReplyTo":"b054cddea58213268b872cf43c725960e6e2dc5b.1244125127.git.sam@vilain.net","subject":"Re: [PATCH 1/7] revision-cache: define revision cache as simple list of revisions","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-06-05T19:28:51Z","receivedAt":"2009-06-05T19:28:51Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 5 Jun 2009, Sam Vilain wrote:\n\n> The very first thing that we want out of the revision cache is to be\n> able to go from a commit to all of its referred objects. Define a\n> revision cache that includes just that.\n> \n> Signed-off-by: Sam Vilain \n\nComments below.\n\n> ---\n> Documentation/technical/revision-cache.txt | 260 ++++++++++++++++++++++++++++\n> 1 files changed, 260 insertions(+), 0 deletions(-)\n> create mode 100644 Documentation/technical/revision-cache.txt\n> \n> diff --git a/Documentation/technical/revision-cache.txt b/Documentation/technical/revision-cache.txt\n> new file mode 100644\n> index 0000000..cc18535\n> --- /dev/null\n> +++ b/Documentation/technical/revision-cache.txt\n> @@ -0,0 +1,260 @@\n> +Revision Cache Format\n> +=====================\n> +\n> +The revision cache is an on-disk format which allows for certain graph\n> +reachability operations to be answered quickly.\n> +\n> +A revision cache contains;\n> +\n> + - A 'start' object (ie, 'interesting' object ID)\n> +\n> + - A list of objects which are referred to by the 'start' object\n> +\n> + * position when sorted in --date-order\n> +\n> + * object ID\n\nDoes the object ID contain the object type or just the SHA1? Having the \nobject type quickly retrievable would be a significant gain as well.\n\n> +Start Object\n> +------------\n> +\n> +The 'start' object is the identifying key of the revision cache.\n> +\n> +\n> +Topological contents list\n> +-------------------------\n> +\n> +This list has fixed-length records, so the topological position into\n> +the list does not need to be stored in each record - it is implicit\n> +from the offset.\n> +\n> +--date-order is used as it is the strictest sort order available, but\n> +this still only specifies an ordering for commit objects. Other\n> +objects will appear after the object which first refers to them. Tag\n> +objects are sorted as if they were commit objects with a single\n> +parent, the object they tag.\n> +\n> +\n> +Use Cases\n> +---------\n> +In this section, the key functions and operations that this index is\n> +designed to answer are explored. For each, their efficiency is\n> +considered in terms of what must be carried out to calculate the\n> +answer.\n> +\n> +\n> +Determining Cache Suitability - rev_cache_suitable()\n> +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n> +\n> +This is an auxiliary function used by the other use cases, when \n\nwhen what?\n\n> +The function is:\n> +\n> + rev_cache_suitable( rev_cache, object )\n> +\n> +The check is simple and fast - it just compares the object to the\n> +'start' object in the revision cache.\n> +\n> +\n> +Revision Walker\n> +~~~~~~~~~~~~~~~\n> +\n> +The revision walker is the main user of this cache; there is the\n> +generic function of revision walking, as well as commands that want\n> +specific information which they normally derive from the revision\n> +walker output.\n> +\n> +\n> +Setting up the walker\n> +^^^^^^^^^^^^^^^^^^^^^\n> +\n> +The functions for this are (intentionally resembling the current\n> +revision walker API):\n> +\n> + rev_cache_init()\n> + rev_cache_add( interesting?, oid )\n> +\n> +As well as this setup, it is necessary to specify which options are\n> +required. Some API exists to do this, and the return value from\n> +'rev_cache_ok' is true if suitable caches were found for the\n> +information required, and false if it would require a graph traversal:\n> +\n> + rev_cache_options( ordered? )\n> + rev_cache_ok( ) : Bool\n> +\n> +The rev_cache_ok() function must open all available revision caches,\n> +and see if their 'interesting' object matches the single 'interesting'\n> +object passed to rev_cache_add(). If it matches, it returns true. If\n> +multiple 'interesting' objects were specified and 'ordered' is true,\n> +then the function returns false.\n> +\n> +If the ordering flag was set to false, then all of the 'interesting'\n> +objects must be found in separate revision caches.\n> +\n> +If any 'uninteresting' objects were passed, then the return value is\n> +always false.\n> +\n> +\n> +Returning objects\n> +^^^^^^^^^^^^^^^^^\n> +\n> +The 'rev_cache_fetch()' iterator returns entries from the topological\n> +list.\n> +\n> + rev_cache_fetch() : oid\n> +\n> +If returning objects from a single revision cache, it opens the \n\nopens what?\n\n> +Accelerating in-progress walking\n> +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n> +\n> +It is possible that during a revision iteration operation, a revision\n> +is discovered that may mean the rest of the revision walking can be\n> +achieved faster.\n> +\n> +In practice, this is likely to be implemented by making in-core cache\n> +entries for objects with revision caches prior to walking; then when\n> +encountered the special action can be taken.\n> +\n> +\n> +Creating Revision Caches\n> +~~~~~~~~~~~~~~~~~~~~~~~~\n> +\n> +Once the revision cache is setup via rev_cache_init() and\n> +an 'interesting' object added, then call:\n> +\n> + rev_cache_create( )\n> +\n> +This function will not work, if multiple 'interesting' objects are\n> +passed, or any 'uninteresting' objects were passed.\n> +\n> +This function must revision walk the commit graph, sorting in\n> +--date-order along the way, and may emit revisions as they are\n> +discovered to the topological object list.\n> +\n> +\n> +receive-pack/pack-objects\n> +~~~~~~~~~~~~~~~~~~~~~~~~~\n> +\n> +pack-objects when called from pack-objects is a special user of the\n ^\nAre you missing some punctuation here?\n\n> +revision cache; it has the extra requirements of wanting to know;\n> +\n> +* how many objects are between 'interesting' and 'uninteresting'\n> + objects, at the beginning of the run, to emit the pack header\n> +\n> +* for checking re-usability of deltas, whether the delta base object\n> + in the pack is in the received set of objects.\n> +\n> +* for 'thin' pack generation, whether the delta base object is in the\n> + received set of objects, -or- reachable from any 'uninteresting'\n> + objects\n> +\n> +* for 'shallow' clone, whether the delta base object is reachable\n> + without passing any of the 'uninteresting' objects\n> +\n> +The aim is for 'pack-objects' to be able to start returning objects\n> +immediately in the case where a suitable revision cache is returned,\n> +without waiting for revision counting or repacking.\n\nEverything that was said so far made lots of sense to me, up to this \nsection. I think that you should really limit the scope of the problem \nto object enumeration only and not dive so deep into pack-objects' \noperation. Having an efficient object enumeration cache that is 1) \nfast, 2) doesn't use up too much disk space and 3) keep itself up to \ndate automatically and transparently is already quite a challenge \nalready. Mixing pack-objects issues listed above into the mix is, I \nthink, a huge mistake and possibly a misunderstanding of the packing \nprocess. More comments below.\n\n> +Returning object counts\n> +^^^^^^^^^^^^^^^^^^^^^^^\n> +\n> +If the revision cache was suitable, eg for a complete fetch, then the\n> +number of objects can be obtained by counting the size of the object\n> +list.\n> +\n> +If multiple revision caches were used for multiple 'interesting'\n> +objects, then the number of objects can be obtained by building a hash\n> +table of all the objects in all of the caches, and returning the\n> +number of hash table entries.\n> +\n> +If 'uninteresting' objects were passed, no cache can be suitable.\n\nKnowing the number of objects early is not that useful. The only way \nyou can know that number is by counting all needed objects, and the \nproblem to solve here is really to provide that list of objects _fast_. \nThe pack-objects code already deals with building a hash of objects and \nthat takes no time compared to actually obtaining that list of objects \nin the first place.\n\n> +Re-using deltas\n> +^^^^^^^^^^^^^^^\n> +\n> +This applies to the 'Compressing Objects' phase, previously known as\n> +the 'Deltafying Objects' phase. Instead of searching for deltas, if\n> +we can be sure that the existing delta can be resolved on the remote,\n> +then we can re-use it.\n\nI don't see how the reachability cache could have anything to do with \nthis. Sure the criteria for reusing some delta data is for the base to \nbe part of the object set, or in the thin pack case, when the base is \nknown to be available on the remote side. But the delta and base has to \nalready exist locally in the _same_ pack, otherwise it simply doesn't \nexist and has to be computed. It is a common situation for a repository \nto have multiple packs for which deltas can be produced when crossing \nsource pack boundaries, and that fact simply cannot fit within an object \nenumeration cache.\n\n> +For the initial clone, this operation is simple - as objects are\n> +emitted, the delta from the packfile is re-used. If a loop is\n> +detected or the delta base is not in the returned set of objects, then\n> +the delta is first resolved.\n\nHow do you know you have a loop? A lot of thoughts went into the \ncurrent code to never get into a situation where loops could be \npossible. And that can only be inferred from the actual content of used \nobject packs. Again the enumeration cache cannot and should not be \nconcerned by such considerations as they will change on every repack.\n\n> +This implies that the list of objects is first loaded into a hash\n> +table prior to returning any objects; however this is probably\n> +acceptable as the entire list is in one stream and will load quickly.\n\nAgain this is duplication of already existing code.\n\n> +For later fetches, the revision cache is not appropriate as they will\n> +have 'uninteresting' objects set.\n> +\n> +\n> +Re-using deltas - 'thin' pack\n> +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n> +\n> +This case is much like the normal re-using deltas case, except there\n> +is the complete set of objects that the remote has claimed to have to\n> +consider.\n> +\n> +The cache is not yet sophisticated enough to assist with this use\n> +case.\n\nAnd it should not attempt anything in that direction. This is simply \nnot the right level for such considerations.\n\nPlease don't mess up the layers of abstractions. Creating a list of \nobjects is currently the biggest bottleneck for big clones. It is not \nthe object compression (delta) phase, it is not the pack creation \neither. The current code is smart enough not to delta objects it knows \ncan be found in source packs already, and it knows how to cull the list \nof deltas that needs to be computed to the strict minimum. And that \nrequires almost no time. What is really time consuming is to figure out \nthe damn object list in the first place. No need to reinvent what \nalready works well.\n\nIn other words, you should really concentrate on making 'git rev-list \n--objects' and 'git rev-list --objects-edge' instantaneous without \nhaving to parse any commit nor tree objects (at least for the part \nalready covered by the cache). And as new objects are added through \n'git add' and 'git commit' or 'git fetch' then the traditional object \nparsing would have to take place only up to the point where the cache \ncould take over, and update the cache for the non covered objects while \nat it. I think this is already quite a difficult problem already.\n\nWhat pack-objects would greatly benefit from is a facility that could \nprovide a list of objects with their SHA1, type, size and the 32-bit \nobject path hash given a list of \"have\" and \"want\" kind of refs. And so \nin a way that doesn't suck, which could mean in less than, say, 5 \nseconds per million objects. That's it, but that's hard. All the rest \nis already done and quite well optimized.\n\n\nNicolas\n"},{"id":"115569","messageId":"alpine.LFD.2.00.0906051628530.3906@xanadu.home","threadId":"19671","inReplyTo":"m34ouu7h70.fsf@localhost.localdomain","subject":"Re: [PATCH 0/7] [GSoC2009] Revision cache / git-daemon caching plan","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-06-05T20:58:36Z","receivedAt":"2009-06-05T20:58:36Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 5 Jun 2009, Jakub Narebski wrote:\n\n> I like this sharing not only completed code, but plans, designs (and\n> status reports) with Git Development Community (i.e. git mailing\n> list). I like this very much.\n> \n> \n> I'd like to ask if there any results of profiling git server\n> (git-daemon) code: how much is spend on object enumeration this GSoC\n> project tries to make faster by the means of caching?\n\nThe git daemon only forks and execs other processes. It is hardly using \nany measurable CPU itself.\n\nIf you want to profile or simply have a good feel for what happens \nduring a clone and clearly see what phase is problematic for the server \nthen do this:\n\n 1) cd to a local repository of your choice. The bigger the better, \n meaning that git itself is probably too small. Try the linux \n kernel, or a gcc mirror, or even better yet the gentoo repository.\n\n 2) run this:\n\n\tgit pack-objects --all-progress --revs --all --stdout \\\n\t\t< /dev/null > /dev/null\n\n 3) Sit and watch. And for extra fun you may even measure the time \n spent in each of the \"counting objects\", \"compressing objects\" and\n \"writing objects\" phases and compare them.\n\n\nNicolas\n"},{"id":"115683","messageId":"1244346575.9843.41.camel@maia.lan","threadId":"19671","inReplyTo":"alpine.LFD.2.00.0906051406330.3906@xanadu.home","subject":"Re: [PATCH 1/7] revision-cache: define revision cache as simple list of revisions","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-06-07T03:49:35Z","receivedAt":"2009-06-07T03:49:35Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"On Fri, 2009-06-05 at 15:28 -0400, Nicolas Pitre wrote:\n> > + - A list of objects which are referred to by the 'start' object\n> > +\n> > + * position when sorted in --date-order\n> > +\n> > + * object ID\n> \n> Does the object ID contain the object type or just the SHA1? Having the \n> object type quickly retrievable would be a significant gain as well.\n\nWell, one of the things I'm trying to avoid is adding information which\nisn't clearly supported by a use case. But now that you mention it I\nguess the type is quite useful and also quite small. What I could do is\nhave 4 bitmaps, one for each object type. That should be quite small\nand re-use the bitmap infrastructure used later.\n\n [...]\n> > +Use Cases\n> > +---------\n> > +In this section, the key functions and operations that this index is\n> > +designed to answer are explored. For each, their efficiency is\n> > +considered in terms of what must be carried out to calculate the\n> > +answer.\n> > +\n> > +\n> > +Determining Cache Suitability - rev_cache_suitable()\n> > +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n> > +\n> > +This is an auxiliary function used by the other use cases, when \n> \n> when what?\n\nWhoops. When deciding whether or not a revision cache is going to be\nuseful to help the current operation. This needs to be quick because we\nneed to identify whether to use a cache or keep going.\n\n> > +The function is:\n> > +\n> > + rev_cache_suitable( rev_cache, object )\n> > +\n> > +The check is simple and fast - it just compares the object to the\n> > +'start' object in the revision cache.\n> > +\n> > +\n [...]\n> > +Returning objects\n> > +^^^^^^^^^^^^^^^^^\n> > +\n> > +The 'rev_cache_fetch()' iterator returns entries from the topological\n> > +list.\n> > +\n> > + rev_cache_fetch() : oid\n> > +\n> > +If returning objects from a single revision cache, it opens the \n> \n> opens what?\n\nAgain sorry this got lost when I was re-arranging the document. It\nopens the revision cache and returns objects in the order they appear in\nthe cache's object list.\n\n\n [...]\n> > +receive-pack/pack-objects\n> > +~~~~~~~~~~~~~~~~~~~~~~~~~\n> > +\n> > +pack-objects when called from pack-objects is a special user of the\n> ^\n> Are you missing some punctuation here?\n\nIt should probably say \"when called from receive-pack\".\n\n> > +revision cache; it has the extra requirements of wanting to know;\n> > +\n> > +* how many objects are between 'interesting' and 'uninteresting'\n> > + objects, at the beginning of the run, to emit the pack header\n> > +\n> > +* for checking re-usability of deltas, whether the delta base object\n> > + in the pack is in the received set of objects.\n> > +\n> > +* for 'thin' pack generation, whether the delta base object is in the\n> > + received set of objects, -or- reachable from any 'uninteresting'\n> > + objects\n> > +\n> > +* for 'shallow' clone, whether the delta base object is reachable\n> > + without passing any of the 'uninteresting' objects\n> > +\n> > +The aim is for 'pack-objects' to be able to start returning objects\n> > +immediately in the case where a suitable revision cache is returned,\n> > +without waiting for revision counting or repacking.\n> \n> Everything that was said so far made lots of sense to me, up to this \n> section. I think that you should really limit the scope of the problem \n> to object enumeration only and not dive so deep into pack-objects' \n> operation.\n\n\n\n> Having an efficient object enumeration cache that is 1) \n> fast, 2) doesn't use up too much disk space and 3) keep itself up to \n> date automatically and transparently [...]\n\nLike the rest of git - the object graph, packs, etc - this design is\nbased around the concept of \"immutable data\". That is, the revision\ncache is defined by the objects it was computed from. Once the later\nstages of it are reached, the \"revision cache stacking\" comes into play\nto achieve automatic and transparent 'updating'. I considered designs\nwhich were not immutable data but decided that the update performance\nwould be too poor or suffer from locking issues.\n\n> > +Re-using deltas\n> > +^^^^^^^^^^^^^^^\n> > +\n> > +This applies to the 'Compressing Objects' phase, previously known as\n> > +the 'Deltafying Objects' phase. Instead of searching for deltas, if\n> > +we can be sure that the existing delta can be resolved on the remote,\n> > +then we can re-use it.\n> \n> I don't see how the reachability cache could have anything to do with \n> this. Sure the criteria for reusing some delta data is for the base to \n> be part of the object set, or in the thin pack case, when the base is \n> known to be available on the remote side. But the delta and base has to \n> already exist locally in the _same_ pack, otherwise it simply doesn't \n> exist and has to be computed. It is a common situation for a repository \n> to have multiple packs for which deltas can be produced when crossing \n> source pack boundaries, and that fact simply cannot fit within an object \n> enumeration cache.\n> \n> > +For the initial clone, this operation is simple - as objects are\n> > +emitted, the delta from the packfile is re-used. If a loop is\n> > +detected or the delta base is not in the returned set of objects, then\n> > +the delta is first resolved.\n> \n> How do you know you have a loop? A lot of thoughts went into the \n> current code to never get into a situation where loops could be \n> possible. And that can only be inferred from the actual content of used \n> object packs. Again the enumeration cache cannot and should not be \n> concerned by such considerations as they will change on every repack.\n> \n> > +This implies that the list of objects is first loaded into a hash\n> > +table prior to returning any objects; however this is probably\n> > +acceptable as the entire list is in one stream and will load quickly.\n> \n> Again this is duplication of already existing code.\n\nThere's no code to be duplicate yet. A lot of the above text is trying\nto summarise what happens in pack-objects, for the purposes of\nconsidering whether the revision cache can help with it. Delta loop\ndetection I'd considered, but decided not to discuss in the already\nquite long document.\n\n> Please don't mess up the layers of abstractions. Creating a list of \n> objects is currently the biggest bottleneck for big clones. It is not \n> the object compression (delta) phase, it is not the pack creation \n> either.\n [...]\n> In other words, you should really concentrate on making 'git rev-list \n> --objects' and 'git rev-list --objects-edge' instantaneous without \n> having to parse any commit nor tree objects (at least for the part \n> already covered by the cache). And as new objects are added through \n> 'git add' and 'git commit' or 'git fetch' then the traditional object \n> parsing would have to take place only up to the point where the cache \n> could take over, and update the cache for the non covered objects while \n> at it. I think this is already quite a difficult problem already.\n\nIt's a good thing, then, that this is exactly what the first milestones\nin the project are covering. \n\nWhat I don't understand though is that during initial clone the object\ncompression phase does take a lot of time, and that there have been\nreports that large initial clones use a lot of VM for the packfile to be\nsent. So what I'm doing is trying to answer the question about why we\ncan't just start streaming the pack as soon as we know how many objects\nwill be in it. All those other stages can happen in parallel - for\ninstance I would wager that it's far more efficient to detect loops as\nwe're streaming, as the packfile is accessed, rather than having to read\nseek object header in the packfile up front.\n\nIn summary, I'm trying to make sure that the revision cache contains\nwhatever information might help with making it start as soon as\npossible, where putting the information in is trivial.\n\nIf pack-objects integration is as small a win as you say - and I have no\nhard facts to dispute this - then when we come to that part and\ninvestigate I'm sure with the facts in hand we will agree on what\napproach to take.\n\n> What pack-objects would greatly benefit from is a facility that could \n> provide a list of objects with their SHA1, type, size\n\nWhich size? compressed, uncompressed? What does that win us? Again\nI'm trying to support all information with a use case.\n\n> and the 32-bit \n> object path hash\n\nI'm not sure what this means, can you refer me to some docs or relevant\nsource?\n\n> given a list of \"have\" and \"want\" kind of refs. And so \n> in a way that doesn't suck, which could mean in less than, say, 5 \n> seconds per million objects. That's it, but that's hard. All the rest \n> is already done and quite well optimized.\n\nThanks for your detailed commentary,\nSam.\n"},{"id":"115684","messageId":"1244347301.9843.52.camel@maia.lan","threadId":"19671","inReplyTo":"m34ouu7h70.fsf@localhost.localdomain","subject":"Re: [PATCH 0/7] [GSoC2009] Revision cache / git-daemon caching plan","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2009-06-07T04:01:41Z","receivedAt":"2009-06-07T04:01:41Z","isPatch":true,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"On Fri, 2009-06-05 at 09:56 -0700, Jakub Narebski wrote:\n> > The plan is to aim for one of these API milestones completed per week.\n> > When complete, each commit will contain tests for the level of cache\n> > that it delivers. Later milestones include joining the dots -\n> > integrating with the 'rev-list' machinery and most importantly,\n> > 'pack-objects'.\n> \n> I like this sharing not only completed code, but plans, designs (and\n> status reports) with Git Development Community (i.e. git mailing\n> list). I like this very much.\n> \n> \n> I'd like to ask if there any results of profiling git server\n> (git-daemon) code: how much is spend on object enumeration this GSoC\n> project tries to make faster by the means of caching?\n\nNo, but you're not the first to ask - I'll research this and include\nprofiling of it (obviously needing to descend into stages taken by\npack-objects/receive-packs, as Nicholas points out) in the next update I\nsend out.\n\n> Are there prepared benchmarks and tests to check if the code gives\n> correct results, and to measure improvements brought by caching?\n> Would it be possible to get some real-life statistics of git-daemon\n> usage, so that you optimize against real scenarios?\n\nIn terms of correct results - that will come down to the test cases\nwhich are written for it, and possibly extending the existing test cases\neg t5500-fetch-pack.sh\n\n> I wish you good work on git-daemon caching...\n\nThanks!\n\nSam.\n"},{"id":"115687","messageId":"alpine.LFD.2.00.0906070001150.3906@xanadu.home","threadId":"19671","inReplyTo":"1244346575.9843.41.camel@maia.lan","subject":"Re: [PATCH 1/7] revision-cache: define revision cache as simple list of revisions","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-06-07T05:43:58Z","receivedAt":"2009-06-07T05:43:58Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 7 Jun 2009, Sam Vilain wrote:\n\n> On Fri, 2009-06-05 at 15:28 -0400, Nicolas Pitre wrote:\n> > Please don't mess up the layers of abstractions. Creating a list of \n> > objects is currently the biggest bottleneck for big clones. It is not \n> > the object compression (delta) phase, it is not the pack creation \n> > either.\n> [...]\n> > In other words, you should really concentrate on making 'git rev-list \n> > --objects' and 'git rev-list --objects-edge' instantaneous without \n> > having to parse any commit nor tree objects (at least for the part \n> > already covered by the cache). And as new objects are added through \n> > 'git add' and 'git commit' or 'git fetch' then the traditional object \n> > parsing would have to take place only up to the point where the cache \n> > could take over, and update the cache for the non covered objects while \n> > at it. I think this is already quite a difficult problem already.\n> \n> It's a good thing, then, that this is exactly what the first milestones\n> in the project are covering. \n> \n> What I don't understand though is that during initial clone the object\n> compression phase does take a lot of time, and that there have been\n> reports that large initial clones use a lot of VM for the packfile to be\n> sent.\n\nDid you duplicate those results yourself?\n\nDid you also try out the simple bench test I suggested while responding \nto Jakub?\n\nFor example, let's take the Linux kernel repository as I have it handy \nhere. For the various phases I get:\n\nCounting objects = 25 seconds\nCompressing objects = 2 seconds\nWriting objects = 3 seconds\n\nA long compression phase is a sign of a really badly packed repository.\nThe solution to that is simply to repack. After that subsequent clones \nas well as further repacks will have much shorter compression phase as \nthe work that was performed in the first repack will be directly \nreusable.\n\n> So what I'm doing is trying to answer the question about why we\n> can't just start streaming the pack as soon as we know how many objects\n> will be in it. All those other stages can happen in parallel - for\n> instance I would wager that it's far more efficient to detect loops as\n> we're streaming, as the packfile is accessed, rather than having to read\n> seek object header in the packfile up front.\n\nMy stance on this is that it is fundamentally impossible to do \nefficiently, if at all. What we currently do is not loop detection but \nrather loop avoidance. And because your pack set is not a static thing \n(new packs are created or fetched, and sometimes they're repacked into a \nsingle pack for a while) then you simply can't have a stable cache of \nobject topology based on their storage into packs. This is simply not \nsome immutable data. Only object names and contents are immutable, \nnothing more.\n\nWhat I'm telling you is: in order to know how many objects the pack \nwhich is about to be created will contain, you need to count them. \nThis is what takes 25 seconds currently in the above example. Then a 2 \nsecond compression phase which could be even less if your repository is \nbetter packed than mine currently is. At which point the writing phase \nstarts and the pack header is streamed. So trying to stream the pack as \nsoon as you know how many objects it contains will save a big whoopee 2 \nseconds. This is nothing to go crazy about, really.\n\nYet, to be able to stream a pack right away, you still would need to \nknow _where_ to pick the pack data from. And in most cases this is not \nfrom a nice single pack but rather multiple ones. And some of those \npacks have objects which are duplicated into other packs. And yet by \nmixing pack data from multiple source packs, you gain new opportunities \nfor delta compression because you're now putting together objects which \nwere separated before and therefore couldn't create delta between them \npreviously (that's the 2 second phase above). You still must be careful \nduring that phase not to create delta loop, and to do that you must take \ninto account all the other deltas from existing source packs that you \nare going to not recompute but just copy straight into the new pack.\n\nAnd of course there is the delta depth limit to enforce. This means \nthat some rearrangements of deltas forces some objects which were deltas \npreviously to become undeltified, or new deltas against a shallower base \nobject. And the only way to know what form each object will take in \nthis context is again by going through the full compression phase which \nworks on a list of object which ordering is totally different from the \none that is used to actually store objects in the pack. In other words, \nyou cannot work out delta issues as you stream the pack because you \ndon't want to write objects in the pack with the same order used for \ndelta processing.\n\nWhy a different object ordering for storing in the pack? Because we want \nto create the best data layout possible in the new pack so future \nruntime access to that pack will be optimal. This often means that \nobjects are picked from existing packs in a non linear fashion but \nrather in a seemingly random way. This is because we want the most \nrecent commits to get the best IO patterns in a pack. However, when the \nrepository is updated through fetches or pushes, the newly obtained \npacks usually carry even more recent commits for which the bulk of \nreferenced objects are still to be found in older packs (this is why a \nfetch is so quick). So the more fetches or pushes are performed, the \nless efficient your repository becomes with regard to the most recent \ncommits. This is why a subsequent repack will reshuffle all objects so \nthat the most recent commit gets a linear IO pattern again by picking \nobjects from the most recent packs as well as from older packs and \nputting them all contiguously in the new pack. But again you cannot \nknow if those objects will be in delta form or not, or against which \nbase object before the compression phase is over.\n\nI hope you have a better idea now to answer the question about why we \ncan't just start streaming the pack as soon as we know how many objects \nwill be in it, and why all those other stages may not happen in \nparallel.\n\n> In summary, I'm trying to make sure that the revision cache contains\n> whatever information might help with making it start as soon as\n> possible, where putting the information in is trivial.\n> \n> If pack-objects integration is as small a win as you say - and I have no\n> hard facts to dispute this - then when we come to that part and\n> investigate I'm sure with the facts in hand we will agree on what\n> approach to take.\n\nGood. I'm glad you see things that way. Because, to me, even just the \nnotion of a good revision cache is not that simple.\n\n> > What pack-objects would greatly benefit from is a facility that could \n> > provide a list of objects with their SHA1, type, size\n> \n> Which size? compressed, uncompressed? What does that win us? Again\n> I'm trying to support all information with a use case.\n\nUncompressed. That information is used by the delta heuristics, and the \ncode currently does its best not to seek all over through delta chains \nto fetch that tiny bit of information if that can be avoided (have a \nlook at check_object() in builtin-pack-objects.c).\n\n> > and the 32-bit \n> > object path hash\n> \n> I'm not sure what this means, can you refer me to some docs or relevant\n> source?\n\nIf you don't know what that is, then I'm afraid you might be lacking \nsome background on the packing and delta strategy. I'd suggest you read \nDocumentation/technical/pack-heuristics.txt first, and then find out in \nthe commit logs for builtin-pack-objects.c (or even within the file \nitself) what has changed since then.\n\n\nNicolas\n"}]}