ANN: CSymPy, fast symbolic manipulation library, written in C++

[Ondřej Čertík]

Hi,

I'd like to announce CSymPy:

https://github.com/certik/csympy

a fast symbolic manipulation library written in C++.
The goal is to eventually be the fastest symbolic manipulation library.
So far it can only do basic arithmetic, arbitrary size integer/rational
numbers, expansion, basic substitution and differentiation, basic implementation
of sin/cos. It's written in
C++ as a standalone library, with the goal of being usable from
multiple languages and environments. It has optional very thin Python
wrappers and conversion to/from SymPy. The license is MIT.

There are some synthetic benchmarks in the benchmarks directory,
you can run them against GiNaC, Sage and Mathematica. One has
to understand that these synthetic benchmarks don't necessarily show
that one software is faster than other, but it's some indicator.
On these benchmarks, CSymPy seems to be faster than GiNaC
(on some of them maybe by 50% or so). It seems faster than current Sage
(e.g. sometimes 7x or more). On some it is a bit faster than Mathematica,
but on some other ones not yet.

Another issue of course is to use specialized datastructures and
algorithms, for example for expansion of polynomials with integer
coefficients ---- Sage uses Singular for that, CSymPy currently my own
implementation of sparse polynomial multiplication (which does seem to
be a bit faster than Singular for one specific benchmark), see
benchmarks/expand2b* ---- but neither Sage nor Mathematica currently
use these specialized algorithms by default. And of course many times
you have symbolic exponents, so you can't use sparse polynomial representation.

There is high value in using just one language. For example, SymPy has
benefited greatly from only using Python (so that one does not have to worry
about multiple languages like C, Cython, ...). Similarly, CSymPy is only using
C++. In order to use it from Python, there are optional Cython wrappers:

https://github.com/certik/csympy/blob/master/csympy/lib/csympy_wrapper.pyx

as you can see, they are very thin and simple --- pretty much they just provide
a better, more natural syntax to the C++ library. I expect that later
people will
provide interfaces to other languages/environments as well (like Julia, Ruby,
Mathematica, ...).

Compared to Python, C++ is a complex language. However, it is currently the
only tool, that allows to have bare metal speed, yet reasonably high
level syntax.
For example, the implementation of expansion of things like (x+y+z+...)*(a+b+c)
is between these two lines (e.g. less than 30 lines):

https://github.com/certik/csympy/blob/5a4d1aabdb565b427ab8585d3737cb4901001e57/src/mul.cpp#L285
https://github.com/certik/csympy/blob/5a4d1aabdb565b427ab8585d3737cb4901001e57/src/mul.cpp#L313

you need to loop over the two parentheses, multiply things out and
construct the final
Add instance. In SymPy, the implementation starts here:

https://github.com/sympy/sympy/blob/8f56ea59ec4737b35166dd8fb799782664905709/sympy/core/mul.py#L691

it is implemented by the _expandsums() and _eval_expand_mul() methods.

Overall compared to Python, it is slower to implement things in C++,
but the speed is great, and one can tweak low level details like
memory allocators (essential for small objects like in CSymPy), have
automatic reference counted pointers, tweak hash functions and
hashmaps (dictionaries) implementation, implement your own high level
types/classes that are easy to use yet as fast as C, etc.

The idea is that if speed is not very important (most applications of
SymPy), then SymPy is the answer. However, if speed is important, for
things like handling long expressions (sympy.mechanics, quantum field
theory, various perturbation methods, ...), maybe some finite element
applications (that use symbolic mathematics on the fly) or having a
public server powered by sympy (depending on application), etc., then
it is essential to squeeze every bit of performance. Then CSymPy is
the answer.

I am now looking for people who suffer because SymPy is too slow, who
would be interested in collaboration. I've been in touch with the
sympy mechanics guys and I've also written to some of you to test it
out. And I know there are many more people. I am happy to concentrate
on implementing whatever needs to be done. Some things on my todo list
is to speedup the implementation of differentiation/substitution and
also implement fast pattern matching. But if somebody needs something
else, I'll be happy to work with you. At the moment, I don't plan to
implement the whole sympy, only things which people need to be as fast
as possible --- let me know.

If you discover any bugs, please report it to github issues at
https://github.com/certik/csympy.

Ondrej

[Matthew Rocklin]

Awesome.  I look forward to hearing more about it.  

What is your vision for SymPy/CSymPy interoperation?  

--
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 http://groups.google.com/group/sympy.
For more options, visit https://groups.google.com/groups/opt_out.

[Frédéric Bastien]

Hi,

Just to better understand the goal, is the goal to do the symbolic derivative faster, to have a faster execution of the final function? Both?

thanks

Fred

[Ondřej Čertík]

On Thu, Sep 19, 2013 at 6:54 AM, Frédéric Bastien <no...@nouiz.org> wrote:
> Hi,
>
> Just to better understand the goal, is the goal to do the symbolic
> derivative faster, to have a faster execution of the final function? Both?

Both.

Ondrej

[Ondřej Čertík]

On Tue, Sep 17, 2013 at 9:07 PM, Matthew Rocklin <mroc...@gmail.com> wrote:
> Awesome. I look forward to hearing more about it.
>
> What is your vision for SymPy/CSymPy interoperation?

For now it automatically converts between the two, see the tests:

https://github.com/certik/csympy/blob/master/csympy/tests/test_sympy_conv.py

it would be nice to figure out ways to plug such faster cores into
sympy somehow,
possibly using multiple dispatch or so. I am sure this can be done later,
if people find it useful.

Ondrej

[F. B.]

Nice work, I think that algorithms which have been stable for a long time and are extensively tested, can be rewritten in C++.

In fact the great advantage of Python is the ease of writing code quickly, writing algorithms in Python lets people focus more on the mathematical results. Unfortunately Python is slow :(

I would hesitate before porting the pattern matching to C++, as I believe that SymPy needs better pattern matching capabilities, and it's better to write them in Python first.

Are there any plans to use GPU or distributed computing in a C++ core?

[Ondřej Čertík]

On Thu, Sep 19, 2013 at 10:37 AM, F. B. <franz....@gmail.com> wrote:
> Nice work, I think that algorithms which have been stable for a long time
> and are extensively tested, can be rewritten in C++.

Exactly.

>
> In fact the great advantage of Python is the ease of writing code quickly,
> writing algorithms in Python lets people focus more on the mathematical
> results. Unfortunately Python is slow :(

Right.

>
> I would hesitate before porting the pattern matching to C++, as I believe
> that SymPy needs better pattern matching capabilities, and it's better to
> write them in Python first.

I agree, we need to figure out a good algorithm first.

>
> Are there any plans to use GPU or distributed computing in a C++ core?

I don't have experience with GPU, but I definitely plan at least using openmp,
so that one can take advantage of all the cores on a given computer.
For things like multiplying out two large expressions it should make
quite a difference.

Ondrej

[Joachim Durchholz]

Am 19.09.2013 20:56, schrieb Ondřej Čertík:
> On Thu, Sep 19, 2013 at 10:37 AM, F. B. <franz....@gmail.com> wrote:
>> Are there any plans to use GPU or distributed computing in a C++ core?
>
> I don't have experience with GPU,

I have some (very limited) experience.

GPUs have some restrictions:
- No string processing.
- No recursion.
- Tight per-core memory constraints.
- No API for debugging or logging in OpenGL. I don't know whether OpenCL
has it.

Some can be worked around.
E.g. there is an OpenGL debugger around. I don't know how they are doing
it - is suspect setting a breakpoint means parsing the program and
rewriting the breakpoint position to fill an int array with codes that
are mapped to strings on the CPU side, then stop execution.

[F. B.]

Any thought at CINT for C++ developing?

http://root.cern.ch/drupal/content/cint

This could help in order to avoid complications stemming from compilers. It was developed by physicists at CERN :)

[Ondřej Čertík]

As far as I know, it does not work with CSymPy. But otherwise I have
nothing against it.

Ondrej

[Stefan Krastanov]

I have heard a lot of bad opinions on CINT - that it covers only
partial ill-defined subset of the language standard. However I have
not tried it myself.

[Joachim Durchholz]

Am 20.09.2013 22:49, schrieb F. B.:
> Any thought at CINT for C++ developing?
>
> http://root.cern.ch/drupal/content/cint
>
> This could help in order to avoid complications stemming from compilers.

A C/C++ interpreter does not help with GPU debugging problems.

Current-day graphic cards accept shader code in the form of a C subset
with extensions (yes, they run a compiler whenever you send them new
code). There are subtle incompatibilities between the graphics cards -
not in the semantics themselves but in stuff like whether they
autoconvert constants between int and float.

An OpenCL emulator would probably be more useful.

> It was developed by physicists at CERN :)

Many physicists still love Fortran.
Being written by physicists, CERN or no, isn't necessarily a sign of
high software quality.

(Mosaic doesn't count. In fact I wouldn't vouch for the software quality
of Mosaic, what was important about it were the concepts.)

[Stefan Krastanov]

> Being written by physicists, CERN or no, isn't necessarily a sign of high software quality.

Actually, it is a pretty reliable sign of bad quality ;)

[Ondřej Čertík]

On Sat, Sep 21, 2013 at 6:18 AM, Joachim Durchholz <j...@durchholz.org> wrote:
> Am 20.09.2013 22:49, schrieb F. B.:

[...]

>> It was developed by physicists at CERN :)
>
> Many physicists still love Fortran.

Because it is still the best language for the job, as long as you do
numerics. I use Fortran every day and I love it.
I created these pages:

http://fortran90.org/

you can see that modern Fortran is as easy to use as Python/NumPy
(e.g. http://fortran90.org/src/rosetta.html), but very very fast.

But for symbolics that we do, C++ seems to be the best option. If in
few years maybe Julia or Numba becomes a viable alternative, we can
always call the C++ core from it, so the work is not lost.

On Sat, Sep 21, 2013 at 2:40 PM, Stefan Krastanov
<stefan.k...@yale.edu> wrote:
>> Being written by physicists, CERN or no, isn't necessarily a sign of high
>> software quality.
>

> Actually, it is a pretty reliable sign of bad quality ;)
>

I am a physicist. I've seen good and bad codes written by physicists,
I don't think it can be generalized.

Ondrej

[Thilina Rathnayake]

Congratulations Ondrej on your awesome work !!!!

I wanted to actively take part in it but I got stuck with the GSoC project

and my college work. I hope to engage more with this project in the future.

This is especially helpful when solving equations like Thue equations
because the speed is essential. For Most of the advanced number
theoretic / Algebraic number theoretic algorithms, the speed is crucial.
So that kind of work can clearly benefit from CSymPy.

Regards,

Thilina

[Ondřej Čertík]

Thilina,

