Search in binary search tree correct out traversal but body does not function

[sinedie]

Hello,
I have written a small program to use parallel_while to traverse a tree. I made a binary search tree and the program is supposed to print values at all the nodes. But I find that the output is given correctly (prints "Found" if the number is found) but the node is not processed in the body object. Can someone point me to the bug please?

[cpp]#include 
#include 
#include 

#include 
#include 

#define N 100

using namespace std;
using namespace tbb;

struct node {
	int val;
	struct node *left;
	struct node *right;
};

class p_bst {
	private:
		node *head;

	public:
		p_bst(int max);

		bool parallel_find( int x );

};

p_bst::p_bst(int max)
{
	cout << "Creating a new BST!" << endl;
	vector v;
	head = NULL;

	for (int i=0; i<< "head " << v[0] << endl;
	
	head = new node;
	head->val = v[0];
	head->left = NULL;
	head->right = NULL;

	for (int i=1; i<< "Inserting " << v << endl;

		tmp_node = head;
		while ( tmp_node != NULL ) {
			if ( tmp_node->val > v ) {
				if ( tmp_node->left ) {
					//cout << "   " << tmp_node->val << " left" << endl;
					tmp_node = tmp_node->left;
				} else {
					//cout << "   " << tmp_node->val << " left" << endl;
					node *new_node = new node;
					new_node->val = v;
					new_node->left = NULL;
					new_node->right = NULL;
					tmp_node->left = new_node;
					tmp_node = NULL;
				}
			} else {
				if ( tmp_node->right ) {
					//cout << "   " << tmp_node->val << " right" << endl;
					tmp_node = tmp_node->right;
				} else {
					//cout << "   " << tmp_node->val << " right" << endl;
					node *new_node = new node;
					new_node->val = v;
					new_node->left = NULL;
					new_node->right = NULL;
					tmp_node->right = new_node;
					tmp_node = NULL;
				}
			}
		}
	}
}

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 ) {
				cout << "  @" << node_x->val << endl;
			}
		}
};

class Stream {
	private:
		node *&root;
		int const &x;

	public:
		Stream( node *&_root, int const _x ) : root(_root), x( _x )  {}

		bool pop_if_present( node *&next_node )
		{
			if ( root == NULL ) {
				return false;
			}
			
			//cout << "   " << x << " " << root->val << endl;

			if ( root->val == x ) {
				cout << "Found " << x << endl;
				return false;
			}
			
			if ( root->val < x ) {
				root = root->right;
			} else {
				root = root->left;
			}

			return true;
		}
};

bool p_bst::parallel_find( int x )
{
	node *root = head;

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

	return true;
}

int main()
{
	task_scheduler_init init(-1);

	p_bst lst(N);

	lst.parallel_find(184);
	lst.parallel_find(57);
	lst.parallel_find(10);

	return 0;
}

[/cpp]

TIA,
-S

[robert-reed]

Quoting - sinedie

Hello,
I have written a small program to use parallel_while to traverse a tree. I made a binary search tree and the program is supposed to print values at all the nodes. But I find that the output is given correctly (prints "Found" if the number is found) but the node is not processed in the body object. Can someone point me to the bug please?

[snip]

I noticed a few things. First of all, parallel_while is a deprecated feature of TBB, still present but discouraged. Next, there's not much parallel code present in this example: all the work is done by the stream implementation, which does a pretty standard serial search through a binary tree but fails to set next_node when it finds a candidate, which is probably why you're not seeing the result you expect. Moreover, the binary tree implementation is very poor and can lead to very unbalanced binary trees, being totally dependent on the sorted order of the data presented to the constructor.

[sinedie]

Quoting - Robert Reed (Intel)

I noticed a few things. First of all, parallel_while is a deprecated feature of TBB, still present but discouraged. Next, there's not much parallel code present in this example: all the work is done by the stream implementation, which does a pretty standard serial search through a binary tree but fails to set next_node when it finds a candidate, which is probably why you're not seeing the result you expect. Moreover, the binary tree implementation is very poor and can lead to very unbalanced binary trees, being totally dependent on the sorted order of the data presented to the constructor.

Thanks Robert. I did not realize from the book I was reading that parallel_while is depreciated. As of binary search tree..., it was just a toy program to understand the syntax before I start using TBB for various projects. I shall try my hands with parallel_do now.
Thanks again,
-S

[robert-reed]

Quoting - sinedie

Thanks Robert. I did not realize from the book I was reading that parallel_while is depreciated. As of binary search tree..., it was just a toy program to understand the syntax before I start using TBB for various projects. I shall try my hands with parallel_do now.
Thanks again,
-S

If you've found parallel_do, which functionally replaces parallel_while in TBB, then you probably also saw the cautions in the manual:

TIP:

The parallelism in parallel_do is not scalable if all of the items come from an input stream that does not have random access. To achieve scaling, do one of the following:

Use random access iterators to specify the input stream.

Design your algorithm such that the body often adds more than one piece of work.

Use parallel_for instead.

To achieve speedup, the grainsize of B::operator() needs to be on the order of at least ~10,000 instructions. Otherwise, the internal overheads of parallel_do swamp the useful work.

If your mission now is to construct a similar tree example substituting one TBB construct for another, you might be able to get working code, but it's not likely that it will scale well on multiple threads. The best you might be able to hope for would be to construct an input iterator that, say, follows the right child for the sequence but whenever there's a right child feeds that to the parallel_do_feeder::add function. There probably still won't be enough work there to scale very well. You need some kind of load to weight down the node processing.