←back to thread

Indices, not Pointers

(joegm.github.io)
102 points vitalnodo | 1 comments | | HN request time: 0s | source
Show context
skulk ◴[] No.45111204[source]
This is a very tempting and commonly used strategy in Rust to bypass the borrow checker. I've used it to implement tries/DFAs with great success (though I can't find the code anymore)
replies(3): >>45112462 #>>45112631 #>>45114374 #
Animats ◴[] No.45112631[source]
The trouble is, you've just replicated the problems of raw pointers. You can have dangling indices if the underlying object is reused or cleared. You can have aliasing, with two indices to the same object.

It's a problem in practice. Of the three times I've ever had to use a debugger on Rust code, two came from code someone had written to do their own index allocation. They'd created a race condition that Rust would ordinary prevent.

replies(3): >>45113452 #>>45121307 #>>45124000 #
1. rstuart4133 ◴[] No.45121307[source]
> You can have dangling indices if the underlying object is reused or cleared.

You can just wrap your pointers, and then say the underlying collection they point to must outlive the pointers returned. Granted, that doesn't work so well if the collection allows removal. But if your collection is append only you've hit the sweet spot for this pattern, because with the lifetime constrained pointers and no deletions literally nothing can go wrong.

He says he's only seen it in Zig. I guess that means he hasn't done much Rust, because the Rust nudges you in that direction. Wrapped pointers are common in the language and it's libraries. They aren't used to save space. They are used to get around lifetime restrictions.

When I've done it in Rust, it has been to save space. A u32 index occupies 1/4 of the space of an Rc on 64 bit. If you're handling millions of them, it's hard to ignore. Ditto using u16 offsets to describe slices into strings I know won't be more than 64k. Again, it's a 4 fold saving on 64 bit.