SymPy args and multiple dispatch

[F. B.]

In a recent PR I submitted it emerged that using sympy's Tuple instead of list or tuple seems to cause a significant slow down of the code execution. I blamed this behavior to the necessity of copying data from the list to the Tuple object once the list has been created.

Currently args in sympy objects are required to be subtypes of Basic, so that methods such as xreplace(), subs(), has(), match() become available. These are inherited from Basic. Technically, these methods could be applied also to non-sympy structures, maybe by dynamically adding new methods to existing classes at runtime. Unfortunately duck-typing does not work on builtins.

What about turning methods such as xreplace(), subs(), has(), atoms(), match() to multiple dispatched functions? They would work the same way as inherited methods, with the possibility of defining such functions on python builtins, e.g.

@dispatch(tuple, dict)
def xreplace(t, d):  # t -> tuple upon which to act, d -> replacements dict
    return tuple([xreplace(i, d) for i in t])

Python is likely to recognize tuple operations an apply better optimizations than on Tuple.

In such a way it would be possible to include python builtin types and maybe even external objects (provided they are immutable) into the args tree.

[Joachim Durchholz]

Am 15.04.2014 11:04, schrieb F. B.:
> What about turning methods such as xreplace(), subs(), has(), atoms(),
> match() to multiple dispatched functions?

Performance?
Somebody (you) said that MD does not come for free.

I'm not sure if this is actually an issue, it really depends on whether
these functions are part of any tight loop. The names make me suspect
that that's the case, so I'd want the performance impact evaluated.

> Python is likely to recognize tuple operations an apply better
> optimizations than on Tuple.

Not if the call goes through multiple dispatch.
This could change if MD becomes a widely recognized and adopted library,
but it's not there today.

[F. B.]

On Tuesday, April 15, 2014 11:28:58 AM UTC+2, Joachim Durchholz wrote:

Am 15.04.2014 11:04, schrieb F. B.:
> What about turning methods such as xreplace(), subs(), has(), atoms(),
> match() to multiple dispatched functions?

Performance?
Somebody (you) said that MD does not come for free.

Just some considerations, accessing a function method is carried out in Python by first looking up the class name in globals(), then looking for the method name in the MRO. For a cached multiple dispatched function it is a globals() lookup, followed by a lookup in the cache dictionary. Both of them involve two dictionary lookups.
 

I'm not sure if this is actually an issue, it really depends on whether
these functions are part of any tight loop. The names make me suspect
that that's the case, so I'd want the performance impact evaluated.

I think it has to be tried before judging, maybe the impact is minimal. I believe that the benefit of avoiding the creation of Tuple objects, using Python's native tuples instead, would boost performance by a greater factor than the loss caused by multiple dispatching.

> Python is likely to recognize tuple operations an apply better
> optimizations than on Tuple.

Not if the call goes through multiple dispatch.
This could change if MD becomes a widely recognized and adopted library,
but it's not there today.

I meant optimizations inside the function body, not on function calls.

[F. B.]

By the way, dictionary search in Python has a time complexity of O(1)

https://wiki.python.org/moin/TimeComplexity

I wouldn't bother too much about the overhead of using multiple dispatch.

[Matthew Rocklin]

Performance?
Somebody (you) said that MD does not come for free.

I brought this up.  I can't get a MD call to go below about a microsecond.  This is a few times slower than a Python call.  It's many times faster than your average SymPy operation.

If anyone wanted to try to get it to go faster that'd be awesome.  The code is, I think, pretty small and approachable.

Python is likely to recognize tuple operations an apply better
optimizations than on Tuple.

Not if the call goes through multiple dispatch.
This could change if MD becomes a widely recognized and adopted library, but it's not there today.

I think that MD needs some major library to start using it.  There is a lot of interest but I think that no project wants to be the first to invest.

[Matthew Rocklin]

