3 ms·

The ability to work with different memory sizes is pretty intriguing. How does the algorithm decide where and when to allocate?

orlp 4y ago
The allocation always happens once, at the start of the algorithm. The default allocation size is hard to describe in plain English, whereas the code is quite readable: const FULL_ALLOC_MAX_BYTES: usize = 1024 * 1024; const HALF_ALLOC_MAX_BYTES: usize = 1024 * 1024 * 1024; fn glidesort_alloc_size<T>(n: usize) -> usize { let tlen = core::mem::size_of::<T>(); let full_allowed = n.min(FULL_ALLOC_MAX_BYTES / tlen); let half_allowed = (n / 2).min(HALF_ALLOC_MAX_BYTES / tlen); let eighth_allowed = n / 8; full_allowed.max(half_allowed).max(eighth_allowed) } Essentially the default allocation size is a linear graph M(n) = n until 1 MiB, where it will plateau until overtaken by M(n) = n / 2 until 1 GiB, where it will once again plateau until overtaken by M(n) = n / 8. Note that this is only the default, you can pass glidesort a buffer with a size/location of your choice and it will use that instead.
- timerol 4y ago
  I used the word "allocate" imprecisely. (The plain English description in the README did a good job of explaining the up-front allocation needs.) What I meant to ask: How does the algorithm stay bounded in memory usage? Is glidesort written in such a way to never use more memory than that? Is the some sort of back-pressure mechanism, when most of the allocated memory is in use, and another operation is ongoing? Basically: when sorting a 1 GiB array of data, how does the algorithm keep from using more than 128 MiB of additional memory? Nothing in the "Technique Overview" section mentions bounded memory use (under n bytes, at least).
  - orlp 4y ago
    > How does the algorithm stay bounded in memory usage? Is glidesort written in such a way to never use more memory than that? It does not ever allocate more than what it allocated at the start. > Is the some sort of back-pressure mechanism, when most of the allocated memory is in use, and another operation is ongoing? Yes and no. I did write some code that will make glidesort back off and use less memory if the allocation request fails: https://github.com/orlp/glidesort/blob/master/src/lib.rs#L206 https://github.com/orlp/glidesort/blob/master/src/lib.rs#L20... The sad part is that this will probably never work in reality due to overcommit. > Basically: when sorting a 1 GiB array of data, how does the algorithm keep from using more than 128 MiB of additional memory? By allocating 128 MiB at the start, and never allocating more than that. Maybe what you really want to know is: how can it do merges in space (much) smaller than the input? The answer is by (recursively) splitting merges into two separate smaller merges using an in-place block swap. You can see this in action at the 10 to 12 second mark here: https://user-images.githubusercontent.com/202547/216675278-e4c8f15c-e42d-4224-b8c7-fdc67fdc2bde.mp4 https://user-images.githubusercontent.com/202547/216675278-e... Because I use block swaps and not rotations, this block swap can often be done implicitly (just not in the case of low-memory fallbacks) by re-assigning buffer names rather than physically moving elements.
    - timerol 4y ago
      > How can it do merges in space (much) smaller than the input. That's part of it. More specifically I'm interested in the dynamic nature of the space overhead. In the video you linked, from 10 to 12 seconds, it looks like the algorithm is using about n/4 scratch space. But for larger arrays, it's bounded at n/8. Is that done by further recursing merges for larger merge sizes? Is the number of recursive layers needed to do a big merge determined by the size of the input, or the size of the scratch space? I see that try_merge_into_scratch will fail when the scratch space isn't big enough, which mostly answers my question https://github.com/orlp/glidesort/blob/master/src/physical_merges.rs#L280 https://github.com/orlp/glidesort/blob/master/src/physical_m.... But I'm still not sure how that failure causes the overall algorithm to change (I have been trying to ask about how glidesort uses the preallocated scratch space internally, not how it interfaces with system memory and system allocators.)
      - orlp 4y ago
        > Is that done by further recursing merges for larger merge sizes? Yes. > Is the number of recursive layers needed to do a big merge determined by the size of the input, or the size of the scratch space? Both. I haven't worked out the exact math yet, but it's likely something on the order of O(log (n / s)) recursive layers. > I see that try_merge_into_scratch will fail when the scratch space isn't big enough, which mostly answers my question If you are reading the code, the whole small-memory magic happens in physical_merge: https://github.com/orlp/glidesort/blob/master/src/physical_merges.rs#L31 https://github.com/orlp/glidesort/blob/master/src/physical_m.... Lines 46-59 are the large-enough memory happy path. Lines 60-65 is the low-memory path in-place recursive path. All other merge functions use try_merge_into_scratch as a happy path, and if that fails end up deferring to physical_merge.
        timerol 4y ago
        Awesome. Thanks for the explanations!
    - zamalek 4y ago
      So under-allocating memory would merely negatively affect performance?

