Wednesday, August 28, 2013

STL is not thread safe, get over it

STL is not thread safe, get over it. Why it should be after all? STL is plain C++ code, compiler doesn't even know the existence of the STL, it's just C++ code released with your compiler, what the STL has in common with the C++ language is the fact that it's standardized. Given the fact that C++ and STL is standardized you can expect to have STL implemented on every platform with same guarantees enforced by the standard. You are not even obliged to use the STL deployed with your compiler indeed there are various version out there, see the roguewave ones for example (http://www.roguewave.com).
Let's take as example the std::list, let's suppose for a moment that the stl implementation it's thread safe,
some problem arise:

  1. If it's not needed to be thread safe you will get extra not needed overhead
  2. What shall do a thread calling a std::list::pop_back on an empty list?
    • Waiting for a std::list::push?
    • Returning with an "error"?
    • Throwing an exception?
    • Waiting for a certain ammount of seconds that an entry is available?
  3. It should be used in an enviroment with a single producer/single consumer, in this case it's possible to implement it without locks.
  4. Shall be multiple readers permitted?
Yes sure you can solve all the points above with a policy template, but just imagine your users complains.

Well, again, get over it, STL standardized is not thread safe you have to create your thread safe list embedding a real std::list, after all making a wrapper around an STL container is a so easy exercise that if you find difficult to do it yourself then you have to ask: "Am I ready to start with multithreading programming" even if someone provides me an out of the shelf std::list thread safe?
Consider that two different instance of  STL containers can be safely manipulated by different threads.

PS: I have written about std::list instead of the most widely used std::vector because std::vector for his own characteristics has to be used in a more "static" way with respect to an std::list and using an std::vector as a container used by multiple threads (producer/consumer) is a plain wrong choice.  






Thursday, June 13, 2013

Code inspecting Stroustrup (TC++PL4) (2nd issue)

Since I learned C++ reading one of the first edition of TC++PL and even if I'm programming using C++ since 2000 or so I'm reading the new TC++PL4 carefully as if this language is totally new to me. It seems my last post about an error found on this book will be not the unique and here we are again.
In 5.3.4.1 he introduces conditions and how two threads can interact each other communicating using events, it's presented the classical producer / consumer interaction exchanging Messages trough a queue, and this is the poor implementation proposed:

  class Message {
    // ...
  };

  queue mqueue;
  condition_variable mcond;
  mutex mmutex;

  void consumer() 
  {
     while(true) {
        unique_lock lck{mmutex};
        while (mcond.wait(lck)) /* do nothing */;
        
        auto m = mqueue.front();
        mqueue.pop();
        lck.unlock();
        // ... process m...
     }
  }

  void producer() 
  {
     while(true) {
        Message m;
        // ... fill the message ...
        unique_lock lck{mmutex};
        mqueue.push(m);
        mcond.notify_one();
     }
  }

This implementation is affected by at least three issues:

  • Unless very lucky the queue will grow indefinitely: that's because basically the consumer will wait at each cycle even if queue contains something, at the same time it has a chance (I repeat a "chance") to exit from the  condition_variable::wait() only each time the producer puts something in the queue.
  • The consumer can miss the condition_variable::notify_one event, indeed if the producer does the notify_one() but the other thread hasn't yet executed the wait() the consumer will block for no reason
  • The producer holds the unique_lock for more time than needed, the mutex has to only protect the queue not the condition as well
Let see how those producer / consumer should have been implemented:


  void consumer() 
  {
     while(true) {
        unique_lock lck{mmutex};
        while (mqueue.empty()) { // the empty condition has to be recheck indeed the thread
                                               // can get sporadic wakeup without any thread doing a notify
          mcond.wait(lck);
        }
        auto m = mqueue.front();
        mqueue.pop();
        lck.unlock();
        // ... process m...
     }
  }

  void producer() 
  {
     while(true) {
        Message m;
        // ... fill the message ...
        {
           unique_lock lck{mmutex};
           mqueue.push(m);
        }  // This extra scope is in here to release the mmutex asap
         mcond.notify_one();
     }
  }

In my opinion this should have been the version of the producer/consumer in TC++PL4, as you can see
with a simple extra scope and the right while(...) the issues reported in the bullets are solved.

There is another problem, I have to admit that this issue most of the times is a minore one:
  • The producer can issue notify_one() even if not needed, and this can be a performance issue 
