Re^2: Multithreading, how to?

Building a multi-threaded program is much harder than building a single threaded one. You can't just spread on a little multi-threading to make it go faster.

Actually, often you can.

As a simplistic example, take the problem in Averaging Elements in Array of Array, and Ikegami's solution as a starting point. If you wrap the first (nested) loops of that solution up into a subroutine that returns the array of sums, then divides them to produce the averages, you have a single threaded solution that will run in time T.

Now assume you have a machine that has 4 cpus/cores. If you call that same subroutine, passing a subpartiton of the total dataset, 4 times--each time in a different thread:

#! perl -slw
use strict;
use threads;
use threads::shared;

sub sumEm{
    my $tid = threads->tid;
    my( $AoARef, $first, $n ) = @_;
    print "$tid: $first - ", $first + $n - 1;
    my @sums = ( 0 ) x 4;
    for my $i ( $first .. $first+$n-1 ) {
        $sums[ $_ ] += $AoARef->[ $i ][ $_ ] for 0 .. 3;
    }
    return @sums;
}

our $N ||= 1e6;
our $T ||= 4;

my @AoA:shared;
$#AoA = $N;

for( 0 .. $N -1 ) {
    $AoA[ $_ ] = &share([]);
    @{ $AoA[ $_ ] } = map rand( 100 ), 1 .. $T;
}

my $perThread = int $N / $T;
my @threads = map{
   threads->create( \&sumEm, \@AoA, $_* $perThread, $perThread )
} 0 .. $T-1;

my @aves = ( 0 ) x 4;
for my $thread ( @threads ) {
    my @subtotals = $thread->join;
    $aves[ $_ ] += $subtotals[ $_ ] for 0 .. 3;
}

$_ /= $N for @aves;

print "@aves";
[download]

