[lit] Sort test start times based on prior test timing data

[davezarzycki]

Summary

Lit as it exists today has three hacks that allow users to run tests earlier:

1. An entire test suite can set the is_early boolean.
2. A very recently introduced "early_tests" feature.
3. The --incremental flag forces failing tests to run first.

All of these approaches have problems.

1. The is_early feature was until very recently undocumented. Nevertheless it still lacks testing and is a imprecise way of optimizing test starting times.
2. The early_tests feature requires manual updates and doesn't scale.
3. --incremental is undocumented, untested, and it requires modifying the *source* file system by "touching" the file. This "touch" based approach is arguably a hack because it confuses editors (because it looks like the test was modified behind the back of the editor) and "touching" the test source file doesn't work if the test suite is read only from the perspective of lit (via advanced filesystem/build tricks).

This patch attempts to simplify and address all of the above problems.

This patch formalizes, documents, tests, and defaults lit to recording the execution time of tests and then reordering all tests during the next execution. By reordering the tests, high core count machines run faster, sometimes significantly so.

This patch also always runs failing tests first, which is a positive user experience win for those that didn't know about the hidden --incremental flag.

Finally, if users want, they can _optionally_ commit the test timing data (or a subset thereof) back to the repository to accelerate bots and first-time runs of the test suite.

[davezarzycki]

Whoops. A couple regression were introduced when I tried to simplify this patch before posting it. Please don't try this yet.

[lebedev.ri]

Nice!
I think this should also be used to improve the ETA time prediction.

Q: Where are these time files stored? I think it would not be good to store them next to the tests themselves.

[davezarzycki]

In D98179#2611438, @lebedev.ri wrote:

Nice!
I think this should also be used to improve the ETA time prediction.

Q: Where are these time files stored? I think it would not be good to store them next to the tests themselves.

There is a dot file named .lit_test_times.txt that lives in the output directory, a.k.a. the "exec_root" as far as lit is concerned. This same file can also *optionally* live alongside the lit.cfg files in the "source_root". In short, lit checks the exec_root first and then falls back to the source_root.

[mehdi_amini]

LGTM!
In general a bit more code documentation could be nice. It seems all obvious in the context of this patch, but someone reading the codebase may not find this as trivial as it seems.

llvm/utils/lit/lit/cl_arguments.py

157

Seems like you deprecated the option, can you update the doc to reflect it?

llvm/utils/lit/lit/discovery.py

144

Maybe add a if litConfig.debug: trace here?

[davezarzycki]

llvm/utils/lit/lit/cl_arguments.py

157

I still can't find any documentation for --incremental. What am I missing?

[davezarzycki]

I believe I've addressed all of the feedback to date.

I've also fixed the regression. I had hoped to avoid adding test_times as a parameter to a bunch of methods, but adding that dictionary to the test suite makes lit effectively single threaded as the worker threads fought over what I assume is the global python interpreter lock.

[mehdi_amini]

llvm/utils/lit/lit/cl_arguments.py

157

Sorry I wasn't clear: I meant the "help" field here.

[yln]

Very happy with the patch! Thanks for all your hard work! :)
I have a few small nits and one ask: can we model "test failed" explicitly instead of making their execution time really large?

llvm/utils/lit/lit/discovery.py

141

Use os.path.join(...)

145–149

Use Python's with statement

llvm/utils/lit/lit/main.py

108

I think it would be sufficient here to pass in the tests that we attempted to run.

166

Really like all the simplifications this enabled! :)

210

Is it possible to directly pass the display callback here now (and remove the local progress_callback())?

267–268

Can we explicitly model this part in code instead of increasing the execution time of failed tests? We can use the test.result.code property.

271–272

Not really needed and can be removed, right?

274–283

Using Python's with and os.path and string interpolation

llvm/utils/lit/tests/Inputs/reorder/.lit_test_times.txt

4

Clarifying my above comment:

PASS 3.0 subdir/ccc.txt
FAIL 2.0 bbb.txt

[jhenderson]

In D98179#2615130, @yln wrote:

can we model "test failed" explicitly instead of making their execution time really large?

I am strongly in favour of this, if it can be done. My team have wanted an option to rerun just failing tests, so being able to distinguish between those tests that failed and those that passed in the previous run would basically solve this (after a new option has been added to lit). When I say "failed" here, I actually mean XPASSes and failures that weren't XFAILs (plus UNRESOLVED etc). Running a subset of the lit testsuite would augment these results, rather than trash them (i.e. tests outside the subset would still be considered as failing until such time as they get run and then pass). I'm not asking for this retry mechanism to be implemented as part of that, but if this change can be made to work such that the retry feature is able to easily build on top of that, that would be great.

[davezarzycki]

I believe I have addressed all of the feedback to date.

For people that care about easily identifying the failures from the previous testing run, that is now encoded via the sign of the test time (please remember that negative test times are impossible). For example:

3.14159 a-successful-test.txt
-2.71828 a-failed-test.txt

I've also implemented but commented out how one might use this to implement --only-failures. Feedback would be appreciated but I don't want to derail this change proposal on what should be an independent change.

Finally, python is not my native programming language, so thank you for helping me with idiomatic changes. What I'd really like help with though is figuring out a way to not pass the prior test timing data down as a new parameter to various methods. I tried to hang the data off the test suite data structure but that had brutal performance side effects. It seemed like python was hammering on the global interpreter lock despite the prior timing data being unused after the sorting phase. Weird. Help would be greatly appreciated. Thanks!

[jhenderson]

I've skimmed the implementation, and it looks good to me, but I haven't got the time right now to review thoroughly. I'm pleased to see the ease of implementing "only-failures" on top of this too, thanks for illustrating.

llvm/utils/lit/lit/main.py

272

file is a builtin python type, so don't use it as a variable name. Just call it time_file or something like that.

