[Bug libstdc++/50661] New: std::equal should use more efficient version for arrays of pointers

[Bug libstdc++/50661] New: std::equal should use more efficient version for arrays of pointers

[emil at wojak dot eu]

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

             Bug #: 50661
           Summary: std::equal should use more efficient version for
                    arrays of pointers
    Classification: Unclassified
           Product: gcc
           Version: 4.4.5
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: emil@wojak.eu


The following program uses the generic comparison algorithm in
bits/stl_algobase.h, while it could use the template specialization using
__builtin_memcmp instead.

#include <iostream>
#include <boost/array.hpp>

int main() {
        boost::array<void*, 888> a, b; 

        bool res = std::equal(a.begin(), a.begin() + 50, b.begin());

        return 0;
}

I checked with gcc-4.4.5, but I saw it's the same in SVN trunk.
The following patch solves this issue.

--- /usr/lib/gcc/i686-pc-linux-gnu/4.4.5/include/g++-v4/bits/stl_algobase.h    
2011-09-07 16:34:35.581681814 +0200
+++ /usr/lib/gcc/i686-pc-linux-gnu/4.4.5/include/g++-v4/bits/stl_algobase.h    
 2011-10-08 01:09:44.987380358 +0200
@@ -823,7 +823,7 @@
     {
       typedef typename iterator_traits<_II1>::value_type _ValueType1;
       typedef typename iterator_traits<_II2>::value_type _ValueType2;
-      const bool __simple = (__is_integer<_ValueType1>::__value
+      const bool __simple = ((__is_integer<_ValueType1>::__value ||
__is_pointer<_ValueType1>::__value)
                             && __is_pointer<_II1>::__value
                             && __is_pointer<_II2>::__value
                             && __are_same<_ValueType1, _ValueType2>::__value);

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #1 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-07 23:47:33 UTC ---
This misoptimization is very very old, but what you are suggesting makes sense
to me. Jakub can you imagine a reason why comparing arrays of pointers with
memcmp could not be Ok?

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[jakub at gcc dot gnu.org]

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-10-08 07:35:25 UTC ---
Depends if pointer comparison on the architecture is the same as comparing
integer of the same size and if the alignment of the pointer is the same as its
size and all bits are significant.
E.g. you can't optimize std::equal of say long double that way (e.g. on x86_64
there are 6 bytes of padding in it), but not even float/double (+/-0).  Not
sure e.g. on s390 31-bit if pointer comparison includes the topmost bit or not.

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |krebbel at gcc dot gnu.org

--- Comment #3 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-08 08:12:29 UTC ---
Thanks Jakub. Indeed, I knew about floats, but for pointers looks like there is
more hope, in general, have to investigate a bit further. About s390, let's ask
Andreas...

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[marc.glisse at normalesup dot org]

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

Marc Glisse <marc.glisse at normalesup dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |marc.glisse at normalesup
                   |                            |dot org

--- Comment #4 from Marc Glisse <marc.glisse at normalesup dot org> 2011-10-08 08:50:00 UTC ---
This seems to call for a traits class (provided by compiler magic) that tells
whether objects are memcmp-comparable (although we might have to be careful to
ask it about the status of T[] instead of plain T, not sure about that). There
are already traits telling whether objects can be copied with memcpy, (I think)
whether objects can be initialized with bzero, etc.

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[paolo.carlini at oracle dot com]

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

--- Comment #5 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-08 09:28:10 UTC ---
The analogy with copying and traits is enticing, but before reading Marc's
message, I wondered: for pointers, which kind of improvement are we talking
about? Comparing 64 bits at a time in a tight loop doesn't seem so bad...

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[marc.glisse at normalesup dot org]

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

--- Comment #6 from Marc Glisse <marc.glisse at normalesup dot org> 2011-10-08 10:59:31 UTC ---
(In reply to comment #5)
> The analogy with copying and traits is enticing, but before reading Marc's
> message, I wondered: for pointers, which kind of improvement are we talking
> about? Comparing 64 bits at a time in a tight loop doesn't seem so bad...

glibc uses SSE2 to work with 128 bits (but it is a bit more than a simple
comparison in this case) and the hand-written asm might be a bit better than
what gcc generates.

My suggestion about traits is actually not such a good idea, since comparison
operators are not generated by the compiler for non-builtin types.

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[paolo.carlini at oracle dot com]

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

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-08 11:19:04 UTC ---
I see, in principle 256 bits too at a time, with avx or something, I guess.
That reminds me, i dont's why appropriate command line switches should not
trigger the use of the same instructions anyway: these loops are *really*
simple (for a range specified via pointers)!!

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[jakub at gcc dot gnu.org]

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-10-08 11:34:51 UTC ---
I guess the problem with autovectorization of loop like:
  for (i = 0; i < n; i++)
    if (array1[i] != array2[i])
      break;
  return i == n;
is the control flow in the loop and that the compiler can't know that it is ok
to access array1[i + 1] (assuming i < n) even when array1[i] == array2[i].
One would need to write something like
if (n >= 4)
  for (i = 0; i < n - 3; i += 4)
    if ((array1[i] != array2[i])
        | (array1[i+1] != array2[i+1])
        | (array1[i+2] != array2[i+2])
        | (array1[i+3] != array2[i+3]))
      return 0;
for (; i < n; i++)
  if (array1[i] != array2[i])
    return 0;
return 1;
to get it SLP vectorized.

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |vincenzo.innocente at cern
                   |                            |dot ch

--- Comment #9 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-08 11:44:08 UTC ---
Thanks Jakub. Maybe Vincenzo is interested in this exchange, we vaguely
discussed a few times the idea of vectorization-friendly (or even explicit),
<numeric>, etc.

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |paolo.carlini at oracle dot
                   |                            |com

--- Comment #10 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-08 11:56:23 UTC ---
Naively, by 'vectorization-friendly' I mean a rewrite of the trivial loops
encoding explicitly the specified semantics (see, for example the 2nd
difficulty pointed out by Jakub). If we find a way to do that effectively but
still abstracting from the detail of the vector instructions, seems a great
idea! Does something similar already exist?

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[jakub at gcc dot gnu.org]

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

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-10-08 12:20:34 UTC ---
One possibility would be some fallthru hint to the compiler similar to
__builtin_assume_aligned that would tell the compiler that certain range of
bytes will not trap/fault on reading and thus it is safe to read it
speculatively.
ptr = __builtin_assume_object_size (ptr, length);
or similar.  You could just insert it before the loop and let it be vectorized.
But I believe we don't vectorize even
void *array1[1024], *array2[1024];
int foo (void)
{
  int i;
  for (i = 0; i < 1024; i++)
    if (array1[i] != array2[i])
      break;
  return i == n;
}
where the will not fault/trap for i 0 .. 1023 is already known (or can be
known).

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[paolo.carlini at oracle dot com]

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

--- Comment #12 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-08 12:57:55 UTC ---
Did you recently check even simpler loops, single range, like std::accumulate?
I'm trying to figure out if we can deal in a light way with the simpler cases,
like provide hints, and then attack nastier cases, rewrite loops, file specific
autovect enhancement PRs motivated by the C++ library.

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[jakub at gcc dot gnu.org]

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

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-10-08 13:08:21 UTC ---
So far I've been mostly looking at C loops (e.g. the ones reported by Vincenzo
or derived from those), or, e.g. with
http://gcc.gnu.org/ml/gcc-patches/2011-10/msg00135.html for std::vector loops.

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[vincenzo.innocente at cern dot ch]

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

--- Comment #14 from vincenzo Innocente <vincenzo.innocente at cern dot ch> 2011-10-08 13:48:22 UTC ---
Thanks for adding me in the loop.
I wonder if we can reuse
-funsafe-loop-optimizations 
to force loop vectorization.
I know that INTEL has introduced a specific pragma to force vectorization for
instance.
Maybe gcc can do the same…

in any case recoding in
if ((array1[i] != array2[i])
        | (array1[i+1] != array2[i+1])
        | (array1[i+2] != array2[i+2])
        | (array1[i+3] != array2[i+3]))

is Vector and size specific (SSE, AVX, future-1024) char,float,double
so very suboptimal...

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[paolo.carlini at oracle dot com]

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

--- Comment #15 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-11 11:05:02 UTC ---
Andreas, can I have your feedback about this? Is it safe or not to compare s390
pointers with memcmp?

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[krebbel at gcc dot gnu.org]

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

--- Comment #16 from Andreas Krebbel <krebbel at gcc dot gnu.org> 2011-10-11 11:41:12 UTC ---
(In reply to comment #15)
> Andreas, can I have your feedback about this? Is it safe or not to compare s390
> pointers with memcmp?

On s390 with 31 bit addressing the uppermost bit indicates to the hardware that
31 bit addressing is used instead of just 24 bit. This indeed is a problem when
creating pointers from integers, what is anyway not backed by the C standard,
or when using __builtin_return_address without masking the bits.

However GCC does *not* mask the bits when comparing two pointer values.  So
(void*)0x00000000 == (void*)0x80000000 does *not* evaluate to true on s390. To
my understanding using a memcmp would not break things for s390. If it is
broken with memcmp it was broken before as well.

I don't know how this works with ARM. I think they put their THUMB markers into
the lower order bits of an address and perhaps we should better check how they
implement a pointer compare.

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011-10-11
                 CC|                            |bernds at codesourcery dot
                   |                            |com
     Ever Confirmed|0                           |1

--- Comment #17 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-11 11:53:45 UTC ---
Ah, thanks for the very complete information, Andreas. Thus, I say, let's add
in CC also a person knowledgeable about ARM, and take a final decision whether
we want to apply this change for 4.7.0 unconditionally.

Bernd, can you tell us whether it would be safe to compare ARM pointers with
memcmp?

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[bernds at gcc dot gnu.org]

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

Bernd Schmidt <bernds at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bernds at gcc dot gnu.org

--- Comment #18 from Bernd Schmidt <bernds at gcc dot gnu.org> 2011-10-11 12:03:09 UTC ---
I think there are better people to answer ARM questions, but to the best of my
knowledge, there is no problem on that target.

I've tried to grep for something that might have an issue, and only found a

(define_expand "canonicalize_funcptr_for_compare"

and

/* We need a libcall to canonicalize function pointers on TARGET_ELF32.  */
#define CANONICALIZE_FUNCPTR_FOR_COMPARE_LIBCALL \
  "__canonicalize_funcptr_for_compare"

in config/pa.

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|bernds at codesourcery dot  |
                   |com                         |

--- Comment #19 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-11 12:08:00 UTC ---
Ok, thanks, let's go ahead and be done with it. Between now and the release of
4.7.0 target maintainers will have plenty of time to report back issues.

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.7.0

--- Comment #21 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-11 12:40:00 UTC ---
Applied.

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[paolo at gcc dot gnu.org]

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

--- Comment #20 from paolo at gcc dot gnu.org <paolo at gcc dot gnu.org> 2011-10-11 12:39:23 UTC ---
Author: paolo
Date: Tue Oct 11 12:39:18 2011
New Revision: 179801

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=179801
Log:
2011-10-11  Emil Wojak  <emil@wojak.eu>

    PR c++/50661
    * include/bits/stl_algobase.h (equal): Compare arrays of pointers
    too with memcmp.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_algobase.h

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[vincenzo.innocente at cern dot ch]

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

--- Comment #22 from vincenzo Innocente <vincenzo.innocente at cern dot ch> 2011-10-11 16:12:18 UTC ---
in reference to jakub comment #8
actually there was this patch proposing a "ivdep macro" (identical to INTEL's
one!)  that never made to mainline
http://gcc.gnu.org/ml/gcc-patches/2005-02/msg01560.html
what about  it?

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[pcarlini at gmail dot com]

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

--- Comment #23 from pcarlini at gmail dot com 2011-10-11 19:01:02 UTC ---
> 
> that never made to mainline
> http://gcc.gnu.org/ml/gcc-patches/2005-02/msg01560.html
> what about  it?

Eh, bisognerebbe ricostruire, ma mi sa che è stato proprio nel periodo nel
quale Apple ha smesso di contribuire a GCC, un piccolo ritardo e addio! Adesso
toccherà in caso riscriverla. Però sarebbe da capire se i maintainer in primo
luogo LA VOGLIONO una roba del genere!

Paolo

[Bug libstdc++/50661] std::equal should use more efficient version for arrays of pointers

[paolo.carlini at oracle dot com]

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

--- Comment #24 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-10-11 19:10:12 UTC ---
:) Sorry about the italian chattering between me and Vincenzo