[Bug c++/102221] New: Missed optimizations for algorithms over std::unique_ptr

[Bug c++/102221] New: Missed optimizations for algorithms over std::unique_ptr

[dangelog at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102221

            Bug ID: 102221
           Summary: Missed optimizations for algorithms over
                    std::unique_ptr
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: dangelog at gmail dot com
  Target Milestone: ---

Sorting/heaping/etc. an array/vector of unique_ptr generates worse codegen than
the equivalent code on an array of raw pointers. This is a missed optimization,
as the operations involved should just be mere swaps.

For instance:


#include <memory>
#include <algorithm>

#if defined(SMART)
using ptr = std::unique_ptr<int>;
#else
using ptr = int*;
#endif

void f()
{
    extern ptr *data;
    const auto cmp = [](const auto &a, const auto &b) { return *a < *b; };
    std::sort(data, data+1000, cmp);
}


https://gcc.godbolt.org/z/7zPYxr9q7


This generates quite some extra code (including calls to operator delete); the
result is that such a sort is slower than the countepart with a raw pointer.

[Bug libstdc++/102221] Missed optimizations for algorithms over std::unique_ptr

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102221

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-09-08
     Ever confirmed|0                           |1
           Keywords|                            |missed-optimization

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This comes from the construction of a local unique_ptr<int> variable in:

  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __unguarded_linear_insert(_RandomAccessIterator __last,
                              _Compare __comp)
    {
      typename iterator_traits<_RandomAccessIterator>::value_type
        __val = _GLIBCXX_MOVE(*__last);
      _RandomAccessIterator __next = __last;
      --__next;
      while (__comp(__val, __next))
        {
          *__last = _GLIBCXX_MOVE(*__next);
          __last = __next;
          --__next;
        }
      *__last = _GLIBCXX_MOVE(__val);
    }

The compiler apparently doesn't see that after std::move(__val) on the last
line there is no need to invoke the deleter, because it's empty.

The use of std::tuple<int*, default_delete<int>> for std::unique_ptr might make
it too hard for the compiler to track the value of the stored pointer.

I'm not sure there's anything the library can do here (except maybe replace
std::tuple with [[no_unique_address]], once all the compilers we care about
support that properly).

[Bug libstdc++/102221] Missed optimizations for algorithms over std::unique_ptr

[dangelog at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102221

--- Comment #2 from Giuseppe D'Angelo <dangelog at gmail dot com> ---
Hi,

Thanks for the analysis!

That basically allows me to reduce the testcase to something as simple as a
swap:


#include <memory>
#include <utility>

#if defined(SMART)
using ptr = std::unique_ptr<int>;
#else
using ptr = int *;
#endif

auto swap1(ptr &a, ptr &b) {
    if (&a == &b)
        __builtin_unreachable(); // 

    ptr tmp(std::move(a));
    a = std::move(b);
    b = std::move(tmp);
}

auto swap2(ptr &a, ptr &b)
{
    // deliberate
    std::swap<ptr>(a, b);
}

https://gcc.godbolt.org/z/Tqzz5eqrW


In both cases there's basically a call to "delete nullptr" that doesn't get
removed. I don't think this falls on libstdc++, rather than on the optimizer?

[Bug libstdc++/102221] Missed optimizations for algorithms over std::unique_ptr

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102221

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Giuseppe D'Angelo from comment #2)
> Hi,
> 
> Thanks for the analysis!
> 
> That basically allows me to reduce the testcase to something as simple as a
> swap:

Yes. The actual swaps done by std::sort don't cause the problem, because they
use the overload for swapping unique_ptrs, which calls the member function,
which doesn't need to create+destroy a local. But the __unguarded_linear_insert
function doesn't use swap, and directly creates a local like the generic
std::swap does.


> I don't think this falls on libstdc++, rather than on the optimizer?

Agreed, except that we might (one day) be able to simplify unique_ptr, to help
the optimizer do better.

[Bug libstdc++/102221] Missed optimizations for algorithms over std::unique_ptr

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102221

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #1)
> This comes from the construction of a local unique_ptr<int> variable in:
> 
>   template<typename _RandomAccessIterator, typename _Compare>
>     _GLIBCXX20_CONSTEXPR
>     void
>     __unguarded_linear_insert(_RandomAccessIterator __last,
> 			      _Compare __comp)

Actually, even if we eliminate the temporary here, there's another in the
__make_heap routine:

      while (true)
        {
          _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
          std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
                             __comp);
          if (__parent == 0)
            return;
          __parent--;
        }

[Bug libstdc++/102221] Missed optimizations for algorithms over std::unique_ptr

[dangelog at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102221

--- Comment #5 from Giuseppe D'Angelo <dangelog at gmail dot com> ---
Here's a further testcase that doesn't even use unique_ptr:


#include <utility>
#include <memory>

using ptr = int *;
using rawptr = int *;

#ifndef RESTRICT
#define RESTRICT
#endif

void swap(ptr & RESTRICT a, ptr & RESTRICT b) 
{
    if (std::addressof(a) == std::addressof(b)) 
        __builtin_unreachable();

    ptr tmp = a; a = nullptr; // ptr tmp = std::move(a)

    // a = std::move(b)
#if ONE
    {
        // a.reset(b.release())
        rawptr tmp = b;   // b.release()
        b = nullptr;
        rawptr old = a;   // a.reset(tmp)
        a = tmp; 
        delete old;
    }
#elif TWO
    {
        // move+swap
        rawptr tmp = b; b = nullptr; // ptr tmp = std::move(b)
        { // a.swap(tmp)
            rawptr tmp2 = a;
            a = tmp;
            tmp = tmp2;
        }
        // ~tmp
        delete tmp;
    }
#elif THREE
    {        
        delete a; a = b; b = nullptr;
    }
#else
#error 
#endif
    delete b; b = tmp; tmp = nullptr; // b = std::move(tmp)
    delete tmp;
}

https://gcc.godbolt.org/z/bv1T64ndo




ONE and TWO don't elide the delete, unless the arguments are marked
__restrict__. THREE does elide it. Sounds like some escape analysis going
wrong, combined with unique_ptr's self-move-assignment safety (that "bans"
THREE's implementation).

[Bug libstdc++/102221] Missed optimizations for algorithms over std::unique_ptr

[dangelog at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102221

--- Comment #6 from Giuseppe D'Angelo <dangelog at gmail dot com> ---
Hi,

(Sorry for chiming in after all this time); given this might not entirely be
libstdc++ related (cf. the latest testcase), would it be possible for someone
on the optimizer to gave their opinion?

[Bug libstdc++/102221] Missed optimizations for algorithms over std::unique_ptr

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102221

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |alias
           Severity|normal                      |enhancement