Faster Common Subexpression Elimination (CSE) in SymPy

09Sep13

Over the past months I’ve been studying  how to improve performance of the Common Subexpression Elimination (CSE) routine of SymPy, so it can be used in SymPyBotics with acceptable computing times.

This resulted in pull request #2355, which had already been merged into SymPy master branch (for release in version 0.7.4).

Here is an example comparing both new and previous CSE implementations when applied to the expressions of the “generic torque”, computed with SymPyBotics, for the first 3 joints of a 7-DOF WAM Arm robot.

Cache has influence in times, but we can notice an average performance improvement of about 25x when external (pre and post) optimizations are used. When no external optimizations are used, the performance has an average improvement of 90x. With the new `order=’none’` option, the improvement rises to 500x for the non cached case, and to 1000x for the cached one!

For this particular case, the CSE is less optimized when external optimizations are done (output has more operations) than when they are not.

How it works now

First, two remarks:

  • expressions are not trees but rather directed acyclic graphs (DAG).  E.g., in the expression sin(x+1)+cos(x+1), the arguments of sin and cos are the same, x+1; indeed the node x+1 has two parents;
  • SymPy (sub)expressions are nicely and fastly hashable, thus great to use in sets and dictionaries.

The CSE core/raw algorithm:

  1. The core of the new CSE parses the expression adding each seen subexpression to the seen set. If a subexpression was already seen, it is added to the repeated set and its children nodes are not parsed (there is no need to).
  2. After knowing the repeated subexpressions (nodes with more than one parent), the core CSE rebuilds the whole tree using intermediate variables in place of repeated subexpressions.

The internal optimizations:

  • Before the core CSE algorithm is performed the expression is parsed to find optimization opportunities; when an optimizable subexpression is found it is added to the opt_subs substitutions dictionary.
  • When the core algorithm parses a subexpressions it looks for it in the opt_subs dictionary, if it is there is parses the substitution instead.
  • The currently implemented internal optimizations are the following:
    • negative signs are striped out from multiplications, e.g., -2*x is substituted by -1*(2*x)
    • negative signs are striped out from exponents, e.g., x**(-2*y) is substituted by (x**(2*y))**-1
    • common Add and Mul terms are grouped, e.g., in cos(a+b+c)+sin(a+b+d)),  a+b+c is substituted by (a+b)+c and a+b+d is substituted by (a+b)+d, so that a+b is a single and repeated node

Future work

In my opinion three things could further improve CSE:

  1. add support for MatrixExprs;
  2. use replacement Symbols which could somehow clone the assumptions of the subexpressions they represent;
  3. implement an optimal Mul/Add term matching system (maybe using Matthew Rocklin’s logpy package).
Advertisements


4 Responses to “Faster Common Subexpression Elimination (CSE) in SymPy”

  1. It won’t be indicative of actual performance, but you can try disabling the SymPy cache by setting the environment variable SYMPY_USE_CACHE=no before importing sympy.

    • Ok thanks, but I’ll let as it is. I clear cache between the different cse calls so that the order they are called does not affect the times.

  2. I’m happy to help with any efforts on MatrixExprs or any use of LogPy.

    More generally why support just Exprs and MatrixExprs, what stops a solution on Basics. Is it the lack of a generic Basic Symbol?

    • Thank you Matthew.

      The CSE makes sense for the creation of intermediate variables/symbols representing (sub-)expressions. For now I seen two cases, the Symbol and the MatrixSymbol to represent Exprs and MatrixExprs, respectively.

      The inclusion of MatrixSymbols/MatrixExprs in CSE is not so difficult, it just needs to add some more is_XXXX or isinstance conditions. I had already implemented basic support for that in older commits, but I removed it in order to focus the speedup objective.

      I hope to have some time in the near future to get back to work on SymPy CSE.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s