Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Learn Rust with entirely too many linked lists (2019)

rust-unofficial.github.io

Post reply on HN
Print view View original

171–179 of 179 posts

Re: Learn Rust with entirely too many linked lists (2019)

#171

Post by dodobirdlord »

dmitrygr wrote: post #150
dodobirdlord wrote: post #114

Earlier quoted context omitted.

Rust's ownership rules aren't for the purpose of making the user's life hard, they are the least restrictive system that could be devised that allow the compiler to uphold Rust's safety guarantees. It was not too long ago that it was common knowledge that a programming language either has a garbage collector or has manual memory management, or possible both. Safe Rust has neither, but not without the effect of making…

> You could put all of your graph nodes into a linear data structure like an array, and have them point to each other by holding a list of indices instead of a list of pointers Rust practitioners keep proposing this solution. It is like you have never heard of caches or do not understand that modern CPUs have multiple special prefetchers for pointer chasing and no prefetchers for "rust fanatics" This solution will be…

I don’t do much graph programming, and the few pieces of graph programming I’ve had to work with that needed to be high-performance fit in L1/L2. But for most non-pathological graphs (treelike, few backlinks from nodes deep in the graph to nodes shallow in the graph, nodes are small) you could arrange a statistical locality property that child nodes are usually located at nearby greater indices. Most operations on the graph would sweep left->right in small strides likely to be either within the a cache page or onto a page that has been prefetched by the linear memory access pattern prefetcher.

Certainly this is more awkward to write than pointer linking, but approximately the same performance should be achievable for sparse or treelike graphs. If you need to work with dense graphs larger than the size of the cache performance will suffer a lot, but this meets the criteria to justify using unsafe, at which point the implementation would look a lot like a C implementation.

Re: Learn Rust with entirely too many linked lists (2019)

#172

Post by josteink »

Animats wrote: post #88

Doubly-linked lists are hard with Rust's ownership system. I've argued for Rust having backpointers as a built-in type the borrow checker understands. You have to maintain the invariant that if A points to B, B points back to A. A is an owning pointer, and B is a non-owning pointer locked in a relationship with A. Easy to check if the language lets you say that's what you're doing. Rust lacks that. If you have safe b…

> I've argued for Rust having backpointers as a built-in type the borrow checker understands. You have to maintain the invariant that if A points to B, B points back to A. A is an owning pointer, and B is a non-owning pointer locked in a relationship with A.

Or you could simply give it a new type/semantic: owner.

You could even use a familiar unix-shorthand for it: ~. Thus Node will have a Parent: ~Node, which you can pass by ~self.

And graphs would suddenly be nice to work with.

> Rust lacks that.

I can’t be the only one who finds that ironic?

And I say that as someone who likes rust.

Re: Learn Rust with entirely too many linked lists (2019)

#174

Post by jdsully »

blub wrote: post #167
jdsully wrote: post #71

Earlier quoted context omitted.

The comment applies word for word to C++ as well. Linked lists are just bad datastructures for modern CPUs. I don’t use rust so I can’t speak to the quality of the std lib, but I don’t think its fair to use the parent comment as evidence either way.

No, it doesn't apply to C++ because the corners of the language required to write lists and trees are exercised enough and don't suffer from unexpected limitations.

The comment originating this discussion provides no evidence in any direction on the quality of the rust standard library. Merely that you wouldn't use these in practice, nor would you in C++.

Re: Learn Rust with entirely too many linked lists (2019)

#175

Post by steveklabnik »

josteink wrote: post #172
Animats wrote: post #88

Doubly-linked lists are hard with Rust's ownership system. I've argued for Rust having backpointers as a built-in type the borrow checker understands. You have to maintain the invariant that if A points to B, B points back to A. A is an owning pointer, and B is a non-owning pointer locked in a relationship with A. Easy to check if the language lets you say that's what you're doing. Rust lacks that. If you have safe b…

> I've argued for Rust having backpointers as a built-in type the borrow checker understands. You have to maintain the invariant that if A points to B, B points back to A. A is an owning pointer, and B is a non-owning pointer locked in a relationship with A. Or you could simply give it a new type/semantic: owner. You could even use a familiar unix-shorthand for it: ~. Thus Node will have a Parent: ~Node , which you c…

