Re: task-safe hash table?

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Thu, 01 Jun 2006 14:30:53 -0500, tmoran@acm.org wrote:

>>> I think you might be able to get part way by consulting the original
>>> Booch components.
>>
>> The 95 BCs were going to have Synchronized and Guarded extensions, but
>    The app I had in mind was the k-nucleotide shootout benchmark, which
> uses a hash table, running on a multi-core cpu.  If lookups are read-only,
> and are much more frequent than writes, one should be able to do them
> concurrently.  Since a lookup in a hash table is, presumably, pretty fast,
> the overhead of making it Protected would probably kill the gain.

Functions on protected objects could potentially run in parallel on a
multi-core CPU. Does anybody know if GNAT does this?

> But one
> ought to be able to arrange things so a concurrent lookup that comes back
> with a hit is correct, ie most of the time, while one that comes back "we
> need to add this" would be rare enough that interlocking for a second
> check and possible add wouldn't cancel the wall clock savings.

What about a window in which each task makes, say, n searches. n is the
window size. All misses are postponed till the window end. At that point
the tasks synchronize on a protected object (the entry count = number of
tasks) and here all insertions are made (some of them could be duplicates).
Then the next windows starts.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de