Re: Fast locking (Was Re: Java vs Ada 95)

Re: Fast locking (Was Re: Java vs Ada 95)

[Marin David Condic, 561.796.8997, M/S 731-93]

"Norman H. Cohen" <ncohen@WATSON.IBM.COM> writes:
>(My favorite PowerPC syncrhonization instruction, used to ensure that
>out-of-order loads and stores do not violate the semantics of volatile
>variables and memory-mapped I/O ports, is Enforce In-Order Execution of
>I/O.  Its mnemonic is, naturally, eieio.)
>
    I thought that was the Farmer's Union - The E.I.E.I.O.?

    MDC

Marin David Condic, Senior Computer Engineer    ATT:        561.796.8997
M/S 731-96                                      Technet:    796.8997
Pratt & Whitney, GESP                           Fax:        561.796.4669
P.O. Box 109600                                 Internet:   CONDICMA@PWFL.COM
West Palm Beach, FL 33410-9600                  Internet:   CONDIC@FLINET.COM
===============================================================================
    "That which belongs to another."

        --  Diogenes, when asked what wine he liked to drink.
===============================================================================

Re: Once again, Ada absent from DoD SBIR solicitation

[Stanley R. Allen]

Bill Nielsen wrote:
> 
> After following up on a post I made last week ("Future of the Ada mandate")
> talking to  program managers involved DoD procurements, one thing is clear:
> The Ada mandate (which is written into law) is being widely ignored. In
> most cases, waivers are not even sought. This includes not just R&D
> software, but fieldable operational software that supports military
> missions for which Ada is expressly designed.
> 

From where I sit, it looks like Bill & Gregory are
right about the DoD.

My company's job is building big simulators, and the
new DoD *mandate* (sound familiar?) for simulations is
called HLA (High Level Architecture), which is being
developed by the Defense Modeling and Simulation
Office (DMSO)  See http://www.dmso.mil/projects/hla/
for some interesting overview and mandate stuff.

It's a good idea. It's time has come.  But the first
cut of the HLA API is given in .... C++ !  No mention
of Ada anywhere.  No justification is given for
avoiding the Ada madate.  And HLA is a *big* *deal*.
All the major DoD simulator contractors are hankering
after this work. 

So, two DoD mandates mitigate against one another.
(Homework: ask yourself seriously which one will win.)
Note that HLA-compliance for simulators must be
considered new development; there is no such thing
as a COTS HLA-based system.  It's too new.  So, the
COTS excuse is no reason.

C++ is still not ISO standardized, but many in the C++
community expect that it will be either this year or
early next.  When this happens, the DoD Ada mandate 
will lose one of its most important contentions --
that Ada is the best choice because of its inter-
national standardization, which no other OO language
currently has.

C++ still seems like a hoax.  Every other article or
book I read about C++ (written by members of the C++
community!) decries the complexity of the language,
how hard it is to maintain, how many "gotcha's" there
are, how difficult it is to build large systems which
don't have pathological dependency and fragility
problems, etc.

If you are a DoD Ada programmer, this could be your
future.  And don't kid yourself into thinking that Java
will be much better.  Java was designed for small
"applets" (the diminutive of "applications"); the Java
code I have seen so far isn't much of an advance in
readability over C++.  And the mindset of the two
language cultures is the same.  I shudder to think
of what a large system in Java will look like.

Imagine the Boeing 777 in C++ or Java.  I wouldn't
want to ride in it.

If you believe in the promise of Ada (as I do), you
could do yourself a favor by listening to Gregory
Aharonian.  And then doing something about it.


-- 
Stanley Allen
s_allen@hso.link.com
(713) 280-4445
-- my opinions only

Re: Java vs Ada 95 (Was Re: Once again, Ada absent from DoD SBIR solicitation)

[Robert I. Eachus]

In article <JSA.96Oct31145647@alexandria> jsa@alexandria (Jon S Anthony) writes:

  > You could do something similar for an Unbounded_String impl, and then
  > you would have a specific type which had GC in your implementation.
  > But it would not be based on malloc/adjusting/copying/freeing (which
  > will never be able to compete here).

    Yes, an implementation of Unbounded_String which uses reference
