Wael_Zaiback's blog

No comment
By Wael_Zaiback, history, 4 months ago, In English

After 6 hours of debugging, this was the bug :

AC code

RTE code

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

»
4 months ago, # |
  Vote: I like it +19 Vote: I do not like it

I can give you lessons in implementation to avoid these mistakes later, you can take my number from eyad

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

RIP

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

I don't get it, max(a, b) = max(b, a) right ?

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

    The latter one involves a calculation, that changes the former.

    RIP

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

      No it's not, actually I still don't know why they are not the same

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

brutal

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

After 6 hours of debugging, the compiler was debugged.

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

Try it by writing a max function and see if it works.

Or try to change your compiler. You are using C++17 (GCC 7-32), use C++20 (GCC 13-64) might be that this will work.

→ Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it +48 Vote: I do not like it

Here's how to debug the code in 10 minutes

Step 1: Generate a random test case using g++ gen.cpp && ./a.out > input.txt

gen.cpp

Step 2: Compile with sanitizer and run against the test case

> g++ 1983F.cpp -O2 -fsanitize=undefined,address -g && ./a.out < input.txt
=================================================================
==109285==ERROR: AddressSanitizer: heap-use-after-free on address 0x150d908e77f8 at pc 0x56238fbb8a6b bp 0x7ffe5cba52d0 sp 0x7ffe5cba52c0
READ of size 4 at 0x150d908e77f8 thread T0
    #0 0x56238fbb8a6a in int const& std::max<int>(int const&, int const&) /usr/include/c++/14.1.1/bits/stl_algobase.h:262
    #1 0x56238fbb8a6a in Trie::get(int, int, int) /home/qmk/code/cpp/1983F.cpp:57

Step 3: Add bound checking for line 57

res = max(get(x, mid, st[node].child[0]), st[node].child[1] < st.size() ? st[st[node].child[1]].mx : 0);

Step 4: Profit 269512762

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

Same behavior replicated here. Switching order fixes it. Interestingly, adding optimization level O0 or O2 both give random outputs.

My best guess for why this happens is that std::max evaluates the second half of the max function, at some point stores a reference to a value in the vector of nodes, but then reallocates the vector while resizing in the recursive step, messing with that reference.

This behavior could not be replicated on Godbolt (but I didn't try very hard). I'm also not familiar enough with low-level programming to use an actual debugger, so I can't give a better answer.

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

    Is this a bug? It seems like a dangerous and easy to forget/not knowing how to fix it detail.

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
      ← Rev. 2   Vote: I like it +16 Vote: I do not like it

      I suppose that this is a bug in the sense that it is not what you would expect happening. Also very frustrating if you don't know about it, get destroyed by it, and never understand why.

      But think about it another way, assuming my understanding of the bug is correct. Let's say we want to implement a dynamically sized array. To make it dynamically sized, we will have to reallocate the memory for it every so often. If we want to allow usage of pointers to values inside this array, whenever we reallocate the array, we also have to redirect all the old pointers to the new array, which is a massive pain and may cause unwanted performance issues. Hence, this bug. (I actually discovered this the hard way during my country's TST last year...)

      Combining a slightly aggressive compiler that uses references over values for performance along with the vector reference bug will likely generate this new bug.

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
        ← Rev. 3   Vote: I like it +9 Vote: I do not like it

        One possible solution is to use BumpAllocator to manage allocations yourself

        It seems to "fix" both of your codes: https://ideone.com/Q0kYAD and https://ideone.com/T8vPD4

        Apply the trick on this blog's RTE code also results in AC: 269565959

        Edit: It's not recommended to use the above method unless performance is the top priority, I'm simply proving a point that the behavior can be defined.

        If you want references to survive a push_back, use deque instead of vector. In case you don't need references, compare with values instead. See https://ideone.com/xEPI3p and 269572580

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

UB should be more suspected in this case, since the order of evaluation of parameters should not matter.

See the comment from qmk above.

→ Reply