3 ms·

Compilers are generally not permitted to change the layout of your data, and standard library data structures and algorithms are generally not that great. Somet

Compilers 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 ago
But 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 ago
  This 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 ago
  The 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.
planede 4y ago
> 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. Can you elaborate on this one?
- anonymoushn 4y ago
  There's a talk about this data structure here: https://www.youtube.com/watch?v=JZE3_0qvrMg https://www.youtube.com/watch?v=JZE3_0qvrMg Basically it stores one array of 1-byte markers that contain a full-or-empty bit and a 7-bit prefix of the hash, then a separate array of buckets. The lookup first loads a neighborhood of bytes in the former array to find entries that match in the first hash byte or empty entries. If the table is very highly loaded or if the hash function is low quality, some checks for equality of the full hash or equality of the value (the former probably just costs a cache miss and the latter might be very expensive) can be skipped, but under better conditions for the hash and load factor and known-pretty-bad conditions for randomness of consecutive lookups, it can be better to avoid the cost of doing one load in the small array of markers and another load in the large array of hash table entries. In the talk the presenter also says that they've changed the first load in such a way that it sometimes spans two cache lines, which makes it a bit more expensive, but that this was nonetheless a win for them.

londons_explore 4y ago

But 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 ago
This 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 ago
The 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.

planede 4y ago

> 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. Can you elaborate on this one?

anonymoushn 4y ago
There's a talk about this data structure here: https://www.youtube.com/watch?v=JZE3_0qvrMg https://www.youtube.com/watch?v=JZE3_0qvrMg Basically it stores one array of 1-byte markers that contain a full-or-empty bit and a 7-bit prefix of the hash, then a separate array of buckets. The lookup first loads a neighborhood of bytes in the former array to find entries that match in the first hash byte or empty entries. If the table is very highly loaded or if the hash function is low quality, some checks for equality of the full hash or equality of the value (the former probably just costs a cache miss and the latter might be very expensive) can be skipped, but under better conditions for the hash and load factor and known-pretty-bad conditions for randomness of consecutive lookups, it can be better to avoid the cost of doing one load in the small array of markers and another load in the large array of hash table entries. In the talk the presenter also says that they've changed the first load in such a way that it sometimes spans two cache lines, which makes it a bit more expensive, but that this was nonetheless a win for them.