Parallel_sort: Use_parallel flag for do combine and unifie std::sort and parallel_sort
AbandonedPublic
Actions

Authored by Iliya Katueshenock (Moder) on Oct 19 2022, 10:11 PM.

Details

Reviewers: None

Summary

Parallel_sort: Use_parallel flag for do combine and unifie std::sort and parallel_sort

The multi-threaded version and the normal one are used in different cases. However, ideally they should be one action.
This patch adds an interface that is easy to use with MSpan`s and also gives real manual control over the sort type.
For now, the sort type remains the same as before. Except in places that I understand (statistics geonode, IndexMask, ...)

Diff Detail

Event Timeline

Since this patch affects a lot of files, I decided to share it with most of the people it might be related to. However, who can check it is not yet sure.

Iliya Katueshenock (Moder) added inline comments.Oct 19 2022, 10:18 PM

source/blender/blenlib/intern/index_mask.cc
170	Forgot to make it forever false. But I think, for example, you can say whether it is possible to use multithreading here, or there are hidden gems. I noticed that it was not used in many places.

I don't think it's helpful to replace std::sort by blender::parallel_sort set to false indiscriminately.

If you carefully check where it's useful and ensure there are no locks being held to avoid deadlocks, it can make sense to make it parallel. But I don't think it's good to do it for other cases which we might never want to make parallel.

There may also be cases where we want the sort to be stable or at least identical with the same input, and parallel sort might not have the same guarantees as serial sort.

There may also be cases where we want the sort to be stable or at least identical with the same input, and parallel sort might not have the same guarantees as serial sort.

Yes. Indeed, there are plenty of reasons not to choose to use multithreading:

Preservation of order in write in the comporator closure.
Preservation of the order of equal elements.
No blocking out of the comparator.
Excessive cost for a small number of elements.

This is the reason why I tried to be careful not to include it where it was not before. However, for many places this can be used and needs to be considered.
However, the main purpose of this proposal is precisely to have a way to use a non-threaded version as part of the blender implementation. Thus, do not require manual use of std where it was required before.
Also, due to the ability to make conditions for enabling multi-threaded sorting, you can not use it in some cases where the size may be too small.

This offer contains a very large number of cases. If we talk about the need for tests, then I think it would be better to check the speed of each algorithm with a new type of sorting separately with patches.

However, the main purpose of this proposal is precisely to have a way to use a non-threaded version as part of the blender implementation. Thus, do not require manual use of std where it was required before.

I don't think "manual use of std" is anything to be resolved. I find it worse to have blender::parallel_sort(false where we want the sort to be serial.

If we want to customize sort somehow I would rather have blender::sort than blender::parallel_sort(false for such cases.

Initially, I wanted to unify this to make it easy to switch. But since in the process it turned out how many requirements for sorting, in the end, most of the uses are still not multi-threaded. And since in the end it turned out that just unification was not enough, and attempts to make more diverse overloads ended up causing a lot of problems with ambiguity, I decided to stop. Sorry for distracting you. From the very beginning I thought that it would be nice and decide not to ask, but to do it right away.