www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4584] New: std.algorithm.sort fails with SwapStrategy.stable

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4584

           Summary: std.algorithm.sort fails with SwapStrategy.stable
           Product: D
           Version: D2
          Platform: Other
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: johannespfau gmail.com


--- Comment #0 from Johannes Pfau <johannespfau gmail.com> 2010-08-05 03:17:37
PDT ---
Created an attachment (id=704)
test case

When using SwapStrategy.stable with std.algorithms sort function, I get
partially wrong results. It works fine with SwapStrategy.unstable. It also
asserts: "core.exception.AssertError std.algorithm(4021): Assertion failure"
(the assert is "assert(isSorted!(lessFun)(r));")

Tested with dmd 2.047 and phobos 2.047.
A test case is attached.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 05 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4584


Andrei Alexandrescu <andrei metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |andrei metalanguage.com
         AssignedTo|nobody puremagic.com        |andrei metalanguage.com


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 09 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4584


Olivier Fabre <axel.foster-5bcwppg yopmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |axel.foster-5bcwppg yopmail
                   |                            |.com


--- Comment #1 from Olivier Fabre <axel.foster-5bcwppg yopmail.com> 2011-10-23
17:34:22 PDT ---
I don't know if it helps, but I've got a similar failure with this program:

import std.algorithm;
void main() {
  sort!("a<b", SwapStrategy.stable)(
    [83, 42, 85, 86, 87, 22, 89, 30, 91, 46, 93, 94, 95, 6,
     97, 14, 33, 10, 101, 102, 103, 26, 105, 106, 107, 6]
  );
}

It returns:

core.exception.AssertError /usr/include/d/std/algorithm.d(6662): Failed to sort
range of type int[]. Actual result is: [6, 42, 85, 86, 87, 22, 89, 30]...

(With the git version of dmd2 and libphobos2 from 21 oct. 2011.)

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 23 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4584



--- Comment #2 from Olivier Fabre <axel.foster-5bcwppg yopmail.com> 2011-10-23
18:52:08 PDT ---
Oh well, Johannes' test case actually works fine here, so my bug might be a
different one. Unless the value of optimisticInsertionSortGetsBetter in
sortImpl() was < 13 at the time...

By experimenting with arrays of growing length filled with random numbers, it
becomes clear that my bug happens for arrays of length 26 and never for a
smaller length, which hints at a bug in the "pivot" (quick?) sort.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 23 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4584


Dmitry Olshansky <dmitry.olsh gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dmitry.olsh gmail.com


--- Comment #3 from Dmitry Olshansky <dmitry.olsh gmail.com> 2012-08-22
06:31:15 PDT ---
Hit this issue in my project. As part of normalization process codepoints are
_stably_ sorted by their canonical combining class.
Can dig up a bunch of cases if required but the end result is it rarely works.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 22 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4584


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs eml.cc


--- Comment #4 from bearophile_hugs eml.cc 2012-08-22 14:41:50 PDT ---
(In reply to comment #3)
 Hit this issue in my project. As part of normalization process codepoints are
 _stably_ sorted by their canonical combining class.
 Can dig up a bunch of cases if required but the end result is it rarely works.
I have seen this: https://github.com/blackwhale/phobos/commit/23a1cd0b7fac5b4480fee060e240ddda29bed54e So is this problem caused by a DMD bug? If this is true are you able to create a minimal example of the bug? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Aug 22 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4584



--- Comment #5 from Dmitry Olshansky <dmitry.olsh gmail.com> 2012-08-22
22:36:30 PDT ---
(In reply to comment #4)
 (In reply to comment #3)
 Hit this issue in my project. As part of normalization process codepoints are
 _stably_ sorted by their canonical combining class.
 Can dig up a bunch of cases if required but the end result is it rarely works.
I have seen this: https://github.com/blackwhale/phobos/commit/23a1cd0b7fac5b4480fee060e240ddda29bed54e So is this problem caused by a DMD bug? If this is true are you able to create a minimal example of the bug?
No, it's just that $ works only with arrays (still). And in order for sort(zip(...)) to work I need this minor fix. The bug with stable sort was there for 2 years now and I don't realy know the cause. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Aug 22 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4584


Xinok <xinok live.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |xinok live.com


--- Comment #6 from Xinok <xinok live.com> 2012-09-03 10:58:38 PDT ---
I've written a collection of sorting algorithms for D:
https://github.com/Xinok/XSort

I recommend using timsort.d or stablesort.d. mergesort.d is a generic
implementation. stablequicksort.d is not recommended.

I've extensively tested each of these modules and can confirm they're stable.
More so, they're many times faster than the stable sort in Phobos. Lastly,
there are no issues regarding the dollar token $ (range.length is used as
necessary).

I provide all of these modules to the public domain. That means anybody is free
to implement any of these modules into Phobos.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Sep 03 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4584



--- Comment #7 from Dmitry Olshansky <dmitry.olsh gmail.com> 2012-09-03
14:14:23 PDT ---
(In reply to comment #6)
 I've written a collection of sorting algorithms for D:
 https://github.com/Xinok/XSort
 
 I recommend using timsort.d or stablesort.d. mergesort.d is a generic
 implementation. stablequicksort.d is not recommended.
 
 I've extensively tested each of these modules and can confirm they're stable.
 More so, they're many times faster than the stable sort in Phobos. Lastly,
 there are no issues regarding the dollar token $ (range.length is used as
 necessary).
Yeah, I recall you had some great stuff on this. Thanks for showing up.
 I provide all of these modules to the public domain. That means anybody is free
 to implement any of these modules into Phobos.
Great, I'll look into making a pull request to do just that. With a proper attribution, of course. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Sep 03 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4584


yebblies <yebblies gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |pull
                 CC|                            |yebblies gmail.com
           Platform|Other                       |All
         AssignedTo|andrei metalanguage.com     |dmitry.olsh gmail.com


--- Comment #8 from yebblies <yebblies gmail.com> 2012-10-28 03:21:52 EST ---
Dmitry's pull:

https://github.com/D-Programming-Language/phobos/pull/787

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 27 2012
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4584


Dmitry Olshansky <dmitry.olsh gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


--- Comment #9 from Dmitry Olshansky <dmitry.olsh gmail.com> 2012-12-13
12:32:45 PST ---
Strangely it didn't pick up commits.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Dec 13 2012