orlp 4y ago

The allocation always happens once, at the start of the algorithm. The default allocation size is hard to describe in plain English, whereas the code is quite readable: const FULL_ALLOC_MAX_BYTES: usize = 1024 * 1024; const HALF_ALLOC_MAX_BYTES: usize = 1024 * 1024 * 1024; fn glidesort_alloc_size<T>(n: usize) -> usize { let tlen = core::mem::size_of::<T>(); let full_allowed = n.min(FULL_ALLOC_MAX_BYTES / tlen); let half_allowed = (n / 2).min(HALF_ALLOC_MAX_BYTES / tlen); let eighth_allowed = n / 8; full_allowed.max(half_allowed).max(eighth_allowed) } Essentially the default allocation size is a linear graph M(n) = n until 1 MiB, where it will plateau until overtaken by M(n) = n / 2 until 1 GiB, where it will once again plateau until overtaken by M(n) = n / 8. Note that this is only the default, you can pass glidesort a buffer with a size/location of your choice and it will use that instead.

timerol 4y ago
I used the word "allocate" imprecisely. (The plain English description in the README did a good job of explaining the up-front allocation needs.) What I meant to ask: How does the algorithm stay bounded in memory usage? Is glidesort written in such a way to never use more memory than that? Is the some sort of back-pressure mechanism, when most of the allocated memory is in use, and another operation is ongoing? Basically: when sorting a 1 GiB array of data, how does the algorithm keep from using more than 128 MiB of additional memory? Nothing in the "Technique Overview" section mentions bounded memory use (under n bytes, at least).
- orlp 4y ago
  > How does the algorithm stay bounded in memory usage? Is glidesort written in such a way to never use more memory than that? It does not ever allocate more than what it allocated at the start. > Is the some sort of back-pressure mechanism, when most of the allocated memory is in use, and another operation is ongoing? Yes and no. I did write some code that will make glidesort back off and use less memory if the allocation request fails: https://github.com/orlp/glidesort/blob/master/src/lib.rs#L206 https://github.com/orlp/glidesort/blob/master/src/lib.rs#L20... The sad part is that this will probably never work in reality due to overcommit. > Basically: when sorting a 1 GiB array of data, how does the algorithm keep from using more than 128 MiB of additional memory? By allocating 128 MiB at the start, and never allocating more than that. Maybe what you really want to know is: how can it do merges in space (much) smaller than the input? The answer is by (recursively) splitting merges into two separate smaller merges using an in-place block swap. You can see this in action at the 10 to 12 second mark here: https://user-images.githubusercontent.com/202547/216675278-e4c8f15c-e42d-4224-b8c7-fdc67fdc2bde.mp4 https://user-images.githubusercontent.com/202547/216675278-e... Because I use block swaps and not rotations, this block swap can often be done implicitly (just not in the case of low-memory fallbacks) by re-assigning buffer names rather than physically moving elements.
  - timerol 4y ago
    > How can it do merges in space (much) smaller than the input. That's part of it. More specifically I'm interested in the dynamic nature of the space overhead. In the video you linked, from 10 to 12 seconds, it looks like the algorithm is using about n/4 scratch space. But for larger arrays, it's bounded at n/8. Is that done by further recursing merges for larger merge sizes? Is the number of recursive layers needed to do a big merge determined by the size of the input, or the size of the scratch space? I see that try_merge_into_scratch will fail when the scratch space isn't big enough, which mostly answers my question https://github.com/orlp/glidesort/blob/master/src/physical_merges.rs#L280 https://github.com/orlp/glidesort/blob/master/src/physical_m.... But I'm still not sure how that failure causes the overall algorithm to change (I have been trying to ask about how glidesort uses the preallocated scratch space internally, not how it interfaces with system memory and system allocators.)
    - orlp 4y ago
      > Is that done by further recursing merges for larger merge sizes? Yes. > Is the number of recursive layers needed to do a big merge determined by the size of the input, or the size of the scratch space? Both. I haven't worked out the exact math yet, but it's likely something on the order of O(log (n / s)) recursive layers. > I see that try_merge_into_scratch will fail when the scratch space isn't big enough, which mostly answers my question If you are reading the code, the whole small-memory magic happens in physical_merge: https://github.com/orlp/glidesort/blob/master/src/physical_merges.rs#L31 https://github.com/orlp/glidesort/blob/master/src/physical_m.... Lines 46-59 are the large-enough memory happy path. Lines 60-65 is the low-memory path in-place recursive path. All other merge functions use try_merge_into_scratch as a happy path, and if that fails end up deferring to physical_merge.
      - timerol 4y ago
        Awesome. Thanks for the explanations!
  - zamalek 4y ago
    So under-allocating memory would merely negatively affect performance?