{"thread":{"id":"28087","subject":"Re: [PATCH 07/11] object: try naive cuckoo hashing","startedAt":"2011-08-13T10:22:44Z","lastAt":"2011-08-13T19:12:06Z","messageCount":2,"participants":["George Spelvin"],"isPatch":true,"patchVersion":1,"patchTotal":11},"messages":[{"id":"173444","messageId":"20110813102244.9033.qmail@science.horizon.com","threadId":"28087","inReplyTo":null,"subject":"Re: [PATCH 07/11] object: try naive cuckoo hashing","fromName":"George Spelvin","fromEmail":"linux@horizon.com","sentAt":"2011-08-13T10:22:44Z","receivedAt":"2011-08-13T10:22:44Z","isPatch":true,"sender":{"key":"linux@horizon.com","avatar":null},"body":"I had vague memories of hearing about cuckoo hashing in the pasr, but\nyour posting inspired me to read up on it.\n\nYour implementation doesn't quite match the standard one.  Did you get\nit from somewhere, or is it your own creation?\n\nIn the classical design, the H1 and H2 hashes use two separate hash\ntables (T1 and T2), so there is never any question about where insertion\nshould happen.\n\nIt's\n- New items are inserted into T1 (at H1).\n- If the slot is full, the new item is still stored there, but\n  it is bumped to T2.\n- If that T2 slot is full, it is still overwritten, but what was there\n  is bumped back to T1.\n\netc., until a NULL pointer is found or \n\nYou use a single hash table.  Is that variant analyzed somewhere, or is\nit something you've found is better?\n\nIt seems that what your insert_obj_hash does is \"if the H1 slot is open,\nstore there.  Otherwise, store in the H2 slot and bump the item already\nthere (if any).\"  What this means is that as soon as you hit an object\nalready in its H2 slot, the insert will fall into an infinite loop and\neventually fail.\n\nThe original scheme could bump items out of H2 slots back to H1 slots.\n\nAnother advantage of the 2-table system is that every object hash two\npossible homes, even if H1 == H2.  With one table, the hash functions\nare twice as big, so the chance of that happening is cut in half, but\nsuch objects have only one possible home and really gum up the works.\n\n(You could define H2 = H1 + obj->sha1[1] % (obj_hash_size-1) to\nsolve this, using the standard shift-and-add optimizations for\ncomputing modulo a power of two less one, but I'm still not sure\nif it's worth it.)\n\n\nAnother technique for using a hash table at a high load factor is\nmultiple-entry buckets.  This is discussed in \"A cool and practical\nalternative to traditional hash tables\"\nhttp://www.ru.is/faculty/ulfar/CuckooHash.pdf\n\nBecause a bucket is a single cache line, accessing it adds no more\noverhead than a single-entry bicket, *as long as you can validate the\nlookup without following a pointer*.\n\nThe best way to do that is to store some additional validation data\n(fortunately, SHA-1 provides lots; even if you're using all 5 words,\ntheir sum is available) in the hash table itself.  This does make the\ntable larger, but speeds up lookups.\n\nOne way to speed up pointer-bumping in the 2-hash case would be to\nstore H1+H2 (the full 32-bit sum) as a validation value.  In addition to\nallowing you to avoid following the pointer on misses the vast majority\nof the time, this also lets you bump pointers from H1 to H2 without\nactually following them.  You know one of the hashes (because you found\nthe pointer in that table slot), and a subtraction produces the other.\n\nThis produces insert code like the following:\n\nstruct obj_hash_entry {\n\tstruct object *obj;\n\tuint32_t hash_sum;\n} *obj_hash;\n\nstatic struct object *insert_obj_hash(struct object *obj)\n{\n\tuint32_t hash_sum = hash_val(obj->sha1);\n\tunsigned ix = hash_sum & (obj_hash_size - 1);\n\tunsigned n = 0, lim = 1;\n\tunsigned loop_check;\t/* Ignore GCC warning */\n\n\thash_sum += hash_val(obj->sha1 + 4)\n\n\tdo {\n\t\tstruct object *tmp_obj = obj_hash[ix].obj;\n\t\tuint32_t tmp_hash_sum = obj_hash[ix].hash_sum;\n\n\t\tobj_hash[ix].obj = obj;\n\t\tobj_hash[ix].hash_sum = hash_sum;\n\n\t\t/* Brent's cycle-finding algorithm */\n\t\tif (++n == lim) {\t/* Less registers: if (n & (n-1)) == 0 */\n\t\t\tloop_check = ix;\n\t\t\tlim *= 2;\n\t\t}\n\t\t\n\t\tobj = tmp_obj;\n\t\thash_sum = tmp_hash_sum;\n\t\tix = (tmp_hash_sum - ix) & (obj_hash_size - 1);\n\n\t} while (obj && ix != loop_check);\n\n\treturn obj;\n}\n\nI presume the optimization to lookup_object is obvious.\n"},{"id":"173460","messageId":"20110813191206.25129.qmail@science.horizon.com","threadId":"28087","inReplyTo":"20110813102244.9033.qmail@science.horizon.com","subject":"Re: [PATCH 07/11] object: try naive cuckoo hashing","fromName":"George Spelvin","fromEmail":"linux@horizon.com","sentAt":"2011-08-13T19:12:06Z","receivedAt":"2011-08-13T19:12:06Z","isPatch":true,"sender":{"key":"linux@horizon.com","avatar":null},"body":"I've been doing a lot of reading on Cuckoo hashing.\n\nYes, the single-table variant is described and used.  However, the\ninsertion procedure is not the way you do it.\n\nAlso, d-ary Cuckoo hashing (also called d-Cuckoo hashing) where you use\nmore than 2 hash functions is also used.\n\nThe insertion algorithm, however, is not really agreed on.\n\nOne algorithm (mostly proposed for hardware) uses d separate tables.\nEvery entry displaced from table i is displaced to table i+1 (mod d).\nhttp://infoscience.epfl.ch/record/164147/files/cuckoo_dir_hpca2011_camera_ready.pdf\n\nIn the single-table case, and in general, however, a displaced entry\nhas more than one possible new location.  This leads to the question of how\nto choose.\n\nOne proposal is to do a breadth-first search looking for a path to\na free slot.  It's provable that this will succeed with high probability\nbefore the exponential growth of the breadth of the search tree\ngets too bad.\nSee \"Space Efficient Hash Tables with Worst Case Constant Access Time\"\nhttp://www.itu.dk/people/pagh/papers/d-cuckoo-jour.pdf\n\nAnother suggested tehcnique is to just pick an alternative at random\nand proceed.  This is recommended in e.g.\n\"Efficient Hash Probes on Modern Processors\"\nhttp://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.1189&rep=rep1&type=pdf\n\nBoth of these lead to rather complex implementations.  The random number\ngenerator is probably simpler than the breadth-first search, but either way\nthere's a bunch of auxiliary code.\n\nSticking with two hash functions, but using multi-entry buckets is\ndefinitely an attractive possibility.\n"}]}