[davezarzycki]

I renamed the file variable as requested.

I also found a workaround to the performance problem I referred to earlier. Now no new parameter is required during test discovery and therefore the diff is both simpler and more effective because now programmatic test creators get test record-and-replay support for free.

[davezarzycki]

I'm downgrading libcxx as a reviewer to non-blocking because the latest patch no longer requires changes to their project.

[jhenderson]

llvm/utils/lit/lit/Test.py

216

I believe you don't need the readlines() part of this line - my understanding is that you can iteratre over a file and it'll yield a line per iteration.

217

You an probably omit the first argument here, as demonstrated. That will split on the first sequence of whitespace.

llvm/utils/lit/lit/cl_arguments.py

154

I'd keep the old wording here and below (specifically "Start" -> "Run"). "Start" implies the tests might be started in a random order, but it may change mid run, which doesn't really make sense.

211

Maybe rather than "was ignored" use "is deprecated". Also "start" -> "run" as before.

llvm/utils/lit/lit/main.py

172

Perhaps worth a message with this assert to make it clear that the failure is due to an unknown TestOrder value.

270–271

Indentation here is inconsistent.

llvm/utils/lit/tests/reorder.py

2

I don't really understand what you mean by "starts" here. Do you mean something like "Check that we can change the test order."

Also, missing full stop.

[davezarzycki]

I've made all of the requested changes to date. Two notes:

1. One cannot simply omit the first argument to split() if the second is provided. As I just learned, python will complain. I switched the first parameter to None as a compromise.
2. For the record, I disagree with the use of the word "run" over "start" but this isn't something that I care enough about to resist changing the patch. Strictly speaking, lit only controls when tests start, not anything about how they run. With enough cores, tests will complete in a fairly predictable order despite any effort to start tests in a different order (or randomly).

[thopre]

In D98179#2621706, @davezarzycki wrote:

I've made all of the requested changes to date. Two notes:

1. One cannot simply omit the first argument to split() if the second is provided. As I just learned, python will complain. I switched the first parameter to None as a compromise.
2. For the record, I disagree with the use of the word "run" over "start" but this isn't something that I care enough about to resist changing the patch. Strictly speaking, lit only controls when tests start, not anything about how they run. With enough cores, tests will complete in a fairly predictable order despite any effort to start tests in a different order (or randomly).

That's odd, the documentation even contains such an example:

For example:
>>>

>>> '1,2,3'.split(',')
['1', '2', '3']
>>> '1,2,3'.split(',', maxsplit=1)
['1', '2,3']
>>> '1,2,,3,'.split(',')
['1', '2', '', '3', '']

[jhenderson]

llvm/utils/lit/lit/Test.py

217

There's a typo in my example: it should be maxsplit=1 (with the s). You need to use the argument name as shown. Example usage from my local python instance:

>>> s = '123 456 789'
>>> s.split(maxsplit=1)
['123', '456 789']

[davezarzycki]

I fixed the call to split as requested. Being unfamiliar with python, I didn't know that it supported keyword arguments / parameter labels. Thanks.

[davezarzycki]

Might somebody be willing to sign off on this change (this week or next)? I'd like to cherry-pick it to Swift's LLVM branch. Thanks for all the feedback so far.

[jhenderson]

In D98179#2626179, @davezarzycki wrote:

Might somebody be willing to sign off on this change (this week or next)? I'd like to cherry-pick it to Swift's LLVM branch. Thanks for all the feedback so far.

LGTM, but probably best to get someone else to confirm they're happy too.

llvm/utils/lit/lit/cl_arguments.py

159–161

Please delete this before pushing.

llvm/utils/lit/lit/main.py

74–75

Please delete this before pushing.

llvm/utils/lit/tests/shtest-shell.py

11

Nit

[davezarzycki]

Removed the commented only-failures and fixed a nit before committing.

Thanks everybody for the various rounds of feedback. I'm quite happy with how this turned out.

[jmorse]

Hi,

I'm experiencing reorder.py failing intermittently on a Windows system -- it seems to pick up the .lit_test_times.txt produced in the build directory for the Inputs tests after the first run, and use that for ordering. And seeing how that just contains noise, the Inputs tests are then run in the wrong order. Is this supposed to be accounted for already?

(I'm trying to produce something that reliably passes, but I'm not familiar with this part of lit).

[davezarzycki]

That implies a different testing environment. How different is the Windows testing environment compared to Unix? Do you specifically have a custom testing setup?

[davezarzycki]

Said differently, the Unix side seems to always run the lit tests from a fresh/clean setup, even for incremental builds. If Windows tests lit differently then ya, things will blow up.

[davezarzycki]

Try: 49d0e115d5df40aa89339f4ace7a8dee378c03bb

[jmorse]

It turns out there's a plain old windows-has-different-slashes problem going on. In the Test object __init__ method, the call to os.sep.join in this patch produces the string "subdir\ccc.txt", which won't match "subdir/ccc.txt" that you load from the the .lit_test_times.txt file. That then leads to no time being loaded for ccc.txt, and it gets mis-ordered.

I think the stale .lit_test_times.txt thing was a slight red-herring, but it's because my usual workflow is:

• run ninja check-llvm or similar to run all tests,
• run llvm-lit directly on any tests that fail

And without running ninja, the "preparing lit tests" step isn't performed, meaning .lit_test_times.txt isn't cleaned up. This means none of the buildbots are going to fail from a stale file as they always run all the tests, but it'll be a bit awkward for anyone running lit manually IMO. Making it idempotent would be highly appreciated!

