wnmrmr's blog

Crazy time difference between submissions with minimal changes
By wnmrmr, history, 9 months ago, In English

Hi, if you compare this submission (296ms) with this one (3025ms), this is the difference:

I think this is crazy because g is a vector<vector<int>> with size 3 * 10^5 with at most 3 * 10^5 entries, and the function build that returns g is called once in the program. This huge time difference is the same on both 64-bit C++ compilers, but it is not present in the 32-bit C++ compiler.

UPD: Calling the function build twice solves the problem

  1. Normal submission (3041ms)
  2. Changed submission (327ms)

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

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

Auto comment: topic has been updated by wnmrmr (previous revision, new revision, compare).

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

Looks like the problem is in tuple. Removed it and got 300 ms: link

Would be nice to know, why it happens.

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

    The output of build() in the "good" version is immediately cast to the tuple, while the "bad" version performs some expensive type conversions. Just look at the disassembly using GDB.

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

Auto comment: topic has been updated by wnmrmr (previous revision, new revision, compare).

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

So $$$x = 3000$$$ and $$$2x = 300$$$? Hmm...

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

Probably that particular version of compiler doesn't handle captures of structured bindings well.

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

    Though I tried to pass it as a parameter instead and it didn't help. Then simply accessing g must be slow.

    → Reply