Archive

Posts Tagged ‘C++’

When True Is Not True Anymore

July 18, 2010 13 comments

We all know that accessing uninitialized variables in C and C++ usually leads to some kind of undefined behavior one usually wants to avoid. What I didn’t know until recently is that uninitialized bool values might be especially malicious beasts. To see what they can do to you, take a look at the following program, and try to predict its output:

#include <string>
#include <iostream>

using namespace std;

namespace {

    inline string stringify(const bool value)
    {
        return (value ? "true" : "false");
    }

    struct Struct
    {
        long l;
        bool u;
    };
}

int main()
{
    Struct s;

    if(true != s.u)
        cout << stringify(true) << " != " << stringify(s.u) << endl;
}

Now type g++ stringify.cc -o stringify and run the generated executable. Here is what you might see on some platforms:

$ ./stringify 
true != true

Yes, you got that right true != true! I get this behaviour with g++-4.3 and g++-4.4 on Gentoo (x86 and x86_64) as well as with g++-4.1 and g++-4.4 on Ubuntu 9.10 (x86_64). Before attempting to explain what happened here, I want to summarize a few additional facts:

  • Several attempts to make this program shorter without ending up with something boring failed.
  • Turning on optimization causes g++ optimize all if statements away (especially the implicit one in stringify) under the assumption that s.u is false, which again leads to a much more sane output.
  • I could not reproduce this with icc-11.1.

So, what happened? Is g++ broken? Actually the answer is no. Accessing uninitialized memory leads to undefined behavior, and undefined means undefined. In fact the C++0x Final Committee Draft contains a footnote that explicitly mentions the oddity we have just seen:

47) Using a bool value in ways described by this International Standard as “undefined,” such as by examining the value of an
uninitialized automatic object, might cause it to behave as if it is neither true nor false.

This is not that surprising if one considers that at assembler level, a bool is not represented by a single bit, but at least by a byte. An uninitialized byte might have 256 different values, and not just two. One could of course consistently map 0 to false and everything else to true, but this is not what g++ does. To see what I mean, take a look at the following assembler snippet, that g++ generated for the if statement in line 24:

movzbl  -40(%rbp), %eax  # move s.u to eax.
xorl    $1, %eax         # xor eax with 1.
testb	%al, %al         # check if the low byte of eax is 0.
je      .L8              # jump to .L8 if so.

If the jump is taken, the body of the if statement in line 24 is skipped, otherwise it is executed. Now the xorl in line 2 switches the lowest bit in eax, leaving all other bits unchanged. Therefore s.u is considered to be equal to true if and only if it has the byte value 0x01.

Now lets take a look at the assembler that represents the ternary operator in stringify:

cmpb $0, -36(%rbp)    # compare the argument with 0.
je   .L2              # jump to .L2 if the argument is 0.
movl $.LC0, %eax      # store "true" in eax.
jmp  .L3              # jump out.
.L2:
     movl $.LC1, %eax # store "false" in eax.
.L3:

Here g++ maps 0 to false and every other value to true. This means that if the actual byte value of s.u is for example 0xFF (which for some reason is what cgdb keeps telling me locally), the if in line 24 will be taken as if s.u was false, but stringify will behave as if s.u was true.

Categories: Programming Tags:

Using C++0x Variadic Templates to Pretty-Print Types

April 18, 2010 3 comments

Recently I stumbled over an exercise in the very interesting book C++ Template Metaprogramming. The challenge of the exercise is to make something like the following compile and do what you expect:

cout << PrintType<int const* const**&>() << endl;

Note that we cannot use typeid, as typeid(T).name() is not required to print anything meaningful, and in practice doesn’t. As long as we don’t support function pointers, the problem from above can be solved rather easily using template specializations, although it requires quite some typing:

#ifndef HH_PRINT_TYPE
#define HH_PRINT_TYPE

#include <ostream>
#include <boost/tr1/type_traits.hpp>
#include <boost/lexical_cast.hpp>

namespace mine {

    template<class T_> struct PrintType
    {
        // Never used directly.
    };

    /**
     * For plain types we don't know.
     *
     * Could be enhanced by using type_traits.
     */
    template<class T_>
    std::ostream& operator<<(std::ostream& os, PrintType<T_>)
    {
        os << "T";
        return os;
    };

    /**
     * For void.
     */
    template<>
    std::ostream& operator<<(std::ostream& os, PrintType<void>)
    {
        os << "void";
        return os;
    };

