code review 9612044: sort: provide different stable sort algorithms

sort: implement stable sorting

This CL provides stable in-place sorting by use of
bottom up merge sort with in-place merging done by
the SymMerge algorithm from P.-S. Kim and A. Kutzner.

The additional space needed for stable sorting (in the form of
stack space) is logarithmic in the inputs size n.
Number of calls to Less and Swap grow like O(n * log n) and
O(n * log n * log n):
Stable sorting random data uses significantly more calls
to Swap than the unstable quicksort implementation (5 times more
on n=100, 10 times more on n=1e4 and 23 times more on n=1e8).
The number of calls to Less is practically the same for Sort and
Stable.

Stable sorting 1 million random integers takes 5 times longer
than using Sort.

BenchmarkSortString1K      50000       328662 ns/op
BenchmarkStableString1K    50000       380231 ns/op  1.15 slower
BenchmarkSortInt1K         50000       157336 ns/op
BenchmarkStableInt1K       50000       191167 ns/op  1.22 slower
BenchmarkSortInt64K         1000     14466297 ns/op
BenchmarkStableInt64K        500     16190266 ns/op  1.12 slower

BenchmarkSort1e2          200000        64923 ns/op
BenchmarkStable1e2         50000       167128 ns/op  2.57 slower
BenchmarkSort1e4            1000     14540613 ns/op
BenchmarkStable1e4           100     58117289 ns/op  4.00 slower
BenchmarkSort1e6               5   2429631508 ns/op
BenchmarkStable1e6             1  12077036952 ns/op  4.97 slower

[volker.dobler, 2013-05-21 09:09:14]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go/

[volker.dobler, 2013-05-21 09:15:29]

Please do not focus on the details like
comments or separators, variable names (taken from
the source and publications) or that like but on
the algorithms themselves. Even the function signatures
are not final (e.g. measuring recursion depth won't
make it into the final CL). Lots of functions are
exported to test them, but won't stay exported.

This CL makes it easy to run the algorithms on
architectures I do not have access to and play
with them. Nothing else. It'll be abandoned and
replaced with a suitable implementation of the
chosen algorithm.

[bradfitz, 2013-05-21 15:31:19]

Excellent, thanks for working on this!

I'm worried about GPL infection.  Could you compare stl_algo.h from an SGI
or HP STL, before it went into GNU's libstdc++ to make sure it's the same,
back before it got a GPL sticker on it too?



On Tue, May 21, 2013 at 2:09 AM, <dr.volker.dobler@gmail.com> wrote:

