Adding a Par construct to Python?

[Steven D'Aprano]

Why would it or need it? A Python that understands the ``par'' keyword
is supposed to know it can play some tricks with optimizing reduce() if
the specific function is commutative.

Fine. Move the smarts out of reduce() into the compiler. How is the
compiler supposed to know if an arbitrary function is commutative?

 

[Aaron Brady]

Fine. Move the smarts out of reduce() into the compiler. How is the
compiler supposed to know if an arbitrary function is commutative?

Unit testing.

 

[CTO]

Unit testing.

I think this kind of gets to the heart of it, here- parallelization
is not a toy, runs with scissors, and will eat your dog, but so will
everything else if you don't know what you're doing. I just don't
see this as being a valid argument- maybe I'm wrong.

In the spirit of continuing to be wrong, would it be possible to
just fork off and synchronize the passed-in variables at the end
of the block via a container in shared memory? That sounds to me
like the simple, safe route, if a route must be taken.

Geremy Condra

 

[Steven D'Aprano]

Unit testing.

(Correction: the characteristic we really care about is associativity,
not commutativity.)

I really shouldn't reply to this, because I fear this is just going to
drag me down into a bottomless pit, but here goes...

I don't see how unit tests can possibly help. There's an infinite number
of possible functions that could be passed to parallel reduce(), and you
can't test them all. Even if you lower your sights and just aim to
recognise a tiny subset of associative functions, you end up with code
like this:

def par_reduce(func, *args):
if func in (operator.add, operator.mul):
if isinstance(args[0], (int, long)):
return _associative_par_reduce(func, *args)
return _nonassociative_par_reduce(func, *args)

You can't even recognise functions like lambda x,y: x+y. In case you're
thinking you can, no, "if func == lambda x,y: x+y" won't work:
False

I suppose if you're willing to special case a tiny handful of functions,
that's a solution of sorts, but I did ask about arbitrary functions.

Perhaps you're thinking of another approach: put the unit tests inside
the par_reduce() function, and use them to determine at runtime whether
or not the argument func is associative.

def par_reduce(func, *args):
try:
# a mass of unittests
except Exception:
# are we catching too much? are we masking bugs in the tests?
return _nonassociative_par_reduce(func, *args)
return _associative_par_reduce(func, *args)


This would be impractical, because the cost would be enormous. But even
putting that aside, it still wouldn't work. I don't see how you could
know what is a valid unittest for an arbitrary function, but suppose you
could, somehow. Then what? True enough, if you run lots of tests, and it
fails one, then you know that func is not associative. But having passed
all those tests, you can't know if your tests covered all the possible
cases.

E.g. for floats, you can run some tests and decide that addition looks
associative:
True

but you'd be wrong:
False

No, you can't expect to discover experimentally whether an arbitrary
function is associative. You would need to analyse what the function
does, which means in practice the *programmer* needs to decide what to
do, not reduce().

 

[Lawrence D'Oliveiro]

That depends on the operation in question. Addition for example would
work. My math-skills are a bit too rusty to qualify the exact nature of
the operation, commutativity springs to my mind.

Associativity:

((A op B) op C) = (A op (B op C))

So for example

A op B op C op D

could be grouped into

(A op B) op (C op D)

and the two parenthesized subexpressions evaluated concurrently. But this
would only give you a speedup that was logarithmic in the number of op's.

 

[Lawrence D'Oliveiro]

threads = [PMapThread(datapool) for i in xrange(numthreads)]

Shouldn’t that “PMapThread†be “thread�

 

[Terry Reedy]

Associativity:

((A op B) op C) = (A op (B op C))

So for example

A op B op C op D

could be grouped into

(A op B) op (C op D)

and the two parenthesized subexpressions evaluated concurrently. But this
would only give you a speedup that was logarithmic in the number of op's.

It is worth noting, I think, that many realistic operations are not
associative. If op combines a summary and an item to create an updated
summary, it will probably croak or give a wrong answer when given a
summary and a summary. Combining two summaries might be possible, but
would be a different operation.

For a specific example, consider list.append(some_list, some_item)
versus list.extend(some_list, another_list). Imagine for that moment
that these methods returned some_list. Then

[].append(a).append(b).append(c).append(d) # parentheses left out

would have to be conceptually converted to the associative

[].extend([a]).extend().extend([c]).extend([d])

before being grouped something like

(([].extend([a])).extend(.extend([c]))).extend([d])

Of course, one would not do the conversion to the slower associative
operation unless one knew that there would be a compensating speedup due
to the grouping.

Terry Jan Reedy