Opened 7 years ago

Closed 7 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:

Description

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 7 years ago by tkluck

  • Status changed from new to needs_review

comment:2 Changed 7 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:

to

if assumptions_list:

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

comment:3 Changed 7 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 7 years ago by tkluck

  • Status changed from needs_work to needs_review

comment:5 Changed 7 years ago by mhansen

Wrong patch?

comment:6 Changed 7 years ago by tkluck

Sorry, I fixed it.

comment:7 Changed 7 years ago by mhansen

  • Status changed from needs_review to positive_review

Looks good to me.

comment:8 Changed 7 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.