std::sort-issue

[Bonita Montero]

I've got a strange sorting-problem:
I've got an array of uintptr_t's. This area is halfed so that the first
half contains a number of hashes and the second half contains a number
of pointers. Both arrays should be sorted against the hash.
But if I give std::sort the pointers to the first array the swapping on
the second array obviously doesn't happen. So how do I incorporate the
second array in the sort? I don't see a solution.

[Paavo Helde]

This is a table sort, you want to sort two columns by a common order.
For that you first sort an array of indices iota(0, N) (complexity
O(N*log(n)), then reorder both columns to the new order (2*O(n)).

[Bonita Montero]

>> I've got a strange sorting-problem:
>> I've got an array of uintptr_t's. This area is halfed so that the first
>> half contains a number of hashes and the second half contains a number
>> of pointers. Both arrays should be sorted against the hash.
>> But if I give std::sort the pointers to the first array the swapping on
>> the second array obviously doesn't happen. So how do I incorporate the
>> second array in the sort? I don't see a solution.

> This is a table sort, you want to sort two columns by a common order.

> For that you first sort an array of indices iota(0, N) ...

That would involve rearrangement afterwards.
I've found a more efficient solution; but thanks.

[Paavo Helde]

If you have found a more efficient solution to sort things than
O(N*log(N)), then please let us know. This would mean a major
breakthrough in computer science!

[Bonita Montero]

>>> This is a table sort, you want to sort two columns by a common order.
>>> For that you first sort an array of indices iota(0, N) ...

>> That would involve rearrangement afterwards.
>> I've found a more efficient solution; but thanks.

> If you have found a more efficient solution to sort things than

> O(N*log(N)), then please let us know. ...

That wasn't what I said. You can't read.

[Chris M. Thomasson]

Why are so nice?

[Bonita Montero]

>> That wasn't what I said. You can't read.

> Why are so nice?

If he wants to sell me as stupid I'll return the favor.

[Bonita Montero]

> Why are so nice?

BTW: Have you tried my code and found appropriate parameters that
prove that mutex-spinning makes sense ? This program would be anything
you need if Öö Tiib's assumptions were correct.

[Chris M. Thomasson]

I have performed many tests way back with all sorts of mutexes, almost
20-years ago. A highly contended lock for a short critical section, say
mutating two or three variables. Well, an adaptive mutex is usually
beneficial by being able to skip many calls into the OS for blocking.
Aka, trying to avoid the slow path! Any time a call into the kernel is
avoided, is a good time... ;^)

Spinning a couple of times is much better than going to the kernel to
actually block in these types of scenarios.

Btw, spinning can be used to try other things rather than just execute a
pause instruction. A try_lock can be used to try other things before
trying to lock again... ;^)

[Bonita Montero]

> I have performed many tests way back with all sorts of mutexes, almost
> 20-years ago. A highly contended lock for a short critical section, say
> mutating two or three variables. Well, an adaptive mutex is usually
> beneficial by being able to skip many calls into the OS for blocking.
> Aka, trying to avoid the slow path! Any time a call into the kernel is
> avoided, is a good time... ;^)
> Spinning a couple of times is much better than going to the kernel to
> actually block in these types of scenarios.

That's not a proof. Give me the parameters for my program to prove this!
The timing-loop is one loop per clock-cycle on any OoO-CPU of the last
20 years so that I could verify that on my computer.

[Ian Collins]

Why do you keep feeding it?

[Chris M. Thomasson]

Its strange. She keeps making me remember things from the past.

[The Real Non Homosexual]

FIGHT FIGHT

[Juha Nieminen]

The easiest solution would be, of course, if you can change that
structure to have the uintptr_t's and the pointers adjacent to
each other (ie. have them as members of a struct. Then you can
simply have a comparison operator for the uintptr_t member of
the struct and the rest will happen automatically).

If you can't change the data structure to be like that, and it must
remain as it is, then the question becomes whether you can use
additional memory to perform this sorting or not.

If you can, then it becomes equally easy: Just create a temporary
array with such structs, copy the uintptr_t values and the pointers
to these struct objects, sort it, and the copy them back to their
new places.

If you absolutely cannot afford to use any extra memory for this,
then it becomes a bit more complicated. One alternative to do it
in-place with no extra memory is to implement your own sorting
which handles the data to be sorted as pairs of values separated
by an offset. (I'm not sure if std::sort() itself could somehow
be used in this manner. Probably not.)

[Bonita Montero]

I copied a std::sort implementation and added a swap template-parameter.
This is feeded with a lambda which knows the offsets between the tables.

[Alf P. Steinbach]

On 22.05.2020 18:32, Juha Nieminen wrote:
> [snip]

> If you absolutely cannot afford to use any extra memory for this,
> then it becomes a bit more complicated. One alternative to do it
> in-place with no extra memory is to implement your own sorting
> which handles the data to be sorted as pairs of values separated
> by an offset. (I'm not sure if std::sort() itself could somehow
> be used in this manner. Probably not.)
>

I'm pretty sure `std::sort` can do it with custom iterators that when
dereferenced produce proxy objects that each represent a pair of items.

However, it's a heck of a lot of code to support an unlikely scenario,
and even though `std::sort` supports optimizations based on inlining I
somehow doubt that it will be as efficient as sorting indices.

The case has at least two sources of unpleasant odour: using effectively
parallel arrays (even though joined into one physical array), and
representing pointers with `intptr_t` values. Instead of using time on
adapting sorting to that, I would spend the time fixing the design
issues that have caused the odours. And then just use `std::sort`.

- Alf

[Mr Flibble]

Use an intrusive sort.

/Flibble