> Reviewers: golang-dev1,
>
> Message:
> Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),
>
> I'd like you to review this change to
> https://code.google.com/p/go/
>
>
> Description:
>   sort: provide different stable sort algorithms
>
> NOT FOR SUBMISSION
>
> This CL is for testing and discussing different variants
> of a stable sort algorithm.
>
> This CL provides three different implementations for
> stable inplace sorting.  Actually the sorting is done
> by a standard merge sort, only the inplace merge
> algorithms differ.  The following three variants are
> compared:
>  - gcc-4.6.3's merge_without_buffer which is used by
>    libstdc++'s inplace_stable_sort function.
>  - SymMerge from Pok-Son Kim and Arne Kutzner, "Stable
>    minimum storage merging ba symetric comparisons"
>    (Algorithms - ESA 2004, Volume 3221 of Lecture Notes
>    in Computer Sience, Springer 2004, p. 714-723)
>  - SplitMerge, also from Kim and Kutzern, "A simple
>    algorithm for stable minimum storage merging."
>
> All three merging algorithm are stable and the recursion
> depth is bound by log(n), so that merge-sorting with them
> requieres only logarithmic additional stack space.
> The main helper function to all merge algorithms is a
> block rotation, the implementation is a direct translation
> of libstdc++'s __rotate function.
>
> The cutoffs when switching from merge- to insertion sort
> where determined on a dualcore Intel i7 2.67GHz CPU.
>
> Benchmarking shows that sorting with SymMerge and
> SplitMerge (SymMergeSort and SplitMergeSort) are comparable
> in speed while using MergeWithoutBuffer (InplaceStableSort)
> is considerable slower.
>
> Measuring the number of operations (swaps and comparisons)
> performed seems to indicate that all three algorithms
> perform O(n log n) swaps and O(n log n) compares.
> InplaceStableSort does more swaps and comparisons than
> Sym/SplitMergeSort - and is thus slower.
>
> SymMergeSort uses only 1.5n compares on an already sorted
> sequence whereas SplitMergeSort needs 2n comparisons and
> InplaceStableSortNeeds 5n. SplitMerge sort and SymMergeSort
> also differ a bit on saw-tooth like data: SymMergeSort uses
> less operations
>
> For the standard benchmarks (data of the form i % 0x2cc)
> SymMergeSort compares well with the standard Sort implementation
> wheras for random data the standard quicksort is faster by
> a factor of 3 to 9.
>
> This data (at least on 64 bit Intel i7) suggests to use
> SymMerge.  Thus something like
>
>   // StableSort sorts data in a stable way.
>   // It makes one call to data.Len to determine n, and O(n*log(n))
>   // calls to data.Less and data.Swap. The sort is guaranteed to
>   // be stable. StableSort has the same asymptotic runtime bounds
>   // as Sort but larger factors hidden in the big O and will take
>   // considerable more time on random data than Sort.
>   func StableSort(data Interface) {
>       // merge-sort using symMerge to merge blocks
>   }
>
>
>
> Benchmarks ("StandardSort" is the unstable Sort):
>
> BenchmarkSearchWrappers               10000000         281 ns/op
> BenchmarkSortString1K                     5000      342614 ns/op
> BenchmarkSortInt1K                       10000      163881 ns/op
> BenchmarkSortInt64K                        100    14672172 ns/op
>
> BenchmarkSymMergeSortInt1K               50000       50043 ns/op
> BenchmarkSplitMergeSortInt1K             50000       50677 ns/op
> BenchmarkInplaceStableSortInt1**K          10000      153956 ns/op
> BenchmarkStandardSortInt1K               10000      156901 ns/op
>
> BenchmarkSymMergeSortInt64K                500     4085378 ns/op
> BenchmarkSplitMergeSortInt64K              500     4112881 ns/op
> BenchmarkInplaceStableSortInt6**4K           100    12846001 ns/op
> BenchmarkStandardSortInt64K                100    14329672 ns/op
>
> BenchmarkSymMergeSortInt4M                   5 318262644 ns/op
> BenchmarkSplitMergeSortInt4M                 5 318633667 ns/op
> BenchmarkInplaceStableSortInt4**M              1  1006823241 ns/op
> BenchmarkStandardSortInt4M                   1  1216140021 ns/op
>
> BenchmarkSymMergeSortString1K            10000      178198 ns/op
> BenchmarkSplitMergeSortString1**K          10000      196506 ns/op
> BenchmarkInplaceStableSortStri**ng1K        5000      349352 ns/op
> BenchmarkStandardSortString1K             5000      332424 ns/op
>
> BenchmarkSymMergeSortedInt64K             1000     1646250 ns/op
> BenchmarkSplitMergeSortedInt64**K           1000     1733652 ns/op
> BenchmarkInplaceStableSortedIn**t64K         500     4065249 ns/op
> BenchmarkStandardSortedInt64K              200     7937829 ns/op
>
> BenchmarkSymMergeReversedInt64**K            500     7451392 ns/op
> BenchmarkSplitMergeReversedInt**64K          500     7429676 ns/op
> BenchmarkInplaceStableReversed**Int64K       100    19820718 ns/op
> BenchmarkStandardSortReversedI**nt64K        200     8690838 ns/op
>
> BenchmarkSymMergeSortUniqe                   1  1594279671 ns/op
> BenchmarkSplitMergeSortUniqe                 1  1596697063 ns/op
> BenchmarkInplaceStableSortUniq**e              1  1662573134 ns/op
> BenchmarkStandardSortUniqe                   5 347079470 ns/op
>
> BenchmarkSymMergeSortSubset                  1  1237720688 ns/op
> BenchmarkSplitMergeSortSubset                1  1207237700 ns/op
> BenchmarkInplaceStableSortSubs**et             1  1349776742 ns/op
> BenchmarkStandardSortSubset                 10   172742441 ns/op
>
> Please review this at
https://codereview.appspot.**com/9612044/<https://codereview.appspot.com/9612...
>
> Affected files:
>   M src/pkg/sort/sort.go
>   M src/pkg/sort/sort_test.go
>
>
> --
>
> ---You received this message because you are subscribed to the Google
> Groups "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to
golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou...
> .
> For more options, visit
https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o...
> .
>
>
>

[iant, 2013-05-21 16:54:08]