The chances are that it will arrive at the same answer in something less than T/3 the time. (I don't have a quad cpu machine on which to prove this!).

I've seen many projects collapse from underestimating the work involved.

I'm gonna make three (totally hairy-arsed, unfounded, speculative) guesses about those projects:

They weren't in Perl using iThreads.
iThreads are imperfect, badly documented, and widely misunderstood.
But, they have some very unique properties that you will see being copied more and more as multi-core machines and threading become ubiquitous.
Indeed, I think, Artur Bergman will, belatedly, be recognised as having contributed something quite special to the world of computing. Something so special, that--when the world catches up with him--will eventually put him up there with the likes of Lovelace, Turing, Knuth and Berners-Lee.
They were in some language in which OO-techniques predominated, or were unavoidable.
It's not that OO and threads don't mix--well, they don't in Perl, but that for other reasons. It is that people will insist on trying to share objects across threads. This creates problems--which relate to the 'horizontal partitioning' and/or 'synchronisation' problems below, but compound them.
There is no problem, barring an (artificial) Perlish limitation, with passing objects between threads. The problem arises when trying to code classes such that their instances and methods can be called concurrently on multiple threads. If you avoid that scenario, about 80% (speculative) of the problems simply disappear.
The architects were writing their first multithreaded project, and made the beginner's mistake of trying to:
- Partition the problem horizontally rather than vertically.
  That is, they tried to partition the algorithm(s) across threads, rather than the data.
- And/or: tried to synchronise the threads.
  This is the threading FAQ error number one. They attempted to share data, rather than communicate information, across threads.

Threads needn't be hard. Certainly no harder, and often easier than forking. There are a raft of commonly cited, difficult to solve, problems that bug threading. And there has been much research, many papers, and a raft-squared proposed, usually complex, or (computationally and/or algorithmically) costly solutions to those problems.

But the simplest solution is invariably overlooked: avoid them!

That is, rather than trying to come up with complex and costly solutions to the well-known problems with locking, sharing and synchronisation--just don't use algorithms and techniques that require them.

iThreads are a damn good start down that road.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Comment on Re^2: Multithreading, how to? Download Code

Replies are listed 'Best First'.
Re^3: Multithreading, how to? by gwadej (Chaplain) on Dec 31, 2008 at 14:40 UTC
Much as I respect your opinion, you've kind of taken an odd approach on this one. Yes, I can agree that, if a problem is embarrassingly parallel the single-threaded solution is designed to make use of that parallelism the implementation of the solution is clean enough to see that solution changes for maintenance have not obscured the original implementation The transformation can be relatively straight-forward. Unfortunately, most of the projects I was working on are based in reality and were not ideal. It only takes violating one of the above to make the conversion quite difficult or impossible. Most of the mistakes I've seen with multi-threading (including my own early work) were from people convinced by a simple exercise like the one you suggest. Scaling that out to a larger production program does not necessarily work as well. In cases where people I've worked with have implemented multi-threaded solutions from the beginning, this wasn't as much of an issue. But, I've dealt with a lot of cases where the code had existed for some time before someone decided to just make it multi-threaded, real quick. Those usually did not go well. My main advice when talking to anyone about threading has always been to simplify the code as much as possible. Your comment about avoiding algorithms that require synchronization is good advice, when designing from scratch. When working on an existing program, shared state may have crept in without being noticed. I'm not trying to say that threads are impossible to get right, don't use them. I'm trying to say that (like security and quality) threads are not something you can just smear on some code and get benefits. Analysis and design are required to make it work. I will grant that I do not have as much experience with iThreads, but every solution that I have run across that makes threading really easy, has turned out to have major caveats. G. Wade	[reply]
Re^4: Multithreading, how to? by BrowserUk (Patriarch) on Dec 31, 2008 at 16:15 UTC
Fundamentally, I don't think that there is much to choose between our positions. I chose that example a) because it was a recent real problem; b) because I knew that it lent itself to a simple solution. In your terms, it was embarrassingly parallel. I'm trying to say that (like security and quality) threads are not something you can just smear on some code and get benefits. Analysis and design are required to make it work No argument there. The counterpoint I was trying to make, is that the explicitly-shared-only nature of iThreads simplifies a whole class of data-parallel algorithms to an extent that in many cases it is no harder--and often easier and with additional benefits--to thread programs of that type as it is to multitask them through forking. You get similar benefits of effectively separate dataspaces; but avoid requiring IPC to communicate results from the concurrent tasks back to the parent for coalescing. In this way, iThreads are different from most other forms of threading, and quite unique. That's not to say they do not have their caveats. I will grant that I do not have as much experience with iThreads, but every solution that I have run across that makes threading really easy, has turned out to have major caveats. And that's perhaps the main point I was trying to make. iThreads are different. And the caveats one needs to be aware of are different from other forms of threading. Some of them are related to the kinds of problems one encounters when using other forms of kernel threading, but they tend to manifest themselves in different ways. Some of them are exactly the same as with those others forms, but only really come into play at the perl internals level. That is, at the C-level, where threading is just native kernel threading, all the normal kernel threading caveats apply--but the Perl programmer does not need to, (and indeed, in many cases, can not), concern themself with them. If the Perl internals guys have done their job correctly, they are not an issue to the Perl programmer. If there is something the internals guys have missed, there's nothing the Perl programmer can do about it other than avoid the problem. And there are a new class of caveats that are unique to the current implementation of iThreads. Some of these arise because of exactly the reasons you mention above, the belated application of threading to a previously single threaded application: Perl. Some, arise because of the need to retain compatibility with the pre-existing designs, architecture and concepts and expose weaknesses in that pre-existing design. Experience of other threading systems frequently does not hold true when working with iThreads. Some good experiences and rules of thumb from other systems will fail dismally if you try to apply them to iThreads. Previous absolute no-nos can be used with scant disregard. The concepts of iThreads, and the current implementation of them, are sufficiently unique, that experience of other systems has to be subject to test and verification before applying them to the design and implementation of iThreaded applications. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."	[reply]