4 ms·

This hashtable sure mallocs a lot! Look here for example: Entry newVal = malloc(sizeof(Entry)); newVal->key = strdup(key); Why not: Entry e = malloc(sizeo

This hashtable sure mallocs a lot! Look here for example: Entry *newVal = malloc(sizeof(Entry)); newVal->key = strdup(key); Why not: Entry* e = malloc(sizeof(Entry) + strlen(key)); Now you can also skip the pointer to the key, saving 8 bytes for each entry. Also, just return the hashtable by value, it's so small. I think that if we're coding in C, C++ or Zig, then it can be fun to actually use the lower level power to our advantage :).

aloisklink 3y ago
Even better, you can use [C99 Flexible array members][1], e.g. something like: struct KeyedEntry { struct Entry entry; char key[]; // flexible array member }; It's not too much more useful when just using `char`, but for other data types, it's a bit cleaner, since it handles alignment/padding better. [1]: https://en.wikipedia.org/wiki/Flexible_array_member https://en.wikipedia.org/wiki/Flexible_array_member, or https://beej.us/guide/bgc/html/split/structs-ii-more-fun-with-structs.html#flexible-array-members https://beej.us/guide/bgc/html/split/structs-ii-more-fun-wit... _Edit_: Something like this might not be suitable for the author, since they did mention how they wanted each `struct` to have a fixed size.
asveikau 3y ago
> malloc(sizeof(Entry) + strlen(key)); Don't forget +1 for the terminator. I also think a linked list is not a great data structure in practice. Having the buckets be one of those amortized-O(1)-append heap allocations would be kinder on CPU caches. But, if you are making the string part of the entry, that would also require padding the string length to word boundaries so that the struct gets aligned. Note also if you kept the length of the string somewhere (which you would need to for my above paragraph's suggestion), you could avoid strcmp-ing hash collisions where the string has different length. Strcmp is going to add up to an expensive thing in this code. This code also never checks the return value of malloc. Color me unimpressed with this code. (Cue people arguing that checking for malloc failure is a bad idea ... Linux oom killer and high level languages have you spoiled, there i said it! /s)
- wahern 3y ago
  > > malloc(sizeof(Entry) + strlen(key)); > Don't forget +1 for the terminator. Also should check for arithmetic overflow, or at least static_assert that sizeof(Entry) is "too small" to matter. (Hopefully the process of deciding what "too small" should be results in just adding the overflow check.)
  - dahfizz 3y ago
    Not really. We defined Entry, so we know it's only a few bytes. And we know size_t is large enough to iterate over all of main memory. So the only way that statement overflows is if the key is literally larger than main memory. Not a concern.
    - asveikau 3y ago
      I agree with your reasoning, but it's not "literally", it's main memory minus (sizeof(struct Entry) - 1). But it's impossible to find a C string that big. Any point in memory is pretty clearly going to hit a 0 or a page fault before then.
- the-smug-one 3y ago
  >But, if you are making the string part of the entry, that would also require padding the string length to word boundaries so that the struct gets aligned. It also makes deletion a far more complicated situation. You'd essentially be implementing your own allocator then.
  - asveikau 3y ago
    That's true. Maybe you could keep it simpler by making small strings inline with the struct, but larger strings go on the heap. This gives you fixed size records, so removal could be o(1) by swapping with the last one and shortening.
- lyu07282 3y ago
  Well it's C, it's ought to be broken in some way. Just put it in some sufficiently high value target, a few months to years later the CVE is gonna explain how it was broken exactly.
kccqzy 3y ago
When writing C code, which for me is rare these days, the language doesn't give me enough guardrails in the type system (e.g. unique_ptr) and at compile time that I'd prefer to write straightforward and dumb code. And that means code that does a lot of malloc()s with no surprises. If I have a char* that cannot be free()d, such as pointing to the middle of a longer string, I don't even let that escape the scope of a single function. Leave the memory management trickeries to more modern languages like C++, or, better yet, Rust.
- amstan 3y ago
  I think parent was criticizing the multiple use of mallocs when one would be cleaner and easier. This wouldn't really make a difference to the library users, besides perhaps more heap fragmentation in the old version.

