From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00,
	REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: 103376,4cf1fd41f64f8f02
X-Google-Attributes: gid103376,public
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news2.google.com!news4.google.com!news3.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!newsfeed00.sul.t-online.de!t-online.de!tiscali!newsfeed1.ip.tiscali.net!proxad.net!proxad.net!newsfeed.arcor.de!news.arcor.de!not-for-mail
From: "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
Subject: Re: task-safe hash table?
Newsgroups: comp.lang.ada
User-Agent: 40tude_Dialog/2.0.15.1
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Reply-To: mailbox@dmitry-kazakov.de
Organization: cbb software GmbH
References: <m2psht4c8e.fsf@grendel.local>
 <NZqdnY-dor_w3eLZnZ2dnUVZ_s-dnZ2d@comcast.com>
Date: Thu, 1 Jun 2006 22:07:41 +0200
Message-ID: <edjojeeb1lwl$.gqavpe4tqkfp.dlg@40tude.net>
NNTP-Posting-Date: 01 Jun 2006 22:07:28 MEST
NNTP-Posting-Host: 53870816.newsread2.arcor-online.net
X-Trace: 
 DXC=9`>O2:e91=<j12nnM8XB1>Q5U85hF6f;4jW\KbG]kaM8[NGU2GAcMG:I;0c7@T6oe:WRXZ37ga[7:jTA67ckJ=X5kMWQbmb\jM<
X-Complaints-To: usenet-abuse@arcor.de
Xref: g2news2.google.com comp.lang.ada:4640
Date: 2006-06-01T22:07:28+02:00
List-Id: <comp.lang.ada>

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