Live data from Hacker News

Rust Sucks If I Fail to Write X

llogiq.github.io

31–40 of 89 posts

Re: Rust Sucks If I Fail to Write X

#31

I think this misses the problem. Should you write your own data-structures? Not unless absolutely necessary. But mostly everyone knows that. So why are people complaining about data-structures? For me, writing the data-structures is the canary in the mine. It's the next step from hello world when trying to pick up a new language. Most importantly, trying to write a few simple data-structures hints at the difficulty t…

> For people like me, if writing trivial data-structures in Rust is a great challenge, it shows that writing other, less trivial things in Rust will be much more challenging than might be preferred.

And this is the real issue, because your assumption doesn't really have any real basis. I don't mean to belittle your point, I can completely understand where you're coming from, but assuming that because writing data structures in Rust is hard, that "real" problems will be difficult as well, is wrong. There's nothing to back this up. Data structures are a very specific domain, often very far away from what you'll be doing in the average "real" program. There's a reason common data structures are often implemented and included in the stdlib of most languages.

What I find is that it's more common that writing data structures in other languages is easy, because most of the time, people aren't implementing them correctly, or safely. 99% of the linked lists I see in C++ fail to even implement the copy constructor, meaning they're going to be broken the moment you do a copy of the list.

Re: Rust Sucks If I Fail to Write X

#32

I think this misses the problem. Should you write your own data-structures? Not unless absolutely necessary. But mostly everyone knows that. So why are people complaining about data-structures? For me, writing the data-structures is the canary in the mine. It's the next step from hello world when trying to pick up a new language. Most importantly, trying to write a few simple data-structures hints at the difficulty t…

> For people like me, if writing trivial data-structures in Rust is a great challenge, it shows that writing other, less trivial things in Rust will be much more challenging than might be preferred.

I understand the source of the sentiment, but also disagree with it. I've been writing Rust code for years and have never had occasion to write my own custom data structure, and (discounting FFI) I've reached for the `unsafe` keyword like twice (which I think I ended up removing anyway, because I was trying to be too clever).

But then again, my background is in higher-level languages (Java, Python) where writing data structures isn't your usual beginner task. I sympathize with C programmers to whom a linked list is the go-to toy learning program, but the urge to resort to unsafe shenanigans to implement self-referential data structures doesn't reflect the typical experience of using the language.

And for those who still wish to persist, may I recommend the book "Learning Rust With Entirely Too Many Linked Lists": http://cglab.ca/~abeinges/blah/too-many-lists/book/

Re: Rust Sucks If I Fail to Write X

#33
You can do linear lists and trees in Rust. The problem is backlinks. If you refcount everything, you can have backlinks, but otherwise there's a safety problem. Backlinks require an invariant which covers two variables, and you can't express that in Rust.

Back pointers are a special sort of pointer from an ownership perspective. They don't carry ownership, but are locked in an invariant relationship with the pointer that does. If you could express that in Rust, it would be compile-time checkable. Rust needs a way to say "field Q of struct T2 is a backpointer to field P of struct T1".

During pointer manipulation, that rule will momentarily be broken. But it's still checkable. It just needs some analysis. First, the checker would have to identify a block of code in which a backpointer was being manipulated, and locate the corresponding manipulation of the forward pointer. This is the code block of interest. It's an atomic transaction, in the database sense. Maybe the user would have to identify the code block with something like "atomic", with syntax like "unsafe".

Then, the checker would have to establish that if the invariant held at entry to the code block, it will hold at exit from the code block. This is a simple application of program verification technology. If the atomic section is small, this is not difficult.

Typical uses would be updating doubly-linked lists, rebalancing trees, and pulling part of a DOM-like tree out and moving it somewhere else.

This is one class of unsafe code - transient. It's the easiest to check, because it's a local problem. At the end of the code block, a safe state has been reestablished.