(Edit: I've no idea why the public buildbots aren't suffering the path separator issue, but it's what I see on our internal test rig)

[davezarzycki]

Ah yes, of course. I've marked that test as unavailable on Window for now: 61ca706461c5e1edc18526c9ddc3250fe074ed94

In the long run, We'll need to figure out a way for people to commit cross-platform trace files but for now the more important record-and-reorder feature works cross platform.

[davezarzycki]

I've run out of time for today, but for the record, I think we should use slash as the canonical separator for the timing data file. The actual separator doesn't matter because these strings are never used as paths, just as keys into a dictionary. (Therefore any character would work.) This would let us harmonize the Unix and Windows timing data files.

[yln]

In D98179#2629578, @davezarzycki wrote:

... I think we should use slash as the canonical separator for the timing data file.

+1

[nlopes]

This patch makes the order of the list of failing tests non-deterministic. This is extremely annoying because you can't do a simple diff between test dumps anymore.
Before the list of failed tests used to be sorted.

Can we revert to the previous behavior please? The current behavior is not user friendly. Thanks!

[mehdi_amini]

Can we revert to the previous behavior please? The current behavior is not user friendly. Thanks!

To clarify: you care about the order in the final summary, not the actual execution order, right? (the goal of this patch is the latter, if it changes the former this is just a side-effect I believe)

How are you diffing? Copy-pasting the terminal output to a file? (I alway pipe these kind of list through sort before diffing them)

[nlopes]

In D98179#2638801, @mehdi_amini wrote:

Can we revert to the previous behavior please? The current behavior is not user friendly. Thanks!

To clarify: you care about the order in the final summary, not the actual execution order, right? (the goal of this patch is the latter, if it changes the former this is just a side-effect I believe)

I don't love that the default test order was changed. For our use case that isn't good, but I can just delete the .lit_test_times.txt file and get the old fixed order. (the reason why having a fixed order is good is because of timeouts. Also, slow tests often consume more memory in our setting, so it's not good to run all the slow tests at the same time).
So I'm just referring to the final summary, yes.

How are you diffing? Copy-pasting the terminal output to a file? (I alway pipe these kind of list through sort before diffing them)

No, I'm running lit and dumping into a file. sorting is not as easy as piping through sort, as I'm running with -vv (required). Anyway, sorting the list on lit side should be 1 line for some that knows where that line goes :)

[mehdi_amini]

No, I'm running lit and dumping into a file. sorting is not as easy as piping through sort, as I'm running with -vv (required).

Since tests run in parallel, don't you already have some non-determinism in the -vv output? Isn't it printing as test finish? (just curious, not pushing back on anything here).

Anyway, sorting the list on lit side should be 1 line for some that knows where that line goes :)

Yeah I agree that sorting on the lit side for the summary should be fairly easy!

[davezarzycki]

In D98179#2638882, @mehdi_amini wrote:

No, I'm running lit and dumping into a file. sorting is not as easy as piping through sort, as I'm running with -vv (required).

Since tests run in parallel, don't you already have some non-determinism in the -vv output? Isn't it printing as test finish? (just curious, not pushing back on anything here).

Right. Unless -j1 is passed to lit, then the lit output is, strictly speaking, non-deterministic. That being said (and especially on a quiet machine), I do understand why people might feel that the output is consistent enough from run to run to be quasi-deterministic.

Anyway, sorting the list on lit side should be 1 line for some that knows where that line goes :)

Yeah I agree that sorting on the lit side for the summary should be fairly easy!

As far as I can tell, the lit architecture likes to "pay-as-you-go" with test output, so there isn't a good place to sort the output and I'd wager that a lot of people would be upset if the test output stalled until completion for sorting reasons.

If people feel that deleting the test timing data is onerous (and IMHO, I don't think that's a big ask), then I think the simplest solution is to add a --ignore-timing-data option to lit that ignores test timing data and gives people the old behavior (for whatever reason).

But I don't think the *default* lit behavior should be to ignore test failures and ignore test timing data. Both of these are about making the out-of-the-box experience for people more productive. If people have reasons to run tests in specific orders, then let's talk about those needs and why a lexical sort was convenient.

[lebedev.ri]

@nlopes are you talking about sorting *all* lit output, or the summary?

[davezarzycki]

In D98179#2638837, @nlopes wrote:

In D98179#2638801, @mehdi_amini wrote:

Can we revert to the previous behavior please? The current behavior is not user friendly. Thanks!

To clarify: you care about the order in the final summary, not the actual execution order, right? (the goal of this patch is the latter, if it changes the former this is just a side-effect I believe)

