[Bug libstdc++/59508] New: std::find could use specialized container's find

[Bug libstdc++/59508] New: std::find could use specialized container's find

[olegendo at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59508

            Bug ID: 59508
           Summary: std::find could use specialized container's find
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: olegendo at gcc dot gnu.org

It should be possible to invoke a container's specialized find function (e.g.
std::set::find, std::map::find, etc) from within std::find, if it is used in a
compatible way, i.e. std::find is invoked with begin and end iterators of the
container and a value ref.

This could be done by something like this ...

#include <vector>
#include <set>
#include <type_traits>
#include <algorithm>

namespace x
{

template<class InputIt, class T, class Enable = void> struct find_impl;

template<class InputIt, class T>
struct find_impl<InputIt, T, typename std::enable_if<std::is_same<typename
std::set<T>::iterator, InputIt>::value>::type>
{
  static InputIt find (InputIt first, InputIt last, const T& value)
  {
    // if first == container's begin () and
    // last == container's end () can use optimized implementation of
    // std::set::find.
    // but to do that, must be able to get container ref from the given
    // iterators somehow, or look at unique properties of begin () and end ()
    // iterators as returned from the container.

    return first;
  }
};

template<class InputIt, class T>
struct find_impl<InputIt, T, typename std::enable_if<!std::is_same<typename
std::set<T>::iterator, InputIt>::value>::type>
{
  static InputIt find (InputIt first, InputIt last, const T& value)
  {
    return std::find (first, last, value);
  }
};

template<class InputIt, class T> InputIt
find (InputIt first, InputIt last, const T& value)
{
  return find_impl<InputIt, T>::find (first, last, value);
}
}


usage example:
int func1 (std::vector<int>& my_container)
{
  return *x::find (my_container.begin (), my_container.end (), 5);
}

int func2 (std::set<int>& my_container)
{
  return *x::find (my_container.begin (), my_container.end (), 5);
}


If it's not possible to figure out whether an iterator is a container's begin
() or end () because it would require adding a data member to the iterator,
another option could be to return internal subclasses of std::set::iterator for
begin () and end () and then check the iterator types in std::find.  However,
I'm not sure whether containers are allowed to do that according to the
standard.

[Bug libstdc++/59508] std::find could use specialized container's find

[daniel.kruegler at googlemail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59508

Daniel Krügler <daniel.kruegler at googlemail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |daniel.kruegler@googlemail.
                   |                            |com

--- Comment #1 from Daniel Krügler <daniel.kruegler at googlemail dot com> ---
A conforming implementation cannot do that, unless the difference weren't
observable by the user (modulo the performance difference), i.e. it would only
be possible for containers that have neither user-defined value types nor
user-defined allocators.
>From gcc-bugs-return-437638-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Sun Dec 15 17:07:47 2013
Return-Path: <gcc-bugs-return-437638-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 1695 invoked by alias); 15 Dec 2013 17:07:47 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 1653 invoked by uid 48); 15 Dec 2013 17:07:44 -0000
From: "hjl.tools at gmail dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug rtl-optimization/59350] [4.9 regression] ICE: in vt_expand_var_loc_chain, at var-tracking.c:8212
Date: Sun, 15 Dec 2013 17:07:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: rtl-optimization
X-Bugzilla-Version: 4.9.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: hjl.tools at gmail dot com
X-Bugzilla-Status: WAITING
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 4.9.0
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: cc
Message-ID: <bug-59350-4-iN7qD12DNa@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-59350-4@http.gcc.gnu.org/bugzilla/>
References: <bug-59350-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2013-12/txt/msg01293.txt.bz2
Content-length: 432

http://gcc.gnu.org/bugzilla/show_bug.cgi?idY350

H.J. Lu <hjl.tools at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hjl.tools at gmail dot com

--- Comment #26 from H.J. Lu <hjl.tools at gmail dot com> ---
FWIW, I can't reproduce this bug with revision 206000 either.

[Bug libstdc++/59508] std::find could use specialized container's find

