3 ms·

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

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
      What's difficult in Rust is: (1) knowing how much memory a particular structure (like a hash table) is using (2) managing that memory as a single chunk; e.g. to free the whole thing at once so that you can pick up another chunk that you had previously serialized It's not impossible in rust, it's just that you have to build up all the pieces and none of it will integrate nicely with the rest of the rust code.

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
    What's difficult in Rust is: (1) knowing how much memory a particular structure (like a hash table) is using (2) managing that memory as a single chunk; e.g. to free the whole thing at once so that you can pick up another chunk that you had previously serialized It's not impossible in rust, it's just that you have to build up all the pieces and none of it will integrate nicely with the rest of the rust code.