to address it the producer has to "forecast" if the consumer can be in a blocked status, and this can happen only if after having acquired the mmutex the queue is empty, this is the final version of producer:

   void producer() 
  {
     while(true) {
        Message m;
        bool notifyIsNeeded = false;
        // ... fill the message ...
        {
           unique_lock lck{mmutex};
           if (mqueue.empty()) {
             notifyIsNeeded  = true;
           }
           mqueue.push(m);
        }  // This extra scope is in here to release the mmutex asap
        if ( notifyIsNeeded ) {
           mcond.notify_one();
        }
     }
  }

Writing correct code is not easy and writing correct multi-threaded is damn hard.



Sunday, June 9, 2013

Code inspecting Stroustrup (TC++PL4)

TC++PL4 is now on my desk and carefully reading it I have to say that even Stroustrup makes stupid mistakes in his classes implementations.

He illustrates a typical Vector implementation (pag. 73):

    class Vector {
    private:
        double* elem;
        int sz;
    public:
        Vector(int s);
        ~Vector() { delete [] elem; }
        
        Vector(const Vector& a);
        Vector& operator=(const Vector& a);

        double& operator[](int i);
        const double& operator[](int i) const;

        int size() const;
    };

and given the fact this class needs a copy constructor implemented he "implements" it (pag. 74):

     Vector::Vector(const Vector& a)
         :elem{new double[sz]},
          sz{a.sz}
     {
         for (int i = 0; i != sz; ++i)
         elem[i] = a.elem[i];
     }


as you can see the elem vector is built with a size retrieved from a not yet initialized variable, being it defined at page 74 I had my last hope flipping the page and checking at page 73 if "int sz" was declared before "double* elem" but it was not the case.

I'm sad.




Monday, November 1, 2010

Temporary objects

Most believe that temporary objects are const, well they are "almost const". It is possible indeed call on a temporary object a non const member. Nifty exception stated in the standard: "Section 3.10.10 in C++ ISO/IEC 14882:1998".
This exception permits to implement a movable constructor (through a proxy) while waiting for Rvalue references in C++0x language standard.





Friday, February 12, 2010

Asserts vs Exceptions

I still see people with the doubt: "shall I use an assert or throw an exception?".
Let me whine a bit about the usage of asserts first. Overall people code badly and I mean it, hence assertions are not used enough. Having say that, "assert" and "exception" have different
meanings and behaves.

A failure assert just terminates the normal program execution (reporting source file name and line position where the error occurred), an exception thrown has a chance to be caught. Asserts disappear/vanish when NDEBUG is defined (usually in production code); this fact is a newbie oversight and what they claim about the massive usage of assert is the overhead introduced by asserts. If I wasn't clear: "Asserts disappear in production code". What didn't you get from: "Asserts disappear in production code"?

Those two facts already give an hint on when to use an assert and when an exception. If the error can be managed (by user or code itself) then an exception must be used, if the error has no chance to be managed by anyone then assert is your friend. This is not the only rule to follow indeed as said: "Asserts disappear in production code" and then in production code that error will not be "detected", errors that you expect to happen in production code can not be spotted by an assert.
Asserts are meant to detect coding error and there is no reason to happen in production code. When writing a method there are some assumption about the internal class status (pre-condition), better to check those first in order to not do something bad, at the end of the same method better check that the internal status of class is in a consistent status (post-condition).
Unfortunately, there are a great deal of people that are using exceptions for case that really ought to be assertions. Throwing exceptions instead of wrapping simple pre/post-conditions into a simple assertion macro is an hint of the fact that you're coding badly. Asserts are used to protect by coding error: using a null pointer for example; exception are to protect by normal program life: server not available, file not writable, etc.

It should be always possible to write a unit test that is able to make an exception to be thrown, if you are not able to then it means that that piece of code is a dead code; to the other side it should be impossible do the same with assert, if you are able to write an unit test that is able to make an assert fail then most likely that assert should be an exception, or of course the code is wrong.

A nice rule that drives the lazy bone programmers to use more assert is: who ever write a code that provides a set of data that asserted then the same person is responsible to fix it. This rule drives library writer to protect them self by an incorrect usage of their library at the cost to fix even the code using the library.

If you have missed it: "Asserts disappear in production code".

Thursday, September 18, 2008

Assignment operator

Today I went through a piece of code similar to this (what matters here is how the assignment operator was written):