On Mon, Sep 23, 2013 at 12:14 PM, Thilina Rathnayake
<thilin...@gmail.com> wrote:
> Congratulations Ondrej on your awesome work !!!!
>
> I wanted to actively take part in it but I got stuck with the GSoC project
> and my college work. I hope to engage more with this project in the future.
>
> This is especially helpful when solving equations like Thue equations
> because the speed is essential. For Most of the advanced number
> theoretic / Algebraic number theoretic algorithms, the speed is crucial.
> So that kind of work can clearly benefit from CSymPy.

Absolutely. If you'd like to contribute some of the algorithms that
you implemented
in SymPy, that would be awesome. I've been thinking about your work, as your
low level algorithms don't really require many advanced features, except
arbitrary integers, which we already have in CSymPy. I'll be happy to
help get you
started once you have some time, as it might be a little tedious at
first to figure
out how to do things in C++, but I have mostly figured that out
already for our purposes.

Ondrej

[Thilina Rathnayake]

Thank you for the reply Ondrej.

I will be more than happy to implement those algorithms in CSymPy
also. I have done a little bit of programming with C++, but I have not

worked with Teuchos.

I'll try to go through the code as I get time. I will contact you whenever
I run into trouble or get stuck in the process.

Regards,

Thilina.

Ondrej

[Ondřej Čertík]

On Mon, Sep 23, 2013 at 2:15 PM, Thilina Rathnayake
<thilin...@gmail.com> wrote:
> Thank you for the reply Ondrej.
>
> I will be more than happy to implement those algorithms in CSymPy
> also. I have done a little bit of programming with C++, but I have not
> worked with Teuchos.

Note that I don't use Teuchos anymore, but instead simply implemented
the necessary reference counted pointers myself, and they store the refcount
in the objects themselves for speed reasons:

https://github.com/certik/csympy/blob/master/src/csympy_rcp.h

syntax-wise they are 100% compatible with Teuchos though and I test on Travis
that CSymPy still compiles against Teuchos.

> I'll try to go through the code as I get time. I will contact you whenever
> I run into trouble or get stuck in the process.

Excellent, looking forward.

Ondrej

[Thilina Rathnayake]

Thanks for the update.

Regards,

Thilina

Ondrej

[Roberto Colistete Jr.]

Em 17-09-2013 19:09, Ondřej Čertík escreveu:
> Hi,
>
> I'd like to announce CSymPy:
>
> https://github.com/certik/csympy
>
> a fast symbolic manipulation library written in C++.
> The goal is to eventually be the fastest symbolic manipulation library.

> ...

> I am now looking for people who suffer because SymPy is too slow, who
> would be interested in collaboration.

Hi,

Another use of CSymPy would be in mobile OS because :
1) they have (compared to PC) more restrictions in CPU performance and
available RAM, so a pure C++ implementation can give a useful faster
loading and running times, as well as lower RAM usage;
2) Python is not a 1st class programming language for some mobile OS, see :
http://thp.io/2012/mobile-matrix/
so it may be easier to develop only in C++ using the default SDK than
trying to compile/package/embed Python/etc .

I would be interested in CSymPy with working "integrate", for example.

About mobile programming, Qt 5.0/5.1 is already being used in Android,
Mer/Nemo Mobile/Sailfish OS, Tizen and Ubuntu Touch. Qt 5.2 (to be
available in November 2013) will also be compatible with iOS.

Python for Qt5/Qt Quick 2 works with two recent releases, PyOtherSide :
https://github.com/thp/pyotherside
and PyQt5 :
http://www.riverbankcomputing.co.uk/news/pyqt-501
http://www.riverbankcomputing.co.uk/software/pyqt/download5

Regards,

Roberto

[Ondřej Čertík]

Hi Roberto,

On Fri, Sep 27, 2013 at 7:51 AM, Roberto Colistete Jr.
<roberto....@gmail.com> wrote:
> Em 17-09-2013 19:09, Ondřej Čertík escreveu:
>>
>> Hi,
>>
>> I'd like to announce CSymPy:
>>
>> https://github.com/certik/csympy
>>
>> a fast symbolic manipulation library written in C++.
>> The goal is to eventually be the fastest symbolic manipulation library.
>> ...
>> I am now looking for people who suffer because SymPy is too slow, who
>> would be interested in collaboration.
>
>
> Hi,
>
> Another use of CSymPy would be in mobile OS because :
> 1) they have (compared to PC) more restrictions in CPU performance and
> available RAM, so a pure C++ implementation can give a useful faster loading
> and running times, as well as lower RAM usage;
> 2) Python is not a 1st class programming language for some mobile OS, see :
> http://thp.io/2012/mobile-matrix/
> so it may be easier to develop only in C++ using the default SDK than trying
> to compile/package/embed Python/etc .

Indeed, I think so too, that C++ might be a better platform for
developing a reusable
library, that could be used on all these devices. In general, Python is not very
good at writing libraries, which you would like to use outside of
Python (it is of course
possible to call Python from C/C++ and I have done that in the past,
but there are
all kinds of issues with module loading/setting up paths, etc. and you
have to link
with the Python library of course).

>
> I would be interested in CSymPy with working "integrate", for example.

It would be cool. Though unfortunately integrate() happens to be the
most difficult part,
as it depends on many modules, so it will take some time. However, if
we choose to implement another version of
integrate based on pattern matching, then that might be possible sooner.

>
> About mobile programming, Qt 5.0/5.1 is already being used in Android,
> Mer/Nemo Mobile/Sailfish OS, Tizen and Ubuntu Touch. Qt 5.2 (to be available
> in November 2013) will also be compatible with iOS.
>
> Python for Qt5/Qt Quick 2 works with two recent releases, PyOtherSide :
> https://github.com/thp/pyotherside
> and PyQt5 :
> http://www.riverbankcomputing.co.uk/news/pyqt-501
> http://www.riverbankcomputing.co.uk/software/pyqt/download5

Ondrej

[Angus Griffith]

> I would be interested in CSymPy with working "integrate", for example.

It would be cool. Though unfortunately integrate() happens to be the
most difficult part,
as it depends on many modules, so it will take some time. However, if
we choose to implement another version of
integrate based on pattern matching, then that might be possible sooner.

A pattern matching based integrate would be awesome!

If we can get this pattern matching API sorted out we could translate the Rubi rules (either by hand or potentially using Mathics) to get a fast integrator that outperforms Mathemaitca.

[someone]

Hi,

> If we can get this pattern matching API sorted out we could translate

> the Rubi <http://www.apmaths.uwo.ca/~arich/> rules

Improving our pattern matching and reimplementing Rubi
on top of Sympy will be a GSOC project for next year.
(I wanted to make the proposal already for this time
but never did it.)

This does not mean someone could do this also outside
of the GSOC frame.

> to get a fast integrator that outperforms Mathemaitca.

While it might be faster, this is not sure. (Python vs
C in MMA etc)

For the integrals it can do it will be fine, but in
no way it will ever replace the full Risch Code
because there will always be integrals which are solvable
but not in the pattern table.

Rubi in sympy would be fine to "patch" cases where
Risch is (not yet) implemented or which fall outside
any algorithmic code in sympy (risch, heurisch, meijerg, ...)

[Ondřej Čertík]

On Sun, Sep 29, 2013 at 4:15 AM, someone <some...@bluewin.ch> wrote:
> Hi,
>
>> If we can get this pattern matching API sorted out we could translate
>> the Rubi <http://www.apmaths.uwo.ca/~arich/> rules
>
> Improving our pattern matching and reimplementing Rubi
> on top of Sympy will be a GSOC project for next year.
> (I wanted to make the proposal already for this time
> but never did it.)
>
> This does not mean someone could do this also outside
> of the GSOC frame.
>
>> to get a fast integrator that outperforms Mathemaitca.
>
> While it might be faster, this is not sure. (Python vs
> C in MMA etc)

CSymPy is written in C++, so my goal is for the pattern matching to
be as fast as in Mathematica.

>
> For the integrals it can do it will be fine, but in
> no way it will ever replace the full Risch Code
> because there will always be integrals which are solvable
> but not in the pattern table.
>
> Rubi in sympy would be fine to "patch" cases where
> Risch is (not yet) implemented or which fall outside
> any algorithmic code in sympy (risch, heurisch, meijerg, ...)

Yes, I think it will be one more algorithm to perform integration,
that users can use.

Ondrej

[F. B.]

Python is normally easier to write code than C++, but I think there is a main exception, i.e. cases of complex class-structure. In C++ there is the possibility of using IDEs with autocompletion enabled, which can any time tell you which type a variable is, a great advantage of statically typed languages. I tried for some time PyDev plugin in Eclipse, but it is not comparable to C++ development, static methods are correctly guessed, but in the case of class instances it is very poor.

By the way, I feel that complex class-objects should be in any case rewritten to C++, for this very reason.

Regarding the Rubi ruleset, I think that a pattern matching improvement and rewriting in C++ would be needed, but one has also to improve the assumptions module in order to be able to perform the same checks as in Mathematica, besides the checks are to be inserted inside the pattern matching algorithm.

It would be very nice to find an equivalent ruleset as Rubi for differential equations, if there are any.

[Ondřej Čertík]

On Mon, Sep 30, 2013 at 11:03 AM, F. B. <franz....@gmail.com> wrote:
> Python is normally easier to write code than C++, but I think there is a
> main exception, i.e. cases of complex class-structure. In C++ there is the
> possibility of using IDEs with autocompletion enabled, which can any time
> tell you which type a variable is, a great advantage of statically typed
> languages. I tried for some time PyDev plugin in Eclipse, but it is not
> comparable to C++ development, static methods are correctly guessed, but in
> the case of class instances it is very poor.
>
> By the way, I feel that complex class-objects should be in any case
> rewritten to C++, for this very reason.

Yes, Python doesn't have types at compile time,
only at runtime. Which has advantages for easy prototyping etc., but based on my
experience, if I want to understand other people's code, it really helps to know
the types that go into methods/functions. As a side effect, also powerful
IDEs can be built around it, as you mentioned. Also, you don't need to
write tests just to check syntax like we have to do in SymPy, because
the compiler checks it for you.

The only problem with C++ that I have is that it takes forever (for me) to write
something in it (compared to Python) and it is a complex language overall.
But I am convinced that it is worthy for symbolic manipulation library.

> Regarding the Rubi ruleset, I think that a pattern matching improvement and
> rewriting in C++ would be needed, but one has also to improve the
> assumptions module in order to be able to perform the same checks as in
> Mathematica, besides the checks are to be inserted inside the pattern
> matching algorithm.

Exactly. CSymPy currently has no assumptions, so those would need to be added.

Based on my discussions so far, I think this should be what I should work on
next in CSymPy --- fast pattern matching and assumptions.

> It would be very nice to find an equivalent ruleset as Rubi for differential
> equations, if there are any.

Ondrej

[Aaron Meurer]

On Mon, Sep 30, 2013 at 11:03 AM, F. B. <franz....@gmail.com> wrote:

> Python is normally easier to write code than C++, but I think there is a
> main exception, i.e. cases of complex class-structure. In C++ there is the
> possibility of using IDEs with autocompletion enabled, which can any time
> tell you which type a variable is, a great advantage of statically typed
> languages. I tried for some time PyDev plugin in Eclipse, but it is not
> comparable to C++ development, static methods are correctly guessed, but in
> the case of class instances it is very poor.

