11 ms·

I'd take a similar approach. After all `unsafe` use cases include the implementation of data structures.

Animats 9y ago
I've argued this issue before. The answer isn't generics, Coq, or some fancy type system nobody will understand or use properly. There are only a few inherent trouble spots in pure Rust code safety. The big two are: - Partially initialized arrays. "Vec" has to be unsafe because growing an array involves uninitialized slots. You just need a way to say "this array is initialized from 0..N only", where N is in a data structure associated with the array. Then you need an operation that says "initialize entry N+1 and update the count". That's all it takes. "Map" could be implemented on top of "Vec", instead of using unsafe code. It would be worth trying this and seeing what the performance penalty is. That may be a premature optimization. - Backpointers. Backpointers have an easily checked invariant relationship with the forward pointer that owns their containing object, but there's no way to tell the language that something is a backpointer.
- a_t48 9y ago
  A hashmap being implemented on top of vectors is a pretty common implementation. Not sure what Rust uses though.
  - __s 9y ago
    Problem is avoiding having to do Vec<Option<T>>
    - Animats 9y ago
      If T is a reference type, doesn't Rust do an optimization where <Option<T>>> is implemented by using null pointers?
      - kevincox 9y ago
        Yes. This optimization is expected to be expanded in the future but there are currently "NonZero" types. Rust notices this and uses the zero value as the enum descriminant. So in this case the code generated is idential to a nullable pointer.
      - sanxiyn 9y ago
        Yes, but that doesn't help when T is not a reference type.
        Animats 9y ago
        If it's not a reference type, then the Option enum value is probably small relative to the rest of the data in the type.
        __s 9y ago
        Option<i32> is 8 bytes
  - cesarb 9y ago
    IIRC, Rust's HashMap uses a single raw vector containing for each entry its hash code, its key, and its value; empty entries have a special hash code as a marker, with the key/value left uninitialized. Also, the hashes are kept together (separate from the rest) for better cache behavior during the linear probing.
    - a_t48 9y ago
      Wouldn't that be two parallel vectors? (Side note: nobody ever thinks to bring up cache behavior in interviews where I ask about how a hash map could be implemented - it's nice to know that the library writers care :) ) How does that special hash marker work? What happens when something actually hashes to it? Just silently increment the hash?
      - cesarb 9y ago
        > Wouldn't that be two parallel vectors? Yes, but it's a single contiguous memory allocation. (It used to be three parallel vectors in a single allocation, with keys and values also kept separate to avoid padding between them, but experiments showed that had worse cache behavior.) > How does that special hash marker work? What happens when something actually hashes to it? Just silently increment the hash? Looking at the code, it always sets the most significant bit of every real hash value (since the least significant bits select the bucket, it makes no difference), and the marker has the most significant bit clear (in fact, all bits of the marker value are clear).
        a_t48 9y ago
        Oh, clever. Of course you can do it that way.
- __s 9y ago
  Good Map implemented on top of Vec: https://github.com/bluss/ordermap https://github.com/bluss/ordermap
  - Animats 9y ago
    Very nice.
  - childintime 9y ago
    This is a PHP map, correct? It is the one language feature that made PHP stand out from the crowd.
    - __s 9y ago
      Python has followed suit
- catnaroek 9y ago
  > The answer isn't generics, Coq, or some fancy type system nobody will understand or use properly. The solution is a formal semantics for unsafe Rust, so that programmers can prove that their unsafe Rust code is safe to use by whatever means they prefer. (Mine would be by hand.) --- Reply to dmix: A formal semantics doesn't have to be particularly fancy, although in Rust's case, it will in most likelihood not be straightforward either.
  - dmix 9y ago
    Is that a fancy <x> system that nobody will understand or use properly? (Honest question)
    - steveklabnik 9y ago
      We intend for it not to be; more on that as we get closer to actually having a model.
    - Animats 9y ago
      Probably. I used to do formal proof of correctness work and headed a project to build a verifier.[1] That stuff is very hard. The partially initialized array thing is an issue of expressive power. You can't talk about that in Rust yet. This is a classic issue. The three big headaches in C around memory safety are "how big is it", "who owns it", and "who locks it". The language lacks the syntax to even talk about those issues. Rust can talk about those, which is a huge step forward. Before you can even consider verifying something, you have to be able to talk about it in some formal language. Preferably the one you're programming in. Having to do formal specifications in a separate language is a huge headache. Been there, done that. There are a few standard trouble spots. I've listed two of them. Most other unsafe code comes from 1) Foreign functions, which can be expected to decline over time as more libraries are implemented in Rust. (How's SSL/TLS in Rust coming along?) 2) "Optimization", which may be premature. This usually consists of bypassing subscript checks. I'd rather have the subscript checks on all the time, and see effort put into hoisting subscript checks out inner loops. (Subscript checks that aren't in inner loops usually aren't significant overhead items.) 3) replicating C/C++ code in Rust. (An early attempt was a transliteration of Doom into Rust, with lots of pointer arithmetic.) Remember, it can blow at any seam. It only takes one buffer overflow to allow an exploit. [1] https://github.com/John-Nagle/pasv https://github.com/John-Nagle/pasv

