7 ms·

> Case in point, some are featuring custom hash maps that feature hashing algorithms that, while fast, would never be useful as they provide no protection again

by lossolo 10y ago

> Case in point, some are featuring custom hash maps that feature hashing algorithms that, while fast, would never be useful as they provide no protection against collisions. They are useful in this case, aren't they? Custom hash map implementation can be also useful in other scenarios. This is feature of the language that allow you to do that so it's not "illegal" to use it. If Rust doesn't allow you to do something while other language does, it doesn't mean it should be illegal. I don't see any tricks in Go and it's faster than Rust and more memory efficient in almost half of the benchmarks. So what's your excuse for those cases ?

steveklabnik 10y ago
Rust can do custom hashes as well, to be clear. There's been some arguments over what hashes are allowed in the game in the past.
- fungos 10y ago
  If it compiles and run it is allowed. There is no rule to benchmark other than having the same end result with best performance. I still can't get all the moral over this. The best thing here for Rust would be to achieve the best performance on this game and nothing else. To me this game is important and winning on it is more yet. So, if Rust don't have better result by "morals" this is so wrong that hurts. But each time I read these responses I ask myself if there is not a real problem there. I like Rust, but performance is decisive. It is really sad to see that Rust keeps going down on this game and that makes me question myself when trying to invest time on Rust.
  - sanderjd 10y ago
    It isn't a "moral" issue. It is about the usefulness of the benchmarks. If you're using them to make a recommendation about which programming language to choose, it is important to have a sense for how well the results generalize to the kind of programs you will be writing. Using unrealistic hacks targeted specifically to each benchmark is contra that goal. If, on the other hand, you're just treating the benchmarks as a fun competition akin to code golf, then by all means, hacks ahoy!
    - fungos 10y ago
      Benchmark GAME :)
      - igouy 10y ago
        http://benchmarksgame.alioth.debian.org/sometimes-people-just-make-up-stuff.html#name-game http://benchmarksgame.alioth.debian.org/sometimes-people-jus...
  - steveklabnik 10y ago
    The Benchmarks Game has more rules than that. It's not about "morals."
    - fungos 10y ago
      But people are criticizing C because the way it is implemented is not "realistic". Or that the "hash" is a hack that will never work in real life. I don't know the background of these people, but they couldn't be more wrong. So that looks like "morals" or just they don't ever saw real C code out there.
      - steveklabnik 10y ago
        You're making an assumption that the C code is allowed to have the same algorithm as the Rust code. This is not actually exactly true, based on the rules of the game.
        igouy 10y ago
        Where is it forbidden for programs written in C to use FNV? For example https://github.com/haipome/fnv/blob/master/fnv.c https://github.com/haipome/fnv/blob/master/fnv.c
        steveklabnik 10y ago
        I'm referring to my reply to you above about not being able to implement a different map, not the hash function itself.
        deleted 10y ago
        [deleted]
  - eridius 10y ago
    > The best thing here for Rust would be to achieve the best performance on this game and nothing else. That's absurd. The benchmarks game doesn't measure real-world performance in any sense whatsoever. And many of the implementations are written in ways that you'd never ever put into production code (for example, the laughably bad hashing functions that are mentioned elsewhere in this thread). From what I understand, the Rust implementations tend to not get up to those shenanigans, which makes them appear worse than the implementations from other languages that do. It's not the goal of a programming language to be the top on a silly benchmarks game. The goal is to be an excellent language for real-world use.
- igouy 10y ago
  To be clear: anyone can contribute a Rust k-nucleotide program that uses a custom hash function, just like those used by other programming languages.
  - steveklabnik 10y ago
    Wasn't there some issues around a "custom library" for this? I distinctly remember there being some kind of argument about what is legal and what isn't. That is, I think I'm thinking of this: > k-nucleotide will explicitly require built-in / library HashMap. https://alioth.debian.org/tracker/?func=detail&group_id=100815&aid=315195&atid=413122 https://alioth.debian.org/tracker/?func=detail&group_id=1008... Since C doesn't have a standard library hashmap, you can write an entirely custom one just for the benchmark. But since Rust has a built-in hashmap in the standard library, you cannot. Even though you could write Rust code that's the same as the custom C hashmap.
    - pvg 10y ago
      The rules provided aren't as clear as they could be: http://benchmarksgame.alioth.debian.org/u64q/knucleotide-description.html#knucleotide http://benchmarksgame.alioth.debian.org/u64q/knucleotide-des... But they say 'don't write a custom hash table', not 'don't write a custom hash function'. Maybe the problem is that the data in this benchmark is just not a good way to exercise the hash tables in a given language the way the benchmark intended. That probably means the benchmark should be modified; the complaint that some implementations use 'laughably bad' hash functions that seem to be measurably decent hash functions for the data at hand seems really strange.
    - igouy 10y ago
      To be clear: anyone can contribute a Rust k-nucleotide program that uses a custom hash function, just like those used by other programming languages. > Since C doesn't have a standard library hashmap, you can write an entirely custom one just for the benchmark. NOT TRUE! #315195 states the opposite! "k-nucleotide will explicitly require built-in / library HashMap"
      - 10y ago