The Jedi completion library for Python is pretty good. In the end,
it's all heuristics because Python is dynamic, but it is pretty good
in my experience. There are plugins for it for the most common
editors, including emacs, vim, and sublime.

>
> By the way, I feel that complex class-objects should be in any case
> rewritten to C++, for this very reason.
>
> Regarding the Rubi ruleset, I think that a pattern matching improvement and
> rewriting in C++ would be needed, but one has also to improve the
> assumptions module in order to be able to perform the same checks as in
> Mathematica, besides the checks are to be inserted inside the pattern
> matching algorithm.
>
> It would be very nice to find an equivalent ruleset as Rubi for differential
> equations, if there are any.

The ODE module basically does work on pattern matching. In fact,
classify_ode is probably the biggest user of pattern matching in SymPy
library code, and it covers quite a few cases that simply cannot be
handled by the current matcher.

One problem I've noticed (I'm the main author of classify_ode and most
of the ODE module, except for the new stuff from this summer) is that
pattern matching basically has to go in two steps: first, you have to
canonicalize the expression, and second you have to match it. That's
because something like a*x**2 + b*x + c will technically match (x -
2)*(x - 1) or x*(x - 1) + y*x, but the pattern matcher won't notice
that unless the expression is first expanded and then collected in x.
For this case, it's easy, but for more complicated expressions, you
have to basically write custom simplification routines. For instance,
say you wanted to match A*exp(B*x**2 + C*x + D) + E, where A, B, C, D,
and E are wild expressions not depending on x. y*exp(x)*E + exp(x*(x +
1)) + 7 matches this. To match this, you have to factor out all
exponentials, combine them, then expand the argument of the
exponential. It would be great if there were a layer on top of the
basic structural pattern matcher that currently exists that is aware
of what sorts of simplifications need to be done on certain types of
expressions in order to maximize mathematically matches.

It would also be nice if it were easier to generate patterns like
Sum(a_i*diff(f(x), x, i), (i, 0, n)) where n is a fixed number (not a
symbol), but not known ahead of time.

Aaron Meurer

[someone]

Hi,

> CSymPy is written in C++, so my goal is for the pattern matching to
> be as fast as in Mathematica.

Oh, maybe my formulation was misleading and confused two things.

First is python vs C++ or any interpreted vs compiled language.
I don't want to start another discussion on pros and cons here.

The other thing is that the Risch algorithm is very complex, having
a recursive nature and many computationally intensive steps.

Searching a (well organized!) table of rules might be faster
in most cases. It depends strongly on how we search and match.

[Matthew Rocklin]

Sophisticated algorithms for pattern matching against a large collection of potentially associative-commutative terms can be both very involved/challenging and also be vastly more efficient than naive algorithms.

Optimization on this problem over algorithms is more effective than optimization over language-implementations and as such the performance advantages of C++ over Python are negligible.

[F. B.]

On Monday, September 30, 2013 9:21:44 PM UTC+2, Matthew wrote:

Sophisticated algorithms for pattern matching against a large collection of potentially associative-commutative terms can be both very involved/challenging and also be vastly more efficient than naive algorithms.

Optimization on this problem over algorithms is more effective than optimization over language-implementations and as such the performance advantages of C++ over Python are negligible.

I agree. I believe we should focus on improving the pattern matching in Python first, I would leave the translation to C++ to a distant future.

By the way, what about trying to force static typing in sympy's core through the usage of decorators? Or maybe even try to define a standard to write Python code in order to make it easy to translate it to C++ through code generators? I am fascinated by the idea of sympy being written in C/C++, but I am also very skeptical about the time needed for a translation by hand.

[Jason Moore]

"Or maybe even try to define a standard to write Python code in order to make it easy to translate it to C++ through code generators?"

Doesn't Cython already do this?

Jason
moorepants.info
+01 530-601-9791

--

[F. B.]

On Tuesday, October 1, 2013 12:07:07 AM UTC+2, Jason Moore wrote:

"Or maybe even try to define a standard to write Python code in order to make it easy to translate it to C++ through code generators?"

Doesn't Cython already do this?

In cython, if you don't use cdef, all variables are translated into PyObject pointers, which is practically the same as dynamic typing. Therefore a naive usage of cython would not give any speed improvement.

On the other hand, using cdef breaks compatibility with standard Python, and code becomes Cython-only.

In order to achieve high performance types have to be static, so maybe a solution for a C++ version of SymPy would be to add a dictionary of remapping of the variable types, for example:

@is_cpp_translatable
class SomeClass(Basic):
    @staticvars({'a': 'int', 'b': 'int', 'c': 'double'})
    def simple_method(a, b):
        c = a // 2 + b // 3
        return c

which would give

class SomeClass : public Basic {
    public:
        double simple_method(int a, int b) {
            double c = ((double)a)/2 + ((double)b)/2;
            return c;
        }
}

[F. B.]

@is_cpp_translatable
class SomeClass(Basic):
    @staticvars({'a': 'int', 'b': 'int', 'c': 'double'})
    def simple_method(a, b):
        c = a // 2 + b // 3
        return c

Such decorators could undergo a first phase of testing, i.e. checking during the execution of the tests that those variables are indeed of the type declared in the dict.

After successful testing of the staticity of internal variables, one could use some existing Python to C++ translators combined with the dict in order to generate C++ code.

This solution would have the advantage that coding is required only once, in Python with some precautions. C++ code would be always up to date with any edits in the Python code.

I know that numba has a similar approach using decorators, except that it compiles the code just-in-time, which is a bit different. I don't know if there is any existing project applying something like a decorator-based translator.

[Joachim Durchholz]

Am 30.09.2013 23:07, schrieb F. B.:
>
> By the way, what about trying to force static typing in sympy's core
> through the usage of decorators?

Can any IDE make use of that?

> Or maybe even try to define a standard to
> write Python code in order to make it easy to translate it to C++ through
> code generators? I am fascinated by the idea of sympy being written in
> C/C++, but I am also very skeptical about the time needed for a translation
> by hand.

One of the problems in Sympy is that it's making quite liberal use of
Python's ability to add class members long after the classes are declared.
The C and S classes are examples of this, and probably the most
significant ones in the Sympy codebase. I've been working on eliminating
C for a quite a while, and it's so pervasive and sometimes interwoven
with other parts of Pyhon that I sometimes found it hard to make any
progress at all; an automatic translation would probably have face more
problems.

So to prepare for translation to C++, I guess the whole codebase would
need to be de-dynamized quite a bit.
This would probably also make the various code analysis plugin more
reliable.

[Matthew Rocklin]

I like Joachim's suggestion of de-dynamizing the codebase.  I suspect it would help not only with future attempts at translation, but also with Cython or PyPy ports.  It would probably even help the pure Python implementation (which remains my top priority) and encourage growth.

Efforts to remove magic without reducing performance would probably have significant positive impact both in increasing portability to other languages and also in supporting growth within the existing codebase.

--
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+unsubscribe@googlegroups.com.

[Matthew Rocklin]

In short, I'm trying to find a way to direct the ideas and enthusiasm generated in this thread back onto the core before launching off in experimental directions.

[Ronan Lamy]

Le 01/10/13 01:30, Matthew Rocklin a �crit :

> I like Joachim's suggestion of de-dynamizing the codebase. I suspect it
> would help not only with future attempts at translation, but also with
> Cython or PyPy ports. It would probably even help the pure Python
> implementation (which remains my top priority) and encourage growth.

There's no need to "port to PyPy", because it already works (PyPy is a a
fully compliant Python interpreter). However, limiting the amount of
run-time magic and not caching every bloody thing would probably help
its performance a lot.

>
> Efforts to remove magic without reducing performance would probably have
> significant positive impact both in increasing portability to other
> languages and also in supporting growth within the existing codebase.
>

I agree. Besides, optimising for PyPy offers the best ratio of
performance improvement vs coding effort by far, IMHO.

[Ondřej Čertík]

Btw, I think some machine translation would probably not bring much speedup.
My view of CSymPy is more like a complement to SymPy, where we can
hand optimize well understood algorithms to pretty much bare metal speed.

Ondrej

[F. B.]

I believe that once static typing has been forced on the Python code, high optimization will come out naturally after transition to C++.

The main problem of Python is that.

Translation could occur only once in the future, as soon as the Python code is deemed mature and stable. After that development would continue in C++.

Otherwise an alternative could be to write the sympy core entirely in cython, so there is an option to use both Python expressions and statically typed variables.

[Aaron Meurer]

Speed generally isn't an issue with the Risch algorithm, at least way
what's implemented so far (the algebraic case may be different). The
exceptions are when it has to do a large expansion, especially when
the answer could be computed without doing so (like integrate((exp(x)
+ 1)**1000*exp(x), x)), or in some integrals whose answers contain
logarithms the resultant calculation can be slow (the former is
perfect for pattern matching algorithms but in the latter case I don't
hold out much hope for anything other than the full algorithm to find
the right logarithms).

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.

[Aaron Meurer]

Also numba targets llvm, which is really much smarter for what it is trying to do, and it focuses mainly on numeric code that uses NumPy arrays. I know there has been some work in trying to make numba more modular, though. Maybe in the future, it would be possible to write a more OO backend to it, or at the very least, teach it how to work with tree-like data structures.  

Aaron Meurer

[Aaron Meurer]

On Sep 30, 2013, at 6:16 PM, Joachim Durchholz <j...@durchholz.org> wrote:
>
> Am 30.09.2013 23:07, schrieb F. B.:
>>
>> By the way, what about trying to force static typing in sympy's core
>> through the usage of decorators?
>
> Can any IDE make use of that?
>
> > Or maybe even try to define a standard to
>> write Python code in order to make it easy to translate it to C++ through
>> code generators? I am fascinated by the idea of sympy being written in
>> C/C++, but I am also very skeptical about the time needed for a translation
>> by hand.
>
> One of the problems in Sympy is that it's making quite liberal use of Python's ability to add class members long after the classes are declared.

I guess you mean just for the metaclasses. C, S, and the assumptions
metaclasses are the primary metaclasses, and the first and third we
would like to remove. To translate S, you would just need to switch
over to whatever kind of singletonization is possible in C++. The
actual classes in SymPy are immutable and really shouldn't be changing
after being constructed.

Aaron Meurer

> The C and S classes are examples of this, and probably the most significant ones in the Sympy codebase. I've been working on eliminating C for a quite a while, and it's so pervasive and sometimes interwoven with other parts of Pyhon that I sometimes found it hard to make any progress at all; an automatic translation would probably have face more problems.
>
> So to prepare for translation to C++, I guess the whole codebase would need to be de-dynamized quite a bit.
> This would probably also make the various code analysis plugin more reliable.
>

[F. B.]

Anyone ever heard of Nuitka? I discovered this project today, and it looks very promising.