[olegendo at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59508

--- Comment #2 from Oleg Endo <olegendo at gcc dot gnu.org> ---
(In reply to Daniel Krügler from comment #1)
> A conforming implementation cannot do that, unless the difference weren't
> observable by the user (modulo the performance difference), i.e. it would
> only be possible for containers that have neither user-defined value types
> nor user-defined allocators.

I don't understand why it would not be possible to do with user defined value
types or user defined allocators.

For example, in the current RB tree implementation each node
(_Rb_tree_node_base) has a field that stores a red/black bit.  It is possible
to use the spare bits to store additional node information whether a node is
the begin () node or end () node.  This will work regardless of the value type
or allocator, since the node type is implementation internal and not visible to
the user.

Could you please elaborate?
>From gcc-bugs-return-437641-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Sun Dec 15 17:47:56 2013
Return-Path: <gcc-bugs-return-437641-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 17067 invoked by alias); 15 Dec 2013 17:47:55 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 17035 invoked by uid 48); 15 Dec 2013 17:47:51 -0000
From: "robert-gcc at debian dot org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug driver/59512] New: Incomplete output files when compiler is killed
Date: Sun, 15 Dec 2013 17:47:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: driver
X-Bugzilla-Version: unknown
X-Bugzilla-Keywords:
X-Bugzilla-Severity: minor
X-Bugzilla-Who: robert-gcc at debian dot org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status bug_severity priority component assigned_to reporter
Message-ID: <bug-59512-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2013-12/txt/msg01296.txt.bz2
Content-length: 1591

http://gcc.gnu.org/bugzilla/show_bug.cgi?idY512

            Bug ID: 59512
           Summary: Incomplete output files when compiler is killed
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: minor
          Priority: P3
         Component: driver
          Assignee: unassigned at gcc dot gnu.org
          Reporter: robert-gcc at debian dot org

Hi