counts and lazy copying would work much better in this case.  It is a
perfectly legal and reasonable implementation of Unbounded_String, and
it looks like it would take a day or two to gin up.  The question is
whether it would be a global win, or just specific to some cases.  My
guess is that it is a net win in general, but only a few percent. I
may try it, but not this week.

    Besides, it would be better to do it against 3.07 to get a real
comparison.


--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Java vs Ada 95 (Was Re: Once again, Ada absent from DoD SBIR solicitation)

[Robert A Duff]

In article <EACHUS.96Nov1103759@spectre.mitre.org>,
Robert I. Eachus <eachus@spectre.mitre.org> wrote:
>    Yes, an implementation of Unbounded_String which uses reference
>counts and lazy copying would work much better in this case.  It is a
>perfectly legal and reasonable implementation of Unbounded_String, and
>it looks like it would take a day or two to gin up.  The question is
>whether it would be a global win, or just specific to some cases.  My
>guess is that it is a net win in general, but only a few percent. I
>may try it, but not this week.

Note that in Ada, or any language with tasking, the reference count
updates have to do locking in general, which might be rather expensive.

- Bob

Re: Java vs Ada 95 (Was Re: Once again, Ada absent from DoD SBIR solicitation)

[Robert A Duff]

In article <55gkch$gg6@fozzie.sun3.iaf.nl>,
Geert Bosch <geert@fozzie.sun3.iaf.nl> wrote:
>Robert A Duff (bobduff@world.std.com) wrote:
>`` Note that in Ada, or any language with tasking, the reference count
>   updates have to do locking in general, which might be rather
>   expensive. ''
>
>It is possible to have implementations that do not need locking for
>objects that are not aliased or allocated by an allocator (using new).

I don't understand what you mean by that.  I thought we were talking
about unbounded strings, and similar packages, where you allocate stuff
on the heap and use reference counting to know when to reclaim it.  The
stuff on the heap is, of course, aliased.

>In the more general case a very simple spin-lock is enough and the
>overhead should only be one memory-read when the object is not locked.
>String objects are locked almost never and when they are locked they
>are only locked for a short time.

True, but we're talking about an implementation of unbounded strings
where a simple string assignment is just a copy of a pointer.  Adding
locking, plus incr/decr of reference counts, is a substantial overhead
for such a simple operation.  If GC can eliminate that overhead, it may
well be a performance win, despite the fact that there is also some
GC-specific overhead.  (And I've seen some papers giving measurements
that agree with that suspicion.)

- Bob

Re: Java vs Ada 95 (Was Re: Once again, Ada absent from DoD SBIR solicitation)

[Robert Dewar]

Geert said

">In the more general case a very simple spin-lock is enough and the
>overhead should only be one memory-read when the object is not locked.
>String objects are locked almost never and when they are locked they
>are only locked for a short time."


What do you mean by a very simple spin lock in a uniprocessor environment.
Can you explain, are you talking about an EWD style implementation of
semaphores using sequential memory models?

Fast locking (Was Re: Java vs Ada 95)

[Geert Bosch]

In article <dewar.847053681@merv> Robert Dewar writes:
   Geert said
   
   "In the more general case a very simple spin-lock is enough and the
    overhead should only be one memory-read when the object is not locked.
    String objects are locked almost never and when they are locked they
    are only locked for a short time."

   What do you mean by a very simple spin lock in a uniprocessor environment.

I meant a lock that uses some form of busy-waiting instead of
blocking. Such a lock can be implemented using atomic test-and-set 
or atomic swap. Although these locks are not efficient for long
waits because of wasted CPU time and possible starving of other
tasks, for resources that are only locked for a short time, like
the ref-counted bounded string example, they are the best solution.

When implementing a sample package for spin locks I found that GNAT
doesn't provide intrinsic subprograms as described in Annex C of the
RM:  "It is recommended that intrinsic subprograms be provided for
convenient access to any machine operations that provide special
capabilities or efficiency that are not otherwise available through the
language constructs." (RM95 C.1(11))

This means that test-and-set is not possible using just GNAT at the
moment and indeed implementing efficient spin-locks is not possible.
Hopefully the extra intrinsic subprograms will be implemented
sometime.

Regards,
   Geert


-- 
E-Mail: geert@sun3.iaf.nl    

Re: Fast locking (Was Re: Java vs Ada 95)

[Larry Kilgallen]

