task-safe hash table?

task-safe hash table?

[tmoran]

Is there some code around for a hash table that allows multiple tasks
to do simultaneous lookup?

Re: task-safe hash table?

[John]

tmoran@acm.org wrote:
> Is there some code around for a hash table that allows multiple tasks
> to do simultaneous lookup?

I think you might be able to get part way by consulting the original
Booch components.

Grady Booch's book "Software Components in Ada" takes pains to describe
tasking semantics, defining terms "concurrent," "guarded", "multiple"
etc.
(My book is a kilomile from me these days, so details are elsewhere.)

What's more, the components don't declare a hash table - at least not
directly and obviously.  But maybe there's something useful there.
Part way at best.

John Woodruff
retired software engineer

Re: task-safe hash table?

[tmoran]

>Grady Booch's book "Software Components in Ada" takes pains to describe
>tasking semantics, defining terms "concurrent," "guarded", "multiple"
   Maybe I missed something, but it appears Booch's book leaves
Maps_Simple_Noncached_Concurrent_* as an exercise for the reader.

Re: task-safe hash table?

[John]

tmoran@acm.org wrote:
> >Grady Booch's book "Software Components in Ada" takes pains to describe
> >tasking semantics, defining terms "concurrent," "guarded", "multiple"
>    Maybe I missed something, but it appears Booch's book leaves
> Maps_Simple_Noncached_Concurrent_* as an exercise for the reader.

While I don't have my book at hand, I do have the components themselves

installed in my travel kit.  I (still) won't claim the solution to your
problem lies
here, I do find (along with lots of others ...)

maps $ ls map_simple_noncached_concurrent*.ads
map_simple_noncached_concurrent_bounded_managed_iterator.ads
map_simple_noncached_concurrent_bounded_managed_noniterator.ads
map_simple_noncached_concurrent_unbounded_managed_iterator.ads
map_simple_noncached_concurrent_unbounded_managed_noniterator.ads
map_simple_noncached_concurrent_unbounded_unmanaged_iterator.ads
map_simple_noncached_concurrent_unbounded_unmanaged_noniterator.ads

hth
John W

Re: task-safe hash table?

[tmoran]

> > >Grady Booch's book "Software Components in Ada" takes pains to describe
> While I don't have my book at hand, I do have the components themselves
  Was there a diskette with that book that I lost, or are they on the
web or someplace handy?

Re: task-safe hash table?

[Georg Bauhaus]

On Mon, 2006-05-29 at 23:35 -0500, tmoran@acm.org wrote:
> > > >Grady Booch's book "Software Components in Ada" takes pains to describe
> > While I don't have my book at hand, I do have the components themselves
>   Was there a diskette with that book that I lost, or are they on the
> web or someplace handy?

You will find the original Booch components (Ada 83) on
www.adapower.com.

Re: task-safe hash table?

[Simon Wright]

"John" <jpwoodruff@irisinternet.net> writes:

> tmoran@acm.org wrote:
>> Is there some code around for a hash table that allows multiple tasks
>> to do simultaneous lookup?
>
> 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
(a) the design meant that this was going to be a _lot_ of work, (b)
the form that just did a global lock on the container was easy enough
to do, but the other, which was meant to implement finer granularity,
turned out to be far too application-specific; so I ended up not doing
either. The killer was iteration.

It seems better to use the BCs (or Ada.Containers come to that) as an
implementation mechanism for whatever storage your application needs
behind appropriate concurrency mechanisms.

Re: task-safe hash table?

[tmoran]

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

Re: task-safe hash table?

[Ludovic Brenta]

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

If you implement the lookup as a function in the protected object,
then lookups can be concurrent.  I think you should benchmark the
actual performance before you decide that it's too slow.

-- 
Ludovic Brenta.

Re: task-safe hash table?

[Dmitry A. Kazakov]

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

Re: task-safe hash table?

[Jeffrey R. Carter]