When cc1plus program is killed for example by OOM then the output file (given
by the `-o' option) can be incomplete, which will than result in linker error.
This is especially visible when the `-pipe' option is used.

I can see that clang always first create some temporary file, and then renames
it into the final one:
 strace -efile -f  clang++ a.cpp -pipe -c -o a.o
  [pid 28990] stat64("a.o", {st_mode=S_IFREG|0644, st_sizeq6, ...}) = 0
  [pid 28990] access("a.o", W_OK)         = 0
  [pid 28990] open("/dev/urandom", O_RDONLY) = 3
  [pid 28990] open("a.o-8cc52ce9", O_RDWR|O_CREAT|O_EXCL, 0666) = 3
// skipped some output
  [pid 28990] rename("a.o-8cc52ce9", "a.o") = 0

It would be nice if g++ could implement the same behaviour.

I tried to simulate it in makefiles by using something like `g++ -o $@.tmp &&
mv $@.tmp $@', and it worked pretty well, unless coverage flags
(`-fprofile-arcs -ftest-coverage') were also given, in which case the generated
gcno/gcda files refered to the `.o.tmp' files, which generally broke the
coverage calculations. For that reason I think that it would be best if g++
could handle this `write to temp && rename temp' approach internally.

[Bug libstdc++/59508] std::find could use specialized container's find

[daniel.kruegler at googlemail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59508

--- Comment #3 from Daniel Krügler <daniel.kruegler at googlemail dot com> ---
(In reply to Oleg Endo from comment #2)
> Could you please elaborate?

My response was referring to the generic code that you provided, because that
would also be applied to user-provided specializations of library containers
and there iterator types. So it would only be feasible for a special scenario
where the library would tag its internal types and where it can proof that the
actual predicate used is equivalent to the usage of the associative container's
predicate.
>From gcc-bugs-return-437648-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Sun Dec 15 18:39:19 2013
Return-Path: <gcc-bugs-return-437648-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 5410 invoked by alias); 15 Dec 2013 18:39:19 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 5373 invoked by uid 48); 15 Dec 2013 18:39:15 -0000
From: "octoploid at yandex dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug ipa/59469] [4.8/4.9 Regression] LLVM build failure with gcc LTO
Date: Sun, 15 Dec 2013 18:39:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: ipa
X-Bugzilla-Version: 4.9.0
X-Bugzilla-Keywords: lto
X-Bugzilla-Severity: normal
X-Bugzilla-Who: octoploid at yandex dot com
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 4.9.0
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-59469-4-SelnKZ69dq@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-59469-4@http.gcc.gnu.org/bugzilla/>
References: <bug-59469-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2013-12/txt/msg01303.txt.bz2
Content-length: 492

http://gcc.gnu.org/bugzilla/show_bug.cgi?idY469

--- Comment #16 from Markus Trippelsdorf <octoploid at yandex dot com> ---
(In reply to H.J. Lu from comment #14)
> (In reply to H.J. Lu from comment #13)
> > Can you try bfd linker, hjl/linux/release/2.24.51.0.2, from
> >
> > https://sourceware.org/git/?p=binutils-gdb.git;a=summary
> >
> > It has a modified LTO bfd linker.
>
> You need to build LLVM from scratch with my bfd linker.

I've tried your bfd version, but it doesn't help.

[Bug libstdc++/59508] std::find could use specialized container's find

[olegendo at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59508

--- Comment #4 from Oleg Endo <olegendo at gcc dot gnu.org> ---
(In reply to Daniel Krügler from comment #3)
> (In reply to Oleg Endo from comment #2)
> > Could you please elaborate?
> 
> My response was referring to the generic code that you provided, because
> that would also be applied to user-provided specializations of library
> containers and there iterator types. So it would only be feasible for a
> special scenario where the library would tag its internal types and where it
> can proof that the actual predicate used is equivalent to the usage of the
> associative container's predicate.

Ah yes.  Of course it would need to check whether the iterator type is a type
of the library's standard implementation, like _Rb_tree_iterator<T> instead of
simply checking for std::set::iterator.
>From gcc-bugs-return-437656-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Sun Dec 15 19:58:32 2013
Return-Path: <gcc-bugs-return-437656-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 7740 invoked by alias); 15 Dec 2013 19:58:32 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 7702 invoked by uid 48); 15 Dec 2013 19:58:29 -0000
From: "petr.pisar at atlas dot cz" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug target/58158] [4.8/4.9 Regression] ICE with conditional moves on GPRs with a floating point conditional on mipsel with loongson2f
Date: Sun, 15 Dec 2013 19:58:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: target
X-Bugzilla-Version: 4.8.1
X-Bugzilla-Keywords: ice-on-valid-code
X-Bugzilla-Severity: normal
X-Bugzilla-Who: petr.pisar at atlas dot cz
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P2
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 4.8.3
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: cc
Message-ID: <bug-58158-4-J0GMdWQPhE@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-58158-4@http.gcc.gnu.org/bugzilla/>
References: <bug-58158-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2013-12/txt/msg01311.txt.bz2
Content-length: 665

http://gcc.gnu.org/bugzilla/show_bug.cgi?idX158

Petr Pisar <petr.pisar at atlas dot cz> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |petr.pisar at atlas dot cz

--- Comment #9 from Petr Pisar <petr.pisar at atlas dot cz> ---
I still can reproduce the problem with GCC 4.8.2 if I try to compile the code
from comment #1 with "gcc -O2 -march=loongson2f -mabi=n32
-Wa,-mfix-loongson2f-nop -c test2.c". Compilation with -O1 passes.

I was hit by this bug when building GIMP. Though the GIMP source fails even
with -O1.

[Bug libstdc++/59508] std::find could use specialized container's find

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59508

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Users can specialize std::set<UserDefinedType>::find to do something different,
e.g. write to a file, and it must not do that if they call std::find.

It's not a matter of whether the type is the library's iterator type or not.

[Bug libstdc++/59508] std::find could use specialized container's find

[olegendo at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59508

--- Comment #6 from Oleg Endo <olegendo at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #5)
> Users can specialize std::set<UserDefinedType>::find to do something
> different, e.g. write to a file, and it must not do that if they call
> std::find.
> 
> It's not a matter of whether the type is the library's iterator type or not.

Right.  If, then std::find should not invoke std::set::find (or std::map::find
etc) but the library's internal function to search the rb tree.

Of course users might still provide specializations of std::find for particular
iterator types but that shouldn't be a problem I think.

[Bug libstdc++/59508] std::find could use specialized container's find

[redi at gcc dot gnu.org]

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

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Oleg Endo from comment #6)
> Right.  If, then std::find should not invoke std::set::find (or
> std::map::find etc) but the library's internal function to search the rb
> tree.

If that internal function exists, then it means the specialization is using the
primary template, and in that case we could just use std::set::find anyway.

> Of course users might still provide specializations of std::find for
> particular iterator types but that shouldn't be a problem I think.

That's not allowed since C++20.

FWIW we already optimize std::distance this way for std::list iterators, where
it's possible to obtain the container from the iterator. But I don't think
we're likely to do this for other containers and std::find. I'm inclined to
close this as WONTFIX.

Anyway, if we did do this for std::find we should do it for ranges::find, at
least when a container is passed directly to ranges::find (rather than a pair
of iterators).