Regarding Code Generation with Sympy

[Tanu Hari Dixit]

Hello all,

I am a GSoC aspirant and I want to work on the Code Generation module as a project this year.

I had a few questions in mind and needed help regarding them.

1) It is mentioned on the ideas page that the codegen module needs an overhaul. What kind of an overhaul would that be? Is the change needed in the API or friendly functions: codegen and make_routine?

2) I read this discussion and construed that we need to make efforts to include CSE in the codegen module and we are aiming at making an optimizing compiler.
This optimizing compiler should be domain unspecific and work for most general cases. Bjorn Dahlgren suggested that we should be using a templating engine. Is this the work that is needed to be done in this project?

3) I read this blog post by Jason K. Moore where he talked about compiler optimizations like loop unrolling. Is this project is about finding balance between what the code generator should do and what the compiler should do? This blog post is a year old. Has this already been implemented?

4) What is the magnitude and nature of work that is incorporated in this idea? Is there some ongoing work that I should be aware of?

5) Please suggest some reading sources, so that I am able to take this up.

Thank you,
Tanu Hari Dixit.

[Jason Moore]

Jason
moorepants.info
+01 530-601-9791

On Tue, Mar 1, 2016 at 10:25 PM, Tanu Hari Dixit <token...@gmail.com> wrote:

Hello all,

I am a GSoC aspirant and I want to work on the Code Generation module as a project this year.

I had a few questions in mind and needed help regarding them.

1) It is mentioned on the ideas page that the codegen module needs an overhaul. What kind of an overhaul would that be? Is the change needed in the API or friendly functions: codegen and make_routine?

There is some work starting on an overhaul, see: https://github.com/sympy/sympy/wiki/Code-Generation-Notes. There are some related pull requests, look for symcc.

 

2) I read this discussion and construed that we need to make efforts to include CSE in the codegen module and we are aiming at making an optimizing compiler.
This optimizing compiler should be domain unspecific and work for most general cases. Bjorn Dahlgren suggested that we should be using a templating engine. Is this the work that is needed to be done in this project?

Yes, cse definitely needs to be incorporated into code gen as an option. Developing templates may be a good route, but I think Aaron is exploring some different ideas based on some of Jim Crist's work.

 

3) I read this blog post by Jason K. Moore where he talked about compiler optimizations like loop unrolling. Is this project is about finding balance between what the code generator should do and what the compiler should do? This blog post is a year old. Has this already been implemented?

There are a lot of compiler optimizations that are available in different compilers. We need to figure out what are the be pre-optimizations that we can do at the sympy level when we have mathematical knowledge of the expressions. These should compliment and enhance the optimizations that compilers do. For example, gcc does some cse but it doesn't do it extensively and to a significant depth. If we pre-cse before compiling with gcc, you can get significant speed ups.

 

4) What is the magnitude and nature of work that is incorporated in this idea?

It can be as much as you like, but the GSoC proposal should be scoped appropriately for the summer's full time work.

 

Is there some ongoing work that I should be aware of?

Yes, see above.

 

5) Please suggest some reading sources, so that I am able to take this up.

I don't know of any. I think you want to learn about compiler optimizations. Also see what other CAS systems offer on this front.

 

Thank you,
Tanu Hari Dixit.

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/256b3c22-fcee-41c9-8cf4-f545a0e92dbb%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Tanu Hari Dixit]

Thank you, Jason, for the reply.

I went through the notes put up on the wiki and the optimizations that are required through code generation. I also looked through the pull request #10486.
I had a few questions regarding what needs to be done. I'll be glad if you answer them.

1) exp2 is used in pyne because probably radioactive decay analysis requires a lot of exponentiation. Why would a general code generator generate code with exp2 (unless the user specifies it or we need to calculate powers of 2 or we have guessed somehow that the exponentiation is a large one)?

2)Do we need to make a specialized polynomial evaluator in C/other languages that uses horner? Will we be processing polynomials as strings initially? I found a few references for this----

     i) http://www.cs.berkeley.edu/~fateman/papers/polyval.pdf
     ii) http://cgpe.gforge.inria.fr/index.php?page=home
     iii) https://hal.archives-ouvertes.fr/ensl-00531721/document

Am I in the right direction?

3)I looked at this: https://github.com/SkidanovAlex/interpreter and I tried to understand the fast-matrix exponentiation algorithm. I want to try to implement this. Please provide me with a starting point. In other words, I want to know about a few examples where implementing this would be worthy so that I know where the code should be added.

4)I tried to look into the code of some of the sources (Stuff outside of SymPy) available in the notes on the wiki. I found that pycodeexport uses Mako as the templating engine and PyNE uses jinja2. You mentioned that Aaron might be exploring different ideas (other than templating). What are those?