On Tue, May 21, 2013 at 8:31 AM, Brad Fitzpatrick <bradfitz@golang.org> wrote:
>
> I'm worried about GPL infection.  Could you compare stl_algo.h from an SGI
> or HP STL, before it went into GNU's libstdc++ to make sure it's the same,
> back before it got a GPL sticker on it too?

The GPL is a copyright license and as such only applies to copyright.
It does not apply to reimplementation of the algorithm in a different
language.  In any case I'm sure the algorithm is well described
elsewhere.

[0xjnml, 2013-05-22 09:07:50]

On Tue, May 21, 2013 at 6:54 PM, Ian Lance Taylor <iant@golang.org> wrote:
> On Tue, May 21, 2013 at 8:31 AM, Brad Fitzpatrick <bradfitz@golang.org>
wrote:
>>
>> I'm worried about GPL infection.  Could you compare stl_algo.h from an SGI
>> or HP STL, before it went into GNU's libstdc++ to make sure it's the same,
>> back before it got a GPL sticker on it too?
>
> The GPL is a copyright license and as such only applies to copyright.
> It does not apply to reimplementation of the algorithm in a different
> language.

That's true for a clean-room (re)implementation. A transliteration of
existing code into another language is a different case which retains
the original license, I think.

-j

[iant, 2013-05-22 13:31:15]

On Wed, May 22, 2013 at 2:07 AM, Jan Mercl <0xjnml@gmail.com> wrote:
> On Tue, May 21, 2013 at 6:54 PM, Ian Lance Taylor <iant@golang.org> wrote:
>> On Tue, May 21, 2013 at 8:31 AM, Brad Fitzpatrick <bradfitz@golang.org>
wrote:
>>>
>>> I'm worried about GPL infection.  Could you compare stl_algo.h from an SGI
>>> or HP STL, before it went into GNU's libstdc++ to make sure it's the same,
>>> back before it got a GPL sticker on it too?
>>
>> The GPL is a copyright license and as such only applies to copyright.
>> It does not apply to reimplementation of the algorithm in a different
>> language.
>
> That's true for a clean-room (re)implementation. A transliteration of
> existing code into another language is a different case which retains
> the original license, I think.

It depends.  There is no one answer in this area.  I wouldn't worry
about this case.

Ian

[volker.dobler, 2013-05-30 12:13:36]

PTAL

Experimenting with several merging and rotation
algorithms convinced me that SymMerge with the simple
block swapping as rotation works very well:
 - Stable sorting 10 million random integers is
   only slower by a factor of ~5.5.
 - The used algorithms are dead simple (at least if
   compared to some fancy published stuff).
 - Clean room implementations where trivial.
 - The sorting is provable stable on _all_ input.
 - Recursion depth (and thus required extra memory
   for the stack) is limited by log(n).
 - Calls to Less show O(n log n) behavior while
   calls to Swap grow like O(n**1.16) which is worse
   than the theoretical lower bound but not really
   bad.

Better algorithms: 
 - Practical in-place mergesort
   Jyrki Katajainen, Tomi A. Pasanen, and Jukka Teuhola
   Nordic Journal of Computing 3,1 (1996), 27-40
   The given algorithms are in-place, ops grow as
n log n
   but _not_ stable.

 - Fast Stable In-Plcae Sorting with O(n) Data Moves
   J.I. Munro and V. Raman
   Algorithmica (1996) 16, 115-160
   Needs additional 2n bits but works only if there 
   are enough different elements available to encode
   some permutations which have to be undone later.

All the optimal in-place sorting/merging algorithms
I found are either unstable or rely on enough different
elements in each step to encode the performed block
rearrangements. See also "In-Place Merging Algorithms",
Denham Coates-Evely, Department of Computer Science,
Kings College, January 2004 and the reverences in there.

[volker.dobler, 2013-05-30 12:13:36]

PTAL

Experimenting with several merging and rotation
algorithms convinced me that SymMerge with the simple
block swapping as rotation works very well:
 - Stable sorting 10 million random integers is
   only slower by a factor of ~5.5.
 - The used algorithms are dead simple (at least if
   compared to some fancy published stuff).
 - Clean room implementations where trivial.
 - The sorting is provable stable on _all_ input.
 - Recursion depth (and thus required extra memory
   for the stack) is limited by log(n).
 - Calls to Less show O(n log n) behavior while
   calls to Swap grow like O(n**1.16) which is worse
   than the theoretical lower bound but not really
   bad.

