3 ms·

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

by bsaul 3y ago

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.

ernst_klim 3y ago
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.
lifthrasiir 3y ago
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.
- bsaul 3y ago
  I agree, but if that's the case, then maybe zig's philosophy of simply creating local memory allocators really is the good pattern ?
  - lifthrasiir 3y ago
    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.
  - masklinn 3y ago
    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.
    - vidarh 3y ago
      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.
yagni_dev 3y ago
It's because borrow checker is very restrictive. Indices are a sanity escape!
yakubin 3y ago
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.
- vidarh 3y ago
  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.
  - spoiler 3y ago
    > 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?
    - vidarh 3y ago
      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.
- ernst_klim 3y ago
  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).
  - yakubin 3y ago
    And at that point you’re slower.
burntsushi 3y ago
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.
IshKebab 3y ago
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.
- burntsushi 3y ago
  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.
  - muldvarp 3y ago
    > * 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.
    - burntsushi 3y ago
      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.
zackoverflow 3y ago
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 https://floooh.github.io/2018/06/17/handles-vs-pointers.html
pornel 3y ago
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.
- burntsushi 3y ago
  I mentioned slab/bump allocators in the README. But whether it works with the Ptrlist type punning is unclear to me.

by bsaul 3y ago

ernst_klim 3y ago

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.

lifthrasiir 3y ago

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.

bsaul 3y ago
I agree, but if that's the case, then maybe zig's philosophy of simply creating local memory allocators really is the good pattern ?
- lifthrasiir 3y ago
  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.
- masklinn 3y ago
  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.
  - vidarh 3y ago
    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.

yagni_dev 3y ago

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

yakubin 3y ago

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.

vidarh 3y ago
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.
- spoiler 3y ago
  > 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?
  - vidarh 3y ago
    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.
ernst_klim 3y ago
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).
- yakubin 3y ago
  And at that point you’re slower.

burntsushi 3y ago

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.

IshKebab 3y ago

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.

burntsushi 3y ago
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.
- muldvarp 3y ago
  > * 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.
  - burntsushi 3y ago
    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.

zackoverflow 3y ago

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 https://floooh.github.io/2018/06/17/handles-vs-pointers.html

pornel 3y ago

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.

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