Hacker News Reader

Comment by volta83 | Hacker News Reader

> Given that DEC Alpha famously had difficulty with RCU, it is only reasonable to ask how Rust will do with it.

> Including some wild speculation about how Rust's ownership model might be generalized

I recommend starting with the latests post in the series and the conclusions(https://paulmck.livejournal.com/64209.html and https://paulmck.livejournal.com/65056.html).

From the snippets at the beginning, it looks like the author documented how they started learning about how to solve these problems in Rust, and it does not take too long until the comment section starts pointing the author at crossbeam-rs, GhostCell, etc. which only start appearing in the series in the last couple of sections.

Learning Rust by implementing a linked-list is pretty hard, but "Learning Rust by implementing RCU" has to be, by far, the hardest way to learn Rust that I know of. Kudos to the author for pushing through this so quickly and thoroguly. The posts are all excellent.

I wish the author would go a little bit more into crossbeam-rs. One thing the author does not consider, is that a safe Rust interface to RCU is essentially a "proof of correctness" for RCU, i.e., it proves that using RCU via that interface cannot introduce undefined behavior. (Or maybe more technically, the contracts on the correctness of unsafe code within the safe wrapper provide a potentially incorrect "proof" of this).

AFAIK no such correctness proof for the C APIs exists (there are a couple of linters that catch some issues, but there is no proof that say that if you stick by those warnings your code is UB free).

The author seems to be assuming that the C APIs to RCU have been proved correct, which AFAIK is incorrect, and by ignoring the safe Rust APIs to RCU, the author is missing out on potentially finding issues on the correctness of the C APIs that Rust would discover.

Basically, the question: "Can we expose Linux RCU apis to Rust?" is definetly worth asking, but the question "Can Rust prove Linux RCU APIs correct?" is much more interesting. If it can't, then why not? The fact that we have such proofs for other RCU and hazard pointers APIs in Rust shows that this is at least possible in general. And if Linux RCU can't be exposed in safe Rust, precisely understanding why would definitely be illuminating (Can Linux RCU be proven correct outside Rust, but not in Rust? Or maybe does Linux RCU APIs can actually be proven incorrect by Rust?).

View on HN

> that a safe Rust interface to RCU is essentially a "proof of correctness" for RCU, i.e., it proves that using RCU via that interface cannot introduce undefined behavior. (Or maybe more technically, the contracts on the correctness of unsafe code within the safe wrapper provide a potentially incorrect "proof" of this).

Adding an unsafe block around a call to C code doesn't prove anything. Rust does not provide proofs of the code you write in it, except if you do not use unsafe at all.

RCU is an API and a general technique. It can be implemented a ton of different ways (including, as the author noted, as a single instruction if Linux is built with pre-emption disabled). You must not conflate the the soundness of an API with the soundness of its implementation. 'Can Rust prove Linux RCU APIs correct?' is nearly completely without meaning.

A similarly meaningless project would be to prove that the idea of malloc/free is correct. There's nothing that could even be incorrect or correct about it, and you don't need Rust wrappers to tell you that. Now prove glibc's malloc is correct; very different question.

> Adding an unsafe block around a call to C code doesn't prove anything.

I didn't say otherwise.

What I said is that writing unsafe code is writing a proof that the code is correct.

If the proof is incorrect, the behavior is undefined, and Rust makes no guarantees.

unsafe literally means "I've proven this code correct".

As mentioned, most uses of unsafe in the standard library are accompanied by a comment that documents the proof.

`unsafe { ... }` means "I hope you are convinced by my arguments in the surrounding comments, or better still in my POPL21 paper, that this is correct". Other than that, not much. The keyword itself has essentially zero relationship with the existence of a formal proof. You are talking about proof in a very loose sense.

The narrower point I think you're making is that hopefully attempting to create a safe API around the RCU pattern makes someone think about RCU's correctness even harder. I'm not sure it will produce much, given how much attention RCU has already received in the past 20 years. Any innovation you get from that process will probably be concentrated in describing/encoding the ownership pattern in Rust terms, since that's non-obvious. But the epoch GC implemented in Crossbeam is pretty similar overall to RCU, so it has much to build on in that regard.

> `unsafe { ... }` means "I hope you are convinced by my arguments in the surrounding comments, or better still in my POPL21 paper, that this is correct".

I disagree here (and that's ok).

The unsafe keyword tells Rust "this code is sound", i.e., there exist no program execution for which this code will cause safe Rust to exhibit undefined behavior.

Rust will parse it, type check it, compile it, link it, etc. "as-if" it was sound.

And Rust only makes any guarantees about what your program does if the unsafe code was actually sound.

From the point of view of the compiler, the unsafe block itself is a user-provided proof that whatever that code does is sound.

If you write: unsafe { *ptr } that's a proof that dereferencing the pointer is sound, therefore the pointer is non-null, it points to an aligned allocation able to hold a type, the value at that memory location is a value of that type (i.e. the pointer is dereferenceable), etc.

The Rust compiler accepts your proof and generates code as if your proof is correct. In particular, it will compile code around that code under that assumption, it will eliminate null pointer checks after that code, etc.

If the proof that an unsafe block provides is incorrect, then the behavior is undefined, and Rust makes no guarantees.

I agree with you that given some unsafe code, actually proving it correct is not something that the compiler does, and that creating a tool that does this is hard. If it were easy, the compiler would already do it, and we wouldn't need unsafe at all.

Unsafe exists because there are things that the compiler can't prove correct, and this escape hatch allows the user to provide a proof that the compiler can integrate into how it compiles the program.

There is a whole repository of Iris proofs for unsafe blocks in the Rust standard library, for which we have formal proofs. But these are not integrated in any way with the Rust code one writes. They have been written by humans aiming to get a confirmation that the proof expressed by the unsafe blocks are indeed correct. Some were not, and had to be fixed, and pretty much every fix has generated a paper.

> I agree [...] actually proving it correct is not something that the compiler does

Yes. Unsafe blocks are bare assertions, no more. Everything you described about what happens in Rustc when you use it is better described as making a bare assertion to the compiler. Everything beyond that is socially constructed. Saying it's a proof sounds even more silly when you recall that Rust programmers treat it as quite the opposite -- radioactive markers of places where the program might cause UB.

You were trying to characterise it as a proof because you're claiming that "Can Rust prove Linux RCU APIs correct?" is an interesting question. But you are actually asking "Will Rust compile RCU code if we assert to it that using the RCU API is safe?", and the answer is unconditionally yes. It is not an interesting question at all. Your misuse of the word proof led you there, so I am suggesting you stop calling the unsafe keyword a proof.

In the broader scheme of things, yes, the way in which Rust encourages you to isolate unsafety is helpful, and so if you wanted something formally verified Rust is a good language for that. That doesn't really translate to RCU, because the hypothetical Rust API would not be an implementation of RCU. All the Iris proofs that have come out of the RustBelt project are bad examples here, because they were actual implementations of things, not APIs around black box implementations that change under your feet when you set kconfigs.

As a final thought, here is a supposedly safe-encapsulated Rust API for RCU, I would invite anyone to suggest how writing down this very simple API or similar + a few calls to extern "C" wrappers for the RCU macros could possibly help "prove Linux RCU APIs correct", whatever that means: https://docs.rs/rcu-clean/0.1.6/rcu_clean/struct.ArcRcu.html

(Little edit: if you're interested in what circumstances will lead Rust wrappers of C code to elucidate safety, look into rlua, a project to create a safe wrapper for Lua (https://github.com/amethyst/rlua). Arguably the main outcome is that we now know that the Lua API cannot be wrapped safely with zero cost, in no small part due to the use of longjmp. Some of RCU's APIs require you do not sleep or block in any way while using it, lest you wake up with the GC train having left the station. For this reason I imagine you won't be able to encode all the usage requirements in the Rust type system, let alone make an actual safe zero-cost API, let alone turn that into a proof of anything.)

I think you are not using 'proof' in the way that most people would understand it. A proof is usually considered a series of steps someone can take to verify that something is true themselves (i.e. there is no need to trust whoever produced the proof is malicious or mistaken about what they are trying to prove, if you can follow the proof you can see for yourself). Proving something to a compiler therefore is generally understood to mean giving something to the compiler which it actually checks it sound (even if it could not produce the proof on its own). This is effectively how type-checking and borrow checking works (your program is a kind of proof the compiler verifies). 'unsafe' in this case is not a proof, it is more like a promise (not in the async sense) or assertion (not in the debug sense). The compiler trusts that you have not made a mistake, it does not have any way to verify that you haven't. You may have a proof to the person reading the code that there is no mistake (or you may not, either because your proof is incorrect or the person cannot understand the proof), but it is not a proof to the compiler.

(In fact, there was much bikeshedding at one point about renaming the 'unsafe' keyword to make this explicit: suggestioned included 'assumed_safe', 'trustme', 'trusted', as well as less serious ones like 'yolo' and 'hold_my_beer_and_watch_this': https://github.com/rust-lang/rfcs/pull/117)

> I think you are not using 'proof' in the way that most people would understand it.

I have corrected many math exams of students over the years.

A "significant" amount of the "proofs" provided by the students in those exams were wrong in one way or another.

Many students continued the exams under the assumption that what they just incorrectly proved, was actually correct.

They had no way to verify whether they proofs were correct or not. No theorem provers were allowed in the exam.

Yet all of them called what they wrote "a proof".

---

This is pretty similar to how Rust works.

Without unsafe, Rust proves your programs sound for you.

Unsafe let's you supply your own soundness proofs for parts of the program that the compiler does not know how to prove (or disprove).

If the proofs are not correct, RUst makes no guarantees.

The claim that because "Rust does not prove these for you, they are not proofs" is unfair.

That's like claiming that any "proof" that has not been proved in a theorem prover does not deserve to be called "a proof".

I respect your way to see this. I just don't see it this way.

What makes you think this kind of proof work hasn’t already been done for this core C code in the kernel?

I've look at the literature every couple of years, and to the best of my knowledge, there is no paper proving that a subset of the Linux kernel RCU apis are sound.

If you are aware of one, I am intrinsically interested in this topic.

Note: If someone wants to learn Rust by implementing linked lists, then https://rust-unofficial.github.io/too-many-lists/ is a must-read :)

Arguably, that's just too hardcore.

You can implement doubly-linked lists in safe Rust by using Rc and Weak, Option, and RefCell (or Arc and Mutex for a safe concurrent doubly-linked list).

Learning about safe Rust is gentler and more useful for a beginner, than starting to learn Rust by learning about "unsafe code".

You have to know what safe Rust allows so that you can appropriately know to which contract unsafe Rust must adhere to.

> You can implement doubly-linked lists in safe Rust by using Rc and Weak, Option, and RefCell (or Arc and Mutex for a safe concurrent doubly-linked list).

You can, but not without introducing runtime overhead relative to C and C++, e.g., by forcing reference-counting where none would be necessary in C.

Rust's safety checks do in fact block some safe and zero-overhead abstractions familiar to people working in C and C++, and denying that isn't helpful. Stating that these techniques can be implemented in Rust with overhead is missing the point.

Arguing that the added overhead is "minimal" (which is a meaningless word, since the word "minimal" just means "I don't care about your scenario") is still missing the point: it's overhead that's not present in unsafe languages.

The reason people use languages like C++ and Rust is to get zero cost abstractions and explicit control over the machine. If you want good performance but don't care about precise control over the machine, write Java or C# or something high level like that. You'll be just as safe as you would be in Rust and more productive.

I'm really tired of this motte and bailey stuff. Rust proponents say Rust gives you fine grained machine control and safety with no performance compromises, and then when you point out that the language doesn't quite live up to that promise, Rust proponents start telling you that you didn't really need that performance anyway. This argumentative tic is annoying.

> You can, but not without introducing runtime overhead relative to C and C++, e.g., by forcing reference-counting where none would be necessary in C.

The runtime overhead is minimal. 96% of it comes from the pointer indirection in the linked list, and this you have either way.

Last time I benchmarked, the checks made the list 4% slower, which is acceptable for many, since doubly-linked lists are already very slow.

This 4% is buying you a correctness proof that your list API cannot introduce undefined behavior. If you write this doubly-linked list abstraction in safe Rust, and make a mistake, the resulting code will still not have undefined behavior.

C and C++, even paying this 4% performance cost, do not provide this guarantee, which is valuable to many.

Unsafe code that removes this 4% runtime overhead is an optimization.

The fact that you can remove this overhead by providing a safe wrapper over unsafe code is a selling point of Rust, but learning how to write such optimized code without learning first what it takes to make it correct IMO completely misses the point of Rust.

It is very easy to write broken safe Rust abstractions over broken unsafe code. At that point, you are in a worse place than C or C++, since you are paying many costs for introducing Rust in a project, but leaving the most valuable feature off the table (correctness, lack of segfaults, lack of data-races, etc.).

Reference counting also adds per-element space overhead.

Also linked lists are often [1] used in C and C++ for intrusive chaining of nodes otherwise owned by other data structures and the reference counting would either impose overhead to those other datastrucutres or be pointless.

[1] In fact I would say this is very common at least in C++ as linked lists make otherwise very poor datastructures by themselves.

I know. So? How does that change anything?

A doubly-linked list is already space inefficient, it adds 2 pointers per element.

Using Rc + Weak adds one extra word per element to store the two (strong and weak) refcounts. So for a 64-bit type, a Vec takes 1x space 1xN, a list takes 3xN, and a ref-counted list 4xN.

Performance wise, the extra space doesn't change anything, since that word is allocated with the element in the same cache line and would have been read anyways (even if you don't access it, the hardware does access it).

If you are using a doubly-linked list, you really don't care that much about any of this, and the only thing that makes a real difference, is the guarantee that your list implementation is correct.

The additional refcount takes space that could be used for the payload that now either needs to spill into the next cacheline or needs to be compressed further.

You can still use double linked lists in high performance code, as long as the list traversal doesn't happen on the critical path (or at all).

If you are concerned about high performance/space overhead/cache awareness you wouldn't want to use a linked list in the first place, instead you'd use an arena.

An arena is not a replacement for linked lists. In some cases you can use it as a replacement, but in many cases you can't. So can the idiomatic rust apologists please stop with this? I know you love it the language and wants more people to use it, but these sort of statements doesn't help your case.

"Performance is almost the same in real world cases"

"You don't really need that data structure anyway"

"You can learn how to optimize code later"

People come and want to use Rust for some fast code. They know what they want the code to do and want it to be as fast as the code they wrote before, and see how Rust would help them achieve that. The above statements are then wrong or patronizing or completely misses the point.

Linked lists are not good for cache locality, it has nothing to do with the language. It'd be my advice over linked lists even if you were doing it in C. Rust does make doubly linked lists in safe code without reference counting impossible, but I don't the argument that you'd use one due to performance or memory overhead.

> Linked lists are not good for cache locality

That doesn't matter if a solution with good cache locality doesn't exist for your problem.

They are not, that's why you would use a flat layout for your primary iteration order. But for any secondary ordering/indexing you might need, if you also need fast insert/removal, chaining in a list can be an option.

The question is fair.

Why would you want to use a non-intrusive doubly-linked list?

AFAIK there is only one answer: you have very big objects and you need O(1) splice.

If you don't have very big objects, or you don't need O(1), pretty much any other data-structure in existence is going to give you much much better performance than a doubly-linked list.

For the only use case for which non-intrusive doubly-linked lists are good at, however, there exists no hardware you can buy for which you can measure a performance difference between ref-counting and not ref-counting.

This has nothing to do with Rust. The same applies to C++, or Java, or Python, or even C. You can do ref counting on any language, and all these languages run pretty much everywhere.

The only thing that Rust gives you over Java, Python, or C here is the possibility to implement a doubly-linked list in safe Rust that will perform the same but that the compiler will prove for you to be memory and thread safe.

Sure, Rust also allows you to use unsafe code, and then prove that safe and create a safe wrapper. It even does this for you and provides this in std::List. But what value does this add? It's more work, and it doesn't perform better, and why a significant number of people have argued in the past that adding std::List was a mistake in one form or another.

> Why would you want to use a non-intrusive doubly-linked list?

Or you have a list of objects with many references to parts inside the list and you want to rearrange those parts from those references at O(1) speed.

Lets say I have pointers two elements A and B in the list. I now want to say that B should come after A, I can do this easily in O(1) time with this with no overhead and all references sees this update instantly. Lets say I put integers in these so the data is embedded in the list. You have many other places referring to elements inside the list and you want those references to track the objects position.

How would you solve this using a Rust compatible data structure?

> The question is fair.

No it is not. Experienced people almost surely knows their use case better than you do.

> there exists no hardware you can buy for which you can measure a performance difference between ref-counting and not ref-counting.

Are you kidding me? Seriously, I don't see how you could believe this unless you never tried to use ref counting to replace other code and compare the performance difference.

> Lets say I have pointers two elements A and B in the list. I now want to say that B should come after A, I can do this easily in O(1) time with this with no overhead and all references sees this update instantly.

You can do this with a vector of pointers as well, at lower space complexity cost (1 pointer per element instead of two), and a lower runtime cost (1 swap of two pointers instead of swapping 4 pointers).

Such a data-structure has also other advantages, like higher cache efficiency, etc.

You can't move an element in a vector in O(1) time. Swapping isn't the same as moving, you'd have to move n elements to make room for the new one.

You mentioned changing the order of two elements in a list, such that one comes after the other.

With a vector of pointers to the elements (C++ std::vector<T*>) this can be easily done in O(1) as I explained above.

If now that I've proven you wrong, you want to change the problem to something else, feel free to state your new problem, and I'll proceed to prove you wrong again.

> You mentioned changing the order of two elements in a list, such that one comes after the other.

Putting B after A is not swapping them, it is putting the element B so it is right after A. You could technically interpret it as you did, but only a contrarian would do that. If you want more people to support rust then you should stop being a contrarian. If you want me and others to assume that the Rust community is full of hard to work with people then please continue, but that wont make people more likely to pick up rust.

If instead of behaving like you do here people would just say "Sure thing, in order to get that performance in rust you just do X and Y!" I bet people would be way more supportive of rust. But if working in the language means that people like you will come and argue like this then why not just write a C library, and then someone will write a Rust wrapper and people are happy? While if they'd write it in unsafe Rust people would come and complain like hell.

> You could technically interpret it as you did, but only a contrarian would do that.

Or you could have been more clearer.

I didn't intend any animosity, but you clearly do.

> If you want more people to support rust

I don't care whether more people support Rust or not. I am just fighting the spectacular amount of disinformation in this thread by malicious actors that have never used Rust.

> Putting B after A is not swapping them, it is putting the element B so it is right after A.

Then you should have written that instead. Take the pointer in the vector right after A, and swap it with B. That way, A is now right before B, and B is now right after A.

> Take the pointer in the vector right after A, and swap it with B. That way, A is now right before B, and B is now right after A.

This is a joke, right? I don't see how it can't be.

But in case it isn't, in almost all problems like this it is assumed that you don't want to change the order of the other elements.

For example, if you wrote a function MoveToDirectlyAfter(a, b), and it did move elements other than a or b people would say that your function contains bugs or that it doesn't do what it says.

In a real life system what is the usual use case for this?

Let's say a user reorders documents with drag and drop. What's the low-level equivalent? Could you help me come up with an algorithm that depends on this?

If write speed is important, I'd just use an in-memory LevelDB-like thing (so a log structured merge tree).

If the data is not much, then I'd optimize for code simplicity.

Before I delve more, are you talking about `rotate` ?

https://en.cppreference.com/w/cpp/algorithm/rotate

Is that what you want?

The objects don't have to be big. They have to be expensive to copy. These are related but not always identical. Objects that refer to things in the real world (or in a complex model) can be either actually non-copyable or just hard to copy.

> The above statements are then wrong or patronizing or completely misses the point.

I think more what's more going on is that longtime Rust programmers can get frustrated by the sheer volume of people who have never used Rust but dismiss it because they hypothesize that they will need to regularly write things like linked lists in Rust just because they are the easiest data structure to write in C.

When in reality let alone the amount of high performance data structures in the standard library and crate ecosystem mean it's extremely unlikely they'll even feel to write any data structures in the first place. Programming Rust and C or C++ is a very different experience in numerous ways and it is unproductive to expect that not to be the case.

But C++ programmers have ergonomic vectors in the standard library. There is no reason to implement data structures there unless you need them for performance reasons.

And correct use of linked lists is not uncommon at all. Binary trees are linked lists for example, would you implement binary trees as a vector pointing to vectors rather than a linked list containing pointers to similar linked lists?

Yes, I would avoid implementing my own binary tree using linked lists (unless it was just an educational exercise). But also yes, if I did decide that I had a production use case for creating my own binary tree implementation, I would be very likely to look for approaches that use contiguous rather than linked data structures.

I think this perspective you're espousing is "sometimes you just want to knock out a simple bespoke binary tree implementation", but I just don't think that use case makes sense. Either you want to use one from a good library or you have a really good reason to roll your own and it is worth the effort to do it well.

> I think this perspective you're espousing is "sometimes you just want to knock out a simple bespoke binary tree implementation", but I just don't think that use case makes sense. Either you want to use one from a good library or you have a really good reason to roll your own and it is worth the effort to do it well.

There is no library for generic tree data structures, you have to implement those yourself. There are libraries implementing a table interface using ordered binary trees but that is just one of many use cases.

Coincidentally I was just watching this talk from Bryan Cantrill: https://youtu.be/vvZA9n3e5pc. Around the 58 minute mark he shares an anecdote that is relevant to this thread. It boils down to him doing something where he would have written a simple bespoke balanced binary tree in C, but when writing a reimplementation in Rust used a "naive" library approach and was surprised to see a 35% speedup, which boiled down to the library using a btree instead of a balanced binary tree.

This doesn't invalidate your point about there being use cases for binary trees that may necessitate you to write your own, I take you at your word that you've often had strong use cases for this, but I do think it illustrates something I believe to be true, which is that people reach for linked data structures too often, when contiguous ones are a better default.

No, I probably would use the BTreeMap in std instead, assuming I want a search tree. Which is even better, because the primary reason you use binary trees in C is that they are easy to make intrusive. But if I want a priority queue instead there's also BinaryHeap. If I wanted to store data on the branch nodes I might use intrusive_collections. Or maybe if I was dealing with a more complex graph I'd pull in a library like petgraph. If all that fails I could still arena-allocate the nodes to get around the lifetime issues. If I really absolutely wanted to, which I don't see happening any time soon, personally. I'd need a more concrete example there.

I said binary tree, not "Map interface implemented using an ordered binary tree". They are not the same thing.

I am aware, as you might be able to gather by reading past the first sentence of my comment. Of course if you'd just said what you needed the binary tree for, I could have given you a better answer.

If you don't have a use case in mind, I'd suggest just trying to actually use Rust for something instead of spending time trying to construct problems where Rust would be bad at the solution.

You can't even explain how doing something as simple as a binary tree with parent pointer is possible in rust, so my assumption is that it isn't possible and I'd have to make work arounds. I can make work arounds just fine in C++, you don't have to teach me those, but I don't see why I'd learn a language where I'd be forced to make those work arounds rather than use the version that fits my problem best.

It might be possible that you can write nice versions etc, if so I'd like to see them, but it seems everyone is hell bent on just saying "You shouldn't do it!".

> You can't even explain how doing something as simple as a binary tree with parent pointer is possible in rust, so my assumption is that it isn't possible

A beginner learns this in the first week:

    struct Node<'a, 'b> {
        left: Option<&'a Node>,
        right: Option<&'b Node>
    }

Many people don't know how to read or write, but you don't hear them every day claiming that "therefore it must be impossible", yet here we are.

> but I don't see why I'd learn a language where I'd be forced to make those work arounds rather than use the version that fits my problem best.

> but it seems everyone is hell bent on just saying "You shouldn't do it!".

The claim was and still is "there are infinitely more effective - as in faster - ways to learn Rust than by starting with how to write doubly-linked lists".

This whole thread is you failing at 3rd grader logic hard and concluding:

- therefore it is impossible to write doubly-linked lists in Rust

- therefore doubly-linked list in Rust are efficient

- therefore it is impossible to learn Rust

- ...and many other things...

I've taught Rust to a 9th year old, but I don't think I could have taught Rust to a 2 year old, so arguably, I think you are right, in that probably _FOR YOU_ it is impossible to learn Rust, you wouldn't be able to grok how to write doubly-linked lists in Rust properly, you wouldn't be able to master Rust to write efficient code in it, etc.

That's ok, don't be frustrated by it, everybody is different.

Just try to stop projecting your limitations to other people. Particularly in this forum, or when talking with Linux kernel developers, were most people are smart experienced programmers that would learn Rust well in a day and master it in a week.

> The additional refcount takes space that could be used for the payload that now either needs to spill into the next cacheline or needs to be compressed further.

It could, but since the cachelines are adjacents the prefetcher will pull subsequent cache lines anyways, and since the objects typically used in doubly-linked lists are very large (much larger than 64-bit), then this doesn't matter on any practical application that I am aware of. Our results of 4% performance increase is for the worst-case that we found. Usually is 1% or less.

If you have a real-world benchmark that shows otherwise, can you please share it?

AFAIK there does not exist any hardware for which the performance model for:

- non-intrusive doubly-linked lists,

- typical object sizes used on these lists (>> 64-bit)

- typical operations done on these lists (splice, etc.)

would predict a performance difference, and in our case, having replaced unsafe lists with safe list in many large applications, we never were able to measure a difference in application performance, only in the synthetic worst-case micro-benchmarks.

So I am truly interested to learn about your use case.

You're ignoring the case of a list being densely packed and embedded inside another data structure. If you bloat a data structure with a useless machine word, there are all sorts of ways for that machine word to hurt the resulting program, and you can't just handwave that away.

The Linux kernel is made by people who spend weeks to shave one bit off the size of a data structure. Do you really think they'd respond positively to your saying they don't need to do that?

You really need to stop assuming what kind of computers other people are programming

The larger point here is you don't get to decide whether other people's use cases are legitimate. Either Rust gives you complete control of the machine or it does not. It does not, not in safe mode, but Rust people keep doing this annoying motte and bailey thing about it.

This conversation started where folks were talking about where to begin learning Rust. Beginning by learning unsafe{} implementations of a doubly-linked list to save 1-4% of the performance isn't where I would recommend anyone begin learning.

If they do need to shave a single bit off, they can do that, that's a neat feature too.

> You're ignoring the case of a list being densely packed and embedded inside another data structure.

No, I am not. This conversation is exclusively about non-intrusive doubly-linked lists.

If you want to have a conversation about intrusive doubly-linked lists we can have it, but it is a very different data-structure.

> You really need to stop assuming what kind of computers other people are programming

Every week I touch x86, arm, ppc64, riscv and gpu assembly.

I write code for apps daily that run from 16-bit micro controllers to the largest super computers in the world, going through phones, desktops, cloud, etc.

I am not assuming what others are programming, but rather talking about what I program for, which include most hardware that anyone can buy today, and quite a bit of hardware that almost no one can even buy, as well as hardware that's not for sale.

> A doubly-linked list is already space inefficient, it adds 2 pointers per element.

...unless you use the XOR trick to store two pointers in one field?

> learning how to write such optimized code without learning first what it takes to make it correct IMO completely misses the point of Rust.

This culture is why rust will never replace C++ and why C++ will never replace C. You can write the same computations in C++ as in C, and in Rust as in C++, but it isn't "idiomatic" so people are really afraid to do it because it will get harshly rejected by the community.

The premise that Rust does not intend to replace C and C++ is not true. Rust is designed to mesh with existing C and C++ code bases well, which is why many large projects support writing code in Rust (Chrome, Firefox, Linux, Windows, etc.).

Your claim that you need to learn all low level details first is also not true.

There are ~20 million programmers in the world, and about ~16 million of those are Javascript programmers. Many of them don't know and don't need to know the difference between the stack and the heap.

Many of them regularly optimize their Javascript hotspots by re-writing them in Rust and compiling it to webassembly. And almost all of them benefit from Javascript libraries that do this internally.

Rust is for many of them the ramp up into lower-level systems programming, and this is one of the reasons the Rust project has so many contributors. Rust enables Javascript programmers to actually hack on the Rust compiler, Firefox, etc.

This is something that C and C++ never achieved, and one of the main reasons for the Linux kernel to want to use Rust (they want to attract more junior developers to increase the developer base and make the project more accessible).

Your tone that the large majority of programmers in the world are somehow "doing programming wrong" by learning higher-level and safe languages first, and delving into low-level details as they need to, sounds very elitist and I personally find it disgusting.

> The premise that Rust does not intend to replace C and C++ is not true.

My point was that Rust wont replace C and C++ as long as the Rust community is as it is now. And from your comments it seems like Rust isn't intended to replace C or C++, but act as a low level language for people who don't know how to write low level code, like javascript programmers.

> Your tone that the large majority of programmers in the world are somehow "doing programming wrong" by learning higher-level and safe languages first, and delving into low-level details as they need to, sounds very elitist and I personally find it disgusting.

I didn't say that everyone has to learn rust by learning how to write the low level parts. I am saying that if someone wants to learn how to write low level parts of rust rather than the safe parts because they are used to writing performance critical bits of code in C or C++ then you shouldn't discourage them from doing that. Please don't put words in my mouth.

It isn't "don't know how to write low level code" in my view, it is more "don't think it is productive to reimplementat basic data structures over and over again". All the stuff you're saying you can't write in idiomatic rust is stuff that has already been written and battle tested in libraries, which are perfectly idiomatic to use. I don't need to write my own linked list and binary tree implementations over and over again. I did that in school, I can go check the code in the libraries I'm using to confirm it makes sense to me, and then just use the library and go about doing what I'm actually trying to do.

> All the stuff you're saying you can't write in idiomatic rust is stuff that has already been written and battle tested in libraries

It is fine for you to not be able to think of any scenarios where the battle tested standard libraries wouldn't be sufficient. But as someone who wrote low level libraries running in production at Google that doesn't apply to me, for me knowing what it would take to eek out performance in Rust compared to C++ is absolutely necessary and given how hostile people are my guess is that the Rust wouldn't look pretty so there is no reason for me to even try to pick up Rust.

And you can't say that I am not your intended user, if you chase away people like me from the rust ecosystem then there is no way that Rust can replace C++ in any reasonable timeframe.

What I'd like to see is a lot of examples and such showing how to write very complex things using unsafe rust. Because without that there is no way rust can compete, there are already plenty of people who know how to write highly performant code using unsafe C++.

You are definitely (one of) the intended audiences of rust, just to dispense with any confusion there.

I don't at all think that there are not "any scenarios where the battle tested standard libraries wouldn't be sufficient". I spent a number of words on exactly that in another comment below. My point in that comment was that the use case I don't believe actually exists in production code is "I'm just gonna knock out a simple bespoke implementation of a binary tree". I'm not saying people don't do that, but they shouldn't. If what you need is simple, there is a good library for it. And if the library for it is not sufficient, then it is important enough to invest time into writing a good implementation.

Maybe here's a way to put it: simple bespoke implementations of linked data structures are easy in both c++ and rust using ref counting, slightly better but low-investment implementations are still pretty easy in c++ but are not really possible in rust, and really good implementations are possible in both languages if the investment is worthwhile for the use case. It is true that you would have to learn how to write such a thing in rust and that it would be non trivial to do so, but that is just part of learning a new programming language to an expert level.

I think one misconception in here is that the rust "wouldn't look so pretty". You could do a line for line port of your c++ code using raw pointers and declare it safe, and the two implementations would have similar aesthetics. If your c++ implementation were memory safe to begin with, your rust implementation will be as well. The same process of thinking through the invariants and implementing them correctly is necessary in both languages.

I think the pushback you get that you find off-putting is against the sometimes expressed idea that it is a big knock against rust that you can't do linked data structures with zero cost abstractions in safe rust. This is why people say either "yeah but you can do minimal cost implementations in safe rust and zero cost implementations in unsafe rust". The pushback is against the idea that this isn't a good enough solution. But it totally is, it's certainly no worse than the situation in c++ where the division between a safe and unsafe subset of the language does not exist. Unsafe rust is no different than generic c++ code.

To your last point, there's a great book / reference called The Rustonomicon that is all about writing unsafe rust code well.

A link to the aforementioned Rustonomicon: https://doc.rust-lang.org/nomicon/

(I seem to recall a comment that it hasn't yet been fully updated for recent versions.)

I just saw this and thought of you, "Learn Rust the Dangerous Way": http://cliffle.com/p/dangerust/

"LRtDW is a series of articles putting Rust features in context for low-level C programmers [...] the sort of people who work on firmware, game engines, OS kernels, and the like. Basically, people like me."

Also, it seems like the author probably also wrote some low level libraries at Google... :)

Fully agree.

I have heard claims that Rust would be performance-equivalent so many times and each time I bothered to check it turned out to be wrong. Especially in video game AI, indirection, pointers and linked lists are common. They are usually used in the performance-critical input-to-frame part of the game and there fitting things nicely into CPU cache lines is crucial for performance.

The end result is that I now have this vague feeling that Rust is a religious cult and I shouldn't take their claims at face value.

C++ is better for performance because it’s old and tremendous effort has been put into optimizing it. Rust is a very young language. It benefits from the clang tool chain and gets some of that optimization for free, but there is a lot of room to make Rust faster.

Unlike GC’d or dynamic languages, there is nothing intrinsic about Rust that makes it a fundamentally harder language to optimize. It’s really like a modern provably safe C++.

It also depends on how you code. If you make heavy use of functional constructs and complex types your Rust code will probably not end up being optimized as well. For tight algorithms it’s good to write “thin” Rust. The exact same is true for C++. You would not want to use a lot of STL or functional stuff in a rendering pipeline core. High performance C++ looks like C.

Which optimizations is the rust compiler missing?

A lot of the optimizations required for fast code, like manual layout of custom datastructures are done by the programmers, not by the compiler. I don't doubt that rust can also express this optimizations given the similar low level control provided by the language, but what the OP and the parent are saying is that some of these are not idiomatic in rust and harder or impossible to express in the safe subset of the language.

> You would not want to use a lot of STL or functional stuff in a rendering pipeline core. High performance C++ looks like C.

FWIW that's not at all my experience.

Agreed. My favorite example of C++ vs C performance is C++’s `std::sort` which is intrinsically faster than anything similar in C because C lacks the language features (templates) to support performant code reuse like that.

TBH, while I can think of many layout optimizations that Rust does and C does not, I can't think of any that C or C++ do that Rust does not.

In particular when it comes to unions which are heavily used in low-level code, Rust does optimizations that C and C++ can't even dream of (like all the niche optimizations).

which optimizations on unions does rust do?

In C++, you have `std::optional<T>`. That's a type that either contains a `T` or contains nothing.

In C++, sizeof(optional<T>) > sizeof(T) because the discriminat has to be stored somewhere.

This is true even if, e.g., you do something like `optional<T&>`. You know that T& is a non-null pointer, and you only have two variants, and one of the variants has no state, so you technically can encode this as 0x0 is the "no reference" variant, and the != 0x0 is the reference variant, and have `optional<T&>` have the same size as `T&`.

Rust does these layout optimizations of compressing the discriminant into gaps in the values of discriminated unions automatically.

So:

    enum Option<T> {
        Some(T),
        None
    }

for `Option<T&>` has the same size as `T&` in Rust, as opposed to C++.

In C, an example would be:

    struct DU {
        enum { A, B } discriminant;
        union {
            bool A;
            bool B;
        }
    };

You could encode that into 3 bits (i.e. have sizeof(DU) == 1), but instead you'll have at least sizeof(DU) == 2, because you need one byte for the discriminant, and one byte for the payload.

It is very easy to create values with gaps in Rust, but C doesn't really support doing this.

Another optimization are alignment optimizations. In C, if you write:

   struct S {
       uint8_t a;
       uint32_t b;
       uint8_t c;
   };

that ends up being 12 bytes long. In Rust, by default, that gets reordered as uint32_t, uint8_t, uint8_t, so it only ends up being 8 bytes.

If you want that instead to be laid out like in C, you can write:

    #[repr(C)]
    struct S {
       a: u8,
       b: u32,
       c: u8
     }

and then you get the same 12 bytes as in C. There are many supported `repr(...)` options supported for algebraic data types, e.g., you can use repr(u32) for the Rust enum above to store the discriminant in a u32, and get the same layout as DU in C.

Right, c++ has no builtin discriminated union, and std::optional<T&> is actually not valid in C++ (unfortunately).

But discriminant-less custom optionals classes with 'zero' type support via traits are easy to do (and I have done it many times). You do not have to rely on the compiler identifying a safe empty state and you can define any application specific one. For example if for one specific (and common) use case strings are always non null, optional<string, non_null_trait> has an obvious implementation.

So, yes, these sorts of optimizations are not done by the compiler has it has no notion of discriminated types (one day maybe...), but can be done generically by the programmer. In fact you could in principle optimize multiple layers of variant<optional<...>,... > and collapse everything in one discriminant,as long as you do not provide reference access to the sub variants; the required metaprogram is not going to be pretty though.

One of the advantages of C++ is that it allows this sort of control.

> One of the advantages of C++ is that it allows this sort of control.

But I believe what the OP showed is that Rust also allows you to have that level of control. However, the default behavior for rust is to do the optimization that you have to go out of your way to manually implement in C++.

Rust isn't taking away control from what you can do in C++, instead, it's made the idiomatic approach one that is well optimized by the compiler.

There are compiler directives for packed structs in C++. struct __attribute__ ((packed))

Rust also has a packed attribute; this is something different. The re-ordering still includes padding, whereas packed removes the padding.

Depending on the values in b, you could do bit-packing in C++ and munch it down to just 1 byte.

You can only do bitpacking if individual fields of a struct cannot be accessed via reference (or 'borrowed', in Rust terms). While C/C++ includes the 'register' keyword which forbids reference access, Rust does not.

Rust uses LLVM so optimizations occur at the AST level. Therefore it should be able to take advantage of the same optimizations as Clang C++ which uses the same approach.

They happen at a lower level than an AST, but you're right that any front end can in theory generate the same IR and therefore get the same optimizations. The trick is if the language semantics allow for it; this bites both ways.

> Rust is a very young language. It benefits from the clang tool chain and gets some of that optimization for free, but there is a lot of room to make Rust faster.

I feel that this sort of belief relies too heavily on a presumption that performance is somehow proportional to the age of a programming language, and in the process ignores the fact that a) it's already using a highly optimized toolchain that benefits from decades of research and development, and b) there is absolutely no suggestion that any potential performance gains are relevant or exclusive to the Rust's front-end.

There is always a long tail of optimizations and tweaks that must be done to get a language that last 5% of the way to parity with a language like C. Building on LLVM gets them 95% of the way.

BTW Rust has some features that make optimization a lot easier, like the ability to assume strict aliasing in more cases. It’s safety features also make it easier to write zero copy, copy on write, and other optimization patterns without making mistakes. This enables some bold performance optimizations at the code level that would require serious bravery in C.

Long term I expect that Rust will be faster in some cases.

You can also align data to cache lines if you want to in Rust, without unsafe [1]. It is not C/C++ specific.

For linked list, you can use an unsafe implementation if that is performance critical. Unsafe implementation can be wrapped in a safe API for others to use, and this is how the standard library is implemented.

There is also a new paper about structures with internal sharing such as graphs without runtime overhead that Rc/RefCell would cause [2].

[1]: https://doc.rust-lang.org/reference/type-layout.html#the-c-r...

[2]: http://plv.mpi-sws.org/rustbelt/ghostcell/

> I now have this vague feeling that Rust is a religious cult

I had this feeling from the very beginning just by the tone of its zealots here and elsewhere. My theory is that since the language is very hard to learn but doesn't provide a lot of tangible benefits (memory safety exists in most mainstream languages fot decades), the sunk cost fallacy hits very hard. Then the only way to get some benefits for the time spent is to recruit new comers in a sort of pyramidal scheme structured around experience in the language. This way the zealots become priests and are compensated in form of social status. Of course, the whole scheme cramble if nobody joins, which is why the community is so aggressive (RIIR, vocal advocating, etc.) with the non-believers.

People like rust for a lot of different reasons; that is, different people see different tangible benefits to it, and that has resulted in both a large and fast growing community of people who like it, and (predictably) backlash to that.

On the side of people coming from other memory safe languages, the benefit is much like Go, which has also become very widely used very quickly, so it seems worth taking seriously that the existing memory safe languages were maybe not satisfying people in some way. I think the popularity of both languages in this space can be boiled down to lowering the amount of abstraction without giving up memory safety, and simplifying the toolchain. Both Go and Rust do both of those things (in my view). I prefer rust because I don't like how the Go type system requires so much repetition of implementation due to lacking generics, but both languages make some amount of sense in this niche IMO.

Other people like rust because they came from C or C++ and got tired of some of their weaknesses but did not want to give up many of their strengths. Of course whether rust requires giving up the strengths of this languages is debatable and this where most of the backlash comes from. But rust is one of a very very few languages (maybe also D and Zig?) that can plausibly make this claim at all, and I think is has become the most actively developed and attracted the largest community of those, which does matter.

For me, it's a huge advantage to be able to plausibly use the same language for everything, from kernel drivers to giant applications. The only real competitor in that space is C++, and I think its cracks show more on both extremes, that is, I think rust is both a better C replacement at the very low end (see people like Linus Torvalds and Bryan Cantrill who are C diehards who dislike C++ but are interested or all in on rust) and is much better at the high level because of easy memory safety.

So I dunno, maybe there's a cult, but there are also very straightforward reasons why a lot of people are attracted to the language.

> I now have this vague feeling that Rust is a religious cult

I'd say even if many of technical claims about Rust are true. It still seems very much like a cult.

I've also heard your claim many times, and every time I checked, replacing a doubly-linked list with something else improved performance by orders of magnitude.

Particularly in video games.

---

> The end result is that I now have this vague feeling that Rust is a religious cult and I shouldn't take their claims at face value.

Also, you realize that Rust allows writing efficient doubly-linked lists right ? And that the Rust standard library provides one for you right?

The whole argument of the OP is that people learning programming need to start doing so by learning how to write doubly linked lists because performance trumps all and therefore all children, elderly, and even university students that learn programming with javascript are lesser human beings and don't deserve our respect.

The linked list provided by the standard library is unfortunately not very useful. It doesn't provide O(1) operations on the middle of the list, making it more or less a worse VecDeque. Of course there are crates that provide better implementations but people really need to stop pointing people toward the one in std.

The lack of goto also bars it from the domain of very fast interpreters. Computed gotos are a common technique used in C/C++ interpreters which aren't possible in Rust.

To be fair, the last time I checked, LLVM was doing an okay job of generating jump tables from big switches and threading the cases for best jump target prediction --- same thing you'd do with computed goto.

But yes, lack of goto and computed goto are deficiencies, not strengths.

> Rust's safety checks do in fact block some safe and zero-overhead abstractions familiar to people working in C and C++

The issue of course is that while these abstractions are zero-overhead and can sometimes be used safely, they aren't compositional in general. That is, they impose requirements on outside code which aren't easily captured by Rust's type system. This is exactly what the 'unsafe' facility in Rust was made for. Note also that more recently-developed abstractions of the "Qcell" or "GhostCell" type can in fact implement linked lists safely, and once these are better understood a variety of them will likely be included in the Rust standard library.

Doesn't GhostCell preclude deletion, and effectively grow forever?

Would anybody use a doubly-linked list if they care about performance? Cache misses are where performance lies in modern systems and linked lists are maximally bad for this.

You can also say almost the same things you are saying here about C++. Type punning is almost always undefined behavior. There is no way to construct an array of variable size at an address that you specify without a pointer indirection. But with ASM you've got no such problems!

> Would anybody use a doubly-linked list if they care about performance?

That's probably the only reason to use them. If you don't care about performance there are simpler data-structures available.

If you need to implement an algorithm for which you need O(1) splice, then doubly-linked lists are a data-structure that give you that. If your objects are very big the cache misses might not matter that much, and neither would ref counting.

If you go one step higher, and can modify your object data types, and are careful with how you allocate your data, then intrusive doubly-linked lists can give you equivalent performance to a vector with better algorithmic complexity for many insertion / removal / splice operations, etc.

The stars do however need to align a lot for a non-intrusive doubly-linked list, like the one being discussed above, to be the best answer for whatever performance / algorithmic problem you are having.

> The stars do however need to align a lot for a non-intrusive doubly-linked list, like the one being discussed above, to be the best answer for whatever performance / algorithmic problem you are having.

That O(1) splice must also be accompanied with an iteration. Which, in my experience, is really rare. If that iteration step wasn't already a part of the splice requirement then it can often be faster to do the splice via a memcopy.

My favorite algorithmic mistake was someone at my company used a binary search to maintain sort order on a linked list. IIRC, that turns insertion into something like an O(n^(log n)) operation whereas it's O(log n) operation on an array.

> That O(1) splice must also be accompanied with an iteration.

I don't think it necessarily must, but it tends to be.

People tend to keep pointers to elements of the list all over the place, so if you have the right 3 pointers (being and end of list you want to insert, and position in another list), then you can do it in O(1).

If not, and you need to traverse the lists... as you mentioned there are other data-structures that might be much better.

With a circular list, you don't even need the extra pointers.

> If you want good performance but don't care about precise control over the machine, write Java or C# or something high level like that. You'll be just as safe

No, you aren't.

None of these languages catch data-races, so writing multi-threaded code is pretty much as hard and error prone as in C. Other higher-level languages like Python fix this by holding a global mutex, so that using multiple threads doesn't really buy you that much there since threads always execute sequentially to avoid data-races.

This is in contrast to Rust, which allows anybody, even people without experience in low-level programming to accelerate their applications using multiple threads, without introducing bugs.

Actually, Mozilla tried to multi-thread Firefox multiple times using C++, and failed, over and over again, because every attempt would introduce subtle bugs. Rust was created to address this issue.

> None of these languages catch data-races, so writing multi-threaded code is pretty much as hard and error prone as in C.

All real world languages have facilities for various kinds of safe concurrency, e.g. actors and other kinds of message passing. When it comes to concurrency, Rust isn't anything special. It's not even that good.

Rust has one killer feature: memory safety without GC. Except for this feature, Rust is mediocre. If you don't need the memory safety without GC, you can use almost anything else and be better off.

Rust only catches integer overflows in debug builds, my C# programs catch it everywhere. The compiler setting is off by default but it is available.

In Rust, many libraries especially the standard one have lots of unsafe code, with a history of security bugs there [1]. In C#, the standard library is written in almost 100% safe code.

About threading, while it doesn't catch all data races automatically, C# implements many useful things on the VM level. Monitor class, or memory model guarantees, are very hard to implement in languages who compile to native code.

[1] https://shnatsel.medium.com/how-rusts-standard-library-was-v...

> I'm really tired of this motte and bailey stuff. Rust proponents say Rust gives you fine grained machine control and safety with no performance compromises, and then when you point out that the language doesn't quite live up to that promise, Rust proponents start telling you that you didn't really need that performance anyway.

Citation needed: which part of my comment says this?

I wonder if that's still relevant way to learn Rust as seems to written in 2018.

The changes since 2018 have been very minor

Yep, the core concepts did not change. It's still relevant.

RCU - Read, Copy, Update - A strategy for readers and writers, where the readers do not exclude writers (best as I can tell).

... without any sort of locking.

>AFAIK no such correctness proof for the C APIs exists

There's a whole proven correct kernel: http://sel4.systems/

SeL4 is not the Linux kernel and it doesn't use RCU.

So yes, there is a correctness proof for a completely different operating system that does not use the one thing we are talking about here.

I can't access the article at $JOB, but if I understand correctly, Rust would guarantee that usage of the RCU API si correct, but it would be silent on the API implementation itself as it would be written with unsafe (but crossbeam-rs). On the other hand the author is probably saying that the kernel RCU C API itself has been proven correct, either manually or by machine checking (directly the C code or a translation of it in a proof assistant); usages of the API might not be proven correct though.

Also note that the author of the article is the actual inventor of RCU.

> Also note that the author of the article is the actual inventor of RCU.

I know, so?

> On the other hand the author is probably saying that the kernel RCU C API itself has been proven correct,

But this is not true right?

There is no formal proof, e.g., in Coq, that proves a useful subset of the RCU C API correct (as in, if you stick to this useful subset, you can't introduce UB).

OTOH, a safe Rust API could be proved correct to use at least, and an implementation of it that uses unsafe, like the one in crossbeam-rs, is typically very amenable to theorem provers (much more than C).

So what I am saying is that the author is ignoring the value of providing a safe Rust API for RCU, like crossbeam-rs.

If the Linux RCU APIs can't be mapped to it, then maybe they are incorrect to use, and this is why we can't prove them correct.

Doing the work of mapping them, and understanding any issues, could lead to changes to those APIs that might allow us to prove them correct.

A quick search shows a bunch of papers about RCU possibly containing proofs. I don't know if there is a coq proof, but there are other dedicated tools to model lock-free algorithms, or possibly the proofs were done by hand.

Of course that's still not proving the actual C code, the translation probably still need to checked by hand.

> an implementation of it that uses unsafe, like the one in crossbeam-rs, is typically very amenable to theorem provers (much more than C)

Just wondering, how many unsafe code in commonly used libraries (standard library, tokio etc.) are proved using theorem provers?

Don't have comprehensive enough data to know, but part of the standard library was proven via the Rustbelt project, and it found some places where there were bugs, as well as some places where things could safely be loosened up.

Most of the unsafe code in libcore is proved in Iris.

Some of the unsafe code in the standard library also.

Some parts of crossbeam have pencil&paper proofs documented.

RCU, for the uninitiated:

https://en.m.wikipedia.org/wiki/Read-copy-update

Reply on news.ycombinator.com