I thought there were ways to do it, just not the obvious most efficient ones. If you really *can't*, that makes me a lot more skeptical of the whole Rust model...
-
-
Yes. You can implement naive linked lists without unsafe.
1 reply 0 retweets 4 likes -
OK. I meant that if the type system Rust bases its memory-safety on didn't admit *any* way to do linked lists without unsafe, the whole formalism would be a lot less impressive/valuable than I thought it was...
2 replies 0 retweets 0 likes -
I didn't even know it was possible, now I want to learn what a linked list looks like without using unsafe
2 replies 0 retweets 2 likes -
Replying to @andy_kelley @RichFelker and
use Rc and Weak Presumably y'all are talking about doubly linked lists, singly linked lists are possible to do efficiently in safe code
4 replies 0 retweets 6 likes -
Replying to @ManishEarth @andy_kelley and
There's also the possibility of using non-pointer references to represent the graph, such as indices into an array or some other pool data structure that holds the nodes
4 replies 0 retweets 8 likes -
Replying to @jckarter @andy_kelley and
Oh yeah, that works too. That's almost as efficient as the unsafe version
2 replies 0 retweets 1 like -
Replying to @ManishEarth @andy_kelley and
Yep, and you have the opportunity to use a type that's smaller than a pointer, or one that's stable when serialized to disk or mapped into another process or device
1 reply 0 retweets 3 likes -
Replying to @jckarter @ManishEarth and
I think calling that a linked list is a bit of a stretch though. It certainly wouldn't satisfy most people arguing about Rust being bad.
3 replies 0 retweets 0 likes -
Replying to @Brittain_Ben @ManishEarth and
IMO, data structures are really about the structure, not the mechanism by which the structure is represented. C has promoted a pointer-centric view of the world, but pointers aren't the one and only way to build graphs, and they have their own tradeoffs
1 reply 1 retweet 4 likes
Exactly. Which GPU programming makes very clear :) In OpenGL pre-4.7 or so your GPU model doesn’t even *have* the concept of pointer addresses. They’re completely abstracted away from you, so indices are the only option.
-
-
It turns out that doing things with indices is often good practice even with GPU APIs that allow raw pointer address manipulation, simply so that you don’t have to keep CPU and GPU side addresses straight.
3 replies 0 retweets 2 likes -
One interesting data point: In Servo Layout 2020 I suggested to
@SimonSapin to try indices, but it quickly proved to be a bad idea because of concurrency concerns (we want parallel layout). We ended up just using *singly* linked trees, which worked surprisingly well!1 reply 0 retweets 2 likes - 3 more replies
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.