Prev: Efficient sorting
Next: Nested variable declarations using the same name
From: restor on 22 Apr 2008 06:22
Hi,
This may not be the best place to post this question, but I didn't
know who to ask, so sorry if this is a bit off topic.

I have the following algorithm, that I want to execute in a separate
thread, so that I do not block the main one:

void findBest()
{
for ( Element elem : collection ) // foreach
{
Score score = ComputeScoreIn25minutes( elem );
if ( score > bestScore )
{
bestScore = score;
bestElem = elem;
// iterruption point here
}
}
}

I could use a future<> abstraction as described in N2094, N2185,
N2276, but I do not really have to run my algorithm to an end. I would
like to be able to obtain the best element found so far rather than
wait till the algorithm computes score for the last element in the
collection.
Thus, I would imagine starting my algorithm similarly to how a future
is created:

QFuture<elem> qfuture = run( ... );

Now, calling qfuture's default operation would interrupt the thread
rather than wait until the thread finishes.
I wonder if anyone here have ever thought of something similar. If it
is already implemented. If it has a name. Or if it is possible to
implement such an abstraction, that would not be too intrusive to
function 'findBest' from my example.

I would appreciate any help,
&rzej

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Tony Delroy on 22 Apr 2008 13:27
On Apr 23, 6:22 am, restor <akrze...(a)interia.pl> wrote:
> I have the following algorithm, that I want to execute in a separate
> thread, so that I do not block the main one:
>
> void findBest()
> {
> for ( Element elem : collection ) // foreach
> {
> Score score = ComputeScoreIn25minutes( elem );
> if ( score > bestScore )
> {
> bestScore = score;
> bestElem = elem;
> // iterruption point here
> }
> }
>
> }
>
> [ snip ]
> I would
> like to be able to obtain the best element found so far rather than
> wait till the algorithm computes score for the last element in the
> collection.

Use a "mutex" (I think in Windows they're called Critical
Sections...?) to arbitrate access to bestScore and bestElem:
serialising reads from your main thread and writes from the
calculation thread. A quick 'net search should turn up the details
you need.

Tony

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Lance Diduck on 23 Apr 2008 04:27
{ Please format your article to fit in 70 columns or so, definitely
less than 80 columns. Lines broken at unwanted positions make it
very hard to read or copy-and-paste. -mod }


On Apr 22, 5:22 pm, restor <akrze...(a)interia.pl> wrote:
> Hi,
> I would appreciate any help,

typedef std::pair<Score, Elem> BestScore;

BestScore Current;
boost::mutex Currentmutex;

BestScore getCurrent(){//called by any thread
boost::mutex::scoped_lock l(Currentmutex);
BestScore ret=Current;
//do not return Current directly, since many compiler will unlock
the mutex becore the copy is made
return ret;

}
void setCurrent(BestScore const& v){//only called by the thread
calculating scores
boost::mutex::scoped_lock l(Currentmutex);
Current =v;
}
void foo(){
Score score = ComputeScoreIn25minutes( elem );
if ( score > Current.first)//since there is only one thread
//doing the modifications (namely this one), unprotected
access is fine here
{
setCurrent(BestScore(score ,elem));

}
}

That is really all there is to it. If there were more than one thread
modifying Current, then it would look like
void foo2(){
Score score = ComputeScoreIn25minutes( elem );
{
boost::mutex::scoped_lock l(Currentmutex);
if ( score > Current.first)
//doing the modifications (namely this one), unprotected
access is fine here
{
Current=BestScore(score ,elem);

}
}
}

Doing this in a lock free style is far easier to componentize, but C++
has poor library support for it at the moment. But basically if it did
it would look like

linear_mutual_ptr<BestScore> Current2;
void foo3(){
Score score = ComputeScoreIn25minutes( elem );
do{
linear_ptr<BestScore> current=Current2;
if ( score > old->first)
if(Current2.compare_and_swap(current,
linear_ptr<BestScore>(new
BestScore(score ,elem)))
break;
else break;
}while(true);
//compare and swap returns true if the value in Current2 is still
the same as current, and then assigns
//Current2 to the new value (using special assembler instructions)
//else it is unchanged and returns false
//if only one thread modifies Current2 then compare_and_swap
always returns true
}
This is the same thing, except that now all threads have unblocked
access to the current best score, and can modify it at will. The
algorithm is independent of how many threads are used, can be called
recursivley, does not suffer from priority inversion, deadlock and
other bad things. mutex placement is not an issue, since it doesn't
exist. NB: lock-free does not always mean "faster" many times it is,
many times it is not.


Lance


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 | 
Pages: 1
Prev: Efficient sorting
Next: Nested variable declarations using the same name