In article <55o4g4$ki8@fozzie.sun3.iaf.nl>, geert@fozzie.sun3.iaf.nl (Geert Bosch) writes:

> This means that test-and-set is not possible using just GNAT at the
> moment and indeed implementing efficient spin-locks is not possible.
> Hopefully the extra intrinsic subprograms will be implemented
> sometime.

Descriptions of the GNAT developer environment posted here have
emphasized uniformity across platforms indicating that many of
those depending on it required that uniformity.

My presumption is that those folks have portable Ada code in mind.
The machine semantics of test-and-set on whatever machine you are
describing would seem to be somewhat different from the Alpha AXP
load-locked/store-conditional semantics.  A higher level construct
which supports portable programs seems better to me than something
specific to test-and-set hardware semantics.

(When I wrote about spin locks earlier in this thread, I thought we
were discussing techniques for compiler writers to use rather than
something exposed to Ada programmers.)

Larry Kilgallen

Re: Fast locking (Was Re: Java vs Ada 95)

[Robert Dewar]

"> This means that test-and-set is not possible using just GNAT at the
> moment and indeed implementing efficient spin-locks is not possible.
> Hopefully the extra intrinsic subprograms will be implemented
> sometime."

GNAT fully supports machine intrinsics, starting with version 3.07.

Re: Fast locking (Was Re: Java vs Ada 95)

[Geert Bosch]

Larry Kilgallen writes:
`` My presumption is that those folks have portable Ada code in mind.
   The machine semantics of test-and-set on whatever machine you are
   describing would seem to be somewhat different from the Alpha AXP
   load-locked/store-conditional semantics.  A higher level construct
   which supports portable programs seems better to me than something
   specific to test-and-set hardware semantics. ''

The Systems Programming Annex of the RM specifically advises atomic
read-modify-write operations like test and set, compare and swap etc.

I can't imagine there are many systems around these days that do not
provide efficient test-and-set semantics. Even the 8088 processor that
does not directly have a test-and-set instruction can easily emulate
one by doing an atomic swap between a processor register and a memory
location. On very simple processors it is almost always possible to
block all interrupts while doing the test-and-set.

Of course machines that do not have any instructions that can be used
to efficiently implement hardware-assisted locking will not have a
test-and-set intrinsic sub-program, but of course nobody expects to
magically be able to use hardware locking support when the target
platform does not have it. The point is that *when* it is available,
it should be usable in a consistent way.

Note that although test-and-set kind of mutual exclusion is a
very fast solution for locking resources for which is almost
never any contention, it certainly doesn't replace high-level
high-overhead locking provided by protected types.

The difference is that protected types provide strictly 
priority-based FIFO queuing which makes fair sharing of scarce
resources possible. It would be a good idea however to use
fast test-and-set locks in these as well.

The example below shows how to do this, when there is hardware
test-and-increment and decrement-and-test. Assumptions are
that the standard queuing is expensive (expensive system calls
involved) and non-queuing but blocking event semaphores are much
cheaper. I've verified that these assumptions hold on OS/2, but
I guess the situation is the same for other operating systems.

Implementing the solution below causes slightly more expensive
blocking/unblocking and essentially free locking/unlocking in absence
of contention for the lock. The semantics of the Fast_Queuing_Mutex
are exactly the same as for the Slow_Queuing_Mutex, although some
bookkeeping should be added to record the priority for the task
owning the fast-lock in case of Ceiling_Locking policy.

Example: (untested incomplete code, details might be wrong)

type Fast_Queuing_Mutex is record
   Slow_Lock	        : Slow_Queuing_Mutex; 
   Fast_Lock    	: Integer := 0;
   Fast_Lock_Ready      : Event_Semaphore := Not_Posted;
   Have_Slow_Lock	: Boolean := False;
end record;

procedure Request (L : in out Fast_Queuing_Mutex) is
   Was_Zero	: Boolean;
