In Elements of Programming Interviews, authors talk about a tip for understanding how to use primitive types (int, double, etc).

Be aware that commutativity and associativity can be used to perform operations in parallel and reorder operations.

I'm having trouble even imagining what these means in the context of bits. For anyone who better grasps what this means, could you explain it and flesh it out with some examples?


Consider the following code:

a = (b + c) + d

e = c + (b + f)

Using associativity and commutativity, we can improve it to

t = b + c

a = t + d

e = t + f

This uses one less addition. Since integer addition (ignoring overflow) is guaranteed to be commutative and associative, an optimizing compiler is allowed to use this optimization. The same isn't quite true for floating point addition, which is not associative.

| cite | improve this answer | |
  • $\begingroup$ Great, this explains the use case in reorder operations really well. Do have an example for how associativity and commutivity can help in parallel operations? $\endgroup$ – Edmund Korley Sep 2 '17 at 10:51
  • $\begingroup$ Unfortunately I'm not an expert in parallel computing. But I guess that you can remove or delay dependencies by rearranging operands. $\endgroup$ – Yuval Filmus Sep 2 '17 at 19:52
  • $\begingroup$ Commutivity means you can do atomic operations without any other synchronization, since the order does not matter. Think about summing a huge array in parallel. $\endgroup$ – Elazar Oct 1 '17 at 12:03

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.