Re: [MIT-Scheme-devel] Symmetric MultiProcessing

[Taylor R Campbell]

   Date: Tue, 3 Mar 2015 16:02:15 -0700
   From: Friar Puck <address@hidden>

   > From: Taylor R Campbell <address@hidden>
   > Date: Tue, 3 Mar 2015 20:50:54 +0000
   > 
   > HASH-TABLE/CLEAN! probably shouldn't cons.

   Then it shouldn't call maybe-shrink-table! and cons a shorter vector
   :-(but not one bucket pair).  If we cons bucket lists too (get more
   functional!) blessings will follow.  Is this not a tenet of our faith?

The MAYBE-SHRINK-TABLE! happens after existing entries have been
deleted, so it's less likely to be an issue.

   What goes kaboom if it is interrupted?  If the user would notice an
   inconsistency after an abort, perhaps the user needed to apply
   without-interrupts (or already has!).  If it is the table operations
   themselves that are thuswise borked, perhaps without-interruption
   needs to be in set-key&datum-ephemeral-entry-datum!.  It does NOT need
   to be where with-table-locked was, in method:modify!.  Many table
   types just do not need it.

We currently provide the property that hash table updates are atomic.
It's not the user's responsibility to ensure this.

Are you tracing this to an observed performance issue or are you just
trying to get rid of WITHOUT-INTERRUPTION as much as possible?

   > Not sure SET-EPHEMRON-DATUM! is guaranteed to be atomic either.

   I DO assume the hardware will be coherent enough that word-size
   reads/writes are atomic/uninterruptible.  Thus without-interruption
   sections can get small enough to vanish.  Are we all cool with
   that?

Fair enough.  If you would like to push WITHOUT-INTERRUPTION into the
SET-ENTRY-DATUM! routines that need it, go ahead.

   Assuming word-size atomic writes, set-ephemeron-datum! is just an
   atomic primitive-object-set! followed by a reference barrier (what the
   what? and is the test for the #f key just an optimization???).

A reference barrier guarantees the object that is passed to it will
not have been GC'd.

If the ephemeron is broken, it is probably a space leak to store a new
datum in it.

   An interrupt anywhere in there is no disaster, yes?

Guess not.

   >    Many operations could move a functional rehash out of their critical
   >    sections, making the sections really tiny.
   > 
   > I don't see anywhere that COMPUTE-HASH! is called while interrupts are
   > blocked.

   That would be a problem except that without-interruption is applied
   when needed, in rehash-table!.  I was referring to rehashes occurring
   in maybe-grow-table! and maybe-shrink-table!, which are called inside
   the former with-table-locked sections, at the end of many operations:
   hash-table/clean!, set-hash-table/rehash-threshold!,
   set-hash-table/rehash-size!, hash-table/put!, hash-table/modify!,
   hash-table/remove! and even hash-table/count (via rehash-table!).

Problem is that one of the invariants of hash tables is that the size
is consistent, so a ^G at the wrong moment won't leave you with a
giant hash table that needs to be shrunk, or an overloaded hash table
that needs to be grown.  That's why those happen in the critical
section.

(Personally I would rather avoid hash tables altogether: there are
much safer data structures that give guaranteed performance, a total
ordering on keys, &c.  But plenty of people use hash tables and
they're what we have.)

   > Hmm?  I don't understand.  Why create two separate abstractions?  Just
   > protect all [populations] by a mutex by default, inside the population
   > abstraction.

   I didn't want to force serialization on all populations, much less
   serialize all operations on all populations.

Since populations are almost always for global databases and are
almost never performance-critical, it would be much simpler, I think,
if they were just covered by locks by default.