The second class of unsafe code involves partially valid data structures. This problem lies underneath "Vec", where the underlying block of storage has preallocated, uninitialized space for later growth. This is harder, because unsafe state persists outside unsafe code sections. To deal with this, it's necessary to somehow attach invariants to the data structure. If you have an array A which is valid from elements 0 to n, you need something like "valid_array(A,0,n)". Then, when you initialize an element n+1, you change the validity limits. The checker needs a few simple theorems, such as "valid_array(A,0,n) and valid_element(A[n+1)) implies valid_array(A,0,n+1)" to check this. This is old and completely automatable technology; we did it in the Pascal-F verifier 35 years ago, and Dafny does it today.

Handling these two classes of unsafe code takes care of a sizable fraction of the unsafe code really needed in Rust. With the support described above, most of the unsafe code in pure Rust could be eliminated. Outside of those two classes, most unsafe code in Rust involves external interfaces to other languages.

Unsafe code which doesn't fit into any of those classes needs to be looked at very hard.

Re: Rust Sucks If I Fail to Write X

#34

I think this misses the problem. Should you write your own data-structures? Not unless absolutely necessary. But mostly everyone knows that. So why are people complaining about data-structures? For me, writing the data-structures is the canary in the mine. It's the next step from hello world when trying to pick up a new language. Most importantly, trying to write a few simple data-structures hints at the difficulty t…

> For people like me, if writing trivial data-structures in Rust is a great challenge, it shows that writing other, less trivial things in Rust will be much more challenging than might be preferred. And this is the real issue, because your assumption doesn't really have any real basis. I don't mean to belittle your point, I can completely understand where you're coming from, but assuming that because writing data str…

Again, the issue isn't data-structures or about them.

The issue is: Can I write something in scratch in this language 1) at all and 2) with some amount of daily progress.

Writing data-structures is a test case of my ability to thing and program in the context of Rust. It serves to answer the question: Can I write a program that implements a well defined, well understood construct so that I may learn the building blocks of rust?

This leads up to an application, the behavior and design of which may not be extremely well defined in the context of Rust and requires more thinking when working out the data-structure in rust.

If the answer to "can I write a data-structure in Rust" is "Ya totally got this makes sense" then writing an application will be relatively easy.

However if the answer is "Wow I did it but there were a lot of pain points and I still have no idea if I've done it in the right or canonical way" then writing an application is going to be very difficult.

Re: Rust Sucks If I Fail to Write X

#35
post #32

I think this misses the problem. Should you write your own data-structures? Not unless absolutely necessary. But mostly everyone knows that. So why are people complaining about data-structures? For me, writing the data-structures is the canary in the mine. It's the next step from hello world when trying to pick up a new language. Most importantly, trying to write a few simple data-structures hints at the difficulty t…

