But if functional programming is what you're looking for, MapReduce isn't exactly it. It's more of a large-scale job control framework for computations that are what a functional program would be more likely to be designed upon (that is, pure functions). If you want to experience the kinds of tools that are associated with more day-to-day stuff, like using (probably lazy) lists, abstract datatypes, pattern matching, type inference, curried functions, composition, folds etc., this isn't where you'll find them.

Two CPAN modules for Perl 5 that bring some of the goodies (incidentally both at version 0.03 right now) are fp and Language::Functional.

I originally started with P::FM as well, because it did look simple. But this uses forks, not threads, and so couldn't be applied to my problem.

(Specifically, concatenating a string in a distributed way, where order wasn't important: using parallel processing to concatenate a string, where order of concatenation doesn't matter.)

It didn't work, in a way that violated my expectations, because parallelization, like I said, is painful. In this case I would have needed to use threads.

Perhaps there could be a ForkedMapReduce as well as a ThreadedMapReduce. The important thing to me is a reliable abstraction that Does What I Mean.

The important thing to me is a reliable abstraction that Does What I Mean.

What's wrong with this?

Okay, I have here stub code for a parallel "threadedreduce", using what I think is pretty much functional style programming.

My goal is along the same lines as my post yesterday concerning concating letters (mentioned in op), but more honed. Basically, I have a slow function for demo purposes, and I want to speed it up by using code executed in parallel; but in such a way that I can abstract the ugly bigs (locks, threads, etcetera) into a module that I maintain separately.

So, here, my function in in the coderef:  $slow_matches_b It's slow because it sleeps for one second. And what it does it, it returns true if the input matches the letter b.

I then have sub slowgrep, which should do the same thing that grep does, but in a more explicit way. slowgrep is built on sub reduce. This function is similar to the reduce you get in List::Util, but like Frank Sinatra, here, I did it my way. Could be it's not quite the same. I actually modeled it after the javascript reduce example code in the joelonsoftware essay Can Your Programming Language Do This?.

Reduce is one of the basic building blocks of functional programming, and half of the google's celebrated MapReduce. This particular implementation of Reduce executes serially.

Then I have the sub fastgrep, which should also do the same thing that grep does, but be faster because it uses some form of parallelization. Every line of this function is the same as slowgrep, except it is based on threadedreduce instead of reduce.

threadedreduce should do the same thing as reduce except... it doesn't. As the tests show. In fact, it is just a stub, and actually it has forks not threads, but you get the idea. I think this function could be implemented either with forks, or with threads, or with POE, or whatever your favorite technique for cranking up parallelization in your environment. The point is that it lets programmers process lists in a parallel way while hiding away the complexity of the parallelized code.

This is where I am hoping the monastery can step in and help me out. Can someone out there make threadedreduce work? threadedreduce could then be used to build threadedgrep, threadedUserAgent (same as UserAgent::Parallel, but you can WWW::Mechanize as the UA instead of the UA inherited from LWP::UserAgent)... or... well... lots of things. And in a way that's beautiful, functional, and maintainable.

 
$ ./test_reduce.pl
not ok 1 - parallel-y executing code works
#   Failed test 'parallel-y executing code works'
#   in ./test_reduce.pl at line 15.
fast matches: $VAR1 = [];
ok 2 - serially executing code works
slow matches: $VAR1 = [
          'blee',
          'blah',
          'bloo'
        ];
1..2
# Looks like you failed 1 test of 2.
$ cat test_reduce.pl
#!/usr/bin/perl
use strict;
use warnings;
use Test::More qw( no_plan );
use Data::Dumper;
use Parallel::ForkManager;

my $slow_matches_b = sub { sleep 1; return 1 if $_[0] =~ /b/; };
my $test_strings = [ ('blee','blah','bloo', 'qoo', 'fwee' ) ];

my $fast_matches = fastgrep( $slow_matches_b, $test_strings );
ok( @$fast_matches, "parallel-y executing code works"  );
print "fast matches: " . Dumper($fast_matches);
# should dump out blee, blah bloo, but not fwee or qoo

my $slow_matches = slowgrep( $slow_matches_b, $test_strings );
ok( @$slow_matches, "serially executing code works"  );
print "slow matches: " . Dumper($slow_matches);

sub fastgrep {
  my $test_function = shift;
  my $array = shift;

  my $grep_builder = sub {
    my $matches = shift;
    my $test_el = shift;
    push @$matches, $test_el if $test_function->($test_el);
    return $matches;
  };
  return threadedreduce ( $grep_builder, $array, [])
}

sub slowgrep {
  my $test_function = shift;
  my $array = shift;

  my $grep_builder = sub {
    my $matches = shift;
    my $test_el = shift;
    push @$matches, $test_el if $test_function->($test_el);
    return $matches;
  };
  return reduce( $grep_builder, $array, [])
}


# just a stub, hoping someone can help me with the threading
sub threadedreduce {
  my $function = shift;
  my $array = shift;
  my $init = shift;

  my $pm=new Parallel::ForkManager(10);
  my $result = $init;
  for my $el ( @$array) {
    $pm->start and next;
    $result = $function->( $result, $el);
    $pm->finish;
  }
  $pm->wait_all_children;
  return $result;
}

sub reduce {
  my $function = shift;
  my $array = shift;
  my $init = shift;

  my $result = $init;
  for my $el ( @$array) {
    $result = $function->( $result, $el)
  }
  return $result;
}
[download]

