Wouldn't the apples-apples comparison be fuzzing a C program? If AFL would catch the same bugs, Rust isn't better than C in this case.
You can find a list of my vobsub bugs in the Rust Fuzz Trophy Case: https://github.com/rust-fuzz/trophy-case They are:
1. The shift overflow: This was harmless in both C and Rust, I believe.
2. The arithmetic overflow: This was a runtime panic in Rust, resulting in a clean crash. In C, this might have been exploitable with a complex enough attack.
3. The three "invalid slice" errors. All of these were clean runtime panics in Rust, and I'm pretty sure that at least two of them would have been exploitable in C with enough work.
So Rust has a couple of advantages here. Out of 5 errors found by the fuzzer, the worst thing that could happen in Rust would have been crashing the program in a controlled fashion. In C, we would have been looking at memory corruption and quite possibly escalation.
Secondly, Rust's runtime checks actually make fuzzers work better. Even simple checks like "is the end index of this slice great >= to the beginning index?" tend to catch problems almost as soon as they occur.
AFL isn't even nearly guaranteed to catch everything, but what it's shown here is that the program contained bugs which would've resulted in an exploitable event in C. The program probably contains more bugs, but following this pattern, it's more likely that they result in panics in most of the worst cases, not exploitable events.
In that sense, fuzzing Rust is more certain to make the bad things actually be caught than with C where there's a chance that the fuzzer developed input that caused UB but the UB didn't happen to be caught by the mechanisms that are supposed to discover bad events during fuzzing.
The thing that really matters is that these errors which the fuzzer found aren't exploitable -- memory errors in rust are guaranteed to panic (unsafe aside) instead of susceptible to overflows, etc. Since fuzzing is very much more of an art than a science, this guarantee is important.
That's an overly glib answer. The fully general form of this problem is undecidable, but it would be theoretically possible to build a "reverse borrow checker" that analyzes a Rust program, detects raw pointers that are provably used exclusively in ways compatible with Rust's lifetime semantics, and converts them to references. But it would probably be a fairly major project requiring lots of specialized knowledge, because lifetime semantics are complicated. Nobody has attempted it yet as far as I know, although the author of Corrode has expressed interest.
You might be able to get it to work sometimes for a very simple subset. I'd be extremely skeptical that it'd be very useful, though.
As part of an incremental re-write or port, this is still useful. It is extremely close to being able to straight-up cross compile CVS, for example.
If a C program works at all, there has to be some computable expression for the length of a C array. Code that uses an array passed as a pointer has to know how big the array is, even though C lacks a language construct for this. The problem is finding that expression. For many cases, it can be automatically inferred, especially if you have cross-module analysis and can see where the original array came from.
I once proposed an extension to C to allow expressing array size information.[1] Discussions indicated it was technically sound but politically too much trouble. It gives a hint, though, of how to approach size information in C. Instead of
int read(int fd, char buf[], size_t len);
int read(int fd, char& buf[len], size_t len);
It doesn't have to be 100% automatic. If the converter could knock off most of the easy cases (especially those involving strings), and accept hints on the hard ones, it could be usable.
[1] http://www.animats.com/papers/languages/safearraysforc43.pdf
With the exception of dynamic memory, virtually all high-level languages that aren't called C/C++ are memory-safe. Memory-safety is not a new feature. Inherent memory-unsafety was a "feature" introduced by C and its immediate ancestors (and later perpetuated by C++) in order to deal with the performance limitations of 8/16-bit architectures and optimizers that were far more limited than they are now.
For many of the older of us – before C/C++ took over much of the world – safe languages were the norm (with the exception of dynamic memory for languages without automatic memory management).
So, in our experience, Rust doesn't really offer us much except an alternative to automatic memory management that imposes a significant cognitive burden. That tradeoff is not always attractive. It presupposes that any and all forms of automatic memory management are not an option. Not a modern incremental, generational garbage collector, not Swift-style ARC (where unnecessary RC updates are optimized away), not some of the various and sundry automatic memory management techniques that researchers have come with over the years (such as MLKit's regions).
If you have this kind of programming background, the tradeoffs that Rust offers are not at all attractive. Not only are the use cases where you need exactly Rust's value proposition relatively rare, the ongoing and often aggressive evangelism sucks up oxygen in the open source commons, so to speak, that could go towards alternative efforts.
That said, plenty of applications can easily afford to pay the runtime cost of a tracing garbage collector and don't need to be using Rust. (You might want to anyway, if you're writing such an application—the language is designed pervasively to eliminate as many sources of program incorrectness as is practical, and this comes through in more areas than just memory safety—but it's not the same kind of critical advantage that memory safety is.) In general I tend to think of Rust as a better replacement for C++, and useful for approximately the same use cases.
I'm not sure how I feel about Swift's ARC; it seems like a bit of a hack compared to Rust's lifetimes and I worry that it makes memory leaks too easy, but I haven't worked with it. I don't think I count techniques that aren't available in any language less obscure than Cyclone.
1. Many embedded applications do not use dynamic memory at all.
2. The runtime cost of a tracing garbage collector is largely a red herring. In a well-designed imperative program, all the cost involved with GC should not typically exceed 10% or so and manual memory management can only avoid part of that. On top of that, Rust's fallback option for shared ownership (Rc<T> and Arc<T>) are very expensive and can be worse than tracing GC. As I noted elsewhere, Rust is a very poor option when you have to deal with shared ownership (such as with persistent data structures).
3. Tracing GC does raise genuine issues in other situations (stack scanning in a multi-language environment, for example), but it's not the only established automatic memory management technique. There's no reason why you can't have a compiler switch to change to a different implementation.
4. Conversely, tracing GC can also have advantages, such as avoiding fragmentation for long-running processes (assuming the GC supports compaction).
> I'm not sure how I feel about Swift's ARC; it seems like a bit of a hack compared to Rust's lifetimes and I worry that it makes memory leaks too easy, but I haven't worked with it.
There's nothing hackish about Swift's ARC. It's basically bog-standard reference counting, which has very well understood semantics, and then the compiler optimizes away reference count updates that aren't needed. The primary downside of the approach is that it can't handle cycles automatically, but then, neither can Rust. Other than that, it ticks off pretty much all the boxes that Rust does.
> I don't think I count techniques that aren't available in any language less obscure than Cyclone.
I'm not sure why, nor why you would tie it to languages. After all, MLKit is Standard ML, hardly a language more obscure than Cyclone; deferred reference counting was first implemented for Java (lots of memory management techniques have actually used Java as a testbed).
> You might want to anyway, if you're writing such an application—the language is designed pervasively to eliminate as many sources of program incorrectness as is practical, and this comes through in more areas than just memory safety—but it's not the same kind of critical advantage that memory safety is.
If you want to go into a more detailed discussion of Rust with respect to software engineering, then we'll also have to discuss the software engineering costs that Rust creates, and that becomes a fairly large topic.
And zero runtime overhead.
> If you have this kind of programming background, the tradeoffs that Rust offers are not at all attractive.
I think you underestimate the attractiveness of zero overhead abstractions.
Please show me an implementation of binary decision diagrams [1] (ideally multi-threaded) where Rust has zero runtime overhead.
Rust has zero runtime overhead only in some cases.
So are you suggesting that claim in such a context is false, citing BDDs as some example, or are you taking my claim to be more broad than the context warrants, and so are arguing a strawman?
And that's what I was referring to. BDDs inherently require Rc<T>/Arc<T> (as long as you want to be memory-safe, at least) and therefore incur significant overhead (reference counting is one of the most expensive forms of automatic memory management). I use BDDs as an example, because there's no way to work around the structural sharing, as it's a requirement for an implementation.
In addition, aiming for zero-cost abstractions is hardly a Rust-only thing. That's more of a Java problem because it only has polymorphic methods and no value types. Outside functional languages, lack of zero-cost abstractions is not a particularly common issue.
And BDDs expose a safe API behind which you can hide the unsafety, so only a fragment of your system would dependent on unsafe Rust.
So we come full circle to your claim that Rust is not "at all attractive", despite being able to express programs more compactly, more elegantly, and more safely than in C/C++, without losing the performance. So I still don't see the case for this claim.
> Outside functional languages, lack of zero-cost abstractions is not a particularly common issue.
Pretty much only Ada and C++ can provide the zero cost abstractions, and they do so only with heavy syntactic and semantic costs (templates for C++, packages and wordy instantiation for Ada). The Rust language does this as part of polymorphic elaboration, which is a natural and compositional language feature, not some ad-hoc secondary language or restricted module system.
I'm frankly finding it hard to believe you think there are serious alternatives. Certainly MLTon if you want the same specialization done, but you then have the unavoidable GC cost, so you're still back to non-zero runtime overhead.
I'm not comparing to C/C++. I'm comparing to other memory-safe languages.
The more general problem is that Rust cannot offer zero-cost abstractions for shared ownership as a result of how it is designed. This is the really killer issue. It's a problem for pretty much any persistent data structure, for example.
> And BDDs expose a safe API behind which you can hide the unsafety, so only a fragment of your system would dependent on unsafe Rust.
The unsafe approach would be to do use an array representation, use indices instead of pointers, and roll your own garbage collector. Or manually remove unnecessary reference count updates whenever you can prove that they are unnecessary. Both of which cannot be easily hidden behind a safe zero-cost API.
> Pretty much only Ada and C++ can provide the zero cost abstractions, and they do so only with heavy syntactic and semantic costs (templates for C++, packages and wordy instantiation for Ada). The Rust language does this as part of polymorphica elaboration, which is a natural and compositional language feature, not some ad-hoc secondary language or restricted module system.
The entire Wirth family of languages qualifies, too. Or Eiffel. Or Fortran. Or Modula-3. As do more recent languages such as Nim and D. Honestly, off the top of my head I can't think of an imperative language with native compilation that doesn't and isn't totally obscure, other than Swift and Go (and even they only some of the time). Note that zero-cost abstractions need to only exist, not that they have to be the only option. Languages can and do provide both expressive constructs that come with overhead and less expressive constructs that are overhead-free. 90:10 rule, premature optimization, and all that.
In addition, parametric polymorphism cannot ever have a zero-cost abstraction (or rather, the term has no meaningful definition in this context), because you pay for it either in runtime overhead (shared generics) or code size (specialization).
I also wouldn't bring up syntactic and semantic costs; that's throwing stones while sitting inside a glass house. Rust is probably one of the worst offenders in this regard.
There are potentially many unsafe approaches, and possibly even some safe ones.
> The entire Wirth family of languages qualifies, too. Or Eiffel [1]. Or Fortran [2]. Or Modula-3 [3]. As do more recent languages such as Nim [4] and D [5].
[1] Doesn't support expressing stack allocation patterns, which are essentially to achieving true zero-cost abstractions.
[2] Oh yeah, that'll be easy and maintainable to program.
[3] Doesn't support 64-bit Windows. Verbose like Ada. Abstraction is weak compared to Rust. Also doesn't support expressing stack allocation.
[4] Nim requires a GC, so not zero cost. It also has surprising runtime semantics. For instance, fields that are are guarded by a clause raise runtime exceptions. These would require different cases which are checked for exhaustiveness statically in Rust.
[5] D is not memory safe for non-trivial programs if you're not using the GC.
Clearly you and I have a different understanding of zero-cost abstraction.
> In addition, parametric polymorphism cannot ever have a zero-cost abstraction (or rather, the term has no meaningful definition in this context), because you pay for it either in runtime overhead (shared generics) or code size (specialization).
Code size is not a problem when discussing zero-cost abstractions. Honestly, it just seems like you're grasping for something to nitpick on.
> I also wouldn't bring up syntactic and semantic costs; that's throwing stones while sitting inside a glass house. Rust is probably one of the worst offenders in this regard.
I have no idea what you're talking about. Once they removed all the special syntax for pointer types years back, Rust is very readable to anyone from a brace-based language tradition.
Says someone that never wrote a single line of Eiffel.
That is what local variables defined as expanded classes are for.
local
array: expanded ARRAY[INTEGER];
do
array := <<1,3,2>>
sorter.sort(array)
....
end
Says someone that never wrote a single line of Modula-3.
TYPE
Time = RECORD
seconds: INTEGER;
milliseconds: [0..999]
END;
PROCEDURE MyProc =
VAR
t: Time; (* Stack Allocated *)
BEGIN
t.seconds := 0;
t.milliseconds := 0
END MyProc;
"Zero-cost abstraction" means "You couldn't have coded it any better yourself." If the problem requires a certain amount of overhead, than an implementation of that solution is considered zero-cost. Rust can't change the laws of math.
Maybe Bjarne should have called it the "Zero additional-cost abstraction" instead; I think it'd clear the principle up a lot.
His contention is that languages with GC don't require reference count updates, and so manipulating the BDD graph is much cheaper in these languages since the resource accounting overhead is deferred by some non-deterministic time.
To be clear, the "contention" is the well-known problem that reference counting (especially atomic reference counting) is one of the most expensive automatic memory management techniques in existence, and it takes pretty significant efforts to get it on par with a modern tracing collector. That's because reference counting has high overhead and poor cache locality (as it comes with a built-in pointer chasing requirement even when you assign a reference).
That the cost is deferred has nothing to do with it.
Second, the reason why I use the BDD example (or, more generally, persistent data structures) is that it's the simplest way for online discussions, because (unlike simpler examples), it's not amenable to pseudo-solutions that don't resolve the underlying problem and that you don't have the space and time for.
The underlying problem is that Rust doesn't really do safe zero-cost abstractions for multiple ownership, and multiple ownership crops up more often in actual Rust code than people like to admit (global caches and memoization often end up with using cloning). You have to deal with it either through Rc<T>, Arc<T>, or cloning, of which cloning is the most common solution, because you don't have the footprints of shared ownership all over your code.
As I said elsewhere, your definition of "zero cost abstractions" differs from what the term means.
> As I said elsewhere, your definition of "zero cost abstractions" differs from what the term means.
I'm going by Stroustrup's definition [1]? If your argument is – I'm not sure here – that "Rust gets zero-cost abstractions by limiting what you can do to beat its normal mechanisms", then that's not terribly convincing. What it boils down to is that multiple ownership is a weak spot of Rust, as for other languages that attempt the compile-time memory management thing, such as ParaSail. TANSTAAFL, "There ain't no such thing as a free lunch." No compile-time mechanism can solve the reachability problem for arbitrary runtime graphs without adding some overhead somewhere. Rust does zero overhead for certain kinds of graphs, but still needs overhead for others.
Yeah Bjane's definition doesn't say "no overhead", it says "no extra overhead." If your data structure requires a GC, then writing a GC for it is a zero-overhead abstraction. What I'm saying is "gotcha, you need some runtime support for this" is not contradictory to zero-cost abstractions.
There are two points to be made here.
1. The problem is not that a data structure needs GC; it's that reference counting (or worse, atomic reference counting) is about the highest-overhead garbage collection in existence. It's popular because it's easy to implement, has mostly predictable performance, and can be implemented as a library without compiler support, but performance is not one of its virtues. The cost really becomes absurd in the `Arc<T>` case, where you have an atomic operation for each reference count update. Nobody actually implements performance-sensitive data structures using naive atomic reference counting outside of C++ and Rust.
2. Persistent data structures (or anything with structural sharing) are, as I mentioned, just the simplest example. They are suitable for illustrating the problems Rust has with shared ownership, but shared ownership is not limited to those. Rust also has problems with shared ownership in a number of other scenarios (such as global caching or any scenario where object lifetime depends on the semantic state of a program).
The underlying problem is that whenever you approximate an undecidable predicate (pointer safety in this case) with a decidable subpredicate, then any zero-cost abstraction claim usually falls flat, because there are typically other decidable subpredicates (not even counting throwing a full theorem prover at the problem) that can handle cases without overhead that your approach can't. In the case of pointer safety, model-checking approaches would be an obvious and well-known example.
Obviously, these alternative approaches may carry different software engineering overhead, but a claim about an abstraction being zero-cost is independent of software engineering costs (not to mention that this is an area where Rust is hardly without its own issues).
You might not want to make that strong assertion without spending some time with the language. Rc/Arc exist or if you want to build a GC into Rust nothing is stopping that. You can break out unsafe and start hacking away, in fact that's what the arena allocator crates do today.
The space where memory and performance matter has very few options, which is why you see those of us who spend time in that area excited about Rust.
You're misreading what I said. I didn't say that Rust doesn't have Rc<T>/Arc<T> (given that I explicitly mentioned it in other comments). My point was that in order for Rust's approach to memory management to be worthwhile, automatic memory management cannot be viable (or you get a much simpler way of ensuring memory safety). Rust also offering a limited form of automatic memory management does not change that.
> The space where memory and performance matter has very few options, which is why you see those of us who spend time in that area excited about Rust.
I did not deny that Rust is an interesting option if automatic memory management is not a viable approach.
I think this is the main niche in which Rust can compete, while of course rust community want to attract people with different backgrounds (eg pythonists, webdevelopers etc).
It's like you say, if I don't need the performance or I am not memory constrained then I will just use GC'd language.
Pony, ATS, Sing#, Spec#, Felix, Gordon, Æminium, DPJ (Deterministic Parallel Java), Kilim, Haller and Odersky. A lot of more linear type languages, like PRFJ or OIGJ. See e.g. http://www.doc.ic.ac.uk/~scd/fast-cheap.pdf
I'm not sure about Factor yet, but it looks good and beats Rust in performance and features also.
D has a lot of great things (I am incredibly jealous of their metaprogramming facilities sometimes), but it doesn't seem like many people are successfully using it in the "fast and SAFE" sense as GP defined it.
Enough to be usable on virtually all platforms that rust is going to target in next 2 years. I hope I'll get proven wrong but that's it for now. And maybe along the time we'll see some decoupling of stdlib from GC too.
OTOH some people like GC too :)
That is already happening. There is no measure, though. How should it be measured?
Related, a few days another blog post in the No-GC series was published: https://dlang.org/blog/2017/07/07/go-your-own-way-part-one-t...
A while back, I ran my subtitle decoder through "cargo fuzz", and I was pleasantly surprised at the results: Close to half a billion fuzz runs found 5 runtime panics, all of which were detected by Rust before they could compromise security. If I'd written this code in C, several of those errors would have been exploitable. I like to think I'm a lot more paranoid than the average programmer. But the MPEG2 format is gnarly and, sooner or later, I'll miss a potential overflow when bit shifting, or get confused following internal "pointers" in a subtitle packet.
Rust has a few advantages for this work:
1. Rust does not require a garbage collector or other specialized runtime. This makes it far easier to pretend to be boring C code. This is a significant advantage over some other excellent languages like Haskell, etc., which require non-trivial runtimes.
2. Rust is very fast by default. For low-level programming, this matters.
3. The Rust infrastructure for testing and fuzzing is surprisingly good and easy to use, which makes it easier to produce bullet-proof libraries.
The downside is that even if you're already familiar with C++, it's probably going to take a couple of weeks to become comfortable with Rust. And if you don't really understand stacks, heaps, memory layout and references, it may take even longer.
I do agree with the underlying thesis: In 15 years, I'll be heartbroken if we're still facing an endless stream of security updates and remote root compromises. But it's going to require literally billions of dollars of programmer time to put a dent in this problem.