Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #342 > unrolled thread

Mutex or reader writer lock

Back to article view | Back to comp.programming.threads

Contents

  Mutex or reader writer lock ittium <ittium@gmail.com> - 2011-06-21 03:27 -0700
    Re: Mutex or reader writer lock David Schwartz <davids@webmaster.com> - 2011-06-21 22:03 -0700
    Re: Mutex or reader writer lock Edek <edek.pienkowski@gmail.com> - 2011-06-23 00:14 +0200
      Re: Mutex or reader writer lock ittium <ittium@gmail.com> - 2011-06-23 06:04 -0700
      Re: Mutex or reader writer lock "Chris M. Thomasson" <cristom@charter.net> - 2011-06-23 11:43 -0700
        Re: Mutex or reader writer lock ittium <ittium@gmail.com> - 2011-06-24 02:26 -0700
          Re: Mutex or reader writer lock Edek <edek.pienkowski@gmail.com> - 2011-06-24 12:02 +0200
            Re: Mutex or reader writer lock "Chris M. Thomasson" <cristom@charter.net> - 2011-06-29 13:46 -0700
              Re: Mutex or reader writer lock "Chris M. Thomasson" <cristom@charter.net> - 2011-06-29 14:26 -0700
                Re: Mutex or reader writer lock "Chris M. Thomasson" <cristom@charter.net> - 2011-06-29 20:30 -0700

#342 — Mutex or reader writer lock

Hi group,
I plan to use pthread read write lock for one of my products. I did
some research and found out that reader writer lock consume more CPU
than mutex. Folloiwng is my understanding, please comment on these
points

1. There are mostly read operations on the shared data and there are
**large** number of readers so even if there is cpu penalty of using
reader writer lock, multiple threads can simultaneously work with
rwlock.

2. If  there are mostly read operations but there are **not many
readers** than contention will be small and it is better to use mutex
since mutex locking/unlocking is light weight

3.If read operations are **heavy weight**, **irrespective of number of
readers**, It is always a good idea to use reader writer locks in
place of mutex since so even if there is cpu penalty of using reader
writer lock, multiple threads can simultaneously work

I will also appreciate, few lines on pthread reader writer locks
implementation. Is is using futex and condition variables ?

thanks
Ittium

[toc] | [next] | [standalone]

#349

On Jun 21, 3:27 am, ittium <itt...@gmail.com> wrote:
> Hi group,
> I plan to use pthread read write lock for one of my products. I did
> some research and found out that reader writer lock consume more CPU
> than mutex. Folloiwng is my understanding, please comment on these
> points

Correct. Reader/writer locks trade off a bit of extra CPU consumption
for greater concurrency.

> 1. There are mostly read operations on the shared data and there are
> **large** number of readers so even if there is cpu penalty of using
> reader writer lock, multiple threads can simultaneously work with
> rwlock.

Right.

> 2. If  there are mostly read operations but there are **not many
> readers** than contention will be small and it is better to use mutex
> since mutex locking/unlocking is light weight

Right.

> 3.If read operations are **heavy weight**, **irrespective of number of
> readers**, It is always a good idea to use reader writer locks in
> place of mutex since so even if there is cpu penalty of using reader
> writer lock, multiple threads can simultaneously work

Right.

> I will also appreciate, few lines on pthread reader writer locks
> implementation. Is is using futex and condition variables ?

Depends on the platform. It is likely using whatever is fastest on
that platform.

DS

[toc] | [prev] | [next] | [standalone]

#355

On 06/21/2011 12:27 PM, ittium wrote:
> Hi group,
> I plan to use pthread read write lock for one of my products. I did
> some research and found out that reader writer lock consume more CPU
> than mutex. Folloiwng is my understanding, please comment on these
> points

>
> 1. There are mostly read operations on the shared data and there are
> **large** number of readers so even if there is cpu penalty of using
> reader writer lock, multiple threads can simultaneously work with
> rwlock

That's the basic idea of an rwlock. I assume this post is not related
to your nearby posts, where readers just fetch something under lock
and work on it later outside.

.
>
> 2. If  there are mostly read operations but there are **not many
> readers** than contention will be small and it is better to use mutex
> since mutex locking/unlocking is light weight

"Not many readers" is not enough information. a) comment above,
b) contention depends not only on count, but also on time of operations
and frequency, sometimes even patterns

>
> 3.If read operations are **heavy weight**, **irrespective of number of
> readers**, It is always a good idea to use reader writer locks in
> place of mutex since so even if there is cpu penalty of using reader
> writer lock, multiple threads can simultaneously work
>

See above. In general the topic of lock granularity comes to (my) mind,
a way to lower the contention. I mean, if there is a really
"heavy weight" operation holding a lock all the time, something has to
wait. Even under RWLock, you can imagine one reader thread blocking
everything else for however long it runs.

And,
> **irrespective of number of
>> readers**

if there is one, there is no need for an rwlock, FWIW.


> I will also appreciate, few lines on pthread reader writer locks
> implementation. Is is using futex and condition variables ?
>

I don't know what platform you are referring to, but atomic + futex
as far as I know (plus bookkeeping of course)


> thanks
> Ittium

Edek

[toc] | [prev] | [next] | [standalone]

#357

Thanks group for the response.
I am targeting pthread library linux platform so was interested in
some very high level detail of RWlock implementation.

[toc] | [prev] | [next] | [standalone]

#360

"Edek" <edek.pienkowski@gmail.com> wrote in message 
news:ittper$joe$1@node2.news.atman.pl...
> On 06/21/2011 12:27 PM, ittium wrote:
[...]
>> I will also appreciate, few lines on pthread reader writer locks
>> implementation. Is is using futex and condition variables ?
>>
>
> I don't know what platform you are referring to, but atomic + futex
> as far as I know (plus bookkeeping of course)

