c++ - ¿Por qué GCC-O3 causa infinita std:: distance con iteradores de filtro sobre std:: deque?

g++ optimization flags

Question

Después de mucho dolor y miseria, he rastreado un comportamiento muy extraño donde std::distance nunca vuelve cuando se le da un rango de boost::filter_iterator s sobre std::deque . Parece que el problema es exclusivo de GCC (6.1+) con optimizaciones de -O3. Aquí hay un ejemplo que demuestra el comportamiento ofensivo:

#include <string>
#include <deque>
#include <iterator>
#include <iostream>

#include <boost/iterator/filter_iterator.hpp>

struct Foo
{
    std::string bar, s = "";
    char a = ''/0'';
};

int main()
{
    const std::deque<Foo> foos(14, {""});
    const std::string test {};
    const auto p = [test] (const auto& foo) { return foo.bar == test; };
    using boost::make_filter_iterator;
    const auto begin = make_filter_iterator(p, std::cbegin(foos), std::cend(foos));
    const auto end   = make_filter_iterator(p, std::cend(foos), std::cend(foos));
    std::cout << std::distance(begin, end) << std::endl;
}

Algunas observaciones:

• GCC con optimizaciones -O2 o menos devuelve como se esperaba.
• Clang (3.8) devuelve la respuesta correcta con cualquier nivel de optimización.
• Cambiar std::deque a std::vector o std::list da como resultado el comportamiento esperado.
• El 14 es crítico; cualquier cosa menos y el problema desaparece.
• El sizeof(Foo) es importante; eliminar s o a hace que el problema desaparezca.
• La captura de la test por referencia, o simplemente la comparación con una expresión constante (por ejemplo, foo.bar == " " ) da como resultado un comportamiento normal.
• No hay advertencias del compilador (con -Wall -Wextra -pedantic ).
• Valgrind informa que no hay errores.
• Use fsanitize=undefined y el problema desaparece.

¿Que esta pasando?

Answer 1

Creo que estos hallazgos a continuación pueden ser útiles para mejorar el informe de errores y también para usar en su código para solucionar el problema.

Al depurar la salida optimizada y jugar con indicadores de optimización y con cambios de código menores, he llegado a la conclusión sobre los indicadores de optimización específicos que están causando el error.

El conjunto de opciones es:

-O -fno-auto-inc-dec -fno-branch-count-reg -fno-combine-stack-adjustments -fno-compare-elim -fno-cprop-registers -fno-dce -fno-defer-pop -fno-delayed-branch -fno-dse -fno-forward-propagate -fno-guess-branch-probability -fno-if-conversion2 -fno-if-conversion -fno-inline-functions-called-once -fno-ipa-pure-const -fno-ipa-profile -fno-ipa-reference -fno-merge-constants -fno-move-loop-invariants -fno-reorder-blocks -fno-shrink-wrap -fno-split-wide-types -fno-ssa-backprop -fno-ssa-phiopt -fno-tree-bit-ccp -fno-tree-ccp -fno-tree-ch -fno-tree-coalesce-vars -fno-tree-phiprop -fno-tree-sink -fno-tree-slsr -fno-tree-dse -fno-tree-forwprop -fno-tree-fre -fno-unit-at-a-time -fno-tree-ter -fno-tree-sra -fno-tree-copy-prop -fstrict-aliasing -ftree-slp-vectorize -std=c++14

Lo siento por ese conjunto tan largo, pero lo que realmente quería era algo así como: -O0 -ftree-copy-prop -ftree-pta -ftree-dce -fstrict-aliasing -ftree-slp-vectorize (lo he intentado con -Og también) más los pasos mágicos de O1 ...

Tenga en cuenta que solo -O3 -f-no-tree-slp-vectorize ya arreglará el comportamiento, pero al usar las opciones completas que he enviado, la depuración es casi fácil ...

Además, parece que la existencia del operador ==(string, string) está generando la confusión en el compilador.

Si examina el código pegado debajo de todos los comentarios del código #if 0, cuando está activado funciona en el lugar del código original, puede encontrar el problema donde yo no lo hice.

Tenga en cuenta que el operador ==() ni siquiera se llama porque foo.a != ''/0'' siempre es verdadero en la prueba. Por lo tanto, parece que su existencia hace que el compilador genere el código incorrecto.

Tenga en cuenta también que cualquiera de los códigos comentados dentro del bucle también cambia el comportamiento al esperado y es por eso que sospeché de las banderas de vectorización para los principiantes.

#include <string>
#include <deque>
#include <iterator>
#include <iostream>

#include <boost/iterator/filter_iterator.hpp>
#include <string.h>

struct Foo
{
    std::string bar, s = "";
    char a = ''n'';
};

std::ostream& operator<<(std::ostream& os, const Foo& f)
{
    os << f.bar << ''/'' << f.a;
    return os;
}

int main()
{
    std::deque<Foo> foos(14, {"abc"});
    const std::string test {"abc"};
    Foo other;
    other.bar = "last"; other.a = ''l'';
    foos.push_back(other);
    other.bar = "first";
    other.a = ''f'';
    foos.push_front(other);
    //
#if 0
    const auto p = [test] (const auto& foo) { return foo.a != ''/0''; };
#elif 0
    const auto p = [test] (const auto& foo) {
        bool  rc =  (foo.a != ''/0'');
        if (!rc)
            rc = (foo.bar == std::string(test));
        return rc;
    };
#elif 1
    const auto p = [test] (const auto& foo) {
        bool  rc =  (foo.a != ''/0'');
        if (!rc)
            rc = (foo.bar == test);
        return rc;
    };
#endif
    using boost::make_filter_iterator;
    const auto begin = make_filter_iterator(p, std::cbegin(foos), std::cend(foos));
    const auto end   = make_filter_iterator(p, std::cend(foos), std::cend(foos));
    std::cout << std::distance(end, end) << std::endl;
    std::cout << std::distance(begin, begin) << std::endl;
    std::cout << std::distance(std::cbegin(foos), std::cend(foos)) << std::endl;

    auto __first = begin;
    auto __last = end;

    int __n = 0;
    //std::cout << __last << std::endl;
    //std::deque<char> trace;
    //Foo trace[21];
    const int max = foos.size();
    char trace[max+5]; memset(trace, ''c'', sizeof(trace));

    std::cout << max << std::endl;
    std::cout << *__last << std::endl;

    while (__first != __last)
    {
        trace[__n] = (*__first).a;
        //trace[__n] = (*__first);
        //trace.push_back((*__first).a);
        //std::cout << *__first << std::endl;
        ++__n;
        ++__first;
        if (__n > max + 5)
            break;
        //std::cout << __n << std::endl;
        //std::cout << (__first != __last) << std::endl;
    }

    for (auto f: trace)
        std::cout << f  << std::endl;
    std::cout << "Tadaaaaa: " <<  __n << std::endl;

    //std::cout << std::distance(begin, end) << std::endl;

}

Answer 2

Este comportamiento se debió a una falla de GCC causada por una mala optimización de vectorización. Se ha emitido una solución, que debería aparecer en GCC 6.3.

Para aquellos que están atrapados con GCC 5.4 - 6.2, la opción del compilador -fno-tree-slp-vectorize ''solucionará'' el problema.