macOS Grand Central Dispatch to paralelize a c++ for loop

[estin]

Hello everyone !

I'm trying to paralelize a for loop inside a instance method of a c++ class. The loop code is like this:

for (int k=0;k<numberOfNodes2;k++)
{
	MeshNode *testNodej = testEntity2->nodeAt(k);
	double testPotential = getPotentialContributionOnNode(testNodei, testNodej);
	A(j+m,k+l)= testPotential;
}

MeshNode is a class that stores spatial coordinates, and have a variety of geometrical functions. Inside the loop the testNodej pointer acts only as a reference to an existing node that won't be modified by the getPotentialContribution function. This loop is nested inside other loops, but this one is the only one suitable for parallelization. the A variable is a matrix declared as __block Matrix<double> A, to get read-write access inside the block function. I'm trying to paralelize the above code as :

dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
dispatch_apply(numberOfNodes2, queue, ^(size_t k)
{
	MeshNode *testNodej = testEntity2->nodeAt(k);
	double testPotential = getPotentialContributionOnNode(testNodei, testNodej);
	A(j+m,k+l)= testPotential;
});

however it gives me the following errors:

error: 'MeshNode* Bem::testNodej' is not a static member of 'class Bem'
error: 'double Bem::testPotential' is not a static member of 'class Bem'

The only useful information about this error I've found is
http://lists.apple.com/archives/perfoptimization-dev/2009/Sep/msg00043.html

however the suggested workarround doesn't work for me as I think I have to declare the block inside the function.

Any suggestions? thanks in advance !

 

[ncl]

When I met that problem, I solved it by calling the block from a C function. That C function received pointers/references to the variables used in the block.
For instance, in your case, I would try something like:

void cpp_block_bug_workaround(T *testEntity2,
		MeshNode *testNodei,
		Matrix<double> &A,
		int numberOfNodes2,
		int j, int m, int l)
{
	dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
	dispatch_apply(numberOfNodes2, queue, ^(size_t k) {
		MeshNode *testNodej = testEntity2->nodeAt(k);
		double testPotential = getPotentialContributionOnNode(testNodei, testNodej);
		A(j+m,k+l) = testPotential;
	});
}

And then, where you normally would have put the block:

cpp_block_bug_workaround(testEntity2, testNodei, A, numberOfNodes2, j, m, l);

Not really elegant but seems to work...

 

[qtx43]

I'm not familiar with GCD (still on the big list of things to learn), but note that ncl's solution is almost exactly the same as making a static member function (as the error message suggested). The point is: you must don't have 'this' so you have to pass it sufficient info in the arguments.

 

[ncl]

I'm not familiar with GCD (still on the big list of things to learn), but note that ncl's solution is almost exactly the same as making a static member function (as the error message suggested). The point is: you must don't have 'this' so you have to pass it sufficient info in the arguments.

Actually, a static member function won't work either. Notice that the problem isn't with the class attributes but with the local variables of the block (where 'this' shouldn't play any role). The problem is with scoping. If I write:

typedef void (^block_ptr)();
struct A {
	void m() { block_ptr b = ^{ int i = 1; }; }
};

I get, as the OP, the error that ‘int A::i’ is not a static member of ‘struct A’. If I write:

struct A {
	static void s() { block_ptr b = ^{ int i = 1; }; }
};

I get the same error. The error even appears with friend functions defined inside the class. This:

struct A {
	friend void f(A *a) { block_ptr b = ^{ int i = 1; }; }
};

gives the same error, whereas :

struct A {
	friend void f(A *a);
};
void f(A *a) { block_ptr b = ^{ int i = 1; }

compiles.

That's why I ended up using a C function.

 

[qtx43]

That's interesting. I'm not sure you could expect 'friend' would make any difference, as that only changes access, whereas 'static' member functions actually change the calling convention. I wonder if it would work if you made it: static int i = 1; maybe it would compile, but the scope consequences would be what? Bleh, I'll get around to learning this eventually. GCD blocks actually look very useful, unlike some of the directions C++ is headed in.

 

[Sander]

The article on the Apple site suggests using explicit scope :i). Have you tried this with your example?

It looks like there's still something broken in the G++ implementation in that it doesn't recognize that new variables are simple locals to the block, and instead thinks it needs to look them up in the containing class.

 

[ncl]

That's interesting. I'm not sure you could expect 'friend' would make any difference, as that only changes access, whereas 'static' member functions actually change the calling convention.

Don't friend functions and static members use the same calling conventions ? In both cases, they're 'simple' functions (without a hidden 'this'). The only difference is that a static member function is in the scope of a class.

I wonder if it would work if you made it: static int i = 1; maybe it would compile, but the scope consequences would be what?

Putting the i static gives the same error, because, again, the compiler thinks it needs to look up the variable in the class, instead of recognizing it as local variable.

Bleh, I'll get around to learning this eventually. GCD blocks actually look very useful, unlike some of the directions C++ is headed in.

What do you mean ? From what I've seen, there are a lot of interesting things in the next C++ version.

The article on the Apple site suggests using explicit scope :i). Have you tried this with your example?

I tried using the explicit scope but I must be missing something. When I try to declare a variable with "int ::i", I get the (expected) error: invalid use of qualified-name ‘::i’. However, declared inside a block, the test compiles:

