5 ms·
> C++20 now has a "hashable" concept to help with this I'm sorry, you can easily solve this problem in K&R C from 1979.
by kazinator 7y ago
> C++20 now has a "hashable" concept to help with this
I'm sorry, you can easily solve this problem in K&R C from 1979.
- shawxe 7y agoYeah, it's called memset. Not sure if this bug is supposed to be subtle or something, but if you require the padding bytes to be consistent then you need to consistently initialize your structs. Ignoring UB often leads to these sorts of bugs. EDIT: Based on some of the comments I'm getting here, it seems like some of you have never implemented a hashmap/generic interface in vanilla C and it shows. If you want a hashmap that is generic and you don't want to write/specify a hashing function for keys on map initialization, then what you're likely to end up doing is ensuring that keys are initialized consistently, providing key size on map initialization, and simply performing a hash on the key as though it were a buffer of bytes. Suggesting that this is somehow any more fragile than anything else in C or that templates should be used instead, which is an absurd comment since templates do not exist in C, is ridiculous. This comment is replying to a comment about how solutions to this problem have existed since K&R C--and they have. You don't need templates to not ignore UB, although if you are using C++ you can certainly use templates (and also take advantage of the stronger type system) to work around issues like this. The point is that avoiding undefined behavior in C/C++ hashmap implementations is not something that has only recently become possible. C solutions may be more fragile, but that doesn't stop them from being "correct" in that will yield correct behavior unless an error is made elsewhere. Code that makes assumptions about the values of padding without explicitly setting those values is NOT correct and for anyone who works in a language like C/C++ regularly, that should be obvious.
- saagarjha 7y agoI don’t think memset is required to zero out padding bytes. The correct way to do this is to only access non-padding bytes.
- shawxe 7y agosizeof(struct foo) is required to return the actual size, including padding, so struct foo foo_inst; memset(&foo_inst, 0, sizeof(foo_inst)); will certainly result in all padding bytes being set to zero.
- saagarjha 7y agosizeof will include padding, but there is no need for memset to actually perform a write that cannot be consistently observed.
- deleted 7y ago[deleted]
- icedchai 7y agoAre you saying memset does not have to write the entire struct? I understand it can be optimized out, but thought it if it was actually executed it had to set all of the specified bytes.
- saagarjha 7y agomemset must write to the bytes that underly the members of the struct. What it does to padding bytes is not of consequence to you, as you cannot observe it as far as I understand. (That is, if you tried to read it out it would not necessarily be the value you had memset, or even be consistent across reads.)
- icedchai 7y agomemset definitely writes to padding bytes, as noted by several other folks here. you observe these padding bytes during serialization and deserialization (disk, network, memory mapped buffer, etc.) Note this is important enough that compiler folks consider it a bug if it doesn't work correctly. see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92486 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92486 for a recent example involving memset and memcpy.
- banachtarski 7y agoWrong answer. This is brittle and relies on the memory always being initialized correctly and will be prone to all sorts of issues in the wild. Better is just either templatize on the key type or store the size on the map.
- saagarjha 7y agoThe answer is wrong more because it relies on padding bytes having consistent values than a lack of templating.
- shawxe 7y agoTo be clear, there are obviously different/better ways to handle this in C++. We're talking about K&R C here.
- banachtarski 7y agoRight I mentioned "store size of the key on the map" as the second option for K&R/Ansi C.
- scatters 7y agomemset, sure, then you copy the struct (return it or pass it by value) and the compiler won't bother copying the padding bytes. Or worse, an optimizing compiler will see that you're writing to padding bytes and helpfully no-op it.
- kazinator 7y agoA compiler that optimizes away memset is not one that could be used for targeting anything that sits on a network.
- saagarjha 7y agoThat immediately rules out GCC and Clang…
- kazinator 7y agoI don't think so, unless we're mistaking memset for __builtin_memset.
- scatters 7y agoGCC treats the two identically. See https://github.com/gcc-mirror/gcc/blob/229c0ef777161ec5adfb71ef1611af502541ccda/gcc/builtins.def#L93 https://github.com/gcc-mirror/gcc/blob/229c0ef777161ec5adfb7...
- kazinator 7y agoI see; because the sixth argument (BOTH_P) in that macro call is true.
- shawxe 7y agoFirst of all, there is no way the compiler is going to optimize a call to memset(&foo, 0, sizeof(foo)) when &foo is being interpreted as a void pointer. That doesn't even make sense. Second of all, in a generic C interface keys are likely to be treated as void pointer and almost certainly are going to be moved around with memcpy etc. rather than returned/passed by value since doing so would make the interface non-generic.
- kazinator 7y agoOne solution consists of using memset to initialize the structure to zero, and using memcpy to copy it instead of structure assignment. (Problem: pass-by-value in function calls won't use memcpy; abstractly, it uses member-for-member assignment which is not required to copy padding. A function that wants to calculate the correct has has to prepare a blank object with memset, then individually assign the fields into it from the incoming object.) Another solution, more along the lines of what I was thinking, is simply to associate the hash table with a hashing function which processes the type as a structure, hashing the members individually rather than as a pad of memory. C++ templates refine this by adding the ability to deduce the hashing function statically, and possibly inline it, which we could do with some preprocessing in C, along the lines of how those TAILQ macros from BSD work for linked lists.
- shawxe 7y ago> Another solution, more along the lines of what I was thinking, is simply to associate the hash table with a hashing function which processes the type as a structure, hashing the members individually rather than as a pad of memory. This solution is probably what I would go for in most cases as well. The most compelling reasons I can think of for going the other way would be if there were a desire to use a specific hashing function/algorithm on all keys regardless of type or if there were a desire to have keys of different types in the same map.
- munchbunny 7y agoThat's true but missing the point. The point is that C++20 adds a way to catch yourself before you make the exact type of mistake the grandparent comment talks about. https://en.cppreference.com/w/cpp/language/constraints https://en.cppreference.com/w/cpp/language/constraints