Review Request: Implemented multithreading in KFileItemModelSortAlgorithm

[David Faure]

On Saturday 08 December 2012 15:33:40 Frank Reininghaus wrote:
> Hi David,
> 
> 2012/12/8 David Faure:
> > On Thursday 25 October 2012 13:48:55 Frank Reininghaus wrote:
> >> I can't really believe that a recursive implementation is slower than the
> >> loop-based one you posted here... (provided that you make sure that the
> >> number of invocations of QtConcurrent::run() is equal to the number of
> >> CPU
> >> cores, which means that you always have to do the second recursive
> >> sort()-call without QtConcurrent, as I said).
> > 
> > Hello from the "this doesn't make sense" police.
> > The above doesn't make sense :-)
> > 
> > QtConcurrent is perfectly capable of running a runnable in the main
> > thread,
> > and does so automatically.
> 
> Yes, I know. But what I had in mind is the case of more than 2 CPU
> cores. Let's assume that we have 4 cores, and that all calls to the
> sort function are done using QtConcurrent.
> 
> The main thread (let's call it thread 1) calls the sort function twice
> using QtConcurrent. These are run in threads 2 and 3, which sort the
> first and second half of the list, respectively, and the function in
> thread 1 waits for them to complete until it can perform the merge.
> 
> Now the sort function is running in thread 2 and 3, and each of them
> uses QtConcurrent twice to invoke the sort function recursively.
> That's the idea of 4-way parallel Mergesort - let each core sort one
> quarter of the list, and then merge them.
> 
> I can see that the QtConcurrent invocations from thread 2 will run in
> a new thread 4 and the main thread 1, but I don't know if QtConcurrent
> is clever enough to see that threads 2 and 3 are blocked waiting for
> their QtConcurrent calls to complete, such that it can assign thread
> 3's sub-tasks to thread 2 and 3. You might have more insight into this
> ;-) I would try it, but unfortunately, my CPU has only 2 cores.

Ah, I see, this is indeed a bit more complex than I thought ;)
I know that future.waitForFinished() can run the future in the calling thread
if it hasn't started yet, that's what I was referring to, but it doesn't help 
here.

In the case you describe, it sounds like the threads 2 and 3 are "blocked 
waiting", but they are still inside the execution of a QRunnable, so as far as 
QThreadPool is concerned, they are not available.
So I think these threads won't be reused for doing something else.
The solution would be to call QThreadPool::releaseThread() before the blocking 
operation (future.waitForFinished()) and reserveThread() afterwards. With the 
caveats indicated in these methods, but I think that's fine.

Or more generally, to configure the global thread pool with a bigger number of 
threads than the "idealThreadCount", i.e. the number of CPUs. But the previous 
paragraph offers a solution that is a bit more refined that this :)

-- 
David Faure, faure at kde.org, http://www.davidfaure.fr
Working on KDE, in particular KDE Frameworks 5