6 ms·

More like 20 it seems ;) > I need these two lower-level structures to expose unsafe stuff at the API boundary Two thoughts: 1) I think you can always use unsa

More like 20 it seems ;) > I need these two lower-level structures to expose unsafe stuff at the API boundary Two thoughts: 1) I think you can always use unsafe to get access to a raw pointer (I honestly don't use unsafe often) 2) you need someway to express ownership between both data structures, this can be annoying, no doubt. > C++, with these iterators and smart pointers Does that make it safer than unsafe Rust? Maybe, but there's a lot less unsafe Rust even in these graphs...

dikaiosune 9y ago
If you click directly on the time of a comment, it's a link to a direct reply page.
Const-me 9y ago
> I think you can always use unsafe to get access to a raw pointer I’m not sure about that. Also I don’t know for how long will it work, C++ has iterator invalidation rules. > you need someway to express ownership between both data structures Not every relation is ownership. Graph modes don’t own each other, an external index doesn’t own the indexed items, etc.
- oconnor663 9y ago
  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...

dikaiosune 9y ago

If you click directly on the time of a comment, it's a link to a direct reply page.

Const-me 9y ago

> I think you can always use unsafe to get access to a raw pointer I’m not sure about that. Also I don’t know for how long will it work, C++ has iterator invalidation rules. > you need someway to express ownership between both data structures Not every relation is ownership. Graph modes don’t own each other, an external index doesn’t own the indexed items, etc.

oconnor663 9y ago
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...