Best way to use parallel_while to find a failure in searching a linked list

[sinedie]

Hello,
I have been able to get working finding an element in a linked list with parallel_while. But I have not been able to find a good way to find if the element is NOT present. One way would be to update a global bool variable (or some referenced variable) default to false to a true (without mutex would be OK?). I am not happy with this solution. Is there a better way?

The code is given here:

[cpp]#include 

#include 
#include 
#include 

#define N 10000000

using namespace std;
using namespace tbb;

struct node {
	int data;
	node *next;
};

class par_stack {
	private:
		spin_mutex smtx;

	public:
		node *top;
		par_stack()
		{
			top = NULL;
			cout << "Created a new parallel stack!" << endl;
		}

		bool empty()
		{
			return top == NULL;
		}

		bool push( const int &x )
		{
			node *new_node = new node;

			if ( new_node != NULL ) {
				new_node->data = x;
				new_node->next = top;
				top = new_node;
				return true;
			} else {
				return false;
			}
		}

		bool print()
		{
			for ( node *tmp = top; tmp != NULL; tmp = tmp->next ) {
				cout << tmp->data << " ";
			}
			cout << endl;
		}

		bool serial_find( int const &x )
		{
			for ( node *tmp = top; tmp != NULL; tmp = tmp->next ) {
				if ( x == tmp->data ) {
					printf("%10d : foundn", x);
					return true;
				}
			}

			printf("%10d : not foundn", x);
			return false;
		}
};

class Body {
	private:
		int x;
		parallel_while &my_while;

	public:
		Body( parallel_while &w, int _x ) : my_while(w), x(_x) {}

		typedef node *argument_type;

		void operator()( node *node_x ) const
		{
			if ( node_x->data == x ) {
				cout << "Found through parallel_while : " << x << endl;
			}
		}
};

class Stream {
	private:
		node *&root;

	public:
		Stream( node *&_root ) : root(_root) {}

		bool pop_if_present( node *&next_node )
		{
			if ( root ) {
				next_node = root;
				root = root->next;
				return true;
			} else {
				return false;
			}
		}
};

void parallel_list_find( node *root, int x )
{
	parallel_while w;
	Stream s(root);
	w.run(s,Body(w,x));
}

int main()
{
	task_scheduler_init init(2);

	par_stack stk;

	for ( int i=0; i<< "Stack is empty!" << endl;
		}

		if ( ! stk.push(i) ) {
			cout << "FAILED to insert " << i << endl;
		}
	}

	cout << "Now deleting ..." << endl;

	stk.serial_find(1000);
	stk.serial_find(N+1);
	stk.serial_find(10000);

	parallel_list_find(stk.top,N-10);
	parallel_list_find(stk.top,N+10);
	parallel_list_find(stk.top,1000000);

	return 0;
}

[/cpp]

Thanks in advance for any suggestions, comments or corrections.
-S

[sinedie]

The following modification, I am not sure, requires explicit locking. Can anyone confirm if it is fine please?

[cpp]class Body { 
	private: 
		int x; 
		bool &found_x; 
		parallel_while &my_while; 
 
	public: 
		Body( parallel_while &w, int _x, bool &_found_x) : my_while(w), x(_x), found_x(_found_x) {} 
 
		typedef node *argument_type; 
 
		void operator()( node *node_x ) const 
		{ 
			if ( node_x->data == x ) { 
				cout << "Found through parallel_while : " << x << endl; 
				found_x = true; 
			} 
		} 
}; 
 
bool parallel_list_find( node *root, int x ) 
{ 
	bool found_x = false; 
	parallel_while w; 
	Stream s(root); 
	w.run(s,Body(w,x,found_x)); 
	return found_x; 
}
[/cpp]

Also probably tucking found_x into Stream also will enable to terminate once the node is found...

[RafSchietekat]

Surely you're joking, Mr. Sinedie (or Ms.)!

[sinedie]

Quoting - Raf Schietekat

Surely you're joking, Mr. Sinedie (or Ms.)!

What do I care what Black Belt thinks? :P

But seriously, I am still groping in the darkness. Not happy with the solution that I could get, looking for improvisation, if any. Somehow the solution does not feel right.
-S

[RafSchietekat]

"Somehow the solution does not feel right."
My earlier response was an invitation to review the situation and find out, for yourself, why it doesn't make sense at all. Unless that simple integer comparison is going to be replaced bya heavy computational stepthat really must be parallelised, this program will behave much like a serial version, only (much?) slower. Another solution might be to write a pointer to every N-th stack element into an array or so, using parallel_for to search different portions of the stack in parallel.