class Test {
Test()
:theId(0), theName()
{}

Test& operator=(const Test& aRhs) {
theID = aRhs.theID;
theName = aRhs.theName;

return *this;
}

private:
int theID;
std::string theName;

};

as it is, the code works and I have nothing to say at first glance. However , who knows how the class will be extended in the future?

Imagine that in a future version some members are added:

class Test {
Test()
:theId(0), theName(), theHammer(), theHeap(0)
{}

Test& operator=(const Test& aRhs) {
theID = aRhs.theID;
theName = aRhs.theName;
theHammer = aRhs.theHammer; //This is going to be a bottleneck
theHeap = aRhs.theHeap; //This is wrong

return *this;
}

private:
int theID;
std::string theName;
HugeClass theHammer; //Extra member with huge footprint
HeapClass* theHeap; //Extra member on heap
};
as you can see with these two extra members following the same code line as the previous version the code becomes invalid. The objection I get is: "if one day someone adds those two members then they will take care to write it correctly", unfortunately in the real world it doesn't work like this. The average programmer will just add those two extra members following the code line already in place, following the rule: "after all if the code works for the already present members why shouldn't it be the same for the two extra members I have been told to add?"

The trick to avoid problems like this is to write the right code, from the start thinking of what will happen in the future, when possible of course. Usually the change to make is just a matter of a few lines of code and a two line comment in order to warn the future coders.

The original well written class would have been:

class Test {
Test()
:theId(0), theName()
{}

Test& operator=(const Test& aRhs) {

//Check for a self assignment
if (this != &aRhs) {
theID = aRhs.theID;
theName = aRhs.theName;
}

return *this;
}
private:
int theID;
std::string theName;
};

At this point the objection is: why check for a self assignment when the event is never going to happen? Who will ever write:

Test t;

t=t;
well, the code is valid so be sure someone will, also it is not always easy to spot a self assignment, consider this:

t[j] = t[i];

or even:

Test t;
Test &a = t;
...
t = a;

The real question here is: "Why was the assignment operator in that class was ever implemented?" The question makes a point, the operator was not needed at all, in that case the right thing to do is to remove it.

Let's then suppose the class is the one with the two extra members, the class is managing dynamically allocated memory then the operator must be implemented. The almost correct version is:



class Test {
Test()
:theId(0), theName(), theHammer(), theHeap(new HeapClass)
{}

Test& operator=(const Test& aRhs) {
if (this != &aRhs) {
theID = aRhs.theID;
theName = aRhs.theName;
theHammer = aRhs.theHammer;

delete theHeap;
theHeap = new HeapClass(*aRhs.theHeap);
}

return *this;
}

private:
int theID;
std::string theName;
HugeClass theHammer; //Extra member with huge footprint
HeapClass* theHeap; //Extra member on heap
};


I wrote "almost correct" because the assignment operator is correct but not exception safe, imagine what will happen if an exception is thrown, if that is the case then the class will be left in an inconsistent state. The goal is not an easy one, in order to make an assignment operator exception safe before modifying the internal state it is better to create a temporary object and then swap it with the internal state with operations that do not throw exceptions. This is achieved using the Pimpl idiom, moving all the internal state of Test inside another class and then leaving inside the class Test a pointer to this new class, it is better to use a boost::shared_ptr in this case to avoid exception catches:



class TestImpl {

friend class Test;

private:
TestImpl()
:theID(0), theName(), theHammer(), theHeap(new HeapClass)
{}

TestImpl(const TestImpl& aRhs)
:theId(aRhs.theID), theName(aRhs.theName),
theHammer(aRhs.theHammer), theHeap(new HeapClass(aRhs.theHeap))
{}

int theID;
std::string theName;
HugeClass theHammer; //Extra member with huge footprint
HeapClass* theHeap; //Extra member on heap
};

class Test {

Test()
:theImplementation(new TestImpl)
{}

Test& operator=(const Test& aRhs) {
if (this != &aRhs) {
boost::shared_ptr<TestImpl> tmp(new TestImpl(*aRhs.theImplementation));

std::swap(theImplementation, tmp);
}

return *this;
}

private:
boost::shared_ptr<TestImpl> theImplementation;
};

As you can see writing right code is not easy, and this becomes more difficult if you want to write exception safe code. What I suggest is, to remove assignment operator and copy constructor and write those only if really needed:


