Opened 10 years ago

Closed 10 years ago

#13359 closed enhancement (fixed)

[Performance] Expression::__nonzero__ shouldn't call variables() unless it is necessary

Reported by: tkluck Owned by: tbd
Priority: major Milestone: sage-5.3
Component: performance Keywords:
Cc: Merged in: sage-5.3.beta2
Authors: Timo Kluck Reviewers: Mike Hansen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges


Expression::__nonzero__ calls variables() in case it needs assumptions:

# If assumptions are involved, falsification is more complicated...
need_assumptions = False
vars = self.variables()
if len(vars) > 0:
   from sage.symbolic.assumptions import assumptions
   assumption_list = assumptions()
   if len(assumption_list) > 0:
      # do something

Now, variables() is a recursive call that walks down the expression tree, so you really only want to do this when necessary. The attached patch changes the order of the if statements. In my case that involves lots of expression manipulations, the running time came down from 2 minutes to 2 seconds.

Background: I'm doing calculations in a LaurentSeriesRing over SR. The LaurentSeriesRing (and/or its underlying polynomial classes) liberally call __nonzero__ on the coefficients to see what the degree or valuation is, etc. So these comparisons are so much a part of my inner looop that I had to disable the test_relation calls and the Maxima calls. Those are hacks I cannot submit to the tracker, but this is the next bottleneck.

It should also be possible to improve the performance for variables by calculating it at construction time from the variables of the subexpressions. I've done some work in that direction, but that's a different story.

Change History (10)

comment:1 Changed 10 years ago by tkluck

  • Status changed from new to needs_review

comment:2 Changed 10 years ago by mhansen

  • Reviewers set to Mike Hansen
  • Status changed from needs_review to needs_work

As long as you're making a performance patch, you should change the statements like

if len(assumptions_list) > 0:


if assumptions_list:

and similarly with the "if len(vars) > 0" line.

comment:3 Changed 10 years ago by tkluck

Good suggestion, here's a patch.

This is a minor point in the sense that it doesn't affect the algorithm's complexity, but you're right that it's probably cheaper.

comment:4 Changed 10 years ago by tkluck

  • Status changed from needs_work to needs_review

comment:5 Changed 10 years ago by mhansen

Wrong patch?

comment:6 Changed 10 years ago by tkluck

Sorry, I fixed it.

comment:7 Changed 10 years ago by mhansen

  • Status changed from needs_review to positive_review

Looks good to me.

comment:8 Changed 10 years ago by jdemeyer

  • Merged in set to sage-5.3.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.