1. Understanding C++ Allocators

    My last post, Stack Allocators for STL Containers, may have been a little confusing for some folks who are unfamiliar with the C++ Standard Library. Even those familiar with the Standard Library may not have dealt with allocators, so let’s take a step back and go over them.

    If one looks into any STL documentation, one will notice an optional Allocator template parameter to most STL classes. In the G++ implementation of the STL, this Allocator parameter defaults to std::allocator which is derived from the __gnu_cxx::new_allocator in libstdc++. If you studied the allocate and deallocate methods of the __gnu_cxx::new_allocator class, it will tell you this base class indeed uses new and delete to allocate and deallocate memory. I am going to leave it as an exercise for the reader to determine how new and delete get memory from the system.

    So why would one use another allocator besides the default? The reasons are aplenty, and here are some reasons that has had yours truly look into using non-default allocators.

    1. Reduce heap contention in a multi-threaded application.
    2. Reduce heap contention by reusing chunks of memory.
    3. Prevent memory fragmentation.
    4. Debugging and/or understanding memory usage in an application.
    5. Attempt to improve application performance (with debatable results).

    The std::allocator is used often enough that I believe its performance has been tuned fairly well in most implemenations, but what if I wanted to use a different allocator because of some specific need? I will use std::vector to work through my examples since it is a class that everyone is familiar with. The following shows how an instance of std::vector may be declared with and without the default allocator.

    // the basic way that a vector will be declared
    std::vector<int> my_vector;
    
    // explicitly using std::allocator as the allocator.  The instance is exactly the same as the one above
    std::vector<int, std::allocator> my_vector
    
    // using __gnu_cxx::malloc_allocator that comes with G++
    std::vector<int, __gnu_cxx::malloc_allocator> my_vector;
    
    // passing an instance of std::allocator to std::vector.  possible with G++ 4.x but not 3.x afaik.
    std::allocator my_allocator;
    

    Using a non-default allocator can be as simple as that! The last example, as far as I am aware, is only possible with libstdc++ that comes with GCC 4.x but not 3.x. It may also be possible with other implementations of the STL besides the one provided by GCC, but I do not have any experience with them. Libstdc++ itself comes with several allocators, some of which you may find interesting to work with. The libstdc++ documentation gives a pretty good description of them, so I am going to let the reader peruse them at her leisure.

     


  2. Stack Allocators for STL Containers

    When I first started learning the C programming language in college, the TAs and professors would always remind us that malloc() is expensive and can lead to memory leaks if we don’t use it properly. I understood the memory leak part, but never quite understood the expensive part until many years later.

    Back in 2008, a server application that my employer had could not run for more than 17-18 hours without running out of memory. Everyone thought it was a memory leak, but valgrind and Google Perftools disagreed, so I dug up an old conjecture made by my mentor and former manager, Nick Galbreath, that it was memory fragmentation.

    How does one go about investigating and proving that our server had a memory fragmentation problem? In my usual fashion, I went digging in the glibc source code to learn how malloc() was implemented, and learned a great deal about the fork of ptmalloc in glibc in the process. Eventually, I determined our version of malloc() (from glibc 2.3.4 in RHEL 4.x) was creating a bunch of arenas that held on to the mmap’ed memory instead of returning it to the system despite coalescing the free chunks into huge chunks. The server application used a one-thread-per-client model and ran 75 concurrent threads, each of which was relentlessly calling new() and delete(), allocating up to 200mb of 200-byte objects to serve a single request. Yes, how crazy is that?

    That problem was eventually solved by replacing glibc’s malloc with jemalloc, and the server never ran out of memory again. I came out of that exercise being forever curious about memory allocation, and how to use the Standard Template Library while avoiding the heap. I wrote a stack allocator that never made it into production because my team was somewhat wary, probably rightfully so, about playing with memory allocators, and my stack allocator got lost to time.

    A few days ago, I chanced upon an excellent article, Stack Allocators for STL Containers, written by John Wellbelove that got me really excited again. John’s stack allocator even maintains a free list so that you can reuse freed chunks of memory, which my 2008 version did not. John does a great job explaining how to use his allocator, so I highly encourage you to review it even if you don’t think it is for you. You may just be able to avoid hitting the heap unnecessary while having access to the ubiquitous STL.

    Memory allocation is not for the faint of heart, but once you learn it, it opens up a lot of possibilities. It also lets you shoot yourself in the foot.

     


  3. If you are competitor focused, you tend to slack off when your benchmarks say that you are the best. But if your focus is on customers, you keep improving.
    — Jeff Bezos
     


  4. Singletons Aren’t That Bad

    Programming 101 taught us that global variables are bad, right? So what do you do when you find yourself in a situation where you need to have one and only one instance of a class in your C/C++ application? Some answers I imagine you yelling out include:

    1. Use a global variable and extern it everywhere you need to use it.
    2. Pass a context object struct around your application that with pointers to the shared object.
    3. Use a singleton class.
    4. etc.

    Ideally, I would pick #2 since it’s nice and clean, but it wouldn’t be my go-to if I had an existing application that I need to refactor in a limited amount of time. Singletons would be my usual choice cos it is so easy to implement. Yes, singletons are basically the same thing as global variables, but the benefit of using singletons far outweigh the cost, so whatev. :)

    Using a global variable and externing it everywhere it’s used works too, right? No, and here’s why.

    1. If you have an application that you build into several static libraries and then link into one or more binaries, you will eventually run into a situation where you have to link unnecessary .a files simply cos the global variable is defined in them and is needed by another static library.
    2. Where do you instantiate the global object? In main(), or on first use? When is the first use? Perhaps use another global variable to indicate the global object has been instantiated? What if I need another global object?

    These 2 reasons alone are enough for me to way to use a singleton wrapper to hide all that away and not have to worry about it again. The following implementation is a barely-modified version of a singleton class that you will find deep in the Boost::Thread library.

    #ifndef __LAZY_SINGLETON_HPP__
    #define __LAZY_SINGLETON_HPP__
    
    namespace lazy {
    
    // this singleton wrapper class is inspired by the singleton class that is
    // distributed deep within the Boost::Thread library.
    // http://svn.boost.org/svn/boost/trunk/boost/thread/detail/singleton.hpp
    template 
    class singleton : private T
    {
    public:
        // \brief data type of the singleton class
        typedef T data_type;
    
        // \brief reference type
        typedef data_type&amp; instance_type;
    
    private:
        // \brief hidden default ctor
        singleton();
    
        // \brief hidden copy ctor
        singleton(singleton&amp;);
    
        // \brief hidden dtor
        ~singleton(singleton&amp;);
    
    public:
        // \brief get an instance of the singleton class
        static T instance();
    };
    
    template 
    T&amp; singleton::instance()
    {
        static singleton m_instance;
        return m_instance;
    }
    
    } // namespace lazy
    
    #endif // __LAZY_SINGLETON_HPP__
    

    How do I use it? Simple!

    using lazy::singleton;
    singleton::instance_type only_one = singleton::instance();
    

    The nice thing about this class is that you will never have to worry about what .a files to link cos your global variable is declared in one of the .cpp files in there. Just #include the singleton header file, use the template method and you are done.

     


  5. The Inaugural Lazy Post

    Hello, world! This inaugural post requires me to live up to the nickname I gave myself, right? Being a C++ guy, it’s not too hard to get lazy since so much is done for you, but I think there is one more thing that needs to be done that isn’t! How do you guys like writing accessors and mutators? Well, I hate it cos it’s such boilerplate code, but it also tears me up inside when I make member attributes public. So what do I do? I whip out some old-style C tricks!

    Imagine the following class that has one member attribute, m_attribute. Writing the accessor and mutator drives me crazy cos it’s so much more unnecessary typing!

    class SomeClass
    {
    public:
        SomeClass() :
            m_attribute(0)
        {
            // NOP
        }
    
        void attribute(const int _attribute)
        {
            m_attribute = _attribute;
        }
    
        const int attribute() const
        {
            return m_attribute;
        }
    
    protected:
        int m_attribute;
    };
    

    So what do I do? I came up with the following header file that generates the accessor and mutator for me.

    #ifndef __LAZY_ATTRIBUTE_HPP__
    #define __LAZY_ATTRIBUTE_HPP__
    
    #ifndef lazy_attribute
    #define lazy_attribute(type, name) \
        protected: \
            type m_##name; \
        public: \
            void name(const type& _##name) { m_##name = _##name; } \
            const type& name() const { return m_##name; }
    #endif
    
    #endif // __LAZY_ATTRIBUTE_HPP__
    

    With this macro, the SomeClass declaration will look like the following.

    class SomeClass
    {
    public:
        SomeClass() :
            m_attribute(0)
        {
            // NOP
        }
    
    protected:
        lazy_attribute(int, attribute);
    };
    

    Here is a sample program using this macro.

    #include <iostream>
    #include "lazy_attribute.hpp"
    
    class SomeClass
    {
    public:
        SomeClass() :
            m_attribute(0)
        {
            // NOP
        }
    
    protected:
        lazy_attribute(int, attribute);
    };
    
    int main(int argc, char** argv)
    {
        SomeClass a;
        std::cout << a.attribute() << "\n";
        a.attribute(5);
        std::cout << a.attribute() << "\n";
    
        return 0;
    }
    

    The lazy_attribute macro generates the accessor and mutator for the attribute member attribute automatically during compile-time and gets inline’d by the compiler. Sweet! How about const and static attributes? The lazy_const_attribute and lazy_static_attribute macros take care of them.

    #ifndef __LAZY_ATTRIBUTE_HPP__
    #define __LAZY_ATTRIBUTE_HPP__
    
    #ifndef lazy_attribute
    #define lazy_attribute(type, name) \
        protected: \
            type m_##name; \
        public: \
            void name(const type& _##name) { m_##name = _##name; } \
            const type& name() const { return m_##name; }
    #endif
    
    #ifndef lazy_const_attribute
    #define lazy_const_attribute(type, name) \
        protected: \
            const type m_##name; \
        public: \
            const type& name() const { return m_##name; }
    #endif
    
    #ifndef lazy_static_attribute
    #define lazy_static_attribute(type, name) \
        protected: \
            static type m_##name; \
        public: \
            static void name(const type& _##name) { m_##name = _##name; } \
            static type& name() { return m_##name; }
    #endif
    
    #endif // __LAZY_ATTRIBUTE_HPP__