<div dir="ltr"><div><div>Theoretically, we could do better. We currently only exploit monotonic runs in merge sort, but we could also exploit bitonic runs:</div><div><br></div><div><div><font face="monospace, monospace"> dlist as = as [] `seq` as []<br></font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace"> sequences [] = [[]]</font></div><div><font face="monospace, monospace"> sequences [a] = [[a]]</font></div><div><font face="monospace, monospace"> sequences (a:xs) = bitonic a a (a:) xs</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace"> bitonic min max as (b:bs)</font></div><div><font face="monospace, monospace"> | b `cmp` max /= LT = bitonic min b (as . (b:)) bs</font></div><div><font face="monospace, monospace"> | b `cmp` min /= GT = bitonic b max ((b:) . as) bs</font></div><div><font face="monospace, monospace"> | otherwise = dlist as : sequences (b:bs)</font></div><div><font face="monospace, monospace"> bitonic _ _ as [] = [dlist as]</font></div><div><br></div></div></div><div><br></div><div>The constant factors here might be too high to notice the difference though.</div><div><br></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">> However, still my version is more laziness-friendly, i.e. it requires fewer</span><br></div><div><span style="font-size:12.8px">> comparisons to get the</span><br style="font-size:12.8px"><span style="font-size:12.8px">> N smallest elements of a list </span><span style="font-size:12.8px">(see</span><br></div>> <a href="https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs" rel="noreferrer" target="_blank" style="font-size:12.8px">https://github.com/greg7mdp/<wbr>ghc-sort/blob/master/src/sort_<wbr>with_trace.hs</a><span style="font-size:12.8px">).</span><div><span style="font-size:12.8px">></span></div><div><span style="font-size:12.8px">> I wonder if this might not be a more useful trait than being able to sort</span><br></div><div><span style="font-size:12.8px">> already sorted lists super fast.</span><br></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">This comes down to a discussion of merge sort vs natural merge sort.</span></div><div><br></div><div>Data.List.sort is an implementation of a variant of merge sort called natural merge sort. The algorithm is linearithmic in the worst case, but linear in the best case (already sorted list).</div><div><br></div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Mar 26, 2017 at 10:47 AM, Gregory Popovitch <span dir="ltr"><<a href="mailto:greg7mdp@gmail.com" target="_blank">greg7mdp@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Thanks again @Siddhanathan! Looks like your gSort fixes the main issue with<br>
Data.List.sort().<br>
<br>
I have updated the test programs in <a href="https://github.com/greg7mdp/ghc-sort" rel="noreferrer" target="_blank">https://github.com/greg7mdp/<wbr>ghc-sort</a> to<br>
include your new version.<br>
<br>
Here are the results (your new version looks like a definite improvement vs<br>
the current GHC one):<br>
<br>
input GHC sort My Orig proposal gSort<br>
------------------------------<wbr>------------------------------<wbr>----------------<br>
---<br>
sorted ints (ascending) 151 456 148<br>
sorted ints (descending) 152 466 155<br>
random ints 2732 2006 2004<br>
random strings 6564 5549 5528<br>
<br>
<br>
So replacing the current GHC version with gSort is a no brainer, as it is<br>
better in all regards.<br>
<br>
However, still my version is more laziness-friendly, i.e. it requires fewer<br>
comparisons to get the<br>
N smallest elements of a list (see<br>
<a href="https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs" rel="noreferrer" target="_blank">https://github.com/greg7mdp/<wbr>ghc-sort/blob/master/src/sort_<wbr>with_trace.hs</a>).<br>
<br>
I wonder if this might not be a more useful trait than being able to sort<br>
already sorted lists super fast.<br>
<span class=""><br>
Thanks,<br>
<br>
greg<br>
<br>
______________________________<wbr>__<br>
<br>
From: <a href="mailto:siddhanathan@gmail.com">siddhanathan@gmail.com</a> [mailto:<a href="mailto:siddhanathan@gmail.com">siddhanathan@gmail.com</a><wbr>] On Behalf Of<br>
Siddhanathan Shanmugam<br>
</span>Sent: Sunday, March 26, 2017 1:05 PM<br>
<span class="">To: Gregory Popovitch<br>
Cc: Haskell Libraries<br>
Subject: Re: Proposal: a new implementation for Data.List.sort and<br>
Data.List.sortBy, which has better performance characteristics and is more<br>
laziness-friendly.<br>
<br>
<br>
</span><div><div class="h5">Interesting. You are right, performance for sorting random lists has<br>
priority over performance for sorting already-sorted lists.<br>
<br>
Ignore the numbers for my previous version. Can you compare GHC's sort, your<br>
proposal, and gSort below?<br>
<br>
<br>
gSort :: Ord a => [a] -> [a]<br>
gSort = gSortBy compare<br>
gSortBy cmp = mergeAll . sequences<br>
where<br>
sequences (a:b:xs)<br>
| a `cmp` b == GT = descending b [a] xs<br>
| otherwise = ascending b (a:) xs<br>
sequences xs = [xs]<br>
<br>
<br>
descending a as (b:bs)<br>
| a `cmp` b == GT = descending b (a:as) bs<br>
descending a as bs = (a:as) : sequences bs<br>
<br>
<br>
ascending a as (b:bs)<br>
| a `cmp` b /= GT = ascending b (\ys -> as (a:ys)) bs<br>
ascending a as bs = as [a] `seq` as [a] : sequences bs<br>
<br>
<br>
mergeAll [x] = x<br>
mergeAll xs = mergeAll (mergePairs xs)<br>
<br>
<br>
mergePairs (a:b:xs) = merge a b : mergePairs xs<br>
mergePairs xs = xs<br>
<br>
<br>
merge as@(a:as') bs@(b:bs')<br>
| a `cmp` b == GT = b : merge as bs'<br>
| otherwise = a : merge as' bs<br>
merge [] bs = bs<br>
merge as [] = as<br>
<br>
<br>
Thanks,<br>
Sid<br>
<br>
<br>
On Sun, Mar 26, 2017 at 9:19 AM, Gregory Popovitch <<a href="mailto:greg7mdp@gmail.com">greg7mdp@gmail.com</a>><br>
wrote:<br>
<br>
<br>
Thank you @Siddhanathan! I welcome any improvement you may make, as<br>
I said I<br>
am very far from a Haskell expert.<br>
<br>
I just tested your change with my test project<br>
(<a href="https://github.com/greg7mdp/ghc-sort" rel="noreferrer" target="_blank">https://github.com/greg7mdp/<wbr>ghc-sort</a><br>
</div></div><<a href="https://github.com/greg7mdp/ghc-sort" rel="noreferrer" target="_blank">https://github.com/greg7mdp/<wbr>ghc-sort</a>> )<br>
<div><div class="h5"> and here are my results (mean times in ms):<br>
<br>
input GHC sort Orig proposal<br>
your<br>
change<br>
<br>
------------------------------<wbr>------------------------------<wbr>----------------<br>
---<br>
sorted ints (ascending) 153 467<br>
139<br>
sorted ints (descending) 152 472<br>
599<br>
random ints 2824 2077<br>
2126<br>
random strings 6564 5613<br>
5983<br>
<br>
Your change is a definite improvement for sorted integers in<br>
ascending<br>
order, but is worse for other cases.<br>
<br>
Is there a real need to optimize the sort for already sorted list?<br>
Of course<br>
it should not be a degenerate<br>
case and take longer than sorting random numbers, but this is not<br>
the case<br>
here. Sorting already sorted<br>
lists is, even with my version, over 4 times faster than sorting<br>
random<br>
lists. This sounds perfectly<br>
acceptable to me, and I feel that trying to optimize this specific<br>
case<br>
further, if it comes at the<br>
detriment of the general case, is not desirable.<br>
<br>
Thanks,<br>
<br>
greg<br>
<br>
______________________________<wbr>__<br>
<br>
From: <a href="mailto:siddhanathan@gmail.com">siddhanathan@gmail.com</a> [mailto:<a href="mailto:siddhanathan@gmail.com">siddhanathan@gmail.com</a><wbr>] On<br>
Behalf Of<br>
Siddhanathan Shanmugam<br>
Sent: Sunday, March 26, 2017 11:41 AM<br>
To: Gregory Popovitch<br>
Cc: Haskell Libraries<br>
Subject: Re: Proposal: a new implementation for Data.List.sort and<br>
Data.List.sortBy, which has better performance characteristics and<br>
is more<br>
laziness-friendly.<br>
<br>
<br>
<br>
Thank you! This identifies a space leak in base which went unnoticed<br>
for 7<br>
years.<br>
<br>
Your implementation can be improved further. Instead of splitting<br>
into<br>
pairs, you could instead split into lists of sorted sublists by<br>
replacing<br>
the pairs function with the following<br>
<br>
pair = foldr f []<br>
where<br>
f x [] = [[x]]<br>
f x (y:ys)<br>
| x `cmp` head y == LT = (x:y):ys<br>
| otherwise = [x]:y:ys<br>
<br>
This should give you the same performance improvements for sorting<br>
random<br>
lists, but better performance while sorting ascending lists.<br>
<br>
The version in base takes it one step further by using a DList to<br>
handle the<br>
descending case efficiently as well, except there's a space leak<br>
right now<br>
because of which it is slower.<br>
<br>
On Sun, Mar 26, 2017 at 7:21 AM, Gregory Popovitch<br>
<<a href="mailto:greg7mdp@gmail.com">greg7mdp@gmail.com</a>><br>
wrote:<br>
<br>
<br>
<br>
Motivation:<br>
----------<br>
<br>
Data.List.sort is a very important functionality in Haskell.<br>
I<br>
believe that<br>
the proposed implementation is:<br>
<br>
- significantly faster than the current implementation on<br>
unsorted<br>
lists,<br>
typically 14% to 27% faster<br>
- more laziness-friendly, i.e.:<br>
take 3 $ sort l<br>
will require significantly less comparisons than the<br>
current<br>
implementation<br>
<br>
Proposed Implementation<br>
-----------------------<br>
<br>
sort :: (Ord a) => [a] -> [a]<br>
sort = sortBy compare<br>
<br>
sortBy cmp [] = []<br>
sortBy cmp xs = head $ until (null.tail) reduce (pair xs)<br>
where<br>
pair (x:y:t) | x `cmp` y == GT = [y, x] : pair t<br>
| otherwise = [x, y] : pair t<br>
pair [x] = [[x]]<br>
pair [] = []<br>
<br>
reduce (v:w:x:y:t) = merge v' x' : reduce t<br>
where v' = merge v w<br>
x' = merge x y<br>
<br>
reduce (x:y:t) = merge x y : reduce t<br>
reduce xs = xs<br>
<br>
merge xs [] = xs<br>
merge [] ys = ys<br>
merge xs@(x:xs') ys@(y:ys')<br>
| x `cmp` y == GT = y : merge xs ys'<br>
| otherwise = x : merge xs' ys<br>
<br>
<br>
Effect and Interactions<br>
-----------------------<br>
<br>
I have a stack project with a criterion test for this new<br>
implementation,<br>
available at <a href="https://github.com/greg7mdp/ghc-sort" rel="noreferrer" target="_blank">https://github.com/greg7mdp/<wbr>ghc-sort</a><br>
<<a href="https://github.com/greg7mdp/ghc-sort" rel="noreferrer" target="_blank">https://github.com/greg7mdp/<wbr>ghc-sort</a>><br>
<br>
<<a href="https://github.com/greg7mdp/ghc-sort" rel="noreferrer" target="_blank">https://github.com/greg7mdp/<wbr>ghc-sort</a><br>
<<a href="https://github.com/greg7mdp/ghc-sort" rel="noreferrer" target="_blank">https://github.com/greg7mdp/<wbr>ghc-sort</a>> > .<br>
I ran the tests on an Ubuntu 14.0.2 VM and GHC 8.0.2, and<br>
had the<br>
following<br>
results:<br>
<br>
- sorting of random lists of integers is 27% faster<br>
- sorting of random lists of strings is 14% faster<br>
- sorting of already sorted lists is significantly slower,<br>
but still<br>
much<br>
faster than sorting random lists<br>
- proposed version is more laziness friendly. For example<br>
this<br>
version of<br>
sortBy requires 11 comparisons to find<br>
the smallest element of a 15 element list, while the<br>
default<br>
Data.List.sortBy requires 15 comparisons.<br>
(see<br>
<br>
<br>
<a href="https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs" rel="noreferrer" target="_blank">https://github.com/greg7mdp/<wbr>ghc-sort/blob/master/src/sort_<wbr>with_trace.hs</a><br>
<<a href="https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs" rel="noreferrer" target="_blank">https://github.com/greg7mdp/<wbr>ghc-sort/blob/master/src/sort_<wbr>with_trace.hs</a>><br>
<br>
<<a href="https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs" rel="noreferrer" target="_blank">https://github.com/greg7mdp/<wbr>ghc-sort/blob/master/src/sort_<wbr>with_trace.hs</a><br>
<<a href="https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs" rel="noreferrer" target="_blank">https://github.com/greg7mdp/<wbr>ghc-sort/blob/master/src/sort_<wbr>with_trace.hs</a>> ><br>
)<br>
<br>
<br>
<br>
Test results<br>
------------<br>
<br>
Criterion output (descending/ascending results are for<br>
already<br>
sorted<br>
lists).<br>
I barely understand what Criterion does, and I am puzzled<br>
with the<br>
various<br>
"T" output - maybe there is a bug in my bench code:<br>
<br>
vagrant@vagrant-ubuntu-trusty-<wbr>64:/vagrant$ stack exec<br>
ghc-sort<br>
benchmarking ascending ints/ghc<br>
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT<wbr>TTTTTTTtime<br>
160.6 ms<br>
(153.4<br>
ms .. 167.8 ms)<br>
0.997 R² (0.986 R² .. 1.000 R²)<br>
mean 161.7 ms (158.3 ms .. 165.9 ms)<br>
std dev 5.210 ms (3.193 ms .. 7.006 ms)<br>
variance introduced by outliers: 12% (moderately inflated)<br>
<br>
benchmarking ascending ints/greg<br>
TTTTTTTTTTTTTTTTtime 473.8 ms (398.6 ms ..<br>
554.9<br>
ms)<br>
0.996 R² (0.987 R² .. 1.000 R²)<br>
mean 466.2 ms (449.0 ms .. 475.0 ms)<br>
std dev 14.94 ms (0.0 s .. 15.29 ms)<br>
variance introduced by outliers: 19% (moderately inflated)<br>
<br>
benchmarking descending ints/ghc<br>
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT<wbr>TTTTTTTtime<br>
165.1 ms<br>
(148.2<br>
ms .. 178.2 ms)<br>
0.991 R² (0.957 R² .. 1.000 R²)<br>
mean 158.7 ms (154.0 ms .. 164.3 ms)<br>
std dev 7.075 ms (4.152 ms .. 9.903 ms)<br>
variance introduced by outliers: 12% (moderately inflated)<br>
<br>
benchmarking descending ints/greg<br>
TTTTTTTTTTTTTTTTtime 471.7 ms (419.8 ms ..<br>
508.3<br>
ms)<br>
0.999 R² (0.995 R² .. 1.000 R²)<br>
mean 476.0 ms (467.5 ms .. 480.0 ms)<br>
std dev 7.447 ms (67.99 as .. 7.865 ms)<br>
variance introduced by outliers: 19% (moderately inflated)<br>
<br>
benchmarking random ints/ghc<br>
TTTTTTTTTTTTTTTTtime 2.852 s (2.564 s ..<br>
3.019 s)<br>
0.999 R² (0.997 R² .. 1.000 R²)<br>
mean 2.812 s (2.785 s .. 2.838 s)<br>
std dev 44.06 ms (543.9 as .. 44.97 ms)<br>
variance introduced by outliers: 19% (moderately inflated)<br>
<br>
benchmarking random ints/greg<br>
TTTTTTTTTTTTTTTTtime 2.032 s (1.993 s ..<br>
2.076 s)<br>
1.000 R² (1.000 R² .. 1.000 R²)<br>
mean 2.028 s (2.019 s .. 2.033 s)<br>
std dev 7.832 ms (0.0 s .. 8.178 ms)<br>
variance introduced by outliers: 19% (moderately inflated)<br>
<br>
benchmarking shakespeare/ghc<br>
TTTTTTTTTTTTTTTTtime 6.504 s (6.391 s ..<br>
6.694 s)<br>
1.000 R² (1.000 R² .. 1.000 R²)<br>
mean 6.499 s (6.468 s .. 6.518 s)<br>
std dev 28.85 ms (0.0 s .. 32.62 ms)<br>
variance introduced by outliers: 19% (moderately inflated)<br>
<br>
benchmarking shakespeare/greg<br>
TTTTTTTTTTTTTTTTtime 5.560 s (5.307 s ..<br>
5.763 s)<br>
1.000 R² (0.999 R² .. 1.000 R²)<br>
mean 5.582 s (5.537 s .. 5.607 s)<br>
std dev 39.30 ms (0.0 s .. 43.49 ms)<br>
variance introduced by outliers: 19% (moderately inflated)<br>
<br>
<br>
Costs and Drawbacks<br>
-------------------<br>
<br>
The only cost I see is the reduced performance when sorting<br>
already<br>
sorted<br>
lists. However, since this remains quite efficient, indeed<br>
over 4<br>
times<br>
faster than sorting unsorted lists, I think it is an<br>
acceptable<br>
tradeoff.<br>
<br>
Final note<br>
----------<br>
<br>
My Haskell is very rusty. I worked on this a couple years<br>
ago when I<br>
was<br>
learning Haskell, and meant to propose it to the Haskell<br>
community,<br>
but<br>
never got to it at the time.<br>
<br>
______________________________<wbr>_________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/libraries</a><br>
<<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/libraries</a><wbr>><br>
<br>
</div></div> <<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/libraries</a><br>
<<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/libraries</a><wbr>> ><br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
</blockquote></div><br></div>