I don't love that the default test order was changed. For our use case that isn't good, but I can just delete the .lit_test_times.txt file and get the old fixed order. (the reason why having a fixed order is good is because of timeouts. Also, slow tests often consume more memory in our setting, so it's not good to run all the slow tests at the same time).

Can you elaborate more about your usage of timeouts? As far as I know, the feature exists only to detect wildly broken tests. If reordering the tests causes timeouts to fire, then either the timeout is too aggressive or the tests themselves were on the edge of failure anyway and any "unrelated" change could cause them to fail.

As to the resource management challenges, lit has an undocumented "parallelism group" feature that would probably help you keep resource usage in check and would be more far appropriate than lexical execution order.

[nlopes]

I'm talking about sorting just the summary of failed tests, not the whole output. We need the whole -vv output, but that can be out of order.

Why are timeouts important? Our use case is running Alive2 with the test suite. Alive2 is heavy machinery and runs into timeouts. Running the tests in roughly the same order every time is important to avoid timeout tests flipping to failed or vice-versa. Plus slow tests = tests that consume a lot of memory (in our scenario), so we can't bundle slow tests together.
Adding a --ignore-timing-data would be great, yes! But I still feel that sorting the list of failed tests is important for user experience. I diff these all the time.

[lebedev.ri]

In D98179#2639476, @nlopes wrote:

I'm talking about sorting just the summary of failed tests, not the whole output. We need the whole -vv output, but that can be out of order.

Aha! +1 then, i think sorting summary should be both easy and nice to have.

[davezarzycki]

In D98179#2639483, @lebedev.ri wrote:

In D98179#2639476, @nlopes wrote:

I'm talking about sorting just the summary of failed tests, not the whole output. We need the whole -vv output, but that can be out of order.

Aha! +1 then, i think sorting summary should be both easy and nice to have.

Agreed. Try: 5cbe2279f723f1cca1a542d95e7d9760e4f52240

[davezarzycki]

In D98179#2639476, @nlopes wrote:

I'm talking about sorting just the summary of failed tests, not the whole output. We need the whole -vv output, but that can be out of order.

Why are timeouts important? Our use case is running Alive2 with the test suite. Alive2 is heavy machinery and runs into timeouts. Running the tests in roughly the same order every time is important to avoid timeout tests flipping to failed or vice-versa. Plus slow tests = tests that consume a lot of memory (in our scenario), so we can't bundle slow tests together.
Adding a --ignore-timing-data would be great, yes! But I still feel that sorting the list of failed tests is important for user experience. I diff these all the time.

That still sounds incredibly brittle. If there is any variety in test machine performance, then any and all attempts at sorting should be futile because the underlying hardware will perturb different timeouts. Is this not your experience? How do you reconcile hardware performance and configuration details (like SMT) with timeout settings?

[nlopes]

In D98179#2639491, @davezarzycki wrote:

In D98179#2639476, @nlopes wrote:

Why are timeouts important? Our use case is running Alive2 with the test suite. Alive2 is heavy machinery and runs into timeouts. Running the tests in roughly the same order every time is important to avoid timeout tests flipping to failed or vice-versa. Plus slow tests = tests that consume a lot of memory (in our scenario), so we can't bundle slow tests together.
Adding a --ignore-timing-data would be great, yes! But I still feel that sorting the list of failed tests is important for user experience. I diff these all the time.

That still sounds incredibly brittle. If there is any variety in test machine performance, then any and all attempts at sorting should be futile because the underlying hardware will perturb different timeouts. Is this not your experience? How do you reconcile hardware performance and configuration details (like SMT) with timeout settings?

Of course it's brittle :) Changing from a time-based setting to a ticks-based system is ongoing work, such that resource exhaustion becomes deterministic.
Nevertheless, on a same machine, we don't see many test flips. It's quite stable most of the times (just one test flip once in a while).

[davezarzycki]

In D98179#2639554, @nlopes wrote:

In D98179#2639491, @davezarzycki wrote:

In D98179#2639476, @nlopes wrote:

Why are timeouts important? Our use case is running Alive2 with the test suite. Alive2 is heavy machinery and runs into timeouts. Running the tests in roughly the same order every time is important to avoid timeout tests flipping to failed or vice-versa. Plus slow tests = tests that consume a lot of memory (in our scenario), so we can't bundle slow tests together.
Adding a --ignore-timing-data would be great, yes! But I still feel that sorting the list of failed tests is important for user experience. I diff these all the time.

That still sounds incredibly brittle. If there is any variety in test machine performance, then any and all attempts at sorting should be futile because the underlying hardware will perturb different timeouts. Is this not your experience? How do you reconcile hardware performance and configuration details (like SMT) with timeout settings?

Of course it's brittle :) Changing from a time-based setting to a ticks-based system is ongoing work, such that resource exhaustion becomes deterministic.
Nevertheless, on a same machine, we don't see many test flips. It's quite stable most of the times (just one test flip once in a while).

This seems really beyond the scope and purpose of sorting the tests.

If you don't mind and given that the workaround is trivial (delete the timing data), I'd like to hold off on adding --ignore-timing-data. If enough people complain then we can add that option. Is that okay with you?

[nlopes]

In D98179#2639565, @davezarzycki wrote:

In D98179#2639554, @nlopes wrote:

In D98179#2639491, @davezarzycki wrote:

In D98179#2639476, @nlopes wrote:

Why are timeouts important? Our use case is running Alive2 with the test suite. Alive2 is heavy machinery and runs into timeouts. Running the tests in roughly the same order every time is important to avoid timeout tests flipping to failed or vice-versa. Plus slow tests = tests that consume a lot of memory (in our scenario), so we can't bundle slow tests together.
Adding a --ignore-timing-data would be great, yes! But I still feel that sorting the list of failed tests is important for user experience. I diff these all the time.

That still sounds incredibly brittle. If there is any variety in test machine performance, then any and all attempts at sorting should be futile because the underlying hardware will perturb different timeouts. Is this not your experience? How do you reconcile hardware performance and configuration details (like SMT) with timeout settings?

Of course it's brittle :) Changing from a time-based setting to a ticks-based system is ongoing work, such that resource exhaustion becomes deterministic.
Nevertheless, on a same machine, we don't see many test flips. It's quite stable most of the times (just one test flip once in a while).

This seems really beyond the scope and purpose of sorting the tests.

If you don't mind and given that the workaround is trivial (delete the timing data), I'd like to hold off on adding --ignore-timing-data. If enough people complain then we can add that option. Is that okay with you?

Sounds good. Thanks for adding support for the summary sort!

[mstorsjo]

Something related to the time recording seems to fail intermittently on buildbots: https://lab.llvm.org/buildbot#builders/93/builds/2697

[lebedev.ri]

In D98179#2689075, @mstorsjo wrote:

Something related to the time recording seems to fail intermittently on buildbots: https://lab.llvm.org/buildbot#builders/93/builds/2697

I'll cut to the fix here: @davezarzycki is there any reason why the timing data is stored in a CSV format, and not JSON?
The fix is to switch to latter.

[davezarzycki]

In D98179#2689079, @lebedev.ri wrote:

In D98179#2689075, @mstorsjo wrote:

Something related to the time recording seems to fail intermittently on buildbots: https://lab.llvm.org/buildbot#builders/93/builds/2697

I'll cut to the fix here: @davezarzycki is there any reason why the timing data is stored in a CSV format, and not JSON?
The fix is to switch to latter.

What? Weird. The file isn't CSV. It's just a number followed by a space and then everything until the newline is the file name. Nothing fancy. Switching to JSON probably just means papering over the real problem which seems to be either that sometimes a test has an empty string for a name or that there is an edge case in python's number printing that can result in pure whitespace. We'd need to look at the timing data file to see why it's bogus (or corrupt).

llvm/docs/CommandGuide/lit.rst

 suites, summarizing their results, and providing indication of failures.
 :program:`lit` is designed to be a lightweight testing tool with as simple a
 user interface as possible.
 
 :program:`lit` should be run with one or more *tests* to run specified on the
 command line.  Tests can be either individual test files or directories to
 search for tests (see :ref:`test-discovery`).
 
-Each specified test will be executed (potentially in parallel) and once all
+Each specified test will be executed (potentially concurrently) and once all
 tests have been run :program:`lit` will print summary information on the number
 of tests which passed or failed (see :ref:`test-status-results`).  The
 :program:`lit` program will execute with a non-zero exit code if any tests
 fail.
 
 By default :program:`lit` will use a succinct progress display and will only
 print summary information for test failures.  See :ref:`output-options` for
 options controlling the :program:`lit` progress display and output.

  enabled, :program:`lit` will also automatically provide a "``vg_leak``"
  feature that can be used to conditionally disable (or expect failure in)
  certain tests.
 
 .. option:: --time-tests
 
  Track the wall time individual tests take to execute and includes the results
  in the summary output.  This is useful for determining which tests in a test
- suite take the most time to execute.  Note that this option is most useful
- with ``-j 1``.
+ suite take the most time to execute.
 
 .. option:: --ignore-fail
 
  Exit with status zero even if some tests fail.
 
 .. option:: --no-indirectly-run-check
 
  Do not error if a test would not be run if the user had specified the
  containing directory instead of naming the test directly.
 
 .. _selection-options:
 
 SELECTION OPTIONS
 -----------------
 
+By default, `lit` will run failing tests first, then run tests in descending
+execution time order to optimize concurrency.
+
+The timing data is stored in the `test_exec_root` in a file named
+`.lit_test_times.txt`. If this file does not exist, then `lit` checks the
+`test_source_root` for the file to optionally accelerate clean builds.
+
+.. option:: --shuffle
+
+ Run the tests in a random order, not failing/slowest first.
+
 .. option:: --max-failures N
 
  Stop execution after the given number ``N`` of failures.
  An integer argument should be passed on the command line
  prior to execution.
 
 .. option:: --max-tests=N
 

 
 .. option:: --run-shard=N
 
  Select which shard to run, assuming the ``--num-shards=M`` option was
  provided. The two options must be used together, and the value of ``N``
  must be in the range ``1..M``. The environment variable
  ``LIT_RUN_SHARD`` can also be used in place of this option.
 
-.. option:: --shuffle
-
- Run the tests in a random order.
-
 .. option:: --timeout=N
 
  Spend at most ``N`` seconds (approximately) running each individual test.
  ``0`` means no time limit, and ``0`` is the default. Note that this is not an
  alias for :option:`--max-time`; the two are different kinds of maximums.
 
 .. option:: --filter=REGEXP
 

  reported as unsupported.  Used by: *ShTest*.
 
  **parent** The parent configuration, this is the config object for the directory
  containing the test suite, or None.
 
  **root** The root configuration.  This is the top-most :program:`lit` configuration in
  the project.
 
- **is_early** Whether the test suite as a whole should be given a head start
- before other test suites run.
-
- **early_tests** An explicit set of '/' separated test paths that should be
- given a head start before other tests run. For example, the top five or so
- slowest tests. See also: `--time-tests`
-
  **pipefail** Normally a test using a shell pipe fails if any of the commands
  on the pipe fail. If this is not desired, setting this variable to false
  makes the test fail only if the last command in the pipe fails.
 
  **available_features** A set of features that can be used in `XFAIL`,
  `REQUIRES`, and `UNSUPPORTED` directives.
 
 TEST DISCOVERY

llvm/test/Unit/lit.cfg.py

 # -*- Python -*-
 
 # Configuration file for the 'lit' test runner.
 
 import os
 import subprocess
 
 import lit.formats
 
 # name: The name of this test suite.
 config.name = 'LLVM-Unit'
 
 # suffixes: A list of file extensions to treat as test files.
 config.suffixes = []
 
-# is_early; Request to run this suite early.
-config.is_early = True
-
 # test_source_root: The root path where tests are located.
 # test_exec_root: The root path where tests should be run.
 config.test_exec_root = os.path.join(config.llvm_obj_root, 'unittests')
 config.test_source_root = config.test_exec_root
 
 # testFormat: The test format to use to interpret tests.
 config.test_format = lit.formats.GoogleTest(config.llvm_build_mode, 'Tests')
 

llvm/utils/lit/lit/Test.py

class TestSuite:
 
     def __init__(self, name, source_root, exec_root, config):
         self.name = name
         self.source_root = source_root
         self.exec_root = exec_root
         # The test suite configuration.
         self.config = config
 
+        self.test_times = {}
+        test_times_file = os.path.join(exec_root, '.lit_test_times.txt')
+        if not os.path.exists(test_times_file):
+            test_times_file = os.path.join(source_root, '.lit_test_times.txt')
+        if os.path.exists(test_times_file):
+            with open(test_times_file, 'r') as time_file:
+                for line in time_file:
+                    time, path = line.split(maxsplit=1)
+                    self.test_times[path.strip('\n')] = float(time)
+
     def getSourcePath(self, components):
         return os.path.join(self.source_root, *components)
 
     def getExecPath(self, components):
         return os.path.join(self.exec_root, *components)
 
 class Test:
     """Test - Information on a single test instance."""
def __init__(self, suite, path_in_suite, config, file_path = None):
 
         # An optional number of retries allowed before the test finally succeeds.
         # The test is run at most once plus the number of retries specified here.
         self.allowed_retries = getattr(config, 'test_retry_attempts', 0)
 
         # The test result, once complete.
         self.result = None
 
+        # The previous test failure state, if applicable.
+        self.previous_failure = False
+
+        # The previous test elapsed time, if applicable.
+        self.previous_elapsed = 0.0
+
+        if os.sep.join(path_in_suite) in suite.test_times:
+            time = suite.test_times[os.sep.join(path_in_suite)]
+            self.previous_elapsed = abs(time)
+            self.previous_failure = time < 0
+
+
     def setResult(self, result):
         assert self.result is None, "result already set"
         assert isinstance(result, Result), "unexpected result type"
         try:
             expected_to_fail = self.isExpectedToFail()
         except ValueError as err:
             # Syntax error in an XFAIL line.
             result.code = UNRESOLVED
def getUsedFeatures(self):
             parsed[k] or [] for k in feature_keywords
         )
         tokens = itertools.chain.from_iterable(
             BooleanExpression.tokenize(expr) for expr in
                 boolean_expressions if expr != '*'
         )
         identifiers = set(filter(BooleanExpression.isIdentifier, tokens))
         return identifiers
