use Rc and Weak Presumably y'all are talking about doubly linked lists, singly linked lists are possible to do efficiently in safe code
-
-
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 -
Replying to @jckarter @Brittain_Ben and
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.
1 reply 0 retweets 1 like -
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 -
Replying to @pcwalton @Brittain_Ben and
Interesting, what were the concurrency concerns?
2 replies 0 retweets 0 likes
Our tree traversal is complex, but the basic invariant is that every thread needs to have exclusive access to its subtree and can farm out jobs to disjoint subtrees in fork-join style. Enforcing this invariant is hard unless you lean on unique ownership
-
-
Old Servo layout tried to address this by shoehorning everything into a small fixed number of traversal patterns, but this turns out to be too rigid for CSS layout, which needs lots of ad-hoc traversals.
0 replies 1 retweet 3 likesThanks. Twitter will use this to make your timeline better. UndoUndo
-
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.