5 ms·

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

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-analytics/ https://www.infoq.com/presentations/abstract-algebra-analyti...

sukilot 6y ago
And that was 10 years before Haskell went huge in that idea.
- lliamander 6y ago
  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/ http://www.generic-programming.org/
skybrian 6y ago
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.
- lliamander 6y ago
  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.
- Koshkin 6y ago
  That’s why in C++ we have traits and overloading.
  - rumanator 6y ago
    Could you explain where do you see traits and overloading helping you with floating point operations?
    - mlvljr 6y ago
      He will - when you fail his phone screen :) Kidding.
- quietbritishjim 6y ago
  > 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.
- lmm 6y ago
  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.
kens 6y ago
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.
- lliamander 6y ago
  Yep. And if what you have is an Abelian Group, then you also get distributed computation as well (thanks to commutativity).
  - dllthomas 6y ago
    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.
    - lliamander 6y ago
      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.
      - dllthomas 6y ago
        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_kmett_there_and_back_again_regular_and/ https://www.reddit.com/r/haskell/comments/9x684a/edward_kmet...
    - Koshkin 6y ago
      To be fair, Abel did not know (or care) about semigroups.
      - dllthomas 6y ago
        That matches my understanding, but the terminology is still (IME) common.
algebra-history 6y ago
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?
- vikiomega9 6y ago
  If you're thinking about map-reduce, the original Google paper talks about associativity.

sukilot 6y ago

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

lliamander 6y ago
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/ http://www.generic-programming.org/

skybrian 6y ago

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.

lliamander 6y ago
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.
Koshkin 6y ago
That’s why in C++ we have traits and overloading.
- rumanator 6y ago
  Could you explain where do you see traits and overloading helping you with floating point operations?
  - mlvljr 6y ago
    He will - when you fail his phone screen :) Kidding.
quietbritishjim 6y ago
> 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.
lmm 6y ago
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.

kens 6y ago

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.

lliamander 6y ago
Yep. And if what you have is an Abelian Group, then you also get distributed computation as well (thanks to commutativity).
- dllthomas 6y ago
  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.
  - lliamander 6y ago
    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.
    - dllthomas 6y ago
      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_kmett_there_and_back_again_regular_and/ https://www.reddit.com/r/haskell/comments/9x684a/edward_kmet...
  - Koshkin 6y ago
    To be fair, Abel did not know (or care) about semigroups.
    - dllthomas 6y ago
      That matches my understanding, but the terminology is still (IME) common.

algebra-history 6y ago

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?

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