Re: task-safe hash table?

[Stephen Leake <stephen_leake@acm.org>]

tmoran@acm.org writes:

>> > 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.  

What "overhead"?

The whole point of the ceiling priority protocol on protected objects
is that they are cheap to access.

I'm not entirely sure what that means in a multi-processor setting,
but it should be at least as fast as any other mechanism.

> 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. 

That sounds perfect for a protected object, with a function for
read/lookup, and a procedure or entry for write/add.

> So this is a very specific test to see what Ada tasking, on a modern
> chip, buys you on this particular app. (I already know it's a win on
> the word count and on a sort.) I'm just hearing too many people say
> "multi-core is dumb because nobody knows how to do concurrent
> programming".

Yes, it would be good to show that Ada helps on this type of problem.

-- 
-- Stephe