5)Aaron has added the newly built Assignment and aug_assign and removed datatype and variables (https://github.com/asmeurer/sympy/commit/bd0a5e788fa423f1ebf0ef91455e719a4b65803e) What is the alternative to datatype and variables?

Thank you,
Tanu Hari Dixit.
 

[Jason Moore]

I'm not familiar with a lot of the details you are mentioning here. Aaron is more familiar with what he's written up there. One response below.

Jason
moorepants.info
+01 530-601-9791

On Thu, Mar 3, 2016 at 7:57 AM, Tanu Hari Dixit <token...@gmail.com> wrote:

Thank you, Jason, for the reply.

I went through the notes put up on the wiki and the optimizations that are required through code generation. I also looked through the pull request #10486.
I had a few questions regarding what needs to be done. I'll be glad if you answer them.

1) exp2 is used in pyne because probably radioactive decay analysis requires a lot of exponentiation. Why would a general code generator generate code with exp2 (unless the user specifies it or we need to calculate powers of 2 or we have guessed somehow that the exponentiation is a large one)?

2)Do we need to make a specialized polynomial evaluator in C/other languages that uses horner? Will we be processing polynomials as strings initially? I found a few references for this----

     i) http://www.cs.berkeley.edu/~fateman/papers/polyval.pdf
     ii) http://cgpe.gforge.inria.fr/index.php?page=home
     iii) https://hal.archives-ouvertes.fr/ensl-00531721/document

Am I in the right direction?

3)I looked at this: https://github.com/SkidanovAlex/interpreter and I tried to understand the fast-matrix exponentiation algorithm. I want to try to implement this. Please provide me with a starting point. In other words, I want to know about a few examples where implementing this would be worthy so that I know where the code should be added.

4)I tried to look into the code of some of the sources (Stuff outside of SymPy) available in the notes on the wiki. I found that pycodeexport uses Mako as the templating engine and PyNE uses jinja2. You mentioned that Aaron might be exploring different ideas (other than templating). What are those?

The methods in PR #10486 are in line to avoid using templates. There will be objects for all types of common structures in programming languages.

5)Aaron has added the newly built Assignment and aug_assign and removed datatype and variables (https://github.com/asmeurer/sympy/commit/bd0a5e788fa423f1ebf0ef91455e719a4b65803e) What is the alternative to datatype and variables?

Thank you,
Tanu Hari Dixit.
 
On Wednesday, March 2, 2016 at 11:55:21 AM UTC+5:30, Tanu Hari Dixit wrote:

Hello all,

I am a GSoC aspirant and I want to work on the Code Generation module as a project this year.

I had a few questions in mind and needed help regarding them.

1) It is mentioned on the ideas page that the codegen module needs an overhaul. What kind of an overhaul would that be? Is the change needed in the API or friendly functions: codegen and make_routine?

2) I read this discussion and construed that we need to make efforts to include CSE in the codegen module and we are aiming at making an optimizing compiler.
This optimizing compiler should be domain unspecific and work for most general cases. Bjorn Dahlgren suggested that we should be using a templating engine. Is this the work that is needed to be done in this project?

3) I read this blog post by Jason K. Moore where he talked about compiler optimizations like loop unrolling. Is this project is about finding balance between what the code generator should do and what the compiler should do? This blog post is a year old. Has this already been implemented?

4) What is the magnitude and nature of work that is incorporated in this idea? Is there some ongoing work that I should be aware of?

5) Please suggest some reading sources, so that I am able to take this up.

Thank you,
Tanu Hari Dixit.

--

You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/ac891a0e-4a37-4bdc-bc51-79a8beacf9df%40googlegroups.com.

[Aaron Meurer]

On Wed, Mar 2, 2016 at 1:25 AM, Tanu Hari Dixit <token...@gmail.com> wrote:
> Hello all,
>
> I am a GSoC aspirant and I want to work on the Code Generation module as a
> project this year.
>
> I had a few questions in mind and needed help regarding them.
>
> 1) It is mentioned on the ideas page that the codegen module needs an
> overhaul. What kind of an overhaul would that be? Is the change needed in
> the API or friendly functions: codegen and make_routine?
>
> 2) I read this discussion and construed that we need to make efforts to
> include CSE in the codegen module and we are aiming at making an optimizing
> compiler.
> This optimizing compiler should be domain unspecific and work for most
> general cases. Bjorn Dahlgren suggested that we should be using a templating
> engine. Is this the work that is needed to be done in this project?

The end goal is to get people to write computational mathematical code
in a high level way so that it's readable, reproducible, maintainable,
and avoids unnecessary bugs from things like typos, dropped signs, and
so on. The way this is achieved is through code generation. The
details are not set in stone. Some people feel that templating is the
best way to do this. Others feel that templating leads to spaghetti
code that is unreadable and difficult to refactor. Code generation is
a tough problem because there are broad use cases and each use case
has its own needs, which are often not really important for others.
For instance, for one use case it may be essential to generate code
with matrices; for another, matrices may not be used at all.

