{"thread":{"id":"8157","subject":"Re: [RFC] Optimize diff-delta.c","startedAt":"2007-05-14T20:43:17Z","lastAt":"2007-05-14T20:43:17Z","messageCount":1,"participants":["Martin Koegler"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"42164","messageId":"11791753973509-git-send-email-mkoegler@auto.tuwien.ac.at","threadId":"8157","inReplyTo":null,"subject":"Re: [RFC] Optimize diff-delta.c","fromName":"Martin Koegler","fromEmail":"mkoegler@auto.tuwien.ac.at","sentAt":"2007-05-14T20:43:17Z","receivedAt":"2007-05-14T20:43:17Z","isPatch":false,"sender":{"key":"mkoegler@auto.tuwien.ac.at","avatar":null},"body":"git-pack-objects: cache small deltas between big objects\n\n---\nOn Mon, 14 May 2007, Nicolas Pitre wrote:\n> > I did some tests on differenent machines:\n> > \n> > - attached patch\n> >    Total 6452 (delta 4581), reused 1522 (delta 0)\n> >    11354.38user 5451.60system 4:40:09elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n> >    0inputs+0outputs (0major+1371504762minor)pagefaults 0swaps\n> >    =>75 MB pack size\n> \n> This is quite weird.  I wonder what might cause such a large difference \n> in pack size.\n> \n> Your first patch is probably faster due to the use of memcmp() which is \n> certainly highly optimized, more than the comparison loop we have.  It \n> is unfortunate that there is no library function to find the number of \n> identical bytes between two buffers.  Or is there some?\n\nAs far as I know, no.\n\n> But the size difference?  That has certainly something to do with your \n> data set since your patch makes no significant difference on the git.git \n> nor the Linux kernel repos.  Would it be possible for me to have a copy \n> of your repo for further analysis?\n\nI generate my repository by dumping a database. A script dumps a\nfew tables with mysqldump into per table files and commits them.\nThe dump file of each tables uses the one insert per line syntax, so \nnearly all lines of a file share a >=27 bytes prefix. A diffstat to \nthe previous commit typically shows, that some \nhundred lines are added at the end of each file.\n\nA statistic of dropped hash table entries of the first thousand objects \nin create_delta_index shows, that up to 41 % are dropped, eg:\nDropping: 3404731 of 8540915 (39.86 %)\nDropping: 3397330 of 8525886 (39.85 %)\nDropping: 3388813 of 8509648 (39.82 %)\nDropping: 3381134 of 8494317 (39.80 %)\nDropping: 3381128 of 8494294 (39.80 %)\nDropping: 3375786 of 8483589 (39.79 %)\nDropping: 3369725 of 8472206 (39.77 %)\nDropping: 3364377 of 8460707 (39.76 %)\nDropping: 3358120 of 8447813 (39.75 %)\nDropping: 3351482 of 8435015 (39.73 %)\nDropping: 3351481 of 8435007 (39.73 %)\nDropping: 3351478 of 8435000 (39.73 %)\nDropping: 3346193 of 8424055 (39.72 %)\nDropping: 3339952 of 8410503 (39.71 %)\nDropping: 3334324 of 8398253 (39.70 %)\nDropping: 3370085 of 8384362 (40.19 %)\nDropping: 3362979 of 8369151 (40.18 %)\nDropping: 3354905 of 8353432 (40.16 %)\n\nSo the current code will probably not always find the best match. As\nmy last patch can match nearly the whole file after finding a match,\nthe missing entries will not have a big influence.\n\nAs a side effect, my last patch increased the total running time and\nminor page faults compared to the orignal version. I can not explain,\nwhy this happens. The deltifing phase needs to read and uncompress the\nsame data. The only difference I can image, is, that different objects are selected\nas delta base for the writing phase, which require more reading time (eg. because\nthey are bigger or have a longer delta chain in their current pack file).\n\nAs a large amount of CPU time is spent in writing the pack file (reading\nall blobs again and applying the delta chain, computing the\ndelta_index and recomputing the delta) and the deltas are small, \nI tried to cache the deltas from try_delta,\nif the compared blobs are big (and therefore the delta operation is\nexpensive):\n\n- my last patch + this patch\n  Total 6452 (delta 4581), reused 1522 (delta 0)\n  4176.04user 322.10system 1:14:58elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n  0inputs+0outputs (0major+83869085minor)pagefaults 0swaps\n  => 75MB\n\n builtin-pack-objects.c |   35 +++++++++++++++++++++++++----------\n 1 files changed, 25 insertions(+), 10 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 966f843..fe19272 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -35,6 +35,7 @@ struct object_entry {\n \tstruct object_entry *delta_sibling; /* other deltified objects who\n \t\t\t\t\t     * uses the same base as me\n \t\t\t\t\t     */\n+\tvoid *delta_data;\t/* cached delta (uncompressed) */\n \tunsigned long delta_size;\t/* delta data size (uncompressed) */\n \tenum object_type type;\n \tenum object_type in_pack_type;\t/* could be delta */\n@@ -445,17 +446,24 @@ static unsigned long write_object(struct sha1file *f,\n \t}\n \n \tif (!to_reuse) {\n-\t\tbuf = read_sha1_file(entry->sha1, &type, &size);\n-\t\tif (!buf)\n-\t\t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n-\t\tif (size != entry->size)\n-\t\t\tdie(\"object %s size inconsistency (%lu vs %lu)\",\n-\t\t\t    sha1_to_hex(entry->sha1), size, entry->size);\n-\t\tif (entry->delta) {\n-\t\t\tbuf = delta_against(buf, size, entry);\n+\t\tif (entry->delta_data) {\n+\t\t\tbuf = entry->delta_data;\n \t\t\tsize = entry->delta_size;\n \t\t\tobj_type = (allow_ofs_delta && entry->delta->offset) ?\n-\t\t\t\tOBJ_OFS_DELTA : OBJ_REF_DELTA;\n+\t\t\t\t\tOBJ_OFS_DELTA : OBJ_REF_DELTA;\n+\t\t} else {\n+\t\t\tbuf = read_sha1_file(entry->sha1, &type, &size);\n+\t\t\tif (!buf)\n+\t\t\t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n+\t\t\tif (size != entry->size)\n+\t\t\t\tdie(\"object %s size inconsistency (%lu vs %lu)\",\n+\t\t\t\t    sha1_to_hex(entry->sha1), size, entry->size);\n+\t\t\tif (entry->delta) {\n+\t\t\t\tbuf = delta_against(buf, size, entry);\n+\t\t\t\tsize = entry->delta_size;\n+\t\t\t\tobj_type = (allow_ofs_delta && entry->delta->offset) ?\n+\t\t\t\t\tOBJ_OFS_DELTA : OBJ_REF_DELTA;\n+\t\t\t}\n \t\t}\n \t\t/*\n \t\t * The object header is a byte of 'type' followed by zero or\n@@ -1359,10 +1367,17 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \tif (!delta_buf)\n \t\treturn 0;\n \n+\tif (trg_entry->delta_data)\n+\t\tfree (trg_entry->delta_data);\n+\ttrg_entry->delta_data = 0;\n \ttrg_entry->delta = src_entry;\n \ttrg_entry->delta_size = delta_size;\n \ttrg_entry->depth = src_entry->depth + 1;\n-\tfree(delta_buf);\n+\t/* cache delta, if objects are large enough compared to delta size */\n+\tif ((src_size >> 20) + (trg_size >> 21) > (delta_size >> 10))\n+\t\ttrg_entry->delta_data = delta_buf;\n+\telse\n+\t\tfree(delta_buf);\n \treturn 1;\n }\n \n-- \n1.5.1.4.g01b3\n"}]}