7 ms·

Very interesting, these kinds of articles are (to me) some of the best content we get on here. I'm no expert in any of the languages used except maybe C, at le

by unwind 6y ago

Very interesting, these kinds of articles are (to me) some of the best content we get on here. I'm no expert in any of the languages used except maybe C, at least I'm quick to form opinions about C code. In C, I'm not so sure that there is a well-established "idiomatic" concept, since C is not so tightly bound to a community as more modern languages. At least that's my feeling. That said, I was shocked to see that the example code did heap-allocations to store integers. Single integers, one per allocation, per "counting bucket". I would store the count in the data pointer without a second thought, I just "can't" make 4/8-byte heap allocations and still sleep at night. Especially after all the concern about processing the input in large blocks for performance! Casting an integer to/from a void pointer should be pretty safe according to my gut feel. If that turns out to be false, I would dump the libc's hash API altogether, since it makes me do heap allocations to store single integers. I tried making the change locally, and the time taken (as measured with the OP's benchmarking program) dropped from 0.11 to 0.10 on my system (a Dell laptop running an Intel i5-7300). That's at least something.

c-cube 6y ago
Afaik the only integer type it's safe to cast from and to pointers is intptr_t. Not exactly the type people reach to when writing the first "simple" version. Another comment also points out that hcreate (which is not posix, only GNU?) and the likes use a global hashmap? I can't see a lot of use cases for such a singleton datastructure.
- remexre 6y ago
  hcreate is POSIX, hcreate_r (which allows having multiple hashmaps per process) is the GNU extension, iirc. I thought POSIX added a bunch more safe pointer casts, but I don't know off the top of my head...
  - therealcamino 6y ago
    I've been programming in C for decades and I'd never heard of hcreate. I'm sitting here wondering how the heck did that ever get standardized, allowing single hash table per process. What a bizarre feature.
    - c-cube 6y ago
      I wonder if it's like insanities like SIGPIPE: it's kind of useful if you write IO tools in a few dozen/hundred lines of C. You don't need to carry around explicit context, or check if writes failed, or anything. Of course it sucks for anything else and we still have to deal with SIGPIPE .
- beached_whale 6y ago
  At least in C++, it’s any integer type that is large enough. uintmax_t/intmax_t are guaranteed to be large enough
- scatters 6y ago
  It just means that you need to cast via intptr_t, i.e. double casts `(void*)(intptr_t)i` and `(int)(intptr_t)p`. GLib has macros for it if you feel that's useful.
- fanf2 6y ago
  If you need to round-trip a pointer through an integer and back to the same pointer, you need to use intptr_t or uintptr_t. (Note that this is true for object pointers but not necessarily function pointers. There’s no integer type guaranteed to be big enough for a function pointer.) If you want to round-trip an integer through a pointer and back to the same integer, you can use any integer type provided it is not bigger than intptr_t or uintptr_t.
benhoyt 6y ago
Yeah, I would have liked to avoid it too. But I think you have to allocate with the hcreate/hsearch API (for the "simple" C version). When I roll my own hash table with optimized.c I don't allocate for the integers.
- unwind 6y ago
  No, you can just jam the integer into the "data" field in the structure and skip that allocation. As I said, and others have commented, it requires some complicated castery to avoid UB, but it's totally doable (and at least GCC does the right thing, while warning, with no advanced casts). Thanks for an interesting article!
chaostheory 6y ago
It would be nice if the post went further as in using code that either uses concurrency or parallelism.
- burntsushi 6y ago
  Someone on Lobsters suggested this too, and I don't think it would be particularly edifying. But maybe I'm wrong. Someone should go out and do that benchmark. Maybe we'll learn something. Here is what I wrote though: Coming up with a benchmark is hard. Benchmarks like these are models. All models are wrong. But. Some are useful. Follow you thinking to its logical conclusion. If you open up the parallel programming flood gates, now you need to do that for all of the programs. Now your effort to contribute a sample for each language goes up. Maybe enough where actually doing the benchmark isn't practical. So let's play the tape. If someone told me, "sure, have fun, throw threads at this!" I'd probably say, "can I use memory maps?" And let's say, "yes, sure, go for it!" I say okay, here's my first crack at it: 1. Hope stdin is a file and open it as a memory map. 2. Split the memory map slice into N chunks where N is the number of logical CPU cores on the system. 3. Run approximately the same algorithm devised in existing code submissions in N different threads, with one thread per chunk. 4. At the end, join the results and print. If that ends up being the best strategy overall, then your model has become over-complicated because performance now likely depends on step (3). Which is exactly what the existing benchmark is. Now, maybe some languages have a harder time passing data over thread boundaries than others and maybe that impacts things. But that doesn't apply to, say, C, Rust, C++ or Go. If that's not the best strategy, then maybe there is a cleverer approach that involves synchronizing on one shared data structure. I doubt it, but maybe. If so, your benchmark turns into one that is very different. It's no longer just about data transformation, but now you have to worry about synchronization trickiness. And now you're way outside of a standard goroutine pool that you might have used in Go. Building a good benchmark is an art. Sometimes the constraints look dumb and arbitrary. But you have to sit down and really look at it from a bunch of different angles: * Do the constraints approximate some real world conditions? * Do the constraints inhibit writing code that looks like real world code? * Do the constraints inhibit optimizing the crap out of the code? * Do the constraints make the benchmark difficult to create in the first place? * Do the constraints permit easy and clear measurement? There are probably more things that I didn't think about.

