search

dimforge / nalgebra

Linear algebra library for Rust.
https://nalgebra.org
Apache License 2.0
3.92k stars 465 forks source link

Stochastic CI failures #309

Open milibopp opened 6 years ago

milibopp commented 6 years ago

There are a bunch of (seemingly stochastic) failures unrelated to the corresponding changes:

https://travis-ci.org/sebcrozet/nalgebra/builds/329862368 https://travis-ci.org/sebcrozet/nalgebra/jobs/329904255

Maybe something to look into? I am not familiar with the failing code, so I can't really judge what is going on without looking more deeply into this.

jswrenn commented 6 years ago

Judging from the CI output for solve_upper_triangular:

  ┌                                                                                                     ┐
  │   65.81852600344888   83.00340203577298 -20.655726768408613  -39.93015956001955  20.189229203045215 │
  │     80.066728825778   86.26126848337208   -53.5373517424664      99.13856605305  -55.90100029258156 │
  │ -26.677837824285234   86.33906003627544  -83.94291689589318   94.75362022070931  -53.88058849703066 │
  │   27.11142463903036   57.49630508823046    70.8921268377965  -88.62742869236158  53.204578501325614 │
  └                                                                                                     ┘
  ┌                                                                                                     ┐
  │   65.81852599915626   83.00340209487459  -20.65572660008175  -39.93016002452854  20.189229229690568 │
  │   80.06672882577678    86.2612684833818 -53.537351742455996   99.13856605303727  -55.90100029258194 │
  │  -26.67783782428512   86.33906003627536  -83.94291689589362   94.75362022070951  -53.88058849703077 │
  │   27.11142463903036   57.49630508823046    70.8921268377965  -88.62742869236158  53.204578501325614 │
  └                                                                                                     ┘

the implementation of solve_upper_triangle is probably correct, but floating point errors are to blame for the failure. For instance, the values -20.655726768408613 and -20.65572660008175 are close, but are not quite equal within 10-7.

Reducing epsilon by an order of magnitude would reduce the frequency of this error, but that's not a general solution to the problem. Could we adapt quickcheck to retry failing inputs with those same inputs represented as Rationals? I think this would basically eliminate false-positives without slowing down testing.

milibopp commented 6 years ago

Thanks for the analysis :) I think your idea is interesting to prevent the issue from happening. It could work, I am not sure how the generics for that would work out, as it sounds like it needs some higher-kinded trait bounds. However, we could still do it with a macro, of course.

What about adding a quick fix raising epsilon first? If it fits within 10-6, it still gives me a lot of confidence in the tests to be honest. We can still follow that up by retrying with rationals, when somebody wants to put in the work.