3 ms·

A hashmap being implemented on top of vectors is a pretty common implementation. Not sure what Rust uses though.

by a_t48 9y ago

__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.

A hashmap being implemented on top of vectors is a pretty common implementation. Not sure what Rust uses though.

by 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.