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.

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

Sorting is not deterministic #18

Closed
Jellix opened this issue Jun 11, 2020 · 3 comments · Fixed by #20
Closed

Sorting is not deterministic #18

Jellix opened this issue Jun 11, 2020 · 3 comments · Fixed by #20
Assignees
Labels
bug Something isn't working enhancement New feature or request
Projects

Comments

@Jellix
Copy link
Member

Jellix commented Jun 11, 2020

See below for the reoccurence


The fix for issue #13 revealed that sorting is not stable.

In case of sorting by time, when two times are identical, we also need to take the entity name/source location into account, I'm afraid.

For VCs, the total_proof_time, the maximum_proof time and then the entity location should be compared.

It's a bit unclear what to do with single proof paths, though. They all reference the same location and entity, even sorting by prover name could result in undeterministic behaviour.

@Jellix Jellix added bug Something isn't working enhancement New feature or request labels Jun 11, 2020
@Jellix Jellix self-assigned this Jun 11, 2020
@Jellix Jellix added this to In progress in Roadmap Jun 11, 2020
@Jellix Jellix linked a pull request Jun 11, 2020 that will close this issue
Roadmap automation moved this from In progress to Done Jun 11, 2020
@Jellix
Copy link
Member Author

Jellix commented Jun 15, 2020

I tried adding steps to the sorting criteria, now the templates fail again.

Although unlikely, I am suspecting some floating point to fixed point conversion issues.

See fix_sorting branch which currently fails templates and the differences should not actually be there, unless the time values are actually different.

@Jellix Jellix reopened this Jun 15, 2020
Roadmap automation moved this from Done to In progress Jun 15, 2020
@Jellix
Copy link
Member Author

Jellix commented Jun 16, 2020

I think I found the issue. It's not the sorting between the proof attempts, but between the proof items. They don't know about steps, and the offending entries have all the same value (max time, total time, rule, severity, and location), so unstable sorting is to be expected. I guess, to stabilize that we need to create unique ids to make these guys different, assuming that (at least for the tests) we can guarantee the order in which the entries are inserted.

@Jellix
Copy link
Member Author

Jellix commented Jun 16, 2020

Fixed in #28

@Jellix Jellix closed this as completed Jun 16, 2020
Roadmap automation moved this from In progress to Done Jun 16, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working enhancement New feature or request
Projects
Roadmap
  
Done
Development

Successfully merging a pull request may close this issue.

1 participant