Re: task-safe hash table?

On Thu, 01 Jun 2006 14:30:53 -0500, tmoran@xxxxxxx 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
.

Relevant Pages

  • Re: task-safe hash table?
    ... running on a multi-core cpu. ... Since a lookup in a hash table is, presumably, pretty fast, ... because nobody knows how to do concurrent programming". ...
    (comp.lang.ada)
  • Re: task-safe hash table?
    ... running on a multi-core cpu. ... Since a lookup in a hash table is, presumably, pretty fast, ... because nobody knows how to do concurrent programming". ...
    (comp.lang.ada)
  • Re: Mutable objects which define __hash__ (was Re: Why are tuples immutable?)
    ... It means you only have to compute the hash for any given object once, ... >> of nested tuples as keys and reused them frequently for lookup. ... is entered into the dict state. ... Once the bucket is selected, a number of keys may be found there. ...
    (comp.lang.python)
  • Re: universality of codons to amino acids
    ... >> When doing bits of bioinformatic software, a hash table for codons ... >> that converts them to amino acids is actually a common theme. ... mapping the hash key to an index in a lookup table that has ... > For hash-tables see: ...
    (talk.origins)
  • Re: universality of codons to amino acids
    ... >> tRNA is rather less than exact in its mapping, ... >>> When doing bits of bioinformatic software, a hash table for codons ... > mapping the hash key to an index in a lookup table that has ... Implement a system to deal with collissions (tradistionally ...
    (talk.origins)