I've argued this issue before. The answer isn't generics, Coq, or some fancy type system nobody will understand or use properly. There are only a few inherent trouble spots in pure Rust code safety. The big two are: - Partially initialized arrays. "Vec" has to be unsafe because growing an array involves uninitialized slots. You just need a way to say "this array is initialized from 0..N only", where N is in a data structure associated with the array. Then you need an operation that says "initialize entry N+1 and update the count". That's all it takes. "Map" could be implemented on top of "Vec", instead of using unsafe code. It would be worth trying this and seeing what the performance penalty is. That may be a premature optimization. - Backpointers. Backpointers have an easily checked invariant relationship with the forward pointer that owns their containing object, but there's no way to tell the language that something is a backpointer.

a_t48 9y ago
A hashmap being implemented on top of vectors is a pretty common implementation. Not sure what Rust uses though.
- __s 9y ago
  Problem is avoiding having to do Vec<Option<T>>
  - Animats 9y ago
    If T is a reference type, doesn't Rust do an optimization where <Option<T>>> is implemented by using null pointers?
    - kevincox 9y ago
      Yes. This optimization is expected to be expanded in the future but there are currently "NonZero" types. Rust notices this and uses the zero value as the enum descriminant. So in this case the code generated is idential to a nullable pointer.
    - sanxiyn 9y ago
      Yes, but that doesn't help when T is not a reference type.
      - Animats 9y ago
        If it's not a reference type, then the Option enum value is probably small relative to the rest of the data in the type.
        __s 9y ago
        Option<i32> is 8 bytes
- cesarb 9y ago
  IIRC, Rust's HashMap uses a single raw vector containing for each entry its hash code, its key, and its value; empty entries have a special hash code as a marker, with the key/value left uninitialized. Also, the hashes are kept together (separate from the rest) for better cache behavior during the linear probing.
  - a_t48 9y ago
    Wouldn't that be two parallel vectors? (Side note: nobody ever thinks to bring up cache behavior in interviews where I ask about how a hash map could be implemented - it's nice to know that the library writers care :) ) How does that special hash marker work? What happens when something actually hashes to it? Just silently increment the hash?
    - cesarb 9y ago
      > Wouldn't that be two parallel vectors? Yes, but it's a single contiguous memory allocation. (It used to be three parallel vectors in a single allocation, with keys and values also kept separate to avoid padding between them, but experiments showed that had worse cache behavior.) > How does that special hash marker work? What happens when something actually hashes to it? Just silently increment the hash? Looking at the code, it always sets the most significant bit of every real hash value (since the least significant bits select the bucket, it makes no difference), and the marker has the most significant bit clear (in fact, all bits of the marker value are clear).
      - a_t48 9y ago
        Oh, clever. Of course you can do it that way.
__s 9y ago
Good Map implemented on top of Vec: https://github.com/bluss/ordermap https://github.com/bluss/ordermap
- Animats 9y ago
  Very nice.
- childintime 9y ago
  This is a PHP map, correct? It is the one language feature that made PHP stand out from the crowd.
  - __s 9y ago
    Python has followed suit
catnaroek 9y ago
> The answer isn't generics, Coq, or some fancy type system nobody will understand or use properly. The solution is a formal semantics for unsafe Rust, so that programmers can prove that their unsafe Rust code is safe to use by whatever means they prefer. (Mine would be by hand.) --- Reply to dmix: A formal semantics doesn't have to be particularly fancy, although in Rust's case, it will in most likelihood not be straightforward either.
- dmix 9y ago
  Is that a fancy <x> system that nobody will understand or use properly? (Honest question)
  - steveklabnik 9y ago
    We intend for it not to be; more on that as we get closer to actually having a model.
  - Animats 9y ago
    Probably. I used to do formal proof of correctness work and headed a project to build a verifier.[1] That stuff is very hard. The partially initialized array thing is an issue of expressive power. You can't talk about that in Rust yet. This is a classic issue. The three big headaches in C around memory safety are "how big is it", "who owns it", and "who locks it". The language lacks the syntax to even talk about those issues. Rust can talk about those, which is a huge step forward. Before you can even consider verifying something, you have to be able to talk about it in some formal language. Preferably the one you're programming in. Having to do formal specifications in a separate language is a huge headache. Been there, done that. There are a few standard trouble spots. I've listed two of them. Most other unsafe code comes from 1) Foreign functions, which can be expected to decline over time as more libraries are implemented in Rust. (How's SSL/TLS in Rust coming along?) 2) "Optimization", which may be premature. This usually consists of bypassing subscript checks. I'd rather have the subscript checks on all the time, and see effort put into hoisting subscript checks out inner loops. (Subscript checks that aren't in inner loops usually aren't significant overhead items.) 3) replicating C/C++ code in Rust. (An early attempt was a transliteration of Doom into Rust, with lots of pointer arithmetic.) Remember, it can blow at any seam. It only takes one buffer overflow to allow an exploit. [1] https://github.com/John-Nagle/pasv https://github.com/John-Nagle/pasv