    /**
     * For int.
     */
    template<>
    std::ostream& operator<<(std::ostream& os, PrintType<int>)
    {
        os << "int";
        return os;
    };

    /**
     * For char.
     */
    template<>
    std::ostream& operator<<(std::ostream& os, PrintType<char>)
    {
        os << "char";
        return os;
    };

    /**
     * For const qualified types.
     */
    template<class T_>
    std::ostream& operator<<(std::ostream& os, PrintType<T_ const>)
    {
        os << PrintType<T_>() << " const";
        return os;
    };

    /**
     * For volatile qualified types.
     */
    template<class T_>
    std::ostream& operator<<(std::ostream& os, PrintType<T_ volatile>)
    {
        os << PrintType<T_>() << " volatile";
        return os;
    };

    /**
     * For const volatile qualified types.
     */
    template<class T_>
    std::ostream& operator<<(std::ostream& os, PrintType<T_ const volatile>)
    {
        os << PrintType<T_>() << " const volatile";
        return os;
    };

    /**
     * For reference types.
     */
    template<class T_>
    std::ostream& operator<<(std::ostream& os, PrintType<T_&>)
    {
        os << PrintType<T_>() << "&";
        return os;
    };

    /**
     * For pointers.
     */
    template<class T_>
    std::ostream& operator<<(std::ostream& os, PrintType<T_*>)
    {
        os << PrintType<T_>() << "*";
        return os;
    }

    /**
     * For pointers to members.
     */
    template<class ClassT_, class MemberT_>
    std::ostream& operator<<(std::ostream& os, PrintType<MemberT_ ClassT_::*>)
    {
        os << PrintType<MemberT_>() << " " << PrintType<ClassT_>() << "::*";
        return os;
    }

    /**
     * Helper function for array types.
     */
    template<std::size_t SizeP_, class T_>
    std::string printDimensions(PrintType<T_[SizeP_]>)
    {
        return 
            "[" + boost::lexical_cast<std::string>(SizeP_) + "]"
            + printDimensions(PrintType<T_>());
    }

    /**
     * Ends the recursion started by printDimensions(PrintType<T_[SizeP_]>).
     */
    template<class T_>
    std::string printDimensions(PrintType<T_>)
    {
        return "";
    }

    /**
     * For arrays.
     */
    template<std::size_t SizeP_, class T_>
    std::ostream& operator<<(std::ostream& os, PrintType<T_[SizeP_]>)
    {
        os << PrintType<typename std::tr1::remove_all_extents<T_>::type>()
           << printDimensions(PrintType<T_[SizeP_]>());

        return os;
    }

    /**
     * For const arrays.
     */
    template<std::size_t SizeP_, class T_>
    std::ostream& operator<<(std::ostream& os, PrintType<const T_[SizeP_]>)
    {
        os << "const " << PrintType<T_[SizeP_]>();
        return os;
    }

    /**
     * For volatile arrays.
     */
    template<std::size_t SizeP_, class T_>
    std::ostream& operator<<(std::ostream& os, PrintType<volatile T_[SizeP_]>)
    {
        os << "volatile " << PrintType<T_[SizeP_]>();
        return os;
    }

    /**
     * For const volatile arrays.
     */
    template<std::size_t SizeP_, class T_>
    std::ostream& operator<<(
            std::ostream& os,
            PrintType<const volatile T_[SizeP_]>)
    {
        os << "const volatile " << PrintType<T_[SizeP_]>();
        return os;
    }
}
#endif

Of course, we are still missing quite a few full specializations but adding them is trivial. In fact, the only part of the code above that is slightly tricky is the part between line 120 and 147, that supports pretty-printing of potentially multi dimensional arrays. Also note the explicit overloads for const volatile at lines 80 and 172. Without them we would get ambiguity errors if trying to pretty print a type that is qualified as such.

While this is all very nice and impressive, the code above still fails us miserably if we do something like

 cout << mine::PrintType<int(int, char, void*)>() << endl;

or even

 cout << mine::PrintType<int(SomeClass::*)(int, char, void*, ...)>() << endl;

as we didn’t yet add support for function pointers. We can of course fix this by adding more specializations, but as functions can take a nearly arbitrary number of arguments (the C++0x Final Committee Draft suggests implementations to support at least 256), doing this in C++03 would be a rather unpleasant experience. Using C++0x variadic templates on the other hand side, supporting function types is not a big deal (as soon as one understands how variadic templates work ;-)):