Better algorithms: 
 - Practical in-place mergesort
   Jyrki Katajainen, Tomi A. Pasanen, and Jukka Teuhola
   Nordic Journal of Computing 3,1 (1996), 27-40
   The given algorithms are in-place, ops grow as
n log n
   but _not_ stable.

 - Fast Stable In-Plcae Sorting with O(n) Data Moves
   J.I. Munro and V. Raman
   Algorithmica (1996) 16, 115-160
   Needs additional 2n bits but works only if there 
   are enough different elements available to encode
   some permutations which have to be undone later.

All the optimal in-place sorting/merging algorithms
I found are either unstable or rely on enough different
elements in each step to encode the performed block
rearrangements. See also "In-Place Merging Algorithms",
Denham Coates-Evely, Department of Computer Science,
Kings College, January 2004 and the reverences in there.

[rsc, 2013-05-30 15:48:26]

Thanks very much for working on this.

Could you please put the notes from your last message in the code so that others
who show up and think there should be a different algorithm can see why this
decision was made/

I assume the n**1.16 is purely empirical? Does the paper say anything about the
expected number of swaps?

Thanks again.
Russ

[volker.dobler, 2013-06-05 10:43:06]

PTAL

Stable sorting uses O(n*log(n)*log(n)) calls to Swap,
a crude derivation of this is included at the bottom of
sort.go.  The O(n**1.16) was a good but purely empirical
fit as Russ pointed out.

I included remarks on other algorithms evaluated in a
comment.

Patchset #10 can be reviewed properly but I'll be awfk
from Friday until end of June.

For the curious: Experimental data on numbers of calls
to Sort and Less sorting random ints can be found in 
http://i.imgur.com/fmZLKx5.png
The fits are n*log^2(n) for the number of Swaps in Stable
and n*log(n) for all the other numbers.

v.

[rsc, 2013-06-10 18:06:29]

Looks great, thanks.

I admit to not thinking through the algorithm details. If testBentleyMcIlroy
says the code works, I will assume the algorithm is correct and that you have
implemented it faithfully.

https://codereview.appspot.com/9612044/diff/33001/src/pkg/sort/sort.go
File src/pkg/sort/sort.go (right):

https://codereview.appspot.com/9612044/diff/33001/src/pkg/sort/sort.go#newcod...
src/pkg/sort/sort.go:367: c := (start + r) / 2
This should be c := start + (r-start) / 2, the same way that mid is computed
above.
This avoids
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-near...

https://codereview.appspot.com/9612044/diff/33001/src/pkg/sort/sort.go#newcod...
src/pkg/sort/sort.go:378: c := (start + r) / 2
Here too.

https://codereview.appspot.com/9612044/diff/33001/src/pkg/sort/sort_test.go
File src/pkg/sort/sort_test.go (right):

https://codereview.appspot.com/9612044/diff/33001/src/pkg/sort/sort_test.go#n...
src/pkg/sort/sort_test.go:351: 
Please add

func TestStableBM(t *testing.T) {
    testBentleyMcIlroy(t, Stable)
}

[volker.dobler, 2013-06-24 21:28:58]

PTAL

https://codereview.appspot.com/9612044/diff/33001/src/pkg/sort/sort.go
File src/pkg/sort/sort.go (right):

https://codereview.appspot.com/9612044/diff/33001/src/pkg/sort/sort.go#newcod...
src/pkg/sort/sort.go:367: c := (start + r) / 2
On 2013/06/10 18:06:29, rsc wrote:
> This should be c := start + (r-start) / 2, the same way that mid is computed
> above.
> This avoids
>
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-near...
> 

Done.

https://codereview.appspot.com/9612044/diff/33001/src/pkg/sort/sort.go#newcod...
src/pkg/sort/sort.go:378: c := (start + r) / 2
On 2013/06/10 18:06:29, rsc wrote:
> Here too.

Done.

https://codereview.appspot.com/9612044/diff/33001/src/pkg/sort/sort_test.go
File src/pkg/sort/sort_test.go (right):

https://codereview.appspot.com/9612044/diff/33001/src/pkg/sort/sort_test.go#n...
src/pkg/sort/sort_test.go:351: 
On 2013/06/10 18:06:29, rsc wrote:
> Please add
> 
> func TestStableBM(t *testing.T) {
>     testBentleyMcIlroy(t, Stable)
> }

