{"thread":{"id":"8303","subject":"[PATCH] sha1_file.c:rearrange_packed_git() should consider packs' object sizes","startedAt":"2007-05-24T22:20:48Z","lastAt":"2007-05-24T22:20:48Z","messageCount":1,"participants":["Dana How"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"43189","messageId":"46560FC0.4020204@gmail.com","threadId":"8303","inReplyTo":null,"subject":"[PATCH] sha1_file.c:rearrange_packed_git() should consider packs' object sizes","fromName":"Dana How","fromEmail":"danahow@gmail.com","sentAt":"2007-05-24T22:20:48Z","receivedAt":"2007-05-24T22:20:48Z","isPatch":true,"sender":{"key":"danahow@gmail.com","avatar":null},"body":"\nShawn O. Pearce wrote:\n> We might be able to fix this by altering the sort_pack function\n> in sha1_file.c to not only order by mtime, but also by the ratio\n> of the size of the .pack to the number of objects stored in it.\n> Any packfile with a high size/object ratio is likely to be what\n> Dana has been calling a \"metadata\" pack, holding things like tags,\n> commits, trees and small blobs.  Its these packfiles that we want\n> to search first, as they are the most likely to be accessed.\n>\n> By pushing the megablob packs to the end of our packed_git search\n> list we won't tend to scan their indexes, as most of our objects\n> will be found earlier in the search list.  Hence we will generally\n> avoid any costs associated with their indexes.\n\nSo change the sort keys in rearrange_packed_git()/sort_pack() to\n  local then alternate,\n  increasing \"deviation\",  <== NEW\n  decreasing mtime (new then old)\n\nEach packfile has a \"rank\",  which is the log10 of its average\nstored object size.  \"Deviation\" is the number of standard deviations\nthis number exceeds its mean,  rounded down and clipped at zero.\nDeviation should be 0 in normal use,  and positive for packfiles\nwith significant populations of huge blobs.\n\nThis definition of deviation is intended to override mtime\nonly when sufficiently significant.  Putting mtime before deviation\nin the sort key list would cause deviation to be irrelevant.\n\nSigned-off-by: Dana L. How <danahow@gmail.com>\n---\n Makefile    |    2 +-\n cache.h     |    1 +\n sha1_file.c |   26 +++++++++++++++++++++++++-\n 3 files changed, 27 insertions(+), 2 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 29243c6..45f0a52 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -383,7 +383,7 @@ BUILTIN_OBJS = \\\n \tbuiltin-pack-refs.o\n \n GITLIBS = $(LIB_FILE) $(XDIFF_LIB)\n-EXTLIBS = -lz\n+EXTLIBS = -lz -lm\n \n #\n # Platform specific tweaks\ndiff --git a/cache.h b/cache.h\nindex cd875bc..630cd89 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -437,6 +437,7 @@ extern struct packed_git {\n \tuint32_t num_objects;\n \tint index_version;\n \ttime_t mtime;\n+\tint deviation;\n \tint pack_fd;\n \tint pack_local;\n \tunsigned char sha1[20];\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 12d2ef2..1565d91 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -6,6 +6,7 @@\n  * This handles basic git sha1 object files - packing, unpacking,\n  * creation etc.\n  */\n+#include <math.h>\n #include \"cache.h\"\n #include \"delta.h\"\n #include \"pack.h\"\n@@ -869,6 +870,14 @@ static int sort_pack(const void *a_, const void *b_)\n \t\treturn -st;\n \n \t/*\n+\t * Packs with large \"deviation\" should be searched last.\n+\t * Such packs have significantly larger blobs.\n+\t */\n+\tst = a->deviation - b->deviation;\n+\tif (st)\n+\t\treturn st;\n+\n+\t/*\n \t * Younger packs tend to contain more recent objects,\n \t * and more recent objects tend to get accessed more\n \t * often.\n@@ -884,6 +893,7 @@ static void rearrange_packed_git(void)\n {\n \tstruct packed_git **ary, *p;\n \tint i, n;\n+\tfloat sum1 = 0, sum2 = 0, mean, sigma;\n \n \tfor (n = 0, p = packed_git; p; p = p->next)\n \t\tn++;\n@@ -892,8 +902,22 @@ static void rearrange_packed_git(void)\n \n \t/* prepare an array of packed_git for easier sorting */\n \tary = xcalloc(n, sizeof(struct packed_git *));\n-\tfor (n = 0, p = packed_git; p; p = p->next)\n+\tfor (n = 0, p = packed_git; p; p = p->next) {\n+\t\t/* this is the log10 of the average object size (almost) */\n+\t\tfloat rank = log10((p->pack_size + 1.0) / (p->num_objects + 1.0));\n+\t\tsum1 += rank;\n+\t\tsum2 += rank * rank;\n \t\tary[n++] = p;\n+\t}\n+\tmean = sum1 / n;\n+\tsigma = sqrt(sum2 / n - mean * mean);\n+\tfor (p = packed_git; p; p = p->next) {\n+\t\tfloat rank = log10((p->pack_size + 1.0) / (p->num_objects + 1.0));\n+\t\tint deviation = sigma > 0 ? floor((rank - mean) / sigma) : 0;\n+\t\tif ( deviation < 0 )\n+\t\t\tdeviation = 0;\n+\t\tp->deviation = deviation;\n+\t}\n \n \tqsort(ary, n, sizeof(struct packed_git *), sort_pack);\n \n-- \n1.5.2.762.gd8c6-dirty\n"}]}