#ifdef __GXX_EXPERIMENTAL_CXX0X__ //<-- set by gcc for '-std=c++0x'.
    /**
     * Helper struct for printing parameter lists.
     *
     * @tparam StartsP_
     *  true iff we are at the start of the list (needed to omit
     *  commas in the output).
     * @tparam ArgsT_
     *  the actual arguments.
     */
    template<bool StartsP_, class... ArgsT_> struct PrintParameters
    {
        // Never used directly.
    };

    /**
     * For parameter lists.
     */
    template<bool StartsP_, class ArgT, class... ArgsT_>
    std::ostream& operator<<(
            std::ostream& os,
            PrintParameters<StartsP_, ArgT, ArgsT_...>)
    {
        os << (StartsP_ ? "" : ", ") 
           << PrintType<ArgT>()
           << PrintParameters<false, ArgsT_...>();

        return os;
    }

    /**
     * Terminates the recursion.
     */
    template<bool StartsP_>
    std::ostream& operator<<(std::ostream& os, PrintParameters<StartsP_>)
    {
        return os;
    }

    /**
     * For function pointers.
     */
    template<class RetT_, class... ArgsT_>
    std::ostream& operator<<(std::ostream& os, PrintType<RetT_(ArgsT_...)>)
    {
        os << PrintType<RetT_>() 
           << "(" << PrintParameters<true, ArgsT_...>() << ")";

        return os;
    }

    /**
     * For member functions.
     */
    template<class ClassT_, class RetT_, class... ArgsT_>
    std::ostream& operator<<(
            std::ostream& os,
            PrintType<RetT_(ClassT_::*)(ArgsT_...)>)
    {
        os << PrintType<RetT_>() 
           << "(" << PrintType<ClassT_>() 
           << "::*)(" << PrintParameters<true, ArgsT_...>() << ")";

        return os;
    }

    /**
     * For parameter lists with varargs.
     */
    template<bool StartsP_, class... ArgsT_> struct PrintParamtersWithVarArgs
    {
        // Never used directly.
    };

    /**
     * For function pointers with varargs.
     */
    template<class RetT_, class... ArgsT_>
    std::ostream& operator<<(
            std::ostream& os,
            PrintType<RetT_(ArgsT_... ...)>)
    {
        os << PrintType<RetT_>() 
           << "(" << PrintParameters<true, ArgsT_...>() << "...)";

        return os;
    }

    /**
     * For member functions with varargs.
     */
    template<class RetT_, class ClassT_, class... ArgsT_>
    std::ostream& operator<<(
            std::ostream& os,
            PrintType<RetT_(ClassT_::*)(ArgsT_... ...)>)
    {
        os << PrintType<RetT_>()
           << "(" << PrintType<ClassT_>()
           << "::*)(" << PrintParameters<true, ArgsT_...>() << "...)";

        return os;
    }

    /**
     * For rvalue references (for completeness).
     */
    template<class T_>
    std::ostream& operator<<(std::ostream& os, PrintType<T_&&>)
    {
        os << PrintType<T_>() << "&&";
        return os;
    };
#endif

The main workhorse in the code above is the operator at line 19, that calls itself recursively in line 26 until it eventually degenerates into the operator defined at line 34. Also note the double ellipsis in lines 81 and 95: The first one unpacks the template parameter list, the second one is for old style varargs.

Last but not least: Feel free to come up with suggestions or comments.

Categories: Programming Tags: , ,

Saying Goodbye to boost::regex.

April 5, 2010 5 comments

Yesterday I decided to finally say goodbye to boost::regex (a.k.a tr1::regex) and use PCRE instead in Untropy. The reason for this is, that boost::regex doesn’t support UTF-8 properly. Yes, there is boost::u32regex together with a few related types and functions, but as the name says, they work with UTF-32, not UTF-8. This wouldn’t be a real problem if UnicodeString was a proper C++ string type, like Glib::ustring for example. Unfortunately it isn’t, as it misses the usual typedefs and iterators; it doesn’t even define ostream operators and seems to have problems with -D_GLIBCXX_DEBUG. In practice this meant that working with boost::u32regex introduced quite a few explicit string conversions, that didn’t make the API very convenient at all. And no, I’m not going to use UnicodeString as my default string type, because this would make almost every other string related API harder to use. As I strongly prefer Perl regular expressions over other flavours, using PCRE was the only reasonable choice. After all, this library is widely used, feature rich, and deals with UTF-8 properly. It also has two C++ wrappers, pcrecpp and PCRE++. Unfortunately they are both unusable:

  • pcrecpp exposes one of the most crippled C++ APIs I’ve ever seen and is poorly documented, although it is shipped with PCRE and has been provided by Google.
  • PCRE++ looks much much saner, but fails to properly separate compiled patterns from match results, although the underlying C API does exactly that.

