4 ms·

That thread brings up per-container memory allocators, and mentions Vec. What's going on there? I have been trying to find a good way to deal with hybrid memor

That thread brings up per-container memory allocators, and mentions Vec. What's going on there? I have been trying to find a good way to deal with hybrid memory/disk structures. One example is external sort, but there are a whole class of such structures used for databases (Hash Join, Hash Aggregation, etc.). The idea is to constrain the memory footprint of a structure and efficiently use the disk. One challenge is simlly knowing how much memory is being used. Another is supporting multiple heaps/arenas/whatever and allocating in the right one. And a third is safely clearing parts of the structure that have been written to disk for later processing (I guess calling the destructors if necessary?). Is there any work in this area?

CyberDildonics 6y ago
Wouldn't memory mapping take care of a lot of these scenarios? The OS will do all the caching. If you make a data structure that is meant to use one contiguous chunk of memory and access memory linearly and/or with locality when possible, I would think it would make explicit disk/hybrid scenarios much less necessary.
- jeff-davis 6y ago
  Consider a hash table. Access is basically random, so if 25% fits in memory and 75% is paged-out at any given time, then 75% of the lookups will be a page fault and require a page-in. Very costly. Compare that to a Grace HashJoin (https://en.m.wikipedia.org/wiki/Hash_join https://en.m.wikipedia.org/wiki/Hash_join) which partitions both sides (lookup side and hash table side) into matching partition pairs. The partitioning step and reading the partitions from disk are both sequential access. Then, pick up and process one pair of partitions at a time, which will only require a small hash table in memory. Note that this is still way more efficient even when on an SSD, because an SSD is still block-oriented, and paging entire blocks in/out for a single lookup is still inefficient. It even helps when the data fits into memory sometimes, because you can size the partitions small enough to fit in cache, which will make lookups even faster. You can say "don't use hash tables", but that's not a great amswer for a low-level high-performance language like Rust.
  - CyberDildonics 6y ago
    I would never say "don't use hash table" but I do think that a lot of the benefits from special data structures like these are more due to the organization of memory than being explicit about memory loading and disk writing. In this case it seems like the downsides you mentioned are the downsides of keeping things on disk, not memory mapping (which would only hit the disk on the first load and would automatically use any available memory). Organization to use disk pages effectively would benefit memory mapping as well.
    - jeff-davis 6y ago
      But to organize memory you need some idea of how much you are using (e.g. how big the in-memory hash table is), and be able to free it in a reasonable pattern (e.g. deallocate the whole heap/arena at once). Both things are difficult in rust currently, and memory mapping doesn't help with either. Memory mapping serves a similar purpose as temp files: a way to tell the OS that it can freely page that out to avoid uncontrolled swapping. But you need to do the organization yourself to keep that access sequential, which is hard to do in rust for the reasons that I mentioned. If you memory map a hash table and have memory pressure, you'll go into the crazy bad scenario of a page-in for every lookup, which is avoidable with better organization. I think we are basically in agreement but perhaps my point was not clear.
      - CyberDildonics 6y ago
        > But to organize memory you need some idea of how much you are using When I talk about organizing the data structure I'm talking about how the data is layed out in the memory map and how locality is affected. What I'm saying is not that I think all uses are covered by memory mapping, just that data structure layout combined with memory mapping can probably take care of lots of the majority of scenarios. I did not know that organizing memory layout was difficult in Rust since it is very straight forward in C++.
        jeff-davis 6y ago
steveklabnik 6y ago
> What's going on there? Box and Vec are starting to gain the ability to be parameterized over an allocator. > Is there any work in this area? Kind of, but it's slow going. You can support multiple heaps/arenas/whatever, but it means you have to implement your own. As the ecosystem standardizes around the allocator traits (only the global one is stable yet), there will be easier interop.
aw1621107 6y ago
> That thread brings up per-container memory allocators, and mentions Vec. What's going on there? I believe they're talking about custom allocator support for Box [0, 1]. The author of the PR says that they intend to add per-container allocator support once support for Box lands, starting with Vec [2]. [0]: https://www.reddit.com/r/rust/comments/jgxgpu/box_will_have_custom_allocator_support_soon_tm/ https://www.reddit.com/r/rust/comments/jgxgpu/box_will_have_... [1]: https://github.com/rust-lang/rust/pull/77187 https://github.com/rust-lang/rust/pull/77187 [2]: https://www.reddit.com/r/rust/comments/jgxgpu/box_will_have_custom_allocator_support_soon_tm/g9turat/ https://www.reddit.com/r/rust/comments/jgxgpu/box_will_have_...

CyberDildonics 6y ago

Wouldn't memory mapping take care of a lot of these scenarios? The OS will do all the caching. If you make a data structure that is meant to use one contiguous chunk of memory and access memory linearly and/or with locality when possible, I would think it would make explicit disk/hybrid scenarios much less necessary.

jeff-davis 6y ago
Consider a hash table. Access is basically random, so if 25% fits in memory and 75% is paged-out at any given time, then 75% of the lookups will be a page fault and require a page-in. Very costly. Compare that to a Grace HashJoin (https://en.m.wikipedia.org/wiki/Hash_join https://en.m.wikipedia.org/wiki/Hash_join) which partitions both sides (lookup side and hash table side) into matching partition pairs. The partitioning step and reading the partitions from disk are both sequential access. Then, pick up and process one pair of partitions at a time, which will only require a small hash table in memory. Note that this is still way more efficient even when on an SSD, because an SSD is still block-oriented, and paging entire blocks in/out for a single lookup is still inefficient. It even helps when the data fits into memory sometimes, because you can size the partitions small enough to fit in cache, which will make lookups even faster. You can say "don't use hash tables", but that's not a great amswer for a low-level high-performance language like Rust.
- CyberDildonics 6y ago
  I would never say "don't use hash table" but I do think that a lot of the benefits from special data structures like these are more due to the organization of memory than being explicit about memory loading and disk writing. In this case it seems like the downsides you mentioned are the downsides of keeping things on disk, not memory mapping (which would only hit the disk on the first load and would automatically use any available memory). Organization to use disk pages effectively would benefit memory mapping as well.
  - jeff-davis 6y ago
    But to organize memory you need some idea of how much you are using (e.g. how big the in-memory hash table is), and be able to free it in a reasonable pattern (e.g. deallocate the whole heap/arena at once). Both things are difficult in rust currently, and memory mapping doesn't help with either. Memory mapping serves a similar purpose as temp files: a way to tell the OS that it can freely page that out to avoid uncontrolled swapping. But you need to do the organization yourself to keep that access sequential, which is hard to do in rust for the reasons that I mentioned. If you memory map a hash table and have memory pressure, you'll go into the crazy bad scenario of a page-in for every lookup, which is avoidable with better organization. I think we are basically in agreement but perhaps my point was not clear.
    - CyberDildonics 6y ago
      > But to organize memory you need some idea of how much you are using When I talk about organizing the data structure I'm talking about how the data is layed out in the memory map and how locality is affected. What I'm saying is not that I think all uses are covered by memory mapping, just that data structure layout combined with memory mapping can probably take care of lots of the majority of scenarios. I did not know that organizing memory layout was difficult in Rust since it is very straight forward in C++.
      - jeff-davis 6y ago

steveklabnik 6y ago

> What's going on there? Box and Vec are starting to gain the ability to be parameterized over an allocator. > Is there any work in this area? Kind of, but it's slow going. You can support multiple heaps/arenas/whatever, but it means you have to implement your own. As the ecosystem standardizes around the allocator traits (only the global one is stable yet), there will be easier interop.

aw1621107 6y ago

> That thread brings up per-container memory allocators, and mentions Vec. What's going on there? I believe they're talking about custom allocator support for Box [0, 1]. The author of the PR says that they intend to add per-container allocator support once support for Box lands, starting with Vec [2]. [0]: https://www.reddit.com/r/rust/comments/jgxgpu/box_will_have_custom_allocator_support_soon_tm/ https://www.reddit.com/r/rust/comments/jgxgpu/box_will_have_... [1]: https://github.com/rust-lang/rust/pull/77187 https://github.com/rust-lang/rust/pull/77187 [2]: https://www.reddit.com/r/rust/comments/jgxgpu/box_will_have_custom_allocator_support_soon_tm/g9turat/ https://www.reddit.com/r/rust/comments/jgxgpu/box_will_have_...