Dmitry A. Kazakov wrote:
> 
> Functions on protected objects could potentially run in parallel on a
> multi-core CPU. Does anybody know if GNAT does this?

Potentially. It depends on the compiler. Last time I checked, GNAT 
obtained a mutex for every operation on a protected object, including 
functions.

-- 
Jeff Carter
"Spam! Spam! Spam! Spam! Spam! Spam! Spam! Spam!"
Monty Python's Flying Circus
53

Re: task-safe hash table?

[Stephen Leake]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> Functions on protected objects could potentially run in parallel on a
> multi-core CPU. 

Only if they are called from different tasks.


-- 
-- Stephe

Re: task-safe hash table?

[tmoran]

>Functions on protected objects could potentially run in parallel on a
>multi-core CPU. Does anybody know if GNAT does this?
>...
>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
  I tried a simple approach:  Lookup is asynchronous, Insert is Protected.
I ran the test data using Gnat 3.15p on a dual-core Pentium and looking at
the Task Manager CPU usage.  With a small number of large buckets in the
hash - so a lookup scans a rather long list and takes a long time - CPU
usage is around 75% (of the total two CPUs).  So there's overlap.  With a
more reasonable hash with a large number of small buckets, the Protected
overhead is larger relative to the "useful work", and CPU usage goes down
to more like 40% (I presume the missing 10% is probably tallied as System
time in task switching instead of app time).  Since by far the best speed
comes from a large number of small buckets, this approach to doing the job
concurrently is a losing proposition.
  Perhaps a windowing or batching approach such as you suggest would
distribute the Protected overhead over more useful work and make the
concurrent approach faster.  I'll look into that this weekend.

Re: task-safe hash table?

[tmoran]

> >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
> ...
>   Perhaps a windowing or batching approach such as you suggest would
> distribute the Protected overhead over more useful work and make the
> concurrent approach faster.  I'll look into that this weekend.
   Dual tasking takes 2/3 as long as sequential.
   The k-nucleotide strings start half the time with 'A' or 'C' and half
the time with 'G' or 'T'.  So I tried using one hash table for the former
and one for the latter.  Then there is no synchronization needed (till
printing the results).  Running with the main program handling A+C and a
second task concurrently handling G+T drives CPU usage up to 96% and takes
2/3 the wall clock time, as compared to doing A+C followed sequentially by
G+T (which only takes CPU usage up to 50%, or all of one core on this
dual-core Pentium).
  So Ada multitasking on a multi-core CPU gives substantial improvements
for another of the shootout benchmarks (which I believe, unfortunately,
are officially measured on obsolete single-core CPUs).

Re: task-safe hash table?

[Stephen Leake]

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

Re: task-safe hash table?

[tmoran]

> > the overhead of making it Protected would probably kill the gain.
>
> What "overhead"?
   In a trivial single-tasking test program on my machine, a call to a
Protected function compiled with Gnat 3.15p -O2 takes
  0.304697000 mics while a call to a regular function takes
  0.022779000 microseconds.
Using -O3, it's
0.291347000 mics while a call to a regular function takes
0.001893000 microseconds.

Re: task-safe hash table?

[M E Leypold]

tmoran@acm.org writes:

> > > the overhead of making it Protected would probably kill the gain.
> >
> > What "overhead"?
>    In a trivial single-tasking test program on my machine, a call to a
> Protected function compiled with Gnat 3.15p -O2 takes
>   0.304697000 mics while a call to a regular function takes
>   0.022779000 microseconds.
> Using -O3, it's
> 0.291347000 mics while a call to a regular function takes
> 0.001893000 microseconds.

Which OS is that? I've just stumbled upon the commentary in the 3.15p
install instructions, that at linux, 3.15p uses FSU-threads and at
(i.e) Solaris it would use native threads. Would that perhaps make a
difference (I wonder wether any 'rescheduling' of threads is taking
place -- perhaps only implicitly -- in the lower level abstraction
layer when GNAT is handling the entry into the protected object?)