richard_todd 10y ago
I have wondered the same for a while now, and I hope someone familiar with Rust can explain it: in many of the benchmarks Go is faster and/or uses less memory despite the GC. Like you, I don't see much trickiness in the Go code.
- dalailambda 10y ago
  In many cases a garbage collected language will be faster when it comes to allocations than using naive allocation strategies (e.g. reallocating a hashmap many times as it grows instead of reserving memory upfront). This is because the garbage collector tends to have preallocated memory lying around, while the RAII needs to call malloc and free every time a heap object is created. Another factor could also be that the GC in the Go examples just never runs since it doesn't allocate enough memory. It's hard to say exactly what's happening without tracing the runtime, which would also affect the benchmarks a bit. It's important to note that while both languages are natively compiled (and I suspect Rust would inch out in that category due to LLVM's backing) most of the overhead would probably be from memory, whether allocations, or cache usage, which makes comparing them in microbenchmarks a little inaccurate.
  - Manishearth 10y ago
    > This is because the garbage collector tends to have preallocated memory lying around, This is an allocator feature independent of garbage collection; jemalloc does this for example. GCd languages have the potential to do this better since they can do additional analysis whilst tracing for little additional cost, but non-GCd languages can still benefit from this.
  - voidlogic 10y ago
    Part of this is also that Go is really good at not allocating from the heap when it can allocate from the stack (escape analysis). Until Go 1.5 the Go garbage collector was pretty weak, but it didn't matter as much as it would have for a language with heavier heap allocation.
anoonmoose 10y ago
I believe that what your OP mmstick might have been saying is that the hashing algorithm used in the C version of the algorithm might be very different from the hashing algorithm in the Rust version, and this difference might be significant. I don't speak Rust, so I can't quite tell what's going on here: http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=rust&id=2 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... But the C hash function is very simple, and probably not at all collision-resistant: #define CUSTOM_HASH_FUNCTION(key) (khint32_t)((key) ^ (key)>>7) Again, I don't speak Rust so hopefully someone can comment on this, but I don't see that same simple hash is being used in the Rust...I think it might be using a default hash function, which would probably be more collision resistant. I am sure that the Rust could be made to do the same thing, but I am not sure that, as-is, this is an apples to apples comparison.
- Manishearth 10y ago
  llogiq wrote a post about this: https://llogiq.github.io/2016/12/08/hash.html https://llogiq.github.io/2016/12/08/hash.html

by lossolo 10y ago

steveklabnik 10y ago

Rust can do custom hashes as well, to be clear. There's been some arguments over what hashes are allowed in the game in the past.

fungos 10y ago
If it compiles and run it is allowed. There is no rule to benchmark other than having the same end result with best performance. I still can't get all the moral over this. The best thing here for Rust would be to achieve the best performance on this game and nothing else. To me this game is important and winning on it is more yet. So, if Rust don't have better result by "morals" this is so wrong that hurts. But each time I read these responses I ask myself if there is not a real problem there. I like Rust, but performance is decisive. It is really sad to see that Rust keeps going down on this game and that makes me question myself when trying to invest time on Rust.
- sanderjd 10y ago
  It isn't a "moral" issue. It is about the usefulness of the benchmarks. If you're using them to make a recommendation about which programming language to choose, it is important to have a sense for how well the results generalize to the kind of programs you will be writing. Using unrealistic hacks targeted specifically to each benchmark is contra that goal. If, on the other hand, you're just treating the benchmarks as a fun competition akin to code golf, then by all means, hacks ahoy!
  - fungos 10y ago
    Benchmark GAME :)
    - igouy 10y ago
      http://benchmarksgame.alioth.debian.org/sometimes-people-just-make-up-stuff.html#name-game http://benchmarksgame.alioth.debian.org/sometimes-people-jus...
- steveklabnik 10y ago
  The Benchmarks Game has more rules than that. It's not about "morals."
  - fungos 10y ago
    But people are criticizing C because the way it is implemented is not "realistic". Or that the "hash" is a hack that will never work in real life. I don't know the background of these people, but they couldn't be more wrong. So that looks like "morals" or just they don't ever saw real C code out there.
    - steveklabnik 10y ago
      You're making an assumption that the C code is allowed to have the same algorithm as the Rust code. This is not actually exactly true, based on the rules of the game.
      - igouy 10y ago
        Where is it forbidden for programs written in C to use FNV? For example https://github.com/haipome/fnv/blob/master/fnv.c https://github.com/haipome/fnv/blob/master/fnv.c
        steveklabnik 10y ago
        I'm referring to my reply to you above about not being able to implement a different map, not the hash function itself.
        deleted 10y ago
        [deleted]