I really like this idea (though perhaps that's to be expected :) )

[Ondřej Čertík]

On Tue, Apr 15, 2014 at 7:18 AM, Matthew Rocklin <mroc...@gmail.com> wrote:
>>
>> Performance?
>> Somebody (you) said that MD does not come for free.
>
>
> I brought this up. I can't get a MD call to go below about a microsecond.
> This is a few times slower than a Python call. It's many times faster than
> your average SymPy operation.

For those reading this thread, MD = multiple dispatch. Not "molecular
dynamics"... (http://en.wikipedia.org/wiki/MD)

>
> If anyone wanted to try to get it to go faster that'd be awesome. The code
> is, I think, pretty small and approachable.
>
>>
>>> Python is likely to recognize tuple operations an apply better
>>> optimizations than on Tuple.
>>
>>
>> Not if the call goes through multiple dispatch.
>> This could change if MD becomes a widely recognized and adopted library,
>> but it's not there today.
>
>
> I think that MD needs some major library to start using it. There is a lot
> of interest but I think that no project wants to be the first to invest.
>

> --
> 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.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/CAJ8oX-GxmEyDpqsw4Yf3B5t-QjiU06zoMdBrgGA02Nc7dDA_Bw%40mail.gmail.com.
>
> For more options, visit https://groups.google.com/d/optout.

[Joachim Durchholz]

This depends on some future developments.

I'm seeing the numba project. They're leveraging LLVM to speed up Python.
Now the core of any serious optimization for OO language is finding out
for which calls you can eliminate dispatch, which enables inlining,
which is the starting point for making all these optimizations in the
book effective on a large scale.
Anything that messes with the dispatching will make it harder for the
analyzer to find out where the single dispatch is, and end in missed
optimization opportunities.

Now that's all future technology, and might never materialize for
standard Python.
Still, we should be prepared to either make the change optional or at
least easily reversible, or be prepared to help those compilers optimize
not just normal dispatch but multiple dispatch as well.

[Aaron Meurer]

On Tue, Apr 15, 2014 at 4:04 AM, F. B. <franz....@gmail.com> wrote:

In a recent PR I submitted it emerged that using sympy's Tuple instead of list or tuple seems to cause a significant slow down of the code execution. I blamed this behavior to the necessity of copying data from the list to the Tuple object once the list has been created.

Did you actually confirm that this is the true source of the slowdown?

 

Currently args in sympy objects are required to be subtypes of Basic, so that methods such as xreplace(), subs(), has(), match() become available. These are inherited from Basic. Technically, these methods could be applied also to non-sympy structures, maybe by dynamically adding new methods to existing classes at runtime. Unfortunately duck-typing does not work on builtins.

Wrong animal. You are thinking of monkey patching. And monkey patching is evil anyway.

 

What about turning methods such as xreplace(), subs(), has(), atoms(), match() to multiple dispatched functions? They would work the same way as inherited methods, with the possibility of defining such functions on python builtins, e.g.

@dispatch(tuple, dict)
def xreplace(t, d):  # t -> tuple upon which to act, d -> replacements dict
    return tuple([xreplace(i, d) for i in t])

Python is likely to recognize tuple operations an apply better optimizations than on Tuple.

The problem is that we would have to change the syntax from object.xreplace(replacement) to xreplace(object, replacement).

 

In such a way it would be possible to include python builtin types and maybe even external objects (provided they are immutable) into the args tree.

Tuple should just be a thin wrapper around tuple. If implemented correctly, it should be just as fast as what you are suggesting (as others have noted multiple dispatch might have performance issues of its own).

Aaron Meurer

 

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

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/b3d0e629-f859-4d6e-80ce-4e2e211cc185%40googlegroups.com.

[F. B.]

I don't believe that the overhead caused by multiple dispatching would be a problem for xreplace, considering that xreplace( ) opens recursively all of the objects contained in the args tree and creates a new object. The major issues are rather those concerning the API change.

In any case, as soon as Julia will support better bindings to python and static compilation, it may be worth trying to translate sympy's core to Julia. That would allow an extensive usage of multiple dispatch without much overhead.

The other advantage of multiple dispatching is type-markings of functions and methods, that makes the code much more readable and provides some protection against passing of faulty parameters.

Python was not engineered for scientific purposes, though it has now been adopted as one of the main open source scientific programming languages.

[Vinzent Steinberg]

On Wednesday, April 16, 2014 3:25:01 AM UTC-4, F. B. wrote:

I don't believe that the overhead caused by multiple dispatching would be a problem for xreplace, considering that xreplace( ) opens recursively all of the objects contained in the args tree and creates a new object. The major issues are rather those concerning the API change.

In any case, as soon as Julia will support better bindings to python and static compilation, it may be worth trying to translate sympy's core to Julia. That would allow an extensive usage of multiple dispatch without much overhead.

You can precompile modules in Julia (you have to recompile all of Julia though). Please note that at the moment importing libraries in Julia can take a very long time (see [1] for instance).

Vinzent

[1] https://github.com/dcjones/Gadfly.jl/issues/251

[Ondřej Čertík]

Yes, this is a very cool feature of Julia. Btw, if any of you are
interested in this,
you can help us write and test Julia wrappers for CSymPy:

https://github.com/sympy/csympy
https://github.com/sympy/csympy/issues/150

Ondrej

[F. B.]

On Friday, April 18, 2014 4:15:36 AM UTC+2, Ondřej Čertík wrote:

Yes, this is a very cool feature of Julia. Btw, if any of you are
interested in this,
you can help us write and test Julia wrappers for CSymPy:

https://github.com/sympy/csympy
https://github.com/sympy/csympy/issues/150

Ondrej

I believe that the main reason to use Julia is avoiding C/C++, that is, Julia is a simple programming language to learn with performance of the same order of magnitude of C/C++. Furthermore Julia provides lisp-like macros, which can be very powerful in a CAS if appropriately used.

My point is that it would be more convenient to experiment a SymPy core in Julia rather than in C++. In any case, Julia is still young, so maybe it would be convenient to wait until it's more mature.

The point is that development in both Python and Julia is much faster than software development in C++.

[Ondřej Čertík]

On Fri, Apr 18, 2014 at 1:34 AM, F. B. <franz....@gmail.com> wrote:
>
>
> On Friday, April 18, 2014 4:15:36 AM UTC+2, Ondřej Čertík wrote:
>>
>> Yes, this is a very cool feature of Julia. Btw, if any of you are
>> interested in this,
>> you can help us write and test Julia wrappers for CSymPy:
>>
>> https://github.com/sympy/csympy
>> https://github.com/sympy/csympy/issues/150
>>
>> Ondrej
>
>
> I believe that the main reason to use Julia is avoiding C/C++, that is,
> Julia is a simple programming language to learn with performance of the same
> order of magnitude of C/C++. Furthermore Julia provides lisp-like macros,
> which can be very powerful in a CAS if appropriately used.

Yes, those are cool.

>
> My point is that it would be more convenient to experiment a SymPy core in
> Julia rather than in C++. In any case, Julia is still young, so maybe it
> would be convenient to wait until it's more mature.
>
> The point is that development in both Python and Julia is much faster than
> software development in C++.

That's true. But what matters is also speed, and if someone can beat CSymPy
with pure Julia, that would be cool. But based on my experience so far,
C++ is the only option which allows me to get the speed and a relatively safe
code.

Ondrej

[Aaron Meurer]

Has anyone yet tried translating CSymPy to Julia and benchmarking it? I personally would get more excited about Julia than C++. It has a vibrant community, a cleaner design, higher level abstractions, and I think what they're doing with jitting and LLVM will in the long run be better for performance than the compile time optimizations you get from C++.

Aaron Meurer

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

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CADDwiVAZ5VQeg_vtXGhcHunO7dncWwqe8cNa3VmLneDOea6xYw%40mail.gmail.com.

[F. B.]

On Friday, April 18, 2014 8:32:31 PM UTC+2, Aaron Meurer wrote:

Has anyone yet tried translating CSymPy to Julia and benchmarking it? I personally would get more excited about Julia than C++. It has a vibrant community, a cleaner design, higher level abstractions, and I think what they're doing with jitting and LLVM will in the long run be better for performance than the compile time optimizations you get from C++.

C/C++ were conceived in the 80's and have remained thus far the most optimized high-level languages. Languages that appeared in the 90's are either scripted (like Python) or rely on a virtual machine (like Java). This is comprehensible: writing a compiler to machine code is a really hard task, even the translation to assembler alone is hard. Since the LLVM appeared, it is now much faster to write compilers, and lots of new programming languages are appearing based on the LLVM. I think that LLVM is a good infrastructure to allow new programming languages to appear.

Julia's types are like those of C, multiple dispatching is done at compile-time rather than at run-time whenever it is possible, for this I see no disadvantage over C in terms of performance. The problem I see is metaprogramming, Julia's code can be loaded as a data structure, and be recompiled at run-time. I fear this capability introduces some performance disadvantages over C, (despite being very useful), as the code has to keep some track of the original source code, but I'm not expert enough about compilation processes to judge that. I hope they will find a way to bring Julia's performance at a level closer to that of C.

In any case, before starting a translation into Julia I would wait until:

• someone introduces a clear way to call Julia code from Python (possibly through static compilation).
• abstract types in Julia can have fields.
• multiple inheritance support in Julia.
• dot and __call__ operator overloading.
  

[Ondřej Čertík]

On Fri, Apr 18, 2014 at 12:32 PM, Aaron Meurer <asme...@gmail.com> wrote:
> Has anyone yet tried translating CSymPy to Julia and benchmarking it? I
> personally would get more excited about Julia than C++.

Nobody yet. It would be nice to do.

> It has a vibrant
> community, a cleaner design, higher level abstractions, and I think what

Agreed.

> they're doing with jitting and LLVM will in the long run be better for
> performance than the compile time optimizations you get from C++.

We'll see about that. The beauty of C++ is that whatever we do now
will be usable for years to come, from any (even future) language. And
it will be fast,
so it fixes the speed issue. There might be a better way to do that, we'll see.
I would like to see the benchmarks though.

Ondrej

[Vinzent Steinberg]

Another deal breaker to me is that loading modules can take like 30 seconds. And that is independent of any changes you made to the Julia source code of your module/script. When using c++, at least only the code that actually changed is compiled.

Vinzent

[Ondřej Čertík]

Exactly. But I think these technical issues can be fixed eventually?

Ondrej

[Joachim Durchholz]

Am 18.04.2014 20:56, schrieb F. B.:
>
> C/C++ were conceived in the 80's and have remained thus far the most
> optimized high-level languages.

Well, for a given definition of "most optimized" and "high-level"...

> Languages that appeared in the 90's are
> either scripted (like Python) or rely on a virtual machine (like Java).

No.
In fact, interesting numeric work is being done in OCaml and F#.

I'm under the impression that your views are biased by your personal
experience with a specific ecosystem.
This does not invalidate them, but they need to be validated by persons
with other perspective - at least as long a you're making broad,
sweeping statements that generalize over all languages.

> This is comprehensible: writing a compiler to machine code is a really hard
> task, even the translation to assembler alone is hard. Since the LLVM
> appeared, it is now much faster to write compilers, and lots of new
> programming languages are appearing based on the LLVM. I think that LLVM is
> a good infrastructure to allow new programming languages to appear.

Agreed.

> Julia's types are like those of C, multiple dispatching is done at
> compile-time rather than at run-time whenever it is possible,

This is actually the first optimization that all OO and functional
languages introduce.
It's massively harder to do in languages which do not give you a
reliable guarantee whether a given data structure is updatable in place
or not.

> for this I
> see no disadvantage over C in terms of performance.

This is a sweeping overgeneralized statement again - benchmarks or it
didn't happen.
From the compiler folks, I hear that the difference is how polymorphic
your code actually is. Lots of polymorphism -> fewer optimization
opportunities.
The SmallEiffel folks reported this optimization to apply to roughly 90%
of call sites in their SmallEiffel compiler. They did not measure the
percentage of call executions, unfortunately.
The Waterloo of this optimization would be a tight loop where the
compiler happened to not know enough about the potential types to
de-polymorphize a call.

Polymorphic calls prevent inlining, which in turn prevents most
optimizations. It's the reason why the C++ folks have sunk so much time
into doing type flow analysis.

> The problem I see is
> metaprogramming, Julia's code can be loaded as a data structure, and be
> recompiled at run-time. I fear this capability introduces some performance
> disadvantages over C, (despite being very useful), as the code has to keep
> some track of the original source code, but I'm not expert enough about
> compilation processes to judge that.

From my compilation background, I'd say:
- It's hard to get right because it's difficult to determine which
differences will affect the compiled binary and which don't.
- If it's done right, and recompilation happens just a few dozen of
times, the performance effect is negligible.
- Exception: If the run-time compiler spends a lot of time optimizing,
then each reloaded code may require more. That's why run-time compilers
usually do less optimization than ahead-of-time compilers.
- This also means that you usually have less optimization for
just-in-time compilers.
- The advantage of just-in-time compilers is that they can optimize for
the processor architecture at hand, which ahead-of-time compilers
usually can't or don't.

I.e. you essentially have to do benchmarks to see which of the various
counteracting effects have dominance.

> In any case, before starting a translation into Julia I would wait until:
>

> - someone introduces a clear way to call Julia code from Python
> (possibly through static compilation).
> - abstract types in Julia can have fields.
> - multiple inheritance support in Julia.
> - dot and __call__ operator overloading.

Now that's quite a list of things.

[Vinzent Steinberg]

On Friday, April 18, 2014 3:44:28 PM UTC-4, Ondřej Čertík wrote:

On Fri, Apr 18, 2014 at 1:32 PM, Vinzent Steinberg

[...]

> Another deal breaker to me is that loading modules can take like 30 seconds.
> And that is independent of any changes you made to the Julia source code of
> your module/script. When using c++, at least only the code that actually
> changed is compiled.

Exactly. But I think these technical issues can be fixed eventually?

Yes, hopefully they will do it like Python at one point (transparently caching the bytecode in .pyc files).

I'm just saying that I think it is not ready yet.

Vinzent