8 ms·

Parallel In-Place Merge Sort

61 points by r4um 12y ago

wfunction 12y ago
It's really silly that they depend on the STL implementations, because I don't believe STL implementations actually implement in-place merges in-place. The actual problem of stable in-place merge is extremely hard, so I was really surprised it would show up in a Dr. Dobbs article.
- yelnatz 12y ago
  Can you clarify what you mean by that? Article said they got 2.2x improvement using their parallel method compared to STL. Trade off was having 100% CPU utilization vs 12.5% with STL.
  - rikkus 12y ago
    That's not really a trade-off, if you're using the term with a negative connotation. Going from using 100% of one core to 100% of eight (well, 4, but hyperthreading) would normally be considered an advantage.
    - gear54rus 12y ago
      I'm probably wrong, but wouldn't it be a decrease in overall productivity? 2.2x increase in speed (higher the better) but ~7x increase in load (lower the better) for the same workload. Or let x be time we need to complete the task: 12.5 * x first (load over time) is less than second 100 * x / 2.2 for the same x. Or is this an inaccurate comparison?
      - deleted 12y ago
        [deleted]
      - illumen 12y ago
        Yeah, it depends. How much memory bandwidth do you use with each? Are the results useful incrementally? What else do you have to do on the machine? If this is the only task, and you don't care about power use, then using all resources for a quicker time is better. If you care about power use, or have other things running on the machine, then great. Being in place will of course matter with memory bandwidth and available RAM. GPUs are way more parallel, and faster than this too. "clocks about 100x faster than calling std::stable_sort on an i7 Sandy Bridge" http://nvlabs.github.io/moderngpu/mergesort.html http://nvlabs.github.io/moderngpu/mergesort.html
  - wfunction 12y ago
    > Can you clarify what you mean by that? I'm saying their merge sort was likely not actually in-place.
- CJefferson 12y ago
  Certainly g++ does have an in-place merge sort. It's tricky in to activate it, because it is only used when an attempt to allocate a spare buffer fails, and on most 64-bit machines malloc doesn't fail, your program just gets killed later when it tries to use the memory.
  - wfunction 12y ago
    Are you talking about this? https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L2491 https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-... Do you know what the time complexity of their merging algorithm is? As a side note, an optimal merging algorithm is in the paper called "On Optimal and Efficient in Place Merging", and it's too complicated for me to expect it in a standard library implementation. (Although the STL doesn't need to be optimal, I think the sub-optimal linear-time algorithms are also complicated enough to not be used for the standard library, but correct me if I'm wrong.)
    - CJefferson 12y ago
      I know the complexity of stable_sort (which uses this) is O(n. log n) with extra memory (which is fairly obvious extra buffer), and the intention is that without extra memory the sort is O(n.log^2 n). I assume that algorithm meets that target, but I'll admit I'm not positive it does.
      - wfunction 12y ago
        See, that would violate the standard. The standard mandates O(n log n), but I don't think any implementation follows this. (Again, that complexity is indeed possible, but quite challenging and not something I've seen in standard library implementations.)
        CJefferson 12y ago
        No, my previous message was a quote from the standard. O(n log^2 n) is fine when no extra memory is available. As you say, this could in principle now be tightened. In the past the standard used to allow O(n^2) std::sort to permit naive quicksort implementations, which has now been tightened to O(n log n). Here's the relevant quote from stable_sort: > Complexity: It does at most N log^2(N) (where N == last - first) comparisons; if enough extra memory is available, it is N log(N).
- aidanhs 12y ago
  A stable in-place merge sort is actually reasonably easy to implement if you happen to be using a linked list - http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html http://www.chiark.greenend.org.uk/~sgtatham/algorithms/lists... I think it's interesting how choice of data structure affects algorithm characteristics.
  - wfunction 12y ago
    I don't think people have linked lists in mind when they talk about merge sort.
    - angersock 12y ago
      I was under the impression that the sorting of linked lists is exactly what merge sort is good for.
      - wfunction 12y ago
        You're confusing two things: 1. Yes, merge sort is exactly the kind of algorithm you'd use for sorting linked lists 2. No, sorting linked lists is not the primary application of merge sort
        angersock 12y ago
        Right, that's not the primary application of merge sort--I meant 1. English is hard sometimes. :(
  - StefanKarpinski 12y ago
    Using a linked list is effectively equivalent to doing things not in place. Except that the memory locality is worse and for word-sized data like integers and floats, the overhead is permanent 3x instead of just temporary 2x. But yes, for linked lists, merge sort is a great choice since it doesn't depend on O(1) indexing.
    - 12y ago
