Hacker News Reader

Comment by lliamander | Hacker News Reader

Rule 5 seems to mirror one of my favorite insights from Alexander Stepanov:

> In 1976, still back in the USSR, I got a very serious case of food poisoning from eating raw fish. While in the hospital, in the state of delirium, I suddenly realized that the ability to add numbers in parallel depends on the fact that addition is associative. (So, putting it simply, STL is the result of a bacterial infection.) In other words, I realized that a parallel reduction algorithm is associated with a semigroup structure type. That is the fundamental point: algorithms are defined on algebraic structures.

This is also exemplified in the analytics infrastructure used at stripe: https://www.infoq.com/presentations/abstract-algebra-analyti...

View on HN

In case you've wondered what a monoid is, that's a monoid. Something with an associative operation (and an identity), so you can do the operation on chunks in parallel, like addition.

Every monoid is a semigroup, but it's only a monoid if there is also a value that serves as an identity.

Yep. And if what you have is an Abelian Group, then you also get distributed computation as well (thanks to commutativity).

While true, that's too strict. An Abelian group (like any group) needs inverses. You get distributed computation if you've got an Abelian semigroup.

Thanks for the correction. I think that in Avi Bryant's talk (that I linked to above) Stripe ended up using Abelian groups for some reason, rather than Abelian semigroups, though if so I forget the reason why.

Inverses don't show up as much as I'd (aesthetically?) like in computing. There was an interesting application here: https://www.reddit.com/r/haskell/comments/9x684a/edward_kmet...

To be fair, Abel did not know (or care) about semigroups.

That matches my understanding, but the terminology is still (IME) common.

You can distribute the computation on just a monoid as well but it needs more bookkeeping. In particular, your reduce function should know

* lhs is before rhs

* There is no data between lhs and rhs

One way of looking at it is that equipping our data with that bookkeeping gives us something that commutes.

Hmm sure, but it is not a requirement that your underlying algebraic structure should commute, so I think original phrasing was misleading. The bookkeeping allows you to commute a specific list of objects, even though the underlying operation is anti-commutative (i.e. exists a,b a.b != b.a).

At the moment of computation, you can build a new structure that commutes by enumerating the data. I guess it's true that you need a commuting intermediate data structure to be able to distribute.

Yeah, I think it's informative that you "need commutativity" but important that you can build it yourself. It's nice (mostly from an efficiency standpoint, sometimes from a complexity stnadpoint) when you can get it "for free" because the underlying type is commutative, and the fact that you're shooting for commutativity can inform how you build and test the bookkeeping.

As an interesting nit, "anticommutative" specifically means that a.b = -(b.a), which is different than simply not being commutative.

A group might be commutative, anticommutative, neither, or even both (trivially true of the empty group and the group with one element, but I think it can be true of larger groups).

Ah, my terminology is rusty as it's been years since my math classes. I guess I need to review my algebra books again. I do have some personal code that called "exists a,b a.b != b.a" anticommutative, didn't even realize that's wrong terminology!

One of the ideas in the talk I link is how you can represent typically non-commutative data (like averages) in a data structure that does support commutative operations (numerator/denominator pair) and to take advantage of generic analytics infrastructure.

But adding floating point numbers isn't associative, in general. Sometimes you need to do it the right way to avoid catastrophic cancellation.

I guess the key is to know how to deal with things that are only mostly true.

> But adding floating point numbers isn't associative, in general. Sometimes you need to do it the right way to avoid catastrophic cancellation.

That exactly proves his point. Systems that are associative can be processed by the parallel algorithm he was thinking of. Floating point numbers, if you care about their non-associativity, cannot be processed by that algorithm. So the validity is that algorithm depends on whether the system is associative.

That's true about floating point numbers. I assume that depending upon the context, it may not be a big issue (e.g. GPU compute)?

In any case, the point Stepanov was making is that if you want to be able to use a certain algorithm, then you have to make a choice to represent your data in a way that enables that algorithm, and the way you know whether the structure is appropriate for that algorithm is the algebraic properties of the structure.

No, the key is to use good abstractions unless you have a really good reason. New code should not be using IEEE 754 floating point unless you have benchmarks and profiles showing that you actually need to.

That’s why in C++ we have traits and overloading.

Could you explain where do you see traits and overloading helping you with floating point operations?

And that was 10 years before Haskell went huge in that idea.

I'm not super familiar with either the C++ or Haskell communities, but Stepanov's notion of Generic Programming[1] certainly seems to fit with the Haskell ethos.

[1]http://www.generic-programming.org/

Recently I searched the Web, trying to find out the origin of monoids as an approach to distributed computing, and couldn’t find it. This quote is a great find for me! Is this the origin?

If you're thinking about map-reduce, the original Google paper talks about associativity.

Reply on news.ycombinator.com