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

[heatwole@his.com (Kevin D. Heatwole)]

In article <dewar.848839209@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) wrote:

>Well here we sure have a similar case -- we have no trouble agreeing that
>Bob Duff's claimed obvious semantics are fine, and that we can implement
>them with no trouble -- but the implementation has a ghastly efficiency
>problem (if taking locks is expensive).
>
>Note that it is not just reference counts that cause this problem. Even if
>we use what I would guess is the expected implementation of unbounded
>strings which is to use controlled types (as in GNAT), we are in trouble.
>
>Controlled types themselves implicitly reference global shared data
>structures, or at least may do so in the model where chains of objects
>to be finalized are maintained. If these chains must be protected against
>multi-threading, there are again ghastly efficiency implications in 
>systems where taking a lock is expensive. 

I think you might be going too far in categorizing this as having "ghastly
efficiency implications".  In a language that incorporates separate 
threads of execution, this "efficiency problem" occurs all over the place.
As you point out, an implementation for controlled types will probably
involve some need for serializing access to shared data structures.  So
does protected types, tasks, and even dynamic allocation of memory.

Indeed, the use of reference counts in an unbounded string implementation
is presumeably done to save a dynamic allocation which would involve
some taking of a lock anyway.

So, what is the big deal here as it applies to the specific case of unbounded
strings?

Certainly, initial implementations of controlled types, dynamic allocation,
and unbounded strings will be less than optimal, but it is up to us implementers
to provide efficient implementations of these features of Ada. 

Is it really that much harder to provide an efficient ref-counted tasking safe
implementation of unbounded strings than it is to provide an efficient tasking
safe allocator?

Kevin Heatwole
OC Systems, Inc.