{"thread":{"id":"9170","subject":"[PATCH] Use Peter J. Weinberger's hash function in xdiff","startedAt":"2007-07-23T11:17:58Z","lastAt":"2007-07-23T11:17:58Z","messageCount":1,"participants":["Marco Costalba"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"48301","messageId":"e5bfff550707230417j3d4ac7f4sb310baf43a327684@mail.gmail.com","threadId":"9170","inReplyTo":null,"subject":"[PATCH] Use Peter J. Weinberger's hash function in xdiff","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-07-23T11:17:58Z","receivedAt":"2007-07-23T11:17:58Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"It seems a little bit faster then current one:\n\nWITH CURRENT ONE\n\ngit tree\n$ time git diff v0.99.. > /dev/null\n0.91user 0.02system 0:01.03elapsed 91%CPU\n(0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+3594minor)pagefaults 0swaps\n\nLinux tree\n$ time git diff v2.6.22.. > /dev/null\n13.61user 0.19system 0:13.90elapsed 99%CPU\n(0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+27279minor)pagefaults 0swaps\n\nWITH NEW ONE\n\ngit tree\n$ time git diff v0.99.. > /dev/null\n0.87user 0.01system 0:00.98elapsed 90%CPU\n(0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+3594minor)pagefaults 0swaps\n\nLinux tree\n$ time git diff v2.6.22.. > /dev/null\n13.26user 0.21system 0:13.57elapsed 99%CPU\n(0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+27277minor)pagefaults 0swaps\n\nSigned-off-by: Marco Costalba <mcostalba@gmail.com>\n---\n\nThis patch is not intended for inclusion, the time diff is very small,\nbut it would be interestiing to understand from where it comes from\npossibly from people more versed then me in hashing functions.\n\nBTW this modified Weinberger's hash function is the one used in Qt\nlibrary, for the QHash class.\n\n xdiff/xutils.c |   20 ++++++++++++++------\n 1 files changed, 14 insertions(+), 6 deletions(-)\n\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex 2ade97b..c19ab6e 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -270,24 +270,32 @@ static unsigned long\n \treturn ha;\n }\n\n+/*\n+    This function is based on Peter J. Weinberger's hash function\n+    (from the Dragon Book). The constant 24 in the original function\n+    was replaced with 23 to produce fewer collisions on input such as\n+    \"a\", \"aa\", \"aaa\", \"aaaa\", ...\n+*/\n\n unsigned long xdl_hash_record(char const **data, char const *top, long flags) {\n-\tunsigned long ha = 5381;\n+\n+\tunsigned long ha = 0;\n+\tunsigned long g;\n \tchar const *ptr = *data;\n\n \tif (flags & XDF_WHITESPACE_FLAGS)\n \t\treturn xdl_hash_record_with_whitespace(data, top, flags);\n\n-\tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n-\t\tha += (ha << 5);\n-\t\tha ^= (unsigned long) *ptr;\n+\twhile (ptr < top && *ptr != '\\n') {\n+\t\tha = (ha << 4) + *ptr++;\n+\t\tif ((g = (ha & 0xf0000000)) != 0)\n+\t\t\tha ^= g >> 23;\n+\t\tha &= ~g;\n \t}\n \t*data = ptr < top ? ptr + 1: ptr;\n-\n \treturn ha;\n }\n\n-\n unsigned int xdl_hashbits(unsigned int size) {\n \tunsigned int val = 1, bits = 0;\n\n-- \n1.5.3.rc2.29.gc4640f-dirty\n"}]}