Kaneki_04's blog

Should Multi-threading be disabled on codeforces server?
By Kaneki_04, history, 7 years ago, In English

I had an assignment involving multi-threading and I was curious about what happens if I implement this here.

So, I ran this code to check if it was possible to reduce execution time.

At an input of N around 7*10^4 2 and 5 threads gave 6162ms while 9 threads gave 3478ms.

So by this logic isn't it possible to implement some brute force solutions via multi-threading?

This would defeat the purpose of competitive programming right?(It is certainly not efficient but someone can submit a brute force solution and get their solution accepted but one who couldn't think of an optimum method ends up losing points)

Edit:

Test 1

Test 2

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

»
7 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Solutions run on a single core of CPU, also as consumed time we calculate total CPU time of all cores.

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

    I am not an expert on this topic but does it have anything to do with why I am not getting a TLE with this and a TLE with this?

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Instead of just down voting (because I don't have a good rating. Lol seriously? People come here to learn stuff) can someone tell me why TLE is not occurring in both cases?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Some threads don't seem to get executed, thus the speedup. Try to output the thread rem when it is started, and you will see that for e.g. k=8 only 6 threads are executed.

Also instead of outputting the primes, output the number of primes found, so you can check the correctness. For a higher number of threads and same n, the number of primes decreases.

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

    Thanks for the response.

    I understood why I am not getting TLE but it still is a valid concern right..

    I mean I am going to implement this thing in the next contest to prove that my claim is valid..

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

      I think you misunderstood. Some threads seem to not get created, thus your program is incorrect (not finding all primes) and only because of that faster.

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

        Can you tell me why because I don't see any difference in this case

        Here are two cases with 10^6

        Case 1

        case 2

        But in the above images I am missing 17 which shows some thread is not running but still it does prove that multi threading is supported because the primes which are printed when remainder is taken with k yields more than one remainder..

        So I have to work on why some threads are not running..

        Thanks!(Also I would appreciate it if you can provide a solution to this problem cause I have to submit my assignment and I shouldn't go wrong ;) )

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 4   Vote: I like it +6 Vote: I do not like it

          Yes, multiple threads are running, but as Mike said, they are running on one cpu. The speedup that made you thought they run in parallel is due to some threads not executing and thus numbers being skipped.

          I didn't see a mistake in your program, I guess it is due to the codeforces server.

          here you can see a different result https://imgur.com/a/YfUIO

          → Reply