Done.

As BentleyMcIlroy checks the number of Swaps which grows
as N Log^2 N for Stable I had to expose this limit.
Testing this for Stable with n <= 1025 only is not very
interesting.

[rsc, 2013-07-02 01:00:54]

LGTM

Thanks very much. This will be a great addition to Go 1.2.

[rsc, 2013-07-02 01:20:37]

*** Submitted as https://code.google.com/p/go/source/detail?r=7eded0df87b8 ***

sort: implement stable sorting

This CL provides stable in-place sorting by use of
bottom up merge sort with in-place merging done by
the SymMerge algorithm from P.-S. Kim and A. Kutzner.

The additional space needed for stable sorting (in the form of
stack space) is logarithmic in the inputs size n.
Number of calls to Less and Swap grow like O(n * log n) and
O(n * log n * log n):
Stable sorting random data uses significantly more calls
to Swap than the unstable quicksort implementation (5 times more
on n=100, 10 times more on n=1e4 and 23 times more on n=1e8).
The number of calls to Less is practically the same for Sort and
Stable.

Stable sorting 1 million random integers takes 5 times longer
than using Sort.

BenchmarkSortString1K      50000       328662 ns/op
BenchmarkStableString1K    50000       380231 ns/op  1.15 slower
BenchmarkSortInt1K         50000       157336 ns/op
BenchmarkStableInt1K       50000       191167 ns/op  1.22 slower
BenchmarkSortInt64K         1000     14466297 ns/op
BenchmarkStableInt64K        500     16190266 ns/op  1.12 slower

BenchmarkSort1e2          200000        64923 ns/op
BenchmarkStable1e2         50000       167128 ns/op  2.57 slower
BenchmarkSort1e4            1000     14540613 ns/op
BenchmarkStable1e4           100     58117289 ns/op  4.00 slower
BenchmarkSort1e6               5   2429631508 ns/op
BenchmarkStable1e6             1  12077036952 ns/op  4.97 slower

R=golang-dev, bradfitz, iant, 0xjnml, rsc
CC=golang-dev
https://codereview.appspot.com/9612044

Committer: Russ Cox <rsc@golang.org>

[dfc, 2013-07-02 01:34:18]

On 2013/07/02 01:20:37, rsc wrote:
> *** Submitted as https://code.google.com/p/go/source/detail?r=7eded0df87b8 ***
> 
> sort: implement stable sorting
> 
> This CL provides stable in-place sorting by use of
> bottom up merge sort with in-place merging done by
> the SymMerge algorithm from P.-S. Kim and A. Kutzner.
> 
> The additional space needed for stable sorting (in the form of
> stack space) is logarithmic in the inputs size n.
> Number of calls to Less and Swap grow like O(n * log n) and
> O(n * log n * log n):
> Stable sorting random data uses significantly more calls
> to Swap than the unstable quicksort implementation (5 times more
> on n=100, 10 times more on n=1e4 and 23 times more on n=1e8).
> The number of calls to Less is practically the same for Sort and
> Stable.
> 
> Stable sorting 1 million random integers takes 5 times longer
> than using Sort.
> 
> BenchmarkSortString1K      50000       328662 ns/op
> BenchmarkStableString1K    50000       380231 ns/op  1.15 slower
> BenchmarkSortInt1K         50000       157336 ns/op
> BenchmarkStableInt1K       50000       191167 ns/op  1.22 slower
> BenchmarkSortInt64K         1000     14466297 ns/op
> BenchmarkStableInt64K        500     16190266 ns/op  1.12 slower
> 
> BenchmarkSort1e2          200000        64923 ns/op
> BenchmarkStable1e2         50000       167128 ns/op  2.57 slower
> BenchmarkSort1e4            1000     14540613 ns/op
> BenchmarkStable1e4           100     58117289 ns/op  4.00 slower
> BenchmarkSort1e6               5   2429631508 ns/op
> BenchmarkStable1e6             1  12077036952 ns/op  4.97 slower
> 
> R=golang-dev, bradfitz, iant, 0xjnml, rsc
> CC=golang-dev
> https://codereview.appspot.com/9612044
> 
> Committer: Russ Cox <mailto:rsc@golang.org>

Sorry, this has broken on 32bit platforms.

[rsc, 2013-07-02 01:36:06]

Testing a trivial fix now.

[volker.dobler, 2014-07-20 11:42:36]

*** Abandoned ***