nor's blog

[Bug] High variance in CF judging times
By nor, 9 months ago, In English

When submitting to 1923E - Count Paths, I noticed that 248189683 takes 124ms and 248191037 takes 420ms.

Both of these are the same code (can be confirmed via diff), and there is no indeterminate behaviour like randomness involved in the submissions. It looks like it points to some issue with the judging machines (maybe one judging server is just slower than the other or the server load was high).

Pinging MikeMirzayanov for increasing chances of this getting fixed. Thanks!

  • Vote: I like it
  • +65
  • Vote: I do not like it

»
9 months ago, # |
← Rev. 2   Vote: I like it -33 Vote: I do not like it

Execution times can vary, but we don't have to worry about our solutions getting TLE in contests due to this variation. When a solution gets TLE, it's checked about 3 times to make sure that it's actually because of wrong logic, and not because of server issue.

Edit: Yeah makes sense, let's see if you find an explanation or answer from Mike. Sorry I'm too newbie to understand these stuffs and probably should stay out of it.

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    This is not true in general: if there is a >3x variation in the time taken for this problem, there's no reason to believe that this variation will not happen in another case. Also, problem authors sometimes struggle to cut-off $$$O(n^{1.5})$$$ from $$$O(n \log n)$$$, let alone smaller differences in complexity, so this should not be an excuse to not have a robust testing mechanism.

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Commenting out all the pragmas keeps it under 200ms (my recent submissions). I guess some weird compiler stuff happens, might not be Codeforces's fault.

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, I submitted the original solution (with pragmas), it's runtime is still 124ms.

    If 2 solutions are exactly the same then pragmas should have the same optimization (better/worse) on both solutions. Most probably it's because of servers. (Though I can be wrong)

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I agree. It might be due to initial cache state, but I don't think that it matters so much for a program that executes for very long (on the order of a few hundred ms) because after a sufficiently large number of memory accesses, you end up in a steady state unless you're doing something peculiar cache-wise.

      Another guess that is not exactly related to other processes on the server is that it might be a Windows issue (like their implementation of heap allocation and so on could be less realtime friendly). But I think server load is a major issue, especially with Windows which loves to preempt stuff and move things around.

      → Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 4   Vote: I like it -19 Vote: I do not like it

    Maybe increasing number of lines and words , increases parsing time of compiler, increasing in runtime of code..., can't we ignore parsing time of code,only focus on execution time?it would be better for python users(hope I am clear)

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Compilation time is not included into the time of the submission. It consists of runtime only.

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        Ohh, then execution time must be same,also i will ping you in that post after 3 months was thinking about it 4-5 hours earlier

        → Reply