17 ms·
A quick and practical “MSI” hash table
- londons_explore 4y agoIt's nice, but I think the days of writing your own standard data structures are probably best left behind us. If we use standard libraries, we can benefit from extreme optimization, both in the library but also in the compiler (eg. A smart enough compiler could see you setting an entry in a map and immediately reading the same entry, and it could optimize out the read). The data structures can be optimized for CPU architectures and cache sizes for example - something that mini implementations like this would never bother with. Likewise, a smart compiler could see that you never call "delete" on entries in a data structure, and use an implementation that is more efficient, yet doesn't support deletes.
- JonChesterfield 4y agoOr instead of standard libraries, a compiler you can add optimisations to that recognise your structures.
- londons_explore 4y agoCompilers don't do any of these things today... but they could.
- _benedict 4y agoStandard libraries are often a lot less impressive than you might expect. I think it’s important that people retain the ability to write their own data structures so that when it is helpful and relevant that skill is in the toolkit.
- anonymoushn 4y agoCompilers are generally not permitted to change the layout of your data, and standard library data structures and algorithms are generally not that great. Sometimes this is because of unreasonable constraints imposed by standards or APIs. For example, c++ std::unordered_map basically must use separate chaining, even though this is really bad, and many standard library sort functions are unnecessarily slow because they expose an API that takes a comparator (so they cannot use radix sort). Even very popular and reputedly performant data structure implementations like absl::flat_hash_map are pretty easy to beat for specific use cases. In this specific case, it's easy to beat because it incurs a cost of at least 2 cache misses per lookup, rather than 1. Edit: As an aside, I have sort of lost faith in "sufficiently smart compilers" as a result of recent adventures in SIMD programming. Compilers seem to do an ok job of constraint propagation on integer values stored individually, but will not do the same sort of thing for values in SIMD registers. For example, if you'd like to compute the vector of u32's resulting from multiplying some vector of u32's `a` by some constant `b` and taking the high 32 bits of the result, there's no instruction for that (in AVX2). There is an instruction to compute the *full* 64-bit multiply result of the lower 32 bits of 64-bit words though. So you can get the high bits of the multiply results for the 1st, 3rd, 5th, and 7th u32's within each lane using that instruction. To get the other u32's into the right places you can use a 64-bit immediate shift by a constant, a shuffle of 8-bit values by a constant, a permute of 32-bit values by a constant, or probably some other operation, and the compiler won't replace the one you pick with the best one of these options even though it's trivial to show these are all equivalent. Then you can multiply that value by the constant. Now your results are in the 2nd, 4th, 6th, and 8th u32's within each lane of 2 vectors. You again must move some of them over using one of the aforementioned 3 or more equivalent methods, and then you must blend the two vectors together. If you literally write a blend here, you may find that it's slower than using a shuffle and a bitwise or, and the compiler will not perform this substitution either. Much of your comment is about much more difficult program transformations than these. I would like compilers to do these things, but I'm not holding my breath.
- londons_explore 4y agoBut all these things could be changed... Compilers could be permitted to change the layout of your data. standard libraries could be great. Exposing an API that takes a comparator need not be slow if that API isn't used, or the function passed in is fully understood by the compiler. Basically, I'm saying that most hours of human effort put into optimising things should be put into compilers and standard libraries, because they benefit every project rather than just your personal project. It's hours better spent on a global basis.
- anonymoushn 4y agoThis sounds good, to the extent that it's feasible. I've recently been thinking about how it's sad that ~everyone uses much worse general-purpose lossless compression and decompression algorithms than those sold by RAD Game Tools. It's difficult to estimate the amount of energy spent daily on the difference between zstd and Oodle. If I had to choose how to spend my personal effort on fixing this issue, I would expect higher ROI over the next few years from submitting patches to zstd than from submitting patches to LLVM that try to get it to emit SIMD-ized inner loops for string processing algorithms like those in zstd.
- Jasper_ 4y agoThe hard problems are always people problems. If they changed the layout of my data, I couldn't use that compiler, since I really do rely on my data being in a specific order. I know what fields in my struct are hot, and what are cold, and a compiler really can't figure that out for me. That would also break every existing ABI out there. Maybe you'd add a struct to say "make this data ABI-compliant" but then everything would get that tag. Standard libraries can't be great. They have to be safe, conservative and generic by default. std::vector<bool> is a classic example of what happens when a standard library tries to become too clever with optimization, and ends up screwing itself for an eternity. C++ is too far gone to introduce good allocation patterns for its core data structures. A custom solution can be tailor-made by knowing what works well together. I could spend 5,000 hours trying to get basic features through the C++ committee, or I could just write my own in half an hour. The idea that effort should always go to the compilers and standard library is countered by 20 years of complete nothing on any of those fronts (std::unordered_map still sucks), half-baked libraries like <random> making it into the standard, and compilers not even getting remotely better for things like SIMD, instead choosing to focus on more random undefined behavior passages to exploit.
- badsectoracula 4y ago> If we use standard libraries, we can benefit from extreme optimization I did a quick test[0] about that since it is a common thing people claim ("use the standard library, it has been battle tested and optimized to heavens", etc). Since the article is mainly just about the hash part of the hash table, i only tried with hash sets instead of full hash maps, though the difference is trivial. I generated a 256MB file with 67108864 32bit unique random integers and tried to use both C++'s unordered_set as well as a custom set built using the method described in the site (i also used the 32bit integer hash from a link in the article). I used C++ because it is the closest to C that has a standard library that provides a hash set. The results on my machine (Ryzen 3700X, Linux, GCC 12.1.1) are: std version: 19504ms custom version: 3979ms The "std version" is almost five times slower than the custom purpose-built version. Note that this is the "best case" scenario where i specify a number of buckets to minimize resizing - without that the std version needs 41382ms instead (i.e. a naive use of unordered_set would be almost twice as slow as with providing the bucket count and about 10 times slower than the custom version). So yeah, i don't think the days of writing your own data structures are left behind, at least as far as purpose built structures for improving performance are concerned. Of course sometimes you just want to replace a very simple/naive algorithm with an at least theoretically faster one (i.e. replacing a linear search in a big unordered array with some map) so having the language provide some reusable data structures is convenient. But if that doesn't solve the performance problem you may have and the problem is in the data structure you can most likely do better than the generic structures the language has - after all you know your data and your code at a better and higher level than the compiler ever will. [0] http://xtra.runtimeterror.com/snippets/dir?ci=tip&name=hash/customvsstd http://xtra.runtimeterror.com/snippets/dir?ci=tip&name=hash/...
- adgjlsfhk1 4y agonote that the c++ built-in hash table is known to be really bad.
- badsectoracula 4y agoYeah i guessed (i haven't really used them much myself), but the argument was about using the functionality in the standard library. Of course another practical alternative to both C++ and C (since the linked article is about C) is to use some 3rd party library.
- Jaruzel 4y agoThe acronym 'MSI' is already heavily in use: https://en.wikipedia.org/wiki/MSI https://en.wikipedia.org/wiki/MSI Might be an idea to re-think the hash table name?
- kubb 4y agoC means rolling your own quick and practical hash table in 250 lines without tests, whenever you need it. Kinda answers the question of why people are looking for a better alternative to C that was discussed here recently. I wish we had a name for this, like "required non-innovative effort penalty" for using C, so that we can abstract some of these discussions that end up happening every time C is mentioned.
- mananaysiempre 4y agoThat’s one of the few places that genuinely itch in my C experience, but I haven’t seen it solved anywhere, even partially. The hard part is, there are a myriad tiny variations of each data structure, especially the simplest ones (even prehistoric Knuth vol 1 lists a dozen of versions of a linked list); the C practice is generally to write the most appropriate one in each case (because there is no reason to value a premade one if you don’t have any, and because manual implementation makes to want and appreciate those small affordances that pointer-to-head / dummy-head / cyclic pointer-to-head / cyclic dummy-head / etc. give you). This does not always work well, both because it forces you to optimize with little data, and because natural laziness can lead you to avoid a marginally more complex data structure for longer than you really should (and possibly have the laziness-induced inefficiency be lost and forgotten). But it does give working with data structures in C a certain feel and style that I haven’t seen reproduced with reusable implementations. When a language uses those, it’s either by choosing a small set of structures and running with them (Lua, Awk, Python, perhaps Tcl as a more interesting example) or by parametrizing everything to the hilt (C++ and D). Even in C, the language more steers you towards rolling your own than forces it (cue qsort & bsearch, BSD and Linux macros, etc.). Yet the small set is frequently too small, and the One Implementation to rule them all is bloated far beyond the mental capacity of a single person and still too inflexible. Honestly, if there is something I’d like from a C successor, it’s reproducing the hand-rolled-data-structure style without the actual hand rolling (in most cases), and that’s as much a library feature as a language one. I can name a lot of other things I’d like to see in my low-level language, but if I had to choose one improvement, that would be it. So far, I haven’t seen a convincing attempt.
- 4y ago
- anonymoushn 4y agoFNV-1a seems like a questionable choice. You can get higher quality and throughput for short strings from a hash that uses AES instructions or wyhash, or for long strings maybe from xxhash. > If your input is made of integers, or is a short, fixed length, use an integer permutation, particularly multiply-xorshift. It takes very little to get a sufficient distribution. Sometimes one multiplication does the trick. Fixed-sized, integer-permutation hashes tend to be the fastest, easily beating fancier SIMD-based hashes, including AES-NI. For example: This is... probably not true? If you want to hash exactly 16 bytes, you can do it in 4 instructions on x64 like this: const u8x16 chunk0 = _mm_loadu_si128((u8x16*)data); const u8x16 h10 = _mm_aesenc_si128(chunk0, key); const u8x16 h20 = _mm_aesenc_si128(h10, key); const u64 hash = _mm_extract_epi64(h20, 0); If the total latency of these instructions is a bit higher than the total latency of the 8 instructions in the provided uuid1_hash, but if you want to hash more than 1 value, you may find that hashing more values allows the 4-instruction approach to achieve higher throughput than the 8-instruction approach. Even 2 values at a time should do it. For example on Haswell the combined latency seems to be 16 cycles for load+aesenc+aesenc+store vs. 12 for 2 shifts, 2 multiplies, 2 xors and 2 adds (the adds and multiplies are arranged in such a way that lea may not be used). I tried uuid1_hash on godbolt.org and it actually emitted a bunch of mov's in addition to what I expected. I am of course not an expert in these matters, and the fine author is invited to publish a benchmark or to demonstrate the superiority of his hash table and his method for hashing short strings at https://highload.fun/tasks/2 https://highload.fun/tasks/2
- Genbox 4y ago> You can get higher quality and throughput for short strings from a hash that uses AES instructions or wyhash, or for long strings maybe from xxhash. What would you consider a short string? The latency of AESENC is 5 if I remember correctly. In that time you can FNV-1a a "short" string. For longer strings I agree that WyHash and xxHash is better. I have a benchmark of both further down on FastHash's github page[1]. Of course, that is only a measure of speed, but both are high quality as well[2]. From the top of my head, t1ha, falkhash, meowhash and metrohash are using AES-NI and none of them are particularly fast on short inputs, and at least two of them have severe issues, despite guarding against lots of vulnerabilities, which your construction does not. You are right regarding bulk-keying with SIMD outperforming any kind of scalar hashing one-at-the-time. I've build a database that does just that (requires keys to be available in bulk - like when doing bulk inserts) using SIMD, and the latency becomes negligible. [1] https://github.com/Genbox/FastHash https://github.com/Genbox/FastHash [2] https://github.com/rurban/smhasher https://github.com/rurban/smhasher
- xnorswap 4y agoI've been implementing data structures like hash tables for a project I've been working on so it's interesting to see alternative approaches for easy to implement hash tables. One particular note of agreement is regarding deletion. An "Insert only hash table" is a very useful data structure which can have performance improvements given the extra overhead needed to support deletion. This is very similar to the design that dotnet uses for HashSet[1]. For deletion they use the term "freelist" rather than "gravestones" which is definitely less emotive language. ( They also use linear probing because it's generally much faster than double-hashing because branch prediction and memory look ahead and other things I don't fully understand mean that it can just grab the next X items from memory all at once before starting to compare them rather than having to jump around the array. ) One choice from OP's design which I find odd is the choice of power-of-2 for the table size. I was under the impression that choosing a table size of a prime number has significant advantages such as being able to more easily expand the table. On a related note, my favourite hash-table is a fixed-size zero-probing "probabilistic" hash table where hash collisions are dealt with by just overwriting the hash. That makes the choice of a good size for the hash table a fun problem in itself. It's extremely fast to both implement and run if you don't mind the occasional bit of data loss, although the probability of data loss can be well controlled by choice of table size. [1] https://github.com/dotnet/runtime/blob/4017327955f1d8ddc43980eb1848c52fbb131dfc/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/HashSet.cs https://github.com/dotnet/runtime/blob/4017327955f1d8ddc4398...
- _benedict 4y ago> They also use linear probing because it's generally much faster than double-hashing Optimal is probably to use linear probing for a few indices at a time (depending on size of hash table entries, say, 4 or 8), and double hashing to move to a new region if no empty elements can be found in that run.
- anonymoushn 4y agoIf you can choose to have a quality hash function, it's probably better to do that.
- bArray 4y agoFor an ultra simple hash table, you just need a few things (the following is from my head). First is a 'reasonable' hash function (although with a few more lines you can do better [1]): unsigned int H(char* s){ int h; for(h = 0; *s; s++) h = ((h << 5) + h) + *s; return h; } And then to build your hash table: int L = <table length>; // Large enough to reduce collisions char** t = (char**)malloc(L * sizeof(char*)); memset(t, 0, L * sizeof(char*)); // Set it all to empty by default Then to use it: /* Put example */ t[H("key string") % L] = "value string"; /* Get example */ char* v = t[H("some key") % L]; if(v) printf("value -> %s\n", v); /* Remove example */ t[H("another key") % L] = NULL; For them most part you can get pretty far with just this in C. [1] https://coffeespace.org.uk/projects/hash-functions-part-2.html https://coffeespace.org.uk/projects/hash-functions-part-2.ht...
- anonymoushn 4y agoThis insert routine can destroy an unrelated key, so I'm not sure it's appropriate to call it a hash table.
- bArray 4y agoYou would of course check whether there is a collision if you care. You would size it such that a collision is low probability though.
- pca006132 4y agoGood luck when key collision happens and wrong value comes out causing errors in other part of your code...
- bArray 4y agoKey collisions are of course a problem. This is a quick and dirty implementation. If you care about checking for collisions, you could instead have: typedef struct{ char* k; char* v; } KV; int L = <table length>; // Large enough to reduce collisions KV* t = (KV*)malloc(L * sizeof(KV)); memset(t, 0, L * sizeof(KV)); // Set it all to empty by default Then: /* Put example (detect collisions) */ char* k; if(t[H(k) % L] == NULL || strcmp(t[H(k) % L].k, k) == 0) t[H(k) % L] = "value string"; else printf("Collision\n"); // Handle as you like Of course this can get more and more advanced. The point wasn't to make a zero-collision table, it was just something that could be used quickly.