how can i use cilk-for with STL container "set" ??

[ammouna]

Hi,

I want to use cilk_for with the STL container "set" but I received this message " no operator "-"matches these operands"

Can you help me ??

[Balaji_I_Intel]

Hello Ammouna,
Can you please give me more information? WHat compiler and version are you using? Also, is it possible for you to cut and paste the part of code that is failing?

Thanks,

Balaji V. Iyer.

[ammouna]

Hi,

I use cilk version 1.1 with visual studio 2008 on windows system

int FPtree::Prune()

{

vector vectorHeader;

int left=0;

cilk_for(set::iterator it = header.begin(); it != header.end(); ) {

if(it->getSupport() < minsup) {

set::iterator tmp = it++;

header.erase(tmp);

}

else {

left++;

it++;

}

}

return left;

}

[Balaji_I_Intel]

Hello Ammouna,
I couldn't reproduce your problem but one thing I noticed is that you did not specify an increment expression in the cilk_for that is required.

Thanks,

Balaji V. Iyer.

[ammouna]

Hi,

this code works well sequetielly , but with cilk_for didn't.

I saw that we can use vector as a reducer object by creating a copie of the header "reducer_list.h" and replacing "list" by "vector"

but I want to know if it is possible to use set as a rducer object

Thanks,

[TimP]

If this is parallelizable in your usage, you could write

int itlast = header.end();

cilk_for(set::iterator it = header.begin(); it < itlast; it++; ) {

if(it->getSupport() < minsup) {

set::iterator tmp = it;

header.erase(tmp);

}

else {

left++;

}

}

It seems that it would be necessary to be able to cast it to an int type as well.
There does appear to be an effort in Cilk+ to displace STL rather than augment it.
This illustrates how STL was designed to be unfriendly to optimization by parallelization, including threading and vectorization.

[ammouna]

In this case , header.end() is a pointer on a user_defined type "Item" and it's not possible to cast it to an int type.

It seems then that it's not possible to use the STL container set with a cilk loop ??

[jimdempseyatthecove]

If the number of erease operations is few as compared to the number of and scan time of the list, then consider making your procedure in two parts:

one (parallel) to scan the list looking for items to erease and placing the position in a thread safe container
one serial to perform the erases.

STL erase is (was?) not thread safe.

Jim Dempsey

[ammouna]

Hi,

i try this with a simple loop

cilk_for (set::iterator it = header.begin(); it!= header.end(); it++)

listItems.push_back(it->getId());

"Item" is auser_defined type.

I get the same error " no operator "-" matches these operands "

the problem was with the STL container "set" that it cannot sbdivise the number of element in the set on the number of thread

[Pablo_H_Intel]

Your loop is inherently unparallizable in its current form, for several reasons.

First the syntactic restrictions: cilk_for does not claim to work as a replacement for every legal for loop. It has a number of additional constraints. In particular, you violated three of them:
1. You don't have an increment expression (required by cilk_for, but notby for).
2. Your loop-control variable (set::iterator it) does not supportsubtraction (hence the error message).
3. You attempt to modify the loop-control variable (LCV) within the loop, which is not allowed in cilk_for.

The rule is that cilk_for wroks only for "countable" loops -- loops where the number of iterations can be dermined in advance by subtracting the starting value of the LCV from ending value of the LCV and where you can "jump" to any specific iteration by adding an integer to the starting value of the LCV. For STL iterators, this means onlyrandom-access iterators will work.std::vector, std::array, and std::deque have random-access iterators. std::set andthe otherordered associative containers have bidirectional iterators, not random-access iterators.

The second problem with paralleizing your loop is that the loop iterations are not independent of one another. The number of elements in the set changes during the loop traversal and the value of the LCV during one iteration is dependent on the execution of the previous iteration. (This is called a loop carry dependency) Thus, there is no way to execute all of the iterations in parallel. Even if you somehow managed to twist the code so that the iterations ran in parallel, you would have a fatal race condition.

- Pablo

[ammouna]

Thanks Pablo ,