Comparison between Rust and D
maikklein.github.io
maikklein.github.io
Seems to go very much into details about syntax bike shedding but not saying much about the more "global" design differences.
Combine GC and non-GC in a single application. This would be great for game programming for example. Handle audio and video in a soft-real-time non-GC thread. Handle other stuff like game logic in a GC thread, such that it is easier to write. The hard part is that GC usually requires stop-the-world. You can currently do this [0] in D, but it is error prone. Rust tackles this problem from the "other side": First make it safe, then possible.
[0] https://p0nce.github.io/d-idioms/#The-impossible-real-time-t...
Rust is actively working on this, in fact.
The idea is to eventually have a Gc<T>-like type, like Rc<T>, which can be used on specific things. It will interact fine with the regular heap, so `Vec<Gc<Foo>>` where `Foo` contains a `Box<Gc<T>>` will still work.
You can then selectively apply this Gc<T> to things which need it. For example if you have a large graphy-datastructure in your code and don't want to bother with weak pointers. Or if you are doing FFI with a language that does have GC.
Rust itself would not have the Gc<T> type in the stdlib, it would only contain a couple of traits and compiler intrinsics that are useful for a GC. (The idea is to be able to turn on LLVM stack maps and use it for GC rooting). So you can write a gc for your specific use case (even if that use case is just safe bindings to a different GC from a runtime you are interacting with!) and it should work. In fact, in the design so far it seems like multiple GC implementations will be able to exist in the same application, and perhaps even safely interact (you can control whether you want this to be possible using the type system; I'm not sure if there is ever a case where this would be needed)
This would of course, still be safe. It would not be possible to violate GC invariants using safe code, nor would it be possible for the GC to violate regular safety invariants.
I guess I'm mostly worried about Gc being used by a large number of libraries, to the extent that it might not matter if stdlib implements it or not, because by using some very popular library you'd end up pulling in this runtime dependency.
Part of me loves the flexibility this will bring to application design, but it could be a slippery slope.
Remember, even the proposed Gc<T> type provides very little in the way of ergonomics (at least compared to garbage-collected types in pervasively-GC'd languages). Essentially it would just be a souped-up Rc<T> with no need for weak pointers to resolve cycles. Alternatively, it would only be used to interoperate with a foreign codebase that already uses GC, like SpiderMonkey or V8.
Given that people tend to only be writing Rust in the first place if they put a large degree of value on performant solutions, I'm not too worried about the library ecosystem suddenly sneaking in GC everywhere, especially since the Rc type is already halfway to garbage collection, and I don't see it used unduly in the wild.
Nor will the stdlib expose a GC API. I do intend on writing an example GC for this, but really each use case will probably need its own special GC implementation; since they are special use cases.
That's not a decision to take lightly.
I don't think GC will be something that can be silently pulled in, either, since you will need to change your codegen flags at the top level. This could be abstracted away by cargo, but it might be better if it wasn't; and you have to explicitly tell cargo in the toplevel toml file that you want GC to be on (and get a compile error if you try to compile without those flags).
==================
Also, the Rust community seems to be very careful about unnecessary costs. Even Rc<T> isn't used much, and when it is, it seems to be used at the application (not library) level.
When I have to box a closure or iterator in Rust because `-> impl Trait` doesn't exist (where you can return anonymous types by specifying the trait they implement), I feel so annoyed by the cost. As do many other Rustaceans. In reality, this is a pretty rare thing to do and the costs are negligible; but it feels annoying to not have the best performance. In such an environment, I doubt a library that frivolously uses GC will survive.
IMO, Rust just not good enough for creating complex specialized data structures.
Even a trivial tree is hard to implement in Rust, and the implementation will be severely limited: https://github.com/SimonSapin/rust-forest
D surely has it’s problems as well (in short, I think the language itself is very good, but its runtime and libraries still need a lot of work), but at least it’s good for complex data structures.
Other languages do this too, for instance in Java you can override final with reflection. I lost my mind, both good and bad, when I discovered this.
It's taken me a year to feel good about my Rust code, I'm still getting a handle on unsafe though.
By “efficient” I mean I want to split my list in two for O(1) complexity, like other programming languages do.
pub struct ListNode<T> {
data: T,
prev: Weak<RefCell<ListNode<T>>>,
next: Rc<RefCell<ListNode<T>>>,
}
Also, the code doesn't use `unsafe`. Now, you would need to use `unsafe` somewhere to actually create a list, in order to initialize the fields (or you could change the type of `next` to be `Option<...>`). However, the use of `unsafe` would be limited to that method. This tries to get at the difference between (i) occasionally using `unsafe` and (ii) having no safety guarantees at all.
There are probably lots of other pain points that you can bring up, and I'm not trying to say this should be good enough, but I thought it might help explain what is possible.
For example, a vector that keeps some items + hash map that implements an index over that vector. Or some container that keeps some items + a linked list to track and evict the least recently used item from that container.
Rust is just too safe for that. That might be technically doable, but harder to implement, and harder to use.
This certainly applies to Rust’s built-in data structures as well. See this example, the problem is trivial to solve in most languages: https://www.reddit.com/r/rust/comments/3cz71e/holding_a_muta...
> See this example, the problem is trivial to solve in most
> languages
About the safety, it’s important to understand there’s a price. In some cases, it causes simple things hard to implement, or cost performance.
For example, there’re algorithms out there that modify items of the same collection at the same time, both single threaded like sorting, and parallel.
Can such algorithm cause a data race? Yes.
Is it good the compiler tells me about that? Sure.
Is it good the compiler prevents me from doing that at all, and forces me to code some workarounds, that will cost me time to implement, will be ugly, and/or will sacrifice runtime performance? Not sure, I like having a choice.
> There’s no malloc/free
> placement new is still unstable
> Is it good the compiler prevents me
> from doing that at all
> workarounds, that will cost me time to
> implement, will be ugly, and/or will
> sacrifice runtime performance
Disagree.
In C++ we have sophisticated debuggers, we have standard C library, STL with its containers, algorithms and lots more, boost and other third-party libraries.
When coding typical Rust, we have descent-quality standard library, also big set of third-party libraries.
When coding Rust as though it were C, we have almost nothing, because the rust’s standard library doesn’t expose unsafe API.
Unsafe Rust only takes same time to write as C++ if you’re coding something trivial, like a “Programming 101” homework. For anything even remotely useful, debugger and libraries make huge difference.
A single bounds checking feature (C++ has that with STL containers in debug builds, controlled by _GLIBCXX_DEBUG or _ITERATOR_DEBUG_LEVEL) can sometimes save hours.
> In C++ we have sophisticated debuggers
> the rust’s standard library doesn’t expose unsafe API
> A single bounds checking feature
Well, here’s a simple example I’ve wrote above: “Some container that keeps some items + a linked list to track and evict the least recently used item from that container”.
You know, LRU caches are everywhere. I remember in C++, I recently wrote something similar in three completely unrelated projects. Well, a linked list alone isn’t usually enough, but a linked list + unordered map that maps elements to list iterators do the job very well. To update the LRU order, I query the hashmap and get a list position, then I move that element to the list’s tail. And when I need to evict an element, I grab the list’s head and evict those.
Note the following good things about this C++ solution:
(1) All those operations (hashmap lookup, linked list reorder, linked list remove head) are O(1), i.e. I can have millions items in my cache, and still update my LRU order for practically no cost (a few pointer writes).
(2) I didn’t wrote much code, only creatively combined what was already here in the C++ standard library.
Now Rust.
The safety means pointers to list nodes aren’t part of the list’s API.
And without raw pointers, linked lists are nearly useless, because we can’t split or reorder them efficiently. If you’ll read the documentation for LinkedList<T>::split_off, you’ll find the complexity is O(n), while for most other languages, linked lists are famous for being able to do that for O(1).
I’m not sure any efficient linked list API is possible within Rust memory management model, safe or unsafe.
> The safety means pointers to list nodes aren’t part of the list’s
> API.
And even if my intuition is wrong and there's some reason why the implementation of LinkedList in the standard library can't do this for some reason, I see no additional reason why some other implementation of linked lists couldn't do this. (The standard library implementation likely optimizes for convenience rather than power, given that our data structures guru has a complicated relationship with linked lists: http://cglab.ca/~abeinges/blah/too-many-lists/book/README.ht... ). The fact that Rust doesn't favor these sorts of things hasn't stopped others from going ahead and writing implementations anyway: https://crates.io/search?q=intrusive
> I didn’t wrote much code, only creatively combined what
> was already here in the C++ standard library.
> I’m not sure any efficient linked list API is possible
> within Rust memory management model, safe or unsafe.
How about rust memory management model?
When I split linked list in two, the new list must somehow become the owner of the newly detached elements.
For both unmanaged and garbage-collected languages there’s a heap (garbage collected or not) that’s shared across all threads of the process. List nodes are freed either explicitly with delete/free, or implicitly with GC.
Rust memory managed model forces to transfer the ownership when the list is split. AFAIK that’s exactly what happens inside split_off, and that operation is O(n).
> unsafe code can use raw pointers willy-nilly
If so, why the implementation of LinkedList<T> doesn’t? You know, O(1) and O(n) is a big difference.
Because the stdlib doesn't want to expose too many unsafe APIs on its datastructures, giving it freedom to evolve the internals. And LinkedLists are considered a niche type anyway, not for general use.
As kibwen mentioned, you are free to create your own linkedlist implementation that exposes this API.
Rust has a heap, and you can free things directly if you need.
In C++, I don’t need to spend time implementing and debugging my own linked lists, because standard library implementation already good enough for the task. I only need to encapsulate two standard containers together, and write a pair of methods to add/remove stuff.
In Rust, I need to roll out my own lists, because stdlib doesn't want to expose too many unsafe APIs on its data structures.
You agree with all of the above?
If yes, hope now you see how Rust isn’t good enough for creating complex specialized data structures.
In fact, you said it yourself, "specialized". Since linkedlists are generally used in specific cases with different required ergonomics, you do not want to expose a catch-all.
Why not? An LRU cache is moderately complex specialized data structure. As you see, for some reasons, it’s much simpler to implement in C++ then in Rust.
> The choice made by thee stdlib to not support many linked list operations does not imply Rust is unsuitable for complex specialized data structures
I never said it’s unsuitable. Technically, all modern programming languages are Turing complete, so in some sense they’re equivalent. I only said Rust isn’t good enough for that. Meaning, in many other languages doing that is much simpler than in Rust.
Linked lists are special case of trees, which in turn special case of graphs. Both trees and graphs are used a lot: DOM trees, syntax trees, KD/PK trees, quad edge graphs, and so on.
Rust’s memory management model is neither manual nor garbage collected. This feature makes it hard to implement those pointer-based data structures, where items are in shared ownership of the container, where you want to split/merge those containers, and move items across containers.
Not impossible, just hard and/or inefficient (like those ref.counted implementation that increment/decrement those counters each time I traverse the graph, even if I only reading stuff).
Because of the standard library. This is not a language issue, this is a library issue. This has nothing to do with Rust's memory model. It has to do with Rust's choices of having a smaller, maintainable stdlib and relying on the crates ecosystem for most libraries (which can then evolve independently of the language, which is nice).
Someone has to write a linkedlist implementation of the type you describe and put it in a crate, and that's it; everyone can use that. It should be trivial to make a pull request to https://github.com/contain-rs/linked-list to add the method you describe, for example.
--------
Edit:
Rust does make it harder to implement the bottom level of low level abstractions (doubly linked lists, LRU caches, etc), since these deal with memory the most and can easily become unsafe. You implement them once with a safe API, and use them as much as you want.
The reason std doesn't expose too many unsafe APIs on its datastructures is because if you need that level of control, it is better to have your own implementation. Safety is hard; and the more unsafe APIs you expose, the more you run the risk of external unsafe code depending on the internals of the implementation in the stdlib. Due to this, it would be preferred if you write the LRU cache with a linkedlist implementation embedded in it (which could be a separate crate for reusability), with the invariants well documented. This is a choice made by the stdlib, but has nothing to do with the language itself and is a choice that external crates are free to not follow.
Yeah, prohibitively harder. If you really need an efficient linked list, or tree, or graph, Rust makes it nearly impossible to accomplish.
> The reason std doesn't expose too many unsafe APIs on its datastructures is because if you need that level of control, it is better to have your own implementation
This might be true for Rust, but the argument is language-specific. In C++ I often need “that level of control” and yet I’m happy with many stock implementations. Moreover, I can combine different data structures to produce whatever I need. Can’t in Rust, because the library designers (not just std, the rest of them as well) think I better have my own implementation if I need that level of control.
> Safety is hard
Not necessarily. C# is very safe, and yet it’s much friendlier to developers: I never used unsafe C# code to overcome language limitations, only to interop with unmanaged code.
No it doesn't. It's literally adding one extra simple function to a library.
> Not necessarily.
Well-performing safety is hard, then. Safety is hard in C++ and Rust, less so in C#. Yes, it is easier to write a linked list in C++, but ensuring it is used safely is hard.
> Can’t in Rust, because the library designers (not just std, the rest of them as well) think I better have my own implementation if I need that level of control.
Right, and that is solely a library issue. Rust doesn't prohibit having composable unsafe libraries either. The ecosystem just hasn't produced those yet, because people probably didn't need it yet; and it is mostly preferred for libraries to keep the unsafety encapsulated inside behind a safe abstraction.
No function will transfer ownership of N nodes to the new container for O(1) complexity.
And if you’ll refactor the list to reference counted nodes, you’ll introduce costs to traversal.
> it is easier to write a linked list in C++
And a tree. And a graph. Trees / graphs structures and algorithms are everywhere, too bad Rust language designers forgot that.
> Rust doesn't prohibit having composable unsafe libraries either.
Does not prohibit but makes it hard, because Rust’s primary design goal was that safety thing.
No safe function. It is easy to do with unsafe. This has been explained already.
> And a tree. And a graph. Trees / graphs structures and algorithms are everywhere, too bad Rust language designers forgot that.
Rust's designers are mainly from the C++ world. They know this. And we have seen tons of these datastructures crop up that are written in Rust code everywhere.
The idea is that you find a safe abstraction boundary for you low level data structure, and stick to it. For an LRU cache, the boundary is the LRU cache (not the internal linked list, which needs to be accessed using `unsafe`). The stdlib exposes a linked list that can be used standalone, but as part of a larger unsafe datastructure you should copy it out and integrate directly to get finer grained unsafe access.
The strategy “find a safe abstraction boundary for you low level data structure, and stick to it” works well for a scripting language. Or for high-level code that’s not performance-critical, like business logic.
It doesn’t work well for a general-purpose language that’s used for algorithms-heavy performance critical tasks.
There’s no “low level data structures”, because data structures are all the way down, and composed all the way down. Very often I need unsafe things at my API boundaries, because performance or because interop. I can’t implement my data structures once and stick to them, because as I work on the project I change both code and data structures (the main input here is profiler).
That safety thing makes data structures impractical. As you see from my linked list example, they are hard to create, use, and compose.
BTW, graphs (including trees and lists) are just one example how pointers are useful in data structures. Here’s another one.
In C++, I can add an index to a collection using unordered_map<tKey, Value*>. This index allows constant-time lookups, and if the tKey is something small like an int, the RAM cost is very low, because only keys + pointers are stored in the hash map, not the values themselves.
If I’ll want to do same in Rust, I suppose you’ll tell me I need to copy-paste the collection source code and add index there, because what’s in stdlib ain’t composable the way I want :-)
> When I split linked list in two, the new list must
> somehow become the owner of the newly detached elements.
If you want you can always use raw pointers and dereference them in unsafe {} blocks, and even provide a safe API (return borrows with appropriate lifetimes) around this. You'll find plenty of common patterns in the standard library and on crates.io too.
I am frustrated with new languages. I agree that C++ is old and needs a more modern replacement but:
- Go is weird with no templates and no functional programming.
- Nim comes close to my dream language but has a GC and some very awkward features like globally imported namespaces.
If I had to start a new project I would probably pick Nim or C++.
I mean, you haven't actually pointed at a trivial tree implementation. The requirement that children be able to navigate to siblings is the issue here (complicating unique ownership by parents).
You could totally do a "trivial tree" as
struct Tree<T> {
payload: T,
children: Vec<Tree<T>>,
}
It's not really clear (to me) that the rctree is really all that complicated; the Rc stuff is there to clarify ownership: for how long should allocated memory stick around. It might just read weirdly due to familiarity, in the same way that D might weird me out.
Any prospect about that?
The other linked posts regarding meta-programming features of D are also great.
fn main() {
let x = true;
let x = false;
}
fn main() {
let x = true;
{
let x = false;
}
}
def fn(object):
let object = predicate(object) ? modify(object) : error();
// do something with the refined object
Can I write
let x = 1;
let x = x + 1;
?I would guess shadowing wouldn't affect values shared with a different thread, because it's technically a new value, but in single-thread use it would be equivalent to assignment.
That is actually a big deal, though.
let x = 1;
let x = x + 1;
x = 99; // Error: you can't accidentally modify the immutable variable `x`
let mut x = 1;
x = x + 1;
x = 99; // Ok
let mut x = 1;
x = x + 1;
let x = x;
x = 99; // Error: `x` became immutable
Consider this program:
fn main() {
let x = 5;
let r1 = &x;
let x = x + 1;
let r2 = &x;
println!("r1: {:p}", r1);
println!("r2: {:p}", r2);
}
r1: 0x7fff955e3dfc
r2: 0x7fff955e3dec
Also, given compiler details like SSA, I'd argue that in a certain sense, mutation is similar to this, rather than this being similar to mutation...
> isn't it just mutability with different syntax then?
let mut a = 2;
let b = 3;
let x = &mut a;
// let y = &mut b; // error: cannot borrow immutable local variable `b` as mutableSome people don't like it, and if you don't you can use clippy to disallow it. From what I've seen, most Rust code does use shadowing.
Dun dun duuun
I used to write a lot of C++ and my idea of immutability always was that if I see a variable declaration at the top of a function and scroll down to where it's used (without reading the code in the middle) I can assume nothing happened to the variable.
Then I started to learn Haskell something like a year ago and found out that shadowing is not only allowed but used by people. Especially in Haskell (or OCaml for that matter) where you can just use x' for a slightly modified version of x. I don't know. Maybe I get used to it one day.
I don't know if it's idiomatic, but I find it keeps things cleaner by not having to define lots of different names for essentially the same variable.
Scope 1
let x = 1
let x = 2
=> error, rebinding variable in scope not allowed
let x = 1
shadow x = 2
=> works!
shadow x = 2
=> error: no variable x to shadow declared in scope
Shadowing within the same scope is admittedly unusual.
D: people don't.
Weka explicitly says "over 200K LoC"
I'm not an avid D user, but I have a guess as to why it is not so widely used.
To me, D is somewhat of a "I like C++s features and ergonomics and want a similar languages with all the features built in from the ground up" (+awesome metaprogramming). One of C++s drawbacks is that features have been bolted on in hacky ways due to backwards compatibility issues. D is like C++, but without this. It is a good goal, and from my limited experience with D I think they have achieved it well.
Thing is, such a language will largely be adopted by people who use C++. And the problem with these folks is that they already know C++. Once you are used to it it doesn't feel so bad. Despite its drawbacks, C++ has lots of tooling, a large ecosystem, and familiarity.
Rust is less affected by this for two reasons. One is that it gets a lot of production users from non-C++ shops who want to use a systems language to speed up their Python/etc tight loops. They would rather not worry about segfaults and stuff. The other is that for C++ users, Rust scratches a large itch. The learning curve for Rust is a lot worse than D, but for many the benefits might overcome this. You can't get used to segfaults the way you get used to template metaprogramming.
I would give D time. These issues just slow adoption, not stop it. That is fine.