Once you have something that will perform better, for good form you should use an atomic to communicate the result (even if it doesn't really matter for a bool), and you could either poll that variable to decide whether to continue, or use TBB's cancel_group_execution()/is_cancelled().

[sinedie]

Quoting - Raf Schietekat

"Somehow the solution does not feel right."
My earlier response was an invitation to review the situation and find out, for yourself, why it doesn't make sense at all.

Thank you Raf, I did understand that you wanted me to have 'Pleasure of finding things out'. :)

I should have explained that I am getting myself familiar with using TBB, not exactly trying to solve some big problem. I wanted to use various parallel algorithms and containers and mutexes, trying to figure out at least one way of doing things right. So yes, the problem as I stated is slightly different in intention (of learning to use parallel_while) than what appears to be the stated goal of finding an element.

[sinedie]

Ok, I got this done!

[cpp]#include 

#include 
#include 

#define N 10000

using namespace std;
using namespace tbb;

struct node {
	int data;
	node *next;
};

class my_list {
	private:
		node *head;

	public:
		my_list(int max)
		{
			cout << "Created a new parallel stack!" << endl;

			head = NULL;
			for ( int i=0; idata = i;
				new_node->next = head;
				head = new_node;
			}
		}

		node * frst_node()
		{
			return head;
		}

		bool serial_find( int const &x )
		{
			for ( node *tmp = head; tmp != NULL; tmp = tmp->next ) {
				if ( x == tmp->data ) {
					printf("%10d : found (while)n", x);
					return true;
				}
			}

			printf("%10d : not found (while)n", x);
			return false;
		}

		bool parallel_list_find( node *root, int x );
};

class Body {
	private:
		int x;
		parallel_while &my_while;
		bool &found_x;

	public:
		Body( parallel_while &w, int _x, bool &_found_x ) : my_while(w), x(_x), found_x(_found_x) {}

		typedef node *argument_type;

		void operator()( node *node_x ) const
		{
			if ( (! found_x) && ( node_x->data == x ) ) {
				found_x = true;
			}
		}
};

class Stream {
	private:
		node *&root;

	public:
		Stream( node *&_root ) : root(_root) {}

		bool pop_if_present( node *&next_node )
		{
			if ( root ) {
				next_node = root;
				root = root->next;
				return true;
			} else {
				return false;
			}
		}
};

bool my_list::parallel_list_find( node *root, int x )
{
	bool found_x = false;

	parallel_while w;
	Stream s(root);
	w.run(s,Body(w,x,found_x));

	if ( found_x ) {
		printf("%10d : found (parallel_while)n", x);
	} else {
		printf("%10d : not found (parallel_while)n", x);
	}
	return found_x;
}


int main()
{
	task_scheduler_init init(2);

	my_list lst(N);

	lst.serial_find(N-10);
	lst.serial_find(1000);
	lst.serial_find(N);
	lst.serial_find(N-1);

	lst.parallel_list_find(lst.frst_node(),10);
	lst.parallel_list_find(lst.frst_node(),N);
	lst.parallel_list_find(lst.frst_node(),N-10);
	lst.parallel_list_find(lst.frst_node(),N+10);

	return 0;
}

[/cpp]

[Alexey-Kukanov]

Quoting - sinedie

Ok, I got this done!

Your soultion is correct for the problem you set.
But please make sure you understand why it is fine to deal with found_x the way you do. In particular, there are data races between accesses (i.e. reads and writes) to found_x. But in this case, the races are benign because the variable only changes from false to true, and never back. So it does not matter if some thread reads the flag as false and the next tick it is set to true to another thread; neither it matters that the first thread could re-write it (fromtrue to true) - the result will still be correct because the question is so simple.
Another example when data races may be benign is watching progress: if one thread monotonically increases some counter, and another thread watches the counter and reports its value, and it does not matter that the reported value is slightly out-of-date, then non-synchronized reads and writes of the counter are fine.
But in general case, one should have put some explicit synchronization when accessing shared data from parallel_while Body's function call operator which can be called concurrently (including for the same Body instance, which makes the instance also shared).

[sinedie]

Thanks Alexy, sorry I missed this replu of yours earlier.

I am happy that found_x was being used in an acceptable manner. But I was surprised to see that when I later used found_x for early termination (in Stream) it did not save much time. Wonder why... I know it is only of academic interest as parallel_while is depricated. But I do wish that there would sometime be an inbuilt flag to terminate spawning of newer threads in parallel_do when some condition is met ... I feel that it may not be too difficult to implement, but as I did not see the source code I could be terribly wrong. But I believe it would be a feature useful to have...

Thanks again,
-S

[Alexey-Kukanov]

Algorithm cancellation is supported in TBB 2.1 (though for some algorithms, it was only added in updates). Search for task_group_context and cancel_group_execution in the forum and the most recent documentation.