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 <E1FnJC.HI4@world.std.com>, bobduff@world.std.com (Robert A
Duff) wrote:

>In article <heatwole-ya023180002511960851580001@news.his.com>,
>Kevin D. Heatwole <heatwole@his.com> wrote:
>>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?
>
>Two points:
>
>You can make "new" efficient by having per-task pools of memory.
>Allocate each task 4K (say) and use that for "new".  And if it runs out,
>allocate some more from a global pool.  Or steal some from another task.
>This will reduce the probability of lock contention.

I suspect that even this approach would have some difficulties involving
pool-specific (or global) locks.  While task A may allocate the storage
out of its per-task pool of memory, task B may be the task that deallocates
the memory later.  If you have two threads mucking about with the same
pool of memory, you will need to implement some form of serialization.

Of course, as you point out, garbage collection techniques might help to
make the usual case efficient but this has its drawbacks (and still might
not reduce/eliminate the need for locking).

Also, note that getting the identity of the currently executing task may be
inefficient as well.  On our target, AIX for the PowerPC, getting the identity
of the current thread involves an AIX call to pthread_self.  Since there is
no thread-specific memory, this call is implemented as a search of a thread
id table using the current stack pointer with appropriate locking (boy, is this 
slow!).  We have chosen to reserve a register to point to thread-specific 
memory to alleviate this problem, but this makes C calling Ada slower 
because it needs to call pthread_self to setup this register.

>OK, here's a third point:  All this talk about inefficient locks is
>based on the assumption that each Ada task is mapped to a single OS
>thread.  If you're willing to give up the benefits of that (on, say,
>Windows 95), then it's not hard to do very efficient locking.

Why is this true?  Is it because on most OSes, OS calls are inherently
expensive?
I would think that if the OS wanted to make this efficient and it was a
priority for the users, the lock calls could be just as efficient (whether done
by the OS or done by the Ada runtime).  Anyway, I suspect that now that
many OSes are becoming multi-threaded and with the more common use of
multiple processors (even in the PC world), that the OSes will become more
friendly and efficient for us Ada compiler implementors.  The OSes are finally
catching up with Ada!

Kevin Heatwole
OC Systems, Inc.