CRITICAL SECTION

[sergey....@gmail.com]

Hi Guys,
I have std::map of ~ 20000 items that shared between multiple threads
(8-16). This collection protected by single CRITICAL_SECTION. While
one thread processing items all other threads are waiting :(. Items
are too big to be copied out of CRITICAL_SECTION.
Idea is to introduce CRITICAL_SECTION for each item, so threads would
wait only while picking items from map and in case of collisions over
the same item.
But CRITICAL_SECTIONs are organized in link list and introduction of
20000 critical sections may be kill any expected gains from de-
serialization.
Even if Cristical section is user mode object how expensive is it?
Another way would be introduction of home grown synchronization
instead of critical section. Each item gets Boolean flag - (Is it
taken or not) and shared semaphore to wait until item is available
(just like Critical section does).

Thank you.

[Johannes Passing]

Hi Sergey,

critical sections are user-mode-only only as long as they are
uncontended. As soon as the first thread has to wait on it (and the spin
count has exceeded if spinning is used), a wait on an event is
performed. Since Windows 2000, this event is created lazily. So if your
application runs for long enough, the event count will slowly converge
to 20000, which is probably to much.

If you can segregate the map accesses into read and write accesses and
concurrent read accesses are allowed, replacing the critical section by
a single writer/multiple reader lock may be a viable approach.

If this is not an option, another approach to save resources and limit
the maximum number of events may be to use one CS per bucket of objects
rather than one CS per object, i.e. you allocate a number of CS (e.g.
100) and share each CS among a number (e.g. 200) of objects. You could
use a hashing scheme based on the object's key to choose the appropriate
CS. If map entries are added and removed, you also may need additional
locking to avoid concurrent map modifications as you do not have the
central CS any more.

--Johannes

--
Johannes Passing - http://int3.de/

[sergey....@gmail.com]

On Aug 28, 2:31 pm, Johannes Passing

> Johannes Passing -http://int3.de/- Hide quoted text -
>
> - Show quoted text -

Thank you.

[Matt]

You could create a spinlock per record as well.

http://blogs.msdn.com/slavao/archive/2005/11/12/492119.aspx

The overhead would be 4 bytes per record.

<sergey....@gmail.com> wrote in message
news:1188330876.8...@d55g2000hsg.googlegroups.com...

[Chris Thomasson]

<sergey....@gmail.com> wrote in message
news:1188318272.5...@19g2000hsx.googlegroups.com...
> Hi Guys,
[...]

Use something like the following:

http://groups.google.com/group/comp.programming.threads/browse_thread/thread/e0c011baf08844c4

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

BTW, if you want to have a conversation with _multi-threading experts_ go
ahead and post over on comp.programming.threads.

[Chris Thomasson]

"Chris Thomasson" <cri...@comcast.net> wrote in message
[...]

BTW, Elcaro is most likely a Troll who makes frequent use of No-Archive-X:

http://groups.google.com/group/comp.arch/browse_thread/thread/eb65de8aa4649832

http://groups.google.com/group/comp.arch/msg/5e94d5f02b35dcfa

Take his worth with a grain of salt. BTW, the USENET group for all things
multi-threading is:
comp.programming.threads. Yes, we take questions wrt threading issues on
windows Solaris Linux and any other operating system you can find.

[Chris Thomasson]

"Elcaro Nosille" <Elcaro....@mailinator.com> wrote in message
news:46d49ed4$0$16103$9b4e...@newsspool1.arcor-online.net...
> Generate a hash from each object (f.e. the address where
> it is stored) and use it as an index to a critical section
> in an array. Use a larger number of critical sectiosn than
> there are threads to limit the number of collisions to a
> point where the performance isn't degraded significantly.

I should point out to the OP that you have got to be careful when your using
lock hashing schemes... You can deadlock if a thread tries to lock two
hashed objects at the same time. This is because hash collisions could muck
up the locking order.

Like this:

pthread_mutex_t locks[16];

objA maps to lock[1];
objB maps to lock[2];
objC maps to lock[1];

Thread A
---------------------
A1: lock objA
A2: lock objB

Thread B
---------------------
B1: lock objB
B2: lock objC

Execution
-------------------
E1: A1
E2: B1
E3: A2 -- deadlock!

Just thought I should point that out to the OP.