#28365 closed defect (fixed)

Use something instead of time() to ensure Manifold uniqueness in tests

Reported by: embray Owned by:
Priority: major Milestone: sage-8.9
Component: geometry Keywords: manifolds
Cc: egourgoulhon, slelievre Merged in:
Authors: Erik Bray Reviewers: Eric Gourgoulhon
Report Upstream: N/A Work issues:
Branch: 4415117 (Commits) Commit: 44151171e686458ff382285357f8580527996d73
Dependencies: Stopgaps:

Description

As discussed in #28331, specifically ticket:28331#comment:9, the Manifold constructor uses unique_tag=getrandbits(128)*time() to ensure all returned manifolds are unique instances.

I'm not exactly sure why time() is used, except for the fact that in the doctests, the random seed is reset to 0 (so the getrandbits is not useful from test case to case case). However, on some systems time() is not high-enough resolution to change from case to case as well.

Perhaps it would be better to either use a different random number that is not re-seeded. Or use a monotonic clock or even just a monotonically increasing integer for each manifold...?

Change History (14)

comment:1 follow-up: Changed 16 months ago by embray

Note: On Python 3 (specifically 3.4+) there is new monotonic clock support. For Python 2.7 there is a backport: https://pypi.org/project/monotonic/

comment:2 in reply to: ↑ description ; follow-up: Changed 16 months ago by jdemeyer

Replying to embray:

a monotonically increasing integer for each manifold

Sounds like the best solution, unless this needs to be cryptographically secure :-)

comment:3 in reply to: ↑ 1 Changed 16 months ago by embray

Replying to embray:

Note: On Python 3 (specifically 3.4+) there is new monotonic clock support. For Python 2.7 there is a backport: https://pypi.org/project/monotonic/

Though it seems on Windows/Cygwin? this is still not good-enough resolution.

comment:4 in reply to: ↑ 2 ; follow-up: Changed 16 months ago by embray

Replying to jdemeyer:

Replying to embray:

a monotonically increasing integer for each manifold

Sounds like the best solution, unless this needs to be cryptographically secure :-)

Yup. Was just discussing this with Samuel and it seems obvious now that we think about it. Just want to confirm that Eric that the use of time() is merely to guarantee uniqueness (in which case, it is not a good guarantee of uniqueness :)

comment:5 Changed 16 months ago by embray

  • Authors set to Erik Bray
  • Branch set to public/ticket-28365
  • Commit set to 44151171e686458ff382285357f8580527996d73
  • Status changed from new to needs_review

Here's a version of the workaround I mentioned. I'm not even really sure the getrandbits is necessary either, but I'm not sure so I left it for now. Could even keep time() but again, it's not clear it's really needed.


New commits:

4415117Trac #28365: Use a unique integer ID instead of time() to ensure manifold uniqueness in the doctest framework.

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

Replying to embray:

Replying to jdemeyer:

Replying to embray:

a monotonically increasing integer for each manifold

Sounds like the best solution, unless this needs to be cryptographically secure :-)

Yup. Was just discussing this with Samuel and it seems obvious now that we think about it. Just want to confirm that Eric that the use of time() is merely to guarantee uniqueness (in which case, it is not a good guarantee of uniqueness :)

Yes the use of time() was only a (bad!) attempt to guarantee uniqueness. Combining it with getrandbits(128) was naively thought as a security in case two successive calls of time() occur with a time separation too small to be resolved. The use of the monotonically increasing integer as in you implemented in the above commit seems a much more robust solution.

In the long term, I think we should get rid of the UniqueRepresentation for manifolds, except for those that do have a mathematically meaningful unique representation, like EuclideanSpace. Having manifolds inherit from UniqueRepresentation was a hack to make pickling work easily, which is required for parallelized computations via multiprocessing.

Last edited 16 months ago by slelievre (previous) (diff)

comment:7 in reply to: ↑ 6 Changed 16 months ago by embray

Replying to egourgoulhon:

Replying to embray:

Replying to jdemeyer:

Replying to embray:

a monotonically increasing integer for each manifold

Sounds like the best solution, unless this needs to be cryptographically secure :-)

Yup. Was just discussing this with Samuel and it seems obvious now that we think about it. Just want to confirm that Eric that the use of time() is merely to guarantee uniqueness (in which case, it is not a good guarantee of uniqueness :)

In the long term, I think we should get rid of the UniqueRepresentation for manifolds, except for those that do have a mathematically meaningful unique representation, like EuclideanSpace. Having manifolds inherit from UniqueRepresentation was a hack to make pickling work easily, which is required for parallelized computations via multiprocessing.

Yes, that doesn't seem like a good enough justification, given that pickling can be done elsewise. Though as you say, having an easy way to construct specific manifolds that should be globally unique would be good too.

comment:8 follow-up: Changed 16 months ago by embray

Specifically, what problems did you encounter with pickling of manifolds that UniqueRepresentation was able to solve?

comment:9 follow-up: Changed 16 months ago by egourgoulhon

  • Status changed from needs_review to positive_review

LGTM. Thanks!

Does this solve the issue with Cygwin/Windows 7 reported in ticket:28331#comment:5 ? If yes, it seems to me that getrandbits is somehow broken on this computer, because it should have solved the degeneracy in time(): in the same session, two successive calls to getrandbits(128) are very unlikely to return the same value, aren't they?

comment:10 Changed 16 months ago by egourgoulhon

  • Reviewers set to Eric Gourgoulhon

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

Replying to embray:

Specifically, what problems did you encounter with pickling of manifolds that UniqueRepresentation was able to solve?

Well, this was some time ago and I have to figure out again what the problems were... Basically, manifolds are objects that are constructed on the fly, with the user adding open subsets, charts and vector frames at any time.

Last edited 16 months ago by egourgoulhon (previous) (diff)

comment:12 in reply to: ↑ 9 ; follow-up: Changed 16 months ago by slelievre

Replying to egourgoulhon:

Does this solve the issue with Cygwin/Windows 7 reported in ticket:28331#comment:5 ? If yes, it seems to me that getrandbits is somehow broken on this computer, because it should have solved the degeneracy in time(): in the same session, two successive calls to getrandbits(128) are very unlikely to return the same value, aren't they?

When running tests, the doctesting framework resets the random seed to 0 at each new doctest, in order to ensure reproducibility of doctests!

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

Replying to slelievre:

Replying to egourgoulhon:

Does this solve the issue with Cygwin/Windows 7 reported in ticket:28331#comment:5 ? If yes, it seems to me that getrandbits is somehow broken on this computer, because it should have solved the degeneracy in time(): in the same session, two successive calls to getrandbits(128) are very unlikely to return the same value, aren't they?

When running tests, the doctesting framework resets the random seed to 0 at each new doctest, in order to ensure reproducibility of doctests!

Ah I see... I was not aware of this point. Thanks for explaining it!

comment:14 Changed 15 months ago by vbraun

  • Branch changed from public/ticket-28365 to 44151171e686458ff382285357f8580527996d73
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.