Being accustomed to the very well designed java.util.regex API, I was left with no other choice than to write a C++ wrapper myself. Luckily the PCRE C API isn’t that bad at all and well documented (although you should really spend at least one hour reading the man page carefully while experimenting with small examples, as the API is definitely neither self explanatory nor fool proof). Finally it took me about 8 hours to design, implement and test this C++ API, that is roughly modelled after java.util.regex, and migrate existing code to it. I’m seriously considering putting an extended and overworked version of this API in a standalone library as soon as I have time.

Propagating exceptions between different threads in C++0x

March 29, 2010 Leave a comment

Yesterday I finally decided to make use of all available C++0x features that are supported by gcc-4.4 in Untropy (a very specialized tool for a limited audience that is not of interest here). Whats interesting about this, is that what finally made the important difference for me is not one of the prominent features like Rvalue References, Auto Typed Variables or Initializer Lists. Instead it’s some seemingly unspectacular type called std::exception_ptr and a few related functions. This rather minimal, but very useful API has been designed to allow transporting exceptions between threads. Here is how this can be done with boost::thread (includes and namespaces are omitted for clarity – you can grab the full source here):

   /**
     * A callable implementation that allows exception propagation between 
     * threads for boost::tread.
     */
    class Callable
    {
        public:

        /**
         * Default copy constructor.
         *
         * @attention
         *  Should not be invoked from different threads with the same objects.
         */
        Callable(const Callable&) = default;

        /**
         * Default assignment operator.
         *
         * @attention
         *  Should not be invoked from diffenrent threads with the same objects.
         */
        Callable& operator=(const Callable&) = default;

        /**
         * To be called by boost::thread.
         */
        void operator()() const;

        /**
         * Rethrows pending exceptions.
         */
        void rethrowIfPending() const;

        /**
         * Returns true iff an exception is pending.
         */
        bool isExceptionPending() const;

        virtual ~Callable() = default;

        protected:

        Callable();

        /**
         * Does the actual work.
         *
         * @attention
         *  Exceptions thrown from this method will be catched in operator()(),
         *  and can be rethrown by rethrowIfPending() const.
         */
        virtual void doWork() const = 0;

        private:
        
        struct ExceptionContainer
        {
            std::exception_ptr exceptionPtr;
        };

        std::tr1::shared_ptr<boost::recursive_mutex> m_exceptionMutex;
        std::tr1::shared_ptr<ExceptionContainer> m_exception;
    };

Note that the only reason we explicitly declared a copy constructor and an assignment operator is for the comments above them. Luckily the C++0x feature Defaulted and Deleted Functions allows us to omit some boilerplate code here. But lets move to the more interesting, and less documented private part of the declaration above: Because boost::thread invokes a copy of our Callable, we cannot store pending exceptions in the class directly if we want them to be visible from outside. To solve this problem, we actually store them in a tr1::shared_ptr to a helper struct. Last but not least, we use a boost::recursive_mutex to guard the stored exception. Here is the implementation (the full source is here):

    void Callable::operator()() const
    {
       try
       {
           doWork();
       }
       catch(...)
       {
           boost::recursive_mutex::scoped_lock lock(*m_exceptionMutex);
           m_exception->exceptionPtr = current_exception();
       }
    }

    void Callable::rethrowIfPending() const
    {
        boost::recursive_mutex::scoped_lock lock(*m_exceptionMutex);
        if(isExceptionPending())
            rethrow_exception(m_exception->exceptionPtr);
    }

    bool Callable::isExceptionPending() const
    {
        boost::recursive_mutex::scoped_lock lock(*m_exceptionMutex);
        return (exception_ptr() != m_exception->exceptionPtr);
    }

    Callable::Callable()
        : m_exceptionMutex(new boost::recursive_mutex()),
          m_exception(new ExceptionContainer)
    {

    }