by unwind 6y ago

c-cube 6y ago

Afaik the only integer type it's safe to cast from and to pointers is intptr_t. Not exactly the type people reach to when writing the first "simple" version. Another comment also points out that hcreate (which is not posix, only GNU?) and the likes use a global hashmap? I can't see a lot of use cases for such a singleton datastructure.

remexre 6y ago
hcreate is POSIX, hcreate_r (which allows having multiple hashmaps per process) is the GNU extension, iirc. I thought POSIX added a bunch more safe pointer casts, but I don't know off the top of my head...
- therealcamino 6y ago
  I've been programming in C for decades and I'd never heard of hcreate. I'm sitting here wondering how the heck did that ever get standardized, allowing single hash table per process. What a bizarre feature.
  - c-cube 6y ago
    I wonder if it's like insanities like SIGPIPE: it's kind of useful if you write IO tools in a few dozen/hundred lines of C. You don't need to carry around explicit context, or check if writes failed, or anything. Of course it sucks for anything else and we still have to deal with SIGPIPE .
beached_whale 6y ago
At least in C++, it’s any integer type that is large enough. uintmax_t/intmax_t are guaranteed to be large enough
scatters 6y ago
It just means that you need to cast via intptr_t, i.e. double casts `(void*)(intptr_t)i` and `(int)(intptr_t)p`. GLib has macros for it if you feel that's useful.
fanf2 6y ago
If you need to round-trip a pointer through an integer and back to the same pointer, you need to use intptr_t or uintptr_t. (Note that this is true for object pointers but not necessarily function pointers. There’s no integer type guaranteed to be big enough for a function pointer.) If you want to round-trip an integer through a pointer and back to the same integer, you can use any integer type provided it is not bigger than intptr_t or uintptr_t.

benhoyt 6y ago

Yeah, I would have liked to avoid it too. But I think you have to allocate with the hcreate/hsearch API (for the "simple" C version). When I roll my own hash table with optimized.c I don't allocate for the integers.

unwind 6y ago
No, you can just jam the integer into the "data" field in the structure and skip that allocation. As I said, and others have commented, it requires some complicated castery to avoid UB, but it's totally doable (and at least GCC does the right thing, while warning, with no advanced casts). Thanks for an interesting article!

chaostheory 6y ago

It would be nice if the post went further as in using code that either uses concurrency or parallelism.

burntsushi 6y ago
Someone on Lobsters suggested this too, and I don't think it would be particularly edifying. But maybe I'm wrong. Someone should go out and do that benchmark. Maybe we'll learn something. Here is what I wrote though: Coming up with a benchmark is hard. Benchmarks like these are models. All models are wrong. But. Some are useful. Follow you thinking to its logical conclusion. If you open up the parallel programming flood gates, now you need to do that for all of the programs. Now your effort to contribute a sample for each language goes up. Maybe enough where actually doing the benchmark isn't practical. So let's play the tape. If someone told me, "sure, have fun, throw threads at this!" I'd probably say, "can I use memory maps?" And let's say, "yes, sure, go for it!" I say okay, here's my first crack at it: 1. Hope stdin is a file and open it as a memory map. 2. Split the memory map slice into N chunks where N is the number of logical CPU cores on the system. 3. Run approximately the same algorithm devised in existing code submissions in N different threads, with one thread per chunk. 4. At the end, join the results and print. If that ends up being the best strategy overall, then your model has become over-complicated because performance now likely depends on step (3). Which is exactly what the existing benchmark is. Now, maybe some languages have a harder time passing data over thread boundaries than others and maybe that impacts things. But that doesn't apply to, say, C, Rust, C++ or Go. If that's not the best strategy, then maybe there is a cleverer approach that involves synchronizing on one shared data structure. I doubt it, but maybe. If so, your benchmark turns into one that is very different. It's no longer just about data transformation, but now you have to worry about synchronization trickiness. And now you're way outside of a standard goroutine pool that you might have used in Go. Building a good benchmark is an art. Sometimes the constraints look dumb and arbitrary. But you have to sit down and really look at it from a bunch of different angles: * Do the constraints approximate some real world conditions? * Do the constraints inhibit writing code that looks like real world code? * Do the constraints inhibit optimizing the crap out of the code? * Do the constraints make the benchmark difficult to create in the first place? * Do the constraints permit easy and clear measurement? There are probably more things that I didn't think about.