Saul_Goodman_'s blog

How to convert the number of operations into time ?
By Saul_Goodman_, history, 3 years ago, In English

Hy everybody

My question is that after I calculate the number of operations that my code will do how can I convert it to time in seconds and also how to know the number of megabytes of memory my code will use. I didn't find a source talking about it so if you have anything that might help me I will be grateful if you share it.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
3 years ago, # |
← Rev. 5   Vote: I like it +3 Vote: I do not like it

Hi. $$$2e8$$$ operations takes around $$$1$$$ second time in CF (It depends on the power of the judging server), and for calculating memory multiply the size of the arrays you are storing by the size of the type of the array and divide it to $$$1e6$$$ , the resulting number shows you the memory that your program is using.

for example if you have an integer array of size $$$1e7$$$ then $$$->$$$ $$$int$$$ $$$=$$$ $$$4$$$ $$$bytes$$$ $$$->$$$ $$$1e7 * 4$$$ / $$$1e6$$$ = $$$40$$$ $$$->$$$ your program uses around $$$40$$$ $$$MB$$$ of memory.

Or for example you have an $$$integer$$$ array of size $$$1e6$$$ and a $$$long$$$ $$$long$$$ array of size $$$1e6$$$ $$$->$$$

($$$1e6$$$ * $$$4$$$ + $$$1e6$$$ * $$$8$$$) / $$$1e6$$$ $$$=$$$ $$$12$$$ $$$MB$$$.

Hope you understand it.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    I thought it was 1e8 operations per 1 second...

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      It depends on the power of the judging server, But yes usually 1e8 operations take 1 second in online judges.

      I think the number in atcoder is different.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +16 Vote: I do not like it

      It's not static, it depends on lots of factors from the solution, probably cache hits/branch prediction being the most important ones that aren't too obscure, other than obviously some operations being fundamentally slower than others as in multiplication vs addition.

      → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

From what I understand, the Codeforces judging servers run Coffee Lake CPUs clocked at around 3.6GHz. In practice most nontrivial competitive programming solutions are limited by memory latency, so the relevant numbers can be found here.

In practice, playing around a bit on custom invocation with pseudorandom latency-bound accesses on an array that should be firmly in the "almost exclusively L3 cache hits" regime, my observed runtimes are typically about 10-20% slower than that 41 cycles of latency number would suggest. That suggests one typically gets up to around $$$7 \times 10^7$$$ bad memory accesses per second.

Also note that if your working set approaches the size of the L3 cache things get much worse. I suspect the judging of other submissions prevents you from being able to effectively exploit all of the L3 cache, especially during system testing.

→ Reply