It's a compiler for Python, which basically translates Python to C++ and then compiles it to machine code. It could be used for translating purposes as well.

Unlike other things like that, such as PyPy, Cython, ShedSkin, they aim to be 100% compatible with CPython syntax. Nuitka does not create its own implementation of the Python language, rather it uses the ast package. of CPython to parse code, which could be a strong point to keep compatibility.

In Nuitka's TODO list there is an interesting feature: static typing through decorators, which unlike Cython's cdef, do not break CPython compatibility. Unfortunately it's not yet implemented, but once it will be, I think the best solution to speed up SymPy would be to clean up Python's code and put static-variable-decorators. As of now, Python variables are still translated as PyObject pointers, which shouldn't have great benefits in term of speed.

In any case, Nuitka could also be used as a starting translation towards a C++ implementation of SymPy, or keep development in Python and use it to generate C++ code.

[Joachim Durchholz]

Am 01.10.2013 19:52, schrieb F. B.:
> Unlike other things like that, such as PyPy, Cython, ShedSkin, they aim to
> be 100% compatible with CPython syntax. Nuitka does not create its own
> implementation of the Python language, rather it uses the ast package. of
> CPython to parse code, which could be a strong point to keep compatibility.

That's a good thing, though they'd still have to upgrade the system with
each new Python version, so it's not buying the project THAT much.

But yes it makes sure that no deviations creep into the parsing, which
is good.

> In Nuitka's TODO list there is an interesting feature: static typing

> through decorators, which unlike Cython's *cdef*, do not break CPython

> compatibility. Unfortunately it's not yet implemented, but once it will be,
> I think the best solution to speed up SymPy would be to clean up Python's
> code and put static-variable-decorators. As of now, Python variables are
> still translated as PyObject pointers, which shouldn't have great benefits
> in term of speed.

The main question, then, is: Is Nuitka viable?
I.e. is it going to stay around as long as Sympy will? How fast do they
fix showstopper bugs? Are type decorators and (hopefully) something
smart for the data representation going to be implemented within our
lifetimes?

Alternatively, we could do our own Python-to-C++ translator. This would
be easier than a full-fledged translator because we'd have to cover only
those constructs that are actually used in Sympy, so we could take
considerable shortcuts (at the cost of needing a list of coding
restrictions, so this option would still come with attached strings).

[F. B.]

On Tuesday, October 1, 2013 8:15:21 PM UTC+2, Joachim Durchholz wrote:

That's a good thing, though they'd still have to upgrade the system with
each new Python version, so it's not buying the project THAT much.

Well, that's partially true. Compared to PyPy, Jython, IronPython and Cython, I think that work in Nuitka is minimal, as the language interpreter is Python's own ast library. The other alternative interpreters often reimplement again the whole of Python's language.

But yes it makes sure that no deviations creep into the parsing, which
is good.

PyPy's problem is that not all of Python's code is compatible, and the same is true for Jython and IronPython. Cython instead should be able (I think) to compile almost all of Python, but if you want to use static typing, you need to use cdef, which breaks compatibility with CPython.

In a few words, PyPy restricts the Python standard language, Cython extends it.

Nuitka is very interesting because it neither restricts nor extends the Python language. Besides, they plan to add static typing upon translation to C++ without breaking compatibility (it is suggested to use decorators).

Here are some considerations by Nuitka's developers:

http://nuitka.net/posts/static-compilation-that-is-the-point.html

 

The main question, then, is: Is Nuitka viable?
I.e. is it going to stay around as long as Sympy will? How fast do they
fix showstopper bugs? Are type decorators and (hopefully) something
smart for the data representation going to be implemented within our
lifetimes?

Nuitka is relatively young as a project (I suppose around 2 years old), and it is already able to compile almost every python library (at least so they claim).

Their first aim was to achieve an almost 100% compatibility with CPython, after that, their second step will focus on performance. As far as I know, they have just finished the compatibility part. Let's see what is coming out of it in the future. It looks like a great replacement for both PyPy and Cython. 

Alternatively, we could do our own Python-to-C++ translator. This would
be easier than a full-fledged translator because we'd have to cover only
those constructs that are actually used in Sympy, so we could take
considerable shortcuts (at the cost of needing a list of coding
restrictions, so this option would still come with attached strings).

That would be a lot of work. In any case, regarding a possible construction of our own translator, I would suggest to use Nuitka still, then compile its C++ result to XML using gccxml, applying transformation rules to the XML-equivalent C++ code, and then transforming back to C++.

XML has a lot of parsers, tree walkers, interpreters. C++ instead is hard to edit as it is.

[Stefan Krastanov]

@Franz, while I do not have an opinion on what is discussed here, I would like to correct an error that was repeated a few times: The Pypy interpreter for Python2.7 does *not* restrict what you can do - it is a *fully* compliant python interpreter.

You are probably thinking about the RPython language, which indeed is a part of the Pypy project and it is a very restricted subset of Python2. But RPython is *not* meant for use outside of writing the interpreter itself.

--

[Joachim Durchholz]

Am 01.10.2013 23:19, schrieb F. B.:
> In any case, regarding a possible construction
> of our own translator, I would suggest to use Nuitka still, then compile

> its C++ result to XML using *gccxml*, applying transformation rules to the

> XML-equivalent C++ code, and then transforming back to C++.

That would give us Python -> AST -> C++ -> XML -> XML transformation -> C++.
Sounds horribly indirect and fragile to me.

I'd do the transformations at the Python AST level.
1) Probably no more complicated than what's available for XML
2) No C++ knowledge required to hack on the transforms (to know what
kind of transforms are valid in C++ and what aren't), Python knowledge
is sufficient
3) No XML knowledge required to hack on the transforms (to know how to
implement a transform), Python knowledge is sufficient

So we get Python -> AST -> AST transform -> C++.
We could even do Python -> AST -> execution. It's not very nice (very
debugging-unfriendly because you don't have line numbers corresponding
to the actual sources in stack traces and error outputs), but it's
shortcutting the C++ -> XML -> C++ detour.

Plus, XML sucks anyway ;-P
(for example, you can't directly encode circular references in it, you
need DTD-dependent hacks for that)

[Björn Dahlgren]

On Tuesday, 1 October 2013 18:52:18 UTC+1, F. B. wrote:

Anyone ever heard of Nuitka? I discovered this project today, and it looks very promising.

I've played around with Cython, Nuitka, shedskin etc. I would not recommend Nuitka (see Stefan Behnels blog post on the topic) - furthermore: it produces huge binaries.

Based on what I've read lately mypy might be the silver bullet but it's quite new and I haven't found
the time to play around with it yet.
 

On the note of  de dynamizing the code base it might be worth looking into param:
https://github.com/ioam/param
http://pyvideo.org/video/1230/param-declarative-programming-using-parameters

I've also played around automatic (cython) code generation of decorated classes
https://gist.github.com/bjodah/6790854
(requires Py3, cython & mako) but it got cumbersome so I didn't go any further.

[F. B.]

On Tuesday, October 1, 2013 11:39:36 PM UTC+2, Stefan Krastanov wrote:

@Franz, while I do not have an opinion on what is discussed here, I would like to correct an error that was repeated a few times: The Pypy interpreter for Python2.7 does *not* restrict what you can do - it is a *fully* compliant python interpreter.

You are probably thinking about the RPython language, which indeed is a part of the Pypy project and it is a very restricted subset of Python2. But RPython is *not* meant for use outside of writing the interpreter itself.

PyPy has an issue about not being able to run numpy. The set of CPython-compatible libraries contains non-PyPy-compliant ones.

[F. B.]

On Wednesday, October 2, 2013 10:53:10 AM UTC+2, Björn Dahlgren wrote:

I've played around with Cython, Nuitka, shedskin etc. I would not recommend Nuitka (see Stefan Behnels blog post on the topic) - furthermore: it produces huge binaries.

 

Maybe you're right, but I would keep an eye on these projects.

 

Based on what I've read lately mypy might be the silver bullet but it's quite new and I haven't found
the time to play around with it yet.

That uses annotators, it would break compatibility with Python 2.

 

On the note of  de dynamizing the code base it might be worth looking into param:
https://github.com/ioam/param
http://pyvideo.org/video/1230/param-declarative-programming-using-parameters

Sounds good, but that could be used simply to keep the code clean.

 

I've also played around automatic (cython) code generation of decorated classes
https://gist.github.com/bjodah/6790854
(requires Py3, cython & mako) but it got cumbersome so I didn't go any further.

Indeed, you're right, translating Python to Cython is much easier than translating Python to C/C++, in fact Cython could work even if no translation takes place at all.

Maybe that could be a candidate proposal as valid alternative to CSymPy.

One could write a decorator to add both signature of parameters, and types of internal variables inside the function. Maybe then add a test in sympy's utilities to check that all local variables inside the function are signed, and write a tool similar to the previous 2to3, maybe sympy2cython, to create a cython optimized code.

What about this? It is far easier than writing CSymPy in C++ by hand, or trying translation into C++. 

[Ondřej Čertík]

The problem with Cython is that I am not able to make it as fast as
CSymPy in C++,
and I tried:

https://github.com/certik/sympyx/blob/master/sympy_pyx.pyx

The reason is that to truly nail the speed, one needs to use special
dictionary implementation,
tweak hashing functions, reference counting, memory allocators etc.
C++ allows to play with all that, while
having a reasonably high level syntax. In Cython one has to use Python
types like hashes/dicts ---- or resort
to effectively writing a pure C code --- either way, it becomes
overall more complex than just writing
things in C++ by hand. So I'll be happy to be proven wrong, but so far
C++ is a clear winner in terms of speed.

Besides speed, I came to appreciate having just one language and write
everything in it. Much simpler to maintain
and master. With your sympy2cython approach, you need to master
Python, SymPy code, the sympy2cython
tool, Cython, C and Python C/API intricacies. That's a lot of layers.
The reason to do this is speed, otherwise
we can just use SymPy --- but to nail speed, you need to master all
these layers extremely well, and it might
still not be enough --- i.e. I think I know Cython and Python C/API
reasonably well, but I don't know how to
make the Cython code above as fast as CSymPy. In C++, on the other
hand, you can really nail the speed and it is
just one language to master and maintain.

Ondrej

[F. B.]

OK, maybe for speed purposes C++ handwriting remains the best solution and automated translators/code generators are not that good.

What about still trying to force static typing inside selected parts of SymPy? I mean, once static typing is enforced, it should become easier to translate Python to C++ by hand, because one is not obliged to heavily alter the algorithm in case of variables of ambiguous type.

[Joachim Durchholz]

Am 02.10.2013 20:26, schrieb Ondřej Čertík:
> The reason is that to truly nail the speed, one needs to use special
> dictionary implementation,
> tweak hashing functions, reference counting, memory allocators etc.

Reference counting can improve latency, but it will actually decrease
throughput.

