concerning a synchronous dictionary

[not_a_commie]

Suppose I want to write a synchronized dictionary class with just two
methods:

bool Add(key, value)
bool Remove(key,value)

The Add returns true if the key-value pair already exist or it was
successfully added. It returns false if a key with a different value
was existing. The Remove returns true if the key was nonexistant or
the key-value pair was successfully removed, and it returns false if
the key was existing with a different value.

I can write this fairly trivially by wrapping a dictionary class and
using a lock/monitor mechanism internally in both methods. However,
what I really want is to be able to do the above methods in a
synchronized fashion without using the lock keyword. Is such a thing
possible? Has anyone seen any synchronized dictionaries that don't
lock? i.e., They use the Interlocked class or some other
synchronization mechanism. Every thread in my program hits the above
methods and I don't want to bottleneck there on a lock.

 

[Pavel Minaev]

Suppose I want to write a synchronized dictionary class with just two
methods:

bool Add(key, value)
bool Remove(key,value)

The Add returns true if the key-value pair already exist or it was
successfully added. It returns false if a key with a different value
was existing. The Remove returns true if the key was nonexistant or
the key-value pair was successfully removed, and it returns false if
the key was existing with a different value.

It's suspicious to have only two methods, since you supposedly add
those key-value pairs to a dictionary so that you can use them somehow
(and not just remove them) - so there should also be a third method
somewhere, which, directly or indirectly, retrieves the value at a
given key, right? In that case, you should look closer at whether you
might get any race conditions not within individual Add/Remove/Get,
but in code that uses more than one of those in a sequence.

I can write this fairly trivially by wrapping a dictionary class and
using a lock/monitor mechanism internally in both methods. However,
what I really want is to be able to do the above methods in a
synchronized fashion without using the lock keyword. Is such a thing
possible? Has anyone seen any synchronized dictionaries that don't
lock? i.e., They use the Interlocked class or some other
synchronization mechanism. Every thread in my program hits the above
methods and I don't want to bottleneck there on a lock.

I'm not aware of any implementation techniques for mutable dictionary/
map data structures that can avoid locking, similar to what is
possible for singly-linked lists. You'll have to use some
synchronization mechanism, and Monitor ("lock") is quite lightweight.

 

[not_a_commie]

The Monitor class in .Net does something similar to what I want to do.
It (apparently) locates a key-value pair for an object and threadId.
If the current threadId matches or there was no key already in its
dictionary, it doesn't block, otherwise it does block. The code for
Monitor is all CLR calls according to Reflector. Anybody know how they
do it there? I'm certain they don't block all threads while any one
thread is in the Monitor.Enter method.

 

[Pavel Minaev]

The Monitor class in .Net does something similar to what I want to do.
It (apparently) locates a key-value pair for an object and threadId.
If the current threadId matches or there was no key already in its
dictionary, it doesn't block, otherwise it does block.

I would think they only need one synchronization primitive per object,
not per object/thread pair - since OS synchronization primitives
already implement the "don't block if already blocked from this
thread" semantics. I would imagine they use a critical section there
internally, since it matches the described limitations of Monitor.