Rust Faster Than C? Not So Fast… | Hacker News Reader

Rust Faster Than C? Not So Fast…

dennisforbes.ca

94 pointsendorphone37 comments

One possible implementation of a hash table in Rust possibly beat another possible implementation of a hash table in C? This has little bearing on the overall inherent speed of either language. Conceptually, both languages should tend to perform similarly, as both are systems programming languages that allocate local variables on the stack and have no runtime overhead of a garbage collector. In practice, many real-world programs written in Rust (or C++) may in fact be faster than C equivalents, due to the possibility of inlining type-generic code (via templates in C++, and traits in Rust), whereas in C, generic code is usually implemented with the runtime overhead of void* pointers or function pointers.

In the area of string formatting, templated C++ library should outperform C printf in theory, but this has been difficult to achieve in practice. So I understand why many people are skeptical about your "in practice" claim.

With iostream, yeah - but in general C++ templates give the compiler more opportunity to outperform similar generic C code that relies on void pointers/function pointers. See the classic qsort vs. std::sort archetypal example of this. Also, with printf in particular, modern C compilers will generally parse the format flags at compile time if possible.

On the other hand, Rust's borrow checker eliminates very many correct programs (unless using unsafe code...not sure if that counts or not).

At a macro scale, I have no doubts that Rust's benefits will win out. Understandable abstractions, fearless concurrency, etc. At a micro level, I would be surprised if some ugly, reprehensible C wasn't faster.

I think Rust's approach to systems programming is superior in many ways. I just won't be surprised if it loses a microbenchmark.

> eliminates very many correct programs

While this is also true (there are certainly correct programs that aren't writable in rust without unsafe{}), in this context I'm guessing you mean "incorrect programs".

I mean correct, as in "Rust compile-time checks prohibit creating some compiled programs that would correctly produce the desired result". Rice's theorem means that rustc must fail programs that actually don't have memory errors.

The same is true of C; some ASM programs can't be transcribed in a way that pleases a C compiler.

But it doesn't mean that rustc (or C) will fail to compile all programs, which implement given functionality.

I don't know what downvoters were thinking. So I'll take a blind shot at explaining.

I didn't say that Rice's theorem wasn't true. I said that in this case it doesn't matter. If program fails to compile, you don't give up because of Rice's theorem, you modify program to make it compile.

Will it make program less efficient? Who knows. There's no theorem about that. Most likely it will.

I theory, Rust's type system can provide hints to the optimizer, for example about pointer aliasing. This is currently not leveraged (LLVM isn't too good at this, and rustc internal optimizations on the intermediate language are still on the roadmap).

Any optimization that the Rust compiler might do can very likely be reproduced in C given sufficient time and effort.

I think you have to compare using equal programmer effort if you have two languages that in principle allow you to produce any instruction sequence you like. You don't see performance critical applications (the stuff supercomputers run for example) written in Assembly, even though in theory you might be able to squeeze out a little more performance when Fortran and a good compiler gets you almost as far for much less money.

In small programs like this, it might not even take a lot of effort. It's trivial to read a program like this and make a very good guess as to where bottlenecks are without even running it, let alone profiling it. That kind of simplicity gets lost quickly, however, when programs grow.

Then again, I don't really believe that the optimization opportunities are likely to ever matter much. At least not at this level. Perhaps for much more complicated things, e.g. a kind of compile-time sql or string-matcher the greater safety and the symbolic nature of the macros will let programmers write libraries that practically reason about instructions you give them and choose optimal strategies where C would need to do so at run time or with unmaintainable and unusable macros, but if it's just aliasing and some threading gains - well, those aren't huge often, and where they are, C can use em unsafely too (and that's often quite doable too!).

Safety and maintainability sound like more realistic selling points to me - it may never actually beat C in real-world performance; but it doesn't have to - it just needs to come close.

> in C, generic code is usually implemented with the runtime overhead of void pointers or function pointers.*

When performance really matters, seasoned C programmers more often write task-specific implementations or choose macro-based libraries. In this particular benchmark, the C implementation is using a macro-based hash table which does not have the penalty of void*.

This is what the author changed:

  < #define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)  
  < #define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
  < #define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
  < #define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
  < #define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
  < #define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
  < #define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))
  ---
  > #define __ac_isempty(flag, i) (flag[i]&2)
  > #define __ac_isdel(flag, i) (flag[i]&1)
  > #define __ac_iseither(flag, i) (flag[i]&3)
  > #define __ac_set_isdel_false(flag, i) (flag[i]&=~1)
  > #define __ac_set_isempty_false(flag, i) (flag[i]&=~2)
  > #define __ac_set_isboth_false(flag, i) (flag[i]=0)
  > #define __ac_set_isdel_true(flag, i) (flag[i]|=1)

I don't think anyone on the Rust side is seriously saying that Rust is faster than C and is pointing to the shootout leaderboard as evidence.

This particular example was a bit of a pain point for Rust, because (IIRC) the rules were such that Rust needed to use its default hash function in its hash table, but the C implementation could optimize for the data that the example uses.

> I don't think anyone on the Rust side is seriously saying that Rust is faster than C and is pointing to the shootout leaderboard as evidence.

It's not an argument to be used against Rust; people who understand programming know this already. It's an argument to be used against Rust's fanboys, who are especially numerous for this language.

Since 2007 the name's been the benchmarks game.