taeric 12y ago
Anyone have any quick comparisons of this to Batcher's sorting method? Quickly consulting wikipedia, I see that those have gained traction in the GPGU community. I was curious if/when those techniques would start to get use.
govilk 12y ago
similar to java8 feature, fork and join
brudgers 12y ago
While the approximately 10x increase of the parallel in-place merge sort over the non-parallel version shown on the benchmarks may be meaningful, it also shows that parallelism reduces constant factors, not exponents.
- readerrrr 12y ago
  It is impossible to get anything better than a constant improvement, if you divide you work by a constant factor.
  - brudgers 12y ago
    Not discussing that is a weakness of the article. The algorithm addresses performance issues caused by the IO bottleneck, not an algorithmic deficiency with common merge-sort implementations. The merits and deficits of trading-off O(n)[Memory] growth for 0(log n)^2[Time] growth are worthy of discussion if it is anticipated that people will implement the algorithm in production code. There's a case for looking at it, certainly, on constrained systems, but such systems may not have processors with the execution pipeline sophistication of an Intel i7 quad-core. Which of course is just a round about way of saying, the article doesn't indicate domains in which the algorithm may be relevant and not relevant.
  - sp332 12y ago
    That's just what brudgers said. But don't worry, CPU and GPU manufacturers are increasing the number of cores exponentially :p
- taeric 12y ago
  If you have a look at sorting networks, they actually do reduce an exponent. Goes from nlg(n) to just lg(n). See [1], for example. Saying that, I feel like I'm trying to mislead, though. This requires nlg(n) comparators, so you still have to pay for it somehow. And I doubt we are going to see that many comparators on any piece of kit any time soon. For large n, anyway. (Though, seeing this can be done with a gpu, it does seem that you can hit rather large arrays already.) [1] http://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort http://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_merges...

61 points by r4um 12y ago

It's really silly that they depend on the STL implementations, because I don't believe STL implementations actually implement in-place merges in-place. The actual problem of stable in-place merge is extremely hard, so I was really surprised it would show up in a Dr. Dobbs article.

yelnatz 12y ago
Can you clarify what you mean by that? Article said they got 2.2x improvement using their parallel method compared to STL. Trade off was having 100% CPU utilization vs 12.5% with STL.
- rikkus 12y ago
  That's not really a trade-off, if you're using the term with a negative connotation. Going from using 100% of one core to 100% of eight (well, 4, but hyperthreading) would normally be considered an advantage.
  - gear54rus 12y ago
    I'm probably wrong, but wouldn't it be a decrease in overall productivity? 2.2x increase in speed (higher the better) but ~7x increase in load (lower the better) for the same workload. Or let x be time we need to complete the task: 12.5 * x first (load over time) is less than second 100 * x / 2.2 for the same x. Or is this an inaccurate comparison?
    - deleted 12y ago
      [deleted]
    - illumen 12y ago
      Yeah, it depends. How much memory bandwidth do you use with each? Are the results useful incrementally? What else do you have to do on the machine? If this is the only task, and you don't care about power use, then using all resources for a quicker time is better. If you care about power use, or have other things running on the machine, then great. Being in place will of course matter with memory bandwidth and available RAM. GPUs are way more parallel, and faster than this too. "clocks about 100x faster than calling std::stable_sort on an i7 Sandy Bridge" http://nvlabs.github.io/moderngpu/mergesort.html http://nvlabs.github.io/moderngpu/mergesort.html
- wfunction 12y ago
  > Can you clarify what you mean by that? I'm saying their merge sort was likely not actually in-place.
