3 ms·

I'm really not sure, but I think there's a miscommunication about raw pointers in this thread. I think other folks are suggesting that you can solve the contain

I'm really not sure, but I think there's a miscommunication about raw pointers in this thread. I think other folks are suggesting that you can solve the container composition problems you're talking about by inserting raw pointers into a HashMap. But I think you're reading that as obtaining raw pointers to the storage that a HashMap owns, which is why you're worried about iterator invalidation rules and stuff like that? (My understanding is that any reference into storage that a container owns is / could be completely invalidated by any &mut operation on that container.)

Const-me 9y ago
To create an external index for the existing collection, I need to get pointer of the item stored in that existing collection, compute a key, and put both into the HashMap<tKey, tValue*> So, I need to do both. And also, I need to know when these pointer expire so I can rebuild my index when it happens.
- oconnor663 9y ago
  I think I understand. The idea would be to have one HashMap<tKey, tValue> that holds the objects themselves, and then a secondary HashMap<tKey2, *tValue> (with a star this time) that indexes on some other key and points to values stored directly in the first map? What's the benefit of doing that, compared to making both the HashMaps store pointers to independently allocated objects on the heap, such that insertions into one map never invalidate the other map? 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?
  - Const-me 9y ago
    > 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.
        9y ago
  - benlorenzetti 9y ago
    Object size possibly.

Const-me 9y ago

To create an external index for the existing collection, I need to get pointer of the item stored in that existing collection, compute a key, and put both into the HashMap<tKey, tValue*> So, I need to do both. And also, I need to know when these pointer expire so I can rebuild my index when it happens.

oconnor663 9y ago
I think I understand. The idea would be to have one HashMap<tKey, tValue> that holds the objects themselves, and then a secondary HashMap<tKey2, *tValue> (with a star this time) that indexes on some other key and points to values stored directly in the first map? What's the benefit of doing that, compared to making both the HashMaps store pointers to independently allocated objects on the heap, such that insertions into one map never invalidate the other map? 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?
- Const-me 9y ago
  > 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.
        9y ago
- benlorenzetti 9y ago
  Object size possibly.