[Announcement] New algorithm: intrusive_sort

[Mr Flibble]

Hi.

Here I present "intrusive_sort" which works like std::sort except that you
pass it a custom "swapper" functor that is used to exchange elements as
required by the sort algorithm. The swapper is passed the iterators of
the two elements that require exchanging.

Example usage:

neolib::intrusive_sort(component_data().begin(), component_data().end(),
[this](auto lhs, auto rhs)
{
std::swap(*lhs, *rhs);
auto lhsIndex = lhs - component_data().begin();
auto rhsIndex = rhs - component_data().begin();
std::swap(index()[lhsIndex], index()[rhsIndex]);
std::swap(reverse_index()[index()[lhsIndex]],
reverse_index()[index()[rhsIndex]]);
},
[](const rigid_body& lhs, const rigid_body& rhs)
{
return lhs.mass > rhs.mass;
});

As you can see intrusive_sort allows us to sort multiple containers in
parallel in a single operation. An alternative approach using a zip
iterator and std::sort wouldn't work in this case as 'reverse_index()' is
a sparse reverse-lookup array.

intrusive_sort has the same complexity guarantees as std::sort.

https://github.com/i42output/neolib/blob/master/include/neolib/intrusive_sort.hpp

/Flibble

--
"Suppose it’s all true, and you walk up to the pearly gates, and are
confronted by God," Bryne asked on his show The Meaning of Life. "What
will Stephen Fry say to him, her, or it?"
"I’d say, bone cancer in children? What’s that about?" Fry replied.
"How dare you? How dare you create a world to which there is such misery
that is not our fault. It’s not right, it’s utterly, utterly evil."
"Why should I respect a capricious, mean-minded, stupid God who creates a
world that is so full of injustice and pain. That’s what I would say."

[Alf P. Steinbach]

On 27.08.2018 15:45, Mr Flibble wrote:
>
> Here I present "intrusive_sort" which works like std::sort except that
> you pass it a custom "swapper" functor that is used to exchange elements
> as required by the sort algorithm.  The swapper is passed the iterators
> of the two elements that require exchanging.
>
> Example usage:
>
> neolib::intrusive_sort(component_data().begin(), component_data().end(),
>     [this](auto lhs, auto rhs)
>     {
>         std::swap(*lhs, *rhs);
>         auto lhsIndex = lhs - component_data().begin();
>         auto rhsIndex = rhs - component_data().begin();
>         std::swap(index()[lhsIndex], index()[rhsIndex]);
>         std::swap(reverse_index()[index()[lhsIndex]],
> reverse_index()[index()[rhsIndex]]);
>     },
>     [](const rigid_body& lhs, const rigid_body& rhs)
>     {
>         return lhs.mass > rhs.mass;
>     });
>
> As you can see intrusive_sort allows us to sort multiple containers in
> parallel in a single operation.  An alternative approach using a zip
> iterator and std::sort wouldn't work in this case as 'reverse_index()'
> is a sparse reverse-lookup array.

Not sure I totally grok what you're doing, but it appears to be a
technique for having multiple sequences permuted in the same way as that
which yields sorted order for a primary sequence?

For that I would just make make a sequence of indices and sort that,
with a comparison function that consulted the primary sequence values.

> intrusive_sort has the same complexity guarantees as std::sort.

I remember reading about and discussing a nifty improvement to intrusive
sort a year or two or three back.

I'm unable to find it now (it doesn't seem to be mentioned in Wikipedia,
and Mr. Google is unhelpful), but I /think/ the Boost implementation of
something was updated to use the new and more shiny algorithm.

So that could be a place to look.


> https://github.com/i42output/neolib/blob/master/include/neolib/intrusive_sort.hpp

Cheers!,

- Alf

[Mr Flibble]

If you look at the swapper carefully you will see that two of the three
swaps are effectively "sorting indices" but it also needs to swap the
actual data so that data can be accessed contiguously in sorted order with
minimal CPU cache invalidation. I suggest you read my data-oriented
design article that I posted about in a separate thread.

>
>
>> intrusive_sort has the same complexity guarantees as std::sort.
>
> I remember reading about and discussing a nifty improvement to intrusive
> sort a year or two or three back.
>
> I'm unable to find it now (it doesn't seem to be mentioned in Wikipedia,
> and Mr. Google is unhelpful), but I /think/ the Boost implementation of
> something was updated to use the new and more shiny algorithm.
>
> So that could be a place to look.

I am unaware of any other implementations of what I call "intrusive sort"
other than my own implementation.

[Rick C. Hodgin]

On 08/29/2018 02:49 PM, Mr Flibble wrote:
> I am unaware of any other implementations of what I call "intrusive
> sort" other than my own implementation.

The concept is not original, Leigh. Here's an idea for a CAlive
syntax example I created in Feb 2016:


