Hacker News Reader

Comment by bsaul | Hacker News Reader

Every time i read about rust requiring you to use indices instead of pointers for some algorithm, i wonder if this isn't just rust forcing you to implement your own memory management, with your own local pointers.

View on HN

It pretty much is but with some fairly huge benefits:

* It's still memory safe (in the traditional sense). No chance of overwriting return addresses or whatever.

* It's type safe. There's no risk of type confusion. There's an excellent crate called `typed_index_collections` that lets you use a unique index type for each vector so the index is properly typed (i.e. you have `UserIndex` and `CommentIndex` or whatever and you can't mix them up).

* You don't need to do it for your entire program.

I have used this extensively in a profiler that worked on array oriented data structures. It worked great, especially because the data was immutable.

For mutable data it would probably work less well. I haven't tried that.

And in this particular case:

* You can choose to use handles smaller than a pointer.

* The NFA is cyclic, which makes memory management quite the chore. Even if you're using Rust's reference counted pointers. But if you use handles, the actual memory management becomes a lot simpler.

> * You can choose to use handles smaller than a pointer.

Did you measure any performance improvements due to using small handles?

I have a medium-sized project that uses a ton of `usize`s to reference elements in `Vec`s and would love to know if there's some potential for performance improvements there.

In this particular program I didn't do an in depth performance comparison because it wasn't really the point of the exercise.

But in the actual regex crate, I do indeed use `u32` as a representation for a handle. To a first approximation, it corresponds to about half as much memory usage.

Same deal with the aho-corasick crate.

What parts of my own memory management did I need to implement in this exercise? And how does its risks and rewards compare to the alternative in C (or Rust)?

We have a real program in front of us. Let's try to be concrete here please.

You would need to do the same in C++, since the underlying dynamic array is being resized throughout the algorithm, i.e. pointers to its elements are being invalidated. Except C++ won’t warn you about it. You’ll just corrupt memory.

And in garbage collected languages you’d do the same to avoid the cost of GC.

In C++ you can trivially opt out of using a dynamic array.

There are plenty of reasons not to use C++, including the lack of memory safety, but if you've already decided to ditch that, C++ does let you pick and choose which parts you want to use.

> does let you pick and choose which parts you want to use

Isn't that the case for most programming languages (ie, you can use the implementation you want/need), though?

Not to the extent of C++. E.g. you can't opt out of dynamic dispatch overhead in Ruby, because everything is method passing, but "virtual" in C++ is a choice.

The commitment to ensure that features do not add cost(memory, runtime) if you don't use them is something fairly uncommon in other languages, and many languages have features you can't meaningfully avoid.

You don't have to use an array based on realloc. You can use a vector based on linked list of memory pages, or linked list if you need deletion (or gap buffer or any other data structure depends on your needs).

And at that point you’re slower.

Even if it's the case, local pointers are at least better than unrestricted global pointers for the same reason that local variables are better than unrestricted global variables. One difference is that local variables generally need no reasoning to prove their safety while local pointers may need one, but that's rather a job for abstractions.

I agree, but if that's the case, then maybe zig's philosophy of simply creating local memory allocators really is the good pattern ?

Yes, it is indeed a good trade-off. That strategy is called a region-based memory management in general, and in fact Rust's borrow checker is its generalization, automatically generating fine-grained small regions that are called "lifetimes" ;-) So they are valid approaches, just that Rust borrow checking is much broader that safe Rust covers wide use cases.

Isn’t it essentially the same pattern except unsafe if you don’t have a borrow checker?

If you have indices into an array you need access to that array, once the array is gone the indexes are “dead”.

If you have pointers into local memory without any sort of borrow checking once the local memory is gone you have UAFs.

Sort of. They do make many patterns far easier to reason about also without help. E.g. in this case, for any memory only used internally by the parser and NFA, guaranteeing that indices or pointers to the underlying memory isn't leaked at all is often fairly easy, and certainly easier than trying to keep precise track of what to free when.

Having it done for you automatically is certainly even better, but if you're first saddled with manual memory management, it's better than nothing.

Most of the time you don't need to do this, usually its the solution for when creating a graph structure with cyclic references.

But when you do, and your data is mutable, generational indices are a legit and very useful strategy that is used in C/C++ too.

See this: https://floooh.github.io/2018/06/17/handles-vs-pointers.html

I think another solution could be to use an arena/memory pool to replace indices with references.

But indices are still safer than raw pointers - vec access does bounds checks. You can make indices typed if you’re worried about mixing them up.

I mentioned slab/bump allocators in the README. But whether it works with the Ptrlist type punning is unclear to me.

That's correct. And you operate with weak pointers at that moment with no help from the type system. So basically that's all about bypassing the too incomplete type system.

It's because borrow checker is very restrictive. Indices are a sanity escape!

Reply on news.ycombinator.com