{"thread":{"id":"7697","subject":"[PATCH 9/9] pack-objects: better check_object() performances","startedAt":"2007-04-16T16:32:13Z","lastAt":"2007-04-16T16:32:13Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":9},"messages":[{"id":"39552","messageId":"alpine.LFD.0.98.0704161231580.4504@xanadu.home","threadId":"7697","inReplyTo":null,"subject":"[PATCH 9/9] pack-objects: better check_object() performances","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-16T16:32:13Z","receivedAt":"2007-04-16T16:32:13Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"With large amount of objects, check_object() is really trashing the pack\nsliding map and the filesystem cache.  It has a completely random access\npattern especially with old objects where delta replay jumps back and\nforth all over the pack.\n\nThis patch improves things by:\n\n 1) sorting objects by their offset in pack before calling check_object()\n    so the pack access pattern is linear;\n\n 2) recording the object type at add_object_entry() time since it is\n    already known in most cases;\n\n 3) recording the pack offset even for preferred_base objects;\n\n 4) avoid calling sha1_object_info() if all possible.\n\nThis limits pack accesses to the bare minimum and makes them perfectly\nlinear.\n\nIn the process check_object() was made more clear (to me at least).\n\nNote: I thought about walking the sorted_by_offset list backward in\nget_object_details() so if a pack happens to be larger than the available\nfile cache, then the cache would have been populated with useful data from\nthe beginning of the pack already when find_deltas() is called.  Strangely,\ntesting (on Linux) showed absolutely no performance difference.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n builtin-pack-objects.c |  206 +++++++++++++++++++++++++++++-------------------\n 1 files changed, 126 insertions(+), 80 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 7100a76..19fae4c 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -813,7 +813,8 @@ static unsigned name_hash(const char *name)\n \treturn hash;\n }\n \n-static int add_object_entry(const unsigned char *sha1, unsigned hash, int exclude)\n+static int add_object_entry(const unsigned char *sha1, enum object_type type,\n+\t\t\t    unsigned hash, int exclude)\n {\n \tstruct object_entry *entry;\n \tstruct packed_git *p, *found_pack = NULL;\n@@ -831,19 +832,19 @@ static int add_object_entry(const unsigned char *sha1, unsigned hash, int exclud\n \t\treturn 0;\n \t}\n \n-\tif (!exclude) {\n-\t\tfor (p = packed_git; p; p = p->next) {\n-\t\t\toff_t offset = find_pack_entry_one(sha1, p);\n-\t\t\tif (offset) {\n-\t\t\t\tif (incremental)\n-\t\t\t\t\treturn 0;\n-\t\t\t\tif (local && !p->pack_local)\n-\t\t\t\t\treturn 0;\n-\t\t\t\tif (!found_pack) {\n-\t\t\t\t\tfound_offset = offset;\n-\t\t\t\t\tfound_pack = p;\n-\t\t\t\t}\n+\tfor (p = packed_git; p; p = p->next) {\n+\t\toff_t offset = find_pack_entry_one(sha1, p);\n+\t\tif (offset) {\n+\t\t\tif (!found_pack) {\n+\t\t\t\tfound_offset = offset;\n+\t\t\t\tfound_pack = p;\n \t\t\t}\n+\t\t\tif (exclude)\n+\t\t\t\tbreak;\n+\t\t\tif (incremental)\n+\t\t\t\treturn 0;\n+\t\t\tif (local && !p->pack_local)\n+\t\t\t\treturn 0;\n \t\t}\n \t}\n \n@@ -856,6 +857,8 @@ static int add_object_entry(const unsigned char *sha1, unsigned hash, int exclud\n \tmemset(entry, 0, sizeof(*entry));\n \thashcpy(entry->sha1, sha1);\n \tentry->hash = hash;\n+\tif (type)\n+\t\tentry->type = type;\n \tif (exclude)\n \t\tentry->preferred_base = 1;\n \telse\n@@ -1008,7 +1011,9 @@ static void add_pbase_object(struct tree_desc *tree,\n \t\t\treturn;\n \t\tif (name[cmplen] != '/') {\n \t\t\tunsigned hash = name_hash(fullname);\n-\t\t\tadd_object_entry(entry.sha1, hash, 1);\n+\t\t\tadd_object_entry(entry.sha1,\n+\t\t\t\t\t S_ISDIR(entry.mode) ? OBJ_TREE : OBJ_BLOB,\n+\t\t\t\t\t hash, 1);\n \t\t\treturn;\n \t\t}\n \t\tif (S_ISDIR(entry.mode)) {\n@@ -1079,7 +1084,7 @@ static void add_preferred_base_object(const char *name, unsigned hash)\n \tcmplen = name_cmp_len(name);\n \tfor (it = pbase_tree; it; it = it->next) {\n \t\tif (cmplen == 0) {\n-\t\t\tadd_object_entry(it->pcache.sha1, 0, 1);\n+\t\t\tadd_object_entry(it->pcache.sha1, OBJ_TREE, 0, 1);\n \t\t}\n \t\telse {\n \t\t\tstruct tree_desc tree;\n@@ -1121,87 +1126,105 @@ static void add_preferred_base(unsigned char *sha1)\n \n static void check_object(struct object_entry *entry)\n {\n-\tif (entry->in_pack && !entry->preferred_base) {\n+\tif (entry->in_pack) {\n \t\tstruct packed_git *p = entry->in_pack;\n \t\tstruct pack_window *w_curs = NULL;\n-\t\tunsigned long size, used;\n+\t\tconst unsigned char *base_ref = NULL;\n+\t\tstruct object_entry *base_entry;\n+\t\tunsigned long used, used_0;\n \t\tunsigned int avail;\n-\t\tunsigned char *buf;\n-\t\tstruct object_entry *base_entry = NULL;\n+\t\toff_t ofs;\n+\t\tunsigned char *buf, c;\n \n \t\tbuf = use_pack(p, &w_curs, entry->in_pack_offset, &avail);\n \n-\t\t/* We want in_pack_type even if we do not reuse delta.\n+\t\t/*\n+\t\t * We want in_pack_type even if we do not reuse delta.\n \t\t * There is no point not reusing non-delta representations.\n \t\t */\n \t\tused = unpack_object_header_gently(buf, avail,\n-\t\t\t\t\t\t   &entry->in_pack_type, &size);\n+\t\t\t\t\t\t   &entry->in_pack_type,\n+\t\t\t\t\t\t   &entry->size);\n \n-\t\t/* Check if it is delta, and the base is also an object\n-\t\t * we are going to pack.  If so we will reuse the existing\n-\t\t * delta.\n+\t\t/*\n+\t\t * Determine if this is a delta and if so whether we can\n+\t\t * reuse it or not.  Otherwise let's find out as cheaply as\n+\t\t * possible what the actual type and size for this object is.\n \t\t */\n-\t\tif (!no_reuse_delta) {\n-\t\t\tunsigned char c;\n-\t\t\tconst unsigned char *base_name;\n-\t\t\toff_t ofs;\n-\t\t\tunsigned long used_0;\n-\t\t\t/* there is at least 20 bytes left in the pack */\n-\t\t\tswitch (entry->in_pack_type) {\n-\t\t\tcase OBJ_REF_DELTA:\n-\t\t\t\tbase_name = use_pack(p, &w_curs,\n-\t\t\t\t\tentry->in_pack_offset + used, NULL);\n-\t\t\t\tused += 20;\n-\t\t\t\tbreak;\n-\t\t\tcase OBJ_OFS_DELTA:\n-\t\t\t\tbuf = use_pack(p, &w_curs,\n-\t\t\t\t\tentry->in_pack_offset + used, NULL);\n-\t\t\t\tused_0 = 0;\n-\t\t\t\tc = buf[used_0++];\n-\t\t\t\tofs = c & 127;\n-\t\t\t\twhile (c & 128) {\n-\t\t\t\t\tofs += 1;\n-\t\t\t\t\tif (!ofs || MSB(ofs, 7))\n-\t\t\t\t\t\tdie(\"delta base offset overflow in pack for %s\",\n-\t\t\t\t\t\t    sha1_to_hex(entry->sha1));\n-\t\t\t\t\tc = buf[used_0++];\n-\t\t\t\t\tofs = (ofs << 7) + (c & 127);\n-\t\t\t\t}\n-\t\t\t\tif (ofs >= entry->in_pack_offset)\n-\t\t\t\t\tdie(\"delta base offset out of bound for %s\",\n+\t\tswitch (entry->in_pack_type) {\n+\t\tdefault:\n+\t\t\t/* Not a delta hence we've already got all we need. */\n+\t\t\tentry->type = entry->in_pack_type;\n+\t\t\tentry->in_pack_header_size = used;\n+\t\t\tunuse_pack(&w_curs);\n+\t\t\treturn;\n+\t\tcase OBJ_REF_DELTA:\n+\t\t\tif (!no_reuse_delta && !entry->preferred_base)\n+\t\t\t\tbase_ref = use_pack(p, &w_curs,\n+\t\t\t\t\t\tentry->in_pack_offset + used, NULL);\n+\t\t\tentry->in_pack_header_size = used + 20;\n+\t\t\tbreak;\n+\t\tcase OBJ_OFS_DELTA:\n+\t\t\tbuf = use_pack(p, &w_curs,\n+\t\t\t\t       entry->in_pack_offset + used, NULL);\n+\t\t\tused_0 = 0;\n+\t\t\tc = buf[used_0++];\n+\t\t\tofs = c & 127;\n+\t\t\twhile (c & 128) {\n+\t\t\t\tofs += 1;\n+\t\t\t\tif (!ofs || MSB(ofs, 7))\n+\t\t\t\t\tdie(\"delta base offset overflow in pack for %s\",\n \t\t\t\t\t    sha1_to_hex(entry->sha1));\n-\t\t\t\tofs = entry->in_pack_offset - ofs;\n-\t\t\t\tbase_name = find_packed_object_name(p, ofs);\n-\t\t\t\tused += used_0;\n-\t\t\t\tbreak;\n-\t\t\tdefault:\n-\t\t\t\tbase_name = NULL;\n+\t\t\t\tc = buf[used_0++];\n+\t\t\t\tofs = (ofs << 7) + (c & 127);\n \t\t\t}\n-\t\t\tif (base_name)\n-\t\t\t\tbase_entry = locate_object_entry(base_name);\n+\t\t\tif (ofs >= entry->in_pack_offset)\n+\t\t\t\tdie(\"delta base offset out of bound for %s\",\n+\t\t\t\t    sha1_to_hex(entry->sha1));\n+\t\t\tofs = entry->in_pack_offset - ofs;\n+\t\t\tif (!no_reuse_delta && !entry->preferred_base)\n+\t\t\t\tbase_ref = find_packed_object_name(p, ofs);\n+\t\t\tentry->in_pack_header_size = used + used_0;\n+\t\t\tbreak;\n \t\t}\n-\t\tunuse_pack(&w_curs);\n-\t\tentry->in_pack_header_size = used;\n \n-\t\tif (base_entry) {\n-\n-\t\t\t/* Depth value does not matter - find_deltas()\n-\t\t\t * will never consider reused delta as the\n-\t\t\t * base object to deltify other objects\n-\t\t\t * against, in order to avoid circular deltas.\n+\t\tif (base_ref && (base_entry = locate_object_entry(base_ref))) {\n+\t\t\t/*\n+\t\t\t * If base_ref was set above that means we wish to\n+\t\t\t * reuse delta data, and we even found that base\n+\t\t\t * in the list of objects we want to pack. Goodie!\n+\t\t\t *\n+\t\t\t * Depth value does not matter - find_deltas() will\n+\t\t\t * never consider reused delta as the base object to\n+\t\t\t * deltify other objects against, in order to avoid\n+\t\t\t * circular deltas.\n \t\t\t */\n-\n-\t\t\t/* uncompressed size of the delta data */\n-\t\t\tentry->size = size;\n-\t\t\tentry->delta = base_entry;\n \t\t\tentry->type = entry->in_pack_type;\n-\n+\t\t\tentry->delta = base_entry;\n \t\t\tentry->delta_sibling = base_entry->delta_child;\n \t\t\tbase_entry->delta_child = entry;\n+\t\t\tunuse_pack(&w_curs);\n+\t\t\treturn;\n+\t\t}\n \n+\t\tif (entry->type) {\n+\t\t\t/*\n+\t\t\t * This must be a delta and we already know what the\n+\t\t\t * final object type is.  Let's extract the actual\n+\t\t\t * object size from the delta header.\n+\t\t\t */\n+\t\t\tentry->size = get_size_from_delta(p, &w_curs,\n+\t\t\t\t\tentry->in_pack_offset + entry->in_pack_header_size);\n+\t\t\tunuse_pack(&w_curs);\n \t\t\treturn;\n \t\t}\n-\t\t/* Otherwise we would do the usual */\n+\n+\t\t/*\n+\t\t * No choice but to fall back to the recursive delta walk\n+\t\t * with sha1_object_info() to find about the object type\n+\t\t * at this point...\n+\t\t */\n+\t\tunuse_pack(&w_curs);\n \t}\n \n \tentry->type = sha1_object_info(entry->sha1, &entry->size);\n@@ -1210,14 +1233,37 @@ static void check_object(struct object_entry *entry)\n \t\t    sha1_to_hex(entry->sha1));\n }\n \n+static int pack_offset_sort(const void *_a, const void *_b)\n+{\n+\tconst struct object_entry *a = *(struct object_entry **)_a;\n+\tconst struct object_entry *b = *(struct object_entry **)_b;\n+\n+\t/* avoid filesystem trashing with loose objects */\n+\tif (!a->in_pack && !b->in_pack)\n+\t\treturn hashcmp(a->sha1, b->sha1);\n+\n+\tif (a->in_pack < b->in_pack)\n+\t\treturn -1;\n+\tif (a->in_pack > b->in_pack)\n+\t\treturn 1;\n+\treturn a->in_pack_offset < b->in_pack_offset ? -1 :\n+\t\t\t(a->in_pack_offset > b->in_pack_offset);\n+}\n+\n static void get_object_details(void)\n {\n \tuint32_t i;\n-\tstruct object_entry *entry;\n+\tstruct object_entry **sorted_by_offset;\n+\n+\tsorted_by_offset = xcalloc(nr_objects, sizeof(struct object_entry *));\n+\tfor (i = 0; i < nr_objects; i++)\n+\t\tsorted_by_offset[i] = objects + i;\n+\tqsort(sorted_by_offset, nr_objects, sizeof(*sorted_by_offset), pack_offset_sort);\n \n \tprepare_pack_ix();\n-\tfor (i = 0, entry = objects; i < nr_objects; i++, entry++)\n-\t\tcheck_object(entry);\n+\tfor (i = 0; i < nr_objects; i++)\n+\t\tcheck_object(sorted_by_offset[i]);\n+\tfree(sorted_by_offset);\n }\n \n static int type_size_sort(const void *_a, const void *_b)\n@@ -1520,20 +1566,20 @@ static void read_object_list_from_stdin(void)\n \n \t\thash = name_hash(line+41);\n \t\tadd_preferred_base_object(line+41, hash);\n-\t\tadd_object_entry(sha1, hash, 0);\n+\t\tadd_object_entry(sha1, 0, hash, 0);\n \t}\n }\n \n static void show_commit(struct commit *commit)\n {\n-\tadd_object_entry(commit->object.sha1, 0, 0);\n+\tadd_object_entry(commit->object.sha1, OBJ_COMMIT, 0, 0);\n }\n \n static void show_object(struct object_array_entry *p)\n {\n \tunsigned hash = name_hash(p->name);\n \tadd_preferred_base_object(p->name, hash);\n-\tadd_object_entry(p->item->sha1, hash, 0);\n+\tadd_object_entry(p->item->sha1, p->item->type, hash, 0);\n }\n \n static void show_edge(struct commit *commit)\n-- \n1.5.1.1.781.g65e8\n"}]}