{"thread":{"id":"11707","subject":"I'm a total push-over..","startedAt":"2008-01-22T23:37:30Z","lastAt":"2008-01-27T15:06:02Z","messageCount":51,"participants":["Linus Torvalds","Kevin Ballard","Junio C Hamano","Andreas Ericsson","Dmitry Potapov","Johannes Schindelin","David Kastrup","Theodore Tso","Marko Kreen","Luke Lu","Jeremy Maitin-Shepard"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"66336","messageId":"alpine.LFD.1.00.0801221515350.1741@woody.linux-foundation.org","threadId":"11707","inReplyTo":null,"subject":"I'm a total push-over..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-22T23:37:30Z","receivedAt":"2008-01-22T23:37:30Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOk, here's an interesting patch based on the current 'next' (since it very \nintimately requires the new in-memory index format).\n\nWhat it does is to create a hash index of every single file added to the \nindex. Right now that hash index isn't actually used for much: I \nimplemented a \"cache_name_exists()\" function that uses it to efficiently \nlook up a filename in the index without having to do the O(logn) binary \nsearch, but quite frankly, that's not why this patch is interesting.\n\nNo, the whole and only reason to create the hash of the filenames in the \nindex is that by modifying the hash function, you can fairly easily do \nthings like making it always hash equivalent names into the same bucket. \n\nThat, in turn, means that suddenly questions like \"does this name exists \nin the index under an _equivalent_ name?\" becomes much much cheaper.\n\nGuiding principles behind this patch:\n\n - it shouldn't be too costly. In fact, my primary goal here was to \n actually speed up \"git commit\" with a fully populated kernel tree, by \n being faster at checking whether a file already existed in the index. I \n did succeed, but only barely:\n\n\tBest before:\n\t\t[torvalds@woody linux]$ time git commit > /dev/null\n\t\treal 0m0.255s\n\t\tuser 0m0.168s\n\t\tsys 0m0.088s\n\n\tBest after:\n\n\t\t[torvalds@woody linux]$ time ~/git/git commit > /dev/null\n\t\treal 0m0.233s\n\t\tuser 0m0.144s\n\t\tsys 0m0.088s\n\n so some things are actually faster (~8%).\n\n Caveat: that's really the best case. Other things are invariably going \n to be slightly slower, since we populate that index cache, and quite \n frankly, few things really use it to look things up. \n\n That said, the cost is really quite small. The worst case is probably \n doing a \"git ls-files\", which will do very little except puopulate the \n index, and never actually looks anything up in it, just lists it.\n\n\tBefore:\n\t\t[torvalds@woody linux]$ time git ls-files > /dev/null\n\t\treal 0m0.016s\n\t\tuser 0m0.016s\n\t\tsys 0m0.000s\n\n\tAfter:\n\t\t[torvalds@woody linux]$ time ~/git/git ls-files > /dev/null\n\t\t\treal 0m0.021s\n\t\t\tuser 0m0.012s\n\t\t\tsys 0m0.008s\n\n and while the thing has really gotten relatively much slower, we're \n still talking about something almost unmeasurable (eg 5ms). And that \n really should be pretty much the worst case.\n\n So we lose 5ms on one \"benchmark\", but win 22ms on another. Pick your \n poison - this patch has the advantage that it will _likely_ speed up \n the cases that are complex and expensive more than it slows down the \n cases that are already so fast that nobody cares. But if you look at\n relative speedups/slowdowns, it doesn't look so good.\n\n - It should be simple and clean\n\n The code may be a bit subtle (the reasons I do hash removal the way I \n do etc), but it re-uses the existing hash.c files, so it really is \n fairly small and straightforward apart from a few odd details.\n\nNow, this patch on its own doesn't really do much, but I think it's worth \nlooking at, if only because if done correctly, the name hashing really can \nmake an improvement to the whole issue of \"do we have a filename that \nlooks like this in the index already\". And at least it gets real testing \nby being used even by default (ie there is a real use-case for it even \nwithout any insane filesystems).\n\nNOTE NOTE NOTE! The current hash is a joke. I'm ashamed of it, I'm just \nnot ashamed of it enough to really care. I took all the numbers out of my \nnether regions - I'm sure it's good enough that it works in practice, but \nthe whole point was that you can make a really much fancier hash that \nhashes characters not directly, but by their upper-case value or something \nlike that, and thus you get a case-insensitive hash, while still keeping \nthe name and the index itself totally case sensitive.\n\nAnd let's face it, it was kind of fun. These things are all _soo_ much \nsimpler than all the issues you have to do in the kernel, so this is just \na complete toy compared to all the things we do inside Linux to do the \nsame thing with pluggable hashes on a per-path-component basis etc.\n\n(User space developers are weenies. One of the most fun parts of git \ndevelopment for me has been how easy everything is ;)\n\n\t\tLinus\n\n----\n cache.h | 6 +++\n dir.c | 2 +-\n read-cache.c | 97 ++++++++++++++++++++++++++++++++++++++++++++++++++++------\n 3 files changed, 94 insertions(+), 11 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 3a47cdc..409738c 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -3,6 +3,7 @@\n \n #include \"git-compat-util.h\"\n #include \"strbuf.h\"\n+#include \"hash.h\"\n \n #include SHA1_HEADER\n #include \n@@ -109,6 +110,7 @@ struct ondisk_cache_entry {\n };\n \n struct cache_entry {\n+\tstruct cache_entry *next;\n \tunsigned int ce_ctime;\n \tunsigned int ce_mtime;\n \tunsigned int ce_dev;\n@@ -131,6 +133,7 @@ struct cache_entry {\n #define CE_UPDATE (0x10000)\n #define CE_REMOVE (0x20000)\n #define CE_UPTODATE (0x40000)\n+#define CE_UNHASHED (0x80000)\n \n static inline unsigned create_ce_flags(size_t len, unsigned stage)\n {\n@@ -188,6 +191,7 @@ struct index_state {\n \tstruct cache_tree *cache_tree;\n \ttime_t timestamp;\n \tvoid *alloc;\n+\tstruct hash_table name_hash;\n };\n \n extern struct index_state the_index;\n@@ -211,6 +215,7 @@ extern struct index_state the_index;\n #define refresh_cache(flags) refresh_index(&the_index, (flags), NULL, NULL)\n #define ce_match_stat(ce, st, options) ie_match_stat(&the_index, (ce), (st), (options))\n #define ce_modified(ce, st, options) ie_modified(&the_index, (ce), (st), (options))\n+#define cache_name_exists(name, namelen) index_name_exists(&the_index, (name), (namelen))\n #endif\n \n enum object_type {\n@@ -297,6 +302,7 @@ extern int read_index_from(struct index_state *, const char *path);\n extern int write_index(struct index_state *, int newfd);\n extern int discard_index(struct index_state *);\n extern int verify_path(const char *path);\n+extern int index_name_exists(struct index_state *istate, const char *name, int namelen);\n extern int index_name_pos(struct index_state *, const char *name, int namelen);\n #define ADD_CACHE_OK_TO_ADD 1\t\t/* Ok to add */\n #define ADD_CACHE_OK_TO_REPLACE 2\t/* Ok to replace file/directory */\ndiff --git a/dir.c b/dir.c\nindex 1b9cc7a..6543105 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -346,7 +346,7 @@ static struct dir_entry *dir_entry_new(const char *pathname, int len)\n \n struct dir_entry *dir_add_name(struct dir_struct *dir, const char *pathname, int len)\n {\n-\tif (cache_name_pos(pathname, len) >= 0)\n+\tif (cache_name_exists(pathname, len))\n \t\treturn NULL;\n \n \tALLOC_GROW(dir->entries, dir->nr+1, dir->alloc);\ndiff --git a/read-cache.c b/read-cache.c\nindex 8ba8f0f..33a8ca5 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -23,6 +23,70 @@\n \n struct index_state the_index;\n \n+static unsigned int hash_name(const char *name, int namelen)\n+{\n+\tunsigned int hash = 0x123;\n+\n+\tdo {\n+\t\tunsigned char c = *name++;\n+\t\thash = hash*101 + c;\n+\t} while (--namelen);\n+\treturn hash;\n+}\n+\n+static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)\n+{\n+\tvoid **pos;\n+\tunsigned int hash = hash_name(ce->name, ce_namelen(ce));\n+\n+\tistate->cache[nr] = ce;\n+\tpos = insert_hash(hash, ce, &istate->name_hash);\n+\tif (pos) {\n+\t\tce->next = *pos;\n+\t\t*pos = ce;\n+\t}\n+}\n+\n+/*\n+ * We don't actually *remove* it, we can just mark it invalid so that\n+ * we won't find it in lookups.\n+ *\n+ * Not only would we have to search the lists (simple enough), but\n+ * we'd also have to rehash other hash buckets in case this makes the\n+ * hash bucket empty (common). So it's much better to just mark\n+ * it.\n+ */\n+static void remove_hash_entry(struct index_state *istate, struct cache_entry *ce)\n+{\n+\tce->ce_flags |= CE_UNHASHED;\n+}\n+\n+static void replace_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)\n+{\n+\tstruct cache_entry *old = istate->cache[nr];\n+\n+\tif (ce != old) {\n+\t\tremove_hash_entry(istate, old);\n+\t\tset_index_entry(istate, nr, ce);\n+\t}\n+\tistate->cache_changed = 1;\n+}\n+\n+int index_name_exists(struct index_state *istate, const char *name, int namelen)\n+{\n+\tunsigned int hash = hash_name(name, namelen);\n+\tstruct cache_entry *ce = lookup_hash(hash, &istate->name_hash);\n+\n+\twhile (ce) {\n+\t\tif (!(ce->ce_flags & CE_UNHASHED)) {\n+\t\t\tif (!cache_name_compare(name, namelen, ce->name, ce->ce_flags))\n+\t\t\t\treturn 1;\n+\t\t}\n+\t\tce = ce->next;\n+\t}\n+\treturn 0;\n+}\n+\n /*\n * This only updates the \"non-critical\" parts of the directory\n * cache, ie the parts that aren't tracked by GIT, and only used\n@@ -323,6 +387,9 @@ int index_name_pos(struct index_state *istate, const char *name, int namelen)\n /* Remove entry, return true if there are more entries to go.. */\n int remove_index_entry_at(struct index_state *istate, int pos)\n {\n+\tstruct cache_entry *ce = istate->cache[pos];\n+\n+\tremove_hash_entry(istate, ce);\n \tistate->cache_changed = 1;\n \tistate->cache_nr--;\n \tif (pos >= istate->cache_nr)\n@@ -697,8 +764,7 @@ static int add_index_entry_with_check(struct index_state *istate, struct cache_e\n \n \t/* existing match? Just replace it. */\n \tif (pos >= 0) {\n-\t\tistate->cache_changed = 1;\n-\t\tistate->cache[pos] = ce;\n+\t\treplace_index_entry(istate, pos, ce);\n \t\treturn 0;\n \t}\n \tpos = -pos-1;\n@@ -758,7 +824,7 @@ int add_index_entry(struct index_state *istate, struct cache_entry *ce, int opti\n \t\tmemmove(istate->cache + pos + 1,\n \t\t\tistate->cache + pos,\n \t\t\t(istate->cache_nr - pos - 1) * sizeof(ce));\n-\tistate->cache[pos] = ce;\n+\tset_index_entry(istate, pos, ce);\n \tistate->cache_changed = 1;\n \treturn 0;\n }\n@@ -887,11 +953,8 @@ int refresh_index(struct index_state *istate, unsigned int flags, const char **p\n \t\t\thas_errors = 1;\n \t\t\tcontinue;\n \t\t}\n-\t\tistate->cache_changed = 1;\n-\t\t/* You can NOT just free istate->cache[i] here, since it\n-\t\t * might not be necessarily malloc()ed but can also come\n-\t\t * from mmap(). */\n-\t\tistate->cache[i] = new;\n+\n+\t\treplace_index_entry(istate, i, new);\n \t}\n \treturn has_errors;\n }\n@@ -966,6 +1029,20 @@ static void convert_from_disk(struct ondisk_cache_entry *ondisk, struct cache_en\n \tmemcpy(ce->name, ondisk->name, len + 1);\n }\n \n+static inline size_t estimate_cache_size(size_t ondisk_size, unsigned int entries)\n+{\n+\tlong per_entry;\n+\n+\tper_entry = sizeof(struct cache_entry) - sizeof(struct ondisk_cache_entry);\n+\n+\t/*\n+\t * Alignment can cause differences. This should be \"alignof\", but \n+\t * since that's a gcc'ism, just use the size of a pointer.\n+\t */\n+\tper_entry += sizeof(void *);\n+\treturn ondisk_size + entries*per_entry;\n+}\n+\n /* remember to discard_cache() before reading a different cache! */\n int read_index_from(struct index_state *istate, const char *path)\n {\n@@ -1016,7 +1093,7 @@ int read_index_from(struct index_state *istate, const char *path)\n \t * has room for a few more flags, we can allocate using the same\n \t * index size\n \t */\n-\tistate->alloc = xmalloc(mmap_size);\n+\tistate->alloc = xmalloc(estimate_cache_size(mmap_size, istate->cache_nr));\n \n \tsrc_offset = sizeof(*hdr);\n \tdst_offset = 0;\n@@ -1027,7 +1104,7 @@ int read_index_from(struct index_state *istate, const char *path)\n \t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);\n \t\tce = (struct cache_entry *)((char *)istate->alloc + dst_offset);\n \t\tconvert_from_disk(disk_ce, ce);\n-\t\tistate->cache[i] = ce;\n+\t\tset_index_entry(istate, i, ce);\n \n \t\tsrc_offset += ondisk_ce_size(ce);\n \t\tdst_offset += ce_size(ce);\n"},{"id":"66345","messageId":"93A91CFE-9B0C-47FE-BA57-9382DF955C43@sb.org","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801221515350.1741@woody.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Kevin Ballard","fromEmail":"kevin@sb.org","sentAt":"2008-01-23T01:35:07Z","receivedAt":"2008-01-23T01:35:07Z","isPatch":false,"sender":{"key":"kevin@sb.org","avatar":"https://avatars.githubusercontent.com/u/714?v=4"},"body":"On Jan 22, 2008, at 6:37 PM, Linus Torvalds wrote:\n\n> Ok, here's an interesting patch based on the current 'next' (since \n> it very\n> intimately requires the new in-memory index format).\n>\n> What it does is to create a hash index of every single file added to \n> the\n> index. Right now that hash index isn't actually used for much: I\n> implemented a \"cache_name_exists()\" function that uses it to \n> efficiently\n> look up a filename in the index without having to do the O(logn) \n> binary\n> search, but quite frankly, that's not why this patch is interesting.\n>\n> No, the whole and only reason to create the hash of the filenames in \n> the\n> index is that by modifying the hash function, you can fairly easily do\n> things like making it always hash equivalent names into the same \n> bucket.\n\nThis is fantastic. Thank you very much for actually taking this issue \nseriously despite the mess I made on the list. This is exactly why I \nwanted to discuss on the lists instead of hacking away myself - there \nare very smart people on the list (like you) that already know how git \nworks that can come up with ideas like this while I would still be \ntrying to figure out where the index code is even stored.\n\n-Kevin Ballard\n\n-- \nKevin Ballard\nhttp://kevin.sb.org\nkevin@sb.org\nhttp://www.tildesoft.com\n\n\n"},{"id":"66351","messageId":"7vabmxqnz8.fsf@gitster.siamese.dyndns.org","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801221515350.1741@woody.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-23T02:23:23Z","receivedAt":"2008-01-23T02:23:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Ok, here's an interesting patch based on the current 'next' (since it very \n> intimately requires the new in-memory index format).\n\nThis is nice. It does not do anything specific with HFS+ issues\nbut aims for faster look-ups, which would help everybody.\n\nTwo things I noticed (only two, not necessarily because you are\ngood but mostly because I am still mired in day job and could\nnot get enough uninterrupted minutes to read the patch ;-)):\n\n - You might want to store the hash table (once computed) in the\n index extension section, and lazily unpack the table the\n first time index_name_exists() or set_index_entry() is called\n on the given istate, instead of unpacking it immediately when\n you read from the disk. That way, ls-files does not have to\n suffer at all.\n\n - You would need to get rid of the table in discard_index().\n"},{"id":"66352","messageId":"7v63xlqnd0.fsf@gitster.siamese.dyndns.org","threadId":"11707","inReplyTo":"7vabmxqnz8.fsf@gitster.siamese.dyndns.org","subject":"Re: I'm a total push-over..","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-23T02:36:43Z","receivedAt":"2008-01-23T02:36:43Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Linus Torvalds writes:\n>\n>> Ok, here's an interesting patch based on the current 'next' (since it very \n>> intimately requires the new in-memory index format).\n>\n> This is nice. It does not do anything specific with HFS+ issues\n> but aims for faster look-ups, which would help everybody.\n>\n> Two things I noticed (only two, not necessarily because you are\n> good but mostly because I am still mired in day job and could\n> not get enough uninterrupted minutes to read the patch ;-)):\n>\n> - You might want to store the hash table (once computed) in the\n> index extension section, and lazily unpack the table the\n> first time index_name_exists() or set_index_entry() is called\n> on the given istate, instead of unpacking it immediately when\n> you read from the disk. That way, ls-files does not have to\n> suffer at all.\n\nActually, I take one fourth of this back. \n\n * I am not yet retracting the suggestion to do the hashing\n lazily (what I mean by \"lazily\" is that the first access that\n wants hashed access will iterate active_cache and hash them\n all, not \"lazily one entry at a time as needed\" which would\n not make any sense for a hashtable). I have to find time to\n try benching the effect of it myself. So that's one half\n retained.\n\n * We certainly do not necessarily want to store this in the\n index right now. The hash algorithms would be improved from\n the version you are almost ashamed of ;-). That sounds as if\n I am retrating the other half, but not quite.\n\n * Once we have a mechanism to detect that the extension section\n stores a precomputed hash that was done with a different\n algorithm and ignore it (and recompute afresh when needed),\n then we can afford to put a more elaborate hashing algorithm,\n slightly loosening one of your \"Guiding principles\", and keep\n the result in the generated index to be reused by the next\n user. So that is why I am retracting only half of the\n suggestion to save it in the extension section (which in turn\n is a half of my suggestion).\n"},{"id":"66360","messageId":"alpine.LFD.1.00.0801221844570.1741@woody.linux-foundation.org","threadId":"11707","inReplyTo":"7vabmxqnz8.fsf@gitster.siamese.dyndns.org","subject":"Re: I'm a total push-over..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-23T02:58:53Z","receivedAt":"2008-01-23T02:58:53Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 22 Jan 2008, Junio C Hamano wrote:\n> \n> - You might want to store the hash table (once computed) in the\n> index extension section, and lazily unpack the table the\n> first time index_name_exists() or set_index_entry() is called\n> on the given istate, instead of unpacking it immediately when\n> you read from the disk. That way, ls-files does not have to\n> suffer at all.\n\nI really hate that. \n\nBasically, I dislike having two copies of the same data. If something can \nbe computed from something else, then only the original data should exist, \nand the other thing should be recomputed. Otherwise you easily get into \nsituations where you spend a lot of time maintaining the other copy, or \nworse, you have inconsistent data and it's really subtle what is going on.\n\nAlso, one of the ideas behind the index is that would depend on your \nnotion of what is \"equivalent\", which is actually somehing fairly fluid. \nIn fact, it's likely going to depend on a config option.\n\nSo encoding the indexing on disk, when it can change when you do a simple \n\"git config\", or even just depending on your LANG environment variable, \nseems like a singularly bad idea, even if it wasn't for the coherence.\n\nI did consider doing the indexing only on demand, and we can certainly \nsimply just \"turn it off\" when we know it's never going to get used (ie \n\"git ls-files\"). So in that sense, it's easy to get rid of the overhead, \nbut it didn't really seem like the conceptual complexity (even if it's \njust a couple of lines) is really worth it. It's not like git ls-files is \nreally performance-critical anyway.\n\n> - You would need to get rid of the table in discard_index().\n\nNow this, of course, is obviously true.\n\nAnd the patch to do that is very simple too. No need to walk any chains, \nsince the \"free(istate->alloc);\" will release all the pre-allocated \ncache_entry structures, and the rest are (necessarily) leaked anyway.\n\n[ Side note for non-Junios: the leaking of cache_entry structures isn't \n new, we've always done it, and it's even done on purpose. The common \n case is that there is one *big* allocation (istate->alloc) that contains \n all the original cache entries.\n\n There are usually none, or only a very few individual allocations, and \n we don't even keep track of them. With the new in-memory format, we \n could make a special flag that does \"is this cache-entry an individual \n allocation or not\" (or we could even just see if they are inside the \n \"alloc\" range), but the common case really should be that there's just a \n couple of them, and we just drop them rather than tracking them. ]\n\nHere.\n\n\t\tLinus\n\n---\n read-cache.c | 1 +\n 1 files changed, 1 insertions(+), 0 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 33a8ca5..abee0fc 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1142,6 +1142,7 @@ int discard_index(struct index_state *istate)\n \tistate->cache_nr = 0;\n \tistate->cache_changed = 0;\n \tistate->timestamp = 0;\n+\tfree_hash(&istate->name_hash);\n \tcache_tree_free(&(istate->cache_tree));\n \tfree(istate->alloc);\n \tistate->alloc = NULL;\n"},{"id":"66364","messageId":"alpine.LFD.1.00.0801221913500.1741@woody.linux-foundation.org","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801221844570.1741@woody.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-23T03:19:12Z","receivedAt":"2008-01-23T03:19:12Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 22 Jan 2008, Linus Torvalds wrote:\n> \n> And the patch to do that is very simple too. \n\nOk, I pushed the squashed/fixed commit to the \"new-lstat\" branch. It's now \nbased on your 'next' branch, and I should have renamed it, since it's not \nabout any of the old lstat() optimizations any more. Whatever.\n\nBut here it is also as a full patch, with a fixed up subject line etc. You \ntend to want to have them as topic-branches, and it's probably easier this \nway.\n\n\t\tLinus\n\n---\nFrom ca98bbc7b0cc1d9d088a8c6ae80e733115a1f775 Mon Sep 17 00:00:00 2001\nFrom: Linus Torvalds \nDate: Tue, 22 Jan 2008 18:41:14 -0800\nSubject: [PATCH] Create pathname-based hash-table lookup into index\n\nThis creates a hash index of every single file added to the index.\nRight now that hash index isn't actually used for much: I implemented a\n\"cache_name_exists()\" function that uses it to efficiently look up a\nfilename in the index without having to do the O(logn) binary search,\nbut quite frankly, that's not why this patch is interesting.\n\nNo, the whole and only reason to create the hash of the filenames in the\nindex is that by modifying the hash function, you can fairly easily do\nthings like making it always hash equivalent names into the same bucket.\n\nThat, in turn, means that suddenly questions like \"does this name exist\nin the index under an _equivalent_ name?\" becomes much much cheaper.\n\nGuiding principles behind this patch:\n\n - it shouldn't be too costly. In fact, my primary goal here was to\n actually speed up \"git commit\" with a fully populated kernel tree, by\n being faster at checking whether a file already existed in the index. I\n did succeed, but only barely:\n\n\tBest before:\n\t\t[torvalds@woody linux]$ time git commit > /dev/null\n\t\treal 0m0.255s\n\t\tuser 0m0.168s\n\t\tsys 0m0.088s\n\n\tBest after:\n\n\t\t[torvalds@woody linux]$ time ~/git/git commit > /dev/null\n\t\treal 0m0.233s\n\t\tuser 0m0.144s\n\t\tsys 0m0.088s\n\n so some things are actually faster (~8%).\n\n Caveat: that's really the best case. Other things are invariably going\n to be slightly slower, since we populate that index cache, and quite\n frankly, few things really use it to look things up.\n\n That said, the cost is really quite small. The worst case is probably\n doing a \"git ls-files\", which will do very little except puopulate the\n index, and never actually looks anything up in it, just lists it.\n\n\tBefore:\n\t\t[torvalds@woody linux]$ time git ls-files > /dev/null\n\t\treal 0m0.016s\n\t\tuser 0m0.016s\n\t\tsys 0m0.000s\n\n\tAfter:\n\t\t[torvalds@woody linux]$ time ~/git/git ls-files > /dev/null\n\t\treal 0m0.021s\n\t\tuser 0m0.012s\n\t\tsys 0m0.008s\n\n and while the thing has really gotten relatively much slower, we're\n still talking about something almost unmeasurable (eg 5ms). And that\n really should be pretty much the worst case.\n\n So we lose 5ms on one \"benchmark\", but win 22ms on another. Pick your\n poison - this patch has the advantage that it will _likely_ speed up\n the cases that are complex and expensive more than it slows down the\n cases that are already so fast that nobody cares. But if you look at\n relative speedups/slowdowns, it doesn't look so good.\n\n - It should be simple and clean\n\n The code may be a bit subtle (the reasons I do hash removal the way I\n do etc), but it re-uses the existing hash.c files, so it really is\n fairly small and straightforward apart from a few odd details.\n\nNow, this patch on its own doesn't really do much, but I think it's worth\nlooking at, if only because if done correctly, the name hashing really can\nmake an improvement to the whole issue of \"do we have a filename that\nlooks like this in the index already\". And at least it gets real testing\nby being used even by default (ie there is a real use-case for it even\nwithout any insane filesystems).\n\nNOTE NOTE NOTE! The current hash is a joke. I'm ashamed of it, I'm just\nnot ashamed of it enough to really care. I took all the numbers out of my\nnether regions - I'm sure it's good enough that it works in practice, but\nthe whole point was that you can make a really much fancier hash that\nhashes characters not directly, but by their upper-case value or something\nlike that, and thus you get a case-insensitive hash, while still keeping\nthe name and the index itself totally case sensitive.\n\nSigned-off-by: Linus Torvalds \n---\n cache.h | 6 +++\n dir.c | 2 +-\n read-cache.c | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++++------\n 3 files changed, 95 insertions(+), 11 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 3a47cdc..409738c 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -3,6 +3,7 @@\n \n #include \"git-compat-util.h\"\n #include \"strbuf.h\"\n+#include \"hash.h\"\n \n #include SHA1_HEADER\n #include \n@@ -109,6 +110,7 @@ struct ondisk_cache_entry {\n };\n \n struct cache_entry {\n+\tstruct cache_entry *next;\n \tunsigned int ce_ctime;\n \tunsigned int ce_mtime;\n \tunsigned int ce_dev;\n@@ -131,6 +133,7 @@ struct cache_entry {\n #define CE_UPDATE (0x10000)\n #define CE_REMOVE (0x20000)\n #define CE_UPTODATE (0x40000)\n+#define CE_UNHASHED (0x80000)\n \n static inline unsigned create_ce_flags(size_t len, unsigned stage)\n {\n@@ -188,6 +191,7 @@ struct index_state {\n \tstruct cache_tree *cache_tree;\n \ttime_t timestamp;\n \tvoid *alloc;\n+\tstruct hash_table name_hash;\n };\n \n extern struct index_state the_index;\n@@ -211,6 +215,7 @@ extern struct index_state the_index;\n #define refresh_cache(flags) refresh_index(&the_index, (flags), NULL, NULL)\n #define ce_match_stat(ce, st, options) ie_match_stat(&the_index, (ce), (st), (options))\n #define ce_modified(ce, st, options) ie_modified(&the_index, (ce), (st), (options))\n+#define cache_name_exists(name, namelen) index_name_exists(&the_index, (name), (namelen))\n #endif\n \n enum object_type {\n@@ -297,6 +302,7 @@ extern int read_index_from(struct index_state *, const char *path);\n extern int write_index(struct index_state *, int newfd);\n extern int discard_index(struct index_state *);\n extern int verify_path(const char *path);\n+extern int index_name_exists(struct index_state *istate, const char *name, int namelen);\n extern int index_name_pos(struct index_state *, const char *name, int namelen);\n #define ADD_CACHE_OK_TO_ADD 1\t\t/* Ok to add */\n #define ADD_CACHE_OK_TO_REPLACE 2\t/* Ok to replace file/directory */\ndiff --git a/dir.c b/dir.c\nindex 1b9cc7a..6543105 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -346,7 +346,7 @@ static struct dir_entry *dir_entry_new(const char *pathname, int len)\n \n struct dir_entry *dir_add_name(struct dir_struct *dir, const char *pathname, int len)\n {\n-\tif (cache_name_pos(pathname, len) >= 0)\n+\tif (cache_name_exists(pathname, len))\n \t\treturn NULL;\n \n \tALLOC_GROW(dir->entries, dir->nr+1, dir->alloc);\ndiff --git a/read-cache.c b/read-cache.c\nindex 8ba8f0f..abee0fc 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -23,6 +23,70 @@\n \n struct index_state the_index;\n \n+static unsigned int hash_name(const char *name, int namelen)\n+{\n+\tunsigned int hash = 0x123;\n+\n+\tdo {\n+\t\tunsigned char c = *name++;\n+\t\thash = hash*101 + c;\n+\t} while (--namelen);\n+\treturn hash;\n+}\n+\n+static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)\n+{\n+\tvoid **pos;\n+\tunsigned int hash = hash_name(ce->name, ce_namelen(ce));\n+\n+\tistate->cache[nr] = ce;\n+\tpos = insert_hash(hash, ce, &istate->name_hash);\n+\tif (pos) {\n+\t\tce->next = *pos;\n+\t\t*pos = ce;\n+\t}\n+}\n+\n+/*\n+ * We don't actually *remove* it, we can just mark it invalid so that\n+ * we won't find it in lookups.\n+ *\n+ * Not only would we have to search the lists (simple enough), but\n+ * we'd also have to rehash other hash buckets in case this makes the\n+ * hash bucket empty (common). So it's much better to just mark\n+ * it.\n+ */\n+static void remove_hash_entry(struct index_state *istate, struct cache_entry *ce)\n+{\n+\tce->ce_flags |= CE_UNHASHED;\n+}\n+\n+static void replace_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)\n+{\n+\tstruct cache_entry *old = istate->cache[nr];\n+\n+\tif (ce != old) {\n+\t\tremove_hash_entry(istate, old);\n+\t\tset_index_entry(istate, nr, ce);\n+\t}\n+\tistate->cache_changed = 1;\n+}\n+\n+int index_name_exists(struct index_state *istate, const char *name, int namelen)\n+{\n+\tunsigned int hash = hash_name(name, namelen);\n+\tstruct cache_entry *ce = lookup_hash(hash, &istate->name_hash);\n+\n+\twhile (ce) {\n+\t\tif (!(ce->ce_flags & CE_UNHASHED)) {\n+\t\t\tif (!cache_name_compare(name, namelen, ce->name, ce->ce_flags))\n+\t\t\t\treturn 1;\n+\t\t}\n+\t\tce = ce->next;\n+\t}\n+\treturn 0;\n+}\n+\n /*\n * This only updates the \"non-critical\" parts of the directory\n * cache, ie the parts that aren't tracked by GIT, and only used\n@@ -323,6 +387,9 @@ int index_name_pos(struct index_state *istate, const char *name, int namelen)\n /* Remove entry, return true if there are more entries to go.. */\n int remove_index_entry_at(struct index_state *istate, int pos)\n {\n+\tstruct cache_entry *ce = istate->cache[pos];\n+\n+\tremove_hash_entry(istate, ce);\n \tistate->cache_changed = 1;\n \tistate->cache_nr--;\n \tif (pos >= istate->cache_nr)\n@@ -697,8 +764,7 @@ static int add_index_entry_with_check(struct index_state *istate, struct cache_e\n \n \t/* existing match? Just replace it. */\n \tif (pos >= 0) {\n-\t\tistate->cache_changed = 1;\n-\t\tistate->cache[pos] = ce;\n+\t\treplace_index_entry(istate, pos, ce);\n \t\treturn 0;\n \t}\n \tpos = -pos-1;\n@@ -758,7 +824,7 @@ int add_index_entry(struct index_state *istate, struct cache_entry *ce, int opti\n \t\tmemmove(istate->cache + pos + 1,\n \t\t\tistate->cache + pos,\n \t\t\t(istate->cache_nr - pos - 1) * sizeof(ce));\n-\tistate->cache[pos] = ce;\n+\tset_index_entry(istate, pos, ce);\n \tistate->cache_changed = 1;\n \treturn 0;\n }\n@@ -887,11 +953,8 @@ int refresh_index(struct index_state *istate, unsigned int flags, const char **p\n \t\t\thas_errors = 1;\n \t\t\tcontinue;\n \t\t}\n-\t\tistate->cache_changed = 1;\n-\t\t/* You can NOT just free istate->cache[i] here, since it\n-\t\t * might not be necessarily malloc()ed but can also come\n-\t\t * from mmap(). */\n-\t\tistate->cache[i] = new;\n+\n+\t\treplace_index_entry(istate, i, new);\n \t}\n \treturn has_errors;\n }\n@@ -966,6 +1029,20 @@ static void convert_from_disk(struct ondisk_cache_entry *ondisk, struct cache_en\n \tmemcpy(ce->name, ondisk->name, len + 1);\n }\n \n+static inline size_t estimate_cache_size(size_t ondisk_size, unsigned int entries)\n+{\n+\tlong per_entry;\n+\n+\tper_entry = sizeof(struct cache_entry) - sizeof(struct ondisk_cache_entry);\n+\n+\t/*\n+\t * Alignment can cause differences. This should be \"alignof\", but \n+\t * since that's a gcc'ism, just use the size of a pointer.\n+\t */\n+\tper_entry += sizeof(void *);\n+\treturn ondisk_size + entries*per_entry;\n+}\n+\n /* remember to discard_cache() before reading a different cache! */\n int read_index_from(struct index_state *istate, const char *path)\n {\n@@ -1016,7 +1093,7 @@ int read_index_from(struct index_state *istate, const char *path)\n \t * has room for a few more flags, we can allocate using the same\n \t * index size\n \t */\n-\tistate->alloc = xmalloc(mmap_size);\n+\tistate->alloc = xmalloc(estimate_cache_size(mmap_size, istate->cache_nr));\n \n \tsrc_offset = sizeof(*hdr);\n \tdst_offset = 0;\n@@ -1027,7 +1104,7 @@ int read_index_from(struct index_state *istate, const char *path)\n \t\tdisk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);\n \t\tce = (struct cache_entry *)((char *)istate->alloc + dst_offset);\n \t\tconvert_from_disk(disk_ce, ce);\n-\t\tistate->cache[i] = ce;\n+\t\tset_index_entry(istate, i, ce);\n \n \t\tsrc_offset += ondisk_ce_size(ce);\n \t\tdst_offset += ce_size(ce);\n@@ -1065,6 +1142,7 @@ int discard_index(struct index_state *istate)\n \tistate->cache_nr = 0;\n \tistate->cache_changed = 0;\n \tistate->timestamp = 0;\n+\tfree_hash(&istate->name_hash);\n \tcache_tree_free(&(istate->cache_tree));\n \tfree(istate->alloc);\n \tistate->alloc = NULL;\n-- \n1.5.4.rc4.1130.g9ad85\n"},{"id":"66374","messageId":"7vprvtngxk.fsf@gitster.siamese.dyndns.org","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801221844570.1741@woody.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-23T07:23:51Z","receivedAt":"2008-01-23T07:23:51Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Basically, I dislike having two copies of the same data. If something can \n> be computed from something else, then only the original data should exist, \n> and the other thing should be recomputed.\n\nYes, I agree with that in principle. Storing computable values\nmakes sense only when it is expensive to recompute. We did not\nhave cache-tree for quite a long time until you noticed that it\nwas rather expensive and wasteful to recompute tree objects from\nunchanged parts of the index every time.\n\nIt's the same argument; when the hashing performance starts to\nbecome noticeable, we can think about storing and reusing it,\nnot before.\n\n> I did consider doing the indexing only on demand, and we can certainly \n> simply just \"turn it off\" when we know it's never going to get used (ie \n> \"git ls-files\"). So in that sense, it's easy to get rid of the overhead, \n> but it didn't really seem like the conceptual complexity (even if it's \n> just a couple of lines) is really worth it. It's not like git ls-files is \n> really performance-critical anyway.\n\nYes, ls-files is cheap. So is lstat(2) on Linux. It only\nmatters when you do it many many times.\n\nIn any case, the change does not look too bad. The best time\n(real) of running git-ls-files in the kernel repository on my\nbox is 0.010s vs 0.011s (10% improvement, heh!, which is the\nsame as the master version) and empty commit is both 0.082s (no\nchange).\n\n-- >8 --\n[PATCH] lazy index hashing\n\nThis delays the hashing of index names until it becomes necessary for\nthe first time.\n\nSigned-off-by: Junio C Hamano \n---\n cache.h | 1 +\n read-cache.c | 26 +++++++++++++++++++++++---\n 2 files changed, 24 insertions(+), 3 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 409738c..e4aeff0 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -191,6 +191,7 @@ struct index_state {\n \tstruct cache_tree *cache_tree;\n \ttime_t timestamp;\n \tvoid *alloc;\n+\tunsigned name_hash_initialized : 1;\n \tstruct hash_table name_hash;\n };\n \ndiff --git a/read-cache.c b/read-cache.c\nindex 9477c0b..e45f4b3 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -34,12 +34,11 @@ static unsigned int hash_name(const char *name, int namelen)\n \treturn hash;\n }\n \n-static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)\n+static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n {\n \tvoid **pos;\n \tunsigned int hash = hash_name(ce->name, ce_namelen(ce));\n \n-\tistate->cache[nr] = ce;\n \tpos = insert_hash(hash, ce, &istate->name_hash);\n \tif (pos) {\n \t\tce->next = *pos;\n@@ -47,6 +46,24 @@ static void set_index_entry(struct index_state *istate, int nr, struct cache_ent\n \t}\n }\n \n+static void lazy_init_name_hash(struct index_state *istate)\n+{\n+\tint nr;\n+\n+\tif (istate->name_hash_initialized)\n+\t\treturn;\n+\tfor (nr = 0; nr < istate->cache_nr; nr++)\n+\t\thash_index_entry(istate, istate->cache[nr]);\n+\tistate->name_hash_initialized = 1;\n+}\n+\n+static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)\n+{\n+\tistate->cache[nr] = ce;\n+\tif (istate->name_hash_initialized)\n+\t\thash_index_entry(istate, ce);\n+}\n+\n /*\n * We don't actually *remove* it, we can just mark it invalid so that\n * we won't find it in lookups.\n@@ -75,7 +92,10 @@ static void replace_index_entry(struct index_state *istate, int nr, struct cache\n int index_name_exists(struct index_state *istate, const char *name, int namelen)\n {\n \tunsigned int hash = hash_name(name, namelen);\n-\tstruct cache_entry *ce = lookup_hash(hash, &istate->name_hash);\n+\tstruct cache_entry *ce;\n+\n+\tlazy_init_name_hash(istate);\n+\tce = lookup_hash(hash, &istate->name_hash);\n \n \twhile (ce) {\n \t\tif (!(ce->ce_flags & CE_UNHASHED)) {\n-- \n1.5.4.rc4.14.g6fc74\n"},{"id":"66378","messageId":"4796FBB6.9080609@op5.se","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801221515350.1741@woody.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-01-23T08:32:54Z","receivedAt":"2008-01-23T08:32:54Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Linus Torvalds wrote:\n> \n> NOTE NOTE NOTE! The current hash is a joke.\n\n\nInsofar as hashes go, it's not that shabby for hashing filenames.\nHere's the test output from a small hash-comparison program I've\ngot, which runs the test-input through a series of different hashes\nto compare dispersion, collisions, lookup- and insert times and\nother things that are interesting from a practical PoV.\n\nFowler/Noll/Vo cheap hash\nCollisions: 1829, 7.91%. Depth max: 3, average: 0.09.\nTime spent in lookups: 167.859ms. Per entry: 0.145us\nTime spent inserting: 2.753ms. Per entry: 0.119us\n\nPHP Zend cheap hash\nCollisions: 1908, 8.25%. Depth max: 3, average: 0.09.\nTime spent in lookups: 171.819ms. Per entry: 0.149us\nTime spent inserting: 2.778ms. Per entry: 0.120us\n\nPhong Vo's linear congruential hash\nCollisions: 1996, 8.63%. Depth max: 3, average: 0.09.\nTime spent in lookups: 168.276ms. Per entry: 0.146us\nTime spent inserting: 2.840ms. Per entry: 0.123us\n\nPhong Vo's second linear congruential hash\nCollisions: 1933, 8.36%. Depth max: 3, average: 0.09.\nTime spent in lookups: 170.416ms. Per entry: 0.147us\nTime spent inserting: 2.774ms. Per entry: 0.120us\n\nGlib string hash\nCollisions: 1907, 8.24%. Depth max: 3, average: 0.09.\nTime spent in lookups: 192.420ms. Per entry: 0.166us\nTime spent inserting: 3.154ms. Per entry: 0.136us\n\nsdbm hash\nCollisions: 1899, 8.21%. Depth max: 3, average: 0.09.\nTime spent in lookups: 170.797ms. Per entry: 0.148us\nTime spent inserting: 2.724ms. Per entry: 0.118us\n\nbfd hash\nCollisions: 1949, 8.43%. Depth max: 3, average: 0.09.\nTime spent in lookups: 206.504ms. Per entry: 0.179us\nTime spent inserting: 3.241ms. Per entry: 0.140us\n\nLinus' GIT hash\nCollisions: 1946, 8.41%. Depth max: 4, average: 0.09.\nTime spent in lookups: 179.336ms. Per entry: 0.155us\nTime spent inserting: 2.781ms. Per entry: 0.120us\n\nThis is with 64K buckets, which (with my implementation) means\na total hash-table size of 256KiB. The test-input is a simple\nfile-listing from the linux kernel (although it has the .git\ndirectory included too).\n\nAs you can see, it loses out on mathematical correctness, as it\nhas more collisions (but not that many). OTOH, the simplicity\nof the implementation makes it a viable option anyway, since\nthe time spent in insertion (which is almost completely inside\nthe hash-function) is on average so much shorter.\n\nFor a temporary hash-table, it will work splendidly. It will\nprobably have issues scaling to, say, 30 or 40 million input\nlines (fairly typical test-data for database hashes, fe).\n\nNote that real-world timings will be shorter. My test-program\ndoesn't have the luxury of keeping hash-functions inline, so\nsome compiler optimizations become impossible.\n\nThis is on a Intel(R) Core(TM)2 Duo CPU T7700 @ 2.40GHz\n(according to /proc/cpuinfo), with a cache size of 4meg. The\nuse of multiplication is sane though, as it means no arch\nwill suffer greatly.\n\nThe FNV hash would be better (pasted below), but I doubt\nanyone will ever care, and there will be larger differences\nbetween architectures with this one than the lt_git hash (well,\na function's gotta have a name).\n\n/*\n * Fowler/Noll/Vo hash\n *\n * The basis of the hash algorithm was taken from an idea sent by email to the\n * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and\n * Glenn Fowler (gsf@research.att.com). Landon Curt Noll (chongo@toad.com)\n * later improved on their algorithm.\n *\n * The magic is in the interesting relationship between the special prime\n * 16777619 (2^24 + 403) and 2^32 and 2^8.\n *\n * This hash produces the fewest collisions of any function that we've seen so\n * far, and works well on both numbers and strings.\n *\n * (Last comment from MySQL code)\n *\n */\nu32 FNV1(u8 *k, u32 len)\n{\n\tu8 *e;\n\tu32 h;\n\n\te = k + len;\n\tfor (h = 0; k < e; k++) {\n\t\th *= 16777619;\n\t\th ^= *k;\n\t}\n\n\treturn (h);\n}\n\n\nI could provide figures for other table-sizes too, if anyone's\ninterested.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"66384","messageId":"20080123091558.GP14871@dpotapov.dyndns.org","threadId":"11707","inReplyTo":"4796FBB6.9080609@op5.se","subject":"Re: I'm a total push-over..","fromName":"Dmitry Potapov","fromEmail":"dpotapov@gmail.com","sentAt":"2008-01-23T09:15:58Z","receivedAt":"2008-01-23T09:15:58Z","isPatch":false,"sender":{"key":"dpotapov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6568595?v=4"},"body":"On Wed, Jan 23, 2008 at 09:32:54AM +0100, Andreas Ericsson wrote:\n> \n> The FNV hash would be better (pasted below), but I doubt\n> anyone will ever care, and there will be larger differences\n> between architectures with this one than the lt_git hash (well,\n> a function's gotta have a name).\n\nActually, Bob Jenkins' lookup3 hash is twice faster in my tests\nthan FNV, and also it is much less likely to have any collision.\n\nThe description and some comparision with other hash can be found here:\nhttp://burtleburtle.net/bob/hash/doobs.html\nhttp://burtleburtle.net/bob/c/lookup3.c\n\nPerhaps, the second choice is Paul Hsieh's hash.\nhttp://www.azillionmonkeys.com/qed/hash.html\n\nNote: Paul Hsieh provides the table where he compares his hash\nwith others. There is also the program he used. I ran his program\non my computer, advantage of his over others was not so big on\nmy computer. Moreover, his test includes an old version of Bob\nJenkins' hash. The new version -- lookup3, which I mentione above,\nhas about the same speed as Paul Hsieh's hash (with -O2) or even\n12% faster when I used -O3 -march=athlon-xp.\n\nAlso, Bob Jenkins' hash is better for non-x86 architectures. So,\nI believe it is the best hash for today.\n\nDmitry\n"},{"id":"66396","messageId":"4797095F.9020602@op5.se","threadId":"11707","inReplyTo":"20080123091558.GP14871@dpotapov.dyndns.org","subject":"Re: I'm a total push-over..","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-01-23T09:31:11Z","receivedAt":"2008-01-23T09:31:11Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Dmitry Potapov wrote:\n> On Wed, Jan 23, 2008 at 09:32:54AM +0100, Andreas Ericsson wrote:\n>> The FNV hash would be better (pasted below), but I doubt\n>> anyone will ever care, and there will be larger differences\n>> between architectures with this one than the lt_git hash (well,\n>> a function's gotta have a name).\n> \n> Actually, Bob Jenkins' lookup3 hash is twice faster in my tests\n> than FNV, and also it is much less likely to have any collision.\n> \n\n>From http://burtleburtle.net/bob/hash/doobs.html\n---\nFNV Hash\n\nI need to fill this in. Search the web for FNV hash. It's faster than my hash on Intel (because Intel has fast multiplication), but slower on most other platforms. Preliminary tests suggested it has decent distributions. \n---\n\nMy tests ran on Intel. I also noticed I had a few hashes commented out when\ndoing the test, one of them being Paul Hsie's. For some reason, Jenkin's and\nHsie's didn't perform well for me last time I used the comparison thing (I\ndid a more thorough job back then, with tests running for several minutes\nper hash and table-size, so I commented out the poor candidates).\n\nI still believe that for this very simple case, the lookup3.c case is not\nvery practical, as the code is that much more complicated, which was my\nmain point with posting the comparison. Iow, not \"switch to this hash,\nbecause it's better\", but rather \"the hash is not as bad as you think and\nwill probably work well for all practical purposes\".\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"66391","messageId":"alpine.LSU.1.00.0801231221120.5731@racer.site","threadId":"11707","inReplyTo":"7v63xlqnd0.fsf@gitster.siamese.dyndns.org","subject":"Re: I'm a total push-over..","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-01-23T12:24:13Z","receivedAt":"2008-01-23T12:24:13Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 22 Jan 2008, Junio C Hamano wrote:\n\n> * We certainly do not necessarily want to store this in the\n> index right now. The hash algorithms would be improved from\n> the version you are almost ashamed of ;-). That sounds as if\n> I am retrating the other half, but not quite.\n> \n> * Once we have a mechanism to detect that the extension section\n> stores a precomputed hash that was done with a different\n> algorithm and ignore it (and recompute afresh when needed),\n> then we can afford to put a more elaborate hashing algorithm,\n> slightly loosening one of your \"Guiding principles\", and keep\n> the result in the generated index to be reused by the next\n> user. So that is why I am retracting only half of the\n> suggestion to save it in the extension section (which in turn\n> is a half of my suggestion).\n\nBoth issues (and the config variable issue Linus raised) are easily helped \nwith: store not only the hashmap in the extension, but also an identifier \nfor the hash method used.\n\nThen you can improve on the hash function all you like, and add the config \nvariable dependent choice of the hashing everybody seems to want all of a \nsudden, as long as you change the method identifier, too.\n\nCiao,\nDscho\n"},{"id":"66392","messageId":"alpine.LSU.1.00.0801231224300.5731@racer.site","threadId":"11707","inReplyTo":"7vprvtngxk.fsf@gitster.siamese.dyndns.org","subject":"Re: I'm a total push-over..","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-01-23T12:25:41Z","receivedAt":"2008-01-23T12:25:41Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 22 Jan 2008, Junio C Hamano wrote:\n\n> Linus Torvalds writes:\n> \n> > Basically, I dislike having two copies of the same data. If something \n> > can be computed from something else, then only the original data \n> > should exist, and the other thing should be recomputed.\n> \n> Yes, I agree with that in principle. Storing computable values makes \n> sense only when it is expensive to recompute. We did not have \n> cache-tree for quite a long time until you noticed that it was rather \n> expensive and wasteful to recompute tree objects from unchanged parts of \n> the index every time.\n> \n> It's the same argument; when the hashing performance starts to become \n> noticeable, we can think about storing and reusing it, not before.\n\nI fully expect it to be noticable with that UTF-8 \"normalisation\". But \nthen, the infrastructure is there, and whoever has an itch to scratch...\n\nCiao,\nDscho\n"},{"id":"66393","messageId":"85lk6giv4k.fsf@lola.goethe.zz","threadId":"11707","inReplyTo":"alpine.LSU.1.00.0801231221120.5731@racer.site","subject":"Re: I'm a total push-over..","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2008-01-23T12:28:27Z","receivedAt":"2008-01-23T12:28:27Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Johannes Schindelin writes:\n\n> Both issues (and the config variable issue Linus raised) are easily\n> helped with: store not only the hashmap in the extension, but also an\n> identifier for the hash method used.\n\nFor a reasonably implemented hash algorithm, computing the hash should\nbe cheaper than reading it from disk.\n\nSo storing precomputed hashes is not worth the trouble.\n\n-- \nDavid Kastrup, Kriemhildstr. 15, 44793 Bochum\n"},{"id":"66394","messageId":"20080123125637.GB7415@mit.edu","threadId":"11707","inReplyTo":"85lk6giv4k.fsf@lola.goethe.zz","subject":"Re: I'm a total push-over..","fromName":"Theodore Tso","fromEmail":"tytso@mit.edu","sentAt":"2008-01-23T12:56:37Z","receivedAt":"2008-01-23T12:56:37Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"On Wed, Jan 23, 2008 at 01:28:27PM +0100, David Kastrup wrote:\n> Johannes Schindelin writes:\n> \n> > Both issues (and the config variable issue Linus raised) are easily\n> > helped with: store not only the hashmap in the extension, but also an\n> > identifier for the hash method used.\n> \n> For a reasonably implemented hash algorithm, computing the hash should\n> be cheaper than reading it from disk.\n> \n> So storing precomputed hashes is not worth the trouble.\n\nYes, but if on Mac OS systems when the git repository is stored on an\nHFS+ system, the hash algorithm gets changed to one which forces\nUnicode strings which HFS+ happens to \"normalize\" into the same hash\nbucket pre- and post- normalization, it might not be cheap any\nmore....\n\n \t \t \t \t \t - Ted\n"},{"id":"66399","messageId":"e51f66da0801230601n6edd2639lff70415afa9f9026@mail.gmail.com","threadId":"11707","inReplyTo":"4797095F.9020602@op5.se","subject":"Re: I'm a total push-over..","fromName":"Marko Kreen","fromEmail":"markokr@gmail.com","sentAt":"2008-01-23T14:01:18Z","receivedAt":"2008-01-23T14:01:18Z","isPatch":false,"sender":{"key":"markokr@gmail.com","avatar":null},"body":"On 1/23/08, Andreas Ericsson wrote:\n> Dmitry Potapov wrote:\n> > On Wed, Jan 23, 2008 at 09:32:54AM +0100, Andreas Ericsson wrote:\n> >> The FNV hash would be better (pasted below), but I doubt\n> >> anyone will ever care, and there will be larger differences\n> >> between architectures with this one than the lt_git hash (well,\n> >> a function's gotta have a name).\n> >\n> > Actually, Bob Jenkins' lookup3 hash is twice faster in my tests\n> > than FNV, and also it is much less likely to have any collision.\n> >\n>\n> >From http://burtleburtle.net/bob/hash/doobs.html\n> ---\n> FNV Hash\n>\n> I need to fill this in. Search the web for FNV hash. It's faster than my hash on Intel (because Intel has fast multiplication), but slower on most other platforms. Preliminary tests suggested it has decent distributions.\n\nI suspect that this paragraph was about comparison with lookup2\n(not lookup3) because lookup3 beat easily all the \"simple\" hashes\nin my testing. Only competitor was Hsieh one which was like 50:50\nfaster or slower depending on alignment / compiler / cpu.\n\n> ---\n>\n> My tests ran on Intel. I also noticed I had a few hashes commented out when\n> doing the test, one of them being Paul Hsie's. For some reason, Jenkin's and\n> Hsie's didn't perform well for me last time I used the comparison thing (I\n> did a more thorough job back then, with tests running for several minutes\n> per hash and table-size, so I commented out the poor candidates).\n>\n> I still believe that for this very simple case, the lookup3.c case is not\n> very practical, as the code is that much more complicated, which was my\n> main point with posting the comparison. Iow, not \"switch to this hash,\n> because it's better\", but rather \"the hash is not as bad as you think and\n> will probably work well for all practical purposes\".\n\n\nIf you don't mind few percent speed penalty compared to Jenkings\nown optimized version, you can use my simplified version:\n\n http://repo.or.cz/w/pgbouncer.git?a=blob;f=src/hash.c;h=5c9a73639ad098c296c0be562c34573189f3e083;hb=HEAD\n\nIt works always with \"native\" endianess, unlike Jenkins fixed-endian\nhashlittle() / hashbig(). It may or may not matter if you plan\nto write values on disk.\n\nSpeed-wise it may be 10-30% slower worst case (in my case sparc-classic\nwith unaligned data), but on x86, lucky gcc version and maybe\nalso memcpy() hack seen in system.h, it tends to be ~10% faster,\nespecially as it does always 4byte read in main loop.\n\n-- \nmarko\n"},{"id":"66449","messageId":"4797518A.3040704@op5.se","threadId":"11707","inReplyTo":"e51f66da0801230601n6edd2639lff70415afa9f9026@mail.gmail.com","subject":"Re: I'm a total push-over..","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-01-23T14:39:06Z","receivedAt":"2008-01-23T14:39:06Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Marko Kreen wrote:\n> On 1/23/08, Andreas Ericsson wrote:\n>> Dmitry Potapov wrote:\n>>> On Wed, Jan 23, 2008 at 09:32:54AM +0100, Andreas Ericsson wrote:\n>>>> The FNV hash would be better (pasted below), but I doubt\n>>>> anyone will ever care, and there will be larger differences\n>>>> between architectures with this one than the lt_git hash (well,\n>>>> a function's gotta have a name).\n>>> Actually, Bob Jenkins' lookup3 hash is twice faster in my tests\n>>> than FNV, and also it is much less likely to have any collision.\n>>>\n>> >From http://burtleburtle.net/bob/hash/doobs.html\n>> ---\n>> FNV Hash\n>>\n>> I need to fill this in. Search the web for FNV hash. It's faster than my hash on Intel (because Intel has fast multiplication), but slower on most other platforms. Preliminary tests suggested it has decent distributions.\n> \n> I suspect that this paragraph was about comparison with lookup2\n\n\nIt might be. It's from the link Dmitry posted in his reply to my original\nmessage. (something/something/doobs.html).\n\n> (not lookup3) because lookup3 beat easily all the \"simple\" hashes\n\nBy how much? FNV beat Linus' hash by 0.01 microseconds / insertion,\nand 0.1 microsecons / lookup. We're talking about a case here where\nthere will never be more lookups than insertions (unless I'm much\nmistaken).\n\n> \n> If you don't mind few percent speed penalty compared to Jenkings\n> own optimized version, you can use my simplified version:\n> \n> http://repo.or.cz/w/pgbouncer.git?a=blob;f=src/hash.c;h=5c9a73639ad098c296c0be562c34573189f3e083;hb=HEAD\n> \n\nI don't, but I don't care that deeply either. On the one hand,\nit would be nifty to have an excellent hash-function in git.\nOn the other hand, it would look stupid with something that's\nquite clearly over-kill.\n\n> It works always with \"native\" endianess, unlike Jenkins fixed-endian\n> hashlittle() / hashbig(). It may or may not matter if you plan\n> to write values on disk.\n> \n> Speed-wise it may be 10-30% slower worst case (in my case sparc-classic\n> with unaligned data), but on x86, lucky gcc version and maybe\n> also memcpy() hack seen in system.h, it tends to be ~10% faster,\n> especially as it does always 4byte read in main loop.\n> \n\nIt would have to be a significant improvement in wall-clock time\non a test-case of hashing 30k strings to warrant going from 6 to 80\nlines of code, imo. I still believe the original dumb hash Linus\nwrote is \"good enough\".\n\nOn a side-note, it was very interesting reading, and I shall have\nto add jenkins3_mkreen() to my test-suite (although the \"keep\ncopyright note\" license thing bugs me a bit).\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"66406","messageId":"alpine.LFD.1.00.0801230754180.1741@woody.linux-foundation.org","threadId":"11707","inReplyTo":"4796FBB6.9080609@op5.se","subject":"Re: I'm a total push-over..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-23T16:06:40Z","receivedAt":"2008-01-23T16:06:40Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 23 Jan 2008, Andreas Ericsson wrote:\n> \n> Insofar as hashes go, it's not that shabby for hashing filenames.\n\nHashing filenames is pretty easy. You can do a reasonable job with any \n\"multiply by an odd number, add in value\". Picking the odd number is a \nrandom choice, some are better than others (and it depends on whether you \nend up always having a power-of-two bucket size etc), but it generally \nwon't be horrible.\n\nAnd considering that we generally won't have tons and tons of pathnames \n(ie we'd generally have thousands, not millions), and that the underlying \nhash not only resizes itself but actually uses the ful 32 bits as the \nlookup key, I don't worry too much. I suspect my random choice is fine.\n\nSo no, I didn't think my hash would _suck_, although I also didn't \nresearch which odd numbers to pick.\n\nNo, it's a joke because it doesn't really give an example of how to do the \n_expected_ hash collissions.\n\nHere's another hash that is actually going to collide *much* more (and on \npurpose!), but is actually showing an example of something that actually \nhashes UTF strings so that upper-case and lower-case (and normalization) \nwill all still hash to the same value:\n\n\tstatic unsigned int hash_name(const char *name, int namelen)\n\t{\n\t unsigned int hash = 0x123;\n\n\t do {\n\t unsigned char c = *name++;\n\t\t\tif (c & 0x80)\n\t\t\t\tc = 0;\n\t\t\tc &= ~0x20;\n\t hash = hash*101 + c;\n\t } while (--namelen);\n\t return hash;\n\t}\n\nbut the above does so by making the hash much much worse (although \nprobably still acceptable for \"normal source code name distributions\" \nthat don't have very many same-name-in-different-cases and high bit \ncharacters anyway).\n\nThe above is still fairly fast, but obviously at a serious cost in hash \ngoodness, to the point of being totally unusable for anybody who uses \nAsian characters in their filenames.\n\nTo actually be really useful, you'd have to teach it about the character \nsystem and do a lookup into a case/normalization table.\n\nSo *that* is mainly why it's a joke. But it should work fine for the case \nit is used for now (exact match).\n\nPicking a better-researched constant might still be a good idea.\n\n\t\tLinus\n"},{"id":"66409","messageId":"alpine.LFD.1.00.0801230817390.1741@woody.linux-foundation.org","threadId":"11707","inReplyTo":"alpine.LSU.1.00.0801231224300.5731@racer.site","subject":"Re: I'm a total push-over..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-23T16:25:01Z","receivedAt":"2008-01-23T16:25:01Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 23 Jan 2008, Johannes Schindelin wrote:\n> \n> I fully expect it to be noticable with that UTF-8 \"normalisation\". But \n> then, the infrastructure is there, and whoever has an itch to scratch...\n\nActually, it's going to be totally invisible even with UTF-8 \nnormalization, because we're going to do it sanely.\n\nAnd by \"sanely\" I mean just having the code test the high bit, and using \nUS-ASCII as-is (possibly with that \" & ~0x20 \" thing to ignore case in \nit).\n\nEnd result: practically all projects will never notice anything at all for \n99.9% of all files. One extra well-predicted branch, and a few more hash \ncollissions for cases where you have both \"Makefile\" and \"makefile\" etc.\n\nDoing names with *lots* of UTF-8 characters will be rather slower. It's \nstill not horrible to do if you do it the smart way, though. In fact, it's \npretty simple, just a few table lookups (one to find the NFD form, one to \ndo the upcasing).\n\nAnd yes, for hashing, it makes sense to turn things into NFD because it's \ngenerally simpler, but the point is that you really don't actually modify \nthe name itself at all, you just hash things (or compare things) character \nby expanded character.\n\nIOW, only a total *moron* does Unicode name comparisons with\n\n\tstrcmp(convert_to_nfd(a), convert_to_nfd(b));\n\nwhich is essentially what Apple does. It's quite possible to do\n\n\tutf8_nfd_strcmp(a,b)\n\nand (a) do it tons and tons faster and (b) never have to modify the \nstrings themselves. Same goes (even more) for hashing.\n\n\t\t\tLinus\n"},{"id":"66410","messageId":"alpine.LSU.1.00.0801231630480.5731@racer.site","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801230817390.1741@woody.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-01-23T16:34:51Z","receivedAt":"2008-01-23T16:34:51Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 23 Jan 2008, Linus Torvalds wrote:\n\n> On Wed, 23 Jan 2008, Johannes Schindelin wrote:\n> > \n> > I fully expect it to be noticable with that UTF-8 \"normalisation\". \n> > But then, the infrastructure is there, and whoever has an itch to \n> > scratch...\n> \n> Actually, it's going to be totally invisible even with UTF-8 \n> normalization, because we're going to do it sanely.\n> \n> And by \"sanely\" I mean just having the code test the high bit, and using \n> US-ASCII as-is (possibly with that \" & ~0x20 \" thing to ignore case in \n> it).\n> \n> End result: practically all projects will never notice anything at all for \n> 99.9% of all files. One extra well-predicted branch, and a few more hash \n> collissions for cases where you have both \"Makefile\" and \"makefile\" etc.\n\nWell, that's the point, to avoid having both \"Makefile\" and \"makefile\" in \nyour repository when you are on case-challenged filesystems, right?\n\n> Doing names with *lots* of UTF-8 characters will be rather slower. It's \n> still not horrible to do if you do it the smart way, though. In fact, \n> it's pretty simple, just a few table lookups (one to find the NFD form, \n> one to do the upcasing).\n> \n> And yes, for hashing, it makes sense to turn things into NFD because \n> it's generally simpler, but the point is that you really don't actually \n> modify the name itself at all, you just hash things (or compare things) \n> character by expanded character.\n> \n> IOW, only a total *moron* does Unicode name comparisons with\n> \n> \tstrcmp(convert_to_nfd(a), convert_to_nfd(b));\n> \n> which is essentially what Apple does.\n\nHeh, indeed that is what I would have done as an initial step (out of \nlaziness).\n\n> It's quite possible to do\n> \n> \tutf8_nfd_strcmp(a,b)\n> \n> and (a) do it tons and tons faster and (b) never have to modify the \n> strings themselves. Same goes (even more) for hashing.\n\nOkay. Point taken.\n\nBut I really hope that you are not proposing to use the case-ignoring \nhash when we are _not_ on a case-challenged filesystem...\n\nCiao,\nDscho\n"},{"id":"66416","messageId":"alpine.LFD.1.00.0801230906000.1741@woody.linux-foundation.org","threadId":"11707","inReplyTo":"alpine.LSU.1.00.0801231630480.5731@racer.site","subject":"Re: I'm a total push-over..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-23T17:09:46Z","receivedAt":"2008-01-23T17:09:46Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 23 Jan 2008, Johannes Schindelin wrote:\n>\n> > End result: practically all projects will never notice anything at all for \n> > 99.9% of all files. One extra well-predicted branch, and a few more hash \n> > collissions for cases where you have both \"Makefile\" and \"makefile\" etc.\n> \n> Well, that's the point, to avoid having both \"Makefile\" and \"makefile\" in \n> your repository when you are on case-challenged filesystems, right?\n\nRight. But what I'm saying is that this is *really* cheap to test for for \nUS-ASCII-only characters, and if only 0.1% of all filenames have unicode \nin them, the fact that they are much mroe expensive isn't even going to be \nnoticeable. Except for some very odd-ball environments.\n\n> > It's quite possible to do\n> > \n> > \tutf8_nfd_strcmp(a,b)\n> > \n> > and (a) do it tons and tons faster and (b) never have to modify the \n> > strings themselves. Same goes (even more) for hashing.\n> \n> Okay. Point taken.\n\nNote that one reason the above is tons faster is that even with complex \nunicode, the *common* case is going to be that the names match with a \nbinary compare.\n\n> But I really hope that you are not proposing to use the case-ignoring \n> hash when we are _not_ on a case-challenged filesystem...\n\nI actually suspect that we could, and nobody will notice. The hash would \ncause a few more collissions, but not so you'd know.\n\nAnd the thing is, people who work with other people who are on \ncase-challenged systems would still want to have the case-insenstive \ncompare too - although it should just warn, not actually \"work\".\n\n\t\t\tLinus\n"},{"id":"66414","messageId":"20080123171004.GS14871@dpotapov.dyndns.org","threadId":"11707","inReplyTo":"4797095F.9020602@op5.se","subject":"Re: I'm a total push-over..","fromName":"Dmitry Potapov","fromEmail":"dpotapov@gmail.com","sentAt":"2008-01-23T17:10:04Z","receivedAt":"2008-01-23T17:10:04Z","isPatch":false,"sender":{"key":"dpotapov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6568595?v=4"},"body":"On Wed, Jan 23, 2008 at 10:31:11AM +0100, Andreas Ericsson wrote:\n> ---\n> FNV Hash\n> \n> I need to fill this in. Search the web for FNV hash. It's faster than my \n> hash on Intel (because Intel has fast multiplication), but slower on most \n> other platforms. Preliminary tests suggested it has decent distributions. \n> ---\n\nI believe that under words \"my hash\", Bob Jenkins meant lookup2, which\nwas significant slower.\n\n> \n> My tests ran on Intel.\n\nPlease, could you specify your CPU model.\n\n> I also noticed I had a few hashes commented out when\n> doing the test, one of them being Paul Hsie's. For some reason, Jenkin's and\n> Hsie's didn't perform well for me last time I used the comparison thing (I\n> did a more thorough job back then, with tests running for several minutes\n> per hash and table-size, so I commented out the poor candidates).\n\nI expected that Paul Hsieh's hash may not do well on some architecture,\nthough it seems it did even worse than I expected.\n\n> \n> I still believe that for this very simple case, the lookup3.c case is not\n> very practical, as the code is that much more complicated, which was my\n> main point with posting the comparison.\n\nI would not describe lookup3 as impractical. It is widely used and well\ntested. Perhaps, for some Intel CPUs, the difference in speed is not so\nbig, and FNV hash is much smaller and simpler, so FNV is a reasonable\nchoice, but the hash is twice slower on my AMD processor and I suspect\nit may be even worse on other CPUs, where integer multiplication is slow.\nBesides, it may turn out that hashing filename may be not only case where\na fast hash is needed.\n\nDmitry\n"},{"id":"66419","messageId":"alpine.LFD.1.00.0801230922190.1741@woody.linux-foundation.org","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801230906000.1741@woody.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-23T17:29:31Z","receivedAt":"2008-01-23T17:29:31Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 23 Jan 2008, Linus Torvalds wrote:\n> \n> > But I really hope that you are not proposing to use the case-ignoring \n> > hash when we are _not_ on a case-challenged filesystem...\n> \n> I actually suspect that we could, and nobody will notice. The hash would \n> cause a few more collissions, but not so you'd know.\n\nTo clarify: the thing I want to point out that the decision to *hash* the \nfilenames in a case-insensitive hash, is very different from the decision \nto then *compare* the filenames when traversing the hash with a \ncase-insensitive compare.\n\nAnd this difference is actually very important. Hashing things together \nthat are \"equivalent\" according to any random rule is what makes it \npossible to then *check* for equivalence cheaply (because you only need to \nmake the potentially expensive check with the subset of cases where it \nmight trigger), but it in no way forces you to actually recode or mangle \nor compare things equivalently.\n\nIn fact, I'd argue that this is what HFS+ did wrong in the first place: \nthey had stupid/incompetent people who didn't understand about this, so \nthey normalized the string *before* the hashing rather than as part of the \nhash itself, and thus actually corrupt the string itself.\n\nSo what you can do (and I'd argue that we do) is to have a hash that can \nhandle almost arbitrary input, but then never corrupt the filename, and \nalways compare exactly by default.\n\nThen, depending on a config option, we can decide to change the compare so \nthat equivalent (according to whatever rule) filenames either cause a \nwarning (people on sane filesystems, but working with people who aren't), \nor are silently considered the same file (people on insane filesystems).\n\n\t\t\tLinus\n"},{"id":"66451","messageId":"F23CA352-416C-49EC-8132-688784CF3C18@vicaya.com","threadId":"11707","inReplyTo":"4797518A.3040704@op5.se","subject":"Re: I'm a total push-over..","fromName":"Luke Lu","fromEmail":"git@vicaya.com","sentAt":"2008-01-24T06:51:37Z","receivedAt":"2008-01-24T06:51:37Z","isPatch":false,"sender":{"key":"git@vicaya.com","avatar":null},"body":"On Jan 23, 2008, at 6:39 AM, Andreas Ericsson wrote:\n> Marko Kreen wrote:\n>> On 1/23/08, Andreas Ericsson wrote:\n>>> Dmitry Potapov wrote:\n>>>> On Wed, Jan 23, 2008 at 09:32:54AM +0100, Andreas Ericsson wrote:\n>>>>> The FNV hash would be better (pasted below), but I doubt\n>>>>> anyone will ever care, and there will be larger differences\n>>>>> between architectures with this one than the lt_git hash (well,\n>>>>> a function's gotta have a name).\n>>>> Actually, Bob Jenkins' lookup3 hash is twice faster in my tests\n>>>> than FNV, and also it is much less likely to have any collision.\n>>>>\n>>> >From http://burtleburtle.net/bob/hash/doobs.html\n>>> ---\n>>> FNV Hash\n>>>\n>>> I need to fill this in. Search the web for FNV hash. It's faster \n>>> than my hash on Intel (because Intel has fast multiplication), \n>>> but slower on most other platforms. Preliminary tests suggested \n>>> it has decent distributions.\n>> I suspect that this paragraph was about comparison with lookup2\n>\n>\n> It might be. It's from the link Dmitry posted in his reply to my \n> original\n> message. (something/something/doobs.html).\n>\n>> (not lookup3) because lookup3 beat easily all the \"simple\" hashes\n>\n> By how much? FNV beat Linus' hash by 0.01 microseconds / insertion,\n> and 0.1 microsecons / lookup. We're talking about a case here where\n> there will never be more lookups than insertions (unless I'm much\n> mistaken).\n>\n>> If you don't mind few percent speed penalty compared to Jenkings\n>> own optimized version, you can use my simplified version:\n>> http://repo.or.cz/w/pgbouncer.git?a=blob;f=src/ \n>> hash.c;h=5c9a73639ad098c296c0be562c34573189f3e083;hb=HEAD\n>\n> I don't, but I don't care that deeply either. On the one hand,\n> it would be nifty to have an excellent hash-function in git.\n> On the other hand, it would look stupid with something that's\n> quite clearly over-kill.\n>\n>> It works always with \"native\" endianess, unlike Jenkins fixed-endian\n>> hashlittle() / hashbig(). It may or may not matter if you plan\n>> to write values on disk.\n>> Speed-wise it may be 10-30% slower worst case (in my case sparc- \n>> classic\n>> with unaligned data), but on x86, lucky gcc version and maybe\n>> also memcpy() hack seen in system.h, it tends to be ~10% faster,\n>> especially as it does always 4byte read in main loop.\n>\n> It would have to be a significant improvement in wall-clock time\n> on a test-case of hashing 30k strings to warrant going from 6 to 80\n> lines of code, imo. I still believe the original dumb hash Linus\n> wrote is \"good enough\".\n>\n> On a side-note, it was very interesting reading, and I shall have\n> to add jenkins3_mkreen() to my test-suite (although the \"keep\n> copyright note\" license thing bugs me a bit).\n\nWould you, for completeness' sake, please add Tcl and STL hashes to \nyour test suite? The numbers are quite interesting. Is your test \nsuite available somewhere, so we can test with our own data and \nhardware as well. Both Tcl hash and STL (from SGI probably HP days, \nstill the current default with g++) string hashes are extremely \nsimple (excluding the loop constructs):\n\nTcl: h += (h<<3) + c; \t// essentially *9+c (but work better on non- \nlate-intels)\nSTL: h = h * 5 + c;\t// worse than above for most of my data\n\nThanks,\n\n__Luke\n"},{"id":"66469","messageId":"47986775.7010603@op5.se","threadId":"11707","inReplyTo":"F23CA352-416C-49EC-8132-688784CF3C18@vicaya.com","subject":"Re: I'm a total push-over..","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-01-24T10:24:53Z","receivedAt":"2008-01-24T10:24:53Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Luke Lu wrote:\n> On Jan 23, 2008, at 6:39 AM, Andreas Ericsson wrote:\n>> Marko Kreen wrote:\n>>> On 1/23/08, Andreas Ericsson wrote:\n>>>> Dmitry Potapov wrote:\n>>>>> On Wed, Jan 23, 2008 at 09:32:54AM +0100, Andreas Ericsson wrote:\n>>>>>> The FNV hash would be better (pasted below), but I doubt\n>>>>>> anyone will ever care, and there will be larger differences\n>>>>>> between architectures with this one than the lt_git hash (well,\n>>>>>> a function's gotta have a name).\n>>>>> Actually, Bob Jenkins' lookup3 hash is twice faster in my tests\n>>>>> than FNV, and also it is much less likely to have any collision.\n>>>>>\n>>>> >From http://burtleburtle.net/bob/hash/doobs.html\n>>>> ---\n>>>> FNV Hash\n>>>>\n>>>> I need to fill this in. Search the web for FNV hash. It's faster \n>>>> than my hash on Intel (because Intel has fast multiplication), but \n>>>> slower on most other platforms. Preliminary tests suggested it has \n>>>> decent distributions.\n>>> I suspect that this paragraph was about comparison with lookup2\n>>\n>>\n>> It might be. It's from the link Dmitry posted in his reply to my original\n>> message. (something/something/doobs.html).\n>>\n>>> (not lookup3) because lookup3 beat easily all the \"simple\" hashes\n>>\n>> By how much? FNV beat Linus' hash by 0.01 microseconds / insertion,\n>> and 0.1 microsecons / lookup. We're talking about a case here where\n>> there will never be more lookups than insertions (unless I'm much\n>> mistaken).\n>>\n>>> If you don't mind few percent speed penalty compared to Jenkings\n>>> own optimized version, you can use my simplified version:\n>>> \n>>> http://repo.or.cz/w/pgbouncer.git?a=blob;f=src/hash.c;h=5c9a73639ad098c296c0be562c34573189f3e083;hb=HEAD \n>>>\n>>\n>> I don't, but I don't care that deeply either. On the one hand,\n>> it would be nifty to have an excellent hash-function in git.\n>> On the other hand, it would look stupid with something that's\n>> quite clearly over-kill.\n>>\n>>> It works always with \"native\" endianess, unlike Jenkins fixed-endian\n>>> hashlittle() / hashbig(). It may or may not matter if you plan\n>>> to write values on disk.\n>>> Speed-wise it may be 10-30% slower worst case (in my case sparc-classic\n>>> with unaligned data), but on x86, lucky gcc version and maybe\n>>> also memcpy() hack seen in system.h, it tends to be ~10% faster,\n>>> especially as it does always 4byte read in main loop.\n>>\n>> It would have to be a significant improvement in wall-clock time\n>> on a test-case of hashing 30k strings to warrant going from 6 to 80\n>> lines of code, imo. I still believe the original dumb hash Linus\n>> wrote is \"good enough\".\n>>\n>> On a side-note, it was very interesting reading, and I shall have\n>> to add jenkins3_mkreen() to my test-suite (although the \"keep\n>> copyright note\" license thing bugs me a bit).\n> \n> Would you, for completeness' sake, please add Tcl and STL hashes to your \n> test suite?\n\nI could do that. Or I just publish the entire ugly thing and let someone\nelse add them ;-)\n\n> The numbers are quite interesting. Is your test suite \n> available somewhere, so we can test with our own data and hardware as \n> well.\n\nNot yet, no. I usually munge it up quite a lot when I want to test hashes\nfor a specific input, so it's not what anyone would call \"pretty\".\n\n> Both Tcl hash and STL (from SGI probably HP days, still the \n> current default with g++) string hashes are extremely simple (excluding \n> the loop constructs):\n> \n> Tcl: h += (h<<3) + c; // essentially *9+c (but work better on \n> non-late-intels)\n> STL: h = h * 5 + c; // worse than above for most of my data\n> \n\nThey sure do look simple enough. As for loop constructs, I've tried to\nuse the same looping mechanics for everything, so as to let the algorithm\nbe the only difference. Otherwise it gets tricky to do comparisons. The\nexceptions are ofcourse hashes relying on Duff's device or similar\nalignment trickery.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"66470","messageId":"47986AD4.3070303@op5.se","threadId":"11707","inReplyTo":"20080123171004.GS14871@dpotapov.dyndns.org","subject":"Re: I'm a total push-over..","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-01-24T10:39:16Z","receivedAt":"2008-01-24T10:39:16Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Dmitry Potapov wrote:\n> On Wed, Jan 23, 2008 at 10:31:11AM +0100, Andreas Ericsson wrote:\n>> ---\n>> FNV Hash\n>>\n>> I need to fill this in. Search the web for FNV hash. It's faster than my \n>> hash on Intel (because Intel has fast multiplication), but slower on most \n>> other platforms. Preliminary tests suggested it has decent distributions. \n>> ---\n> \n> I believe that under words \"my hash\", Bob Jenkins meant lookup2, which\n> was significant slower.\n> \n>> My tests ran on Intel.\n> \n> Please, could you specify your CPU model.\n> \n\n>From /proc/cpuinfo. It's the best I can do without going to our purchase\ndepartment and asking for the spec so I can contact the vendor and get\nthe real thing. Dualcore shouldn't matter for this test, as it isn't\nthreaded.\nIntel(R) Core(TM)2 Duo CPU T7700 @ 2.40GHz\n\n>> I also noticed I had a few hashes commented out when\n>> doing the test, one of them being Paul Hsie's. For some reason, Jenkin's and\n>> Hsie's didn't perform well for me last time I used the comparison thing (I\n>> did a more thorough job back then, with tests running for several minutes\n>> per hash and table-size, so I commented out the poor candidates).\n> \n> I expected that Paul Hsieh's hash may not do well on some architecture,\n> though it seems it did even worse than I expected.\n> \n\nIt doesn't do that well on certain types of data, in my experience. It does\nhave excellent dispersion, so with very long strings it's usually the\nbest to use, because collisions become so expensive.\n\n>> I still believe that for this very simple case, the lookup3.c case is not\n>> very practical, as the code is that much more complicated, which was my\n>> main point with posting the comparison.\n> \n> I would not describe lookup3 as impractical. It is widely used and well\n> tested. Perhaps, for some Intel CPUs, the difference in speed is not so\n> big, and FNV hash is much smaller and simpler, so FNV is a reasonable\n> choice, but the hash is twice slower on my AMD processor and I suspect\n> it may be even worse on other CPUs, where integer multiplication is slow.\n> Besides, it may turn out that hashing filename may be not only case where\n> a fast hash is needed.\n> \n\nAh well. I think once the patch is in master, it will be easy enough to\ntest and verify different algorithms. Since it's intended for in-memory\ndata only, it's no problem to have several algorithms and pick the one\nmost suitable for the architecture we're compiling for.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"66474","messageId":"e51f66da0801240519u4c8e6ddfrb7af8df34552252a@mail.gmail.com","threadId":"11707","inReplyTo":"4797518A.3040704@op5.se","subject":"Re: I'm a total push-over..","fromName":"Marko Kreen","fromEmail":"markokr@gmail.com","sentAt":"2008-01-24T13:19:46Z","receivedAt":"2008-01-24T13:19:46Z","isPatch":false,"sender":{"key":"markokr@gmail.com","avatar":null},"body":"On 1/23/08, Andreas Ericsson wrote:\n> Marko Kreen wrote:\n> > (not lookup3) because lookup3 beat easily all the \"simple\" hashes\n>\n> By how much? FNV beat Linus' hash by 0.01 microseconds / insertion,\n> and 0.1 microsecons / lookup. We're talking about a case here where\n> there will never be more lookups than insertions (unless I'm much\n> mistaken).\n\nFNV is around 40% slower than lookup3 on my Intel Core CPU, on 4byte aligned\ninput. See below for more detailed info.\n\n> > If you don't mind few percent speed penalty compared to Jenkings\n> > own optimized version, you can use my simplified version:\n> >\n> > http://repo.or.cz/w/pgbouncer.git?a=blob;f=src/hash.c;h=5c9a73639ad098c296c0be562c34573189f3e083;hb=HEAD\n>\n> I don't, but I don't care that deeply either. On the one hand,\n> it would be nifty to have an excellent hash-function in git.\n> On the other hand, it would look stupid with something that's\n> quite clearly over-kill.\n\nJenkins hash is fast because it does not look at individual bytes.\nIf you _do_ want to look at them for unrelated reasons, (case-insensitive,\nunicode-juggling), then it obiously loses the point. That is, if you\nwant to process the string in one go.\n\n> > It works always with \"native\" endianess, unlike Jenkins fixed-endian\n> > hashlittle() / hashbig(). It may or may not matter if you plan\n> > to write values on disk.\n> >\n> > Speed-wise it may be 10-30% slower worst case (in my case sparc-classic\n> > with unaligned data), but on x86, lucky gcc version and maybe\n> > also memcpy() hack seen in system.h, it tends to be ~10% faster,\n> > especially as it does always 4byte read in main loop.\n>\n> It would have to be a significant improvement in wall-clock time\n> on a test-case of hashing 30k strings to warrant going from 6 to 80\n> lines of code, imo. I still believe the original dumb hash Linus\n> wrote is \"good enough\".\n\nWell, ad-hoc dumb hashes may have horrible worst-cases that you cant\nsee with light testing. Therefore I'd still suggest some better\nresearched dumb hash (eg. FNV or OAT).\n\n> On a side-note, it was very interesting reading, and I shall have\n> to add jenkins3_mkreen() to my test-suite (although the \"keep\n> copyright note\" license thing bugs me a bit).\n\nSorry. I just used template boilerplate. Considering all the\nhard work was done by other people, it not proper to put under\nmy own license. I tagged the file as 'public domain' and pushed out.\n\nBtw, the reason I started cleaning lookup3 was that at first I was\nscared of the complexity of Jenkins code and decided to go with\nHsieh hash. Then I found out that Hsieh code is under totally\nwerdo license (http://www.azillionmonkeys.com/qed/weblicense.html)\nso I could not use it.\n\n====================================================================\n\nHere is my raw-speed test of different hashes. Input is 4-byte\naligned which should be common case for malloc()-ed strings.\nThis also is best case for original lookup3(), on unaligned\ninput the memcpy variants beat it easily. Input string\nlength varies randomly in range 0..64.\n\nown_memcpy - last 12-byte memcpy() calls out to libc\nmemcpy_hack - last memcpy is inlined bytewise copy loop:\n\n while (len--) *dst++ = *src++;\n\nNote that is is raw-speed test, if you benchmark larger code the\nhash difference probably matters less.\n\n--------------------------------------------------------------------\n\nTesting: seed=34 align=4 minlen=0 maxlen=64 trycnt=2 duration=10\n\nlookup3 : try=0: ... 247.4880 MB/s\nlookup3 : try=1: ... 247.6154 MB/s\nown_memcpy: try=0: ... 223.5508 MB/s\nown_memcpy: try=1: ... 223.5830 MB/s\nmemcpy_hack: try=0: ... 241.2241 MB/s\nmemcpy_hack: try=1: ... 241.2492 MB/s\nlookup2 : try=0: ... 190.2697 MB/s\nlookup2 : try=1: ... 190.3283 MB/s\nfnv : try=0: ... 153.0318 MB/s\nfnv : try=1: ... 153.0178 MB/s\nhsieh : try=0: ... 234.0468 MB/s\nhsieh : try=1: ... 234.0426 MB/s\noat : try=0: ... 154.7804 MB/s\noat : try=1: ... 154.8226 MB/s\nelf : try=0: ... 125.5892 MB/s\nelf : try=1: ... 125.5734 MB/s\n\nResults compared to reference:\n\nlookup3 : 100.000 %\nown_memcpy : 90.311 %\nmemcpy_hack : 97.449 %\nlookup2 : 76.872 %\nfnv : 61.815 %\nhsieh : 94.544 %\noat : 62.533 %\nelf : 50.729 %\n\n\n-- \nmarko\n"},{"id":"66484","messageId":"4798B633.8040606@op5.se","threadId":"11707","inReplyTo":"e51f66da0801240519u4c8e6ddfrb7af8df34552252a@mail.gmail.com","subject":"Re: I'm a total push-over..","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-01-24T16:00:51Z","receivedAt":"2008-01-24T16:00:51Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Marko Kreen wrote:\n> On 1/23/08, Andreas Ericsson wrote:\n>> Marko Kreen wrote:\n>>> (not lookup3) because lookup3 beat easily all the \"simple\" hashes\n>> By how much? FNV beat Linus' hash by 0.01 microseconds / insertion,\n>> and 0.1 microsecons / lookup. We're talking about a case here where\n>> there will never be more lookups than insertions (unless I'm much\n>> mistaken).\n> \n> FNV is around 40% slower than lookup3 on my Intel Core CPU, on 4byte aligned\n> input. See below for more detailed info.\n> \n\nBut the tests surely need to check for unaligned cases, as that's what\nwe're likely to hash, no?\n\n>>> If you don't mind few percent speed penalty compared to Jenkings\n>>> own optimized version, you can use my simplified version:\n>>>\n>>> http://repo.or.cz/w/pgbouncer.git?a=blob;f=src/hash.c;h=5c9a73639ad098c296c0be562c34573189f3e083;hb=HEAD\n>> I don't, but I don't care that deeply either. On the one hand,\n>> it would be nifty to have an excellent hash-function in git.\n>> On the other hand, it would look stupid with something that's\n>> quite clearly over-kill.\n> \n> Jenkins hash is fast because it does not look at individual bytes.\n> If you _do_ want to look at them for unrelated reasons, (case-insensitive,\n> unicode-juggling), then it obiously loses the point. That is, if you\n> want to process the string in one go.\n> \n\nI believe the ability to add unicode-juggling was a major point\nwith the patch, so perhaps Jenkins' isn't such a good option.\n\nI'm not familiar with data-mangling the way Linus (or Theo Tso\nis), so I hadn't even considered that aspect of unrolled hashes.\n\n>> It would have to be a significant improvement in wall-clock time\n>> on a test-case of hashing 30k strings to warrant going from 6 to 80\n>> lines of code, imo. I still believe the original dumb hash Linus\n>> wrote is \"good enough\".\n> \n> Well, ad-hoc dumb hashes may have horrible worst-cases that you cant\n> see with light testing. Therefore I'd still suggest some better\n> researched dumb hash (eg. FNV or OAT).\n> \n\nTrue. FNV is used in both MySQL and PostgreSQL. I'd say it's safe to\nassume it's fairly well tested.\n\n>> On a side-note, it was very interesting reading, and I shall have\n>> to add jenkins3_mkreen() to my test-suite (although the \"keep\n>> copyright note\" license thing bugs me a bit).\n> \n> Sorry. I just used template boilerplate. Considering all the\n> hard work was done by other people, it not proper to put under\n> my own license. I tagged the file as 'public domain' and pushed out.\n> \n\nThanks. I'll see if I can add it, although it'll probably have to\nwait until I have reason to dig into it at work again. I've added\nthe hash to the code-base, but not yet incorporated it into the\ntest-case.\n\n> Btw, the reason I started cleaning lookup3 was that at first I was\n> scared of the complexity of Jenkins code and decided to go with\n> Hsieh hash. Then I found out that Hsieh code is under totally\n> werdo license (http://www.azillionmonkeys.com/qed/weblicense.html)\n> so I could not use it.\n> \n\nTrue. I was in contact with him a while back since I wanted to use it\nin an opensource project, but the licensing issues made me go with\nanother one instead. The patch got turned down anyways, so it was a\nnon-issue in the end, but... Ah well.\n\n> \n> Here is my raw-speed test of different hashes. Input is 4-byte\n> aligned which should be common case for malloc()-ed strings.\n\nUnless arena allocated, like we do in git.\n\nI'm not surprised that this test favours Jenkin's and Hsie's.\nThat's to be expected as those benefit far more than simpler\nhashing algorithms for long strings. The overhead when trying\nshorter strings (say, between 3 and 15 chars, and not necessarily\n4-byte aligned) sometimes make them quite a lot slower though.\n\n> This also is best case for original lookup3(), on unaligned\n> input the memcpy variants beat it easily. Input string\n> length varies randomly in range 0..64.\n> \n\nWell, memcpy() isn't very interesting to compare against\nhashes, as they test vastly different parts of the hardware's\nparts' performance. memcpy() should also perform exactly the\nsame no matter what the test-data, which isn't always true for\nhashes.\n\nWhat *would* be interesting would be something along the lines\nof \"duff_cpy()\": ie, an unrolled loop that aligns itself and\ncopies each byte to the same address each time.\n\nThe bytewise equivalence would ofcourse be\n\nmagic_cpy(unsigned char *k, int len)\n{\n\tunsigned char magic;\n\tdo {\n\t\tmagic = *k++;\n\t} while (--len);\n}\n\n> own_memcpy - last 12-byte memcpy() calls out to libc\n> memcpy_hack - last memcpy is inlined bytewise copy loop:\n> \n> while (len--) *dst++ = *src++;\n> \n> Note that is is raw-speed test, if you benchmark larger code the\n> hash difference probably matters less.\n> \n> --------------------------------------------------------------------\n> \n> Testing: seed=34 align=4 minlen=0 maxlen=64 trycnt=2 duration=10\n> \n> lookup3 : try=0: ... 247.4880 MB/s\n> lookup3 : try=1: ... 247.6154 MB/s\n> own_memcpy: try=0: ... 223.5508 MB/s\n> own_memcpy: try=1: ... 223.5830 MB/s\n> memcpy_hack: try=0: ... 241.2241 MB/s\n> memcpy_hack: try=1: ... 241.2492 MB/s\n> lookup2 : try=0: ... 190.2697 MB/s\n> lookup2 : try=1: ... 190.3283 MB/s\n> fnv : try=0: ... 153.0318 MB/s\n> fnv : try=1: ... 153.0178 MB/s\n> hsieh : try=0: ... 234.0468 MB/s\n> hsieh : try=1: ... 234.0426 MB/s\n> oat : try=0: ... 154.7804 MB/s\n> oat : try=1: ... 154.8226 MB/s\n> elf : try=0: ... 125.5892 MB/s\n> elf : try=1: ... 125.5734 MB/s\n> \n> Results compared to reference:\n> \n> lookup3 : 100.000 %\n> own_memcpy : 90.311 %\n> memcpy_hack : 97.449 %\n> lookup2 : 76.872 %\n> fnv : 61.815 %\n> hsieh : 94.544 %\n> oat : 62.533 %\n> elf : 50.729 %\n> \n> \n\nInteresting output, but not very surprising. Do you have the code\navailable somewhere?\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"66486","messageId":"e51f66da0801240813v61d3bc74x2863eb37678439db@mail.gmail.com","threadId":"11707","inReplyTo":"4798B633.8040606@op5.se","subject":"Re: I'm a total push-over..","fromName":"Marko Kreen","fromEmail":"markokr@gmail.com","sentAt":"2008-01-24T16:13:02Z","receivedAt":"2008-01-24T16:13:02Z","isPatch":false,"sender":{"key":"markokr@gmail.com","avatar":null},"body":"On 1/24/08, Andreas Ericsson wrote:\n> Marko Kreen wrote:\n> > On 1/23/08, Andreas Ericsson wrote:\n> >> Marko Kreen wrote:\n> >>> (not lookup3) because lookup3 beat easily all the \"simple\" hashes\n> >> By how much? FNV beat Linus' hash by 0.01 microseconds / insertion,\n> >> and 0.1 microsecons / lookup. We're talking about a case here where\n> >> there will never be more lookups than insertions (unless I'm much\n> >> mistaken).\n> >\n> > FNV is around 40% slower than lookup3 on my Intel Core CPU, on 4byte aligned\n> > input. See below for more detailed info.\n> >\n>\n> But the tests surely need to check for unaligned cases, as that's what\n> we're likely to hash, no?\n\n\n\n> >> It would have to be a significant improvement in wall-clock time\n> >> on a test-case of hashing 30k strings to warrant going from 6 to 80\n> >> lines of code, imo. I still believe the original dumb hash Linus\n> >> wrote is \"good enough\".\n> >\n> > Well, ad-hoc dumb hashes may have horrible worst-cases that you cant\n> > see with light testing. Therefore I'd still suggest some better\n> > researched dumb hash (eg. FNV or OAT).\n> >\n>\n> True. FNV is used in both MySQL and PostgreSQL. I'd say it's safe to\n> assume it's fairly well tested.\n\nPostgreSQL uses lookup2...\n\n> > Here is my raw-speed test of different hashes. Input is 4-byte\n> > aligned which should be common case for malloc()-ed strings.\n>\n> Unless arena allocated, like we do in git.\n>\n> I'm not surprised that this test favours Jenkin's and Hsie's.\n> That's to be expected as those benefit far more than simpler\n> hashing algorithms for long strings. The overhead when trying\n> shorter strings (say, between 3 and 15 chars, and not necessarily\n> 4-byte aligned) sometimes make them quite a lot slower though.\n\nOk, here is 0..15 chars, random alignment:\n\nTesting: seed=34 align=0 minlen=0 maxlen=15 trycnt=2 duration=10\n\nlookup3 : try=0: ... 69.8092 MB/s\nlookup3 : try=1: ... 69.8146 MB/s\nown_memcpy: try=0: ... 66.7808 MB/s\nown_memcpy: try=1: ... 66.7814 MB/s\nmemcpy_hack: try=0: ... 74.0635 MB/s\nmemcpy_hack: try=1: ... 74.0518 MB/s\nlookup2 : try=0: ... 68.6582 MB/s\nlookup2 : try=1: ... 68.6634 MB/s\nfnv : try=0: ... 74.5098 MB/s\nfnv : try=1: ... 74.5283 MB/s\nhsieh : try=0: ... 71.6708 MB/s\nhsieh : try=1: ... 71.6814 MB/s\noat : try=0: ... 74.7828 MB/s\noat : try=1: ... 74.7716 MB/s\nelf : try=0: ... 65.2077 MB/s\nelf : try=1: ... 65.2128 MB/s\n\nResults compared to reference:\n\nlookup3 : 100.000 %\nown_memcpy : 95.659 %\nmemcpy_hack : 106.082 %\nlookup2 : 98.351 %\nfnv : 106.743 %\nhsieh : 102.670 %\noat : 107.112 %\nelf : 93.409 %\n\n> > This also is best case for original lookup3(), on unaligned\n> > input the memcpy variants beat it easily. Input string\n> > length varies randomly in range 0..64.\n> >\n>\n> Well, memcpy() isn't very interesting to compare against\n> hashes, as they test vastly different parts of the hardware's\n> parts' performance. memcpy() should also perform exactly the\n> same no matter what the test-data, which isn't always true for\n> hashes.\n\nSorry, I meant my \"simple-memcpy-based-lookup3\".\n\n> What *would* be interesting would be something along the lines\n> of \"duff_cpy()\": ie, an unrolled loop that aligns itself and\n> copies each byte to the same address each time.\n\nHow the hash fetched data from mempry is _very_ relevant.\n\n> Interesting output, but not very surprising. Do you have the code\n> available somewhere?\n\nI can put it out.\n\n-- \nmarko\n"},{"id":"66489","messageId":"37fcd2780801240828vac82e6ds4da5aecde56e8d2f@mail.gmail.com","threadId":"11707","inReplyTo":"4798B633.8040606@op5.se","subject":"Re: I'm a total push-over..","fromName":"Dmitry Potapov","fromEmail":"dpotapov@gmail.com","sentAt":"2008-01-24T16:28:28Z","receivedAt":"2008-01-24T16:28:28Z","isPatch":false,"sender":{"key":"dpotapov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6568595?v=4"},"body":"On Jan 24, 2008 7:00 PM, Andreas Ericsson wrote:\n> Marko Kreen wrote:\n> >\n> > Jenkins hash is fast because it does not look at individual bytes.\n> > If you _do_ want to look at them for unrelated reasons, (case-insensitive,\n> > unicode-juggling), then it obiously loses the point. That is, if you\n> > want to process the string in one go.\n> >\n>\n> I believe the ability to add unicode-juggling was a major point\n> with the patch, so perhaps Jenkins' isn't such a good option.\n\nI don't think you can any meaningful unicode-juggling without converting\nsymbols to UCS-4, and after that it makes much more sense to operate\nwith uint32 than bytes. So, Jenkins' hash is still relevant, just because\nit does not operate on single bytes, but using uint32.\n\nDmitry\n"},{"id":"66492","messageId":"alpine.LFD.1.00.0801240839590.2803@woody.linux-foundation.org","threadId":"11707","inReplyTo":"37fcd2780801240828vac82e6ds4da5aecde56e8d2f@mail.gmail.com","subject":"Re: I'm a total push-over..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-24T17:15:43Z","receivedAt":"2008-01-24T17:15:43Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 24 Jan 2008, Dmitry Potapov wrote:\n> \n> I don't think you can any meaningful unicode-juggling without converting\n> symbols to UCS-4, and after that it makes much more sense to operate\n> with uint32 than bytes. So, Jenkins' hash is still relevant, just because\n> it does not operate on single bytes, but using uint32.\n\nNo, no, no, NO!\n\nEgads! Why do people constantly do these totally idiotic things for \nUnicode?\n\nYou can do a perfectly fine 8-bytes-at-a-time hash for almost 100% of all \nsource code projects in UTF-8, without *ever* doing any format changes at \nall. Admittedly, it's a lot easier if the hash is a pure in-memory one (ie \nwe don't care about byte-order or size of integers or anything like that), \nbut that's the common case for most hashes that aren't used for BTree \nlookup on disk or something like that.\n\nHere, let me show you:\n\n\tunsigned int name_hash(const char *name, int size)\n\t{\n\t\thash = HASH_INIT;\n\t\tdo {\n\t\t\tunsigned char c;\n\t\t\tif (size >= sizeof(long)) {\n\t\t\t\tunsigned long val = get_unaligned_long(name);\n\t\t\t\tif (!(val & 0x8080808080808080)) {\n\t\t\t\t\t/* Make it equivalent in case */\n\t\t\t\t\tval &= ~0x2020202020202020;\n\t\t\t\t\thash = hash_long(hash, val);\n\t\t\t\t\tname += sizeof(long);\n\t\t\t\t\tsize -= sizeof(long);\n\t\t\t\t\tcontinue;\n\t\t\t\t}\n\t\t\t}\n\n\t\t\tc = *name;\n\t\t\tif (!(c & 0x80)) {\n\t\t\t\thash = hash_long(hash, c & ~0x20);\n\t\t\t\tname++;\n\t\t\t\tsize--;\n\t\t\t\tcontinue;\n\t\t\t}\n\n\t\t\t/* This is the unusual and slowish case */\n\t\t\thash = hash_utf8_char(hash, c, &name, &size);\n\t\t} while (size);\n\t\treturn hassh;\n\t}\n\nand then the only point you ever do that actual UTF8->codepoint conversion \nis for that \"high bit set\" case.\n\nA few things to note on the above:\n\n - the hash obviously has \"odd\" characteristics. We're not necessarily \n hashing characters at a time at all, and the alignment of characters \n with high bits *within*the*string* will make a difference to how we \n hash them.\n\n But it's also important that the \"get_unaligned_long()\" means that the \n alignment of the string itself doesn't matter, so its' purely a \n \"chunking within the string\" thing, and the alignment of the string \n itself won't affect the hash value\n\n - I'm not writing out hash_utf8_char(), because it's certainly not \n totally trivial, but it's not *really* complex either. The \n nontriviality isn't so much the decoding into a codepoint (which is \n pretty simple), but the fact that when you have the codepoint you \n should then decompose it and turn it into lower case, which is \n generally two table lookups. Then, you just do\n\n\tfor_each_decomposed_uppercased_codepoint(c)\n\t\thash = hash_long(hash, c);\n\n and one thing to note is that for the hashing, the decomposition and \n uppercasing doesn't even have to be \"exact\" (the same way I didn't do \n an \"exact\" upper-casing for US-ASCII, just a \"good enough\" one!)\n\nSimilarly, when you actually do a unicode *compare* function, you should \nnever *ever* actually convert to any unicode codepoints or do any \nexpensive decomposition AT ALL by default! What you do is to compare \nthings byte-by-byte, and only convert to unicode/decompse if there are any \ndifferences, and only for those parts of the sequence that differ!\n\nSo if you have two UTF-8 strings (even if they have \"complex\" characters, \nie with the high bit set), the *common* case is that you'll match them \nbyte for byte, and they'll match without any Unicode conversion needed at \nall! This is common because:\n\n - normally, even if you don't ever normalize, people tend to input things \n in a *similar* manner (again, OS X is the odd man out), so even \n non-normalized strings are often non-normalized the same way!\n\n - we're only going to compare things that have hashed to the same thing \n anyway, so the common case is that it's the same string, and most \n likely had the same source. And if it's a collision, it's often totally \n different. And even if it's different only in case, the *common* case \n is going to be (for source code trees, at least) that the different \n point is a US-ASCII letter, and the case-comparison will again be done \n without any Unicode knowledge at all!\n\nThis is why normalization of strings before-hand is generally so utterly \nstupid. It doesn't buy you anything. It complicates things a lot (you \ndon't want to normalize in-place, so you have memory management issues), \nand it actually SLOWS THINGS DOWN.\n\nIt's much better to do UTF-8 comparisons and hashing char-by-char. At \nleast if you know that the common case is not going to be the complex part \nof the character set (which is undoubtedly true for source code \nfilenames). \n\nNormalizing things ahead of time *only* makes sense if:\n\n - you expect complex characters to be a big part of your load\n\nand\n\n - you're going to do literally *thousands* of comparisons against the \n *same* strings over and over (so that the cost of normalization is\n literally up-front)\n\nFor example, for a filesystem, it's true that you're going to compare \nagainst the *target* (on-disk) multiple times, but that doesn't actually \nmean that normalizing it makes any sense - because the data you're going \nto compare against comes from user space and isn't guaranteed to be \nnormalized, so you still cannot do a simple memcmp() without the expense \nof normalizing that.\n\nAnd since you're going to hash the filenames anyway, you will not have \n\"thousands of comparisons\" per source lookup, you'll generally only have a \ncouple, so now your normalization actually cost you *more* than doing the \nabove on-the-fly comparison!\n\nSee?\n\nBasically, it's almost always a stupid thing to actually normalize a whole \nstring. You do those things character-by-character, and only lazily when \nyou actually need to!\n\n\t\t\tLinus\n"},{"id":"66505","messageId":"37fcd2780801241045o359c19b3h4e2b0c3cf6786aa@mail.gmail.com","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801240839590.2803@woody.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Dmitry Potapov","fromEmail":"dpotapov@gmail.com","sentAt":"2008-01-24T18:45:18Z","receivedAt":"2008-01-24T18:45:18Z","isPatch":false,"sender":{"key":"dpotapov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6568595?v=4"},"body":"On Thu, Jan 24, 2008 at 09:15:43AM -0800, Linus Torvalds wrote:\n>\n>\n> You can do a perfectly fine 8-bytes-at-a-time hash for almost 100% of all\n\nI suppose 8 bytes for 64-bit platforms and 4 bytes for 32-bits.\n\n>\n> \tunsigned int name_hash(const char *name, int size)\n> \t{\n> \t\thash = HASH_INIT;\n> \t\tdo {\n> \t\t\tunsigned char c;\n> \t\t\tif (size >= sizeof(long)) {\n> \t\t\t\tunsigned long val = get_unaligned_long(name);\n> \t\t\t\tif (!(val & 0x8080808080808080)) {\n> \t\t\t\t\t/* Make it equivalent in case */\n> \t\t\t\t\tval &= ~0x2020202020202020;\n> \t\t\t\t\thash = hash_long(hash, val);\n> \t\t\t\t\tname += sizeof(long);\n> \t\t\t\t\tsize -= sizeof(long);\n> \t\t\t\t\tcontinue;\n> \t\t\t\t}\n> \t\t\t}\n>\n> \t\t\tc = *name;\n> \t\t\tif (!(c & 0x80)) {\n> \t\t\t\thash = hash_long(hash, c & ~0x20);\n> \t\t\t\tname++;\n> \t\t\t\tsize--;\n> \t\t\t\tcontinue;\n> \t\t\t}\n\nIt is better to use 'while' instead of 'if' here, i.e.:\n\n\t\t\twhile (!((c = *name) & 0x80)) {\n\t\t\t\thash = hash_long(hash, c & ~0x20);\n\t\t\t\tname++;\n\t\t\t\tif (!--size)\n\t\t\t\t\treturn hash;\n\t\t\t}\n\n>\n> \t\t\t/* This is the unusual and slowish case */\n> \t\t\thash = hash_utf8_char(hash, c, &name, &size);\n> \t\t} while (size);\n> \t\treturn hassh;\n> \t}\n\n\nDmitry\n"},{"id":"66509","messageId":"alpine.LFD.1.00.0801241106020.2803@woody.linux-foundation.org","threadId":"11707","inReplyTo":"37fcd2780801241045o359c19b3h4e2b0c3cf6786aa@mail.gmail.com","subject":"Re: I'm a total push-over..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-24T19:08:35Z","receivedAt":"2008-01-24T19:08:35Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 24 Jan 2008, Dmitry Potapov wrote:\n> \n> It is better to use 'while' instead of 'if' here, i.e.:\n\nYes, that looks like a good further micro-optimization.\n\n\t\tLinus\n"},{"id":"66540","messageId":"87fxwmv5tf.fsf@jbms.ath.cx","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801230922190.1741@woody.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Jeremy Maitin-Shepard","fromEmail":"jbms@cmu.edu","sentAt":"2008-01-25T05:21:16Z","receivedAt":"2008-01-25T05:21:16Z","isPatch":false,"sender":{"key":"jbms@cmu.edu","avatar":null},"body":"Linus Torvalds wrote:\n[snip]\n> So what you can do (and I'd argue that we do) is to have a hash that can \n> handle almost arbitrary input, but then never corrupt the filename, and \n> always compare exactly by default.\n\nIn general, there may be a large number of comparison function options\nthat git will eventually support, and they will likely not all form a\nsingle chain of increasing \"strictness\".\n\nGiven that the hash values aren't even being stored on disk (and if they\nwere, a simple approach of also storing an identifier for the hash\nfunction to know whether they stored values are still valid could be\nused), having a chain of increasingly \"strict\" comparison functions and\nusing a hash function that corresponds to the least strict one is useful\nfor exactly one reason: giving (possibly several different levels of)\nnon-fatal warnings for various types of duplicates.\n\nBut since multiple hash functions will be needed anyway to support\ndifferent notions of case-insensitivity, if the warning is not enabled,\nthere is no reason to use a case-insensitive hash function with a\nbyte-exact comparison.\n\n-- \nJeremy Maitin-Shepard\n"},{"id":"66542","messageId":"7vejc6761g.fsf@gitster.siamese.dyndns.org","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801221913500.1741@woody.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-25T06:50:19Z","receivedAt":"2008-01-25T06:50:19Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> +static inline size_t estimate_cache_size(size_t ondisk_size, unsigned int entries)\n> +{\n> +\tlong per_entry;\n> +\n> +\tper_entry = sizeof(struct cache_entry) - sizeof(struct ondisk_cache_entry);\n> +\n> +\t/*\n> +\t * Alignment can cause differences. This should be \"alignof\", but \n> +\t * since that's a gcc'ism, just use the size of a pointer.\n> +\t */\n> +\tper_entry += sizeof(void *);\n> +\treturn ondisk_size + entries*per_entry;\n> +}\n> +\n\nI wonder if the issue Dave Miller addressed with\n69ae517541ed5ab7d4fdcd8f82a9b8bd949df347 (fast-import: fix\nunalinged allocation and access) applies here.\n\ncommit 69ae517541ed5ab7d4fdcd8f82a9b8bd949df347\nAuthor: David S. Miller \nDate: Fri Dec 14 20:39:16 2007 -0800\n\n fast-import: fix unalinged allocation and access\n \n The specialized pool allocator fast-import uses aligned objects on the\n size of a pointer, which was not sufficient at least on Sparc. Instead,\n make the alignment for objects of type unitmax_t.\n \n Signed-off-by: David S. Miller \n Signed-off-by: Junio C Hamano \n"},{"id":"66562","messageId":"alpine.LSU.1.00.0801251250120.5731@racer.site","threadId":"11707","inReplyTo":"87fxwmv5tf.fsf@jbms.ath.cx","subject":"Re: I'm a total push-over..","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-01-25T12:51:43Z","receivedAt":"2008-01-25T12:51:43Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 25 Jan 2008, Jeremy Maitin-Shepard wrote:\n\n> But since multiple hash functions will be needed anyway to support \n> different notions of case-insensitivity, if the warning is not enabled, \n> there is no reason to use a case-insensitive hash function with a \n> byte-exact comparison.\n\nNo, only multiple compare functions will be needed. The hash function can \nbe built in such a manner that it guarantees that file names being equal \nwith _any_ of the compare functions fall into the same bucket.\n\nThe upside of such a hash function: less code to maintain.\n\nHth,\nDscho\n"},{"id":"66575","messageId":"alpine.LFD.1.00.0801250811380.14161@hp.linux-foundation.org","threadId":"11707","inReplyTo":"7vejc6761g.fsf@gitster.siamese.dyndns.org","subject":"Re: I'm a total push-over..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-25T16:24:05Z","receivedAt":"2008-01-25T16:24:05Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 24 Jan 2008, Junio C Hamano wrote:\n> \n> I wonder if the issue Dave Miller addressed with\n> 69ae517541ed5ab7d4fdcd8f82a9b8bd949df347 (fast-import: fix\n> unalinged allocation and access) applies here.\n\nGood point, although we actually do things wrong for *another* reason.\n\nWe currently force cache_entry to be 8-byte aligned regardless of what the \nactual \"sizeof(ptr)\" is, so we should assume that alignment:\n\n\t#define cache_entry_size(len) ((offsetof(struct cache_entry,name) + (len) + 8) & ~7)\n\nand if that isn't correct, we'd need to change this #define.\n\nSo right now, the right thing to do is probably to make this alignment \nexplicit:\n\n\t#define CE_ALIGN 8\n\nand then use that both in the \"cache_entry_size()\" _and_ in the \n\"estimate_cache_size()\" calculations to make it obvious what the alignment \nis.\n\nAnd then we could actually make the alignment less on architectures that \ndon't need that much (there may be architectures that need more, but I \ndoubt it: we don't have any large fields in that structure, so the \nstructure alignment really probably does max out at 8 in practice even if \nthe C language theory doesn't give you any such guarantees).\n\nSide note: this is not likely to be a problem in _practice_. The on-disk \nrepresentation is also aligned (also by 8), and while they can be \n*differently* aligned due to the relative alignment of the varying-length \n\"name[]\" field, and that can cause some padding to be needed, in practice \nit will never matter. The on-disk size also contains a header that we \ndon't take into account, so it's already \"over-estimated\" to begin with \nfor the in-memory representation.\n\nSo \"estimate_cache_size()\" really does over-estimate its needs by a \nbiggish amount, which is why it all works regardless, but better safe than \nsorry. \n\n\t\tLinus\n"},{"id":"66580","messageId":"87abmtvkd8.fsf@jbms.ath.cx","threadId":"11707","inReplyTo":"alpine.LSU.1.00.0801251250120.5731@racer.site","subject":"Re: I'm a total push-over..","fromName":"Jeremy Maitin-Shepard","fromEmail":"jbms@cmu.edu","sentAt":"2008-01-25T18:19:15Z","receivedAt":"2008-01-25T18:19:15Z","isPatch":false,"sender":{"key":"jbms@cmu.edu","avatar":null},"body":"Johannes Schindelin writes:\n\n> On Fri, 25 Jan 2008, Jeremy Maitin-Shepard wrote:\n\n>> But since multiple hash functions will be needed anyway to support \n>> different notions of case-insensitivity, if the warning is not enabled, \n>> there is no reason to use a case-insensitive hash function with a \n>> byte-exact comparison.\n\n> No, only multiple compare functions will be needed. The hash function can \n> be built in such a manner that it guarantees that file names being equal \n> with _any_ of the compare functions fall into the same bucket.\n\nIn theory, I agree that this is possible, but in practice it may not be\nreasonable at all. Consider two possible comparison functions:\n\n1. compare file names as strings case-insensitively assuming a latin 1\nencoding\n\n2. compare file names as strings case-insensitively assuming a UTF-8\nencoding\n\nActually writing a hash function such that two strings hash to the same\nvalue if either of these comparison functions says that the strings are\nequal would appear to be rather difficult.\n\n> The upside of such a hash function: less code to maintain.\n\nA simple hash function that doesn't try to do anything regarding\ncase-insensitivity is extremely short and simple and therefore is hardly\na maintenance burden.\n\nAlthough in some cases it is possible to \"share\" a hash function, except\nfor the \"warning\" purpose, actually doing so doesn't make much sense.\nUsing the \"case-insensitive\" hash function when you intend to use an\n\"exact\" comparison function just amounts to using a hash function that\nis unequivocally worse: it is slower, more complicated, and has a higher\ncollision rate.\n\n-- \nJeremy Maitin-Shepard\n"},{"id":"66581","messageId":"alpine.LSU.1.00.0801251822530.23841@racer.site","threadId":"11707","inReplyTo":"87abmtvkd8.fsf@jbms.ath.cx","subject":"Re: I'm a total push-over..","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-01-25T18:24:46Z","receivedAt":"2008-01-25T18:24:46Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 25 Jan 2008, Jeremy Maitin-Shepard wrote:\n\n> Johannes Schindelin writes:\n> \n> > The upside of such a hash function: less code to maintain.\n> \n> A simple hash function that doesn't try to do anything regarding \n> case-insensitivity is extremely short and simple and therefore is hardly \n> a maintenance burden.\n\nYou misunderstand me. If the complicated hash function is the one that is \nless exercised, you _will_ face problems.\n\nOTOH if you _already_ need the \"complicated\" hash function, there is \n_little_ point not to use it, and be consistent between platforms, \n_especially_ since now all people eat the same dog food.\n\nSo I never thought about the simple hash function as being a burden.\n\nHth,\nDscho\n"},{"id":"66586","messageId":"7v63xh7mgt.fsf@gitster.siamese.dyndns.org","threadId":"11707","inReplyTo":"87abmtvkd8.fsf@jbms.ath.cx","subject":"Re: I'm a total push-over..","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-01-25T19:07:46Z","receivedAt":"2008-01-25T19:07:46Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeremy Maitin-Shepard writes:\n\n> In theory, I agree that this is possible, but in practice it may not be\n> reasonable at all. Consider two possible comparison functions:\n>\n> 1. compare file names as strings case-insensitively assuming a latin 1\n> encoding\n>\n> 2. compare file names as strings case-insensitively assuming a UTF-8\n> encoding\n>\n> Actually writing a hash function such that two strings hash to the same\n> value if either of these comparison functions says that the strings are\n> equal would appear to be rather difficult.\n\nOnce you start adding more \"case folding\" supported filesystems\nto the repertoire, such a unified hash function Dscho suggests\nneeds to throw paths that other (N-1) \"case folding\" filesystems\ntreat as distinct but only 1 filesystem treats \"equivalent\" into\nthe same hash bucket. I would say not just difficult but the\nresulting function would have too many collisions to make it\nineffective.\n"},{"id":"66593","messageId":"e51f66da0801251208i3d6a78c2xc6e08c509ed4e35e@mail.gmail.com","threadId":"11707","inReplyTo":"4798B633.8040606@op5.se","subject":"Re: I'm a total push-over..","fromName":"Marko Kreen","fromEmail":"markokr@gmail.com","sentAt":"2008-01-25T20:08:09Z","receivedAt":"2008-01-25T20:08:09Z","isPatch":false,"sender":{"key":"markokr@gmail.com","avatar":null},"body":"On 1/24/08, Andreas Ericsson wrote:\n> Interesting output, but not very surprising. Do you have the code\n> available somewhere?\n\nhttp://pgbouncer.projects.postgresql.org/hashtest/hashtest-2008-01-25.tgz\n\nI cleaned it up a bit. Also fixed a bug - the lookup3 was called\nvia wrapper function so it acually is tiny bit faster than the\nresults show.\n\nYou can consider the code as public domain too. Also remember\nthe was not meant to be published, so it rather hack...\n\n-- \nmarko\n"},{"id":"66595","messageId":"e51f66da0801251252r1950c2d5g12caa5e71b9a37a@mail.gmail.com","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801240839590.2803@woody.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Marko Kreen","fromEmail":"markokr@gmail.com","sentAt":"2008-01-25T20:52:06Z","receivedAt":"2008-01-25T20:52:06Z","isPatch":false,"sender":{"key":"markokr@gmail.com","avatar":null},"body":"On 1/24/08, Linus Torvalds wrote:\n> You can do a perfectly fine 8-bytes-at-a-time hash for almost 100% of all\n> source code projects in UTF-8, without *ever* doing any format changes at\n> all. Admittedly, it's a lot easier if the hash is a pure in-memory one (ie\n> we don't care about byte-order or size of integers or anything like that),\n> but that's the common case for most hashes that aren't used for BTree\n> lookup on disk or something like that.\n>\n> Here, let me show you:\n>\n> unsigned int name_hash(const char *name, int size)\n\nWell, although this is very clever approach, I suggest against it.\nYou'll end up with complex code that gives out substandard results.\n\nI think its better to have separate case-folding function (or several),\nthat copies string to temp buffer and then run proper optimized hash\nfunction on that buffer.\n\nThat way you can use already tested building blocks and can optimize\nboth sides separately. Eg. the folding-only function can aswell be\noptimized to load 4 or 8-byte at-a-time. This also isolates hashing\nfrom exact details how folding happens to access the input string which\nseem to be the weak point in your approach. (In both collision and\ncomplexity sense.)\n\nSuch temp buffer happens to fits my lookup3_memcpy also better (heh).\nIts weak point is that on platforms that do not allow unaligned access,\nit degenerates to byte-by-byte loading. But if know you always\nhave aligned buffer, you can notify gcc to do 4-byte fetch there too.\nIt should be as simple as tagging data pointer as uint32_t *.\n\nAnyway, now you dont need to worry about folding when picking hash.\n\n> Basically, it's almost always a stupid thing to actually normalize a whole\n> string. You do those things character-by-character, and only lazily when\n> you actually need to!\n\nIf your input strings are over kilobyte on average then I'd\nagree with you, but if you process 20-30 bytes on average,\nis the additional complexity worth it?\n\n-- \nmarko\n"},{"id":"66603","messageId":"alpine.LFD.1.00.0801251407010.5056@hp.linux-foundation.org","threadId":"11707","inReplyTo":"e51f66da0801251252r1950c2d5g12caa5e71b9a37a@mail.gmail.com","subject":"Re: I'm a total push-over..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-25T22:16:22Z","receivedAt":"2008-01-25T22:16:22Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 25 Jan 2008, Marko Kreen wrote:\n> \n> Well, although this is very clever approach, I suggest against it.\n> You'll end up with complex code that gives out substandard results.\n\nActually, *your* operation is the one that gives substandard results.\n\n> I think its better to have separate case-folding function (or several),\n> that copies string to temp buffer and then run proper optimized hash\n> function on that buffer.\n\nI'm sorry, but you just cannot do that efficiently and portably.\n\nI can write a hash function that reliably does 8 bytes at a time for the \ncommon case on a 64-bit architecture, exactly because it's easy to do \n\"test high bits in parallel\" with a simple bitwise 'and', and we can do \nthe same with \"approximate lower-to-uppercase 8 bytes at a time\" for a \nhash by just clearing bit 5.\n\nIn contrast, trying to do the same thing in half-way portable C, but being \nlimited to having to get the case-folding *exactly* right (which you need \nfor the comparison function) is much much harder. It's basically \nimpossible in portable C (it's doable with architecture-specific features, \nie vector extensions that have per-byte compares etc).\n\nAnd hashing is performance-critical, much more so than the compares (ie \nyou're likely to have to hash tens of thousands of files, while you will \nonly compare a couple). So it really is worth optimizing for.\n\nAnd the thing is, \"performance\" isn't a secondary feature. It's also not \nsomething you can add later by optimizing. \n\nIt's also a mindset issue. Quite frankly, people who do this by \"convert \nto some folded/normalized form, then do the operation\" will generally make \nmuch more fundamental mistakes. Once you get into the mindset of \"let's \npass a corrupted strign around\", you are in trouble. You start thinking \nthat the corrupted string isn't really \"corrupt\", it's in an \"optimized \nformat\". \n\nAnd it's all downhill from there. Don't do it.\n\n\t\t\tLinus\n"},{"id":"66604","messageId":"alpine.LFD.1.00.0801251417380.5056@hp.linux-foundation.org","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801251407010.5056@hp.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-25T22:35:45Z","receivedAt":"2008-01-25T22:35:45Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 25 Jan 2008, Linus Torvalds wrote:\n> \n> I can write a hash function that reliably does 8 bytes at a time for the \n> common case on a 64-bit architecture, exactly because it's easy to do \n> \"test high bits in parallel\" with a simple bitwise 'and', and we can do \n> the same with \"approximate lower-to-uppercase 8 bytes at a time\" for a \n> hash by just clearing bit 5.\n\nSide note: you *can* get better approximations fairly cheaply if you care.\n\nIf you want to distinguish the characters 0-31 from the characters 31-63 \nin your hash (pointless for filenames, but it can be worthwhile for some \nother string cases), you can decide to clear bit#5 only if bit#6 in that \nbyte was also set, with just a few bitwise operations.\n\nEg, imagine that you have \"unsigned long x\" containing eight bytes of \nascii data (ie you already did the test by 0x8080808080808080), you can do \nthings like\n\n\tunsigned long bit6 = x & 0x4040404040404040;\n\tx &= ~(bit6 >> 1);\n\nwhich will only clear bit5 if bit6 in the same byte was set..\n\nSo you can do tricks like that, and it will still be plenty fast. And \nnobody will ever care that while it collides 'A' with 'a' (by design), it \nalso causes '{' and '[' to be considered \"case collisions\".\n\n[ Amusing side note: '{' and '[' *are* case collisions in legacy 7-bit \n \"Finnish ASCII\". The editor I use still \"upper-cases\" '{' to '['. I'm \n not kidding, and yes, it really does it on purpose!\n\n It used to be that before everybody turned to Latin1, the {|} characters \n were re-used in Finland (and Sweden, for that matter) for the \n extra characters needed in Finnish. Because obviously nobody ever\n needed them for any real work.\n\n I (and probably every Finnish C UNIX programmer) used to be very good at \n reading C source code even when it was full of odd finnish characters \n with dots on top, instead of curly braces! ]\n\nAnd yes, from a performance standpoint, things liek this probably do realy \nmatter. For the kernel tree, the average pathname length is ~28 \ncharacters. If you can do it with three iterations that do the first 24 \ncharacters eight characters at a time, and then four iterations over the \nfour last ones, rather than 28 iterations with byte->longword and \nmultiplications in each, I bet it's quite visible.\n\nOf course, it's going to be visible only if everything else is fast too, \nbut git has been pretty good at that in general.\n\n\t\t\tLinus\n"},{"id":"66636","messageId":"e51f66da0801260416p5f5ffb98w16fe832fe62dc7c9@mail.gmail.com","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801251407010.5056@hp.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Marko Kreen","fromEmail":"markokr@gmail.com","sentAt":"2008-01-26T12:16:29Z","receivedAt":"2008-01-26T12:16:29Z","isPatch":false,"sender":{"key":"markokr@gmail.com","avatar":null},"body":"On 1/26/08, Linus Torvalds wrote:\n> On Fri, 25 Jan 2008, Marko Kreen wrote:\n> > Well, although this is very clever approach, I suggest against it.\n> > You'll end up with complex code that gives out substandard results.\n>\n> Actually, *your* operation is the one that gives substandard results.\n>\n> > I think its better to have separate case-folding function (or several),\n> > that copies string to temp buffer and then run proper optimized hash\n> > function on that buffer.\n>\n> I'm sorry, but you just cannot do that efficiently and portably.\n>\n> I can write a hash function that reliably does 8 bytes at a time for the\n> common case on a 64-bit architecture, exactly because it's easy to do\n> \"test high bits in parallel\" with a simple bitwise 'and', and we can do\n> the same with \"approximate lower-to-uppercase 8 bytes at a time\" for a\n> hash by just clearing bit 5.\n>\n> In contrast, trying to do the same thing in half-way portable C, but being\n> limited to having to get the case-folding *exactly* right (which you need\n> for the comparison function) is much much harder. It's basically\n> impossible in portable C (it's doable with architecture-specific features,\n> ie vector extensions that have per-byte compares etc).\n\nHere you misunderstood me, I was proposing following:\n\nint hash_folded(const char *str, int len)\n{\n char buf[512];\n do_folding(buf, str, len);\n return do_hash(buf, len);\n}\n\nThat is - the folded string should stay internal to hash function.\n\nOnly difference from combined foling+hashing would be that\nyou can code each part separately.\n\n> And hashing is performance-critical, much more so than the compares (ie\n> you're likely to have to hash tens of thousands of files, while you will\n> only compare a couple). So it really is worth optimizing for.\n>\n> And the thing is, \"performance\" isn't a secondary feature. It's also not\n> something you can add later by optimizing.\n>\n> It's also a mindset issue. Quite frankly, people who do this by \"convert\n> to some folded/normalized form, then do the operation\" will generally make\n> much more fundamental mistakes. Once you get into the mindset of \"let's\n> pass a corrupted strign around\", you are in trouble. You start thinking\n> that the corrupted string isn't really \"corrupt\", it's in an \"optimized\n> format\".\n>\n> And it's all downhill from there. Don't do it.\n\nAgaing, you seem to keep HFS+ behaviour in mind, but that was\nnot what I did suggest. Probably my mistake, sorry.\n\n-- \nmarko\n"},{"id":"66638","messageId":"e51f66da0801260437t7c6d4c6ck2d37d36a452de5f0@mail.gmail.com","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801251407010.5056@hp.linux-foundation.org","subject":"Re: I'm a total push-over..","fromName":"Marko Kreen","fromEmail":"markokr@gmail.com","sentAt":"2008-01-26T12:37:50Z","receivedAt":"2008-01-26T12:37:50Z","isPatch":false,"sender":{"key":"markokr@gmail.com","avatar":null},"body":"On 1/26/08, Linus Torvalds wrote:\n> It's also a mindset issue. Quite frankly, people who do this by \"convert\n> to some folded/normalized form, then do the operation\" will generally make\n> much more fundamental mistakes. Once you get into the mindset of \"let's\n> pass a corrupted strign around\", you are in trouble. You start thinking\n> that the corrupted string isn't really \"corrupt\", it's in an \"optimized\n> format\".\n\nOk, you seem to focus on case folding and general performance,\nI focus on hash quality and code complexity. Considering you\nmay want several folding methods, it seemed to me that it would\nbe good to separate the two aspects.\n\nBut I'll try to follow your path for a moment.\n\nHashing 32 or 64 bits at a time is not trivial, eg. you cannot\nuse same algorithm for both cases, 64 bits requires twice the\nwork to mix well.\n\nPer Jenkins notes, hash inner loop should be reversible - that\nmeans that details from beginning of data should shift out of horizon.\nBut final mixing should achieve avalanche - that means each bit in\ninput should affect 50% bits in output.\n\nAlso must be noted that we are mixing 32->32 and 64->64 instead\nof the usual 8->32. So it seems that the best bet would be to use\ninteger hash functions as core. Jenkins himself points to Thomas\nWang (http://www.cris.com/~Ttwang/tech/inthash.htm) who has good\ninteger mix functions for both 32 and 64 bits.\n\nInteger hash function must have both reversibility and avalance,\nso they may be slightly overkill for this purpose, but fixing that\nmeans lot of work.\n\nSo here is what I propose for hashing, if you really want to have\ncombined folding + hashing:\n\n/* Thomas Wang integer hash functions */\n\nstatic inline uint32_t hash32(uint32_t key)\n{\n key = ~key + (key << 15);\n key = key ^ (key >> 12);\n key = key + (key << 2);\n key = key ^ (key >> 4);\n key = key * 2057;\n key = key ^ (key >> 16);\n return key;\n}\n\nstatic inline uint64_t hash64(uint64_t key)\n{\n key = (~key) + (key << 21); // key = (key << 21) - key - 1;\n key = key ^ (key >> 24);\n key = (key + (key << 3)) + (key << 8); // key * 265\n key = key ^ (key >> 14);\n key = (key + (key << 2)) + (key << 4); // key * 21\n key = key ^ (key >> 28);\n key = key + (key << 31);\n return key;\n}\n\n/*\n * Simple addition should be enough for new values,\n * considering the mix functions does work well.\n */\n\n/* this is functon to use in git */\nstatic inline unsigned long hash_long(unsigned long hash, unsigned long val)\n{\n if (sizeof(long) == 8)\n return hash64(hash + val);\n else\n return hash32(hash + val);\n}\n\n/* below is regular hash for testing */\n\nstatic uint32_t inline hash_int32(uint32_t hash, uint32_t val)\n{\n return hash32(hash + val);\n}\n\nstatic uint64_t inline hash_int64(uint64_t hash, uint64_t val)\n{\n return hash64(hash + val);\n}\n\n/* hack to avoid call to libc memcpy() */\nstatic inline void simple_memcpy(void *_dst, const void *_src, unsigned len)\n{\n const uint8_t *src = _src;\n uint8_t *dst = _dst;\n while (len--)\n *dst++ = *src++;\n}\n\nuint32_t int32_hash(const void *_data, unsigned int size)\n{\n const uint8_t *src = _data;\n /* inital value. +size avoids \\0 and \\0\\0 hashing same */\n uint32_t hash = 1234567890 + size;\n uint32_t val;\n while (size >= 4) {\n memcpy(&val, src, 4); /* direct load on x86/64 */\n src += 4;\n size -= 4;\n hash = hash_int32(hash, val);\n }\n if (size > 0) {\n val = 0;\n simple_memcpy(&val, src, size);\n hash = hash_int32(hash, val);\n }\n return hash;\n}\n\nuint32_t int64_hash(const void *_data, unsigned int size)\n{\n const uint8_t *src = _data;\n uint64_t hash = 12345678901234567890ULL + size;\n uint64_t val;\n while (size >= 8) {\n memcpy(&val, src, 8); /* direct load on x86/64 */\n hash = hash_int64(hash, val);\n src += 8;\n size -= 8;\n }\n if (size > 0) {\n val = 0;\n simple_memcpy(&val, src, size);\n hash = hash_int64(hash, val);\n }\n /* here we go to 32 bits, simple masking is enough */\n return hash;\n}\n\n\nIn the \"regular\" hash functions I again use the memcpy() trick, because\nI don't want to bother with access optimizations. Especially considering\nthat part is unnecessary for git.\n\n\nIntel Core Duo (32bit). String length 0 .. 40, random alignment:\n-------------------------------------------------------------------\n\n\nTesting: seed=34 align=0 minlen=0 maxlen=40 trycnt=3 duration=10\n\nlookup3 : #0 .. 165.489 #1 .. 165.494 #2 .. 165.490 MB/s\nint32_hash : #0 .. 148.359 #1 .. 148.350 #2 .. 148.435 MB/s\nint64_hash : #0 .. 123.105 #1 .. 123.040 #2 .. 123.039 MB/s\nlookup3_memcpy_hack : #0 .. 169.791 #1 .. 169.795 #2 .. 169.749 MB/s\noat : #0 .. 134.737 #1 .. 134.702 #2 .. 134.735 MB/s\nfnv : #0 .. 131.457 #1 .. 131.470 #2 .. 131.474 MB/s\nhsieh : #0 .. 166.619 #1 .. 166.622 #2 .. 166.588 MB/s\n\nResults compared to reference:\n\nlookup3 : 100.000 %\nint32_hash : 89.661 %\nint64_hash : 74.361 %\nlookup3_memcpy_hack : 102.591 %\noat : 81.409 %\nfnv : 79.441 %\nhsieh : 100.676 %\n\n\nAMD Opteron(tm) Processor 252 (64bit) 2.6GHz\n-------------------------------------------------\n\nTesting: seed=34 align=0 minlen=0 maxlen=40 trycnt=3 duration=10\n\nlookup3 : #0 .. 208.819 #1 .. 208.877 #2 .. 208.897 MB/s\nint32_hash : #0 .. 181.096 #1 .. 181.100 #2 .. 181.097 MB/s\nint64_hash : #0 .. 196.823 #1 .. 196.761 #2 .. 196.825 MB/s\nlookup3_memcpy_hack : #0 .. 201.593 #1 .. 201.597 #2 .. 201.594 MB/s\noat : #0 .. 160.769 #1 .. 160.774 #2 .. 160.772 MB/s\nfnv : #0 .. 200.046 #1 .. 200.044 #2 .. 200.046 MB/s\nhsieh : #0 .. 205.515 #1 .. 205.520 #2 .. 205.517 MB/s\n\nResults compared to reference:\n\nlookup3 : 100.000 %\nint32_hash : 86.706 %\nint64_hash : 94.225 %\nlookup3_memcpy_hack : 96.519 %\noat : 76.974 %\nfnv : 95.778 %\nhsieh : 98.398 %\n\n\nSo speedwise the result is not bad. Especially considering unoptimized\ndata fetching. On larger data (~1k) is tends to lose to lookup3 more,\nI guess lookup3 parallelizes better (3x 32bit int vs. 1x 32/64 int).\n\nThe functions pass Jenkins lookup3 selftest that eg. FNV does not.\n\nThe code is also available at:\n\n http://pgbouncer.projects.postgresql.org/hashtest/hashtest-2008-01-26.tgz\n\n\n-- \nmarko\n"},{"id":"66664","messageId":"alpine.LFD.1.00.0801262247140.3222@www.l.google.com","threadId":"11707","inReplyTo":"e51f66da0801260416p5f5ffb98w16fe832fe62dc7c9@mail.gmail.com","subject":"Re: I'm a total push-over..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-01-27T06:51:18Z","receivedAt":"2008-01-27T06:51:18Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 26 Jan 2008, Marko Kreen wrote:\n> \n> Here you misunderstood me, I was proposing following:\n> \n> int hash_folded(const char *str, int len)\n> {\n> char buf[512];\n> do_folding(buf, str, len);\n> return do_hash(buf, len);\n> }\n> \n> That is - the folded string should stay internal to hash function.\n\nIf it's internal, it's much better, but you still missed the performance \nangle.\n\nThe fact is, hashing can take shortcuts that folding cannot do!\n\nCase folding, by definition, has to be \"exact\" (since the whole point is \nwhat you're going to use the same folding function to do the compare, so \nif you play games with folding, the compares will be wrong).\n\nBut hashing doesn't have to be exact. It's ok to hash '{' and '[' as if \nthey were different cases of the same character, if that gives you a \nfaster hash function. Especially as those charactes are rather rare in \nfilenames.\n\nSo if you do hashing as a function of its own, you can simply do a better \njob at it.\n\nI do agree that the functions that create a folded set of characters from \na _complex_ UTF-8 character should be shared between folding and hashing, \nsince that code is too complex and there are no simple shortcuts for doing \na faster hash that still retains all the properties we want. \n\n\t\t\tLinus\n"},{"id":"66667","messageId":"20080127082128.GH26664@dpotapov.dyndns.org","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801262247140.3222@www.l.google.com","subject":"Re: I'm a total push-over..","fromName":"Dmitry Potapov","fromEmail":"dpotapov@gmail.com","sentAt":"2008-01-27T08:21:28Z","receivedAt":"2008-01-27T08:21:28Z","isPatch":false,"sender":{"key":"dpotapov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6568595?v=4"},"body":"On Sat, Jan 26, 2008 at 10:51:18PM -0800, Linus Torvalds wrote:\n> \n> \n> On Sat, 26 Jan 2008, Marko Kreen wrote:\n> > \n> > Here you misunderstood me, I was proposing following:\n> > \n> > int hash_folded(const char *str, int len)\n> > {\n> > char buf[512];\n> > do_folding(buf, str, len);\n> > return do_hash(buf, len);\n> > }\n> > \n> > That is - the folded string should stay internal to hash function.\n> \n> If it's internal, it's much better, but you still missed the performance \n> angle.\n> \n> The fact is, hashing can take shortcuts that folding cannot do!\n> \n> Case folding, by definition, has to be \"exact\" (since the whole point is \n> what you're going to use the same folding function to do the compare, so \n> if you play games with folding, the compares will be wrong).\n\nLet's rename do_folding as something else, because it is not a real\nfolding, but a preparation step for hash calculation. Keeping these\nsteps separately simplifies the code, and allows further optimization,\nfor instance, you do not need this do_folding step on a case-sensitive\nfilesystem. Though it is certainly possible to mix both steps together,\nit bloats the code and makes it less readable. Of course, the idea to\navoid a temporary buffer and do everything at once is very appealing,\nso I gave it a try -- and here is a 32-bit version of name_hash(), but\nI am not very happy with the result:\n\n\n#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))\n\n#define mix(a,b,c) \\\n{ \\\n\ta -= c; a ^= rot(c, 4); c += b; \\\n\tb -= a; b ^= rot(a, 6); a += c; \\\n\tc -= b; c ^= rot(b, 8); b += a; \\\n\ta -= c; a ^= rot(c,16); c += b; \\\n\tb -= a; b ^= rot(a,19); a += c; \\\n\tc -= b; c ^= rot(b, 4); b += a; \\\n}\n#define final(a,b,c) \\\n{ \\\n\tc ^= b; c -= rot(b,14); \\\n\ta ^= c; a -= rot(c,11); \\\n\tb ^= a; b -= rot(a,25); \\\n\tc ^= b; c -= rot(b,16); \\\n\ta ^= c; a -= rot(c,4); \\\n\tb ^= a; b -= rot(a,14); \\\n\tc ^= b; c -= rot(b,24); \\\n}\n\n#define hash_value(x) \\\n\ths[hp] += (x); \\\n\tif (++hp == 3) { \\\n\t\tmix (hs[0], hs[1], hs[2]); \\\n\t\thp = 0; \\\n\t}\nunsigned int name_hash(const char *name, unsigned size)\n{\n\tunsigned hp = 0;\n\tunsigned hs[3];\n\ths[0] = hs[1] = hs[2] = 0xdeadbeef + size;\n\n\tdo {\n\t\tunsigned char c;\n\t\tif (size >= sizeof(unsigned)) {\n\t\t\tunsigned val = get_unaligned_uint(name);\n\t\t\tif (!(val & 0x80808080)) {\n\t\t\t\tval &= ~0x20202020;\n\t\t\t\thash_value(val);\n\t\t\t\tname += sizeof(val);\n\t\t\t\tsize -= sizeof(val);\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t}\n\n\t\twhile (!((c = *name) & 0x80)) {\n\t\t\thash_value(c & ~0x20);\n\t\t\tname++;\n\t\t\tif (!--size)\n\t\t\t\tgoto done:\n\t\t}\n\n\t\tdo {\n\t\t\t// TODO: add denormalization for Mac\n\t\t\tunsigned val = towupper (utf8_to_wchar(&name, &size));\n\t\t\thash_value(val);\n\t\t} while (size && (*name & 0x80));\n\n\t} while (size);\ndone:\n\tif (hp)\n\t\tfinal(a,b,c);\n\treturn hs[2];\n}\n\n\nDmitry\n"},{"id":"66669","messageId":"e51f66da0801270145w41a94414g7bebd4a31293344d@mail.gmail.com","threadId":"11707","inReplyTo":"alpine.LFD.1.00.0801262247140.3222@www.l.google.com","subject":"Re: I'm a total push-over..","fromName":"Marko Kreen","fromEmail":"markokr@gmail.com","sentAt":"2008-01-27T09:45:25Z","receivedAt":"2008-01-27T09:45:25Z","isPatch":false,"sender":{"key":"markokr@gmail.com","avatar":null},"body":"On 1/27/08, Linus Torvalds wrote:\n> On Sat, 26 Jan 2008, Marko Kreen wrote:\n> >\n> > Here you misunderstood me, I was proposing following:\n> >\n> > int hash_folded(const char *str, int len)\n> > {\n> > char buf[512];\n> > do_folding(buf, str, len);\n> > return do_hash(buf, len);\n> > }\n> >\n> > That is - the folded string should stay internal to hash function.\n>\n> If it's internal, it's much better, but you still missed the performance\n> angle.\n>\n> The fact is, hashing can take shortcuts that folding cannot do!\n>\n> Case folding, by definition, has to be \"exact\" (since the whole point is\n> what you're going to use the same folding function to do the compare, so\n> if you play games with folding, the compares will be wrong).\n>\n> But hashing doesn't have to be exact. It's ok to hash '{' and '[' as if\n> they were different cases of the same character, if that gives you a\n> faster hash function. Especially as those charactes are rather rare in\n> filenames.\n>\n> So if you do hashing as a function of its own, you can simply do a better\n> job at it.\n>\n> I do agree that the functions that create a folded set of characters from\n> a _complex_ UTF-8 character should be shared between folding and hashing,\n> since that code is too complex and there are no simple shortcuts for doing\n> a faster hash that still retains all the properties we want.\n\nWell, you can always have fold_quick_and_dirty() function that\nis used only internally in hash_folded() function, which can:\n\n- fold with simple |= 0x20202020..\n- write out full uint32/64, no need to make result proper string\n- zero-fill at the end, so hash function does not need to check\n for partial block, which is pretty expensive part of hashing.\n\nThe win would be:\n- more modularized code\n- can use faster/any hash\n- hash function can be certain to work on aligned data\n (win on non-x86)\n\nThe minus:\n- some memory i/o overhead which may or may not matter\n- the parts would not be fully generic, but special to hashing\n\n\n-- \nmarko\n\n\nPS. Typo in last mail - \"inner loop should be reversible - that\nmeans that details from beginning of data should shift out of\nhorizon.\" That obviously means \"data should _not_ shift\nout of horizon.\n\nbtw, \"reversible\" for integer hashes means that there is 1:1\nmapping between input and output - no collisions. Thus\nno info loss.\n"},{"id":"66673","messageId":"alpine.LSU.1.00.0801271406130.23907@racer.site","threadId":"11707","inReplyTo":"20080127082128.GH26664@dpotapov.dyndns.org","subject":"Re: I'm a total push-over..","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-01-27T14:07:25Z","receivedAt":"2008-01-27T14:07:25Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 27 Jan 2008, Dmitry Potapov wrote:\n\n> #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))\n> \n> #define mix(a,b,c) \\\n> { \\\n> \ta -= c; a ^= rot(c, 4); c += b; \\\n> \tb -= a; b ^= rot(a, 6); a += c; \\\n> \tc -= b; c ^= rot(b, 8); b += a; \\\n> \ta -= c; a ^= rot(c,16); c += b; \\\n> \tb -= a; b ^= rot(a,19); a += c; \\\n> \tc -= b; c ^= rot(b, 4); b += a; \\\n> }\n> #define final(a,b,c) \\\n> { \\\n> \tc ^= b; c -= rot(b,14); \\\n> \ta ^= c; a -= rot(c,11); \\\n> \tb ^= a; b -= rot(a,25); \\\n> \tc ^= b; c -= rot(b,16); \\\n> \ta ^= c; a -= rot(c,4); \\\n> \tb ^= a; b -= rot(a,14); \\\n> \tc ^= b; c -= rot(b,24); \\\n> }\n> \n> #define hash_value(x) \\\n> \ths[hp] += (x); \\\n> \tif (++hp == 3) { \\\n> \t\tmix (hs[0], hs[1], hs[2]); \\\n> \t\thp = 0; \\\n> \t}\n> unsigned int name_hash(const char *name, unsigned size)\n> {\n> \tunsigned hp = 0;\n> \tunsigned hs[3];\n> \ths[0] = hs[1] = hs[2] = 0xdeadbeef + size;\n> \n> \tdo {\n> \t\tunsigned char c;\n> \t\tif (size >= sizeof(unsigned)) {\n> \t\t\tunsigned val = get_unaligned_uint(name);\n> \t\t\tif (!(val & 0x80808080)) {\n> \t\t\t\tval &= ~0x20202020;\n> \t\t\t\thash_value(val);\n> \t\t\t\tname += sizeof(val);\n> \t\t\t\tsize -= sizeof(val);\n> \t\t\t\tcontinue;\n> \t\t\t}\n> \t\t}\n> \n> \t\twhile (!((c = *name) & 0x80)) {\n> \t\t\thash_value(c & ~0x20);\n> \t\t\tname++;\n> \t\t\tif (!--size)\n> \t\t\t\tgoto done:\n> \t\t}\n> \n> \t\tdo {\n> \t\t\t// TODO: add denormalization for Mac\n> \t\t\tunsigned val = towupper (utf8_to_wchar(&name, &size));\n> \t\t\thash_value(val);\n> \t\t} while (size && (*name & 0x80));\n> \n> \t} while (size);\n> done:\n> \tif (hp)\n> \t\tfinal(a,b,c);\n> \treturn hs[2];\n> }\n\nOh yes, let's take this one, it is so much shorter, cleaner and \noverall more elegant than Linus' code.\n\nCiao,\nDscho\n"},{"id":"66675","messageId":"20080127144850.GJ26664@dpotapov.dyndns.org","threadId":"11707","inReplyTo":"alpine.LSU.1.00.0801271406130.23907@racer.site","subject":"Re: I'm a total push-over..","fromName":"Dmitry Potapov","fromEmail":"dpotapov@gmail.com","sentAt":"2008-01-27T14:48:50Z","receivedAt":"2008-01-27T14:48:50Z","isPatch":false,"sender":{"key":"dpotapov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6568595?v=4"},"body":"Hi,\n\nOn Sun, Jan 27, 2008 at 02:07:25PM +0000, Johannes Schindelin wrote:\n> \n> \n> Oh yes, let's take this one, it is so much shorter, cleaner and \n> overall more elegant than Linus' code.\n\nI am not sure what you meant by that, and what exactly code you meant\nsaying Linus' code....\n\nAnyway, my point was that mixing both steps together does not look very\nnice, and the code was intended to demonstrate why.\n\nDmitry\n"},{"id":"66677","messageId":"20080127150602.GK26664@dpotapov.dyndns.org","threadId":"11707","inReplyTo":"e51f66da0801270145w41a94414g7bebd4a31293344d@mail.gmail.com","subject":"Re: I'm a total push-over..","fromName":"Dmitry Potapov","fromEmail":"dpotapov@gmail.com","sentAt":"2008-01-27T15:06:02Z","receivedAt":"2008-01-27T15:06:02Z","isPatch":false,"sender":{"key":"dpotapov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6568595?v=4"},"body":"On Sun, Jan 27, 2008 at 11:45:25AM +0200, Marko Kreen wrote:\n\n> The minus:\n> - some memory i/o overhead which may or may not matter\n\nIf a string is short, it will probably reside in the processor cache, so\nthere is no real memory i/o overhead here. For more longer strings, it\nmay be better to do that in short chunks, so each chunk can reside in\nthe cache. But I don't think filenames are long, so it is not an issue\nhere.\n\n> - the parts would not be fully generic, but special to hashing\n\nI think the second part can be rather generic to be reused for hashing\nsomething else that does not require filename specific case-folding.\n\nDmitry\n"}]}