== Quote from Lutger (lutger.blijdestijn@gmail.com)'s article
>
> Some time ago I reinvented these wheels for study purpose. A custom stack was a little faster but not
that much. std.swap can't be inlined because it uses ref params, that cost also a bit since it's called
> many times. Switching to another sort if a certain recursion depth is reached helped, but mostly in
degenerate cases.
> I still have the thing somewhere, it is about twice as fast as builtin sort. It's not a lot of work but I could
dig it up and provide some timings if you want.

The sort I wrote for Tango uses the same basic heuristics, thanks to a ticket that either you or Stewart Gordon submitted long ago.  I've been meaning to compare it against the sort routine in std.algorithm to see whether the Phobos routine could benefit from any of the same tweaks.

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
> If swap is not inlined that would be serious. Sort does a lot of swapping.

It only works for arrays, but what I ended up doing to get swap inlined was to pass it two array indices instead of two references.  There must be some way to address this for ranges if ref parameters prevent inlining with DMD.

Sean Kelly wrote:
> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
>> Sean Kelly wrote:
>>> Andrei Alexandrescu wrote:
>>>> Note how the left edge of result follows the left edge of r, but the
>>>> right edge stays put because partition() returns the right-hand-side
>>>> range. r shrinks from both ends to exhaustion.
>>> So all the elements that satisfy the predicate end up at the end of the
>>> original range instead of the beginning?  Was that an arbitrary choice,
>>> or is there a reason for it?
>> The elements satisfying the predicate are at the beginning, see e.g. the
>> unittests. The range returned is (as always) the right-hand side, i.e.
>> the range containing the elements that don't satisfy the predicate.
> 
> Weird.  I'd always thought that the standard behavior was the opposite.
> That way partition could be passed a lessThan predicate and be used
> for sorting.  Though I guess you can just use a greaterThan predicate
> instead.

Nono, lessThan is a binary predicate whereas partition takes a unary predicate. The spec of partition is very simple: do whatever the hell it takes to put elements e that satisfy pred(e) before elements that don't.

If you follow the way std.sort uses partition, you'll see that it passes a unary predicate that compares for less than against the chosen pivot.


Andrei

Sean Kelly wrote:
> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
>> If swap is not inlined that would be serious. Sort does a lot of swapping.
> 
> It only works for arrays, but what I ended up doing to get swap inlined
> was to pass it two array indices instead of two references.  There must
> be some way to address this for ranges if ref parameters prevent inlining
> with DMD.

Well the least we can do is to say

static if (is(Range R == T[], T))
{
    ... use array-specific swap ...
}
else
{
    ... use regular swap ...
}


Andrei

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
> Sean Kelly wrote:
> > == Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
> >> Sean Kelly wrote:
> >>> Andrei Alexandrescu wrote:
> >>>> Note how the left edge of result follows the left edge of r, but the right edge stays put because partition() returns the right-hand-side range. r shrinks from both ends to exhaustion.
> >>> So all the elements that satisfy the predicate end up at the end of the original range instead of the beginning?  Was that an arbitrary choice, or is there a reason for it?
> >> The elements satisfying the predicate are at the beginning, see e.g. the unittests. The range returned is (as always) the right-hand side, i.e. the range containing the elements that don't satisfy the predicate.
> >
> > Weird.  I'd always thought that the standard behavior was the opposite. That way partition could be passed a lessThan predicate and be used for sorting.  Though I guess you can just use a greaterThan predicate instead.
> Nono, lessThan is a binary predicate whereas partition takes a unary predicate. The spec of partition is very simple: do whatever the hell it takes to put elements e that satisfy pred(e) before elements that don't. If you follow the way std.sort uses partition, you'll see that it passes a unary predicate that compares for less than against the chosen pivot.

Okay, I think we're talking at cross-purposes :-)  It seems we both agree that partition should place the elements satisfying pred before those that do not.  And I should have been more clear about pred being a unary function.  In any case, what I'm wondering is why partition returns the range representing the elements that do not satisfy pred.  When I call partition, wouldn't I be interested in the result containing the elements that have satisfied the supplied predicate?  Or does this cause problems for the sort routine.