At best, RC in C++ is faster than what Python does (which has a very
crappy garbage collector).
A good GC, such as what's available in Java, can beat any RC
implementation hands down. Mostly because malloc() and free() do MUCH
more work than most people think; it's not unheard of that
allocation-intensive programs (and Sympy would certainly qualify) spend
20% of their time in memory management, and a mark-and-sweep collector,
even a simplicistic one, simply has a much better throughput.

> Besides speed, I came to appreciate having just one language and write
> everything in it. Much simpler to maintain
> and master.

Well sure, but that would be a case for setting up an entirely new
SymC++ project, wouldn't it?

> With your sympy2cython approach, you need to master
> Python, SymPy code, the sympy2cython
> tool, Cython, C and Python C/API intricacies. That's a lot of layers.

Fully agreed that that would become a serious problem over time.
Also, it would deter contributors that don't know all these layers.

[Ondřej Čertík]

On Wed, Oct 2, 2013 at 1:47 PM, Joachim Durchholz <j...@durchholz.org> wrote:
> Am 02.10.2013 20:26, schrieb Ondřej Čertík:
>
>> The reason is that to truly nail the speed, one needs to use special
>> dictionary implementation,
>> tweak hashing functions, reference counting, memory allocators etc.
>
>
> Reference counting can improve latency, but it will actually decrease
> throughput.
>
> At best, RC in C++ is faster than what Python does (which has a very crappy
> garbage collector).
> A good GC, such as what's available in Java, can beat any RC implementation
> hands down. Mostly because malloc() and free() do MUCH more work than most
> people think; it's not unheard of that allocation-intensive programs (and
> Sympy would certainly qualify) spend 20% of their time in memory management,
> and a mark-and-sweep collector, even a simplicistic one, simply has a much
> better throughput.

Yes, I have found that malloc, resp. the default new/delete operators
in C++ can be sped-up
by 10% or 20% by using custom allocators. I have tried

http://warp.povusers.org/FSBAllocator/

see my implementation here:

https://github.com/certik/csympy/compare/master...alloc_fsb

and also tried

http://goog-perftools.sourceforge.net/doc/tcmalloc.html

both of which provide good speedup. At the moment I use neither, because
the FSBAllocator does not work for std::unordered_map. Ultimately the
best approach
seems to allocate a pool of memory and then do our own memory
allocation along the lines
of FSBAllocator and in-place new(). (C++ allows to implement all this,
while this is very hard
in Cython.)

As to garbage collection approach, I should try it as well. Though
what I read it might
not beat the above approach.

>
>
>> Besides speed, I came to appreciate having just one language and write
>> everything in it. Much simpler to maintain
>> and master.
>
>
> Well sure, but that would be a case for setting up an entirely new SymC++
> project, wouldn't it?

Right.

The only way to maintain single code base to run both in pure Python and
compiled in C/C++ for speed that I know of is to use pure Python mode
in Cython or some kind
of translation as we discussed. But I don't know how to effectively
nail the speed
with either of these approaches, as discussed.

So the other simplest obvious approach is to stick to pure C++. But by having
thin Python wrappers, one can use it complementary together with SymPy,
and we might be able to incorporate such optional libraries in SymPy
more tightly
in the future by using some double dispatch or such.

>
>
>> With your sympy2cython approach, you need to master
>>
>> Python, SymPy code, the sympy2cython
>> tool, Cython, C and Python C/API intricacies. That's a lot of layers.
>
>
> Fully agreed that that would become a serious problem over time.
> Also, it would deter contributors that don't know all these layers.

Exactly. C++, while complex, is still a very very popular language with
quite a lot of people able to contribute.

Ondrej

[Ondřej Čertík]

I think once we stop supporting Python 2.7, we can start using static typing
quite easily and I think it helps.

Though I think one of the most useful algorithms in SymPy that are
candidates for C++ rewrite
are polynomials, and those as far as I know don't use much duck typing, so
it should be fairly easy to rewrite using fast native C++ datastructures.
For example, here is my implementation of sparse polynomial multiplication
in C++:

https://github.com/certik/csympy/blob/master/src/rings.cpp#L63
https://github.com/certik/csympy/blob/master/src/monomials.cpp#L7

and I think it might be possible to speed it up further by playing
with the hashtable
and hashes and similar things. I tried to optimize a hash function for
this case already,
see here:

https://github.com/certik/csympy/blob/master/src/dict.h#L48

the idea is that the hash function needs to be fast to compute for the
tuple of ints and
also as unique as possible.



Btw, I don't want to discourage you from trying things. I only wanted
to share my own
(hard-earned) experience, as I tried various approaches. For example,
one great project
would be to implement similar symbolic core in Julia. It might get
competitive or even
faster than my Cython version above. Whether it could match my C++ version,
that I don't know.


Ondrej

[Joachim Durchholz]

Am 02.10.2013 23:48, schrieb Ondřej Čertík:
> On Wed, Oct 2, 2013 at 1:47 PM, Joachim Durchholz <j...@durchholz.org> wrote:
>> Am 02.10.2013 20:26, schrieb Ondřej Čertík:
>>
>>> The reason is that to truly nail the speed, one needs to use special
>>> dictionary implementation,
>>> tweak hashing functions, reference counting, memory allocators etc.
>>
>>
>> Reference counting can improve latency, but it will actually decrease
>> throughput.
>>
>> At best, RC in C++ is faster than what Python does (which has a very crappy
>> garbage collector).
>> A good GC, such as what's available in Java, can beat any RC implementation
>> hands down. Mostly because malloc() and free() do MUCH more work than most
>> people think; it's not unheard of that allocation-intensive programs (and
>> Sympy would certainly qualify) spend 20% of their time in memory management,
>> and a mark-and-sweep collector, even a simplicistic one, simply has a much
>> better throughput.
>
> Yes, I have found that malloc, resp. the default new/delete operators
> in C++ can be sped-up
> by 10% or 20% by using custom allocators.

Try the Boehm-Demers-Weiser collector and see what that brings.
Use really long-running tasks to benchmark it, it has a relatively high
fixed space overhead.

Note that the BDW collector is a lot less efficient than it could be,
because it takes great pains to avoid depending on compiler and language
support. In particular, it cannot be a copying collector because C and
C++ simply cannot work if objects are moved around, and copying would be
essential to combat heap fragmentation (which is a real issue if you
have a task that runs for more than a few hours).

I'd suggest trying out Java, which has a top-tier GC. Java does have
some performance issues related to run-time class loading and the
presence of introspection facilities, so it might not shine until the GC
really starts to become relevant.

>>> Besides speed, I came to appreciate having just one language and write
>>> everything in it. Much simpler to maintain
>>> and master.
>>
>> Well sure, but that would be a case for setting up an entirely new SymC++
>> project, wouldn't it?
>
> Right.
>
> The only way to maintain single code base to run both in pure Python and
> compiled in C/C++ for speed that I know of is to use pure Python mode
> in Cython or some kind
> of translation as we discussed. But I don't know how to effectively
> nail the speed
> with either of these approaches, as discussed.
>
> So the other simplest obvious approach is to stick to pure C++. But by having
> thin Python wrappers, one can use it complementary together with SymPy,
> and we might be able to incorporate such optional libraries in SymPy
> more tightly
> in the future by using some double dispatch or such.

With Python wrappers, you still can't recruit contributors from the user
base.
You'll end with less contributions. Also, algorithmic optimization is
somewhat harder in C++ than in more abstract languages, so you'll want
to keep Python as a testbed even for the stuff you're eventually
implementing in C++; you'll still end with a mixed-language development.
I'm reading you that you think that C++ is common, and while that's
true, contributors still need to know both languages if the ability to
translate Python to C++ is desired, because that will impose design
constraints even on the Python code structure.

I'm rather sceptical even of mixing in just C++. I'm not convinced that
the linear improvements of C++, however good they may be, can beat the
(allegedly) faster development speed and algorithmic improvements of
Python. Garbage management is a real issue in C++. You can't use Sympy
in Jython if parts of it are coded up in C++. You have a higher barrier
for turning users into contributors.
That's quite a long list of what-ifs and annoying entanglements, and you
can expect a few of them to actually bite; I'm not sure that the net
result will be worth the effort. Then, of course, whether it's worth it
is a value judgement that you might answer differently than me, so by
all means make your own decisions :-) (I guess I'm playing Devil's
Advocate here, enumerating all the counterarguments, just so that they
are considered, not really to shoot the project down)

[Stefan Krastanov]

Indeed, but that is quite a different problem and it does not concern sympy (which is pure-python + optional dependencies on PyPy supported non-pure-python libraries).

Concerning numpy: pypy already has a numpy implementation that covers more than what sympy uses. Moreover PyPy provides a high performance C-api that also works in CPython. Finally, even these libraries which (due to the use of the CPython C-api) do not work directly under pypy can be used in pypy with a (very hackish) embedding of the CPython interpreter.

[Ondřej Čertík]

I'll give it a shot, thanks for the tip. If nothing, it would be good to know
the performance of GC compared to reference counting.

>
> Note that the BDW collector is a lot less efficient than it could be,
> because it takes great pains to avoid depending on compiler and language
> support. In particular, it cannot be a copying collector because C and C++
> simply cannot work if objects are moved around, and copying would be
> essential to combat heap fragmentation (which is a real issue if you have a
> task that runs for more than a few hours).
>
> I'd suggest trying out Java, which has a top-tier GC. Java does have some
> performance issues related to run-time class loading and the presence of
> introspection facilities, so it might not shine until the GC really starts
> to become relevant.

I doubt you can beat CSymPy with Java, but I'll be happy to be proven wrong.

In my experience, one has to write a clean algorithm in C++ by hand, so
the only thing that matters is the algorithm itself. In many cases, we
already have a pretty good idea how to implement things in SymPy.
Specifically for the reason you mentioned (to avoid mixed language development)
I made Python wrappers in CSymPy optional, to ensure a single language
development.

>
> I'm rather sceptical even of mixing in just C++. I'm not convinced that the
> linear improvements of C++, however good they may be, can beat the

It depends on the benchmark of course, but it can be roughly 100x
for the basic symbolics.

> (allegedly) faster development speed and algorithmic improvements of Python.

Yes, it's much faster to develop new things in Python. But the reason
for CSymPy is speed --- so if you don't need speed, it has little
benefit. However,
if you need speed, then it is awesome, and it is of little use that
SymPy is easy
to develop, if it is slow for the given application.

> Garbage management is a real issue in C++.

Currently I use reference counting. I don't see any issue --- can you elaborate
on what you mean?

> You can't use Sympy in Jython if
> parts of it are coded up in C++.

Correct. That's why I view CSymPy as complementary, as I mentioned in my
previous emails.

> You have a higher barrier for turning users
> into contributors.

Higher than for SymPy, which is in Python. I agree.
Also, SymPy list might not be the best place to recruit C++ programmers.
But I know that a lot of people don't use SymPy because it was not fast enough
for their application. So with CSymPy among the available tools, there
would be no reason (in my opinion) not to use SymPy.

