{"thread":{"id":"34902","subject":"[PATCH] lookup_object: remove hashtable_index() and optimize hash_obj()","startedAt":"2013-09-10T22:17:12Z","lastAt":"2013-09-12T20:30:57Z","messageCount":4,"participants":["Nicolas Pitre","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"227376","messageId":"alpine.LFD.2.03.1309101811510.20709@syhkavp.arg","threadId":"34902","inReplyTo":null,"subject":"[PATCH] lookup_object: remove hashtable_index() and optimize hash_obj()","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-10T22:17:12Z","receivedAt":"2013-09-10T22:17:12Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nhashtable_index() appears to be a close duplicate of hash_obj().\nKeep only the later and make it usable for all cases.\n\nAlso remove the modulus as this is an expansive operation.\nThe size argument is always a power of 2 anyway, so a simple\nmask operation provides the same result.\n\nOn a 'git rev-list --all --objects' run this decreased the time spent\nin lookup_object from 27.5% to 24.1%.\n\nSigned-off-by: Nicolas Pitre <nico@fluxnic.net>\n---\n\nI discovered this patch in my git work tree dating from 2 years ago.\n\ndiff --git a/object.c b/object.c\nindex d8a4b1f..e2dae22 100644\n--- a/object.c\n+++ b/object.c\n@@ -43,16 +43,16 @@ int type_from_string(const char *str)\n \tdie(\"invalid object type \\\"%s\\\"\", str);\n }\n \n-static unsigned int hash_obj(struct object *obj, unsigned int n)\n+static unsigned int hash_obj(const unsigned char *sha1, unsigned int n)\n {\n \tunsigned int hash;\n-\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n-\treturn hash % n;\n+\tmemcpy(&hash, sha1, sizeof(unsigned int));\n+\treturn hash & (n - 1);\n }\n \n static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)\n {\n-\tunsigned int j = hash_obj(obj, size);\n+\tunsigned int j = hash_obj(obj->sha1, size);\n \n \twhile (hash[j]) {\n \t\tj++;\n@@ -62,13 +62,6 @@ static void insert_obj_hash(struct object *obj, struct object **hash, unsigned i\n \thash[j] = obj;\n }\n \n-static unsigned int hashtable_index(const unsigned char *sha1)\n-{\n-\tunsigned int i;\n-\tmemcpy(&i, sha1, sizeof(unsigned int));\n-\treturn i % obj_hash_size;\n-}\n-\n struct object *lookup_object(const unsigned char *sha1)\n {\n \tunsigned int i, first;\n@@ -77,7 +70,7 @@ struct object *lookup_object(const unsigned char *sha1)\n \tif (!obj_hash)\n \t\treturn NULL;\n \n-\tfirst = i = hashtable_index(sha1);\n+\tfirst = i = hash_obj(sha1, obj_hash_size);\n \twhile ((obj = obj_hash[i]) != NULL) {\n \t\tif (!hashcmp(sha1, obj->sha1))\n \t\t\tbreak;\n"},{"id":"227482","messageId":"20130911184845.GA25386@sigill.intra.peff.net","threadId":"34902","inReplyTo":"alpine.LFD.2.03.1309101811510.20709@syhkavp.arg","subject":"Re: [PATCH] lookup_object: remove hashtable_index() and optimize hash_obj()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-09-11T18:48:45Z","receivedAt":"2013-09-11T18:48:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 10, 2013 at 06:17:12PM -0400, Nicolas Pitre wrote:\n\n> hashtable_index() appears to be a close duplicate of hash_obj().\n> Keep only the later and make it usable for all cases.\n\nThanks. This duplication has often bugged me when looking at that\nhash table, but I just never actually wrote the patch.\n\n> Also remove the modulus as this is an expansive operation.\n> The size argument is always a power of 2 anyway, so a simple\n> mask operation provides the same result.\n> \n> On a 'git rev-list --all --objects' run this decreased the time spent\n> in lookup_object from 27.5% to 24.1%.\n\nNice. This is a tiny bit subtle, though, as the power-of-2 growth\nhappens elsewhere, and we may want to tweak it later (the decorate.c\nhash, for example, grows by 3/2).\n\nMaybe it's worth squashing in one or both of the comments below as a\nwarning to anybody who tries to tweak it.\n\n---\ndiff --git a/object.c b/object.c\nindex e2dae22..5f792cb 100644\n--- a/object.c\n+++ b/object.c\n@@ -47,6 +47,7 @@ static unsigned int hash_obj(const unsigned char *sha1, unsigned int n)\n {\n \tunsigned int hash;\n \tmemcpy(&hash, sha1, sizeof(unsigned int));\n+\t/* Assumes power-of-2 hash sizes in grow_object_hash */\n \treturn hash & (n - 1);\n }\n \n@@ -94,6 +95,10 @@ static void grow_object_hash(void)\n static void grow_object_hash(void)\n {\n \tint i;\n+\t/*\n+\t * Note that this size must always be power-of-2 to match hash_obj\n+\t * above.\n+\t */\n \tint new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;\n \tstruct object **new_hash;\n \n"},{"id":"227568","messageId":"alpine.LFD.2.03.1309121606130.20709@syhkavp.arg","threadId":"34902","inReplyTo":"20130911184845.GA25386@sigill.intra.peff.net","subject":"Re: [PATCH] lookup_object: remove hashtable_index() and optimize hash_obj()","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-12T20:08:04Z","receivedAt":"2013-09-12T20:08:04Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 11 Sep 2013, Jeff King wrote:\n\n> On Tue, Sep 10, 2013 at 06:17:12PM -0400, Nicolas Pitre wrote:\n> \n> > Also remove the modulus as this is an expansive operation.\n> > The size argument is always a power of 2 anyway, so a simple\n> > mask operation provides the same result.\n> > \n> > On a 'git rev-list --all --objects' run this decreased the time spent\n> > in lookup_object from 27.5% to 24.1%.\n> \n> Nice. This is a tiny bit subtle, though, as the power-of-2 growth\n> happens elsewhere, and we may want to tweak it later (the decorate.c\n> hash, for example, grows by 3/2).\n> \n> Maybe it's worth squashing in one or both of the comments below as a\n> warning to anybody who tries to tweak it.\n\nAgreed.\n\n@Junio: are you willing to squash those in, or do you prefer a resent?\n\n> ---\n> diff --git a/object.c b/object.c\n> index e2dae22..5f792cb 100644\n> --- a/object.c\n> +++ b/object.c\n> @@ -47,6 +47,7 @@ static unsigned int hash_obj(const unsigned char *sha1, unsigned int n)\n>  {\n>  \tunsigned int hash;\n>  \tmemcpy(&hash, sha1, sizeof(unsigned int));\n> +\t/* Assumes power-of-2 hash sizes in grow_object_hash */\n>  \treturn hash & (n - 1);\n>  }\n>  \n> @@ -94,6 +95,10 @@ static void grow_object_hash(void)\n>  static void grow_object_hash(void)\n>  {\n>  \tint i;\n> +\t/*\n> +\t * Note that this size must always be power-of-2 to match hash_obj\n> +\t * above.\n> +\t */\n>  \tint new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;\n>  \tstruct object **new_hash;\n>  \n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at  http://vger.kernel.org/majordomo-info.html\n> \n"},{"id":"227574","messageId":"xmqqmwnhok8u.fsf@gitster.dls.corp.google.com","threadId":"34902","inReplyTo":"alpine.LFD.2.03.1309121606130.20709@syhkavp.arg","subject":"Re: [PATCH] lookup_object: remove hashtable_index() and optimize hash_obj()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-09-12T20:30:57Z","receivedAt":"2013-09-12T20:30:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@fluxnic.net> writes:\n\n>> Maybe it's worth squashing in one or both of the comments below as a\n>> warning to anybody who tries to tweak it.\n>\n> Agreed.\n>\n> @Junio: are you willing to squash those in, or do you prefer a resent?\n\nI think I've queued it ready to be squashed.  No need for resend.\n\nThanks.\n"}]}