GCC lambda optimization issue?

[Catfish3]

The following function causes my program to stall if the program was compiled with either -O2 or -O3.
See the two std::clog statements.

Using nuwen's MinGW 9.5 distro (GCC 4.7.2).
Full source code here: http://pastebin.com/jstpqDFj

void compress(std::istream &is, std::ostream &os)
{
    std::map<std::vector<char>, CodeType> dictionary;

    // "named" lambda function, used to reset the dictionary to its initial contents
    auto reset_dictionary = [&dictionary] {
        dictionary.clear();

        char c = std::numeric_limits<char>::min();

        do
        {
            dictionary.insert({{c}, dictionary.size()});
        }
        while (c++ != std::numeric_limits<char>::max());
    };

std::clog << "This gets output.\n";

    reset_dictionary();

std::clog << "This doesn't. Program stalls above.\n";

    std::vector<char> s; // String
    char c;

    while (is.get(c))
    {
        // dictionary's maximum size was reached
        if (dictionary.size() == globals::dms)
            reset_dictionary();

        s.push_back(c);

        if (dictionary.count(s) == 0)
        {
            dictionary.insert({s, dictionary.size()});
            s.pop_back();
            os.write(reinterpret_cast<const char *> (&dictionary.at(s)), sizeof (CodeType));
            s = {c};
        }
    }

    if (!s.empty())
        os.write(reinterpret_cast<const char *> (&dictionary.at(s)), sizeof (CodeType));
}

[JLBorges]

As a standalone snippet (I've assumed that CodeType is an integral type), this works as expected on GCC 4.7.2 with -O3.
http://liveworkspace.org/code/q9ogR$0

Try this snippet on the nuwen build od MinGW, and if that works as expected, the problem is not with the lambda expression.

[Catfish3]

Your code snippet works as expected. This is a bit discouraging.

[Peter87]

Make sure to flush clog.
std::clog << "This doesn't. Program stalls above." << std::endl;

[Peter87]

I think the real problem here is that the lambda invokes undefined behaviour. Signed integer overflow is UB which is exactly what happens in the loop condition when c == std::numeric_limits<char>::max(); and c is incremented. Because this is UB the compiler can assume this will never happen so my guess is that it removes the whole condition all together, causing an infinite loop.

[JLBorges]

> I think the real problem here is that the lambda invokes undefined behaviour.
> Signed integer overflow is UB which is exactly what happens in the loop
> Because this is UB the compiler can assume this will never happen

True.

> so my guess is that it removes the whole condition all together, causing an infinite loop.

AFAIK, GCC never does that for char on x86; it just wraps around as it it was unsigned char
In any case, GCC 4.7.2 does not do that in this particular case.
http://liveworkspace.org/code/q9ogR$3

And clang faithfully mimics GCC behaviour.
http://liveworkspace.org/code/q9ogR$4

There still seems to a problem in some other part of the code.

Note: GCC does apply -fstrict-overflow optimizations ( -O2 or higher ) for int, long etc.


In any case, the code is broken and needs to be modified; std::vector<unsigned char> is one option.
http://liveworkspace.org/code/q9ogR$5

[Catfish3]

Thanks for the help. I modified the lambda as seen below, and now the program works.

If you have suggestions to make it more elegant, please post.

    const auto reset_dictionary = [&dictionary] {
        dictionary.clear();

        const int minc = std::numeric_limits<char>::min();
        const int maxc = std::numeric_limits<char>::max();

        for (int c = minc; c <= maxc; ++c)
            dictionary.insert({{static_cast<char> (c)}, dictionary.size()});
    };

@ JLBorges: what is the purpose of making reset_dictionary a const object (I assume it's std::function<void()>)?

[JLBorges]

> I modified the lambda as seen below, and now the program works.

Great. So the cause of the trouble was UB spotted by Peter87.


> what is the purpose of making reset_dictionary a const object

Nothing other than that it is used as a const object. I just instinctively add const to a lot of things where many other programmers wouldn't bother.


> I assume it's std::function<void()>

The types of a closure objects are implementation defined; the IS specifies the behaviour and leaves the rest to the implementation. A closure object is a callable object, and can therefore be wrapped by a call wrapper.

[LB]

What's wrong with this?

    unsigned char c = 0;
    do
    {
        std::cout << c << ' ' << std::flush;
    }while(c++ < std::numeric_limits<unsigned char>::max());