> That's quite a long list of what-ifs and annoying entanglements, and you can
> expect a few of them to actually bite; I'm not sure that the net result will
> be worth the effort. Then, of course, whether it's worth it is a value

I am convinced it is worth the effort --- as long as you need speed.
If you don't need speed, then SymPy works great.

> judgement that you might answer differently than me, so by all means make
> your own decisions :-) (I guess I'm playing Devil's Advocate here,
> enumerating all the counterarguments, just so that they are considered, not
> really to shoot the project down)

Absolutely, thanks for the discussion. :)

Ondrej

[Joachim Durchholz]

Am 03.10.2013 07:46, schrieb Ondřej Čertík:
>> Try the Boehm-Demers-Weiser collector and see what that brings.
>> Use really long-running tasks to benchmark it, it has a relatively high
>> fixed space overhead.
>
> I'll give it a shot, thanks for the tip. If nothing, it would be good to know
> the performance of GC compared to reference counting.

Well, the BDW collector cannot give you the full power of GC, for the
reasons mentioned, so you'll be comparing the BDW collector, not GC in
general.

>> I'd suggest trying out Java, which has a top-tier GC. Java does have some
>> performance issues related to run-time class loading and the presence of
>> introspection facilities, so it might not shine until the GC really starts
>> to become relevant.
>
> I doubt you can beat CSymPy with Java, but I'll be happy to be proven wrong.

Heh. Unfortunately, I won't find the time to do that, so I'll have to pass.
Also, Java is unattractive for Sympy because it's a rather heavyweight
runtime that you simply do not want to interface with any Python except
Jython.

... that's giving me a thought though: Maybe it's a good idea to make a
Sympy-to-whatever-language translation. On Jython, a C++ library just
doesn't make sense, but it would allow experimentation with different
languages.
It still comes with all the multiple-language-downsides as discussed
above, but if the backend can work with multiple languages, it's easier
to avoid relying too much on the features of one backend language, so
the restrictions on the Python side would turn out to be less.

> In my experience, one has to write a clean algorithm in C++ by hand, so
> the only thing that matters is the algorithm itself.

Okay... pity.

>> Garbage management is a real issue in C++.
>
> Currently I use reference counting. I don't see any issue --- can you elaborate
> on what you mean?

See http://www.hpl.hp.com/personal/Hans_Boehm/gc/issues.html for issues
with and around the BDW collector.

There's also the seminal Zorn paper "Memory Allocation Costs in Large C
and C++ Programs" at
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=6E5ECAB5D093601BF25863BDECEC9821?doi=10.1.1.89.6277&rep=rep1&type=pdf

[Ondřej Čertík]

On Thu, Oct 3, 2013 at 1:50 AM, Joachim Durchholz <j...@durchholz.org> wrote:
> Am 03.10.2013 07:46, schrieb Ondřej Čertík:

[...]

>>> Garbage management is a real issue in C++.
>>
>>
>> Currently I use reference counting. I don't see any issue --- can you
>> elaborate
>> on what you mean?
>
>
> See http://www.hpl.hp.com/personal/Hans_Boehm/gc/issues.html for issues with
> and around the BDW collector.
>
> There's also the seminal Zorn paper "Memory Allocation Costs in Large C and
> C++ Programs" at
> http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=6E5ECAB5D093601BF25863BDECEC9821?doi=10.1.1.89.6277&rep=rep1&type=pdf

I see, thanks for the pointers. They are a bit old, so maybe things
have improved since then.
In any case, I feel reference counting is more robust/predictable, so
that's what I currently use in CSymPy,
so there is no problem.

Ondrej

[F. B.]

I think once we stop supporting Python 2.7, we can start using static typing 
quite easily and I think it helps. 

That will be a long time, maybe 2017-2018 ? I'm just giving a naive estimate.

Though I think one of the most useful algorithms in SymPy that are 
candidates for C++ rewrite 
are polynomials, and those as far as I know don't use much duck typing, so 
it should be fairly easy to rewrite using fast native C++ datastructures. 
For example, here is my implementation of sparse polynomial multiplication 
in C++: 

https://github.com/certik/csympy/blob/master/src/rings.cpp#L63 
https://github.com/certik/csympy/blob/master/src/monomials.cpp#L7 

and I think it might be possible to speed it up further by playing 
with the hashtable 
and hashes and similar things. I tried to optimize a hash function for 
this case already, 
see here: 

https://github.com/certik/csympy/blob/master/src/dict.h#L48 

the idea is that the hash function needs to be fast to compute for the 
tuple of ints and 
also as unique as possible. 
 

Experiments on data types can be made in Python too. Python has basically three complex data-structures (I mean, the most common used): tuples, lists, dicts.

But in C++ a list can be different things. For example, in STL there are vector and list, vector fits better for fixed-length arrays, while lists is good if you have to append/pop elements. Python offers only a list object, but in many cases it would be useful to choose the array-like data structure that fits best. And by the way, if one already knows the size of the array, he should be able to pre-allocate the dimension of the list object.

I would try first to put this in Python, that would be a good point in easing translation and efficiency.

Btw, I don't want to discourage you from trying things. I only wanted 
to share my own 
(hard-earned) experience, as I tried various approaches. For example, 
one great project 
would be to implement similar symbolic core in Julia. It might get 
competitive or even 
faster than my Cython version above. Whether it could match my C++ version, 
that I don't know. 

It is possible that over the time new programming languages with powerful feature will start to emerge, in any case I would not commit too much time to optimization. You know, it's a continuously evolving subject, unrelated to just SymPy, maybe in the future a new technology will appear making things easier and faster. I would rather keep an eye an websites and papers related to optimization.

Trying hard on one way today, may turn up having being futile in the future.

On the other hand, adding new features to SymPy is always good.

[F. B.]

On Thursday, October 3, 2013 9:50:05 AM UTC+2, Joachim Durchholz wrote:

... that's giving me a thought though: Maybe it's a good idea to make a
Sympy-to-whatever-language translation. On Jython, a C++ library just
doesn't make sense, but it would allow experimentation with different
languages.

That would be an enormous amount of time. It's just hard to make a Python to C++ translator, I wouldn't imagine a translator to any language.

Besides, it is a very annoying task, you have to parse AST and define a generic format, maybe even some translation stages. Unless you mean to try some artificial intelligence approaches, such as translating some example files and make the translator learn how to do it on the remainder of the code. 

[Ondřej Čertík]

On Thu, Oct 3, 2013 at 10:59 AM, F. B. <franz....@gmail.com> wrote:
>>
>> I think once we stop supporting Python 2.7, we can start using static
>> typing
>> quite easily and I think it helps.
>>
>
> That will be a long time, maybe 2017-2018 ? I'm just giving a naive
> estimate.

Yeah, that might be true.

Exactly. Note that I use std::unordered_map for the representation of the
polynomials for now, but I use std::vector for the tuple and it might
not be the most optimal, since I need to add them together fast.

>
> I would try first to put this in Python, that would be a good point in
> easing translation and efficiency.

Here is the Python version that I "translated" to C++:

https://github.com/sympy/sympy/blob/master/sympy/polys/rings.py#L1033
https://github.com/sympy/sympy/blob/master/sympy/polys/monomials.py#L92

>
>> Btw, I don't want to discourage you from trying things. I only wanted
>> to share my own
>> (hard-earned) experience, as I tried various approaches. For example,
>> one great project
>> would be to implement similar symbolic core in Julia. It might get
>> competitive or even
>> faster than my Cython version above. Whether it could match my C++
>> version,
>> that I don't know.
>>
>
> It is possible that over the time new programming languages with powerful
> feature will start to emerge, in any case I would not commit too much time
> to optimization. You know, it's a continuously evolving subject, unrelated
> to just SymPy, maybe in the future a new technology will appear making
> things easier and faster. I would rather keep an eye an websites and papers
> related to optimization.
>
> Trying hard on one way today, may turn up having being futile in the future.

It is possible.

In numerical computing, which is my day job, the best
compromise that I arrived at is modern Fortran, which allows very readable
NumPy like code, but extremely fast execution, which pretty much can
only be beaten by very hard laborious work of optimizing for specific
architecture/cache/cpu, either in assembler, or by having various kernels
and choosing which one is faster, e.g. like FFTW works.

C++ seems a similar thing here for symbolics, but unlike Fortran, it
is much more complex,
so the benefits are not that clear, I agree with that.

But the bottom line is --- whatever programming language emerges in the future
as the winner, I will always be able to reuse Fortran or C++ codes, so it's
not a lost work. For example FFTPACK, written in 1984 in F77 is still
only 2x or so slower than FFTW on a *single* core on modern
architectures with the best
Fortran compilers today. The advantage of modern code like FFTW is that
it consumes less memory bandwidth, so it scales better on more cores and so on.

So my conclusion from all this is that I am not going to go to
assembler or stuff like that.
Rather, I want to have a readable single C++ codebase, that compiles
and is as fast or faster
than other symbolic programs/libraries. It seems it is possible. That
way people can use
SymPy together with CSymPy today, and be able to do anything that is
possible with
other programs.

> On the other hand, adding new features to SymPy is always good.

I agree.

Ondrej

[Joachim Durchholz]

Am 03.10.2013 19:40, schrieb F. B.:
>
>
> On Thursday, October 3, 2013 9:50:05 AM UTC+2, Joachim Durchholz wrote:
>>
>>
>> ... that's giving me a thought though: Maybe it's a good idea to make a
>> Sympy-to-whatever-language translation. On Jython, a C++ library just
>> doesn't make sense, but it would allow experimentation with different
>> languages.
>>
>
> That would be an enormous amount of time. It's just hard to make a Python
> to C++ translator, I wouldn't imagine a translator to any language.

Ondrej said he'd have to rewrite the algorithm in C++, so the way he
envisions doing it won't work that way anyway.
But then if an automated translation does give a useful amount of
speed-up without incurring the cost of a manual rewrite, it would still
be a net win.

> Besides, it is a very annoying task, you have to parse AST and define a
> generic format, maybe even some translation stages.

In essence, it would be a translator from Python to other languages.

If the classes do not have their lists of attributes modified at
runtime, this is actually not too hard to do. Sympy isn't there, but
it's heading that way, so this might be an option.

