7
$\begingroup$

Many common operations are monoids. Haskell has leveraged this observation to make many higher-order functions more generic (Foldable being one example).

There is one obvious way in which using monoids can be used to improve performance: the programmers is asserting the operation's associativity, and so operations can be parallelized.

I'm curious if there are any other ways a compiler could optimize the code, knowing that we're dealing with a monoid.

$\endgroup$
  • $\begingroup$ Coincidentally, the author of the HLearn library has a series of posts on this now. $\endgroup$ – Xodarap Nov 25 '12 at 16:03
7
$\begingroup$

The compiler can optimize exponentiation with monoids. Let $\oplus$ be a binary operator calculateable in constant time such that $\oplus$ and $a_1, a_2, ... \in A$ form a monoid. Then the operation

$$\bigoplus_{[1..n]} a_k = \underbrace{a_k \oplus a_k \oplus \dots \oplus a_k}_{\text{$n$ times}}$$

which usually takes $\cal O(n)$ time can be evaluated with the square and multiply algorithm in only $\cal O(\log n)$ time if the compiler knows that $\oplus$ obeys the monoid laws.

$\endgroup$
  • 1
    $\begingroup$ Nice observation. Maybe you should specify that you are assuming that $a_k \oplus a_k$ can be computed in $O(1)$ time. $\endgroup$ – Zach Langley Nov 24 '12 at 0:17
0
$\begingroup$

If you are in the constant folding/constant propagation step, whenever you come up with the identity of the monoid, you can just ignore it if it's multiplying other non-constant expressions.

$\endgroup$
  • $\begingroup$ I was thinking about this - do you know if it's actually faster? $\endgroup$ – Xodarap Nov 24 '12 at 14:42
  • $\begingroup$ It could make a difference inside a loop, for example. $\endgroup$ – Roberto Mizzoni Nov 24 '12 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.