#23592 closed enhancement (fixed)

Faster comparison of manifold points

Reported by: egourgoulhon Owned by:
Priority: major Milestone: sage-8.1
Component: geometry Keywords: manifold point
Cc: karimvanaelst, tscrim Merged in:
Authors: Eric Gourgoulhon Reviewers: David Roe
Report Upstream: N/A Work issues:
Branch: 48a66fc (Commits) Commit: 48a66fcc1282ca7749d69550a15c60d0ae56c3de
Dependencies: Stopgaps:

Description

Comparison of manifold points, as implemented in ManifoldPoint.__eq__, relies on comparison of coordinate values in a common chart. When coordinates are symbolic, this goes through Maxima and can take a lot of time. Now, comparison of points is involved in the unique representation of tangent spaces. When many tangent spaces are created (as for instance when plotting a vector field), this has a non-neglible cost. This ticket makes ManifoldPoint.__eq__ faster by invoking (a-b).is_trivial_zero() when a and b are symbolic coordinates of two points, while the previous version was using a == b. Note that for non-symbolic values (i.e. numerical values), a == b is still used.

Change History (13)

comment:1 Changed 16 months ago by egourgoulhon

  • Branch set to public/manifolds/point_comparison-23592
  • Commit set to 34472e89cfdb36f96937cfdfd73b902e879d720d

New commits:

34472e8Faster comparison of manifold points

comment:2 Changed 16 months ago by egourgoulhon

  • Cc karimvanaelst tscrim added
  • Status changed from new to needs_review

comment:3 follow-up: Changed 16 months ago by roed

Shouldn't you also short-circuit the for loop in case you ever get False?

comment:4 Changed 16 months ago by git

  • Commit changed from 34472e89cfdb36f96937cfdfd73b902e879d720d to bd717d91f2edc087036328d55d0b02627fbd0914

Branch pushed to git repo; I updated commit sha1. New commits:

bd717d9Better comparison of manifold points

comment:5 in reply to: ↑ 3 Changed 16 months ago by egourgoulhon

Replying to roed:

Shouldn't you also short-circuit the for loop in case you ever get False?

You are perfectly right! Thanks for pointing this. The latest commit takes it into account.

comment:6 follow-up: Changed 16 months ago by roed

The only other comment that I have is that you have three nested if statements, e.g.

if isinstance(diff_c, Expression):
    if not diff_c.is_trivial_zero():
        return False

I think it's clearer if such statements are phrased as

if isinstance(diff_c, Expression) and not diff_c.is_trivial_zero():
    return False

since there are fewer nested blocks this way.

Other than that, looks good once tests pass!

comment:7 in reply to: ↑ 6 ; follow-up: Changed 16 months ago by egourgoulhon

Replying to roed:

The only other comment that I have is that you have three nested if statements, e.g.

if isinstance(diff_c, Expression):
    if not diff_c.is_trivial_zero():
        return False

I think it's clearer if such statements are phrased as

if isinstance(diff_c, Expression) and not diff_c.is_trivial_zero():
    return False

since there are fewer nested blocks this way.

I wrote it with nested blocks because is_trivial_zero() is implemented only for instances of Expression. Is it safe to assume that the second form will never return any attribute error? i.e. that the test following the and is performed only if the test preceding the and is passed? (maybe this is guaranted by Python standard rules)

Other than that, looks good once tests pass!

The failures reported by the patchbot do not pertain to this ticket; on my computer all tests passed within Sage 8.1.beta1.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 16 months ago by roed

Replying to egourgoulhon:

Replying to roed:

The only other comment that I have is that you have three nested if statements, e.g.

if isinstance(diff_c, Expression):
    if not diff_c.is_trivial_zero():
        return False

I think it's clearer if such statements are phrased as

if isinstance(diff_c, Expression) and not diff_c.is_trivial_zero():
    return False

since there are fewer nested blocks this way.

I wrote it with nested blocks because is_trivial_zero() is implemented only for instances of Expression. Is it safe to assume that the second form will never return any attribute error? i.e. that the test following the and is performed only if the test preceding the and is passed? (maybe this is guaranted by Python standard rules)

Yep, Python supports short-circuit evaluation for and and or.

comment:9 Changed 16 months ago by git

  • Commit changed from bd717d91f2edc087036328d55d0b02627fbd0914 to 48a66fcc1282ca7749d69550a15c60d0ae56c3de

Branch pushed to git repo; I updated commit sha1. New commits:

48a66fcSlight code simplification in manifold point comparison

comment:10 in reply to: ↑ 8 Changed 16 months ago by egourgoulhon

Replying to roed:

Yep, Python supports short-circuit evaluation for and and or.

Very good, thanks. I've updated the code accordingly. I've also slightly simplified it, since there was no need to create a list of coordinate differences.

comment:11 follow-up: Changed 16 months ago by roed

  • Reviewers set to David Roe
  • Status changed from needs_review to positive_review

The errors all have to do with docbuilding, which clearly isn't your faults since you don't edit any documentation.

Looks good to me.

comment:12 in reply to: ↑ 11 Changed 16 months ago by egourgoulhon

Replying to roed:

The errors all have to do with docbuilding, which clearly isn't your faults since you don't edit any documentation.

Looks good to me.

Thanks for the review!

comment:13 Changed 16 months ago by vbraun

  • Branch changed from public/manifolds/point_comparison-23592 to 48a66fcc1282ca7749d69550a15c60d0ae56c3de
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.