4 ms·
It'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 fro
by londons_explore 4y ago
It'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.