Using the C++0x features std::current_exception() in line 10 and std::rethrow_exception in line 18, thats all that needs to be done. The careful reader might notice, that Callable isn’t entirely thread save itself: Coping or assigning Callable instances that share internal state from within multiple threads will most likely result in undefined behavior, because tr1::shared_ptr is not thread save. In theory, C++0x contains APIs for accessing shared_ptr instances atomically from within multiple threads, but they are not available with gcc-4.4. Of course, I could have implemented a thread save reference counter in the Callable class directly, but that doesn’t seem worth the effort, as manipulating identical Callable instances from multiple threads is an error anyway. Last but not least: Here is a unit test for the code above, that also illustrates how it is meant to be used.

Categories: Programming Tags: , ,

Java Anti-Patterns revisited

December 8, 2009 5 comments

Today I’ve stumbled over an interesting Homepage that contains a section about Java Anti-Patterns. It’s really well written and funny to read. Unfortunately it also contains some advises that I cannot agree with at all:

Lists are overrated: I would say quite the opposite: Prefer lists to arrays unless you have a very good reason not to. Arrays might perform considerably better in some cases, but they are far more easily used incorrectly (because of a major design flaw) and don’t mix well with generics. Also, programming against the List interface is more convenient and adds an additional layer of abstraction that allows you to change the actual List implementation easily. EffJava2 dedicates Item 25 to this topic alone.

Hashtable, HashMap and HashSet are overrated: I cannot agree here too: Yes, the entry wrappers are bigger than one might initially expect as they contain an additional forward reference and a cache for the hash code. And yes, HashSet is in fact implemented using a HashMap. I have to admit that this made me a bit curious, so I looked at the corresponding implementations in libstdc++ for unordered_map and unordered_set. What I found out is that they are using basically the same entry wrappers, although they let you decide with a C++ template parameter if the hash code is cached, which is false by default. Here is a comment found in one of the related headers:

// Nodes, used to wrap elements stored in the hash table. A policy
// template parameter of class template _Hashtable controls whether
// nodes also store a hash code. In some cases (e.g. strings) this
// may be a performance win.

To be fair however, it should be noted, that the C++ implementation does not waste a pointer if caching is disabled. Also, although they too use a shared implementation for unordered_map and unordered_set, C++ templates allows them to do this without wasting any space for sets, or doing lots of casting (which would be unavoidable if one tried the same approach in Java). To cut a long story short: The implementations that are shipped with the Java standard library aren’t that bad at all, they just reflect the fact that Java isn’t C++, which features a turing complete, code generating metalanguage via the template mechanism, that looks like Java generics only on the surface. Should your analysis reveal that the Java implementations of HashSet and HashMap generally (not only in a few hotspots) waste too much space, then most likely Java isn’t the right tool for your task at all. Otherwise just use HashMap and HashSet and don’t care about the memory overhead, which isn’t that bad as long as you don’t store small objects in these containers. Using exotic Map implementations like IdentiyHashMap is the right thing to do only in rare occasions, because IdentiyHashMap intentionally violates Map‘s general contract which is normally not what you want.

Not properly propagating the exception: Here the author claims that you may loose information if you do

catch(SomeException e)
{
    throw new RuntimeException(e);
}

instead of

catch(SomeException e)
{
    throw new RuntimeException(e.getMessage(), e);
}

which is true in theory for the detail message of the constructed RuntimeException, but should happen in practice only if SomeException overrides Throwable.toString() or Throwable.getLocalizedMessage() in a rather obscure way. I’m not aware of any exceptions that do this (and if I was I would rather fix them), but maybe I missed something, so please correct me if I’m wrong.

Too much static: In this item the author makes an interesting point about storing loggers in static fields prevents unused classes from being garbage collected. This sounds perfectly reasonable and caused me some headaches as I always store loggers in static fields. Some research however revealed, that it is not true. Let me cite the relevant part from the Java Language Specification:

A class or interface may be unloaded if and only if its defining class loader may be reclaimed by the garbage collector as discussed in §12.6. Classes and interfaces loaded by the bootstrap loader may not be unloaded.

So abandoning static loggers won’t change anything as far as class unloading is concerned. Storing loggers in normal instance fields on the other hand side can be annoying in entity beans and can cause screwups with serialization, as correctly pointed out in The transient trap. So my advice here is: Just store your loggers in private static final fields, and be done with it. Should you ever have the need to access the logger of a superclass, you can still obtain it explicitly by something like

Logger log = LoggerFactory.getLogger(getClass().getSuperclass());

although I don’t know any usecase for this other than someone deliberately obfuscating the source of the log messages.

Categories: Programming Tags: , ,
Follow

Get every new post delivered to your Inbox.