CJefferson 12y ago
Certainly g++ does have an in-place merge sort. It's tricky in to activate it, because it is only used when an attempt to allocate a spare buffer fails, and on most 64-bit machines malloc doesn't fail, your program just gets killed later when it tries to use the memory.
- wfunction 12y ago
  Are you talking about this? https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L2491 https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-... Do you know what the time complexity of their merging algorithm is? As a side note, an optimal merging algorithm is in the paper called "On Optimal and Efficient in Place Merging", and it's too complicated for me to expect it in a standard library implementation. (Although the STL doesn't need to be optimal, I think the sub-optimal linear-time algorithms are also complicated enough to not be used for the standard library, but correct me if I'm wrong.)
  - CJefferson 12y ago
    I know the complexity of stable_sort (which uses this) is O(n. log n) with extra memory (which is fairly obvious extra buffer), and the intention is that without extra memory the sort is O(n.log^2 n). I assume that algorithm meets that target, but I'll admit I'm not positive it does.
    - wfunction 12y ago
      See, that would violate the standard. The standard mandates O(n log n), but I don't think any implementation follows this. (Again, that complexity is indeed possible, but quite challenging and not something I've seen in standard library implementations.)
      - CJefferson 12y ago
        No, my previous message was a quote from the standard. O(n log^2 n) is fine when no extra memory is available. As you say, this could in principle now be tightened. In the past the standard used to allow O(n^2) std::sort to permit naive quicksort implementations, which has now been tightened to O(n log n). Here's the relevant quote from stable_sort: > Complexity: It does at most N log^2(N) (where N == last - first) comparisons; if enough extra memory is available, it is N log(N).
aidanhs 12y ago
A stable in-place merge sort is actually reasonably easy to implement if you happen to be using a linked list - http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html http://www.chiark.greenend.org.uk/~sgtatham/algorithms/lists... I think it's interesting how choice of data structure affects algorithm characteristics.
- wfunction 12y ago
  I don't think people have linked lists in mind when they talk about merge sort.
  - angersock 12y ago
    I was under the impression that the sorting of linked lists is exactly what merge sort is good for.
    - wfunction 12y ago
      You're confusing two things: 1. Yes, merge sort is exactly the kind of algorithm you'd use for sorting linked lists 2. No, sorting linked lists is not the primary application of merge sort
      - angersock 12y ago
        Right, that's not the primary application of merge sort--I meant 1. English is hard sometimes. :(
- StefanKarpinski 12y ago
  Using a linked list is effectively equivalent to doing things not in place. Except that the memory locality is worse and for word-sized data like integers and floats, the overhead is permanent 3x instead of just temporary 2x. But yes, for linked lists, merge sort is a great choice since it doesn't depend on O(1) indexing.
  - 12y ago

taeric 12y ago

Anyone have any quick comparisons of this to Batcher's sorting method? Quickly consulting wikipedia, I see that those have gained traction in the GPGU community. I was curious if/when those techniques would start to get use.

govilk 12y ago

similar to java8 feature, fork and join

brudgers 12y ago

While the approximately 10x increase of the parallel in-place merge sort over the non-parallel version shown on the benchmarks may be meaningful, it also shows that parallelism reduces constant factors, not exponents.

readerrrr 12y ago
It is impossible to get anything better than a constant improvement, if you divide you work by a constant factor.
- brudgers 12y ago
  Not discussing that is a weakness of the article. The algorithm addresses performance issues caused by the IO bottleneck, not an algorithmic deficiency with common merge-sort implementations. The merits and deficits of trading-off O(n)[Memory] growth for 0(log n)^2[Time] growth are worthy of discussion if it is anticipated that people will implement the algorithm in production code. There's a case for looking at it, certainly, on constrained systems, but such systems may not have processors with the execution pipeline sophistication of an Intel i7 quad-core. Which of course is just a round about way of saying, the article doesn't indicate domains in which the algorithm may be relevant and not relevant.
- sp332 12y ago
  That's just what brudgers said. But don't worry, CPU and GPU manufacturers are increasing the number of cores exponentially :p
taeric 12y ago
If you have a look at sorting networks, they actually do reduce an exponent. Goes from nlg(n) to just lg(n). See [1], for example. Saying that, I feel like I'm trying to mislead, though. This requires nlg(n) comparators, so you still have to pay for it somehow. And I doubt we are going to see that many comparators on any piece of kit any time soon. For large n, anyway. (Though, seeing this can be done with a gpu, it does seem that you can hit rather large arrays already.) [1] http://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort http://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_merges...