www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Parallel foreach over AliasSec?

reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
Hi,

Is it possible to parallelise the iteration over an AliasSec? 
Ordinary parallel foreach does not work. I have tried submitting 
tasks to taskPool in an ordinary foreach, but I can't because i 
cannot be read at compile time.

int one(int) {return 1;}
int two(int) {return 2;}
int three(int) {return 3;}
int four(int) {return 4;}
int five(int) {return 5;}
int six(int) {return 6;}
int seven(int) {return 7;}
int eight(int) {return 8;}

int[8] values;

template eval_all(funcs...)
{
	void eval_all(int val)
	{
		import std.parallelism;
		//foreach (i, f; parallel(funcs))	// Tries to evaluate f(void)
		foreach (i, f; funcs)	// How do I parallelise this?
			values[i] = f(val);
	}
}

void main()
{
	eval_all!(one, two, three, four, five, six, seven, eight)(42);
	foreach(i, val; values)
		assert(val == i + 1);
}

Thanks!
Feb 26 2017
parent reply ag0aep6g <anonymous example.com> writes:
On 02/27/2017 01:35 AM, Bastiaan Veelo wrote:

 template eval_all(funcs...)
 {
     void eval_all(int val)
     {
         import std.parallelism;
         //foreach (i, f; parallel(funcs))    // Tries to evaluate f(void)
         foreach (i, f; funcs)    // How do I parallelise this?
             values[i] = f(val);
     }
 }


Make a range or an array of function pointers from the AliasSeq of 
function aliases:

----
import std.meta: staticMap;
import std.range: only;

enum fptr(alias f) = &f;
enum fptrs = staticMap!(fptr, funcs);
auto r = only(fptrs);

foreach (i, f; parallel(r))
     values[i] = f(val);
----
Feb 26 2017
next sibling parent Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Monday, 27 February 2017 at 02:02:57 UTC, ag0aep6g wrote:

 Make a range or an array of function pointers from the AliasSeq 
 of function aliases:

 ----
 import std.meta: staticMap;
 import std.range: only;

 enum fptr(alias f) = &f;
 enum fptrs = staticMap!(fptr, funcs);
 auto r = only(fptrs);

 foreach (i, f; parallel(r))
     values[i] = f(val);
 ----


Wow. Thank you!
Feb 26 2017
prev sibling parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Monday, 27 February 2017 at 02:02:57 UTC, ag0aep6g wrote:

 Make a range or an array of function pointers from the AliasSeq 
 of function aliases:

 ----
 import std.meta: staticMap;
 import std.range: only;

 enum fptr(alias f) = &f;
 enum fptrs = staticMap!(fptr, funcs);
 auto r = only(fptrs);

 foreach (i, f; parallel(r))
     values[i] = f(val);
 ----