I'm admittedly only wildly speculating, but I'd like to anchor you
empirical data to some solid coordinates like "at system X gnat 3.15p
takes 15 times longer to enter a protected function than a "normal"
function". If then a second data point comes along we/I'll have
something to think about :-).

Regards -- Markus

Re: task-safe hash table?

[tmoran]

>Which OS is that? I've just stumbled upon the commentary in the 3.15p
>...
>empirical data to some solid coordinates like "at system X gnat 3.15p
  Windows 2000 on a 3GHz multicore Pentium.  The function had a trivial
body, so almost all the time is calling it, and -O3 really cut that down
over -O2 for the call (but not for the Protected function call).

Re: task-safe hash table?

[Stephen Leake]

tmoran@acm.org writes:

>> > the overhead of making it Protected would probably kill the gain.
>>
>> What "overhead"?
>    In a trivial single-tasking test program on my machine, a call to a
> Protected function compiled with Gnat 3.15p -O2 takes
>   0.304697000 mics while a call to a regular function takes
>   0.022779000 microseconds.

Interesting. Please post the program; I'll run it with a later GNAT,
and if the results are still so bad, submit a bug report.

> Using -O3, it's 0.291347000 mics while a call to a regular function
> takes 0.001893000 microseconds.

-O3 does inlining, so the function call overhead probably disappeared.
But I'd have to see the Ada and assembly code to be sure.

-- 
-- Stephe

Re: task-safe hash table?

[tmoran]

with ada.calendar,
     ada.text_io;