begin
   Test_And_Increment(L.Fast_Lock, Was_Zero);
   if Was_Zero then
      -- We have lock without any overhead
      return;
   else
      -- The fast lock already was in use.
      -- Now wait in the queue for the Mutex,
      -- (No wait if we're first)
      Request_Mutex(L.Slow_Lock);   
      -- We also have to wait for the fast lock
      -- This can be done using a non-priority based
      -- event semaphore
      Wait_Event(L.Fast_Lock_Ready);
      -- Can't set this before fast lock is released
      L.Have_Slow_Lock := True;
   end if;
end Request;

Article Unavailable

Re: Fast locking (Was Re: Java vs Ada 95)

[Larry Kilgallen]

In article <55r16k$m00@fozzie.sun3.iaf.nl>, geert@fozzie.sun3.iaf.nl (Geert Bosch) writes:

> I can't imagine there are many systems around these days that do not
> provide efficient test-and-set semantics. Even the 8088 processor that
> does not directly have a test-and-set instruction can easily emulate
> one by doing an atomic swap between a processor register and a memory
> location. On very simple processors it is almost always possible to
> block all interrupts while doing the test-and-set.

"Blocking all interrupts" in a multiprocessor environment would be
hazardous to the speed of other, non-interfering, activities.

> Of course machines that do not have any instructions that can be used
> to efficiently implement hardware-assisted locking will not have a
> test-and-set intrinsic sub-program, but of course nobody expects to
> magically be able to use hardware locking support when the target
> platform does not have it. The point is that *when* it is available,
> it should be usable in a consistent way.

My complaint is not that some machines lack fast locking primitives,
but rather that there was an assumption that those primitives will
always be "test and set".  DEC designers made the choice that their
"load-locked/store-conditional" semantics would be faster than more
traditional approaches.  Since they consistently win the SpecFP
and SpecInt comparisons with each new chip, I presume they know
what they are doing about fast hardware (although the portion of
their design having to do with locking primitives has nothing to
do with the portion of their design needed for the rather limited
SpecFP and SpecInt tests).

Larry Kilgallen

Re: Fast locking (Was Re: Java vs Ada 95)

[Robert Dewar]

Geert says

"> I can't imagine there are many systems around these days that do not
> provide efficient test-and-set semantics. Even the 8088 processor that
> does not directly have a test-and-set instruction can easily emulate
> one by doing an atomic swap between a processor register and a memory
> location. On very simple processors it is almost always possible to
> block all interrupts while doing the test-and-set."

Your imagination is deficient. Examples are the RS6000 and all earlier
MIPS chips. There are others!

Re: Fast locking (Was Re: Java vs Ada 95)

[Norman H. Cohen]

Robert Dewar wrote:
> 
> Geert says
> 
> "> I can't imagine there are many systems around these days that do not
> > provide efficient test-and-set semantics. 
...
> 
> Your imagination is deficient. Examples are the RS6000 and all earlier
> MIPS chips. There are others!

The RS6000 is not a processor, but a family of systems, early versions
of which were based on the POWER architecture and later versions of
which were based on the PowerPC architecture.  Robert is presumably
referring to the POWER architecture, which did not include
syncrhonization operations for shared-memory multiprocessors.  In
contrast, the PowerPC architecture provides the lwarx (load word
arithmetic and reserve, indexed) and stwcx (store word conditional,
indexed) instructions, which provide powerful and efficient
syncrhonization.  Every PowerPC architecture document I have seen
includes an appendix with syncrhonization programming examples, showing
how a handful of instructions, generally built around a lwarx/stwcx
pair, can be used to program such syncrhonization idioms as
Fetch-and-Store, Fetch-and-Add, Test-and-Set, Compare-and-Swap, and
lock/unlock.

(My favorite PowerPC syncrhonization instruction, used to ensure that
out-of-order loads and stores do not violate the semantics of volatile
variables and memory-mapped I/O ports, is Enforce In-Order Execution of
I/O.  Its mnemonic is, naturally, eieio.)

-- 
Norman H. Cohen
mailto:ncohen@watson.ibm.com
http://www.research.ibm.com/people/n/ncohen

Re: Fast locking (Was Re: Java vs Ada 95)

[Geert Bosch]

Larry Kilgallen (kilgallen@eisner.decus.org) wrote:
   "Blocking all interrupts" in a multiprocessor environment would be
   hazardous to the speed of other, non-interfering, activities.

Please don't twist my words. I specifically said for that this
solution might be good for small/old systems. If you need an example,
think of microcontrollers.

I also wrote:
   "Of course machines that do not have any instructions that can be used
    to efficiently implement hardware-assisted locking will not have a
    test-and-set intrinsic sub-program"

How could you still think I was suggesting that "Blocking all interrupts"
in a multiprocessor environment was a good idea? A multiprocessor system
without test-and-set or similar mechanisms falls into the category:
   "[...] of course nobody expects to magically be able to use hardware
    locking support when the target platform does not have it. The
    point is that *when* it is available, it should be usable in a
    consistent way.

Larry wrote:
  "My complaint is not that some machines lack fast locking primitives,
   but rather that there was an assumption that those primitives will
   always be "test and set".  "

I never said that, although test-and-set is the most well-known
primitive in this area, so I used that. I even listed some of the
other possible primitives. In any case, the test-and-set operation
can easily be implemented with other fast-locking operations. 

And the point is not that these low-level locks should be used in
most applications, but that they can be very valuable tools in
cases where they are needed just like the other parts of Annex C
of the ARM.

Larry wrote:
  "DEC designers made the choice that their "load-locked/
   store-conditional" semantics would be faster than more traditional
   approaches."

If I use that instruction as load-locked/store-whenzero than I have the
equivalent of test-and-set, which is why it makes sense to provide a
very generic fast-locking primitive like test-and-set in Ada
implementations rather than using DECs instruction-of-the-day.

Regards,
   Geert
-- 
E-Mail: geert@sun3.iaf.nl    

Re: Fast locking (Was Re: Java vs Ada 95)

[Hannes Haug]

kilgallen@eisner.decus.org (Larry Kilgallen) writes:

> My presumption is that those folks have portable Ada code in mind.
> The machine semantics of test-and-set on whatever machine you are
> describing would seem to be somewhat different from the Alpha AXP
> load-locked/store-conditional semantics.  A higher level construct
> which supports portable programs seems better to me than something
> specific to test-and-set hardware semantics.

Something like an inlined mutex_trylock?
This is something like test-and-set-lock.

> (When I wrote about spin locks earlier in this thread, I thought we
> were discussing techniques for compiler writers to use rather than
> something exposed to Ada programmers.)

The compiler writers should use fast locks and unlocks,
too. I think the os-mutexes are not fast enough.

 -hannes

Re: Fast locking (Was Re: Java vs Ada 95)

[Hannes Haug]

geert@fozzie.sun3.iaf.nl (Geert Bosch) writes:

> I meant a lock that uses some form of busy-waiting instead of
> blocking. Such a lock can be implemented using atomic test-and-set 
> or atomic swap. Although these locks are not efficient for long
> waits because of wasted CPU time and possible starving of other
> tasks, for resources that are only locked for a short time, like
> the ref-counted bounded string example, they are the best solution.

You can yield the task if the mutex is already locked.
Untested pseudo gnu c for sparc:

typedef struct mutex {
  volatile int lock;
} mutex_t;

static void
mutex_init (mutex_t *mp)
{
  mp->lock = 0;
}

static void
mutex_unlock (mutex_t *mp)
{
  mp->lock = 0;
}

static int
mutex_trylock (mutex_t *mp)
{
  int old_lock;
  asm volatile ("ldstub [%1],%0" : "=r" (old_lock) : "r" (&mp->lock));
  return old_lock;
}

static void
mutex_lock (mutex_t *mp)
{
  while (mutex_trylock (mp) != 0)
    thread_yield ();
}


typedef struct semaphore {
  mutex_t mutex;
  volatile int count;
} semaphore_t;

static void
semaphore_init (semaphore_t *sp, int count)
{
  mutex_init (&sp->mutex);
  sp->count = count;
}

static void
semaphore_post (semaphore_t *sp)
{
  mutex_lock (&sp->mutex);
  sp->count = sp->count + 1;
  mutex_unlock (&sp->mutex);
}

static int
semaphore_trywait (semaphore_t *sp) /* this is NOT the ordinary trywait */
{
  int old_count;
  mutex_lock (&sp->mutex);
  old_count = sp->count;
  if (old_count > 0)
    sp->count = old_count - 1;
  mutex_unlock (&sp->mutex);
  return old_count;
}

static void
semaphore_wait (semaphore_t *sp)
{
  while (semaphore_trywait (sp) == 0)
    thread_yield ();
}


This should be pretty fast. Even semaphore_wait
is small enough for automatic inlining.

 -hannes