{"id":5650,"date":"2019-06-09T13:00:01","date_gmt":"2019-06-09T13:00:01","guid":{"rendered":"http:\/\/writeasync.net\/?p=5650"},"modified":"2019-06-08T15:49:08","modified_gmt":"2019-06-08T15:49:08","slug":"an-even-faster-hash-table","status":"publish","type":"post","link":"http:\/\/writeasync.net\/?p=5650","title":{"rendered":"An even faster hash table"},"content":{"rendered":"

Last week, in my continuing exploration of a C++ Letter Boxed solver<\/a>, I had to build a faster hash table<\/a> to improve performance. Today we’ll make it even faster, hoping to catch up to the performance of my .NET Core solver app<\/a>.<\/p>\n

Before making the code changes, I first needed to fix the benchmark code<\/a>. The find operations were not really working the way they should have been. (Luckily the numbers didn’t change all that much.)<\/p>\n

Now, let’s start optimizing! First, note that Hashtable<\/code> has a single vector for its buckets. Each entry looks like this:<\/p>\n

\r\nstruct Entry\r\n{\r\n    TKey key_;\r\n    TValue value_;\r\n    bool occupied_;\r\n};\r\n<\/pre>\n
This means that every time we resize the table, we have to reallocate and copy these keys and values again. Perhaps we can get a performance edge by using two vectors — one for buckets, which would just be a list of int<\/code>s, and another for the entries which would never need to change other than appending totally new key-value pairs. The number in each bucket would refer to the index of the entry stored there.<\/p>\n
Since a vector zero-fills by default<\/a>, we should take advantage of that fact by treating a bucket value of zero as empty. Then we just need to be careful to one-index<\/a> the entry list by setting its initial size to one.<\/p>\n
Unfortunately, this approach forces us into a near total rewrite of the Hashtable<\/code> class. But no matter — we have precious CPU cycles at stake! After a lot more logic errors than I care to admit, I was able to come up with these changes: Hashtable.h diff<\/a>. Overall, I think this actually looks simpler, even if some of the loop patterns are duplicated. Where possible, I extracted helper functions to avoid literal copy\/paste code. Also note that we do not need to keep track of any additional bookkeeping information about occupied buckets, so now the Entry is just a typedef<\/code>:<\/p>\n
\r\ntypedef std::pair<TKey, TValue> Entry;\r\n<\/pre>\n
Given the structure of this new code, we can even explore a new collision scheme. Recall that we are using linear probing, where we try successive buckets B, B + 1, B + 2, B + 3, etc. In practice, quadratic probing<\/a> can be much faster than linear probing (with a few caveats about load factor being 0.5 or less). An example quadratic probing scheme would use buckets B, B + 1, B + 4, B + 9, etc. Using the fact that each perfect square is the sum of consecutive odd numbers (11<\/sup> = 1, 22<\/sup> = 1 + 3, 32<\/sup> = 1 + 3 + 5, and so on), we can implement it as follows:<\/p>\n
\r\nvoid next_index(int& index, int c) const\r\n{\r\n    index += 1 + (2 * c);\r\n    int n = static_cast<int>(buckets_.size());\r\n    if (index >= n)\r\n    {\r\n        index = index % n;\r\n    }\r\n}\r\n<\/pre>\n
In this case, c<\/code> represents the (zero-based) collision count: commit<\/a>.<\/p>\n
So now we have implementation A (original), implementation B (use separate buckets and entries vectors), and implementation C (B with quadratic probing). Did any of this make a difference? Let’s run the benchmark again:<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Operation<\/th>\nn<\/th>\nf<\/th>\nTime A<\/th>\nTime B<\/th>\nTime C<\/th>\n<\/tr>\n
FindMissing<\/td>\n10<\/td>\n0.25<\/td>\n0.137<\/td>\n0.134<\/td>\n0.143<\/td>\n<\/tr>\n
FindPresent<\/td>\n10<\/td>\n0.25<\/td>\n0.132<\/td>\n0.13<\/td>\n0.156<\/td>\n<\/tr>\n
Insert<\/td>\n10<\/td>\n0.25<\/td>\n0.869<\/td>\n1.29<\/td>\n1.315<\/td>\n<\/tr>\n
FindMissing<\/td>\n100<\/td>\n0.25<\/td>\n1.305<\/td>\n1.315<\/td>\n1.313<\/td>\n<\/tr>\n
FindPresent<\/td>\n100<\/td>\n0.25<\/td>\n1.29<\/td>\n1.267<\/td>\n1.248<\/td>\n<\/tr>\n
Insert<\/td>\n100<\/td>\n0.25<\/td>\n16.809<\/td>\n9.726<\/td>\n9.677<\/td>\n<\/tr>\n
FindMissing<\/td>\n1000<\/td>\n0.25<\/td>\n13.147<\/td>\n12.983<\/td>\n13.071<\/td>\n<\/tr>\n
FindPresent<\/td>\n1000<\/td>\n0.25<\/td>\n12.858<\/td>\n12.699<\/td>\n12.39<\/td>\n<\/tr>\n
Insert<\/td>\n1000<\/td>\n0.25<\/td>\n155.848<\/td>\n126.977<\/td>\n127.08<\/td>\n<\/tr>\n
FindMissing<\/td>\n10000<\/td>\n0.25<\/td>\n202.026<\/td>\n129.621<\/td>\n131.877<\/td>\n<\/tr>\n
FindPresent<\/td>\n10000<\/td>\n0.25<\/td>\n128.109<\/td>\n128.009<\/td>\n124.676<\/td>\n<\/tr>\n
Insert<\/td>\n10000<\/td>\n0.25<\/td>\n4560.988<\/td>\n1433.636<\/td>\n1519.233<\/td>\n<\/tr>\n
FindMissing<\/td>\n100000<\/td>\n0.25<\/td>\n1326.763<\/td>\n1299.435<\/td>\n1314.786<\/td>\n<\/tr>\n
FindPresent<\/td>\n100000<\/td>\n0.25<\/td>\n1300.205<\/td>\n1273.827<\/td>\n1248.835<\/td>\n<\/tr>\n
Insert<\/td>\n100000<\/td>\n0.25<\/td>\n30199.97<\/td>\n15307.192<\/td>\n15920.22<\/td>\n<\/tr>\n
FindMissing<\/td>\n10<\/td>\n0.5<\/td>\n0.137<\/td>\n0.134<\/td>\n0.137<\/td>\n<\/tr>\n
FindPresent<\/td>\n10<\/td>\n0.5<\/td>\n0.132<\/td>\n0.131<\/td>\n0.13<\/td>\n<\/tr>\n
Insert<\/td>\n10<\/td>\n0.5<\/td>\n1.211<\/td>\n1.469<\/td>\n1.469<\/td>\n<\/tr>\n
FindMissing<\/td>\n100<\/td>\n0.5<\/td>\n1.302<\/td>\n1.301<\/td>\n1.306<\/td>\n<\/tr>\n
FindPresent<\/td>\n100<\/td>\n0.5<\/td>\n1.286<\/td>\n1.267<\/td>\n1.252<\/td>\n<\/tr>\n
Insert<\/td>\n100<\/td>\n0.5<\/td>\n10.765<\/td>\n10.147<\/td>\n10.127<\/td>\n<\/tr>\n
FindMissing<\/td>\n1000<\/td>\n0.5<\/td>\n13.053<\/td>\n13.091<\/td>\n13.171<\/td>\n<\/tr>\n
FindPresent<\/td>\n1000<\/td>\n0.5<\/td>\n13.114<\/td>\n12.752<\/td>\n12.976<\/td>\n<\/tr>\n
Insert<\/td>\n1000<\/td>\n0.5<\/td>\n94.139<\/td>\n86.497<\/td>\n87.787<\/td>\n<\/tr>\n
FindMissing<\/td>\n10000<\/td>\n0.5<\/td>\n131.463<\/td>\n131.698<\/td>\n131.291<\/td>\n<\/tr>\n
FindPresent<\/td>\n10000<\/td>\n0.5<\/td>\n127.911<\/td>\n127.799<\/td>\n124.366<\/td>\n<\/tr>\n
Insert<\/td>\n10000<\/td>\n0.5<\/td>\n2145.042<\/td>\n1308.991<\/td>\n1290.921<\/td>\n<\/tr>\n
FindMissing<\/td>\n100000<\/td>\n0.5<\/td>\n1295.371<\/td>\n1297.845<\/td>\n1301.38<\/td>\n<\/tr>\n
FindPresent<\/td>\n100000<\/td>\n0.5<\/td>\n1259.002<\/td>\n1268.924<\/td>\n1249.057<\/td>\n<\/tr>\n
Insert<\/td>\n100000<\/td>\n0.5<\/td>\n26632.592<\/td>\n17775.16<\/td>\n17773.18<\/td>\n<\/tr>\n
FindMissing<\/td>\n10<\/td>\n0.75<\/td>\n0.137<\/td>\n0.143<\/td>\n0.137<\/td>\n<\/tr>\n
FindPresent<\/td>\n10<\/td>\n0.75<\/td>\n0.132<\/td>\n0.13<\/td>\n0.129<\/td>\n<\/tr>\n
Insert<\/td>\n10<\/td>\n0.75<\/td>\n1.116<\/td>\n1.554<\/td>\n1.572<\/td>\n<\/tr>\n
FindMissing<\/td>\n100<\/td>\n0.75<\/td>\n1.292<\/td>\n1.306<\/td>\n1.316<\/td>\n<\/tr>\n
FindPresent<\/td>\n100<\/td>\n0.75<\/td>\n1.285<\/td>\n1.271<\/td>\n1.256<\/td>\n<\/tr>\n
Insert<\/td>\n100<\/td>\n0.75<\/td>\n12.537<\/td>\n12.031<\/td>\n11.966<\/td>\n<\/tr>\n
FindMissing<\/td>\n1000<\/td>\n0.75<\/td>\n13.19<\/td>\n12.976<\/td>\n13.125<\/td>\n<\/tr>\n
FindPresent<\/td>\n1000<\/td>\n0.75<\/td>\n14.007<\/td>\n12.686<\/td>\n12.453<\/td>\n<\/tr>\n
Insert<\/td>\n1000<\/td>\n0.75<\/td>\n138.326<\/td>\n118.606<\/td>\n115.429<\/td>\n<\/tr>\n
FindMissing<\/td>\n10000<\/td>\n0.75<\/td>\n130.416<\/td>\n129.792<\/td>\n131.337<\/td>\n<\/tr>\n
FindPresent<\/td>\n10000<\/td>\n0.75<\/td>\n127.876<\/td>\n127.651<\/td>\n125.036<\/td>\n<\/tr>\n
Insert<\/td>\n10000<\/td>\n0.75<\/td>\n1388.83<\/td>\n1365.991<\/td>\n1241.811<\/td>\n<\/tr>\n
FindMissing<\/td>\n100000<\/td>\n0.75<\/td>\n1294.254<\/td>\n1297.491<\/td>\n1311.522<\/td>\n<\/tr>\n
FindPresent<\/td>\n100000<\/td>\n0.75<\/td>\n1271.941<\/td>\n1417.87<\/td>\n1324.824<\/td>\n<\/tr>\n
Insert<\/td>\n100000<\/td>\n0.75<\/td>\n28530.218<\/td>\n21140.233<\/td>\n20065.233<\/td>\n<\/tr>\n
FindMissing<\/td>\n10<\/td>\n1<\/td>\n0.137<\/td>\n0.134<\/td>\n0.137<\/td>\n<\/tr>\n
FindPresent<\/td>\n10<\/td>\n1<\/td>\n0.131<\/td>\n0.131<\/td>\n0.129<\/td>\n<\/tr>\n
Insert<\/td>\n10<\/td>\n1<\/td>\n0.988<\/td>\n1.618<\/td>\n1.642<\/td>\n<\/tr>\n
FindMissing<\/td>\n100<\/td>\n1<\/td>\n1.298<\/td>\n1.301<\/td>\n1.315<\/td>\n<\/tr>\n
FindPresent<\/td>\n100<\/td>\n1<\/td>\n1.289<\/td>\n1.26<\/td>\n1.253<\/td>\n<\/tr>\n
Insert<\/td>\n100<\/td>\n1<\/td>\n10.695<\/td>\n12.925<\/td>\n12.879<\/td>\n<\/tr>\n
FindMissing<\/td>\n1000<\/td>\n1<\/td>\n13.024<\/td>\n13.055<\/td>\n15.003<\/td>\n<\/tr>\n
FindPresent<\/td>\n1000<\/td>\n1<\/td>\n12.719<\/td>\n18.594<\/td>\n16.313<\/td>\n<\/tr>\n
Insert<\/td>\n1000<\/td>\n1<\/td>\n267.827<\/td>\n252.815<\/td>\n162.483<\/td>\n<\/tr>\n
FindMissing<\/td>\n10000<\/td>\n1<\/td>\n129.751<\/td>\n129.187<\/td>\n131.334<\/td>\n<\/tr>\n
FindPresent<\/td>\n10000<\/td>\n1<\/td>\n127.38<\/td>\n127.444<\/td>\n124.795<\/td>\n<\/tr>\n
Insert<\/td>\n10000<\/td>\n1<\/td>\n5708.22<\/td>\n5482.168<\/td>\n2368.82<\/td>\n<\/tr>\n
FindMissing<\/td>\n100000<\/td>\n1<\/td>\n1299.615<\/td>\n1293.964<\/td>\n1314.281<\/td>\n<\/tr>\n
FindPresent<\/td>\n100000<\/td>\n1<\/td>\n1265.741<\/td>\n1259.396<\/td>\n1252.715<\/td>\n<\/tr>\n
Insert<\/td>\n100000<\/td>\n1<\/td>\n94450.147<\/td>\n109098.851<\/td>\n31993.897<\/td>\n<\/tr>\n<\/table>\n
Paying attention the 0.5 load factor numbers (since this is what we chose for the trie’s use case), we are clearly doing better with B. C is roughly the same, though drastically faster in some situations as the load factor increases. For now we’ll declare C the winner and use it as our solver implementation.<\/p>\n
The final contest will be a head-to-head tourney of the managed and native solver implementations, to see if our theoretical improvements translate to actual wall clock time savings:<\/p>\n\n\n\n\n
Puzzle<\/th>\n.NET Core Solver<\/th>\nC++ Solver<\/th>\n<\/tr>\n
RME
WCL<\/br>TGK
API<\/th>\n		\n
\r\n[000.000] Loading trie...\r\n[000.059] Loaded 162309 words.\r\n[000.060] Finding valid words...\r\n[000.072] Found 754 valid words.\r\n[000.072] Finding solutions...\r\nMARKETPLACE-EARWIG\r\nWIGWAM-MARKETPLACE\r\nPRAGMATIC-CAKEWALK\r\n[000.080] Done.\r\n<\/pre>\n<\/td>\n
\n
\r\n[000.000] Loading trie...\r\n[000.049] Loaded 162309 words.\r\n[000.049] Finding valid words...\r\n[000.052] Found 754 valid words.\r\n[000.052] Finding solutions...\r\nMARKETPLACE-EARWIG\r\nWIGWAM-MARKETPLACE\r\nPRAGMATIC-CAKEWALK\r\n[000.054] Done.\r\n<\/pre>\n<\/td>\n<\/tr>\n
ERG
BID
NCF
TAO<\/th>\n		\n
\r\n[000.000] Loading trie...\r\n[000.056] Loaded 162309 words.\r\n[000.057] Finding valid words...\r\n[000.071] Found 1436 valid words.\r\n[000.072] Finding solutions...\r\nROBAND-DEFECTING\r\n -- snipped 72 other solutions -- \r\nOBTECTED-DRAFTING\r\n[000.120] Done.\r\n<\/pre>\n<\/td>\n
\n
\r\n[000.000] Loading trie...\r\n[000.049] Loaded 162309 words.\r\n[000.050] Finding valid words...\r\n[000.053] Found 1436 valid words.\r\n[000.053] Finding solutions...\r\nBAITED-DEFORCING\r\n -- snipped 72 others solutions --\r\nOBTECTED-DRAFTING\r\n[000.092] Done.\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/table>\n
C++ wins! It “only” took a custom data structure and several iterations of optimizations, but we got there in the end. Was it worth it? Sure, if all we care about is personal enrichment. Otherwise, you should look at your situation and heed the advice of Carlos Bueno<\/a>:<\/p>\n
Unless your optimizations are going to stick around long enough to pay for the time you spend making them plus the opportunity cost of not doing something else, it’s a net loss.<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"
Last week, in my continuing exploration of a C++ Letter Boxed solver, I had to build a faster hash table to improve performance. Today we’ll make it even faster, hoping to catch up to the performance of my .NET Core… <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[105,101,104],"tags":[],"class_list":["post-5650","post","type-post","status-publish","format-standard","hentry","category-games","category-native","category-performance"],"_links":{"self":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5650","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5650"}],"version-history":[{"count":4,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5650\/revisions"}],"predecessor-version":[{"id":5654,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5650\/revisions\/5654"}],"wp:attachment":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5650"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5650"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5650"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}