--
"Snakes didn't evolve, instead talking snakes with legs changed into snakes." - Rick C. Hodgin

“You won’t burn in hell. But be nice anyway.” – Ricky Gervais

“I see Atheists are fighting and killing each other again, over who doesn’t believe in any God the most. Oh, no..wait.. that never happens.” – Ricky Gervais

"Suppose it's all true, and you walk up to the pearly gates, and are confronted by God," Byrne 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."

[The Real Non Homosexual]

On Friday, May 22, 2020 at 2:20:55 PM UTC-7, Mr Flibble wrote:
> On 21/05/2020 14:42, Bonita Montero wrote:
> > I've got a strange sorting-problem:
> > I've got an array of uintptr_t's. This area is halfed so that the first
> > half contains a number of hashes and the second half contains a number
> > of pointers. Both arrays should be sorted against the hash.
> > But if I give std::sort the pointers to the first array the swapping on
> > the second array obviously doesn't happen. So how do I incorporate the
> > second array in the sort? I don't see a solution.
>
> Use an intrusive sort.
>

Or if all else fails, use miracle sort.

[Juha Nieminen]

Paavo Helde <ees...@osa.pri.ee> wrote:
> This is a table sort, you want to sort two columns by a common order.
> For that you first sort an array of indices iota(0, N) (complexity
> O(N*log(n)), then reorder both columns to the new order (2*O(n)).

If you can afford the extra memory needed for an array of indices,
you can probably afford the extra memory to simply copy the pairs
of values into struct objects, sort it, and assign the values back.
No need for the complexities of that index-based sorting and
rearrangement.

[Paavo Helde]

This is the obvious and boring solution which apparently did not satisfy
Bonita, so I wanted to offer something more interesting.

Anyway, in this case (two columns of small element size) you are
probably right. With more columns and larger element size the things
might change.

Anyway, Bonita's solution to modify std::sort to is still worse because
in her solution she also sorts pairs, but the pair elements are disjoint
in memory, which basically just means he has slowed down the most
expensive step of the algorithm.

[Juha Nieminen]

Paavo Helde <ees...@osa.pri.ee> wrote:
> Anyway, Bonita's solution to modify std::sort to is still worse because
> in her solution she also sorts pairs, but the pair elements are disjoint
> in memory, which basically just means he has slowed down the most
> expensive step of the algorithm.

If you are thinking about cache optimization, if I understood correctly,
the pairs of values are always the a fixed offset from each other, so they
should work with the CPU cache as well as if they were adjacent (because
every access to one element will also access its pair at the fixed
offset.)

[Pavel]

Parallel array representations are often more efficient than the
alternatives so it might turn out there is nothing to fix.

E.g. given N locations defined by x, y and h (height) coordinates and a
need to move all N locations up or down, it can be done most efficiently
when the locations are represented by 3 parallel arrays e.g. xs, ys and hs.

Also, more library and/or hardware support is often available for
parallel arrays of basic types than is for a single array of
user-defined compound objects (e.g. think vector operations).

>
> - Alf

-Pavel

[Jorgen Grahn]

On Tue, 2020-05-26, Pavel wrote:
...

> Also, more library and/or hardware support is often available for
> parallel arrays of basic types than is for a single array of
> user-defined compound objects (e.g. think vector operations).

Surely it makes no difference if you copy 100 int or 50 std::pair<int, int>?
I'd expect a quality compiler to optimize them the same way.

(Of course it's different if things like std::strings are involved.)

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Pavel]

Jorgen Grahn wrote:
> On Tue, 2020-05-26, Pavel wrote:
> ...
>> Also, more library and/or hardware support is often available for
>> parallel arrays of basic types than is for a single array of
>> user-defined compound objects (e.g. think vector operations).
>
> Surely it makes no difference if you copy 100 int or 50 std::pair<int, int>?
> I'd expect a quality compiler to optimize them the same way.
>
> (Of course it's different if things like std::strings are involved.)
>
> /Jorgen
>

Sorry, has been off the group for a while. The point was not in unrolling 2-dim
array to 1-dim array (although it is also often beneficial in some apps like
matrix ops but it's besides the point). parallel vs pairs want make a different
for copy of course. The point was in that you have, say, those 50 std::pair<int,
int> -- which are logically 2-D vectors (x,y); and you want to e.g. find an
array of 50 lengths of these vector using, say, Intel vector instructions for
that (some SSE-something), you are better off if you had them in parallel arrays
of 50 xs and 50 ys to load to, say, XMM registers and index by a single index
register, say, EDI than storing them as an array of 50 pairs (for both
load/store streaming and indexing convenience). And, if you only need xs or only
ys for some op (say, translate your vectors only up or down or only left or
right), it's even more obvious.

-Pavel

[Jorgen Grahn]

On Sat, 2020-06-06, Pavel wrote:
> Jorgen Grahn wrote:
>> On Tue, 2020-05-26, Pavel wrote:
>> ...
>>> Also, more library and/or hardware support is often available for
>>> parallel arrays of basic types than is for a single array of
>>> user-defined compound objects (e.g. think vector operations).
>>
>> Surely it makes no difference if you copy 100 int or 50 std::pair<int, int>?
>> I'd expect a quality compiler to optimize them the same way.
>>
>> (Of course it's different if things like std::strings are involved.)
>>
>> /Jorgen
>>
> Sorry, has been off the group for a while. The point was not in unrolling 2-dim
> array to 1-dim array (although it is also often beneficial in some apps like
> matrix ops but it's besides the point). parallel vs pairs want make a different
> for copy of course. The point was in that

[snip explanation]

Thanks. Looking back, it's not clear to me why I thought the context
was copying arrays. Perhaps it was, further upthread,