chrome's blog

By chrome, 9 years ago, translation, In English

Hello, %username%!

Suppose we have statement and tests of some task.

We want to check our solution with given time && memory limit.

We can do this using .bat — script with run.exe.

But how to do this on linux without using wine?

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

»
9 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

A manual way:

Type in bash to create a new shell process.

In the new shell, run ulimit -v %your_memory_limit_in_KB% to set a memory limit. The limit will be applied to all child processes of the shell.

Then simply use time ./a.out <input >output to run your program a.out. The running time of your program will be printed to stderr and you can see it on screen.

After that type exit to quit the new shell and cancel the limit of memory.

To make the process automatically, you can write a bash script just like bat in Windows.

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

    I've also seen ulimit -m, but couldn't figure out how does it work. Does it even work?

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      ulimit -m sets a limit to physical memory. That means if this limit is exceeded, system will put some data into swap partition. Use ulimit -v instead. It sets a limit to virtual memory. It works as I tested.

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

        Oh I see now, OJs count virtual memory use, I've tested now. I thought they count physical memory use. Yes, it works, thanks.

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

    OFFTOP Question: Can we measure time limit and memory limit by python script. (If yes how?).

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

    May we use result of function time as variable?

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes, but you should change time's output format (in order to print the value by itself). For example:

      TIMEFORMAT='%3R'; time /bin/echo > /dev/null

      (where 3 is the decimal precision)

      This will execute a command (for example: /bin/echo but you can change it to ./program or something) and redirect its stdout to /dev/null (because all we want is stderr, where time will print the time).

      To save that value in a variable, you will do:

      variable=$((TIMEFORMAT='%3R'; time /bin/echo) 2>&1 >/dev/null)

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

    If I understand correctly, "ulimit -v" limits the size of address space, not the actual memory usage. In such case it is totally incorrect; it may be close to actual memory usage for trivial C/C++ programs, but that's pretty much the only case when it is close to memory usage. Non-trivial C/C++ programs, or programs running in a special environment (i.e. Java, Python, ... programs) will have it much larger than the actual memory usage.

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

      But it looks that OJs (at least codeforces) count virtual memory: 9476756

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        How very "nice" of them. This is pretty evil: the actual amount of memory "used" for complex programs is going to be huge this way. Also, if there is a task with large input, and someone decides to mmap() it, he'll get an unpleasant surprise.

        I wonder why don't they just use resident size of the process. This should be the correct value.

        Besides, other online judges (e.g., ejudge and Yandex.Contest) use the right value. Maybe it is only a problem of windows-based invokers?

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

          When someone mmap()s a file, he is effectively using kernel memory to hold portions of the file. Is it fair not to count it towards memory usage?

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

            It is fair to count these portions, but unfair to count the entire file. Note that regardless of mmap, everyone who reads something from disk, (indirectly) uses kernel buffers. If organizers are afraid of the abuse, they can just limit total size of kernel buffers by something small.

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

      My response is wrong. In fact the reason of failure of ulimit -m is following in the man page of bash:

      -m The maximum resident set size ( many systems do not honor this limit )

      Anyone can see it by execute man bash then type /ulimit. So unfortunately we can only use the limit to virtual memory. Maybe someone can modify Linux kernel to control resident set size.

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

        There is no need to modify Linux kernel: such limits can easily be enforced via cgroups.

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Only to set the time limit timelimit.

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

    It's better to watch the execution time using time ./a.out < in > out. While the judging system only cares about the binary can pass / can't pass, you care about how fast it is to estimate its chances.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Chortos-2 has written a tool in Python to help the testing of solutions locally. You can check it out here.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How about other operating systems like windows? How can I check memory limit in my C++ codes?