Opened 3 years ago

Closed 3 years ago

#23683 closed defect (fixed)

Speed up function field doctests

Reported by: saraedum Owned by:
Priority: major Milestone: sage-8.1
Component: commutative algebra Keywords:
Cc: chapoton, roed, xcaruso Merged in:
Authors: Julian Rüth Reviewers: Travis Scrimshaw, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: d3bd64c (Commits) Commit: d3bd64cdde8c75b43b767950885fb6ec2aeedd6a
Dependencies: Stopgaps:

Description (last modified by saraedum)

Followup to #23193.

Function field doctests take 10 minutes on reasonable machines. That's way too much. The changes introduced here drop this again to 7/70 seconds for the doctests/long doctests.

Change History (26)

comment:1 Changed 3 years ago by saraedum

  • Branch set to u/saraedum/speed_up_function_field_doctests

comment:2 Changed 3 years ago by saraedum

  • Commit set to bf5f0a86b4d36e4967e63e0d894b3e059df3b878
  • Status changed from new to needs_review

New commits:

bf5f0a8Limit runs of function field test suites

comment:3 Changed 3 years ago by saraedum

  • Description modified (diff)

comment:4 Changed 3 years ago by saraedum

  • Authors set to Julian Rüth
  • Cc chapoton added

comment:5 Changed 3 years ago by chapoton

I think you should rather reduce the length of "some_elements" to at most 5 or 6. I have not chekced the current length, but it is probably much too long. IT was 3 before the ticket that caused the "long-time doctest" problem.

comment:6 Changed 3 years ago by saraedum

Why should some_elements be so short? This is precisely why we introduced max_runs in the first place. If I would write some_elements() manually, I would centainly come up with a list much longer than that. We actually find lots of bugs with having long some_elements lists in say p-adics code.

Last edited 3 years ago by saraedum (previous) (diff)

comment:7 Changed 3 years ago by chapoton

ok, I did not know about max_runs.

comment:8 follow-up: Changed 3 years ago by saraedum

The length is typically about 50. The problem is that some doctests consider squares or triples of these. I think that max_runs is the way to go to make these doctests fast enough.

comment:9 in reply to: ↑ 8 Changed 3 years ago by tscrim

Replying to saraedum:

The length is typically about 50. The problem is that some doctests consider squares or triples of these. I think that max_runs is the way to go to make these doctests fast enough.

-1 because it doesn't get the same sort of coverage as to using 5-10 elements. E.g., it only does x0 * (y * z) == (x0 * y) * z for a fixed x0, which maybe too simple. So IMO, it is better to do a subset of some_elements (passed via elements to the TestSuite) to make sure you get more complicated elements tested, which is part of the reason you have these more complicated some_elements(), right?

Really, some_elements() is designed primarily for testing rather than to tell the user something. So having smaller number of some_elements(), but having those elements be "interesting" (in an appropriate definition), is what I think it should be.

comment:10 follow-up: Changed 3 years ago by saraedum

I think this is a problem of some_elements or the doctests that use pairs and triples. Either some_elements should not just select the first few, or the doctests should generate the product in a more "interesting" fashion.

comment:11 Changed 3 years ago by saraedum

I am strongly opposed to shorten some_elements. As I said, having some_elements be long has proved very useful in the past. Of course, if the pairs tested are not "interesting" that is very bad.

comment:12 Changed 3 years ago by saraedum

This is now #23686.

comment:13 in reply to: ↑ 10 Changed 3 years ago by tscrim

Replying to saraedum:

I think this is a problem of some_elements or the doctests that use pairs and triples. Either some_elements should not just select the first few, or the doctests should generate the product in a more "interesting" fashion.

That would be an overengineered solution: you create a long list just to make a shorter list by sampling, which in turn, does not guarantee you get good elements. We could randomize this, but then you could have things that look like heisenbugs. So I do not think it makes any sense to have something like _test_associative to not go through all triples of the testing elements.

comment:14 follow-up: Changed 3 years ago by saraedum

  • Cc roed xcaruso added

I can write down manually a lot of interesting elements in a p-adic ring that I would want tests to be run for. There are so many weird corner cases with precision in particular in extensions that you do not want to shorten these lists. Of course you can not test everything in all triples but that's ok. I still want almost everything be tested for the individual elements and pairs. (Actually p-adic some_elements is not so large yet because (as far as I recall) when we wrote it max_runs was not ready yet.) What is wrong about not just taking the plain cartesian product but do some deterministic sampling? How we implement that is a different question. I believe there are a few viable options by either adapting the tests or have some_elements detect that it is being queried for a prouduct.

comment:15 in reply to: ↑ 14 ; follow-up: Changed 3 years ago by tscrim

Replying to saraedum:

What is wrong about not just taking the plain cartesian product but do some deterministic sampling?

Because then you have fundamentally no control over the elements that are chosen and it can defeat the entire purpose of having a few interesting elements. Say you want 4 relatively trivial elements and 1 very complicated element in order to test interesting examples but it is too slow otherwise (perhaps in reality it would be 2x or 3x these particular numbers). It is very likely that you would sample only the trivial elements, but you would have no idea that those were the ones sampled, much less have any clear (or even feasible) way to change that. If you want to sample elements, then you sample the elements and pass them to the TestSuite. However, you have to do that for every such test, so the best solution is to make some_elements smaller and instead pass elements with more complicated elements for those other more fundamental tests.