> For people like me, if writing trivial data-structures in Rust is a great challenge, it shows that writing other, less trivial things in Rust will be much more challenging than might be preferred. I understand the source of the sentiment, but also disagree with it. I've been writing Rust code for years and have never had occasion to write my own custom data structure, and (discounting FFI) I've reached for the `uns…

Ive made a comment below, that I'm sure I'll make again (since I want to make it here).

So I've added to my original comment.

Re: Rust Sucks If I Fail to Write X

#36

Earlier quoted context omitted.

C++ programmers usually prefer contiguous data layout as well. I mean std::vector is just a contiguous array that dynamically reallocates and copies/move-constructs everything as needed. But many interesting data structures are hard to write in a memory-efficient manner without resorting to non-contiguous nodes. Even a hashtable often will use linked lists within each bucket for collision resolution. You can argue th…

How often do you really need those interesting structures(and the memory fragmentation that comes with them)? I've seen countless times where a developer reached for std::hash_map/linked_list when there will never be more than 10 values in their dataset. In that case an array would be at least as fast and much easier on your data layout. Also if you're trying to implement lockfree data structures then safe/unsafe poi…

When you need them you really need them. A Patricia Trie for example, which includes back pointers to ancestor nodes, is simply an ideal structure for prefix search.

Re: Rust Sucks If I Fail to Write X

#37

I think this misses the problem. Should you write your own data-structures? Not unless absolutely necessary. But mostly everyone knows that. So why are people complaining about data-structures? For me, writing the data-structures is the canary in the mine. It's the next step from hello world when trying to pick up a new language. Most importantly, trying to write a few simple data-structures hints at the difficulty t…

> For people like me, if writing trivial data-structures in Rust is a great challenge, it shows that writing other, less trivial things in Rust will be much more challenging than might be preferred. And this is the real issue, because your assumption doesn't really have any real basis. I don't mean to belittle your point, I can completely understand where you're coming from, but assuming that because writing data str…

>Data structures are a very specific domain, often very far away from what you'll be doing in the average "real" program.

I disagree. Choosing the right data structure often simplifies coding implementation and provides memory/performance guarantees.

And it's not only me that thinks that way either. Here's proof by Linus Torvalds (and a whole bunch of people on HN that agree with that sentiment)

https://news.ycombinator.com/item?id=4560334

Re: Rust Sucks If I Fail to Write X

#38
post #7

In my programming experience, there are two kinds of code: 1. Code where my objects form a tree. Rust's ownership model is great for this. 95% of my code looks this way naturally, and maybe another 3% can be rewritten to look like this. 2. Code where my objects form a complex graph. At this point, I need to make a choice between manual pointer management (C++, unsafe Rust) and a garbage collector (lots of languages).…

I've thought about this issue quite a bit because I had a use case (using scala) with lots of graphical data structures and GC mark phases were totally killing my performance, and I thought about using rust until I found out my graph shenanigans wouldn't work there either.

One of those hairbrained research-y ideas I have bouncing around in the back of my head is to fix this. The thing about graphical structures is that there is a huge body of work in graph theory that could be used to provably and deterministically cover >90% (ballpark) of these data structure use cases, but likely at the cost of compiler performance. And if I were even remotely competent with rust macros, I would totally hook up some annotation macro that would call out to Z3/CVC4 to determine satisfiability and then rewrite the code safely (even if it uses unsafe blocks under the covers) or throw an error. But thats for another time :)

Re: Rust Sucks If I Fail to Write X

#39

> As an aside, remember that the only difference to C/c++ is that if you write a “basic linked list” in them, all of your code will be unsafe. I stopped reading here.

What he's saying is correct: all C/C++ code operates in semantics equivalent to Rust's "unsafe" blocks.

Given that in unsafe block you still have to uphold the same invariants as in other blocks of code, your job is actually much harder in Rust that it is in C/C++.

Take a look at examples in [0], they would be perfectly valid in C/C++, but are potentially considered undefined behaviour in Rust.

[0] http://smallcultfollowing.com/babysteps/blog/2017/02/01/unsa...

Re: Rust Sucks If I Fail to Write X

#40

Earlier quoted context omitted.

> For people like me, if writing trivial data-structures in Rust is a great challenge, it shows that writing other, less trivial things in Rust will be much more challenging than might be preferred. And this is the real issue, because your assumption doesn't really have any real basis. I don't mean to belittle your point, I can completely understand where you're coming from, but assuming that because writing data str…

Again, the issue isn't data-structures or about them. The issue is: Can I write something in scratch in this language 1) at all and 2) with some amount of daily progress. Writing data-structures is a test case of my ability to thing and program in the context of Rust. It serves to answer the question: Can I write a program that implements a well defined, well understood construct so that I may learn the building bloc…

> If the answer to "can I write a data-structure in Rust" is "Ya totally got this makes sense" then writing an application will be relatively easy.

> However if the answer is "Wow I did it but there were a lot of pain points and I still have no idea if I've done it in the right or canonical way" then writing an application is going to be very difficult.

I feel like one of implicit points of the OP is that this isn't obviously true: writing a data structure is often a very different type of programming to writing a normal application. Most of the code I write isn't like a data structure, and is definitely not like a really good data structure: I can just glue together such code that others have written (or even I personally wrote once, a while ago) without having to worry about the details that it packages up/manages for me. (This is true in both Rust and C++, the latter of which I use day-to-day.)

Post reply on HN