Re^2: use threads for dir tree walking really hurts

I never got around to the blog post I'd intended for the above code- some commentary:

I doubt that more CPU can fetch a physical hard drive faster than a single one.

When in doubt, benchmark! Both Mario & I timed a variety of ways to walk a directory tree, and well-written multi-threaded file walkers generally beat out the single-threaded ones. I'm not able to dig up my variants now, but if you're curious, compare what Mario posted, and the OP's working code, with File::Find on a few directory trees on the systems of your choice.

My goal was to divide up the work with as little overhead as possible. And I wanted it general enough so that all threads would be busy, regardless of working in 1 directory with a million files, or a directory tree with a million leaves and no files.

Above is the result of about eight different methods, with Mario's help- and there are still a couple more ideas I'd like to benchmark, whenever I can get back to it- I think there are still more efficient ways!

One thing benchmarking shows, is that even though multi-threaded walkers can finish faster- they can use less wallclock time- CPU time always increases: it simply takes more total cycles, when you add up the work from all CPUs. Be careful of what the Benchmark module is really telling you!

(Thanks Mario for making my code look better than the original & tweaking it too.)

Comment on Re^2: use threads for dir tree walking really hurts

Replies are listed 'Best First'.

Re^3: use threads for dir tree walking really hurts
by marioroy (Prior) on Sep 15, 2016 at 00:20 UTC

The following is an attempt for having all workers remain busy, "regardless of working in 1 directory with a million files, or a directory tree."

For extra performance, the execution time completes ~ 25% faster via cperl-5.22c.

use strict;
use warnings;

# usage: ./count_files.pl /var/tmp [ /path/to/dir2 ... ]
# usage: perl count_files.pl C:\

use Data::Dumper;
use File::Spec::Functions qw( catfile );

use MCE;
use MCE::Queue;
use MCE::Shared;

# Get directories to start with
my @start_dirs = @ARGV
   or die "Please specify one or more starting directories, stopped";

for ( @start_dirs ) {
   -d or die "No such directory: $_, stopped";
}

# Shared queue, counter, and arrays
my $shared_work = MCE::Queue->new( fast => 1, queue => \@start_dirs );
my $free_count  = MCE::Shared->scalar( 0 );

my $isDir       = MCE::Shared->array;
my $isFile      = MCE::Shared->array;
my $denied      = MCE::Shared->array;

# Walk routine
sub traverse {
   $free_count->decr;

   my ( $entry, $path );
   my @work  = ( $_ );
   my $count = 0;

   while ( defined ( $entry = shift @work ) ) {
      if ( ref $entry ) {
         $isFile->push( @{ $entry } );
      }
      else {
         opendir DH, $entry or $denied->push( $entry ), next;

         $isDir->push( $entry );
         my @files;

         for ( readdir DH ) {
            next if $_ eq '.' || $_ eq '..';

            if ( -d ( $path = catfile( $entry, $_ ) ) ) {
               ( @work < 5 )
                  ? push @work, $path
                  : $shared_work->enqueue( $path );

               next;
            }
            elsif ( -f _ ) {
               push @files, $path;

               if ( ++$count == 2000 ) {
                  $shared_work->enqueue( \@files );
                  $count = 0, @files = ();
               }
            }
         }

         $isFile->push( @files ) if @files;
      }
   }

   # Done with our work, let everyone know we're free
   if ( $free_count->incr == MCE->max_workers && !$shared_work->pendin
+g ) {
      $shared_work->enqueue( (undef) x MCE->max_workers );
   }
}

# Instantiate MCE and run.
MCE->new(
   max_workers => 6,

   user_begin => sub {
      $free_count->incr;
   },

   user_func => sub {
      traverse() while ( defined ( $_ = $shared_work->dequeue ) );
   },

)->run;

# Display counts.
printf "count dirs   : %d\n", $isDir->len;
printf "count files  : %d\n", $isFile->len;
printf "count denied : %d\n", $denied->len;

# print Dumper( $isDir->export  ), "\n";
# print Dumper( $isFile->export ), "\n";
# print Dumper( $denied->export ), "\n";
[download]

Best regards, Mario.

[reply]
[d/l]


Perl Monk, Perl Meditation
	PerlMonks