Sean Kelly wrote:
> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
>> Sean Kelly wrote:
>>> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
>>>> Sean Kelly wrote:
>>>>> Andrei Alexandrescu wrote:
>>>>>> Note how the left edge of result follows the left edge of r, but the
>>>>>> right edge stays put because partition() returns the right-hand-side
>>>>>> range. r shrinks from both ends to exhaustion.
>>>>> So all the elements that satisfy the predicate end up at the end of the
>>>>> original range instead of the beginning?  Was that an arbitrary choice,
>>>>> or is there a reason for it?
>>>> The elements satisfying the predicate are at the beginning, see e.g. the
>>>> unittests. The range returned is (as always) the right-hand side, i.e.
>>>> the range containing the elements that don't satisfy the predicate.
>>> Weird.  I'd always thought that the standard behavior was the opposite.
>>> That way partition could be passed a lessThan predicate and be used
>>> for sorting.  Though I guess you can just use a greaterThan predicate
>>> instead.
>> Nono, lessThan is a binary predicate whereas partition takes a unary
>> predicate. The spec of partition is very simple: do whatever the hell it
>> takes to put elements e that satisfy pred(e) before elements that don't.
>> If you follow the way std.sort uses partition, you'll see that it passes
>> a unary predicate that compares for less than against the chosen pivot.
> 
> Okay, I think we're talking at cross-purposes :-)  It seems we both agree
> that partition should place the elements satisfying pred before those that
> do not.  And I should have been more clear about pred being a unary
> function.  In any case, what I'm wondering is why partition returns the
> range representing the elements that do not satisfy pred.  When I call
> partition, wouldn't I be interested in the result containing the elements
> that have satisfied the supplied predicate?  Or does this cause problems
> for the sort routine.

Oh, now I understand. Sorry.

As a general rule, when they could return either the left or the right
subrange of a range, functions in std.algorithm return the right range.
This is because sentinel-terminated ranges cannot express the
left-hand-side range.

Partition is in fact the perfect example because it works with forward
ranges. If you want to partition a singly-linked list, you'd have to
return the right-hand sublist. There's nothing else you could possibly
return! If you wanted to return the left-hand sublist, you'd have to
return a different type of range (something like "list up to this node").

So for generality's sake, whenever you have a choice, return the
right-hand part of a range.

There is growing interest in defining additional ranges that express (at
a cost) things like "the portion of a singly-linked list starting at
node X and ending at node Y". For example, people want to do a find()
and then deal with the portion _before_ the found element. I'd love to
discuss that further, but I guess I'll have to wait for the d.next
newsgroup. :oD


Andrei

Sean Kelly wrote:
> The sort I wrote for Tango uses the same basic heuristics, thanks to
> a ticket that either you or Stewart Gordon submitted long ago.

*Ahem*, I believe that http://www.dsource.org/projects/tango/ticket/571 was one of mine ;-)

-- 
E-mail address: matti.niemenmaa+news, domain is iki (DOT) fi

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article
>
> As a general rule, when they could return either the left or the right subrange of a range, functions in std.algorithm return the right range. This is because sentinel-terminated ranges cannot express the left-hand-side range.

Gotcha.  That's unfortunate, but makes perfect sense.

> Partition is in fact the perfect example because it works with forward ranges. If you want to partition a singly-linked list, you'd have to return the right-hand sublist. There's nothing else you could possibly return! If you wanted to return the left-hand sublist, you'd have to return a different type of range (something like "list up to this node"). So for generality's sake, whenever you have a choice, return the right-hand part of a range.

It looks like there may be another bug in partition then.  The static else clause (ss == SwapStrategy.unstable) is supposed to work for forward ranges but it calls popBack().  It looks like only the semistable option is actually available to forward ranges.  Is this correct?

> There is growing interest in defining additional ranges that express (at a cost) things like "the portion of a singly-linked list starting at node X and ending at node Y". For example, people want to do a find() and then deal with the portion _before_ the found element. I'd love to discuss that further, but I guess I'll have to wait for the d.next newsgroup. :oD

Yeah, it would be great if it were possible to slice and dice a range in any manner of different ways.

== Quote from Matti Niemenmaa (see_signature@for.real.address)'s article
> Sean Kelly wrote:
> > The sort I wrote for Tango uses the same basic heuristics, thanks to a ticket that either you or Stewart Gordon submitted long ago.
> *Ahem*, I believe that http://www.dsource.org/projects/tango/ticket/571 was one of mine ;-)

Darnit, I knew if I didn't look it up I'd get it wrong.  Sorry about that :-)

fwiw, I found the code and attached it with a benchmark found in the bugreport (2966). It works only on arrays, might be buggy too. But it does sort ;)

Timings based on 1000_000 elements:

std.algorithm:  624 // modified with the fix posted in this thread
Builtin sort:  540
iterative introsort:  244