Last time I checked (a couple of years ago), most POSIX rw-locks impls I 
have seen used mutexs and condition variables. They had rather horrible 
performance characteristics... 

[toc] | [prev] | [next] | [standalone]

#362

>
> Last time I checked (a couple of years ago), most POSIX rw-locks impls I
> have seen used mutexs and condition variables. They had rather horrible
> performance characteristics...

Chris, I also did some more searching and it seems the rwlock
implementation is still based on mutex and condition variable and is
quite slow. For low contention case atleast on linux mutex (based on
futex) can be very fast.  Criteria for choosing rwlock or mutex was
the intention of my post.

[toc] | [prev] | [next] | [standalone]

#363

On 06/24/2011 11:26 AM, ittium wrote:
>
>>
>> Last time I checked (a couple of years ago), most POSIX rw-locks impls I
>> have seen used mutexs and condition variables. They had rather horrible
>> performance characteristics...
>
> Chris, I also did some more searching and it seems the rwlock
> implementation is still based on mutex and condition variable and is
> quite slow. For low contention case atleast on linux mutex (based on
> futex) can be very fast.  Criteria for choosing rwlock or mutex was
> the intention of my post.
>

Interesting - what kind of mutex can a rwlock use, if mutex is based on
futex? Non-futex mutex? What for?

On my 2.6.3x, in no collision case there is not even a futex call; on
collisions, futex calls (according to strace).

Before futexes there was no other option.

Edek

[toc] | [prev] | [next] | [standalone]

#368

"Edek" <edek.pienkowski@gmail.com> wrote in message 
news:iu1nar$dbi$1@node2.news.atman.pl...
> On 06/24/2011 11:26 AM, ittium wrote:
>>
>>>
>>> Last time I checked (a couple of years ago), most POSIX rw-locks impls I
>>> have seen used mutexs and condition variables. They had rather horrible
>>> performance characteristics...
>>
>> Chris, I also did some more searching and it seems the rwlock
>> implementation is still based on mutex and condition variable and is
>> quite slow. For low contention case atleast on linux mutex (based on
>> futex) can be very fast.  Criteria for choosing rwlock or mutex was
>> the intention of my post.
>>
>
> Interesting - what kind of mutex can a rwlock use, if mutex is based on
> futex? Non-futex mutex? What for?

A rw-mutex implementation does not need to use any mutex/futex operations on 
the fast-paths.




> On my 2.6.3x, in no collision case there is not even a futex call; on
> collisions, futex calls (according to strace).

The last Linux rw-mutex impl I looked at actually locked a damn mutex on the 
fast-path; something like this:
__________________________________________________
int
pthread_rwlock_rdlock(
    pthread_rwlock_t *self
)  {

    LOCK(&self->mutex);

    /* make sure we are alone! */

    UNLOCK(&self->mutex);

    return ...;
}
__________________________________________________

IMVHO, this is horrible!




> Before futexes there was no other option.

FWIW, you can examine my one of my rw-mutex implementations:

http://software.intel.com/en-us/forums/showthread.php?t=65822
(read all!)


Last time I checked it beat the heck out of several existing implementations 
(ect, Solaris & Linux). BTW, here is a version that should compile on most 
32-bit x86 systems with MSVC or GCC:

http://pastebin.com/f3d6140eb


BTW, if your system supports `sem_post_multiple()' be sure to define 
`SEM_USE_POST_MULTIPLE' for possibly better slow-path performance... lol


enjoy!   :^) 

[toc] | [prev] | [next] | [standalone]

#369

"Chris M. Thomasson" <cristom@charter.net> wrote in message 
news:raMOp.4353$_b7.1088@newsfe22.iad...
[...]

> Last time I checked it beat the heck out of several existing 
> implementations (ect, Solaris & Linux). BTW, here is a version that should 
> compile on most 32-bit x86 systems with MSVC or GCC:
>
> http://pastebin.com/f3d6140eb

I forgot to mention that your system needs to support PThreads and 
semaphores (e,g, `sem_init()') in order for this to compile!


Also, here is a thread that shows some "performance" results when compared 
to native `pthread_rdlock' implementations:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/61676475dbb8762b


this message in particular:

http://groups.google.com/group/comp.programming.threads/msg/3e7531657a11baf0

[toc] | [prev] | [next] | [standalone]

#371

"Chris M. Thomasson" <cristom@charter.net> wrote in message 
news:mMMOp.19636$Md1.2069@newsfe19.iad...
> "Chris M. Thomasson" <cristom@charter.net> wrote in message 
> news:raMOp.4353$_b7.1088@newsfe22.iad...
> [...]
>
>> Last time I checked it beat the heck out of several existing 
>> implementations (ect, Solaris & Linux). BTW, here is a version that 
>> should compile on most 32-bit x86 systems with MSVC or GCC:
>>
>> http://pastebin.com/f3d6140eb
>
> I forgot to mention that your system needs to support PThreads and 
> semaphores (e,g, `sem_init()') in order for this to compile!
>
>
> Also, here is a thread that shows some "performance" results when compared 
> to native `pthread_rdlock' implementations:
>
> http://groups.google.com/group/comp.programming.threads/browse_frm/thread/61676475dbb8762b

[...]

Check this one out:

http://www.opensource.apple.com/source/Libc/Libc-594.9.5/pthreads/pthread_rwlock.c

It uses an algorithm that contains explicit loops along with 64-bit CAS 
logic... AFAICT, a rw-lock does not need to use any explicit loops or CAS at 
all! Fetch-and-Add is sufficient. Since it contains a loop, the fast-paths 
cannot be wait-free by definition.

;^/ 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web