digitalmars.D.bugs - [Issue 6192] New: std.algorithm.sort performance
- d-bugmail puremagic.com (36/36) Jun 21 2011 http://d.puremagic.com/issues/show_bug.cgi?id=6192
- d-bugmail puremagic.com (25/25) Jun 26 2011 http://d.puremagic.com/issues/show_bug.cgi?id=6192
- d-bugmail puremagic.com (24/24) Jul 06 2011 http://d.puremagic.com/issues/show_bug.cgi?id=6192
- d-bugmail puremagic.com (11/35) Jul 06 2011 http://d.puremagic.com/issues/show_bug.cgi?id=6192
- d-bugmail puremagic.com (26/26) Jul 11 2011 http://d.puremagic.com/issues/show_bug.cgi?id=6192
http://d.puremagic.com/issues/show_bug.cgi?id=6192 Summary: std.algorithm.sort performance Product: D Version: D2 Platform: All OS/Version: All Status: NEW Keywords: performance Severity: enhancement Priority: P2 Component: Phobos AssignedTo: nobody puremagic.com ReportedBy: bearophile_hugs eml.cc Created an attachment (id=1004) sort bench The small benchmark program shows the performance of std.algorithm.sort compared to a different one (it doesn't accept a key sort function, etc). One output example: sort-sort2 benchmarks (milliseconds), N=6000000: Random distribution: sort: 4131 sort2: 2635 Already sorted arrays: sort: 1979 sort2: 787 Inverted order arrays: sort: 2105 sort2: 1374 Few random doubles appended to the sorted arrays: sort: 2890 sort2: 1551 See also bug 5077 -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jun 21 2011
http://d.puremagic.com/issues/show_bug.cgi?id=6192 Dmitry Olshansky <dmitry.olsh gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |dmitry.olsh gmail.com 08:35:32 PDT --- Results for me on upcomming 2.054 Phobos: sort-sort2 benchmarks (milliseconds), N=6000000: Random distribution: sort: 1040 sort2: 1012 Already sorted arrays: sort: 357 sort2: 312 Inverted order arrays: sort: 361 sort2: 576 Few random doubles appended to the sorted arrays: sort: 3657 sort2: 482 compiled with: dmd -O -inline -release sort_bench.d -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jun 26 2011
http://d.puremagic.com/issues/show_bug.cgi?id=6192 Was this update in the sort code caused by this enhancement request, or are they unrelated? Timings with DMD 2.054beta, a different CPU: sort-sort2 benchmarks (milliseconds), N=6000000: Random distribution: sort: 1892 sort2: 1131 Already sorted arrays: sort: 748 sort2: 376 Inverted order arrays: sort: 1048 sort2: 656 Few random doubles appended to the sorted arrays: sort: 3085 sort2: 734 It seems the random case is improved a lot, the already sorted case is improved, the inverted order is about the same, and the few random values added case is slower than before. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jul 06 2011
http://d.puremagic.com/issues/show_bug.cgi?id=6192 kennytm gmail.com changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |kennytm gmail.comWas this update in the sort code caused by this enhancement request, or are they unrelated? Timings with DMD 2.054beta, a different CPU: sort-sort2 benchmarks (milliseconds), N=6000000: Random distribution: sort: 1892 sort2: 1131 Already sorted arrays: sort: 748 sort2: 376 Inverted order arrays: sort: 1048 sort2: 656 Few random doubles appended to the sorted arrays: sort: 3085 sort2: 734 It seems the random case is improved a lot, the already sorted case is improved, the inverted order is about the same, and the few random values added case is slower than before.https://github.com/D-Programming-Language/phobos/pull/74 -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jul 06 2011
http://d.puremagic.com/issues/show_bug.cgi?id=6192 Thank you for your work. The new timings (after pull 74): sort-sort2 benchmarks (milliseconds), N=6000000: Random distribution: sort: 1261 sort2: 1201 Already sorted arrays: sort: 300 sort2: 441 Inverted order arrays: sort: 315 sort2: 729 Few random doubles appended to the sorted arrays: sort: 9962 sort2: 632 The last case is a common use case in Python code. Python programmers sometimes append unsorted items to a sorted list, and once in a while they sort it. Because the Timsort used in Python (and Java) is able to face this case very well, this is an efficient strategy to keep a rarely updated list sorted in Python. I don't know how much common this pattern is in real D code (but experience shows that often real-world data is already partially sorted). -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jul 11 2011