-
-    def isEarlyTest(self):
-        """
-        isEarlyTest() -> bool
-
-        Check whether this test should be executed early in a particular run.
-        This can be used for test suites with long running tests to maximize
-        parallelism or where it is desirable to surface their failures early.
-        """
-        if '/'.join(self.path_in_suite) in self.suite.config.early_tests:
-            return True
-        return self.suite.config.is_early

llvm/utils/lit/lit/TestingConfig.py

def __init__(self, parent, name, suffixes, test_format,
         self.excludes = set(excludes)
         self.available_features = set(available_features)
         self.pipefail = pipefail
         self.standalone_tests = standalone_tests
         # This list is used by TestRunner.py to restrict running only tests that
         # require one of the features in this list if this list is non-empty.
         # Configurations can set this list to restrict the set of tests to run.
         self.limit_to_features = set(limit_to_features)
-        # Whether the suite should be tested early in a given run.
-        self.is_early = bool(is_early)
-        # List of tests to run early.
-        self.early_tests = {}
         self.parallelism_group = parallelism_group
         self._recursiveExpansionLimit = None
 
     @property
     def recursiveExpansionLimit(self):
         return self._recursiveExpansionLimit
 
     @recursiveExpansionLimit.setter

llvm/utils/lit/lit/cl_arguments.py

 import argparse
 import enum
 import os
 import shlex
 import sys
 
 import lit.reports
 import lit.util
 
 
 class TestOrder(enum.Enum):
-    EARLY_TESTS_THEN_BY_NAME = enum.auto()
-    FAILING_FIRST = enum.auto()
+    DEFAULT = enum.auto()
     RANDOM = enum.auto()
 
 
 def parse_args():
     parser = argparse.ArgumentParser(prog='lit')
     parser.add_argument('test_paths',
             nargs='+',
             metavar="TEST_PATH",
selection_group.add_argument("--max-tests",
             help="Maximum number of tests to run",
             type=_positive_int)
     selection_group.add_argument("--max-time",
             dest="timeout",
             metavar="N",
             help="Maximum time to spend testing (in seconds)",
             type=_positive_int)
     selection_group.add_argument("--shuffle",
             help="Run tests in random order",
             action="store_true")
     selection_group.add_argument("-i", "--incremental",
-            help="Run modified and failing tests first (updates mtimes)",
+            help="Run failed tests first (DEPRECATED: now always enabled)",
             action="store_true")
     selection_group.add_argument("--filter",
             metavar="REGEX",
             type=_case_insensitive_regex,
             help="Only run tests with paths matching the given regular expression",
             default=os.environ.get("LIT_FILTER", ".*"))
     selection_group.add_argument("--filter-out",
             metavar="REGEX",
             type=_case_insensitive_regex,
             help="Filter out tests with paths matching the given regular expression",
             default=os.environ.get("LIT_FILTER_OUT", "^$"))
     selection_group.add_argument("--xfail",
def parse_args():
     env_args = shlex.split(os.environ.get("LIT_OPTS", ""))
     args = sys.argv[1:] + env_args
     opts = parser.parse_args(args)
 
     # Validate command line options
     if opts.echoAllCommands:
         opts.showOutput = True
 
+    if opts.incremental:
+        print('WARNING: --incremental is deprecated. Failing tests now always run first.')
+
     if opts.shuffle:
         opts.order = TestOrder.RANDOM
-    elif opts.incremental:
-        opts.order = TestOrder.FAILING_FIRST
     else:
-        opts.order = TestOrder.EARLY_TESTS_THEN_BY_NAME
+        opts.order = TestOrder.DEFAULT
 
     if opts.numShards or opts.runShard:
         if not opts.numShards or not opts.runShard:
             parser.error("--num-shards and --run-shard must be used together")
         if opts.runShard > opts.numShards:
             parser.error("--run-shard must be between 1 and --num-shards (inclusive)")
         opts.shard = (opts.runShard, opts.numShards)
     else:

llvm/utils/lit/lit/discovery.py

if ts is None:
         litConfig.warning('unable to find test suite for %r' % path)
         return (),()
 
     if litConfig.debug:
         litConfig.note('resolved input %r to %r::%r' % (path, ts.name,
                                                         path_in_suite))
 
     return ts, getTestsInSuite(ts, path_in_suite, litConfig,
                                testSuiteCache, localConfigCache, indirectlyRunCheck)
 
 def getTestsInSuite(ts, path_in_suite, litConfig,
                     testSuiteCache, localConfigCache, indirectlyRunCheck):
     # Check that the source path exists (errors here are reported by the
     # caller).
     source_path = ts.getSourcePath(path_in_suite)
     if not os.path.exists(source_path):
         return
 
     # Check if the user named a test directly.
     if not os.path.isdir(source_path):
         test_dir_in_suite = path_in_suite[:-1]
         lc = getLocalConfig(ts, test_dir_in_suite, litConfig, localConfigCache)
         test = Test.Test(ts, path_in_suite, lc)
 
         # Issue a error if the specified test would not be run if
def find_tests_for_inputs(lit_config, inputs, indirectlyRunCheck):
     local_config_cache = {}
     for input in actual_inputs:
         prev = len(tests)
         tests.extend(getTests(input, lit_config, test_suite_cache,
                               local_config_cache, indirectlyRunCheck)[1])
         if prev == len(tests):
             lit_config.warning('input %r contained no tests' % input)
 
+    # This data is no longer needed but keeping it around causes awful
+    # performance problems while the test suites run.
+    for k, suite in test_suite_cache.items():
+      suite[0].test_times = None
+
     # If there were any errors during test discovery, exit now.
     if lit_config.numErrors:
         sys.stderr.write('%d errors, exiting.\n' % lit_config.numErrors)
         sys.exit(2)
 
     return tests

llvm/utils/lit/lit/main.py

if opts.maxIndividualTestTime is not None:  # `not None` is important (default: 0)
             lit_config.maxIndividualTestTime = opts.maxIndividualTestTime
 
     determine_order(discovered_tests, opts.order)
 
     selected_tests = [t for t in discovered_tests if
         opts.filter.search(t.getFullName()) and not
         opts.filter_out.search(t.getFullName())]
 
     if not selected_tests:
         sys.stderr.write('error: filter did not match any tests '
                          '(of %d discovered).  ' % len(discovered_tests))
         if opts.allow_empty_runs:
             sys.stderr.write("Suppressing error because '--allow-empty-runs' "
                              'was specified.\n')
             sys.exit(0)
         else:
             sys.stderr.write("Use '--allow-empty-runs' to suppress this "
                              'error.\n')
def main(builtin_params={}):
     mark_xfail(discovered_tests, opts)
 
     mark_excluded(discovered_tests, selected_tests)
 
     start = time.time()
     run_tests(selected_tests, lit_config, opts, len(discovered_tests))
     elapsed = time.time() - start
 
+    record_test_times(selected_tests, lit_config)
+
     if opts.time_tests:
         print_histogram(discovered_tests)
 
     print_results(discovered_tests, elapsed, opts)
 
     for report in opts.reports:
         report.write_results(tests_for_report, elapsed)
 
if show_suites:
             print('    Available Substitutions: %s' % substitutions)
 
     if show_tests:
         print('-- Available Tests --')
         for t in tests:
             print('  %s' % t.getFullName())
 
 
 def determine_order(tests, order):
     from lit.cl_arguments import TestOrder
-    if order == TestOrder.EARLY_TESTS_THEN_BY_NAME:
-        tests.sort(key=lambda t: (not t.isEarlyTest(), t.getFullName()))
-    elif order == TestOrder.FAILING_FIRST:
-        def by_mtime(test):
-            return os.path.getmtime(test.getFilePath())
-        tests.sort(key=by_mtime, reverse=True)
-    elif order == TestOrder.RANDOM:
+    if order == TestOrder.RANDOM:
         import random
         random.shuffle(tests)
-
-
-def touch_file(test):
-    if test.isFailure():
-        os.utime(test.getFilePath(), None)
+    else:
+        assert order == TestOrder.DEFAULT, 'Unknown TestOrder value'
+        tests.sort(key=lambda t: (not t.previous_failure, -t.previous_elapsed, t.getFullName()))
 
 
 def filter_by_shard(tests, run, shards, lit_config):
     test_ixs = range(run - 1, len(tests), shards)
     selected_tests = [tests[i] for i in test_ixs]
 
     # For clarity, generate a preview of the first few test indices in the shard
     # to accompany the arithmetic expression.
for t in excluded_tests:
         t.setResult(result)
 
 
 def run_tests(tests, lit_config, opts, discovered_tests):
     workers = min(len(tests), opts.workers)
     display = lit.display.create_display(opts, len(tests), discovered_tests,
                                          workers)
 
-    def progress_callback(test):
-        display.update(test)
-        if opts.order == lit.cl_arguments.TestOrder.FAILING_FIRST:
-            touch_file(test)
-
-    run = lit.run.Run(tests, lit_config, workers, progress_callback,
+    run = lit.run.Run(tests, lit_config, workers, display.update,
                       opts.max_failures, opts.timeout)
 
     display.print_header()
 
     interrupted = False
     error = None
     try:
         execute_in_tmp_dir(run, lit_config)
finally:
         if tmp_dir:
             try:
                 import shutil
                 shutil.rmtree(tmp_dir)
             except Exception as e: 
                 lit_config.warning("Failed to delete temp directory '%s', try upgrading your version of Python to fix this" % tmp_dir)
 
 
+def record_test_times(tests, lit_config):
+    times_by_suite = {}
+    for t in tests:
+        if not t.result.elapsed:
+            continue
+        if not t.suite.exec_root in times_by_suite:
+            times_by_suite[t.suite.exec_root] = []
+        time = -t.result.elapsed if t.isFailure() else t.result.elapsed
+        times_by_suite[t.suite.exec_root].append((os.sep.join(t.path_in_suite), t.result.elapsed))
+
+    for s, value in times_by_suite.items():
+        try:
+            path = os.path.join(s, '.lit_test_times.txt')
+            with open(path, 'w') as time_file:
+                for name, time in value:
+                    time_file.write(("%e" % time) + ' ' + name + '\n')
+        except:
+            lit_config.warning('Could not save test time: ' + path)
+            continue
+
+
 def print_histogram(tests):
     test_times = [(t.getFullName(), t.result.elapsed)
                   for t in tests if t.result.elapsed]
     if test_times:
         lit.util.printHistogram(test_times, title='Tests')
 
 
 def print_results(tests, elapsed, opts):
     tests_by_code = {code: [] for code in lit.Test.ResultCode.all_codes()}
     for test in tests:
         tests_by_code[test.result.code].append(test)
 

llvm/utils/lit/tests/Inputs/reorder/.lit_test_times.txt

+3.0 subdir/ccc.txt
+2.0 bbb.txt
+0.1 aaa.txt

llvm/utils/lit/tests/Inputs/reorder/lit.cfg

 import lit.formats
-config.name = 'early-tests'
+config.name = 'reorder'
 config.suffixes = ['.txt']
 config.test_format = lit.formats.ShTest()
 config.test_source_root = None
 config.test_exec_root = None
-config.early_tests = { "subdir/ccc.txt" }

llvm/utils/lit/tests/early-tests.py

-## Check that we can run tests early.
-
-# RUN: %{lit} -j1 %{inputs}/early-tests | FileCheck %s
-
-# CHECK:     -- Testing: 3 tests, 1 workers --
-# CHECK-NEXT: PASS: early-tests :: subdir/ccc.txt
-# CHECK-NEXT: PASS: early-tests :: aaa.txt
-# CHECK-NEXT: PASS: early-tests :: bbb.txt
-# CHECK:     Passed: 3

llvm/utils/lit/tests/ignore-fail.py

 # Check that --ignore-fail produces exit status 0 despite various kinds of
 # test failures but doesn't otherwise suppress those failures.
 
 # RUN: not %{lit} -j 1 %{inputs}/ignore-fail | FileCheck %s
 # RUN: %{lit} -j 1 --ignore-fail %{inputs}/ignore-fail | FileCheck %s
 
 # END.
 
-# CHECK: FAIL: ignore-fail :: fail.txt
-# CHECK: UNRESOLVED: ignore-fail :: unresolved.txt
-# CHECK: XFAIL: ignore-fail :: xfail.txt
-# CHECK: XPASS: ignore-fail :: xpass.txt
+# CHECK-DAG: FAIL: ignore-fail :: fail.txt
+# CHECK-DAG: UNRESOLVED: ignore-fail :: unresolved.txt
+# CHECK-DAG: XFAIL: ignore-fail :: xfail.txt
+# CHECK-DAG: XPASS: ignore-fail :: xpass.txt
 
 #      CHECK: Testing Time:
 # CHECK-NEXT:   Expectedly Failed : 1
 # CHECK-NEXT:   Unresolved : 1
 # CHECK-NEXT:   Failed : 1
 # CHECK-NEXT:   Unexpectedly Passed: 1
 #  CHECK-NOT: {{.}}

llvm/utils/lit/tests/reorder.py

+## Check that we can reorder test runs.
+
+# RUN: cp %{inputs}/reorder/.lit_test_times.txt %{inputs}/reorder/.lit_test_times.txt.orig
+# RUN: %{lit} -j1 %{inputs}/reorder | FileCheck %s
+# RUN: not diff %{inputs}/reorder/.lit_test_times.txt %{inputs}/reorder/.lit_test_times.txt.orig
+# END.
+
+# CHECK:     -- Testing: 3 tests, 1 workers --
+# CHECK-NEXT: PASS: reorder :: subdir/ccc.txt
+# CHECK-NEXT: PASS: reorder :: bbb.txt
+# CHECK-NEXT: PASS: reorder :: aaa.txt
+# CHECK:     Passed: 3

llvm/utils/lit/tests/shtest-shell.py

 # Check the internal shell handling component of the ShTest format.
 #
 # RUN: not %{lit} -j 1 -v %{inputs}/shtest-shell > %t.out
 # FIXME: Temporarily dump test output so we can debug failing tests on
 # buildbots.
 # RUN: cat %t.out
 # RUN: FileCheck --input-file %t.out %s
 #
 # Test again in non-UTF shell to catch potential errors with python 2 seen
 # on stdout-encoding.txt
+# FIXME: lit's testing sets source_root == exec_root which complicates running lit more than once per test.
+# RUN: rm -f %{inputs}/shtest-shell/.lit_test_times.txt
 # RUN: env PYTHONIOENCODING=ascii not %{lit} -j 1 -a %{inputs}/shtest-shell > %t.ascii.out
 # FIXME: Temporarily dump test output so we can debug failing tests on
 # buildbots.
 # RUN: cat %t.ascii.out
 # RUN: FileCheck --input-file %t.ascii.out %s
 #
 # END.
 

mlir/test/Unit/lit.cfg.py

 # -*- Python -*-
 
 # Configuration file for the 'lit' test runner.
 
 import os
 import subprocess
 
 import lit.formats
 
 # name: The name of this test suite.
 config.name = 'MLIR-Unit'
 
 # suffixes: A list of file extensions to treat as test files.
 config.suffixes = []
 
-# is_early; Request to run this suite early.
-config.is_early = True
-
 # test_source_root: The root path where tests are located.
 # test_exec_root: The root path where tests should be run.
 config.test_exec_root = os.path.join(config.mlir_obj_root, 'unittests')
 config.test_source_root = config.test_exec_root
 
 # testFormat: The test format to use to interpret tests.
 config.test_format = lit.formats.GoogleTest(config.llvm_build_mode, 'Tests')