I suggest reading through the code generation notes page on the wiki
(most of it was written by me), and looking at some of the example
projects that use code generation (with or without SymPy), to get a
feel for what the use cases are and what works and what doesn't work
(I wrote some of my own opinions on the wiki, but you're allowed to
disagree with me). In other words, you should figure out what is
needed and the best way to do it, and write that in your proposal.

You should know that I am working on code generation in SymPy, but I
think there is room for more than one person.

>
> 3) I read this blog post by Jason K. Moore where he talked about compiler
> optimizations like loop unrolling. Is this project is about finding balance
> between what the code generator should do and what the compiler should do?
> This blog post is a year old. Has this already been implemented?

That is right. There are many kinds of optimizations that compilers
won't do, but SymPy can (for example, trig simplification). There are
other optimizations that it can do, but which may need to be disabled
for very large code generated expressions (in other words, sometimes
you have to compile code with -O0 or else the compiler takes too
long).

Aaron Meurer

>
> 4) What is the magnitude and nature of work that is incorporated in this
> idea? Is there some ongoing work that I should be aware of?
>
> 5) Please suggest some reading sources, so that I am able to take this up.
>
> Thank you,
> Tanu Hari Dixit.
>

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/256b3c22-fcee-41c9-8cf4-f545a0e92dbb%40googlegroups.com.

[Aaron Meurer]

On Thu, Mar 3, 2016 at 10:57 AM, Tanu Hari Dixit <token...@gmail.com> wrote:
> Thank you, Jason, for the reply.
>
> I went through the notes put up on the wiki and the optimizations that are
> required through code generation. I also looked through the pull request
> #10486.
> I had a few questions regarding what needs to be done. I'll be glad if you
> answer them.
>
> 1) exp2 is used in pyne because probably radioactive decay analysis requires
> a lot of exponentiation. Why would a general code generator generate code
> with exp2 (unless the user specifies it or we need to calculate powers of 2
> or we have guessed somehow that the exponentiation is a large one)?

The idea is to have an optimization pipeline, with smart defaults, but
which can be customized by the user.

For exp2, the code generator should be able to have enough information
to look at the expression and make a smart guess if rewriting an
expression using exp2 will be faster.

>
> 2)Do we need to make a specialized polynomial evaluator in C/other languages
> that uses horner? Will we be processing polynomials as strings initially? I
> found a few references for this----
>
> i) http://www.cs.berkeley.edu/~fateman/papers/polyval.pdf
> ii) http://cgpe.gforge.inria.fr/index.php?page=home
> iii) https://hal.archives-ouvertes.fr/ensl-00531721/document
>
> Am I in the right direction?

I was thinking more along the lines of calling horner() on an
expression or subexpression.

>
> 3)I looked at this: https://github.com/SkidanovAlex/interpreter and I tried
> to understand the fast-matrix exponentiation algorithm. I want to try to
> implement this. Please provide me with a starting point. In other words, I
> want to know about a few examples where implementing this would be worthy so
> that I know where the code should be added.

My symcc branch has the necessary operators for that algorithm, so I
suppose it could be implemented there (say, some function that takes
in a CodeBlock and returns an optimized CodeBlock).

As to where to put it, that isn't clear yet. I haven't worked out
exactly what the optimization pipeline will look like in the codebase
yet.

>
> 4)I tried to look into the code of some of the sources (Stuff outside of
> SymPy) available in the notes on the wiki. I found that pycodeexport uses
> Mako as the templating engine and PyNE uses jinja2. You mentioned that Aaron
> might be exploring different ideas (other than templating). What are those?

The alternative to templating is generating AST expressions (see my
symcc branch).

>
> 5)Aaron has added the newly built Assignment and aug_assign and removed
> datatype and variables
> (https://github.com/asmeurer/sympy/commit/bd0a5e788fa423f1ebf0ef91455e719a4b65803e)
> What is the alternative to datatype and variables?

I removed those because I haven't thought about them enough to
determine if that's the best way to implement them. If you have any
thoughts on it feel free to open an issue for discussion.

(by the way, I think I just need to push a few more tests to my symcc
branch and then it can be reviewed and merged)

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/ac891a0e-4a37-4bdc-bc51-79a8beacf9df%40googlegroups.com.

[Tanu Hari Dixit]

Thank you, Jason and Aaron for the elaborate reply.

I am now a bit clear as to what has to be done if one takes this up.
I also understood why you have considered AST as a better option than templating.

Also, this is what I construed:

1)An optimization pipeline has to be formulated.

I have thought about this and think that it should be somewhat like this:

2)The optimizer can implement the following with individual switches:

