{"thread":{"id":"7513","subject":"(unknown)","startedAt":"2007-04-04T16:59:44Z","lastAt":"2007-04-04T16:59:44Z","messageCount":1,"participants":["Geert Bosch"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"38638","messageId":"20070404165944.E4D7848CC08@nile.gnat.com","threadId":"7513","inReplyTo":null,"subject":"(unknown)","fromName":"Geert Bosch","fromEmail":"bosch@gnat.com","sentAt":"2007-04-04T16:59:44Z","receivedAt":"2007-04-04T16:59:44Z","isPatch":false,"sender":{"key":"bosch@gnat.com","avatar":null},"body":"From: Geert Bosch <bosch@gnat.com>\nDate: Mon, 2 Apr 2007 11:24:46 +0200\nSubject: [PATCH] find_pack_entry_one: Use interpolation search for finding objects in the pack index.\n\nAlso be careful about avoiding overflow in signed integer arithmetic.\n\nSigned-off-by: Geert Bosch <bosch@gnat.com>\n---\nThis patch is what I used in my experiments before proposing an\nalternative file format for the index.  This gives about a 2.5%\nspeed-up for git-rev-list --all on the Linux repository,\nwhile not changing anything at all for small repositories.\nThese tests were done on a Core 2 Duo MacBook Pro with Mac OS X.\n\nWhile this passes the test suite, I'm not sure it should be applied,\nbecause it doesn't really address the issues for very large repositories\nwith large numbers of pack files.\n\n  -Geert\n\n sha1_file.c |   37 ++++++++++++++++++++++++++++++++-----\n 1 files changed, 32 insertions(+), 5 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 9c26038..e463710 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1547,14 +1547,39 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\t\t\t  struct packed_git *p)\n {\n \tconst uint32_t *level1_ofs = p->index_data;\n-\tint hi = ntohl(level1_ofs[*sha1]);\n-\tint lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));\n+\tconst unsigned char level1_key = sha1[0];\n+\tconst unsigned int level2_key =  (sha1[1] << 16) + (sha1[2] << 8)\n+\t    + sha1[3];\n+\tuint32_t hi = ntohl(level1_ofs[level1_key]);\n+\tuint32_t lo = !level1_key ? 0 : ntohl(level1_ofs[level1_key - 1]);\n+\tuint32_t mi = ((hi - lo) * (level2_key >> 13) >> 11)  + lo;\n \tconst unsigned char *index = p->index_data;\n+\tconst int ents = hi - lo;\n+\n+        uint32_t try;\n \n \tindex += 4 * 256;\n \n-\tdo {\n-\t\tint mi = (lo + hi) / 2;\n+        if (ents < 0xffffff)\n+        do {\n+\t\tint ofs = 24 * mi + 4;\n+\n+\t\ttry = ntohl(*((uint32_t *) (index + ofs))) & 0xffffff;\n+\n+\t\tif (try < level2_key) {\n+\t\t\tlo = mi + 1;\n+\t\t\tmi = lo + (((level2_key - try) >> 16) * ents >> 8);\n+\t\t\tif (mi >= hi || mi < lo) mi = hi - 1;\n+\t\t}\n+\t\telse if (try > level2_key)\n+\t\t{\n+\t\t\thi = mi;\n+\t\t\tmi = hi - 1 - (((try - level2_key) >> 16) * ents >> 8);\n+\t\t\tif (mi < lo || mi >= hi) mi = lo;\n+\t\t}\n+\t} while (try != level2_key && lo + (ents >> 8) < hi);\n+\n+        while (lo < hi) {\n \t\tint cmp = hashcmp(index + 24 * mi + 4, sha1);\n \t\tif (!cmp)\n \t\t\treturn ntohl(*((uint32_t *)((char *)index + (24 * mi))));\n@@ -1562,7 +1587,9 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \t\t\thi = mi;\n \t\telse\n \t\t\tlo = mi+1;\n-\t} while (lo < hi);\n+\t\tmi = lo + (hi - lo) / 2;\n+\t};\n+\n \treturn 0;\n }\n \n-- \n1.4.5-rc0.GIT\n"}]}