[skybrian]

There are benefits but they come with downsides: you can have node ids pointing to deleted nodes, and collecting unused nodes is up to you. If you want to avoid fragmentation, you need to recycle nodes and possibly node ids as well. These are things garbage collectors handle.

It's not all that different from a database, though.

[Twisol]

> It's not all that different from a database, though.

Indeed! I'm tempted to coin a variant of Greenspun's Tenth Rule: any sufficiently complicated program contains an ad-hoc, informally specified, bug-ridden, incomplete implementation of a database engine.

> There are benefits but they come with downsides

Downsides relative to what? The downsides listed are all in common with traditional pointer-based references, so I would argue that garbage collection is rather orthogonal to the question of storing indices instead of pointers. Any allocation comes out of a memory arena of some kind, be it an explicit vector of slots or the implicitly-defined standard heap. The tools for solving these problems are the same in all cases.

Certainly, Rust's references avoid all of the problems you listed. Rust pointers essentially embed the semantics of a garbage collector at compile-time [0], in the domain where ownership patterns can be strictly verified. But nodes within a graph are already a poor fit for the ownership model -- the entity that "owns" a node is really the graph itself, not its neighbors -- so that's the level of granularity at which Rust's references are useful. You need something else within the scope of the graph.

EDIT: On reflection, you might be referring to a language like Java which has an ambient global garbage collector. Indeed, using indices instead of pointers means you're on your own -- you've allocated the memory arena through the standard means, but then you take on the responsibility of managing that memory yourself. This is a fair criticism! Purely in my experience, data modeled as a loose graph of directly-related objects is a lot more difficult to understand and maintain than data modeled indirectly using some form of identifier -- mostly because of the effects I mentioned in my earlier post on associating new information to an entity.

[0] https://words.steveklabnik.com/borrow-checking-escape-analys...

[skybrian]

Yes, that's what I meant. Cleaning up unreferenced nodes (should you want to do that) would require some kind of mini-garbage collection algorithm. And indeed, git has a gc command to do this, even though reference counting would work for a DAG. It's doable, but it's not what I'd call simple.

But if you know through some other means the exact time when a node should be deleted, you can delete it at that time, and anyone following a soft reference will find that it's no longer there, which may be a way of catching a bug. This is how both databases and entity component systems work. But it does mean that resolving a reference can fail, and you have to handle that somehow.

[steveklabnik]

Recycling IDs is pretty easy with generational indices.

[fulafel]

Does specs provide answers to these issues?