Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

complexity_test.cc spuriously fails #272

Closed
EricWF opened this issue Aug 9, 2016 · 1 comment · Fixed by #1757
Closed

complexity_test.cc spuriously fails #272

EricWF opened this issue Aug 9, 2016 · 1 comment · Fixed by #1757

Comments

@EricWF
Copy link
Contributor

EricWF commented Aug 9, 2016

The benchmark registered by BENCHMARK(BM_Complexity_O1) -> Range(1, 1<<18) -> Complexity(); sometimes reports it's complexity as lgN as opposed to ([0-9]+). This happens when one of the later repetitions happens to run faster due to CPU load.

For example:

BM_Complexity_O1/1                 2106 ns       3125 ns      10000
BM_Complexity_O1/8                 2132 ns       1563 ns      10000
BM_Complexity_O1/64                2050 ns       3125 ns      10000
BM_Complexity_O1/512               2032 ns       1563 ns      10000
BM_Complexity_O1/4k                2041 ns       1563 ns      10000
BM_Complexity_O1/32k               2264 ns      15625 ns       1000
BM_Complexity_O1/256k              2128 ns       1563 ns      10000
BM_Complexity_O1_BigO            163.31 lgN     389.19 lgN

I'm not quite sure how to fix this test, or even if this is a bug in the complexity implementation. I would like some guidance on how to tackle this.

This is making our Appveyor build frequently fail so I would like to fix it. For now I'm going to checkin a temporary fix which simply accepts 'lg(N)' as valid test output.
EricWF added a commit that referenced this issue Aug 9, 2016
@EricWF
Workaround flaky complexity_test.cc test case.
a7a7c56 
See #272
@dmah42
Copy link
Member

dmah42 commented Apr 27, 2021

i think this is what we've been seeing recently on the appveyor windows release tests. it does seem though that the github workflows are more stable.

LebedevRI added a commit to LebedevRI/benchmark that referenced this issue Feb 1, 2024
@LebedevRI
complexity_test: deflake, same as google#272
6853697 
As it can be seen in e.g. https://github.com/google/benchmark/actions/runs/7711328637/job/21016492361
We may get `65: BM_Complexity_O1_BigO                           0.00 N^2        0.00 N^2  `
@LebedevRI LebedevRI mentioned this issue Feb 1, 2024
Merged
LebedevRI added a commit that referenced this issue Feb 2, 2024
@LebedevRI
Deflake CI (#1751)
b04cec1 
* `complexity_test`: deflake, same as #272

As it can be seen in e.g. https://github.com/google/benchmark/actions/runs/7711328637/job/21016492361
We may get `65: BM_Complexity_O1_BigO                           0.00 N^2        0.00 N^2  `

* `user_counters_tabular_test`: deflake

We were still getting zero times there. Perhaps this is better?
LebedevRI added a commit to LebedevRI/benchmark that referenced this issue Feb 14, 2024
@LebedevRI
Rewrite complexity_test to use (hardcoded) manual time
ef22e2f 
This test is fundamentally flaky, because it tried to read tea leafs,
and is inherently misbehaving in CI environments,
since there are unmitigated sources of noise.

Fixes google#272
@LebedevRI LebedevRI mentioned this issue Feb 14, 2024
Merged
LebedevRI added a commit to LebedevRI/benchmark that referenced this issue Feb 14, 2024
@LebedevRI
Rewrite complexity_test to use (hardcoded) manual time
b2496c8 
This test is fundamentally flaky, because it tried to read tea leafs,
and is inherently misbehaving in CI environments,
since there are unmitigated sources of noise.

Fixes google#272
LebedevRI added a commit to LebedevRI/benchmark that referenced this issue Feb 14, 2024
@LebedevRI
Rewrite complexity_test to use (hardcoded) manual time
0806db7 
This test is fundamentally flaky, because it tried to read tea leafs,
and is inherently misbehaving in CI environments,
since there are unmitigated sources of noise.

Fixes google#272
LebedevRI added a commit to LebedevRI/benchmark that referenced this issue Feb 17, 2024
@LebedevRI
Rewrite complexity_test to use (hardcoded) manual time
4aa8882 
This test is fundamentally flaky, because it tried to read tea leafs,
and is inherently misbehaving in CI environments,
since there are unmitigated sources of noise.

That being said, the computed Big-O also depends on the `--benchmark_min_time=`

Fixes google#272
dmah42 pushed a commit that referenced this issue Feb 19, 2024
@LebedevRI
Rewrite complexity_test to use (hardcoded) manual time (#1757)
3d85343 
* Rewrite complexity_test to use (hardcoded) manual time

This test is fundamentally flaky, because it tried to read tea leafs,
and is inherently misbehaving in CI environments,
since there are unmitigated sources of noise.

That being said, the computed Big-O also depends on the `--benchmark_min_time=`

Fixes #272

* Correctly compute Big-O for manual timings. Fixes #1758.

* complexity_test: do more stuff in empty loop

* Make all empty loops be a bit longer empty

Looks like on windows, some of these tests still fail,
i guess clock precision is too small.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Rewrite complexity_test to use (hardcoded) manual time LebedevRI/benchmark
2 participants
@dmah42 @EricWF