Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
Coincidentally, the author of the HLearn library has a series of posts on this now. –  Xodarap Nov 25 '12 at 16:03
add comment

2 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
Nice observation. Maybe you should specify that you are assuming that $a_k \oplus a_k$ can be computed in $O(1)$ time. –  Zach Langley Nov 24 '12 at 0:17
add comment

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.

share|improve this answer
    
I was thinking about this - do you know if it's actually faster? –  Xodarap Nov 24 '12 at 14:42
    
It could make a difference inside a loop, for example. –  Roberto Mizzoni Nov 24 '12 at 21:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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