-14's blog

Incredible bug found in __gnu_cxx::rope
By -14, history, 3 years ago, In English

Today when I took part in the Round #740 solving problem D. Top-Notch Insertions, my submission failed on test 2 without knowing why. After asserting I found that rope contains unwanted contents and I didn't fix the problem during the contest.

However, when I replace all __gnu_cxx::rope.erase(x) into __gnu_cxx::rope.erase(x, 1), my code works fine (idk if it will pass system test or not; at least, it passes asserting that all elements are rolled back to the initial state).

Then! I found it unbelievable to see the following code from here:

Look at the line 2318, comments: Erase, single character.

However, it calls erase(__p, __p + 1);, who will erase __p + 1 characters starting from the position __p.

I found it incredible since it's part of libstdc++. I don't know if there's a way to report such failure. Could anyone tell me if I can do something with it? (or instead, NEVER USE SUCH FUNCTION IN THE FUTURE)

Thank you!

UPD: I've submitted the bug to gcc.

Fortunately, it's quickly replied by Jonathan Wakely. Unfortunately, just exactly as adamant predicted, Jonathan Wakely wrotes:

We should just delete this class, so I don't have to keep fixing bugs in code that nobody uses or cares about.

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

»
3 years ago, # |
  Vote: I like it +41 Vote: I do not like it

I didn't even know something like Rope existed. Is this DS very useful at higher levels in CP?

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

    Generally speaking, it's a list that can random access. It can be useful when you don't want to implement a balanced search tree.

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

    To some extent. See this blog. It's terrifically slow, tho.

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

      Sure. I modified and resubmitted the code, got TLE on $$$m = 2\times 10 ^5$$$.

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

        My submission with rope passes right under the time limit with 2.729/3s, if you're interested.

        Thanks for finding this bug. I will avoid using gnu c++ stuff in the future!

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

          Cool!

          I've made a subtle change to your code, 127004930, got a 1.528s result. I remove the pop back operation and copy the whole rope at the beginning of each test case. The assignment operation is $$$O(1)$$$, since it's a persistent structure.

          But it's still quite slow. In fact, $$$2\times 10^5$$$ pop back operations had made more than $$$1$$$ second gap between two submissions. If you use one extra operation in the loop, boom -- TLE.

          So, consider prepare a splay or treap next time, if the time limit is not as optimistic as this problem.

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

            Wow, thanks!

            I never knew that assignment was $$$\mathcal{O}(1)$$$. When you say it's a persistent structure, do you mean that it creates (amortized $$$\mathcal{O}(\log (\text{size}))$$$) new nodes each time the tree is updated? Like an persistent segment tree? Sorry for asking. I can't for the life of me understand the documentation.

            And since this is a dynamic tree, I'd imagine that the code is very cancerous. :P

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

              Not amortized but strict (or in expectation?) $$$O(\log (\mathrm{size}))$$$. If I understand the document correctly, it was implemented as something like persistent treap. When you replace the character at position $$$i$$$ for example, it will split the original sequence into $$$[0, i - 1]$$$ and $$$[i + 1, n - 1]$$$, then merge $$$[0, i - 1]$$$, new character, $$$[i + 1, n - 1]$$$ into one. So it only need to implement split and merge to support all kinds of operation, both can be done in $$$O(\log (\mathrm{size}))$$$ time.

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

                Oops, I should have said high-probability $$$\mathcal{O}(\log(\text{size}))$$$ instead of amortized.

                Thank you for your help today!

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

        Shocking! Is this just again that the GCC implementation is very poor? My own contest submission passes the time limit pretty easily using Data.Sequence.Seq from the Haskell containers library, which provides a similar set of features, if I understand correctly.

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

          I guess it's because implementation is not as satisfying as we expect C++ to be. However, it's may not be author's fault. The following is my suspicion:

          1. Since rope is a persistent data structure, as a library it needs GC to recycle memory. However, GC is not natural in C++, and I noticed some long code fragments enclosed by #ifndef __GC to implement a refcount solution, which I guess make it with a large constant and lack of optimization.

          2. I am not familiar with FP languages, but I have an impression that FP compilers do heavy & fancy optimizations on data structures to improve its performance, especially on simple structures like maintaining a sequence. BTW, it may also be a way to show the FP's advantage of maintaining a persistent data structure, so it's very likely they do benchmark and focus on these structures.

          So, it's quite possible that Haskell over-perform GCC on such task, especially it's a class, by Jonathan Wakely, "nobody uses or cares about".

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

You can report it on their bugzilla (see this report on pbds, for example), but it would take years to fix and might even end up in Jonathan Wakely or smb else on libstdc++ team suggesting to deprecate these structures as they have little industrial use.

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

    I think loujunjie was the one to provide a fix there, might be you would be interested in this one?

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

    Well, if they decide to delete rope, it'd be better if they never know the bug since I want to use it (lol

    I will try to submit the bug to bugzilla. Thank you!

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

      Implement your own rope! And also make sure to make a blog about it ;)

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

    I've submitted a report to bugzilla.

    Hope to see the bug fixed in ~10 years I guess, since the last change made to the line is 17 years ago.

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

      Yeah, just as I said, Jonathan Wakely immediately suggested to remove the class :)

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

        You are definitely a prophet! LMAO

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

NEVER USE SUCH FUNCTION IN THE FUTURE — never use rope in the future, use treap.

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

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

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

"NEVER USE SUCH FUNCTION IN THE FUTURE"

We need a rope after a bad round though

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

I can't debug my own code but this Chinese debuged C++

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

    Sometimes you can't debug your own code because C++ itself has bugs,so you maybe need to debug C++ first before debug your own code just like this Chinese :)

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

      That's clear, but only Chinese people can debug C++

      → Reply