pimenta's blog

Bug using global anonymous struct in GNU C++11 and GNU C++14
By pimenta, history, 7 years ago, In English

Hi,

I've sent submission 25136808 using a global anonymous struct with some big arrays and methods inside. The submission got RTE case 7.

Next, I send submission 25137642 only removing the struct from around the arrays and the methods, and I got AC.

Then I thought "maybe the global arrays are not being initialized to zero when they are inside the struct". So I called memset(&st,0,sizeof st); and I got RTE case 7 again: 25137670.

What's the deal with structs in Codeforces? All these 3 codes work fine I'm my notebook in test case 7.

UPD: I've just submitted the same 3 codes again, now with GNU C++14. The behavior is the same for all 3 codes.

UPD2: Now I've just submitted 25138080, only giving a name to the struct from the first submission and it got AC. So the problem is with anonymous structs??

UPD3: Seems like anonymous structs are not supported in C++ 11, after some Internet research...

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

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

All these 3 codes work fine I'm my notebook in test case 7.

How do you check? Test 7 is truncated when you view the submissions.

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

    I print the input in Codeforces with if (n == 1000). I have to print several times, several ranges... It's exhaustive =(

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

      That's clever.

      As for the original question, I don't know. Have you tried a named struct type? Or using custom test?

      So you have the whole test case. If the effect is reproducible in custom test, you can try to gradually simplify your program there, and so find the point when the effect vanishes. This will perhaps localize the problem, so that the source of the bug (in your program or elsewhere) becomes obvious.

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

        I've just made a second update to the post. If I just put a name in the struct, the code gets AC! But a friend just told me that anonymous structs are not in the C++ 11 standard... That's probably the cause...

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

This is an unnamed class, not an anonymous one. See http://stackoverflow.com/a/14248127/4879303 for their differences. Unnamed classes are explicitly permitted in C++: A class-specifier whose class-head omits the class-head-name defines an unnamed class. (§ 9.0.1, P231, n4618). Note that class and struct are the same in C++, except for the default permission.

Would you please share the data for test 7 so others can try to reproduce this issue easier?

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

    Sure! Here: http://pastebin.com/TiDmbkH7

    The correct answer is 10.

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

      It seems g++ didn't initialize the variable st in the runtime error case. When compiling with a struct name, I can see:

      st:
        .zero   3200160
n:
        .zero   4

      at the bottom, so st is clearly initialized as expected, but without a struct name, there's no such thing, I cannot find where st is initialized. Also the address printed at runtime has large difference.

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

        And what about the third submission, in which I call memset to initialize the variable st? Why does it get RTE?

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

          In the assembly level, consider st as a pointer, if it's uninitialized, the memset was called to an invalid address.

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

            Nice! That explains everything... Well, I wish I could get at least a compilation error for that...

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

            And here is my guess for why the code works for small test cases (1 to 6). The label st is present throughout the assembly, but not declared in the data segment. Then the assembler makes st equivalent to zero or some other initial offset in the data segment. With luck, some bytes after this offset are zero initialized and the code works for small test cases. But when it came to a big one, the bad actually happened. Is that it? Is this a good theory?

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

              If the issue is related to uninitialized st. That's a reasonable explanation. (I can't be sure since I failed to find doesn't imply g++ couldn't initialize it somewhere and the assembly is obtained under linux which may differ from what we have under windows.)

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

The difference between unnamed and named structure in this case is linkage. For unnamed type we have internal linkage and it allows compiler to do more optimizations.

Overall it looks like G++ optimizer bug, I've tried to play around with your code and minified it to:

http://codeforces.com/contest/319/submission/25139170

This one still gets RTE.

→ Reply