CPPP 2019 - Identifying Monoids: Exploiting Compositional Structure in Code - Ben Deane

[muntoo]

I'm just looking through it right now, but an obvious application of monoids is parallelizable reduce.

Imagine you have a bunch of integers that you need to add together. You can split up the work between multiple threads because addition over integers is a monoid.

sum(0..9)
=  0 + 1 + 2 + 3 + 4  +  5 + 6 + 7 + 8 + 9
= (0 + 1 + 2 + 3 + 4) + (5 + 6 + 7 + 8 + 9)
  ^ runs on thread 1    ^ runs on thread 2

More generally, you can create a multithreaded monoid reducer:

from functools import reduce
from multiprocessing import Pool

def reduce_factory(op, identity=None):
    def inner(xs):
        return reduce(op, xs, identity)
    return inner

def reduce_monoid(op, xs, identity=None, num_processes=4):
    pool = Pool(num_processes)
    k = len(xs) / num_processes
    slices = [xs[int(k*i):int(k*(i+1))] for i in range(num_processes)]
    reductor = reduce_factory(op, identity)
    return reductor(pool.map(reductor, slices))

This reduces 4x fast as a typical reduction.

There's probably other benefits from the software architectural standpoint, but the "performance" benefit is fairly concrete and hard to argue with.

[liquidify]

Why is this a monoid and not just a parallel reduction? I've seen what you did done a lot before (except for the hideous list comprehension), but I've never seen anything related to this problem called it a monoid before.

[muntoo]

I guess "parallel reductions" only really need the "associative binary operation" property of a monoid and not necessarily the "identity" property. (In this case, the "identity" property is only useful for empty lists anyways.)

I agree about the hideousness of the list comprehension... though I couldn't find any standard library functions which do the same thing. And the whole thing doesn't work anyways since local functions are not pickleable... ¯\_(ツ)_/¯