comment:16 follow-up: Changed 3 years ago by chapoton

Whatever solution is chosen at the end, you should not remove the real time indications in the comments, but update them.

comment:17 Changed 3 years ago by chapoton

I would prefer to see this solved, even if in a bad way, than to stay unsolved any second longer.

comment:18 in reply to: ↑ 15 Changed 3 years ago by saraedum

Replying to tscrim:

Replying to saraedum:

What is wrong about not just taking the plain cartesian product but do some deterministic sampling?

Because then you have fundamentally no control over the elements that are chosen and it can defeat the entire purpose of having a few interesting elements. Say you want 4 relatively trivial elements and 1 very complicated element in order to test interesting examples but it is too slow otherwise (perhaps in reality it would be 2x or 3x these particular numbers). It is very likely that you would sample only the trivial elements, but you would have no idea that those were the ones sampled, much less have any clear (or even feasible) way to change that. If you want to sample elements, then you sample the elements and pass them to the TestSuite. However, you have to do that for every such test, so the best solution is to make some_elements smaller and instead pass elements with more complicated elements for those other more fundamental tests.

I don't understand. How can I pass in pairs and triples of elements to the TestSuite?? I also don't understand the proposal apart from that technicality. If I follow what you propose, then I pass in a long list of elements to most test (the ones that are linear in the number of elements) and just use the default some_elements for the tests that use pairs and triples?

comment:19 follow-up: Changed 3 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

I've been talking with David at Days 88 about this, and I realized that I wasn't clear that I am not opposed to the current branch as a short-term solution. Julian, if you could update the timings, I will set a positive review.

Also, David and I discussed implementing a sampling feature to the TestSuite that would not be run by default, but by passing another argument to TestSuite that would only be used when the number of elements was bigger than max_runs.

comment:20 Changed 3 years ago by git

  • Commit changed from bf5f0a86b4d36e4967e63e0d894b3e059df3b878 to a931f35fa05980baa5fdce9fb555b569edabe05c

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

a931f35Put long time timing back in

comment:21 in reply to: ↑ 16 Changed 3 years ago by saraedum

Replying to chapoton:

Whatever solution is chosen at the end, you should not remove the real time indications in the comments, but update them.

Ok. I put indications back in.

comment:22 in reply to: ↑ 19 ; follow-up: Changed 3 years ago by saraedum

Replying to tscrim:

I've been talking with David at Days 88 about this, and I realized that I wasn't clear that I am not opposed to the current branch as a short-term solution. Julian, if you could update the timings, I will set a positive review.

Ok. Cool.

Also, David and I discussed implementing a sampling feature to the TestSuite that would not be run by default, but by passing another argument to TestSuite that would only be used when the number of elements was bigger than max_runs.

Could you elaborate or maybe rather comment on the followup ticket?

comment:23 in reply to: ↑ 22 Changed 3 years ago by tscrim

Replying to saraedum:

Replying to tscrim:

I've been talking with David at Days 88 about this, and I realized that I wasn't clear that I am not opposed to the current branch as a short-term solution. Julian, if you could update the timings, I will set a positive review.

Ok. Cool.

Minor typo: # long timeA (10s); you can set a positive review once fixed.

Also, David and I discussed implementing a sampling feature to the TestSuite that would not be run by default, but by passing another argument to TestSuite that would only be used when the number of elements was bigger than max_runs.

Could you elaborate or maybe rather comment on the followup ticket?

I believe David (Roe) will post the followup ticket with perhaps more details and/or a first implementation. What we agreed upon was basically the following:

  • if some_elements()^N > max_runs and something like max_samples or sampling=True was passed:
    • do sampling
  • else:
    • use the direct iterator

As far as sampling goes, in order to do "good" sampling, we would need to decide upon a convention for where in some_elements the more "interesting" objects are at the end and we sample more heavily from there.

Something that I have used the TestSuite for is to increase the max_runs and fix failures as more interesting elements come up. So I needed that to behave in a more deterministic way as with sampling, it could be nice for N but fail for N-1 because of the elements used. I also like it to work for infinite (enumerated) sets as well.

comment:24 Changed 3 years ago by roed

The followup is #23724. I'm happy for feedback on the approach taken there.

comment:25 Changed 3 years ago by chapoton

  • Branch changed from u/saraedum/speed_up_function_field_doctests to public/23683
  • Commit changed from a931f35fa05980baa5fdce9fb555b569edabe05c to d3bd64cdde8c75b43b767950885fb6ec2aeedd6a
  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Frédéric Chapoton
  • Status changed from needs_review to positive_review

after correcting the typo, I am setting to positive


New commits:

d3bd64cfix typo

comment:26 Changed 3 years ago by vbraun

  • Branch changed from public/23683 to d3bd64cdde8c75b43b767950885fb6ec2aeedd6a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.