This hashtable sure mallocs a lot! Look here for example: Entry *newVal = malloc(sizeof(Entry)); newVal->key = strdup(key); Why not: Entry* e = malloc(sizeo

aloisklink 3y ago

Even better, you can use [C99 Flexible array members][1], e.g. something like: struct KeyedEntry { struct Entry entry; char key[]; // flexible array member }; It's not too much more useful when just using `char`, but for other data types, it's a bit cleaner, since it handles alignment/padding better. [1]: https://en.wikipedia.org/wiki/Flexible_array_member https://en.wikipedia.org/wiki/Flexible_array_member, or https://beej.us/guide/bgc/html/split/structs-ii-more-fun-with-structs.html#flexible-array-members https://beej.us/guide/bgc/html/split/structs-ii-more-fun-wit... _Edit_: Something like this might not be suitable for the author, since they did mention how they wanted each `struct` to have a fixed size.

asveikau 3y ago

> malloc(sizeof(Entry) + strlen(key)); Don't forget +1 for the terminator. I also think a linked list is not a great data structure in practice. Having the buckets be one of those amortized-O(1)-append heap allocations would be kinder on CPU caches. But, if you are making the string part of the entry, that would also require padding the string length to word boundaries so that the struct gets aligned. Note also if you kept the length of the string somewhere (which you would need to for my above paragraph's suggestion), you could avoid strcmp-ing hash collisions where the string has different length. Strcmp is going to add up to an expensive thing in this code. This code also never checks the return value of malloc. Color me unimpressed with this code. (Cue people arguing that checking for malloc failure is a bad idea ... Linux oom killer and high level languages have you spoiled, there i said it! /s)

wahern 3y ago
> > malloc(sizeof(Entry) + strlen(key)); > Don't forget +1 for the terminator. Also should check for arithmetic overflow, or at least static_assert that sizeof(Entry) is "too small" to matter. (Hopefully the process of deciding what "too small" should be results in just adding the overflow check.)
- dahfizz 3y ago
  Not really. We defined Entry, so we know it's only a few bytes. And we know size_t is large enough to iterate over all of main memory. So the only way that statement overflows is if the key is literally larger than main memory. Not a concern.
  - asveikau 3y ago
    I agree with your reasoning, but it's not "literally", it's main memory minus (sizeof(struct Entry) - 1). But it's impossible to find a C string that big. Any point in memory is pretty clearly going to hit a 0 or a page fault before then.
the-smug-one 3y ago
>But, if you are making the string part of the entry, that would also require padding the string length to word boundaries so that the struct gets aligned. It also makes deletion a far more complicated situation. You'd essentially be implementing your own allocator then.
- asveikau 3y ago
  That's true. Maybe you could keep it simpler by making small strings inline with the struct, but larger strings go on the heap. This gives you fixed size records, so removal could be o(1) by swapping with the last one and shortening.
lyu07282 3y ago
Well it's C, it's ought to be broken in some way. Just put it in some sufficiently high value target, a few months to years later the CVE is gonna explain how it was broken exactly.

kccqzy 3y ago

When writing C code, which for me is rare these days, the language doesn't give me enough guardrails in the type system (e.g. unique_ptr) and at compile time that I'd prefer to write straightforward and dumb code. And that means code that does a lot of malloc()s with no surprises. If I have a char* that cannot be free()d, such as pointing to the middle of a longer string, I don't even let that escape the scope of a single function. Leave the memory management trickeries to more modern languages like C++, or, better yet, Rust.

amstan 3y ago
I think parent was criticizing the multiple use of mallocs when one would be cleaner and easier. This wouldn't really make a difference to the library users, besides perhaps more heap fragmentation in the old version.