2

I am looking for a controllable way (easy to set the time for delay) to slow down my C++ solution on online judges. (Mainly for UVa, g++ 4.8.2 -lm -lcrypt -O2 -std=c++11 -pipe)

I've tried the following code:

{auto start=std::chrono::high_resolution_clock::now();
while (std::chrono::duration<double,std::milli>
    (std::chrono::high_resolution_clock::now()-start).count()<2000);
}

But the solution was slowed down for about 1.6 seconds, not the expected 2 seconds, I don't know why.

I also tried std::this_thread::sleep_for and usleep() fom <unistd.h>, but these almost didn't influence the runtime on online judges.

For std::this_thread::sleep_for, I tried:

std::this_thread::sleep_for(std::chrono::milliseconds(2600));

The reason why I want to do this is my teacher often assign problems on these online judges, and our homework grader will submit our solutions to those online judges to check if they can get AC (Accepted). As a result, my solution will be counted twice in the ranking system and I think this is unfair for later users, especially when my solution was ranked at the top of the ranklist. So I prefer to slow down my solution to reduce the influence on other users before submitting it to the homework grading system.

5gon12eder
  • 24,280
  • 5
  • 45
  • 92
James
  • 703
  • 1
  • 7
  • 22

4 Answers4

5

If you want to suspend execution of your program for a given amount of time, then std::this_thread::sleep_for is the way to go. Note however, that it really makes your thread sleep. That is, it relinquishes the CPU while it is sleeping. If the benchmark environment is measuring CPU time as opposed to wall time, then sleeping will not “help”. Instead, what you have to do is give the CPU some useless work to do. (Un)fortunately, compilers have become very good at eliminating useless work so you have to be careful.

You can use the time (1) utility to measure CPU and wall time consumed by your program.

This program sleeps for two wall time seconds.

#include <chrono>
#include <thread>

int
main()
{
  std::this_thread::sleep_for(std::chrono::seconds {2});
}

$ g++ -o wall -std=c++14 -Wall -Wextra -Werror -pedantic wall.cxx -pthread
$ time ./wall

real    0m2.003s
user    0m0.000s
sys     0m0.000s

As you can see, the elapsed “real” time is almost exactly two seconds but the CPU time (detailed into CPU time used in user mode and by the kernel) is negligible.

This program wastes two seconds worth of CPU time.

#include <ctime>

int
main()
{
  const auto t0 = std::clock();
  while ((std::clock() - t0) / CLOCKS_PER_SEC < 2)
    continue;
}

$ g++ -o cpu1 -std=c++14 -Wall -Wextra -Werror -pedantic cpu1.cxx
$ time ./cpu1

real    0m2.003s
user    0m0.530s
sys     0m1.470s

Again, the total (“real”) execution time is two seconds but this time, we've also spent about half a second in user-mode and one and a half second in kernel mode (due to the many calls to clock).

You can shift this by doing more work in user mode. For example, instead of immediately calling std::clock again, we can do some silly loop.

#include <ctime>

int
main()
{
  const auto t0 = std::clock();
  while ((std::clock() - t0) / CLOCKS_PER_SEC < 2)
    {
      int dummy;
      volatile int * pdummy = &dummy;
      for (int i = 0; i < 1'000'000; ++i)
        *pdummy = i;
    }
}

$ g++ -o cpu2 -std=c++14 -Wall -Wextra -Werror -pedantic cpu2.cxx
$ time ./cpu2

real    0m2.005s
user    0m2.003s
sys     0m0.000s

This time, nearly all CPU cycles were wasted in user mode. You may have to tinker with the magic number if your computer needs too long for one million iterations.

5gon12eder
  • 24,280
  • 5
  • 45
  • 92
2

In morden online judgment systems usualy there is difference between time limit (which is count process system time) and real time limit (which is count real time elapsed). So your code get 1.6 sec from process time during 2 sec because your process gets about 80% cpu on server.

mingaleg
  • 2,017
  • 16
  • 28
1

I have written a small test case for what you want and I cannot reproduce, that std::this_thread::sleep_for() does not give the expected result.

#include <thread>
#include <chrono>

int main() {
        std::this_thread::sleep_for(std::chrono::seconds(2));
        return 0;
}

This will give me (compiled using g++ -o slow slow.cpp -std=c++11) when run with time ./slow:

real    0m2.001s
user    0m0.000s
sys     0m0.000s

Thus giving the expected time of about 2 seconds.

Please notice that std::this_thread::sleep_for will block the current thread for at least the given duration. So it might block a few milliseconds longer than expected. See here:

Blocks the execution of the current thread for at least the specified sleep_duration.

A steady clock is used to measure the duration. This function may block for longer than sleep_duration due to scheduling or resource contention delays.

Nidhoegger
  • 4,973
  • 4
  • 36
  • 81
  • Thanks for testing. Code like `std::this_thread::sleep_for(std::chrono::seconds(2));` also worked on my local computer, but won't increase runtime returned by UVa online judge as expected. ( When I used this, the runtime only increased 7ms) – James Nov 08 '15 at 13:13
1

Online judge systems usually do not rely on real execution time. Instead of this, they measure user CPU time or user + system (depends on implementation).

It means that you should consume 2 seconds of CPU time rather than execute for 2 seconds of real time. There is no system-independent way of doing this. If the server is running on Linux, you can try this solution: How do I get the total CPU usage of an application from /proc/pid/stat?. But if the online judge system is smart enough, it may block these actions.

Community
  • 1
  • 1
Andrey Nasonov
  • 2,619
  • 12
  • 26