Since Sep 10 2016 the Rust k-nucleotide #2 program has been shown using FnvHasher instead of the default hash function.

http://benchmarksgame.alioth.debian.org/u64q/program.php?tes...

I really love what this game accomplishes. I think rust can ultimately be optimized more than c because of the guarantees the language could hand llvm. Right now bugs like https://bugs.llvm.org//show_bug.cgi?id=27860 are preventing this. In the n-body benchmark FORTRAN is winning even with no explicit vector code because of language guarantees like this. I have gotten the rust solution to vectorize some loops but not enough yet.

I think these kind of exercices are essential to show the power of the language. The scope is limited and forces us to look for new ways to solve given problem targeting best performance, because some real life situations, this is what is required and this game helps filter unqualified languages for specific problems. Rust proves itself a real option.

In theory Java can be more optimized than C—machine code generation benefits from knowledge of how the program actually executes. Just let the JIT figure out where you should've used C++ templates instead of dynamic runtime behavior.

In practice, it rarely happens even in micro-benchmarks like these. Though pointer aliasing rules are a special pain point. If you're sure you know what you're doing, restrict exists as a band-aid over this. Yay archaic language baggage!

LLVM's optimizer also doesn't help, as the post mentions—I have real-world code that runs at 1/3rd the speed just from compiling with clang instead of gcc. I love LLVM for what it's let people build on top of it, but it isn't remotely state-of-the-art in this department.

Yes I'm beginning to realize this. The number of tricks I had to use to convince llvm to optimize, when my c++ version just needed __restrict__ was disappointing. Likewise gfortran is way behind ifort.

> In theory Java can be more optimized than C—machine code generation benefits from knowledge of how the program actually executes.

I used to believe this, but I think the same level of theory that says a JIT can be sufficiently smart enough to figure everything out means that a compiler can be sufficiently smart enough to figure everything out as well. This is one of those areas that theory and practice are so far apart that theory should be accompanied with a context of "some day, in the future, if we're lucky..."

What we've seen in reality is that as JIT engines get better, compilers also get better, and retain their lead.

This is true. Compilers even sometimes act vaguely like JIT—see also speculative devirtualization. If your code really needs runtime profiling information to optimize well, we have profile-guided optimization too.

In theory your could still benefit from JIT if, say, you have a Java application that's half written in XML config files and always heavily customized for each deployment. But probably that application also needs 8 modern cores and 16GB RAM to start for reasons that aren't even Java's fault.

But I try not to write code like that.

No, even in theory there's an advantage to having information only available at runtime. Some optimizations depend on the probability distribution of data coming in (eg. an optimization for a CSV parser that makes it faster when dealing with well-formed CSVs that would slow the program down if it starts getting a lot of mis-formatted CSVs). The compiler can choose one or the other, but not both. The JVM can effectively choose both by deciding during execution.

If the compiler is allowed to embed a JIT or other runtime system, then all bets are off.

I'd prefer something that is based on C and C++ than a new language that offers new paradigms but fails to really gain entry because it tries too much to solve some common, difficult, programming problems.

I don't really buy the whole safety issue. Granted, fighting against unsafe programming is hard, but I will always prefer a language that is easy to learn and lets you do mistakes so you can just fix them.

Only we've had what you ask for since the last 40+ years. And it hadn't work out that well, costing billions and untold lost hours and security issues.

Yes. But there's also substantial cost in abandoning existing C/C++ codebases and rewriting them from scratch. Since the advances of C++11, something like SaferCPlusPlus[1] (a memory safe dialect/subset of C++) might be a more practical/expedient way to address memory safety in many cases. An automated conversion (assistance) tool is being worked on, but could use more bodies if anyone's looking for a project to contribute to. :)

[1] shameless plug: https://github.com/duneroadrunner/SaferCPlusPlus-BenchmarksG...

>Yes. But there's also substantial cost in abandoning existing C/C++ codebases and rewriting them from scratch.

Fortunately, we don't have too. We can always a) just write NEW stuff in Rust, or b) just use Rust to extend and piecemeal replace old apps (since it supports linking to C and/or C++ libs).

> or b) just use Rust to extend and piecemeal replace old apps (since it supports linking to C and/or C++ libs).

Yes, Rust's FFI support is nice, but rewriting piecemeal is still rewriting. (And retesting.) It should be faster and easier to just replace unsafe elements in existing code. Of course, that doesn't conflict with choosing Rust for new components and rewrites of existing components when the time and resources are available.

Btw, I haven't investigated lately, what is the state of Rust interoperability with C++ interfaces?

> Btw, I haven't investigated lately, what is the state of Rust interoperability with C++ interfaces?

Not that I'm an expert on the matter, I think it's still through C interop both directions. There was a github project for a Rust module submitted to HN recently[1] to correctly deal with C++ name mangling, and I think it was mentioned that the plan is for it to eventually be used as part of the future C++ interop plans, but I could be misremembering.

1: https://news.ycombinator.com/item?id=13706799

There's also checkedc from Microsoft.

https://github.com/Microsoft/checkedc

Security will always be an issue with computers. You cannot have both security and performance so easily. That's why there are languages like python, C# and java to reduce development costs at the price of performance.

Rust might be safer, but it really lacks entry. If we could just have something a little simpler than C++ and with nicer features than C, it would be great.

If microsoft adopts D, I would be so happy.

Reply on news.ycombinator.com