Opened 19 months ago
Closed 18 months ago
#23592 closed enhancement (fixed)
Faster comparison of manifold points
Reported by:  egourgoulhon  Owned by:  

Priority:  major  Milestone:  sage8.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 nonneglible cost. This ticket makes ManifoldPoint.__eq__
faster by invoking (ab).is_trivial_zero()
when a
and b
are symbolic coordinates of two points, while the previous version was using a == b
. Note that for nonsymbolic values (i.e. numerical values), a == b
is still used.
Change History (13)
comment:1 Changed 19 months ago by
 Branch set to public/manifolds/point_comparison23592
 Commit set to 34472e89cfdb36f96937cfdfd73b902e879d720d
comment:2 Changed 19 months ago by
 Cc karimvanaelst tscrim added
 Status changed from new to needs_review
comment:3 followup: ↓ 5 Changed 19 months ago by
Shouldn't you also shortcircuit the for loop in case you ever get False?
comment:4 Changed 19 months ago by
 Commit changed from 34472e89cfdb36f96937cfdfd73b902e879d720d to bd717d91f2edc087036328d55d0b02627fbd0914
Branch pushed to git repo; I updated commit sha1. New commits:
bd717d9  Better comparison of manifold points

comment:5 in reply to: ↑ 3 Changed 19 months ago by
Replying to roed:
Shouldn't you also shortcircuit 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 followup: ↓ 7 Changed 19 months ago by
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 ; followup: ↓ 8 Changed 19 months ago by
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 FalseI think it's clearer if such statements are phrased as
if isinstance(diff_c, Expression) and not diff_c.is_trivial_zero(): return Falsesince 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 ; followup: ↓ 10 Changed 19 months ago by
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 FalseI think it's clearer if such statements are phrased as
if isinstance(diff_c, Expression) and not diff_c.is_trivial_zero(): return Falsesince there are fewer nested blocks this way.
I wrote it with nested blocks because
is_trivial_zero()
is implemented only for instances ofExpression
. Is it safe to assume that the second form will never return any attribute error? i.e. that the test following theand
is performed only if the test preceding theand
is passed? (maybe this is guaranted by Python standard rules)
Yep, Python supports shortcircuit evaluation for and
and or
.
comment:9 Changed 19 months ago by
 Commit changed from bd717d91f2edc087036328d55d0b02627fbd0914 to 48a66fcc1282ca7749d69550a15c60d0ae56c3de
Branch pushed to git repo; I updated commit sha1. New commits:
48a66fc  Slight code simplification in manifold point comparison

comment:10 in reply to: ↑ 8 Changed 19 months ago by
Replying to roed:
Yep, Python supports shortcircuit evaluation for
and
andor
.
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 followup: ↓ 12 Changed 19 months ago by
 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 19 months ago by
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 18 months ago by
 Branch changed from public/manifolds/point_comparison23592 to 48a66fcc1282ca7749d69550a15c60d0ae56c3de
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Faster comparison of manifold points