http://www.libsf.org:8990/projects/LIB/repos/libsf/browse/ideas/qsort.txt

The idea is for a qsort() algorithm with callbacks to handle each
aspect of its operation through custom code that's supplied in the
initial call. It allows for jagged data to be sorted without first
creating a sanitary list of pointers to it, etc.

Many people have had such ideas, Leigh. They've all been good.

--
Rick C. Hodgin

[Mr Flibble]

And Satan invented fossils yes?

[Rick C. Hodgin]

On 08/29/2018 03:17 PM, Mr Flibble wrote:
> And Satan invented fossils yes?

It is the truth which makes us free, Leigh. So long as you
refuse to give the truth any consideration ... you self-condemn
your own soul to Hell.

--
Rick C. Hodgin

[Alf P. Steinbach]

On 29.08.2018 20:49, Mr Flibble wrote:
> On 29/08/2018 05:57, Alf P. Steinbach wrote:
>> On 27.08.2018 15:45, Mr Flibble wrote:
>>

>> [snip]

>>> intrusive_sort has the same complexity guarantees as std::sort.
>>
>> I remember reading about and discussing a nifty improvement to
>> intrusive sort a year or two or three back.
>>
>> I'm unable to find it now (it doesn't seem to be mentioned in
>> Wikipedia, and Mr. Google is unhelpful), but I /think/ the Boost
>> implementation of something was updated to use the new and more shiny
>> algorithm.
>>
>> So that could be a place to look.
>
> I am unaware of any other implementations of what I call "intrusive
> sort" other than my own implementation.

Sorry, the terms are so similar that my fingers typed the wrong one. :(

https://en.wikipedia.org/wiki/Introsort

Some variant of this is presumably how `std::sort` is implemented in
~all implementations, since it needs to have guaranteed worst case O(n
log n), and also, at the same time, needs to be quick about it. :)

I'm just unable to find info on the modern improvement, if any, that I
seem to remember. But then my memory isn't always to be trusted
nowadays. E.g. I distinctly remember discussing the details of a 1990's
movie with a girl I knew in the middle 1980's and haven't seen since.

We all (d)evolve...


Cheers!,

- Alf

[Chris M. Thomasson]

On 8/29/2018 12:17 PM, Mr Flibble wrote:
> On 29/08/2018 20:02, Rick C. Hodgin wrote:
>> On 08/29/2018 02:49 PM, Mr Flibble wrote:
>>> I am unaware of any other implementations of what I call "intrusive
>>> sort" other than my own implementation.
>>
>> The concept is not original, Leigh.  Here's an idea for a CAlive
>> syntax example I created in Feb 2016:
>>
>>
>> http://www.libsf.org:8990/projects/LIB/repos/libsf/browse/ideas/qsort.txt
>>
>> The idea is for a qsort() algorithm with callbacks to handle each
>> aspect of its operation through custom code that's supplied in the
>> initial call.  It allows for jagged data to be sorted without first
>> creating a sanitary list of pointers to it, etc.
>>
>> Many people have had such ideas, Leigh.  They've all been good.
>
> And Satan invented fossils yes?

Living beings created their own unique fossils?

[Mr Flibble]

On 30/08/2018 06:46, Alf P. Steinbach wrote:
> On 29.08.2018 20:49, Mr Flibble wrote:
>> On 29/08/2018 05:57, Alf P. Steinbach wrote:
>>> On 27.08.2018 15:45, Mr Flibble wrote:
>>>
>>> [snip]
>>>> intrusive_sort has the same complexity guarantees as std::sort.
>>>
>>> I remember reading about and discussing a nifty improvement to
>>> intrusive sort a year or two or three back.
>>>
>>> I'm unable to find it now (it doesn't seem to be mentioned in
>>> Wikipedia, and Mr. Google is unhelpful), but I /think/ the Boost
>>> implementation of something was updated to use the new and more shiny
>>> algorithm.
>>>
>>> So that could be a place to look.
>>
>> I am unaware of any other implementations of what I call "intrusive
>> sort" other than my own implementation.
>
> Sorry, the terms are so similar that my fingers typed the wrong one. :(
>
> https://en.wikipedia.org/wiki/Introsort
>
> Some variant of this is presumably how `std::sort` is implemented in ~all
> implementations, since it needs to have guaranteed worst case O(n log n),
> and also, at the same time, needs to be quick about it. :)

Yes my intrusive_sort uses introsort so it has same complexity guarantees
as std::sort.

[Öö Tiib]

On Monday, 27 August 2018 16:46:12 UTC+3, Mr Flibble wrote:
>
> intrusive_sort has the same complexity guarantees as std::sort.
>
> https://github.com/i42output/neolib/blob/master/include/neolib/intrusive_sort.hpp
>

Nice. Doing that with std::sort is tricky because it does move
the elements instead of swapping those.