Support saving quasi-inverses on disk

[dalcde]

Currently, we store all quasi-inverses in memory, which takes up the bulk of the memory consumption (e.g. up to the 140th stem, we need 25.8 MiB to store the differentials and 40GiB for the quasi-inverses). If we want to resolve to larger degrees, we will run out of memory on any reasonable system.

Since these quasi-inverses are used at very predictable times, we ought to be able store these on the disk and call them on demand. Perhaps a custom allocator could be used for this purpose.

[JoeyBF]

I've been thinking about this for some time and here's my idea so far. Using zero-copy deserialization, it would be possible to deserialize Resolution by simply mmap'ing a save file and pointing to that memory region. This has at least two advantages:

• we only load in memory the data that we need for the computation in the first place;
• the kernel handles page swapping as the RAM gets more saturated, so we can delegate that part of memory management.

I was thinking we could implement zero-copy deserialization with the rkyv crate. The hurdle so far is that mutexes aren't supported, but that's coming in version 0.7. Does that seem like a good way to proceed?

[dalcde]

On Thu, May 20, 2021 at 11:13:28PM -0700, Joey Beauvais-Feisthauer wrote: I was thinking we could implement zero-copy deserialization with the [`rkyv`](https://docs.rs/rkyv/0.6.4/rkyv/) crate. The hurdle so far is that mutexes aren't supported, but that's coming in version 0.7. Does that seem like a good way to proceed?

In my experience the largest problems is supporting Arc. The heavy inter-dependence means the deserialization function needs to accept custom arguments as "auxiliary data". One option is to go even more low level, and write a custom mmap-backed allocator. For our purposes this can simply be a bump allocator on a mmapped region. We then need to modify all our objects to support custom allocators. The problem with this is that the code will likely become much harder to maintain, since this mmap option will result in different types, which have to be chosen at compile time.

[JoeyBF]

In my experience the largest problems is supporting Arc.

I don't think that should be a big issue. Since everything would be zero-copy the right data structures would already be in place before deserialization starts, and in any case we can write our own deserializer that uses an arbirtrary Fallible type as auxiliary data. Also rkyv supports Rc/Weak and Arc/Weak since version 0.4, and will support mutexes soon. Another idea would be to replace mutexes by a strategic use of channels, but I'm not sure how that would work concretely. I've read that channels are the standard solution when there are Arc's and Mutexes all over the code.

One option is to go even more low level, and write a custom mmap-backed
allocator.

Implementing a new allocator would be feasible but that's quite low level, and I'm not sure that would solve everything. If I understand correctly, allocation would have to depend on an mmap which could be either file-backed (with a dynamically known file handle) or anonymous. Then we would have to interact with it when the computation for a given t has finished, and I'm not even sure if Rust allows explicitly interacting with the allocator that way. Or the allocator would have to somehow figure out whether a quasi-inverse can be safely swapped out based on the other data that it has access to, and only when Rust happens to call it.

[JoeyBF]

Here's another thought. If differentials in Resolution was OnceVec<Weak<...>> instead of OnceVec<Arc<...>>, we could "load" the differentials by simply instantiating a dummy Weak pointer. Then when some thread wants to access a given differential, it can try to upgrade it to an Arc; if it gets None, it could then use some other piece of data to find the differential in a file, actually load it, and then use that. As soon as there is no upgraded version of the Weak owned by anything, the allocator is now free to deallocate it.

[JoeyBF]

@dalcde I think your latest PR solves this as well right?