11 ms·

> Is the hope to avoid paying the cost of an extra pointer dereference when we're using the first map? Or does independently allocating each object hurt cache l

> Is the hope to avoid paying the cost of an extra pointer dereference when we're using the first map? Or does independently allocating each object hurt cache locality or something like that? Both. In practice, I probably wouldn’t use a hashmap for the first container that actually owns these items. When I do expect gigabytes of data, in C++ I use something like vector<vector<tValue>>, where the inner vectors are of the same fixed size (except for the last one), e.g. 2-16MB RAM / each. If I need to erase elements, I include a free list such as this one: https://github.com/Const-me/CollectionMicrobench/blob/master/Source/PlexAlloc/FreeList.hpp https://github.com/Const-me/CollectionMicrobench/blob/master... But the exact container is not that important here. If you don’t have that many values, it can as well be a standard vector. The point is, C++ allows composing these containers making higher-level ones, such as this indexed array example, using pointers to link individual items across them. This feature allows building sophisticated and efficient data structures that are still possible to reason about.

burntsushi 9y ago
Right, and I don't understand why you think that same exact approach wouldn't work in Rust either. If you have a `Vec<Vec<tValue>>`, then you can spread all the raw pointers you want everywhere without any additional boxing of `tValue`, and you know exactly when those pointers might become invalidated: whenever you call an `&mut` method on your `Vec<Vec<tValue>>` (or rather, on one of the interior `Vec<tValue>`s). Because of that, you can even build safe abstractions on top of such data structures such that your callers can't possibly misuse it (without themselves using `unsafe`). The technique of giving stable addresses to things by stuffing them into vectors isn't unique to C++. People do it in Rust too: https://github.com/SimonSapin/rust-typed-arena/blob/master/src/lib.rs https://github.com/SimonSapin/rust-typed-arena/blob/master/s...
- Const-me 9y ago
  The exact container is not that important here. The point is, C++ allows composing these containers making higher-level ones, such as this indexed array example. They can be standard, third-party, my own, I still can compose them. About my particular example, I’m not sure you can easily implement a free list in rust, to reuse space from de-allocated items. Especially if these items have non-empty constructor and destructor.
  - burntsushi 9y ago
    > The point is, C++ allows composing these containers making higher-level ones, such as this indexed array example. What I---and others---are trying to tell you is that it's perfectly possible in Rust too. I don't think you've pointed out anything that isn't possible in Rust. My previous comment was exactly about composing containers to make higher-level ones. Have you tried building such things? Did you get stuck? Maybe someone can help. > About my particular example, I’m not sure you can easily implement a free list in rust, to reuse space from de-allocated items. Especially if these items have non-empty constructor and destructor. I don't see any reason why implementing a free list in Rust wouldn't be possible either.
    - Const-me 9y ago
      > I don't see any reason why implementing a free list in Rust wouldn't be possible either. Is placement new available in rust stable?
      - burntsushi 9y ago
        Why do you think placement new is necessary to implement a free list?
    - oconnor663 9y ago
      It seems like one of Const-me's objections is that Rust data structures like HashMap don't document a lot of guarantees about when they would and wouldn't invalidate unsafe interior pointers. That said, for Vec in particular, Rust actually makes a ton of guarantees about its layout (more that C++ std::vector I think): https://doc.rust-lang.org/std/vec/struct.Vec.html https://doc.rust-lang.org/std/vec/struct.Vec.html
      - Const-me 9y ago
        Correct. While vectors are comparable, C++ also guarantees a lot about the rest of the containers. E.g. unordered associative containers never expire pointers to keys or values. Linked lists never expire pointers nor iterators. In C++ I can create an efficient LRU cache in a dozen lines of code, combining list<const tKey* > with unordered_map<tKey, struct{tValue, list<const tKey* >::iterator}> (this implies tKey is not an int, otherwise list<tKey> is more efficient). Rust’s built-in LinkedHashMap had to reimplement a linked list instead.

burntsushi 9y ago

Right, and I don't understand why you think that same exact approach wouldn't work in Rust either. If you have a `Vec<Vec<tValue>>`, then you can spread all the raw pointers you want everywhere without any additional boxing of `tValue`, and you know exactly when those pointers might become invalidated: whenever you call an `&mut` method on your `Vec<Vec<tValue>>` (or rather, on one of the interior `Vec<tValue>`s). Because of that, you can even build safe abstractions on top of such data structures such that your callers can't possibly misuse it (without themselves using `unsafe`). The technique of giving stable addresses to things by stuffing them into vectors isn't unique to C++. People do it in Rust too: https://github.com/SimonSapin/rust-typed-arena/blob/master/src/lib.rs https://github.com/SimonSapin/rust-typed-arena/blob/master/s...

Const-me 9y ago
The exact container is not that important here. The point is, C++ allows composing these containers making higher-level ones, such as this indexed array example. They can be standard, third-party, my own, I still can compose them. About my particular example, I’m not sure you can easily implement a free list in rust, to reuse space from de-allocated items. Especially if these items have non-empty constructor and destructor.
- burntsushi 9y ago
  > The point is, C++ allows composing these containers making higher-level ones, such as this indexed array example. What I---and others---are trying to tell you is that it's perfectly possible in Rust too. I don't think you've pointed out anything that isn't possible in Rust. My previous comment was exactly about composing containers to make higher-level ones. Have you tried building such things? Did you get stuck? Maybe someone can help. > About my particular example, I’m not sure you can easily implement a free list in rust, to reuse space from de-allocated items. Especially if these items have non-empty constructor and destructor. I don't see any reason why implementing a free list in Rust wouldn't be possible either.
  - Const-me 9y ago
    > I don't see any reason why implementing a free list in Rust wouldn't be possible either. Is placement new available in rust stable?
    - burntsushi 9y ago
      Why do you think placement new is necessary to implement a free list?
  - oconnor663 9y ago
    It seems like one of Const-me's objections is that Rust data structures like HashMap don't document a lot of guarantees about when they would and wouldn't invalidate unsafe interior pointers. That said, for Vec in particular, Rust actually makes a ton of guarantees about its layout (more that C++ std::vector I think): https://doc.rust-lang.org/std/vec/struct.Vec.html https://doc.rust-lang.org/std/vec/struct.Vec.html
    - Const-me 9y ago
      Correct. While vectors are comparable, C++ also guarantees a lot about the rest of the containers. E.g. unordered associative containers never expire pointers to keys or values. Linked lists never expire pointers nor iterators. In C++ I can create an efficient LRU cache in a dozen lines of code, combining list<const tKey* > with unordered_map<tKey, struct{tValue, list<const tKey* >::iterator}> (this implies tKey is not an int, otherwise list<tKey> is more efficient). Rust’s built-in LinkedHashMap had to reimplement a linked list instead.