Although this answers my question perfectly, it turns out that I 
have simplified my case too much. It looks like existing 
overloads are complicating the matter. (I am actually trying to 
parallelise 
https://github.com/PhilippeSigaud/Pegged/blob/master/pegged/peg.d#L1646.)

The problem seems to be

 enum fptr(alias f) = &f;


(This is still a bit magical to me: it this a shorthand for a 
template?)

Can the following be made to work?

int one(int) {return 1;}
int two(int) {return 2;}
int three(int) {return 3;}
int four(int) {return 4;}
int five(int) {return 5;}
int six(int) {return 6;}
int seven(int) {return 7;}
int eight(int) {return 8;}

int one(string) {return 0;} // How to ignore this?

int[8] values;

template eval_all(funcs...)
{
     void eval_all(int val)
     {
         import std.meta: staticMap, Filter;
         import std.range: only;
         import std.parallelism;
         import std.traits;

         alias int function(int) iwant;
         //enum fptr(alias f) = &f;          // Error: cannot 
infer type from
                                             // overloaded 
function symbol & one
         enum fptr(alias int f(int)) = &f;   // ditto.
         enum fptrs = staticMap!(fptr, funcs);
         auto r = only(fptrs);

         foreach (i, f; parallel(r))
             values[i] = f(val);
     }
}

void main()
{
     eval_all!(one, two, three, four, five, six, seven, eight)(42);
     foreach(i, val; values)
         assert(val == i + 1);
}
Feb 27 2017
parent reply ag0aep6g <anonymous example.com> writes:
On 02/27/2017 10:52 AM, Bastiaan Veelo wrote:

 On Monday, 27 February 2017 at 02:02:57 UTC, ag0aep6g wrote:


[...]

 enum fptr(alias f) = &f;


 (This is still a bit magical to me: it this a shorthand for a template?)


Yes, it's short for this:

template fptr(alias f) { enum fptr = &f; }

"addrOf" is probably a better name for this. It's not restricted to 
functions.


 Can the following be made to work?

 int one(int) {return 1;}


[...]

 int one(string) {return 0;} // How to ignore this?

 int[8] values;

 template eval_all(funcs...)
 {
     void eval_all(int val)
     {


[...]

         //enum fptr(alias f) = &f;          // Error: cannot infer type
 from
                                             // overloaded function
 symbol & one
         enum fptr(alias int f(int)) = &f;   // ditto.


Aside: That funky, C-like syntax surprised me. I guess that's a function 
type as opposed to a function pointer type, which would be `alias int 
function(int) f`. That distinction always trips me up.


         enum fptrs = staticMap!(fptr, funcs);
         auto r = only(fptrs);

         foreach (i, f; parallel(r))
             values[i] = f(val);
     }
 }


You can generate wrapper functions that have no overloads:

----
static int wrap(alias f)(int arg) { return f(arg); }
enum addrOf(alias f) = &f;
enum fptrs = staticMap!(addrOf, staticMap!(wrap, funcs));
/* ... r and foreach as before ... */
----

This also unifies the signatures in other ways. For example, you can 
have a function that takes a `long` instead of an int.

Of course, if you passed the functions at run time, and not in a 
template parameter, the code would be much shorter:

----
void eval_all(int val, int function(int)[] funcs ...)
{
     import std.parallelism;

     foreach (i, f; parallel(funcs))
         values[i] = f(val);
}
void main()
{
     eval_all(42, &one, &two, &three, &four, &five, &six, &seven,
	&eight);
     foreach(i, val; values)
         assert(val == i + 1);
}
----

One little disadvantage of this is that the signatures have to match 
exactly. Overloads are fine, but you can't have a function with a `long` 
parameter. But that's really minor, and can be handled at the call site.

I think I'd prefer this over the template version. You have to make a 
run-time list of the functions anyway, for `parallel`, so the template 
stuff just seems to add complexity.
Feb 27 2017
parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Monday, 27 February 2017 at 11:53:09 UTC, ag0aep6g wrote:
You can generate wrapper functions that have no overloads:

 ----
 static int wrap(alias f)(int arg) { return f(arg); }
 enum addrOf(alias f) = &f;
 enum fptrs = staticMap!(addrOf, staticMap!(wrap, funcs));
 /* ... r and foreach as before ... */
 ----


I'm in awe. <Taking deep bow>


 [...] the template stuff just seems to add complexity.


Yes, but the template is one of my constraints (no pun). It needs 
to happen in there.

This compiles when I apply this to the Pegged source, but 
something else is wrong. I get a bus error some time out in 
execution. Maybe when tasks are garbage collected? Or because of 
missing synchronisation on the array that the tasks write into? 
This is a complicated situation, because the evaluation of these 
functions may themselves cause a parallel foreach on a different 
set of functions (or the same set, for recursive rules). I might 
not be able to solve this, sadly -- a parser that does parallel 
matching would have been so cool.

Anyway I am glad to have seen powers of meta programming that I 
didn't know were possible.

Bastiaan.
Feb 27 2017
parent Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Monday, 27 February 2017 at 16:04:00 UTC, Bastiaan Veelo wrote:

 I get a bus error some time out in execution.


It could be that I am running out of stack space. I am on OS X, 
and non-main threads are given a very limited stack size, they 
say [1, 2]. This foreach of mine calls into itself, and for my 
test case it nests upto 52 levels deep, which may be too much. 
Core.thread allows threads to be created with specified stack 
size, but that seems to be abstracted away in std.parallelism.

[1] http://stackoverflow.com/a/33805928/2871767
[2] 
https://groups.google.com/a/chromium.org/forum/#!topic/chromium-reviews/DMt5bDdK7s8
Feb 27 2017