- eridius 10y ago
  > The best thing here for Rust would be to achieve the best performance on this game and nothing else. That's absurd. The benchmarks game doesn't measure real-world performance in any sense whatsoever. And many of the implementations are written in ways that you'd never ever put into production code (for example, the laughably bad hashing functions that are mentioned elsewhere in this thread). From what I understand, the Rust implementations tend to not get up to those shenanigans, which makes them appear worse than the implementations from other languages that do. It's not the goal of a programming language to be the top on a silly benchmarks game. The goal is to be an excellent language for real-world use.
igouy 10y ago
To be clear: anyone can contribute a Rust k-nucleotide program that uses a custom hash function, just like those used by other programming languages.
- steveklabnik 10y ago
  Wasn't there some issues around a "custom library" for this? I distinctly remember there being some kind of argument about what is legal and what isn't. That is, I think I'm thinking of this: > k-nucleotide will explicitly require built-in / library HashMap. https://alioth.debian.org/tracker/?func=detail&group_id=100815&aid=315195&atid=413122 https://alioth.debian.org/tracker/?func=detail&group_id=1008... Since C doesn't have a standard library hashmap, you can write an entirely custom one just for the benchmark. But since Rust has a built-in hashmap in the standard library, you cannot. Even though you could write Rust code that's the same as the custom C hashmap.
  - pvg 10y ago
    The rules provided aren't as clear as they could be: http://benchmarksgame.alioth.debian.org/u64q/knucleotide-description.html#knucleotide http://benchmarksgame.alioth.debian.org/u64q/knucleotide-des... But they say 'don't write a custom hash table', not 'don't write a custom hash function'. Maybe the problem is that the data in this benchmark is just not a good way to exercise the hash tables in a given language the way the benchmark intended. That probably means the benchmark should be modified; the complaint that some implementations use 'laughably bad' hash functions that seem to be measurably decent hash functions for the data at hand seems really strange.
  - igouy 10y ago
    To be clear: anyone can contribute a Rust k-nucleotide program that uses a custom hash function, just like those used by other programming languages. > Since C doesn't have a standard library hashmap, you can write an entirely custom one just for the benchmark. NOT TRUE! #315195 states the opposite! "k-nucleotide will explicitly require built-in / library HashMap"
    - 10y ago

richard_todd 10y ago

I have wondered the same for a while now, and I hope someone familiar with Rust can explain it: in many of the benchmarks Go is faster and/or uses less memory despite the GC. Like you, I don't see much trickiness in the Go code.

dalailambda 10y ago
In many cases a garbage collected language will be faster when it comes to allocations than using naive allocation strategies (e.g. reallocating a hashmap many times as it grows instead of reserving memory upfront). This is because the garbage collector tends to have preallocated memory lying around, while the RAII needs to call malloc and free every time a heap object is created. Another factor could also be that the GC in the Go examples just never runs since it doesn't allocate enough memory. It's hard to say exactly what's happening without tracing the runtime, which would also affect the benchmarks a bit. It's important to note that while both languages are natively compiled (and I suspect Rust would inch out in that category due to LLVM's backing) most of the overhead would probably be from memory, whether allocations, or cache usage, which makes comparing them in microbenchmarks a little inaccurate.
- Manishearth 10y ago
  > This is because the garbage collector tends to have preallocated memory lying around, This is an allocator feature independent of garbage collection; jemalloc does this for example. GCd languages have the potential to do this better since they can do additional analysis whilst tracing for little additional cost, but non-GCd languages can still benefit from this.
- voidlogic 10y ago
  Part of this is also that Go is really good at not allocating from the heap when it can allocate from the stack (escape analysis). Until Go 1.5 the Go garbage collector was pretty weak, but it didn't matter as much as it would have for a language with heavier heap allocation.

anoonmoose 10y ago

I believe that what your OP mmstick might have been saying is that the hashing algorithm used in the C version of the algorithm might be very different from the hashing algorithm in the Rust version, and this difference might be significant. I don't speak Rust, so I can't quite tell what's going on here: http://benchmarksgame.alioth.debian.org/u64q/program.php?test=knucleotide&lang=rust&id=2 http://benchmarksgame.alioth.debian.org/u64q/program.php?tes... But the C hash function is very simple, and probably not at all collision-resistant: #define CUSTOM_HASH_FUNCTION(key) (khint32_t)((key) ^ (key)>>7) Again, I don't speak Rust so hopefully someone can comment on this, but I don't see that same simple hash is being used in the Rust...I think it might be using a default hash function, which would probably be more collision resistant. I am sure that the Rust could be made to do the same thing, but I am not sure that, as-is, this is an apples to apples comparison.

Manishearth 10y ago
llogiq wrote a post about this: https://llogiq.github.io/2016/12/08/hash.html https://llogiq.github.io/2016/12/08/hash.html