Occasional failure of the complexity test

[jagerber48]

#275 added the first performance benchmarks to uncertainties. This included the addition of test_repeated_summation_complexity: https://github.com/lmfit/uncertainties/pull/275/files#diff-78b0fd2262d012f3449eb6345a4f631c0df7f76716b2797807542a7937c2596aR20

The original naive standard deviation calculation algorithm ran in time quadratic in the number of summands. Some users complained about slow performance and this drove lebigot to develop the lazy linear combination expansion algorithm which greatly sped up performance on this repeated summation test by reducing to time linear in the number of summands. Indeed, when I was first refactoring the core uncertainties code my first naive algorithm ran in quadratic rather than linear time. After studying Lebigot's algorithm and revising the code some I was able to get the refactor to run in linear time. However, at one point I made what seemed to be a minor change but which actually broke the linear-in-time algorithm. At that point I realized it might be valuable to test that we maintain the linear-in-time complexity to avoid regressions like what I had accidentally introduced and this test was my strategy to do so.

However, when introducing this test, @andrewgsavage commented the following:

I've seen a test similar to this that kept randomly failing so I don't know how reliable this test will be.
I think test_repeated_summation_speed will catch any increases in time so these tests are testing the same thing. I'm not opposed to this test- we can leave it in for now, and if it we find it unreliable we can remove it.

Indeed we have begun to see failures of this test in the CI. For example:
https://github.com/lmfit/uncertainties/actions/runs/17617077617/job/50052893572?pr=341

Resolutions that I see to this issue:

• Broaden the range within which the test can pass. Right now the range is 90% to 110%. We could increase to 80% to 120%.
• Eliminate the test

Suggestions or opinions?

[jagerber48]

I consider this low priority to work on relative to other things going on. I just wanted to capture my thoughts. We can work around the issue by just re-running the CI when it fails in this way.

[newville]

@jagerber48 I think that tests of run-time should be pretty generous, especially when running as CI on someone else's shared resource or compute farm.

I might suggest marking runtimes as "failing" when they are twice the expected time.

If I understand correctly, the question here is not actually absolute runtime but "linear" vs. "quadratic" in time. Perhaps the comparison could be the time to calculate a single error propagation, vs and one that is much more complex. Maybe something like

 vals = [10 + i/4 for i in range(10)]
 std = [0.3+i/5 for i in range(10)]
 uv = [ufloat(a, b) for a,b in zip(vals, std)]

t1 = timeit(lambda: uv[0]*uv[1],  number=10000)
t2 = timeit(lambda: uv[0]*uv[1]+uv[2]*uv[3],  number=10000)
t3=  timeit(lambda: uv[0]*uv[1]+uv[2]*uv[3]+uv[4]*uv[5],  number=10000)
t4=  timeit(lambda: uv[0]*uv[1]+uv[2]*uv[3]+uv[4]*uv[5]+uv[6]*uv[7],  number=10000)
t5 = timeit(lambda: uv[0]*uv[1]+uv[2]*uv[3]+uv[4]*uv[5]+uv[6]*uv[7]+uv[8]*uv[9],  number=10000)

and seeing if that is linear or quadratic-ish: is t5/t1 around 5 or around 25 (maybe "assert < 15"). FWIW, with v 3.2.3 on my laptop, I get t5/t1 ~ 9:

>>> t2/t1, t3/t1, t4/t1, t5/t1
(3.206651331222669, 5.774383643941443, 7.346212596052392, 8.839396415794146)

[jagerber48]

@newville your code snippet is essentially what I'm looking at in the test. look at tN/t1 or something for a number of different values of N and I assert that tN/t1 should be "close" to N. Something like that, I work in logarithmic space to try to reduce sensitivity. Need to look at the code to remind myself exactly the strategy I'm using. But working in logarithmic space was my main strategy to mitigate timing noise.

What you're suggesting essentially falls into the "broaden the threshold" option which I'm happy to do. I think that would be my first option as well.

[newville]

@jagerber48 Ah, sorry, I must have looked at that test wrong. I think my main point would be that testing timing is tricky, especially with an automated CI system.

It is definitely interesting to see the output of timing tests, and accidentally killing performance is something I have done in my own code many times. I know one could use https://github.com/airspeed-velocity/asv for testing runtime, but I don't know if that is still the fashionable choice. An advantage of timing reports being separate from "unit testing" is that not every loss in performance is necessarily a "failure".

But, having that tested here is fine too, but maybe just relax the threshold.

[jagerber48]

I'll relax the test. Right now it is 0.9 log(n/n0) < log(t/t0) < 1.1 log(n/n0) I'll relax it to log(t/t0) < 1.5log(n/n0).
2.0 log(n/n0) would be quadratic, so it's still much faster than quadratic. And I'll remove the lower limit. We don't care if the test is running sub-linear. That would bee interesting to know, but, not problematic and not likely to happen. More likely a test fails because of it which is just annoying.