i)unrolled pow(x, n)

ii)fused add multiply for floating point calculations

iii)intelligent guess about whether to use exp2

iv)horner

v)horner with fused add multiply, maybe?

vi)fast matrix exponentiation that takes in an AST

vii)trignometric simplification

viii)pre-computing constant expressions

ix)using cse with 'basic' optimization.

x)splitting very large expressions into number of Augmented Assignments

xi)fractional power optimization (a=x**(1/2), b=x**(3/2) => a=x**(1/2), b=x*a)

xii)integer power optimization (a=x**8, b=x**10 => t1=x**2, t2=t1**2, a=t2**2, b=a*t1

xiii)Sub-product optimization (a=xyz, b=wyz => t1=yz, a=xt1, b=wt1)

xiv)Sum multiple optimization (a =x-y, b=2y-2x => a=x-y, b=-2a)

The last four are taken from http://www.jnaiam.org/new/uploads/files/16985fffb53018456cf3506db1c5e42b.pdf which is a paper by Allan Wittkopf on code generation in Maple.

I understand that these optimizations need to be tested and might not necessarily provide a speed up in all contexts.

I would like to ask if you have any comments on how you think the optimization pipeline should be (improvements on the naive model I drew on Pinta) and according to you, which of the above optimizations are worth being included ( after being tested ).

[Björn Dahlgren]

On Wednesday, 9 March 2016 14:57:14 UTC+1, Tanu Hari Dixit wrote:

2)The optimizer can implement the following with individual switches:

i)unrolled pow(x, n)

ii)fused add multiply for floating point calculations

iii)intelligent guess about whether to use exp2

i, ii) any modern compiler makes this moot, it's simply a matter of supplying the correct flags (whether SymPy should know about these flags for respective compiler or not I don't know).
iii) I know Anthony Scopatz does this, but on the hardware and compilers I've tested this on I've seen everything from ~15% faster to 50% slower execution. Again, we would have to teach SymPy about combinations of math library versions, compiler versions and hardware.
 

iv)horner

v)horner with fused add multiply, maybe?

vi)fast matrix exponentiation that takes in an AST

vii)trignometric simplification

viii)pre-computing constant expressions

ix)using cse with 'basic' optimization.

x)splitting very large expressions into number of Augmented Assignments

xi)fractional power optimization (a=x**(1/2), b=x**(3/2) => a=x**(1/2), b=x*a)

xii)integer power optimization (a=x**8, b=x**10 => t1=x**2, t2=t1**2, a=t2**2, b=a*t1

I wonder if compilers do this already, I have not tried myself.

xiii)Sub-product optimization (a=xyz, b=wyz => t1=yz, a=xt1, b=wt1)

xiv)Sum multiple optimization (a =x-y, b=2y-2x => a=x-y, b=-2a)

The last four are taken from http://www.jnaiam.org/new/uploads/files/16985fffb53018456cf3506db1c5e42b.pdf which is a paper by Allan Wittkopf on code generation in Maple.

I would be inclined to think that a lot has happened to the optimizers in compilers since 2007, one would need to replicate some of the experiments on modern hardware/compilers.
 

I understand that these optimizations need to be tested and might not necessarily provide a speed up in all contexts.

I would like to ask if you have any comments on how you think the optimization pipeline should be (improvements on the naive model I drew on Pinta) and according to you, which of the above optimizations are worth being included ( after being tested ).

As you say, testing this will be crucial. SymPy would need access to some dedicated hardware and I suppose a benchmark suite for SymPy generated code would be almost a must?
 

[Tanu Hari Dixit]

Bjorn,

Thanks for the reply.

 

I would be inclined to think that a lot has happened to the optimizers in compilers since 2007, one would need to replicate some of the experiments on modern hardware/compilers.

As you say, testing this will be crucial. SymPy would need access to some dedicated hardware and I suppose a benchmark suite for SymPy generated code would be almost a must?

Will this project require some resources which I might not be able to arrange? I am really lost as to what has to be done. I need to draft a proposal and ascertain a timeline of the implementation.
Though, I read through the notes on the Wiki and the optimizations listed (in this page and my last mail), ( I also went through the various links on this discussion on the mailing list), I am not able to find a suitable starting point.
Please help me.

Thanks,
Tanu Hari Dixit.

[Aaron Meurer]

Some of those optimizations are special cases of cse() (see also
https://github.com/sympy/sympy/issues/10228).

Regarding compilers, two things of note: first, compilers are
generally very conservative unless you use --ffast-math. Second,
sometimes code generated expressions are so large that you have to use
-O1 or -O0.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/ae39dab4-2f6e-4a17-abdd-99f79fba0453%40googlegroups.com.

[Tanu Hari Dixit]

Aaron,

Thank you for the reply.

Tanu Hari Dixit.