It would be a considerable amount of up-front work, with no guarantees
of the outcome; Ondrej's approach is more incremental, he can
cherry-pick those cases that work best; I suspect in the end, his
approach will work better for some specialized cases and the generalized
approach will work better for speeding up Sympy in general (and on
platforms where C++ isn't really accessible).

The two approaches aren't mutually exclusive and could be combined.

> Unless you mean to try
> some artificial intelligence approaches, such as translating some example
> files and make the translator learn how to do it on the remainder of the
> code.

Nah, AI is too unpredictable in when it will work and when not.

[Joachim Durchholz]

Am 03.10.2013 17:04, schrieb Ondřej Čertík:
> On Thu, Oct 3, 2013 at 1:50 AM, Joachim Durchholz <j...@durchholz.org> wrote:
>> Am 03.10.2013 07:46, schrieb Ondřej Čertík:
> [...]
>>>> Garbage management is a real issue in C++.
>>>
>>> Currently I use reference counting. I don't see any issue --- can you
>>> elaborate
>>> on what you mean?
>>
>> See http://www.hpl.hp.com/personal/Hans_Boehm/gc/issues.html for issues with
>> and around the BDW collector.
>>
>> There's also the seminal Zorn paper "Memory Allocation Costs in Large C and

>> C++ Programs" [...]

>
> I see, thanks for the pointers. They are a bit old, so maybe things
> have improved since then.

I think both mark&sweep and reference-counting approaches have improved
since that paper, but the relative performance is still the same.

RC does have its niches, but the problem is that as applications evolve,
they tend to leave the RC-friendly niche and then you need to rewrite
all the allocation code because the RC scheme is visible over all of the
code.
Hmm... okay, you could probably stub out whatever SmartPointer<> class
you're using, dropping all the reference counting code, the variables,
and the free calls, and see what the performance is. Your code might
still be geared towards being RC-friendly instead of
mark&sweep-friendly, but it would give at least a preliminary result.

In fact it would be interesting to see how the performance figures have
evolved since the papers were written.

> In any case, I feel reference counting is more robust/predictable, so
> that's what I currently use in CSymPy,

Heh. Actally, you're just exchanging one kind of unpredictability with
another.
With a mark&sweep collector, you don't know when a block will be
deallocated.
With an RC collector, you don't know how much time a pointer update will
take, because the pointer may be the last reference to a large network
of objects and the update might cause an avalanche of count updates and
free() calls.

The RC collector scene is aware of the problem, and they're trying to
remedy this by deferring free() calls - but that means you don't know
when a block will be deallocated, so we're back to the original
behaviour, just less efficient (because reference count updates cost
time and have horrible cache locality).

You can make a mark&sweep collector concurrent, or integrate it into a
malloc() function that does a bit of GC work on each call. With that
approach, you can tune the GC to the minimal level of activity that
prevents the heap from growing. You could make it a setting that can be
tuned to whatever use case you have - switch GC off entirely by default
when in the interactive loop, and letting it kick in if a command turns
out to eat memory. Or have it trade speed vs. memory usage - a higher GC
activity will be slower but take less memory.

Also, RC collectors cannot handle cycles. There are various approaches
to remedy this, but all that I have seen just graft a standard
mark&sweep collector on top of the RC machinery - I doubt that that's
going to be more efficient than having a mark&sweep collector right from
the start.

Outside of the C++ community, RC is generally discredited as a dead end.
I don't know how much of that is based on fact vs. hearsay. Also, RC
might be the best alternative for C++'s semantics anyway... the Zorn
paper says otherwise.
The tl;dr variant of the Zorn paper is: replace malloc() with calls into
a garbage-collecting memory management, cancel free() out via the
preprocessor, and the majority of programs speeds up, a few slow down.

There's also consensus that C++'s concept of "memory deallocation is
resource deinitialization" does not translate to a garbage-collected
environment at all. Python uses context handlers, and I consider that
approach really solid (Java recently acquired something similar).
I guess you'd want to create a ContextHandler class for your C++ code
since you can't rely on free() being called anymore.
This aspect isn't thoroughly covered in the Zorn paper IIRC.

[Björn Dahlgren]

I do know of http://rosecompiler.org/ which supposedly does this for the big languages, but I have
absolutely no experience with it - maybe someone else on the list could fill in the gaps and present their view on using it?

[Ondřej Čertík]

Good ideas --- here is the RCP class that I created for CSymPy:

https://github.com/certik/csympy/blob/master/src/csympy_rcp.h#L59

$ ./expand2
Expanding: ((y + x + z + w)^15 + w)*(y + x + z + w)^15
1217ms
number of terms: 6272


So I deleted all reference counting and deleting of objects (patch
here https://gist.github.com/certik/6829650)
--- but I left the RCP class for now. Just to get an idea.

$ ./expand2
Expanding: ((y + x + z + w)^15 + w)*(y + x + z + w)^15
1382ms
number of terms: 6272


And things got slower... Haha, that was unexpected. Why would that be?

Based on my experience, one always has to try various approaches and
pick the fastest.
RC has been pretty robust in my experience, but I will try some GC approaches
as well. I feel there is at least 10% maybe more potential for speedup thanks to
better memory management.

Ondrej

[Joachim Durchholz]

None at all... except that benchmarking is difficult :-)

Did you run your test multiple times?
A difference for one-off runs can have a multitude of reasons that are
related to the system's state, you need a warm-up phase and you need to
observe the variance. Observing actual memory usage might also be
interesting, just to get an idea how much of a role memory management
actually plays in expand2. Your RCP class could count memory sizes and
delete requests.

Maybe this result indicates that questions of garbage collection are
irrelevant for expand2, possibly because it generates almost no garbage.
OTOH if the program is generating lots of garbage, it may be that the
program spent a lot of time increasing the heap, setting up data
structures and zeroing out memory.

> Based on my experience, one always has to try various approaches and
> pick the fastest.
> RC has been pretty robust in my experience, but I will try some GC approaches
> as well. I feel there is at least 10% maybe more potential for speedup thanks to
> better memory management.

As I said - profiling indicates that allocation-intensive programs can
spend 20% of their time in memory management. So a 10% improvement would
be quite good actually.

Speed is really hard to measure though because there is so much
variation. "Pick the fastest" assumes there is a "fastest" approach -
which does not exist in general, there's always the odd program where
one otherwise bad approach will fly and all others suck.

I hate that C++ doesn't really allow a copying GC. That approach is the
one where the differences are bound to be significant.

On
http://stackoverflow.com/questions/8251645/generational-gc-source-code
I'm seeing Qish, which does some heavy (but maybe Sympy-compatible?)
restrictions on what C++ is allowed to do, and copying. I just don't
know how optimized Qish is.
That page generally lists some more GC approaches.

The Boehm collector is still mentioned so it hasn't gone out of favor.
It would be interesting to see how it fares with the non-RC variant of
your code.

[Ondřej Čertík]

Yes. I run it about 10 to 15 times in two terminals with and without the feature
that I want to measure and I report the best times in both.

> A difference for one-off runs can have a multitude of reasons that are
> related to the system's state, you need a warm-up phase and you need to
> observe the variance.

I don't measure variance, only by looking at it. Do you see a problem
with reporting the best time?

> Observing actual memory usage might also be
> interesting, just to get an idea how much of a role memory management
> actually plays in expand2. Your RCP class could count memory sizes and
> delete requests.

Good point, I should play with that.

>
> Maybe this result indicates that questions of garbage collection are
> irrelevant for expand2, possibly because it generates almost no garbage.
> OTOH if the program is generating lots of garbage, it may be that the
> program spent a lot of time increasing the heap, setting up data structures
> and zeroing out memory.
>
>
>> Based on my experience, one always has to try various approaches and
>> pick the fastest.
>> RC has been pretty robust in my experience, but I will try some GC
>> approaches
>> as well. I feel there is at least 10% maybe more potential for speedup
>> thanks to
>> better memory management.
>
>
> As I said - profiling indicates that allocation-intensive programs can spend
> 20% of their time in memory management. So a 10% improvement would be quite
> good actually.

Absolutely. It's 10% this, then 10% hashing function, then 10% (or
more!) the right data structure
etc., and it all adds up in the end.

>
> Speed is really hard to measure though because there is so much variation.
> "Pick the fastest" assumes there is a "fastest" approach - which does not
> exist in general, there's always the odd program where one otherwise bad
> approach will fly and all others suck.
>
> I hate that C++ doesn't really allow a copying GC. That approach is the one
> where the differences are bound to be significant.
>
> On http://stackoverflow.com/questions/8251645/generational-gc-source-code
> I'm seeing Qish, which does some heavy (but maybe Sympy-compatible?)
> restrictions on what C++ is allowed to do, and copying. I just don't know
> how optimized Qish is.
> That page generally lists some more GC approaches.
>
> The Boehm collector is still mentioned so it hasn't gone out of favor. It
> would be interesting to see how it fares with the non-RC variant of your
> code.

Ondrej

[F. B.]

I just had a look at the Julia project http://julialang.org/

Have a look at how they manage operator overloading:

https://github.com/JuliaLang/julia/blob/master/examples/quaternion.jl

That is a great idea, it would keep code clear and readable, and avoid the need of all those if isinstance( ) ... elif isinstance( )

By the way, the aim of Julia is to be both an interpreted language and a fast compiled language, with speed of execution near to those of C. At the same time they want to keep perfect interaction with both Python and C...

So, why not try rewriting Sympy Core in Julia? It would keep the programming language simple, maybe even simpler than in Python, and at the same time allow perfect interaction with both Python and C, and reach the performance of C.

By the way, I know that using classes in C++ decreases performance, the way Julia overloads operators would keep things as easy as in simple C.

[F. B.]

[Ondřej Čertík]

Yes, that's roughly the idea behind Julia. The other is better support
for "templates"
and reasoning about types.

However, whether it can actually match performance of C++ in practice,
that remains
to be seen. But it should be tried.

Ondrej

[Joachim Durchholz]

Am 07.10.2013 20:07, schrieb F. B.:
> I just had a look at the Julia project http://julialang.org/
>
> Have a look at how they manage operator overloading:

I just did and shuddered.
Unrestrained multple dispatch runs into modularity issues. It's one of
those mistakes that language designers make over and over again, because
the base idea seems to simple and the use cases one can think of are so
straightforward, but they almost never consider the case what happens
when two independent developers have their work merged by a third.

> That is a great idea, it would keep code clear and readable, and avoid the

> need of all those *if isinstance( ) ... elif isinstance( )*

There are better and more general ways to avoid that.
Unfortunately, neither Julia's approach nor the ones typically employed
in FPLs are available in Python.

> By the way, the aim of Julia is to be both an interpreted language and a
> fast compiled language, with speed of execution near to those of C. At the
> same time they want to keep perfect interaction with both Python and C...

Sounds like they're too ambitious to succeed.

> So, why not try rewriting Sympy Core in Julia?

Now you're just talking crazy ;-P

> It would keep the
> programming language simple, maybe even simpler than in Python,

Unlikely. Every language has its quirks.

Joel isn't right in everything he writes, but the points he raises are
usually well worth considering.
He covered rewrites already:
http://www.joelonsoftware.com/articles/fog0000000069.html

> and at the
> same time allow perfect interaction with both Python and C, and reach the
> performance of C.

I doubt that you can have both easy interaction with dynamic languages
and raw performance. To the very least, you'll have to keep the number
of inter-language calls down, and that would impose design restrictions
on Sympy's code. Sympy already has a lot of restrictions to observe, I
doubt that that's going to be easy.

[F. B.]

On Monday, October 7, 2013 8:28:04 PM UTC+2, Joachim Durchholz wrote:

Am 07.10.2013 20:07, schrieb F. B.:
> I just had a look at the Julia project http://julialang.org/
>
> Have a look at how they manage operator overloading:

