[X10-core] general implementation of map/reduce

[Josh M. <jos...@an...>]

Hi all,

with the separation of Rail from the simple x10.array and the 
fully-featured x10.regionarray classes, the map and reduce methods have 
been lost from Rail.  The map and reduce patterns (and to a lesser 
extent, scan) are so fundamental that I think this might be an 
appropriate time to define a standard approach for applying these 
patterns across X10 data structures.

The existing approach seems to be to just implement methods for 
map/reduce as needed on container classes like Array and DistArray. This 
may lead to undesirable repetition if it is extended to other types like 
Rail, ArrayList and other Collections.  Would it be appropriate to 
create a new interface Indexable that defines the indices() method and 
get and set operators?  This could be used to implement a general map 
operation as follows:

     public class x10.lang.Map {
         public @Inline static def map[T](op:(T)=>T, a:Indexable[T]) {
             finish for (p in a.indices()) async {
                 a(p) = op(a(p));
             }
         }
     }

A related question: should map/reduce be parallel or sequential by 
default?  The current implementations on the simple array classes are 
all sequential, but there are TODO comments on each suggesting they 
should be parallel.  The new work stealing implementation should 
substantially reduce the overhead of a parallel loop, which may swing 
the balance in favour of parallel map/reduce.

There are obviously multiple different ways of dividing map/reduce for 
parallel execution; it seems to me that the best general-purpose 
implementation would be recursive bisection, possibly with some minimum 
grain size; but other implementations may work better for particular 
problems.

Do you think it is possible to come up with a standard approach in time 
for version 2.4?

Cheers,

Josh

-- 
------------------------------------------
Josh Milthorpe

Postdoctoral Fellow, Research School of Computer Science
Australian National University, Building 108
Canberra, ACT 0200
Australia
Phone:  + 61 (0)2 61254478
Mobile: + 61 (0)407 940743
E-mail: jos...@an...
Web:    http://cs.anu.edu.au/~Josh.Milthorpe/