Using multiple threads makes very little sense for a depth-first search, as both tree traversal approaches (depth-first, breadth-first) impose a fixed order on when the nodes are visited.

Maybe you can show us some examples of how you think the nodes should be visited if multiple threads are iterating over a tree.

Usually, the "best" algorithmic approach is to have a worker pool of trees threads and as long as there are multiple nodes at the current level of the current tree and workers available in the pool, spawn send off a worker thread for every child node until the pool is exhausted and process the remaining nodes using the current thread.

Update: Corrected some words, as per ikegamis reply

The whole point of worker pools is the avoid having to spawn off threads after processing has started.

The whole point of worker pools is the avoid having to spawn off threads after processing has started.

Yeah, so obviously by "spawn" Corion means, give the worker a job to do

This starts processing the nodes in DFS order.

use threads;
use threads::shared;

use constant NUM_WORKERS => ...;

sub process {
   my ($node) = @_;
   ...
}

{
   my $tree: shared = ...;

   my $q = Thread::Queue->new(NUM_WORKERS);

   for (1..NUM_WORKERS) {
      async {
         while (my $node = $q->dequeue()) {
            process($node);
         }
      };
   }

   my @todo = $tree;
   while (@todo) {
      my $node = pop(@todo);
      $q->enqueue($node);
      push @todo, $node->children();
   }

   $q->end();
   $_->join() for threads->list();
}
[download]

That pseudo code is entirely broken.

1. It doesn't do a depth first search.

   It processes the root node; then its children; then their children; then ....

2. It provides no possibility for "all children at the same stage will be analyse together"
3. It makes no attempt to do any locking of the shared data structure.

And if you corrected all of that, it would run 10x slower than a single threaded solution.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

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". I knew I was on the right track :)

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

What does your tree look like? (Show your code!)

Hi lets say this I have this hash:

my %document = (
    '1' => {
        '1.1' => 'xxx',
        '1.2' => {
            '1.2.1' => 'xxx',
            '1.2.2' => 'xxx'
        }
    },
    '2' => {
        '2.1' => {
            '2.1.1' => 'xxx'
        }
    }
);
[download]

and I would like to go over all of the children and then the fathers I will do it like this in perl 6 , I would like to find a why using perl5 to do the same .

sub process (%chapters) {
    await do for %chapters.kv -> $number, $content {
        start {
            note "Chapter $number started";
            &?ROUTINE.outer.($content) if $content ~~ Hash;
            sleep 1; # here the chapter itself is processed
            note "Chapter $number finished";
        }
    }
}
process(%document);
[download]

Thanks , for the help !

Or more like this?

#! perl -slw
use strict;
use threads;

sub traverse {
    my $href = shift;

    $_->join for map async{
        print "Chapter $_ started";
        my $v = $href->{ $_ };
        ref( $v ) eq 'HASH' and  traverse( $v );
        sleep 1;
        print "Chapter $_ finished";
    }, keys %$href;
}

my %document = (
    '1' => { '1.1' => 'xxx', '1.2' => { '1.2.1' => 'xxx', '1.2.2' => '
+xxx' } },
    '2' => { '2.1' => { '2.1.1' => 'xxx' } }
);

traverse( \%document );

__END__
C:\test>1169475
Chapter 1 started
Chapter 2 started
Chapter 1.1 started
Chapter 1.2 started
Chapter 2.1 started
Chapter 1.2.2 started
Chapter 1.2.1 started
Chapter 2.1.1 started
Chapter 1.1 finished
Chapter 1.2.2 finished
Chapter 1.2.1 finished
Chapter 2.1.1 finished
Chapter 1.2 finished
Chapter 2.1 finished
Chapter 1 finished
Chapter 2 finished
[download]

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

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". I knew I was on the right track :)

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

Could you post the output from the P6 code? Does it look like this?:

Chapter 1 started
Chapter 1.1 started
Chapter 1.1 finished
Chapter 1.2 started
Chapter 1.2.2 started
Chapter 1.2.2 finished
Chapter 1.2.1 started
Chapter 1.2.1 finished
Chapter 1.2 finished
Chapter 1 finished
Chapter 2 started
Chapter 2.1 started
Chapter 2.1.1 started
Chapter 2.1.1 finished
Chapter 2.1 finished
Chapter 2 finished
[download]

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

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". I knew I was on the right track :)

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