class Test {

Test()
:theID(0), theName(), theHammer(), theHeap(new HeapClass)
{}

private:
Test& operator=(const Test& aRhs); //disabled (do not even implement it)
Test(const Test& aRhs); //disabled (do not even implement it)


int theID;
std::string theName;
HugeClass theHammer; //Extra member with huge footprint
HeapClass* theHeap; //Extra member on heap
};

Thursday, June 19, 2008

Threading mess (2)!

I got some comments about my last post (threading-mess) about the fact that the showed solution was just detecting the scenario of two or more threads entering at the same time a critical section (in the last post example the method Shared::foo). What it doesn't answer is the real question: "is this class during its life being used by more than a single thread, or more specifically, is a certain section of code used by more than a thread"? Indeed if you remember after a SCOPED_LOCK leaves his scope, it "releases" the stored current ID thread allowing another thread to enter it.

I have added a nested Watch class to ThreadCollisionWarning class that detects also if a critical section is ever used by two different threads ( for example you can detect if a given class is constructed and destroyed within the same thread).

The code is the following:

#ifndef THREAD_COLLISION_WARNING
#define THREAD_COLLISION_WARNING

#include <stdexcept>

#ifdef NDEBUG

#define THREAD_WATCH(obj)
#define SCOPED_WATCH(obj)
#define WATCH(obj)

#else

#define THREAD_WATCH(obj) ThreadCollisionWarning _##obj;
#define SCOPED_WATCH(obj) ThreadCollisionWarning::ScopedWatch scoped_watch_##obj(_##obj);
#define WATCH(obj)        ThreadCollisionWarning::Watch watch_##obj(_##obj);

#endif

class ThreadCollisionWarning {
public:
    ThreadCollisionWarning()
    :theActiveThread(0)
    { }

    ~ThreadCollisionWarning() { }

    class Watch {
        public:
            Watch(ThreadCollisionWarning& aTCW)
            :theWarner(aTCW)
            { theWarner.enter_self(); }

            ~Watch() { }

        private:
            ThreadCollisionWarning& theWarner;
    };

    class ScopedWatch {
        public:
            ScopedWatch(ThreadCollisionWarning& aTCW)
            :theWarner(aTCW)
            { theWarner.enter(); }

            ~ScopedWatch() { theWarner.leave(); }

        private:
            ThreadCollisionWarning& theWarner;
    };

private:

    void enter_self() { 
        //If the active thread is 0 then I'll write the current thread ID
        //if two or more threads arrive here only one will success to write on theActiveThread 
        //the current thread ID
        if (! __sync_bool_compare_and_swap(&theActiveThread, 0, pthread_self())) { 

            //Last chance! may be is the thread itself calling from a critical section
            //another critical section
            if (!__sync_bool_compare_and_swap(&theActiveThread, pthread_self(), theActiveThread)) {
                throw std::runtime_error("Thread Collision");
            }
        }
    }

    void enter() { 
        if (!__sync_bool_compare_and_swap(&theActiveThread, 0, pthread_self())) {
            //gotcha! another thread is trying to use the same class
            throw std::runtime_error("Thread Collision");
        }
    }

    void leave() { 
        __sync_fetch_and_xor(&theActiveThread, theActiveThread);
    }

    pthread_t theActiveThread;
};

#endif


The nested Watch class (used by WATCH macro) just during his constructor initializes theActiveThread member with the current id thread if it isn't still initialized, in case it gives another chance to check if the active thread is itself.

So let's see some examples of use:

Case #1: Check that one thread ever uses some critical section (recursion allowed)

struct Shared {
   void foo() { 
       WATCH(CriticaSectionA);
       bar();
   }

   void bar() {
       WATCH(CriticaSectionA);
   }

   THREAD_WATCH(CriticaSectionA);
};


Case #2: Check that a class is constructed and destroyed inside the same thread

struct Shared {

    Shared() {
        WATCH(CTOR_DTOR_SECTION);
        ...
    }

   ~Shared() { 
       WATCH(CTOR_DTOR_SECTION);
       ...
   }

   THREAD_WATCH(CTOR_DTOR_SECTION);
};

note that doing so the Shared destructor can throw an exception, so do not use this in a production code (put the WATCH between a try-catch and just notify it in some way).

Case #3: Two or more different threads can enter a critical section but in exclusive way (useful to check if external sync mechanism are working).

struct Shared {

    foo() {
        SCOPED_WATCH(CriticalSectionA);
    }


   THREAD_WATCH(CriticalSectionA);
};