I just did and shuddered.
Unrestrained multple dispatch runs into modularity issues. It's one of
those mistakes that language designers make over and over again, because
the base idea seems to simple and the use cases one can think of are so
straightforward, but they almost never consider the case what happens
when two independent developers have their work merged by a third.

Methods and operators in Python and C++ are not very different from Julia's idea, it's just the way you write it: the first argument in Python is self, you just have to write it inside the class declaration, while in Julia you write it outside of it. The same is true for C++ methods, the only difference is that in Julia you're free to write the methods everywhere, but problems could be avoided by keeping the code clean.

Wolfram Mathematica has an overloading approach which also has pattern matching... it simply fits very well to a symbolic CAS.

 

> That is a great idea, it would keep code clear and readable, and avoid the
> need of all those *if isinstance( ) ... elif isinstance( )*

There are better and more general ways to avoid that.
Unfortunately, neither Julia's approach nor the ones typically employed
in FPLs are available in Python.

A type dispatcher is a must for a CAS, in my opinion. It would keep things easier.

 

> By the way, the aim of Julia is to be both an interpreted language and a
> fast compiled language, with speed of execution near to those of C. At the
> same time they want to keep perfect interaction with both Python and C...

Sounds like they're too ambitious to succeed.

Well, it is not impossible nowadays. There is LLVM now.

When Python was invented it was an extremely difficult task to write such a thing, both a compiler and an interpreted language, because you had to write it all on your own. Today we have LLVM, which is of great help, and LLVM is a recently appeared tool.

 

By the way, Julia-Python interaction is already there. As Julia is able to compile to machine code, it should be easy to extend the LLVM compiling framework to create compiled Python plugins, but I don't know what's in the developers' minds.

In any case I read that some of cython's developers are amazed by Julia.

 

 > and at the
> same time allow perfect interaction with both Python and C, and reach the
> performance of C.

I doubt that you can have both easy interaction with dynamic languages
and raw performance. To the very least, you'll have to keep the number
of inter-language calls down, and that would impose design restrictions
on Sympy's code. Sympy already has a lot of restrictions to observe, I
doubt that that's going to be easy.

Well, I believe that you are looking back in time at traditional languages, without realizing the power of a language specifically engineered for scientific research. 

[Joachim Durchholz]

Am 07.10.2013 21:06, schrieb F. B.:
>
>
> On Monday, October 7, 2013 8:28:04 PM UTC+2, Joachim Durchholz wrote:
>>
>> Am 07.10.2013 20:07, schrieb F. B.:
>>> I just had a look at the Julia project http://julialang.org/
>>>
>>> Have a look at how they manage operator overloading:
>>
>> I just did and shuddered.
>> Unrestrained multple dispatch runs into modularity issues. It's one of
>> those mistakes that language designers make over and over again, because
>> the base idea seems to simple and the use cases one can think of are so
>> straightforward, but they almost never consider the case what happens
>> when two independent developers have their work merged by a third.
>>
>>
> Methods and operators in Python and C++ are not very different from Julia's

> idea, it's just the way you write it: the first argument in Python is *self*,

> you just have to write it inside the class declaration, while in Julia you
> write it outside of it. The same is true for C++ methods, the only
> difference is that in Julia you're free to write the methods everywhere,
> but problems could be avoided by keeping the code clean.

The relevant point is that you have multipe parameters that you dispatch
on (or overload, the issues are the same).

>>> That is a great idea, it would keep code clear and readable, and avoid
>> the
>>> need of all those *if isinstance( ) ... elif isinstance( )*
>>
>> There are better and more general ways to avoid that.
>> Unfortunately, neither Julia's approach nor the ones typically employed
>> in FPLs are available in Python.
>>
> A type dispatcher is a must for a CAS, in my opinion. It would keep things
> easier.

Yes, but multiple dispatch is *so* not the way to go.
Unless all dispatch combinations are forced to be within the same module.

Multiple dispatch: modularity, unsurprising behaviour, unrestricted
ability to add new variants - pick any two.

>>> By the way, the aim of Julia is to be both an interpreted language and a
>>> fast compiled language, with speed of execution near to those of C. At
>> the
>>> same time they want to keep perfect interaction with both Python and
>> C...
>>
>> Sounds like they're too ambitious to succeed.
>
> Well, it is not impossible nowadays. There is LLVM now.

LLVM solves quite a few challenges, but not these.

>> > and at the
>>> same time allow perfect interaction with both Python and C, and reach
>> the
>>> performance of C.
>>
>> I doubt that you can have both easy interaction with dynamic languages
>> and raw performance. To the very least, you'll have to keep the number
>> of inter-language calls down, and that would impose design restrictions
>> on Sympy's code. Sympy already has a lot of restrictions to observe, I
>> doubt that that's going to be easy.
>
> Well, I believe that you are looking back in time at traditional languages,
> without realizing the power of a language specifically engineered for
> scientific research.

I think I should stop in politeness here and just point out that you are
wrong in your belief.

[Ondřej Čertík]

Let's keep being polite please. :)

I have similar views as F.B., so I won't repeat them.

But I would point out,
that besides Julia, there is also Numba, with similar goals --- they started
optimizing arrays, but my understanding is that they plan to ultimately allow
more things, similar to Julia.

My ultimate conclusion is, that it remains to be seen, in a few years,
how well these new languages perform. While C++ and Fortran allow
me to have very high performance now.

Ondrej

[F. B.]

It seems that someone is already porting SymPy to Julia, though just via PyCall linking:

https://github.com/jverzani/SymPy.jl

[Ondřej Čertík]

Yes, I've seen this before. There is also this:

https://github.com/johnmyleswhite/Calculus.jl

Ondrej

[Ondřej Čertík]

Hi Marduk,

On Sat, Nov 2, 2013 at 6:03 PM, Marduk <mar...@ciencias.unam.mx> wrote:
> It might help to take a look at SymbolicC++.

Thanks for the suggestion. I have in fact looked at SymbolicC++ when I
was benchmarking CSymPy ---
I implemented the simple benchmark in my "expand"
branch here:

https://github.com/certik/SymbolicCpp/tree/expand

Just do:

cd examples
g++ -O3 -march=native -ffast-math -funroll-loops -I../headers expand.cpp
./a.out

and you can see that it is even slower than SymPy which is in pure
Python... The idea of using C++ is to get faster than SymPy, not slower.
Maybe I am using it wrong. If you see any problem, please let me know.

Also, SymbolicC++ seems to be expanding things by default. For our purpose,
it needs to be able to handle any expression.

Ondrej

P.S. I sent this message also to your private email in a separate
thread, as I didn't realize that you only
sent it to me there.

[Marduk]

Sorry, Google Groups newbie here. I intended to reply to your original message about the announcement but accidentally sent you a private message. Thanks for replying here so that others know about it.

[Marduk]

Just for the record. With the help of Rubi I just solved an integral for which both Mathematica and Maxima gave a rather ugly answer. Rubi provided the same result that appears in a book. Based on this experience I definitely recommend, and if I can find the time I will collaborate, to work on implenting the Rubi rules for Sympy.

[Joachim Durchholz]

For those who're getting redirected to Ruby (the programming language),
the Rubi homepage is here: http://www.apmaths.uwo.ca/~arich/

In general, we've been considering moving towards more rule-based
reasoning (instead of coding stuff directly in Python), on the grounds
that rules are easier to reason about than code.
Implementing the Rubi rules could be a nice use case for that.

What I don't know is what the quality of that ruleset is, and how well
it would blend with other simplification rules (some Rubi rules might be
duplicating work done in existing simplification steps of SymPy). So I
guess before we decide anything, somebody with insight into what SymPy's
simplification can and cannot do should look into the Rubi rules and
decide how to best integrate it.
From what I can see, Rubi certainly looks impressive, but I have only
cursor knowledge of SymPy's simplification and no integration skills
worth mentioning, so I guess I'm easily impressed :-)

[F. B.]

On Sunday, November 3, 2013 9:46:43 AM UTC+1, Marduk wrote:

Just for the record. With the help of Rubi I just solved an integral for which both Mathematica and Maxima gave a rather ugly answer. Rubi provided the same result that appears in a book. Based on this experience I definitely recommend, and if I can find the time I will collaborate, to work on implenting the Rubi rules for Sympy.

Sympy needs a better pattern matching and a better assumptions system to port Rubi.

I already had a look if it is possible to write a code generator to translate Rubi's rules to Sympy, but Sympy's rules and assumptions are not as powerful as Mathematica's ones.

By the way, I think that pattern matching through expression trees should be somewhat more ground-based than an implementation into Sympy's core. I mean, pattern matching should be a tool native to the language itself. Python is reaching a widespread usage among scientific research recently, unfortunately it's not the best language for scientific purposes.

Most importantly, a good multiple dispatcher is the starting point before a good pattern matcher can be written.

I believe that rewriting SymPy in C++ would be a too long journey, and code could be harder to maintain, as C++ is a complicated language. Maybe it would be better to try either numba or Julia.

There was a discussion this summer about introducing multiple dispatch into Sympy, what's the situation now? I think that, as Sympy has types, it would be cleaner to switch to a function-struct strategy, where methods of classes are not declared inside the class, rather through the usage of decorators on external functions.

In Julia types allow only a constructor as a method (unlike classes which allow any method inside), multiple dispatch provides the operator overloading. Something similar would help to keep the code clean in Sympy, with multiple dispatch indeed the code would be far more readable.

Regarding numba's future plans, it seems they got inspired by Julia, and they will put a LLVM based multiple dispatcher: http://continuumio.github.io/numba-nextgen-docs/

I think that refactoring SymPy with multiple dispatch and less usage of class methods would be a good start. After that it would be possible to write a check if numba is installed, trying to use it. Otherwise it would fall back to the usual python mode. This could help speed up SymPy without rewriting it to another language. What do you think?

Otherwise, on Julia a library focusing on pattern matching is already being written: https://github.com/kmsquire/Match.jl

Regarding the power pattern matching to simplify the code, just have a look at the rules to simplify gamma matrices written in Python code in a recent PR, lots of lines of code, if we had a better pattern matching that would be far easier to write.

[Joachim Durchholz]

In general, I do not think that extending the language is going to help
SymPy.
1) Extending a programming language is a huge amount of work.
2) Getting all the bugs and interactions with existing language features
out is even more work.
3) Making a new feature work as intended is often difficult. Many
extensions work well for the small examples, everything looks nice for
months and sometimes years, until you start hitting problems. (Multiple
dispatch is one of these features that everybody wants and that don't
scale to arbitrary ecosystem size. Making it scale requires
restrictions, which one rarely wants to do but it's also technically
hard in a restriction-unfriendly language like Python.)
4) Teaching all the static analysis tools about the new language
features is a neverending amount of work, again.
5) There's not need for that. We can always write pattern-matching rules
as Python data structures, usuing function and constructor calls; we can
always write a tree transform engine that applies these rules to an Expr
tree.