It is not particularly ironic; there's no actual design here. It's easy to say that a feature should exist (and your parent has said this, about this, repeatedly) but it's much harder to make sure that it's something that has the correct semantics (and your parent has never actually produced this, even though they've been asked, repeatedly.).

(See the sibling comment by dan-robinson for just some of the issues here)

Re: Learn Rust with entirely too many linked lists (2019)

#176

Post by eximius »

wruza wrote: post #165
eximius wrote: post #103

Earlier quoted context omitted.

Rust has a concept of ownership and borrowing. (I think) everything is fine when you just have immutable references everywhere. But as soon as you start taking mutable references (of which only one can exist at a time) or ownership (stronger than mutable references), then cycles break things. You can get around it with Interior Mutability, it's just slightly more verbose. Also, it isn't really that they made an easy…

Complete blind guess here, but maybe a safest language could “borrow” from accounting systems. Basic idea is that you don’t need to validate every step as long as the outcome of a specific set of operations is atomically valid. Some SQL have it, like checks on foreign keys and column check-exprs on commit, not on insert (that’s how you make back-refs by {insert; insert}, and not {insert; insert null; update}, which i…

That's kind of how unsafe rust works, except that the compiler doesn't check that you maintained the variants. Your unsafe code is expected to conform such that safe code interacting with it is safe.

> But a solution to this problem is articulated easily: adjust corresponding nodes if this one goes away. It could help with that instead of just exposing,

Articulating things easily doesn't mean they are easy. Now every value needs a backreference to every value that holds it and, during its destructor (which isn't guaranteed to run), it has to make those held references invalid?

I know just enough to know how difficult the problem is, in the general case. The folks thinking about these problems for their day jobs have looked into a lot of simple solutions and they fall apart in cases that are too common or too valuable to no support.

Re: Learn Rust with entirely too many linked lists (2019)

#177

Post by josteink »

steveklabnik wrote: post #175
josteink wrote: post #172

Earlier quoted context omitted.

> I've argued for Rust having backpointers as a built-in type the borrow checker understands. You have to maintain the invariant that if A points to B, B points back to A. A is an owning pointer, and B is a non-owning pointer locked in a relationship with A. Or you could simply give it a new type/semantic: owner. You could even use a familiar unix-shorthand for it: ~. Thus Node will have a Parent: ~Node , which you c…

It is not particularly ironic; there's no actual design here. It's easy to say that a feature should exist (and your parent has said this, about this, repeatedly) but it's much harder to make sure that it's something that has the correct semantics (and your parent has never actually produced this, even though they've been asked, repeatedly.). (See the sibling comment by dan-robinson for just some of the issues here)

The absolute simplest semantic I can come up with here (too simple?) would be for a struct containing a non-null owner-pointer to be bound by its owner’s ownership/lifetime-scope.

For most commonly used graph-types this should lead to pretty simple one-directional ownership chains which should be doable (although probably not trivial) for a compiler to enforce.

Re: Learn Rust with entirely too many linked lists (2019)

#178

Post by wruza »

eximius wrote: post #176
wruza wrote: post #165

Earlier quoted context omitted.

Complete blind guess here, but maybe a safest language could “borrow” from accounting systems. Basic idea is that you don’t need to validate every step as long as the outcome of a specific set of operations is atomically valid. Some SQL have it, like checks on foreign keys and column check-exprs on commit, not on insert (that’s how you make back-refs by {insert; insert}, and not {insert; insert null; update}, which i…

That's kind of how unsafe rust works, except that the compiler doesn't check that you maintained the variants. Your unsafe code is expected to conform such that safe code interacting with it is safe. > But a solution to this problem is articulated easily: adjust corresponding nodes if this one goes away. It could help with that instead of just exposing, Articulating things easily doesn't mean they are easy. Now every…

Unsafe is not any kind of transaction, it is a deal under the bridge, quite the opposite. Actix author fell victim of that recently, iirc. Anyway, I’m not arguing, it is clear how microcontrol works. My concern is why to do it so hard for a developer to reason about referential balance, when a machine exists.

>Now every value needs a backreference to every value that holds it

If it didn’t, wouldn’t that be out of scope of graph/dl-list discussion?

It is interesting that solutions fall apart, because it seems like a warehouse-level problem to me. Any code path is just +1 -1 countable references with some matching-branching in the end. Are these design discussions archived somewhere, like a mailing list / technical rationale talks?

ps. I did not mean anything like “rust magically freeing graphs”. Only that “transaction {shuffle} check” thing. Like in physics, N spin in, N spin out, what’s where is not important, since nothing lost.

Re: Learn Rust with entirely too many linked lists (2019)

#179

Post by Hello71 »

nicoburns wrote: post #168
Hello71 wrote: post #60

Earlier quoted context omitted.

Allegedly, some platforms have pointer trap representations, where a certain pointer can be created, but may not be used in any operations of that type. No modern systems have such trap representations for pointer types, but the C standard inherits their legacy, and, more importantly, C compilers use it as justification for certain types of optimizations. Since it's not a hardware limitation, Rust can perfectly well…

> C compilers use it as justification for certain types of optimizations I believe that the Rust compiler is free to make it's own choices about what is considered valid, and which optimisations it wants to enable. It doesn't need to follow C's lead here.

isn't that what I said
Post reply on HN