[woolvalley]

From my friends that have tried rust, creating a graph or doubly linked list without using some special structures is fairly painful or impossible. You can create a graph by using some sort of adjacency matrix or some other kind of structure that keeps ownership in some sort of tree without much pain, but that has it's own downsides.

[rwmj]

This was also my experience. It's a fine language if you can't (or more usually "won't" for spurious reasons) use a garbage collector. However a lot of things are just easier to do using a GC, and I suspect in many, not all, of the use cases of Rust, a GC would be just fine.

(Also I have to rant here a bit: Yes I know the GC you used in Java or Emacs in 1997 was terrible, but modern GCs are very good indeed)

[tasty_freeze]

The garbage collector in 80s MS BASIC was incredibly inefficient. The routine was written on to minimize the amount of memory to perform the GC, something like 8 bytes.

It would simply iterate through every entry in the temp string stack and then all the entries in the symbol table to find the string with the lowest address above whatever was the previous lowest address. After that full sweep, it would move that string to its new home and adjust pointers to it, then set the new low bound to the string just identified. It would keep iterating until all strings had been visited.

As a result, it required (n2)/2 sweeps of memory (n=# of strings). Having BASIC lock up for 30 seconds every once in awhile was just how it went.

[ and in case someone is going to correct me, it might have swept from top of memory to bottom, I have forgotten the details ]

[woolvalley]

Graphs are OK in reference counting languages like swift / objective-c, it doesn't have to be done with a GC.

I think you could use Rc<Thing> in rust too if you want to solve it using rust, but then you have "swift with more boilerplate" as one friend said.

[rwmj]

Ref counting is a poor kind of garbage collection. In particular it has a very large overhead: typical GC has an overhead of a couple of bits per allocation, but ref counting usually wants to allocate an extra word (eg. 32 or even 64 bits) per allocation.

Another actually more serious problem is that typical ref counting implementations mix the allocated data with the references, so that when you inc/dec the reference you dirty a cache line containing the data. There exist implementations which improve on this by storing the references in a separate part of memory, but they are not how it's commonly implemented.

[mgsouth]

...annnnd this is probably a good example of the frustration that comes from solving familiar problems in a new paradigm, before the lightbulb clicks on.

Disclaimers: I'm only lightly familiar with Rust, and linked-lists are perfectly reasonable solutions _in the proper context and paradigm_.

So the problem to be solved is that we want to a) have collection of items which have a very strict ordering; b) be able to directly access the first and last item in that order; c) given a particular item, find the item which is immediately before/after it; d) when removing or adding an item, the relative ordering of the other items is undisturbed. Oh yeah, and e) we want it simple and efficient.

Doubly-linked lists are, of course, a very common solution used for these kinds of problems. They are perfectly suitable _if our paradigm is_ "I hereby assert that somehow, external to the compiler, I've verified that all list manipulation is being done correctly in all circumstances." If, however, our paradigm is "I want the compiler to automatically guarentee lots of these invariants" we run into some problems:

1) The data structure itself (each item has two pointers, and there are two global pointers for "head" and "tail") makes very few guarentees. Just one, actually: "each pointer will either point to an object, or will be null (or its moral equivalent)". There just isn't much compile-time meat for the compiler to chew on.

2) Linked-lists typically have (relatively) persistent scope, and exist outside of the lexical scope of whatever code block is immediately operating upon them. Again, it doesn't give the compiler much to go on.

3) Without managed memory (GC), there's no way for the compiler to guarentee that a pointed-to object still exists.

4) There's no built-in guarentee that the "head" and "tail" pointers actually point to the first/last object.

5) There's no guarentee of overall ordering (if a.next == b, then b.prev == a).

6) There's no guarentee of even a consistent view of the items in the collection (head == a, a.next == b, but b.prev == null/end-of-list).

7) There's no way for the compiler to guarentee, when viewing the collection as a whole, that modifications are atomic or thread-safe.

Yes, it's possible to take care of these issues in a non-Rust paradigm by making the structure of the list itself opaque, and only exposing insert/remove functions which enforce all the invariants. (I think Rust itself can do this with unsafe code.) However, you're still left with difficulties:

8) If list items are opaque containers, how do you guarentee that the payload object continues to exist?

9) How do you guarentee payload object ownership, atomicity, mutability, or other properties?

10) How do you guarentee that these needed invariants are held transitively?

Now the Rust paradigm, of course, isn't the only way to deal with these issues. But whether you're using Rust, managed-memory, C++ smart pointers, immutability guarentees, etc., you're going to need to do things that are unnatural in the other paradigms. Rust has the benefit of automatically enforcing lots of these invariants without having to do copying, worrying about shallow vs. deep copying, transitivey, etc.