3 ms·

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 t

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
    Correct.

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
  Correct.