<div dir="ltr">Does this rely on Common Subexpression Elimination optimization in order to work? Would it work more reliably if the `seq`-ed expression were let-bound? </div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature" data-smartmail="gmail_signature">-- Dan Burton</div></div>
<br><div class="gmail_quote">On Mon, Mar 27, 2017 at 5:41 PM, David Feuer <span dir="ltr"><<a href="mailto:david.feuer@gmail.com" target="_blank">david.feuer@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto">The first seq is useless: constructor application is never suspended. I haven't had a chance to look at the rest yet.</div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Mar 27, 2017 7:59 PM, "Gregory Popovitch" <<a href="mailto:greg7mdp@gmail.com" target="_blank">greg7mdp@gmail.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><u></u>



<div>
<div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140146023323-27032017"><font face="Calibri"><font color="#000080"><span class="m_-8278973055558469163m_8686323323360374140755023923-27032017">Sid, 
</span></font></font></span></div>
<div dir="ltr" align="left">
<div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140146023323-27032017"><font face="Calibri"><font color="#000080"><span class="m_-8278973055558469163m_8686323323360374140755023923-27032017"></span></font></font></span> </div>
<div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140146023323-27032017"><font face="Calibri"><font color="#000080"><span class="m_-8278973055558469163m_8686323323360374140755023923-27032017"></span>I'd be delighted to 
submit<span class="m_-8278973055558469163m_8686323323360374140755023923-27032017"> </span>the patch, as long as I have 
permission (which I probably don't), you feel confident about the change and 
maybe a couple of other people agree.</font></font></span></div>
<div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140146023323-27032017"><font color="#000080" face="Calibri"></font></span> </div>
<div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140146023323-27032017"><font face="Calibri"><font color="#000080">Here is the proposed change. Tests shows significant speed 
improvement (30%) when sorting lists of random numbers, and same efficiency for 
sorting already sorted lists (both ascending and descending).<span class="m_-8278973055558469163m_8686323323360374140523135523-27032017"> </span></font></font></span></div>
<div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140146023323-27032017"><font face="Calibri"><font color="#000080"><span class="m_-8278973055558469163m_8686323323360374140523135523-27032017"> </span></font></font></span></div>
<div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140146023323-27032017"><font color="#000080" face="Calibri"><img src="cid:523135523@27032017-0380"></font></span></div>
<div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140146023323-27032017"></span><span class="m_-8278973055558469163m_8686323323360374140146023323-27032017"><font color="#000080" face="Calibri"></font></span> </div>
<div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140146023323-27032017"><font color="#000080" face="Calibri">Thanks,</font></span></div>
<div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140146023323-27032017"><font color="#000080" face="Calibri"></font></span> </div>
<div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140146023323-27032017"><font color="#000080" face="Calibri">greg</font></span></div></div><br>
<div lang="en-us" class="m_-8278973055558469163m_8686323323360374140OutlookMessageHeader" dir="ltr" align="left">
<hr>
<font size="2" face="Tahoma"><b>From:</b> <a href="mailto:siddhanathan@gmail.com" target="_blank">siddhanathan@gmail.com</a> 
[mailto:<a href="mailto:siddhanathan@gmail.com" target="_blank">siddhanathan@gmail.com</a><wbr>] <b>On Behalf Of </b>Siddhanathan 
Shanmugam<br><b>Sent:</b> Monday, March 27, 2017 6:53 PM<br><b>To:</b> Gregory 
Popovitch<br><b>Subject:</b> RE: Proposal: a new implementation for 
Data.List.sort and Data.List.sortBy, which has better performance 
characteristics and is more laziness-friendly.<br></font><br></div>
<div></div>
<div>
<div>Since I don't see any regressions, this doesn't really need CLC approval. 
The changes are also small enough that a Github PR may be accepted (otherwise, 
the change goes in via Phabricator).<br></div>
<div><br></div>
<div>Are you interested in implementing this patch? If yes, a standard Github PR 
should be fine. Right now gSort is a three line change I think. It will be 
changed in ghc/libraries/base/Data/OldLis<wbr>t.hs on the ghc/ghc repo on 
Github.</div>
<div><br></div>
<div><span style="FONT-FAMILY:sans-serif">I'm hoping for some more comments 
from other Haskellers, before pushing for this change in base. I feel like we 
may be missing a potential optimization that someone else might spot. So 
probably going to wait a few days. </span><br></div><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Mar 27, 2017 11:43 AM, "Gregory Popovitch" <<a href="mailto:greg7mdp@gmail.com" target="_blank">greg7mdp@gmail.com</a>> wrote:<br type="attribution">
<blockquote class="m_-8278973055558469163m_8686323323360374140quote" style="PADDING-LEFT:1ex;BORDER-LEFT:#ccc 1px solid;MARGIN:0px 0px 0px 0.8ex"><u></u>
  <div>
  <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236217273418-27032017"><font color="#000080" face="Calibri">Hi Sid,</font></span></div>
  <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236217273418-27032017"><font color="#000080" face="Calibri"></font></span> </div>
  <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236217273418-27032017"><font color="#000080" face="Calibri">Thanks, glad you looked into that. My understanding of the 
  Haskell execution model is really poor, so I can't say one way or 
  the other, but I felt that laziness ought to be considered as well, and 
  I'm glad it was :-)</font></span></div>
  <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236217273418-27032017"><font color="#000080" face="Calibri"></font></span> </div>
  <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236217273418-27032017"><font color="#000080" face="Calibri">So  in conclusion it looks like we have a winner with 
  your latest gSortBy version. How do we get this pushed to the GHC 
  library?</font></span></div>
  <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236217273418-27032017"><font color="#000080" face="Calibri"></font></span> </div>
  <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236217273418-27032017"><font color="#000080" face="Calibri">Thanks,</font></span></div>
  <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236217273418-27032017"><font color="#000080" face="Calibri"></font></span> </div>
  <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236217273418-27032017"><font color="#000080" face="Calibri">greg</font></span></div><br>
  <div lang="en-us" class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236OutlookMessageHeader" dir="ltr" align="left">
  <hr>
  <font size="2" face="Tahoma">
  <div class="m_-8278973055558469163m_8686323323360374140quoted-text"><b>From:</b> <a href="mailto:siddhanathan@gmail.com" target="_blank">siddhanathan@gmail.com</a> [mailto:<a href="mailto:siddhanathan@gmail.com" target="_blank">siddhanathan@gmail.com</a><wbr>] <b>On Behalf Of 
  </b>Siddhanathan Shanmugam<br></div><b>Sent:</b> Monday, March 27, 2017 2:12 
  PM<br><b>To:</b> Gregory Popovitch 
  <div class="m_-8278973055558469163m_8686323323360374140elided-text"><br><b>Subject:</b> Re: Proposal: a new implementation 
  for Data.List.sort and Data.List.sortBy, which has better performance 
  characteristics and is more laziness-friendly.<br></div></font><br></div>
  <div class="m_-8278973055558469163m_8686323323360374140elided-text">
  <div></div>
  <div dir="ltr">Hi Greg,<br>
  <div class="gmail_extra"><br>
  <div class="gmail_quote">On Mon, Mar 27, 2017 at 10:19 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="PADDING-LEFT:1ex;BORDER-LEFT:rgb(204,204,204) 1px solid;MARGIN:0px 0px 0px 0.8ex"><u></u>
    <div>
    <div dir="ltr" align="left"><font color="#000080" face="Calibri"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017">Unfortunately, 
    this optimization makes the sort less lazy, so doing something 
    like:</span></font></div>
    <div dir="ltr" align="left"><font color="#000080" face="Calibri"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017"></span></font> </div>
    <div dir="ltr" align="left"><font color="#000080" face="Calibri"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017">take 4 $ 
    sort l</span></font></div>
    <div dir="ltr" align="left"><font color="#000080" face="Calibri"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017"></span></font> </div>
    <div dir="ltr" align="left"><font color="#000080" face="Calibri"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017">requires 
    more sorting of the list l with this change. I'm not sure it is a good 
    tradeoff.</span></font></div>
    <div dir="ltr" align="left"><font color="#000080" face="Calibri"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017"></span></font> </div>
    <div dir="ltr" align="left"><font color="#000080" face="Calibri"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017">This 
    can be verified with: <a href="https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs" target="_blank">https://github.com/greg7mdp/gh<wbr>c-sort/blob/master/src/sort_wi<wbr>th_trace.hs</a></span></font></div></div></blockquote>
  <div><br></div>
  <div>I think you're running without optimizations turned on. It is lazy in my 
  case.</div>
  <div><br></div>
  <div>Also, the difference should be negligible (if any at all). Here's an 
  example of the list being sorted:</div>
  <div><br></div>
  <div>
  <div>[11,4,6,8,2,5,1,7,9,55,11,3]</div></div>
  <div>...</div>
  <div>[[4,11],[6,8],[2,5],[1,7,9,55]<wbr>,[3,11],[]]<br></div>
  <div>...</div>
  <div>
  <div>[[1,2,4,5,6,7,8,9,11,55],[3,11<wbr>]]</div>
  <div> * 1 3</div>
  <div> * 2 3</div>
  <div> * 4 3</div>
  <div> * 4 11</div>
  <div>[1,2,3,4]</div></div>
  <div><br></div>
  <div>The number of operations saved is only in the last merge. It's only lazy 
  at this step.</div>
  <div><br></div>
  <div>So we save at most one traversal of the list, which is not too expensive 
  since our worst case bounds is O(n log n) anyway.</div>
  <div><br></div>
  <div>This should mean that the asymptotic performance should be identical, 
  regardless of the number of comparisons saved. Of course, you do get better 
  constants, but I would be surprised if those constants translated to 
  significantly better performance for a reasonable size list.</div>
  <div> </div>
  <blockquote class="gmail_quote" style="PADDING-LEFT:1ex;BORDER-LEFT:rgb(204,204,204) 1px solid;MARGIN:0px 0px 0px 0.8ex">
    <div>
    <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017"><font color="#000080" face="Calibri"></font></span> </div>
    <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017"> <font color="#000080" face="Calibri">I do agree that it would be nice to have a more 
    serious validation test suite.</font></span></div>
    <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017"><font color="#000080" face="Calibri"></font></span> </div>
    <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017"><font color="#000080" face="Calibri">Thanks,</font></span></div>
    <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017"><font color="#000080" face="Calibri"></font></span> </div>
    <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017"><font color="#000080" face="Calibri">greg</font></span></div>
    <div dir="ltr" align="left"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618136311517-27032017"></span> </div>
    <div dir="ltr" align="left">
    <hr>
    </div>
    <div dir="ltr" align="left"><font size="2" face="Tahoma"><span class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-"><b>From:</b> <a href="mailto:siddhanathan@gmail.com" target="_blank">siddhanathan@gmail.com</a> [mailto:<a href="mailto:siddhanathan@gmail.com" target="_blank">siddhanathan@gmail.com</a><wbr>] <b>On Behalf Of 
    </b>Siddhanathan Shanmugam<br></span><b>Sent:</b> Monday, March 27, 2017 
    12:53 PM 
    <div>
    <div class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-h5"><br><b>To:</b> Gregory 
    Popovitch<br><b>Cc:</b> Haskell Libraries<br><b>Subject:</b> Re: Proposal: a 
    new implementation for Data.List.sort and Data.List.sortBy, which has better 
    performance characteristics and is more 
    laziness-friendly.<br></div></div></font><br></div>
    <div>
    <div class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-h5">
    <div></div>
    <div dir="ltr">
    <div>We can improve things a bit further by forcing evaluation (with seq) 
    along the way appropriately.<br></div>
    <div><br></div>
    <div><br></div>
    <div><br></div>
    <div>
    <div><span style="FONT-FAMILY:monospace,monospace">gregSortBy cmp [] = 
    []</span><br></div>
    <div><font face="monospace, monospace">gregSortBy cmp xs = head $ until 
    (null.tail) reduce (pair xs)</font></div>
    <div><font face="monospace, monospace">  where</font></div>
    <div><font face="monospace, monospace">    pair (x:y:t) | x `cmp` 
    y == GT  = [y, x] : pair t</font></div>
    <div><font face="monospace, monospace">          
           | otherwise        = [x, y] : 
    pair t</font></div>
    <div><font face="monospace, monospace">    pair [x] = 
    [[x]]</font></div>
    <div><font face="monospace, monospace">    pair []  = 
    []</font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace">    reduce (v:w:x:y:t) = 
    merge v' x' `seq` merge v' x' : reduce t</font></div>
    <div><font face="monospace, monospace">          
                   where v' = merge v w 
    `seq` merge v w</font></div>
    <div><font face="monospace, monospace">          
                        
     x' = merge x y `seq` merge x y</font></div>
    <div><font face="monospace, monospace">          
                   </font></div>
    <div><font face="monospace, monospace">    reduce (x:y:t) = merge 
    x y `seq` merge x y : reduce t</font></div>
    <div><font face="monospace, monospace">    reduce xs     
     = xs</font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace">    merge xs []   
            = xs</font></div>
    <div><font face="monospace, monospace">    merge []  ys 
             = ys</font></div>
    <div><font face="monospace, monospace">    merge xs@(x:xs') 
    ys@(y:ys') </font></div>
    <div><font face="monospace, monospace">         | x 
    `cmp` y == GT  = y : merge xs  ys'</font></div>
    <div><font face="monospace, monospace">         | 
    otherwise        = x : merge xs' ys</font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><span style="FONT-FAMILY:monospace,monospace">gSortBy cmp = mergeAll . 
    sequences</span><br></div>
    <div><font face="monospace, monospace">  where</font></div>
    <div><font face="monospace, monospace">    sequences 
    (a:b:xs)</font></div>
    <div><font face="monospace, monospace">      | a `cmp` b == 
    GT = descending b [a]  xs</font></div>
    <div><font face="monospace, monospace">      | otherwise 
          = ascending  b (a:) xs</font></div>
    <div><font face="monospace, monospace">    sequences xs = 
    [xs]</font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace">    descending a as 
    (b:bs)</font></div>
    <div><font face="monospace, monospace">      | a `cmp` b == 
    GT = descending b (a:as) bs</font></div>
    <div><font face="monospace, monospace">    descending a as bs 
     = (a:as) `seq` (a:as) : sequences bs</font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace">    ascending a as 
    (b:bs)</font></div>
    <div><font face="monospace, monospace">      | a `cmp` b /= 
    GT = ascending b (as . (a:)) bs</font></div>
    <div><font face="monospace, monospace">    ascending a as bs 
      = as [a] `seq` as [a] : sequences bs</font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace">    mergeAll [x] = 
    x</font></div>
    <div><font face="monospace, monospace">    mergeAll xs  = 
    mergeAll (mergePairs xs)</font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace">    mergePairs (a:b:xs) = 
    merge a b `seq` merge a b : mergePairs xs</font></div>
    <div><font face="monospace, monospace">    mergePairs xs   
        = xs</font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace">    merge as@(a:as') 
    bs@(b:bs')</font></div>
    <div><font face="monospace, monospace">      | a `cmp` b == 
    GT = b : merge as  bs'</font></div>
    <div><font face="monospace, monospace">      | otherwise 
          = a : merge as' bs</font></div>
    <div><font face="monospace, monospace">    merge [] bs   
          = bs</font></div>
    <div><font face="monospace, monospace">    merge as []   
          = as</font></div></div>
    <div><br></div>
    <div><br></div>
    <div><br></div>
    <div><br></div>
    <div><b>Before the change:</b></div>
    <div><br></div>
    <div>
    <div><font face="monospace, monospace">benchmarking random 
    ints/ghc</font></div>
    <div><font face="monospace, monospace">time         
            3.687 s    (3.541 s .. NaN 
    s)</font></div>
    <div><font face="monospace, monospace">          
               1.000 R²   (1.000 R² .. 1.000 
    R²)</font></div>
    <div><font face="monospace, monospace">mean         
            3.691 s    (3.669 s .. 3.705 
    s)</font></div>
    <div><font face="monospace, monospace">std dev         
         21.45 ms   (0.0 s .. 24.76 ms)</font></div>
    <div><font face="monospace, monospace">variance introduced by outliers: 19% 
    (moderately inflated)</font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace">benchmarking random 
    ints/greg</font></div>
    <div><font face="monospace, monospace">time         
            2.648 s    (2.482 s .. 2.822 
    s)</font></div>
    <div><font face="monospace, monospace">          
               0.999 R²   (0.998 R² .. 1.000 
    R²)</font></div>
    <div><font face="monospace, monospace">mean         
            2.704 s    (2.670 s .. 2.736 
    s)</font></div>
    <div><font face="monospace, monospace">std dev         
         52.68 ms   (0.0 s .. 54.49 ms)</font></div>
    <div><font face="monospace, monospace">variance introduced by outliers: 19% 
    (moderately inflated)</font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace">benchmarking random 
    ints/gSort</font></div>
    <div><font face="monospace, monospace">time         
            2.733 s    (2.682 s .. 2.758 
    s)</font></div>
    <div><font face="monospace, monospace">          
               1.000 R²   (1.000 R² .. 1.000 
    R²)</font></div>
    <div><font face="monospace, monospace">mean         
            2.707 s    (2.689 s .. 2.718 
    s)</font></div>
    <div><font face="monospace, monospace">std dev         
         16.84 ms   (0.0 s .. 19.20 ms)</font></div>
    <div><font face="monospace, monospace">variance introduced by outliers: 19% 
    (moderately inflated)</font></div></div>
    <div><br></div>
    <div><b>After the change:</b></div>
    <div><br></div>
    <div>
    <div><font face="monospace, monospace">benchmarking random 
    ints/greg</font></div>
    <div><font face="monospace, monospace">time         
            2.576 s    (2.548 s .. 2.628 
    s)</font></div>
    <div><font face="monospace, monospace">          
               1.000 R²   (1.000 R² .. 1.000 
    R²)</font></div>
    <div><font face="monospace, monospace">mean         
            2.590 s    (2.578 s .. 2.599 
    s)</font></div>
    <div><font face="monospace, monospace">std dev         
         12.99 ms   (0.0 s .. 14.89 ms)</font></div>
    <div><font face="monospace, monospace">variance introduced by outliers: 19% 
    (moderately inflated)</font></div>
    <div><font face="monospace, monospace"><br></font></div>
    <div><font face="monospace, monospace">benchmarking random 
    ints/gSort</font></div>
    <div><font face="monospace, monospace">time         
            2.538 s    (2.412 s .. 2.627 
    s)</font></div>
    <div><font face="monospace, monospace">          
               1.000 R²   (0.999 R² .. 1.000 
    R²)</font></div>
    <div><font face="monospace, monospace">mean         
            2.543 s    (2.517 s .. 2.560 
    s)</font></div>
    <div><font face="monospace, monospace">std dev         
         26.16 ms   (0.0 s .. 30.21 ms)</font></div>
    <div><font face="monospace, monospace">variance introduced by outliers: 19% 
    (moderately inflated)</font></div></div>
    <div><br></div>
    <div><br></div>
    <div><br></div>
    <div><br></div></div>
    <div class="gmail_extra"><br>
    <div class="gmail_quote">On Sun, Mar 26, 2017 at 1:54 PM, Siddhanathan 
    Shanmugam <span dir="ltr"><<a href="mailto:siddhanathan+eml@gmail.com" target="_blank">siddhanathan+eml@gmail.com</a>></span> wrote:<br>
    <blockquote class="gmail_quote" style="PADDING-LEFT:1ex;BORDER-LEFT:rgb(204,204,204) 1px solid;MARGIN:0px 0px 0px 0.8ex">
      <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><span>
      <div><br></div>
      <div><span style="FONT-SIZE:12px"><br></span></div>
      <div><span style="FONT-SIZE:12px">> However, still my version is more 
      laziness-friendly, i.e. it requires fewer</span><br></div>
      <div><span style="FONT-SIZE:12px">> comparisons to get the</span><br style="FONT-SIZE:12px"><span style="FONT-SIZE:12px">> N smallest 
      elements of a list </span><span style="FONT-SIZE:12px">(see</span><br></div>> <a style="FONT-SIZE:12px" 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><span style="FONT-SIZE:12px">).</span> 
      <div><span style="FONT-SIZE:12px">></span></div>
      <div><span style="FONT-SIZE:12px">> I wonder if this might not be a 
      more useful trait than being able to sort</span><br></div>
      <div><span style="FONT-SIZE:12px">> already sorted lists super 
      fast.</span><br></div>
      <div><span style="FONT-SIZE:12px"><br></span></div></span>
      <div><span style="FONT-SIZE:12px">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="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618HOEnZb">
      <div class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618h5">
      <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="PADDING-LEFT:1ex;BORDER-LEFT:rgb(204,204,204) 1px solid;MARGIN:0px 0px 0px 0.8ex">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/gh<wbr>c-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/gh<wbr>c-sort/blob/master/src/sort_wi<wbr>th_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><br>Thanks,<br><br>greg<br><br>______________________________<wbr>__<br><br>From: 
        <a href="mailto:siddhanathan@gmail.com" target="_blank">siddhanathan@gmail.com</a> [mailto:<a href="mailto:siddhanathan@gmail.com" target="_blank">siddhanathan@gmail.com</a><wbr>] On Behalf 
        Of<br>Siddhanathan Shanmugam<br></span>Sent: Sunday, March 26, 2017 1:05 
        PM<br><span>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="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618m_6283889194055629001h5">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" target="_blank">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/g<wbr>hc-sort</a><br></div></div><<a href="https://github.com/greg7mdp/ghc-sort" rel="noreferrer" target="_blank">https://github.com/greg7mdp/g<wbr>hc-sort</a>> )<br>
        <div>
        <div class="m_-8278973055558469163m_8686323323360374140m_-3409671060788413236gmail-m_-5012754740519492618m_6283889194055629001h5">  
              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" target="_blank">siddhanathan@gmail.com</a> [mailto:<a href="mailto:siddhanathan@gmail.com" target="_blank">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" target="_blank">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/gh<wbr>c-sort</a><br><<a href="https://github.com/greg7mdp/ghc-sort" rel="noreferrer" target="_blank">https://github.com/greg7mdp/g<wbr>hc-sort</a>><br><br>  
              <<a href="https://github.com/greg7mdp/ghc-sort" rel="noreferrer" target="_blank">https://github.com/greg7mdp/g<wbr>hc-sort</a><br><<a href="https://github.com/greg7mdp/ghc-sort" rel="noreferrer" target="_blank">https://github.com/greg7mdp/g<wbr>hc-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/gh<wbr>c-sort/blob/master/src/sort_wi<wbr>th_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/g<wbr>hc-sort/blob/master/src/sort_w<wbr>ith_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/g<wbr>hc-sort/blob/master/src/sort_w<wbr>ith_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/g<wbr>hc-sort/blob/master/src/sort_w<wbr>ith_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" target="_blank">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-bi<wbr>n/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-b<wbr>in/mailman/listinfo/libraries</a>><br><br></div></div>  
              <<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-b<wbr>in/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-b<wbr>in/mailman/listinfo/libraries</a>> 
        ><br><br><br><br><br><br><br><br><br></blockquote></div><br></div></div></div></blockquote></div><br></div></div></div></div></blockquote></div><br></div></div></div></div></blockquote></div><br></div></div></div>
<br>______________________________<wbr>_________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank">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-bi<wbr>n/mailman/listinfo/libraries</a><br>
<br></blockquote></div></div>
</div></div><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>
<br></blockquote></div><br></div>