procedure timeprot is

  protected type p_type is
    entry a(x: in integer);
    procedure b(x : in integer);
    function c(x : in integer) return integer;
  private
    p_dummy : integer := 0;
  end p_type;

  protected body p_type is
    entry a(x: in integer) when p_dummy = 0 is
    begin p_dummy := x;end a;
    procedure b(x : in integer) is
    begin p_dummy := x;end b;
    function c(x : in integer) return integer is
    begin return p_dummy+x;end c;
  end p_type;

  dummy : integer := 0;

  procedure a(x : in integer) is
  begin dummy := x;end a;
  procedure b(x : in integer) is
  begin dummy := x;end b;
  function c(x : in integer) return integer is
  begin return dummy+x;end c;

  procedure measure is
    use type ada.calendar.time;
    t0,t1 : ada.calendar.time;
    junk : integer;
  begin
    t0 := ada.calendar.clock;
    for i in 1 .. 1_000 loop
      a(i/3_000);  -- ensure that parameter to call = 0
    end loop;
    t1 := ada.calendar.clock;
    ada.text_io.put_line("a" & duration'image((t1-t0)*1000) & " mics");
    t0 := ada.calendar.clock;
    for i in 1 .. 1_000 loop
      b(i/3_000);
    end loop;
    t1 := ada.calendar.clock;
    ada.text_io.put_line("b" & duration'image((t1-t0)*1000) & " mics");
    t0 := ada.calendar.clock;
    for i in 1 .. 1_000 loop
      junk:=c(i/3_000);
    end loop;
    t1 := ada.calendar.clock;
    ada.text_io.put_line("c" & duration'image((t1-t0)*1000) & " mics");
  end measure;

  prot : p_type;

  procedure measure_p is
    use type ada.calendar.time;
    t0,t1 : ada.calendar.time;
    junk : integer;
  begin
    t0 := ada.calendar.clock;
    for i in 1 .. 1_000 loop
      prot.a(i/3_000);
    end loop;
    t1 := ada.calendar.clock;
    ada.text_io.put_line("prot.a" & duration'image((t1-t0)*1000) & " mics");
    t0 := ada.calendar.clock;
    for i in 1 .. 1_000 loop
      prot.b(i/3_000);
    end loop;
    t1 := ada.calendar.clock;
    ada.text_io.put_line("prot.b" & duration'image((t1-t0)*1000) & " mics");
    t0 := ada.calendar.clock;
    for i in 1 .. 1_000 loop
      junk:=prot.c(i/3_000);
    end loop;
    t1 := ada.calendar.clock;
    ada.text_io.put_line("prot.c" & duration'image((t1-t0)*1000) & " mics");
  end measure_p;

begin
  measure;
  measure_p;
  measure;
  measure_p;
end timeprot;

Re: task-safe hash table?

[Stephen Leake]

tmoran@acm.org writes:

> with ada.calendar,
>      ada.text_io;
> procedure timeprot is
>
> <snip>

This looks like a reasonable test. Here's my results with GNAT 5.04 on
Windows XP (I only kept the second run; the first loads cache):

gnatmake -O0
./timeprot.exe 
a 0.025702000 mics
b 0.026539000 mics
c 0.029333000 mics
prot.a 4.420673000 mics
prot.b 0.504533000 mics
prot.c 0.423238000 mics


gnatmake -O2
./timeprot.exe 
a 0.023188000 mics
b 0.022629000 mics
c 0.023187000 mics
prot.a 7.770820000 mics
prot.b 0.576610000 mics
prot.c 0.529676000 mics

Interesting that it is slower with -02!

AdaCore recommends against using -O3 because it includes "potentially
unsafe and disruptive optimizations". But here it is anyway:

gnatmake -O3
./timeprot.exe 
a 0.014806000 mics
b 0.014527000 mics
c 0.004470000 mics
prot.a 7.431950000 mics
prot.b 0.619911000 mics
prot.c 0.529676000 mics

There is some variation from run to run. But this is pretty convincing
that a protected function call is 25 times slower than a plain
function call. I'll see what AdaCore has to say. And I'll try it on
Lynx, which is more real-time than Windows or Linux :).

-- 
-- Stephe

Re: task-safe hash table?

[Georg Bauhaus]

tmoran@acm.org wrote:
> with ada.calendar,
>      ada.text_io;
> procedure timeprot is

FWIW, ObjectAda 8.2 for Windows gives similar results
(Using Ada.Real_Time in place of Ada.Calendar for
measuring mics.)


a 0.0610 mics
b 0.0610 mics
c 0.0610 mics
prot.a 1.2817 mics
prot.b 0.9155 mics
prot.c 0.8545 mics
a 0.0610 mics
b 0.0610 mics
c 0.0610 mics
prot.a 1.2817 mics
prot.b 0.9155 mics
prot.c 0.8545 mics

optimized:

a 0.0610 mics
b 0.0610 mics
c 0.0610 mics
prot.a 1.2207 mics
prot.b 0.8545 mics
prot.c 0.7935 mics
a 0.0610 mics
b 0.0610 mics
c 0.0610 mics
prot.a 1.2207 mics
prot.b 0.8545 mics
prot.c 0.7935 mics

Re: task-safe hash table?

[Simon Wright]

Stephen Leake <stephen_leake@acm.org> writes:

> tmoran@acm.org writes:
>
>>> > the overhead of making it Protected would probably kill the gain.
>>>
>>> What "overhead"?
>>    In a trivial single-tasking test program on my machine, a call to a
>> Protected function compiled with Gnat 3.15p -O2 takes
>>   0.304697000 mics while a call to a regular function takes
>>   0.022779000 microseconds.
>
> Interesting. Please post the program; I'll run it with a later GNAT,
> and if the results are still so bad, submit a bug report.

I wouldn't have thought 0.3 microseconds was that bad?

Re: task-safe hash table?

[tmoran]

>I wouldn't have thought 0.3 microseconds was that bad?
 Why I remember when a single mainframe NOP instruction took ten times that...

Re: task-safe hash table?

[Steve Whalen]

tmoran@acm.org wrote:
> > > the overhead of making it Protected would probably kill the gain.
> >
> > What "overhead"?
>    In a trivial single-tasking test program on my machine, a call to a
> Protected function compiled with Gnat 3.15p -O2 takes
>   0.304697000 mics while a call to a regular function takes
>   0.022779000 microseconds.
> Using -O3, it's
> 0.291347000 mics while a call to a regular function takes
> 0.001893000 microseconds.

When I run your program on a Linux Debian Sarge server with a vanilla
install of GNAT 3.15p with a slow 450mhz Pentium (and no other load) I
get:

==> compiled with no optimization <==
     a 0.076000000 mics
     b 0.075000000 mics
     c 0.073000000 mics
prot.a 3.590000000 mics
prot.b 2.480000000 mics
prot.c 1.710000000 mics

==> compiled with O2 optimization <==
     a 0.064000000 mics
     b 0.041000000 mics
     c 0.041000000 mics
prot.a 3.726000000 mics
prot.b 2.356000000 mics
prot.c 1.586000000 mics

==>  compiled with O3 optimization  <==
     a 0.017000000 mics
     b 0.017000000 mics
     c 0.006000000 mics
prot.a 3.820000000 mics
prot.b 2.369000000 mics
prot.c 1.865000000 mics

So the relationship between optimization levels looks materially the
same, as does the overhead of protected mode.

Steve

Re: task-safe hash table?

[Ole-Hjalmar Kristensen]

More or less the same pattern on my system:

~/ada/div-ada> uname -a
SunOS techra25 5.9 Generic_118558-08 sun4u sparc SUNW,Sun-Fire-V210

~/ada/div-ada> gnatmake -s tmoran
gcc -c tmoran.adb
gnatbind -x tmoran.ali
gnatlink tmoran.ali
<ok145024@techra25:~/ada/div-ada> ./tmoran
a 0.111000000 mics
b 0.108000000 mics
c 0.112000000 mics
prot.a 1.696000000 mics
prot.b 1.202000000 mics
prot.c 0.589000000 mics
a 0.106000000 mics
b 0.107000000 mics
c 0.111000000 mics
prot.a 1.325000000 mics
prot.b 1.209000000 mics
prot.c 0.596000000 mics
~/ada/div-ada> gnatmake -s -O2 tmoran
gcc -c -O2 tmoran.adb
gnatbind -x tmoran.ali
gnatlink tmoran.ali
<ok145024@techra25:~/ada/div-ada> ./tmoran
a 0.096000000 mics
b 0.090000000 mics
c 0.091000000 mics
prot.a 1.461000000 mics
prot.b 1.148000000 mics
prot.c 0.498000000 mics
a 0.090000000 mics
b 0.089000000 mics
c 0.091000000 mics
prot.a 1.313000000 mics
prot.b 1.140000000 mics
prot.c 0.498000000 mics
~/ada/div-ada> gnatmake -s -O3 tmoran
gcc -c -O3 tmoran.adb
gnatbind -x tmoran.ali
gnatlink tmoran.ali
~/ada/div-ada> ./tmoran
a 0.089000000 mics
b 0.084000000 mics
c 0.003000000 mics
prot.a 1.282000000 mics
prot.b 0.969000000 mics
prot.c 0.485000000 mics
a 0.085000000 mics
b 0.084000000 mics
c 0.004000000 mics
prot.a 1.273000000 mics
prot.b 0.967000000 mics
prot.c 0.484000000 mics

-- 
   C++: The power, elegance and simplicity of a hand grenade.

Re: task-safe hash table?

[Matthew Heaney]

tmoran@acm.org wrote:
> Is there some code around for a hash table that allows multiple tasks
> to do simultaneous lookup?

That's the wrong question.

Find a hash table type with sequential semantics, and then wrap the
hash table object inside a protected object (or use whatever
synchronization scheme best suites your application).

You can find a hash table here:

http://charles.tigris.org

-Matt