Chambers <ben### [at] pacificwebguycom> wrote:
> > -----Original Message-----
> > From: clipka [mailto:nomail@nomail]
> > (BTW, why is Boost used if it is so slow?)

> Boost isn't slow.  Mutexing is slow (relatively).

  Boost mutexes are actually the slowest I have tried, although not by a
very large margin.

  Using Pthreads mutexes directly is (at least in my system) slightly
faster, and using OpenMP mutexes still slightly faster.

  The reason why Boost is used is that it's portable to most systems.
Pthreads can only be used in posix systems which implement it (if I'm
not mistaken, most Windows compilers don't). OpenMP is a rather new
standard and few compilers support it.

  As a curiosity, I tested the actual slowdown caused by Boost mutexes.
Consider this function:

void incrementCounter()
{
    boost::mutex::scoped_lock lock(mutex);
    ++someCounter;
}

  I tested calling this function (from a different compilation unit, so
that the compiler cannot inline it, in order to better give a true notion
of its speed) 500000000 times in a loop (compiler options -O3 -march=native)
and in my system it takes 47 seconds. If I comment out the locking, it
takes 1.8 seconds.

  Mutexing is a rather hard problem. Not only is it enough to lock access
from more than one thread at the same time, you also have to prioritize
the accesses. In other words, assume you have this situation using a
naive mutex:

- Thread 1 accesses the mutexed resource and gets the lock to itself.
- Now thread 2 gets scheduled and tries to access the same resource, but
  the mutex blocks it, so for now it has to wait.
- Thread 1 gets done and frees the lock. However, it needs the resource
  immediately again, and locks it again.
- Thread 2 gets scheduled and tries again to access the resource, but
  it's locked, so it can't get it.
- Repeat.

  Thread 2 may be locked out of the resource by thread 1 if the former
never gets scheduled when the lock would be free.

  For this reason the mutex must prioritize: When thread 1 tries to
immediately lock the resource again, after freeing it, the mutex should
not give it, but instead it should prioritize thread 2, who requested it
earlier.

  If a naive mutex would be enough, then this would be by far the most
efficient way of locking I know of:

void incrementCounter()
{
    static int lockFlag = 0;
    while(!__sync_bool_compare_and_swap(&lockFlag, 0, 1)) sched_yield();

    ++someCounter;

    lockFlag = 0;
}

  This runs in 15 seconds in my system. OTOH it requires the gcc extension
__sync_bool_compare_and_swap as well as the posix <sched.h> library. So
it's not really a viable option for portable code.

  (And of course it has the problem that it doesn't prioritize requests.)

-- 
                                                          - Warp

Post a reply to this message