UPDATE: I'm actually thinking the promising avenue of approach may to use Parallel::Queue, along the lines diotalevi suggested yesterday in Re: using parallel processing to concatenate a string, where order of concatenation doesn't matter.

Side note: there's another attempt at something like MapReduce in Perl called DMap, written by Brad Fitzpatrick and built on Gearman. As far as I know, not available in packaged form - some links;

http://code.sixapart.com/svn/gearman/trunk/doc/overview.txt

http://brad.livejournal.com/2106943.html

http://brad.livejournal.com/2210265.html

That's distributed again though although I guess it would be easy to run the whole lot on a single system.

Unless something has really changed within Perl recently, ithreads won't do what you want here, as they are not OS threads. You'll still have one process on one processor.

So maybe I would need to use forks, and store part of the computation on the hard drive, in some temp directory?

That's ok by me, as long as the abstraction is hidden away and reduceForked( $functionBuilder, $arrayref, $initvalue ) always does what I mean.

I want this. Bad :)

Now, I don't have 80,000 machines.

But I do have a single machine that can run multiple processes.

But I hate writing code that does this, because threads are painful, forks are painful, you get race conditions, you have to use locks...

Aside from the pains you cite, there is also the inescapable truth that if you try to do more with just the one machine, you will hit a limit -- a plateau -- beyond which further "parallelizing" will hurt rather than help.

Whether your task is mainly i/o bound, or memory bound, or cpu bound, adding more instances of the task will, at some point, exacerbate the load on the given resource to the point where improvements are not only impossible, but negated.

Maybe running three instances in parallel will be faster, overall, than running two-at-once then one, but maybe running four at once will be slower than running two parallelized pairs in sequence. YMMV.

Yes, no doubt this is all true.

But my point is that by hiding my parallelization code in a threadedreduce, and putting the "meat" of my program in a "function builder" such as grepbuilder / mapbuilder / urlgrabbuilder -- that relies on threadedreduce or nonthreadedreduce -- I make experimentation easier, and maintenance easier.

I also write code that is easily portable to running on more than one thread, or more than machine. Just change one line, and see if you get an improvement. If there's no improvement, or things actually get worse, switch back to nonthreadreduce / nondistributedreduce.

These days, feels to me like I'm always second guessing myself with my thread code, rather than concentrating on the meat of my program.

Ira, I'm real interested by that module you recently posted.

I am having to write a lot of code that works in a parallel way, and I hate it. What is most appealing to me about MapReduce is not so much that it allows you to split things up on a cluster (though that's great), but that the code itself is so clean. No locks, no guards, no name-your-poison. Just Reader/Map/Reduce. Simple. Clean. All the dirt is hidden away, where your rocket scientists can optimize things in your custom MapReduce code to their hearts content.

I posted about this at

Could there be ThreadedMapReduce (and/or ForkedMapReduce) instead of DistributedMapReduce?

What I'm wondering is if you could have this goodness working even when you just have one computer, by using threads/forks. I'm thinking ThreadedMapReduce / ForkedMapReduce. Maybe even all inheriting from your original module in a sane way.

This would do the same thing that ParallelForkManager, and Thread::Queue, and countless other modules, but with a much cleaner functional interface.

I'm thinking along the same lines as Joel in "Can Your Programming Language Do This?":

http://www.joelonsoftware.com/items/2006/08/01.html

Well, can perl do this?

What do you think? :)

Best, thomas.

******************************************************
******************************************************

Ira Woodhead responded:

Actually, yes! The version I'm currently getting ready to post has two config options "maps" and "reduces" which allow you to set the number of map task and reduce task processes per machine. To use it on a single machine you simply have a single-machine cluster. If you want threads, well, sorry but I'm not comfortable using perl threads, having experienced some pitfalls with them. Not to mention they require a recompile, and I really want to keep this simple to deploy. The relatively more expensive full forks are the way I'm going, at least for now.

I'm glad there is some interest in this. I was quite surprised to find no effort underway besides Hadoop to implement this model. And yes, I did see JSpolsky's post about mapreduce, it's a nice way of explaining it.

Currently I'm trying to figure out if there's a way to make the deployment even easier, and, more significantly, to somehow allow mapreduce operations to take place inside of a program, rather than just being a separate utility, so that multiple such operations can be used as part of a larger system. Right now it's one invocation of a command line "mr" program per operation, but wouldn't it be nice as more of a language feature?

Anyway, I'll be uploading the next version soon. Let me know if you have any comments or ideas.

Cheers!

******************************************************
******************************************************

I responded:

Ira, I think it's great what you're doing. The feature to run a controlled "cluster" on a single computer could potentially pay dividends for a lot of people, both in functionality and maintainability. The way I see it, it's basically threading/forking with the dirty bits hidden away, in a way that will scale.

My thoughts / idea, and links to the evolution thereof, are well summarized in a perlmonks post I just made

Using functional programming to reduce the pain of parallel-execution programming (with threads, forks, or name your poison)

If I could plug MapReduce into the "hashmap_parallel" function builder in the Map.pm code there (buried in a readmore), I would have my pony.

******************************************************
******************************************************

To sum it up, there should be a way of doing what I want pretty soon, using the option for a single machine cluster described by Ira above.

Kudos to Ira for putting this together, and keeping the improvements coming.