struct A {
	void m() {block_ptr b = ^{int ::i = 42; printf("%d\n", i);}; b();}
};

but the printed value is 0… And if I declare a global variable i and print ::i, then the value of the global variable is printed, and not the value of the "local" i.

It looks like there's still something broken in the G++ implementation in that it doesn't recognize that new variables are simple locals to the block, and instead thinks it needs to look them up in the containing class.

Yes. g++ and blocks don't go very well together. Another "fun" thing. If you have a struct:

struct A {
	A() { }
	A(int) { }
};

If you simply declare a variable with "A t1;", the first constructor will be called. Declared it with the __block modifier and the constructor doesn't seem to be called at all.
Next, if you declare a variable with "__block A t2(42);", the compiler crashes with a bus error. However "__block A t2 = A(42);" seems to work.
Or, in the same vein, this: https://forums.macrumors.com/threads/901341/

 

[qtx43]

'friend' only changes access for friends, it is still a regular member function with a 'this' pointer. 'static' member functions don't have a 'this' (like a regular function), although maybe 'calling convention' isn't the right word. I'm blanking on what the right word is.

Yes, it's true, I'm not excited about C++'s direction. I love and hate the language, very flexible and expressive. But it's complicated enough. For example, I don't think functional language extensions are a good fit. I know it makes algorithms semi-usable, but it's way too bloated and complicated already. Even though this thread's question isn't directly an example of it, it's similar to the kinds of things that will happen with C++, and nobody but a language lawyer will know what's going on. Well, this probably isn't the thread to get into a big discussion about C++, so I'll stop.

Oh, and thanks for trying out all those variations that I was interested in but too lazy/busy to do!

 

[ncl]

'friend' only changes access for friends, it is still a regular member function with a 'this' pointer.

According to section 11.4 §1 of the standard (03):

A friend of a class is a function or class that is not a member of the class but is permitted to use the private and protected member names from the class.

So, it is not a regular member function (more precisely, it could be a member function but of another class).

I love and hate the language, very flexible and expressive. But it's complicated enough.

I agree with that However, the functional extensions are amongst the things I am really waiting for. From what I've read, they basically are a simpler syntax for doing the exact same thing as what we've already been doing with function-object. Anyway, as you said, this is not the thread for a discussion like that.

Oh, and thanks for trying out all those variations that I was interested in but too lazy/busy to do!

You're welcome It didn't take long to do these tests because the code snippets I posted where actually parts of the various tests I made a few months ago trying to circumvent the problem the OP posted. And as I posted, I eventually used a friend C function, with a big comment above explaining why I had to do that.

With all this, I hope the OP solved his/her problem...

 

[qtx43]

Yes, I'm talking sloppily, sorry. Earlier post you said they "are" simple functions, sticking the word 'friend' in front of something does not change anything about the this pointer for the designated function, it just changes access granted. That was my point, I don't see why it should have any bearing on this problem.

And yes, it probably did solve OP's problem, but not in a way he liked.

 

[ncl]

Ah ok. I misunderstood what you wrote.
I mentioned the friend function because when I tried to solve the problem, I thought the cause was that since the function was a member (static or not) of the class A, the compiler tries to lookup the local variables in the class A. So I tried by declaring the function friend instead of static. Then the function wouldn't be a member anymore. However, I also defined it inside the class, which didn't work. I had to put the body of the function outside the class.

 

[bilboa]

Very interesting discussion. This does seem like a rather serious bug in Apple's implementation of blocks. The compiler should certainly give precedence to block local variables over variables from outer scopes when resolving variable names inside a block, but it seems to not be doing that when the block is defined inside a member function.

FYI, I've been recently playing with the new C++0x standard implementation of lambda functions in MS Visual Studio 10, and they do not have problems like this, and they do make using the STL much nicer. As a fan of functional programming languages, and languages with some functional programming features, I think it's great that standard C++, and Apple's C, have added lambdas, or blocks as Apple calls them. It's just too bad Apple's implementation has a serious bug like this.

 

[qtx43]

Again, I'm not totally familiar with GCD, but it's my understanding that llvm's blocks are actually a method of queuing up jobs in a separate thread. Which is very different from C++'s new functional functionality (although they do seem similar), which is primarily syntactic-sugar for making templatized-algorithms easier to use. I suppose people smarter than me will come up with (or have already) all sorts of other nifty things to do with them though. If you tried to use GCD to dispatch a C++ lambda function, I'm not sure it would work, since C++ isn't really thread aware, and it probably doesn't have the necessary context information compiled in.

Or maybe I'm all confused.

 

[ncl]

Blocks are anonymous functions. They don't have to be used with GCD. For instance, in Cocoa, several methods expecting callbacks now exists accepting blocks.
And, in GCD, jobs are described using blocks.

C++ lambda are similar to blocks. And they apparently are already used in intel threading building blocks in the same way than blocks are used in GCD.

 

[estin]

Working.

Hey guys, and sorry for my very late answer. I've been really really busy and without time to test all the suggestions(and not really so hard to test it...).

I can confirm that ncl's suggestion is working perfectly ! I have implemented it in several loops on my program without issues. I suppose that's the only way to deal with this problem until g++ becomes more friendly with blocks.

Thank you very much guys. Really appreciated.

 

[Catfish_Man]

clang++ may have better support for blocks in C++; I haven't checked, but I remember discussion of it.