Improve sorting speed for high number of tests

[francois-normandin]

As shown in this benchmark (see link below), Caraya's execution time does not increase linearly with the number of tests being run. The benchmark does not differentiate between test execution and report generation. The time it takes to process the tests should not be influenced by the number of previous tests unless a processing of the whole series of tests (or part of) is being performed. This only happens in two occasions: displaying the test results live (interactive mode) or to sort the test hierarchy and produce the report.

https://github.com/IncQueryLabs/LabVIEW-knowledge-base/wiki/Unit-testing-tools-benchmark-and-DQMH-example (credit: InstaCoverage Unit Framework)

Some time should be spent on optimization of the result sorting algorithm, or on refactoring the test aggregation method to not require sorting.

[tannerblair]

This is currently killing me. We're running a suite of tests with about 5000 test cases in it, and it slows to an absolute crawl after about 2k. I'm concerned that if these tests take too long to run, devs just won't run them.

[francois-normandin]

@tannerblair can you comment on your current setup to help frame the optimization paths? For example, are you running in interactive mode? Are you creating a test suite or not? Are you running raw tests or using a discovery method such as project reference or folder? Which build version are you running from?

Just trying to document a bit more the issue, that's all. I don't think there is currently any workarounds, apart from breaking down your tests in multiple suites and running them sequentially. (Each suite will clear the result of the previous one, possibly avoiding the unoptimized test sorting... At the cost that you'll need to hold on to the test results and process them without going on interactive mode)

[tannerblair]

Sure! I am running in interactive mode, and I'm currently not creating a test suite, just adding tests to the project. There are quite a few tests that I'm reading from a file then looping over each test case. To give you a rough idea of how this is structured, it's something like:

System

• Subsystem
  • Test
  • Test Value
    • Assert

I am then running them from the project reference.

I think a test suite per subsystem could do the trick. I can also see that the top-level system test VI that runs all tests finishes WAY before the interactive UI. I don't know how you have the UI code structured, but I have seen similar problems when inserting rather than appending items to a tree control in LV.

[francois-normandin]

Thanks for the details. That will help create real world analog stress tests to benchmark any improvements to the sorting algorithm.

I think the problem is that the sort is currently scaling as O^2... Which is pretty bad for large sets. It is not redrawing the tree at every test, but rather it's the way the test results are stored and later reorganized based on the call chain structure that lags.

To perform individual tests quickly, the assertions are put through a pipeline that is serially handled by the test manager process without any kind of preprocessing. The test manager is also the UI, so this is why it is a bit tangled at the moment. IMO, the UI is not the problem, although decoupling would be nice. It's rather the search through the results that does not scale optimally. There are two paths to improvement. First, we can look into storing the assertions differently, so that reordering them is less of an intensive job. Second, we can improve the sort algorithm itself, to rebuild the tree structure from the call chains more efficiently. Both approaches would result in improvement, but I'm not too certain which one would give the biggest bang for your buck. I guess one would have to pick either one and see.

Obviously, this is a unit test framework... So we should make sure we build good tests and benchmarking harnesses before we optimize those routines. It would be quite bad to break existing code in an effort to make it faster.

[tannerblair]

Gotcha. I've been doing some digging, and I really do think the implementation of "Add Node to Tree.vi" is the culprit here. The insertion time on tree items when using "Add Item" is really, really slow. If I have some time this weekend I'll experiment with replacing it with "Add Item to End" and see if that helps. It seems like the tests are already sorted and execute in sorted order, so this should be an easy change. If that's not true, it's still probably cheaper to sort them outside the tree and use this method.

[tannerblair]

Or if you really want to go nuts, since you aren't updating the display after every item anyways, Add Multiple Items to End right before + refresh would be awesome.

[francois-normandin]

Eager to see what you come up with. Ping me if you have questions. I don't know that I'll have time to look into it as well (I'm drawing from memory here) but if I can enable you in any way...

[tannerblair]

Alright, if I disable the tree control entirely I see a massive improvement in speed. That said, I think the test sorting that this ticket was actually in reference to is also an issue. It still takes 10s of minutes to run tests that take a few minutes to run separately.

[francois-normandin]

@tannerblair that's a good confirmation that we have two problems to solve.

The first problem can easily be circumvented by using non interactive mode and by handling the test results object separately. The test sorting problem is, in my opinion, more urgent to tackle. Is this a fair assessment?

[tannerblair]

Definitely agree that there are two problems to solve here. I think interactive mode is still appealing to our workflow, but I can't disagree with your assessment.

[francois-normandin]

Update: I'll use the "Run Tests in Active Project" as a qualitative benchmark. As it is, there are 800+ self-tests being run within the current Caraya project. The UI completes in about 2.4x the time it takes to perform the tests. If I disable the UI: Update?frame until the tests are complete, it finishes a couple of seconds after the test is completed. It does confirm that the biggest chunks of the processing time is taken by Tree Control refreshes, even with deferred panel updates.

[francois-normandin]

As stated multiple times in other threads, we would like to decouple the UI from the Test Manager engine, so I'm trying to keep the official work done on the test manager to a minimum until that time. However, lagging issues for large test suites are very much problematic and so I'd like to offer a temporary patch... which is really a hack and does not actually solve the problem, but rather makes it less punitive.

I've added a geometric progression of the refresh time for the Tree control in the interactive UI. The current code will refresh the tree every 100ms. It becomes quickly problematic for >1000 tests. So instead of constant update delay, we can start every test suite with 100ms update rate and multiply by a factor (arbitrarily set to 2 at the moment).

The addition looks like this, with a boolean flag to disable it and test its effect.

Feedback requested

If anyone would like to give that a try with your large test suites and give feedback, that would be very much appreciated.

This is the precise commit where this is happening (Develop branch). Fork it and try it out... but please, this is not production code. Do not install permanently on your CI server!

My arbitrary benchmarks: I ran a test which calls 820 assertions and takes 17 seconds to execute on my VM. With the flag = false, the UI updated at every ~20 results and took an extra 21 seconds to complete. With flag = true, the UI updated at ~30, 60, 150, 430 and 820 results, and took an extra 2 seconds to complete.

Q&A

Is it a real fix? No. This does not address the real issue that processing the results and updating the Tree control are inefficient in their current implementation.

Why not fix the problem at the source? Good question. The assert results are stored in a pair of variant attribute dictionaries, using Test Events and Assert Events. Those are private methods to the framework and will likely be changed in the optimization process. The UI is currently calling directly those private nodes, so any optimization of the UI is likely to be wasted effort in the refactor to come, if any of the interface between these two functions is changed in the process. The source of the problem steps on the boundary between these coupled functionalities. Fortunately, those methods were kept private the whole time so that this refactor is possible without breaking any existing installation.

When will this be done? Again, a very good question... You have a knack for tough ones don't you? There are only three reasons for it not to be already in the works: Time, time and... time. Seriously though, this is an open source project... everyone is welcome to fork the project and try things out. Who knows, you might have a fix to propose that is elegant and minimally invasive, one that would make the delight of your peers!

[francois-normandin]

For convenience, I'm sharing a package to test. I realize that not everyone is set up to build Caraya (VM, LV2013, etc.), so this will hopefully bring more feedback. I repeat: This is a NON-OFFICIAL PRE-ALPHA RELEASE (if such a thing even exists) of Caraya 1.2.0, so at your own risks.

jki_lib_caraya-1.2.0.122.vip.zip (fyi. can't upload a .VIP file in this thread...)

This package will not be available in the release page, nor on VIPM. You should make sure you take appropriate steps not to use this in production. (although it would work, really... because it passed all the tests, but you know, fairly warned...)