Storage management

Storage management

[Florian Weimer]

What is the current state of the art with regard to programmer support
for storage management?

With GNAT, Ada.Finalization adds tons of run-time calls to deal with
abort deferral (even with pragma Restrictions (No_Abort_Statements)),
puts the object on some sort of list, and does some secondary stack
allocations which I don't understand.  Clearly, this is not supposed
to be used in performance-critical code, so I doubt it can be used for
a generic smart pointer implementation.  (Object allocation in inner
loops is generally a bad idea, but this overhead is also incurred when
copying smart pointers around.)

Is there some other approach?  Can limited types be used to enforce
linearity (in the sense of linear types, cf.
<http://home.pipeline.com/~hbaker1/Use1Var.html> and
<http://iml.univ-mrs.fr/~girard/linear.pdf>)?

If it's about pure storage management, GC support would be an option,
too, but AFAIK, you need one of the managed code implementations for
that, or somewhat unsafe libraries (in the sense that you need to
specify which objects are leaf objects, and only store access values
in locations where they are visible to the collector).

Re: Storage management

[Robert A Duff]

Florian Weimer <fw@deneb.enyo.de> writes:

> What is the current state of the art with regard to programmer support
> for storage management?
>
> With GNAT, Ada.Finalization adds tons of run-time calls to deal with
> abort deferral (even with pragma Restrictions (No_Abort_Statements)),
> puts the object on some sort of list, and does some secondary stack
> allocations which I don't understand.  Clearly, this is not supposed
> to be used in performance-critical code, so I doubt it can be used for
> a generic smart pointer implementation.  (Object allocation in inner
> loops is generally a bad idea, but this overhead is also incurred when
> copying smart pointers around.)

AdaCore is actively working on making finalization much more efficient
(e.g. avoiding all those finalization lists, when possible).

> Is there some other approach?  Can limited types be used to enforce
> linearity (in the sense of linear types, cf.
> <http://home.pipeline.com/~hbaker1/Use1Var.html> and
> <http://iml.univ-mrs.fr/~girard/linear.pdf>)?

Yes, you can do better with limited types (derive from
Limited_Controlled instead of Controlled).

> If it's about pure storage management, GC support would be an option,
> too, but AFAIK, you need one of the managed code implementations for
> that, or somewhat unsafe libraries (in the sense that you need to
> specify which objects are leaf objects, and only store access values
> in locations where they are visible to the collector).

There is some intention to support proper GC at AdaCore, but it's going
to be rather far in the future -- not a whole lot of (paying) customer
demand for that.  Meanwhile, you can try the Boehm "conservative" GC.
My experience is that it works pretty well, so long as you don't use up
most of your address space with allocated objects.  So on a 64-bit
machine, that should work pretty well.  Or on a 32-bit machine, if you
don't use too much real memory.

The ARG is also working on some interesting "region based" schemes.

- Bob

Re: Storage management

[sjw]

On Nov 1, 11:13 am, Florian Weimer <f...@deneb.enyo.de> wrote:
> What is the current state of the art with regard to programmer support
> for storage management?
>
> With GNAT, Ada.Finalization adds tons of run-time calls to deal with
> abort deferral (even with pragma Restrictions (No_Abort_Statements)),
> puts the object on some sort of list, and does some secondary stack
> allocations which I don't understand.  Clearly, this is not supposed
> to be used in performance-critical code, so I doubt it can be used for
> a generic smart pointer implementation.  (Object allocation in inner
> loops is generally a bad idea, but this overhead is also incurred when
> copying smart pointers around.)

It has to depend on how fast a processor you can afford to buy for
your application. Here (2.4 GHz Macbook Pro, GCC 4.3.0) it takes 150
ns to allocate/free a character vs 1050 ns for the (rough) equivalent
using a BC smart pointer.

Re: Storage management

[Florian Weimer]

* Robert A. Duff:

> Florian Weimer <fw@deneb.enyo.de> writes:
>
>> What is the current state of the art with regard to programmer support
>> for storage management?
>>
>> With GNAT, Ada.Finalization adds tons of run-time calls to deal with
>> abort deferral (even with pragma Restrictions (No_Abort_Statements)),
>> puts the object on some sort of list, and does some secondary stack
>> allocations which I don't understand.  Clearly, this is not supposed
>> to be used in performance-critical code, so I doubt it can be used for
>> a generic smart pointer implementation.  (Object allocation in inner
>> loops is generally a bad idea, but this overhead is also incurred when
>> copying smart pointers around.)
>
> AdaCore is actively working on making finalization much more efficient
> (e.g. avoiding all those finalization lists, when possible).

This sounds interesting.  Unfortunately, the language-mandated
overhead (primarily abort deferral) is difficult to get rid of.  I
hope that there will be a configuration pragma which eliminates it,
even if it means using a self-compiled run-time.

>> Is there some other approach?  Can limited types be used to enforce
>> linearity (in the sense of linear types, cf.
>> <http://home.pipeline.com/~hbaker1/Use1Var.html> and
>> <http://iml.univ-mrs.fr/~girard/linear.pdf>)?
>
> Yes, you can do better with limited types (derive from
> Limited_Controlled instead of Controlled).

Hmm.  What I want is to mark certain subprograms as consumers, and get
a warning when a subprogram is exited without calling a consumer
subprogram for a local variable of limited type.  OTOH, with overflow
checking, there's a chance of raising an exception almost all the
time, so I'll need something like

      Clear (Ref);
   exception
      when others =>
         Clear (Ref);
         raise;
   end Proc;

at the end of each procedure.  So it's not actually desirable, either,
even if tools support (maybe based on ASIS?) to enforce this coding
style.

> There is some intention to support proper GC at AdaCore, but it's going
> to be rather far in the future -- not a whole lot of (paying) customer
> demand for that.  Meanwhile, you can try the Boehm "conservative" GC.

I know, but I fear that some aspects are difficult to get 100% right.
For instance, it seems necessary to change the way the secondary stack
is allocated, so that it is scanned for pointers, too.  I'm not sure
if this can be done with a purely library-based approach.

Re: Storage management

[Randy Brukardt]

"Florian Weimer" <fw@deneb.enyo.de> wrote in message 
news:87abciurrl.fsf@mid.deneb.enyo.de...
...
> This sounds interesting.  Unfortunately, the language-mandated
> overhead (primarily abort deferral) is difficult to get rid of.  I
> hope that there will be a configuration pragma which eliminates it,
> even if it means using a self-compiled run-time.

Actually, that's the easiest to get rid of (or minimize enough to make it 
irrelevant most of the time). The Janus/Ada implementation of controlled 
types is roughly the same as the GNAT one. We take two steps to reduce the 
overhead of abort-deferral:

(1) If the program has no tasks, there is no task supervisor and the abort 
deferral routine does nothing (it gets called, but the overhead is just an 
indirect call and a return instruction). We optimized programs not 
containing tasks so that we have less of a disadvantage in benchmarks 
against other non-tasking languages (like C and C++). (It's not as common 
for real Ada programs to not contain tasks, but it helps any that don't as 
well.)

(2) We made abort deferral as cheap as possible. It is just a counter in the 
TCB of a task, and we change it directly in the supervisor interface code 
(this is a big advantage of not use OS threads for task mapping). It takes 4 
machine instructions (this is assembler code). Re-enabling aborts is 
slightly more expensive, as we have to check if someone did abort the task 
while it was abort deferred. But that is the rare case, and it add only two 
machine instructions.

Actually adding or removing an object from the finalization chain isn't that 
expensive, either. It takes about 10 machine instructions.

The biggest expense with Janus/Ada is putting the needed exception handler 
around a Finalize call (we have to turn all exceptions into Program_Error). 
That's probably cheaper with GNAT.

I find I have more sympathy with those that worry about the 16-byte per 
object space overhead (that can be significant for smart pointers, for 
instance, if there are a lot of them in the program). The time will matter 
only in the most critical of applications. (And, based on another thread 
here, moving a few bytes around in some random location will change the 
performance of your program +/- 50% anyway -- that effect will completely 
swamp any finalization overhead.) I doubt anyone with truely critical 
performance needs is going to be using smart pointers or containers or 
anything else that adds overhead.

                                        Randy.

Re: Storage management

[Dmitry A. Kazakov]

I have a general question. Does anybody use abort and asynchronous transfer
of control?

After all, there is no chance to have them reasonably working anyway. The
notorious example from ARM 9.7.1:

select
   delay 5.0;
then abort
   Get_Line (...);
end select;

has good chances not to work.

How about to remove that stuff altogether and make a far more important
finalization right and fast?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Storage management

[Dmitry A. Kazakov]

On Fri, 07 Nov 2008 11:54:05 +0200, Niklas Holsti wrote:

> Dmitry A. Kazakov wrote:
>> I have a general question. Does anybody use abort
>> and asynchronous transfer of control?
> 
> I do, to set a limit on the running time of a possibly lengthy 
> procedure Analyse:
> 
>      select
>         delay Opt.Max_Analysis_Time;
>         Output.Error ("Maximum analysis time exceeded.");
>      then abort
>         Analyse;
>      end select;

That does not look like a good example. In such cases there would be some
GUI with progress indication stuff, etc. I mean that most likely Analyse
would periodically call something in order to indicate its state; store the
results etc. These would be natural candidates to abort it "cooperatively,"
through an exception propagation.

I think that abort/ATC as a language feature just does not hold with Ada's
level of safety. 

>> After all, there is no chance to have them reasonably working anyway.
> 
> It seems to work for me (GNAT 3.15p), except that I had to add a 
> dummy "delay 0.1" at the end of the main subprogram. Otherwise the 
> program would sometimes hang indefinitely in the termination phase. 
> This program has no tasks, so the abort and ATC are the only form 
> of concurrency.

The example I meant was to cancel Get_Line. It worked once in 3.15p under
Windows, if I correctly remember. It does not work now. And there is
absolutely no guaranty that it will ever work.

I honestly believe that the only case that may justify abort/ATC is
cancellation of an outstanding blocking I/O. But exactly this case is not
guaranteed to work, or rather is guaranteed not to work...

>> How about to remove that stuff altogether and make a far more important
>> finalization right and fast?
> 
> Isn't pragma Restrictions (No_Select_Statements) enough? Or is it 
> too strong, and a new restriction specifically for ATC would be better?

I would prefer pragma Cancelable put on a task. If a task is not cancelable
then abort would raise Tasking_Error, and an ATC in the task body would be
a compile-time error. All tasks would be non-cancelable per default.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Storage management

[Niklas Holsti]

Dmitry A. Kazakov wrote:
> I have a general question. Does anybody use abort
> and asynchronous transfer of control?

I do, to set a limit on the running time of a possibly lengthy 
procedure Analyse:

     select
        delay Opt.Max_Analysis_Time;
        Output.Error ("Maximum analysis time exceeded.");
     then abort
        Analyse;
     end select;

> After all, there is no chance to have them reasonably working anyway.

It seems to work for me (GNAT 3.15p), except that I had to add a 
dummy "delay 0.1" at the end of the main subprogram. Otherwise the 
program would sometimes hang indefinitely in the termination phase. 
This program has no tasks, so the abort and ATC are the only form 
of concurrency.

> How about to remove that stuff altogether and make a far more important
> finalization right and fast?

Isn't pragma Restrictions (No_Select_Statements) enough? Or is it 
too strong, and a new restriction specifically for ATC would be better?

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Storage management

[Niklas Holsti]

Dmitry A. Kazakov wrote:
> On Fri, 07 Nov 2008 11:54:05 +0200, Niklas Holsti wrote:
> 
> 
>>Dmitry A. Kazakov wrote:
>>
>>>I have a general question. Does anybody use abort
>>>and asynchronous transfer of control?
>>
>>I do, to set a limit on the running time of a possibly lengthy 
>>procedure Analyse:
>>
>>     select
>>        delay Opt.Max_Analysis_Time;
>>        Output.Error ("Maximum analysis time exceeded.");
>>     then abort
>>        Analyse;
>>     end select;
> 
> 
> That does not look like a good example. In such cases there
> would be some GUI with progress indication stuff, etc. I mean
> that most likely Analyse would periodically call something in
> order to indicate its state; store the results etc. These
> would be natural candidates to abort it "cooperatively,"
> through an exception propagation.

This example is a batch program -- no GUI, no interaction. The most 
unpredictable part of the execution time is spent waiting for a 
child process to respond, using blocking I/O to read a pipe that 
carries the standard output channel of the child process. The child 
process can get stuck (take a very long time) at any point, so it 
is not enough to make Analyse check the elapsed time after every 
pipe-read, for example.

If this example had a GUI, it would not need a programmed 
delay-then-abort time-out; the user would get bored and would click 
something to abort the child process, which would make the Analyse 
procedure terminate, too.

> I honestly believe that the only case that may justify
> abort/ATC is cancellation of an outstanding blocking I/O.

Which is the case in my example.

I think that abort/ATC is also useful in hard real-time systems as 
a guard against a task overrunning its deadlines (although 
execution-time budgeting is an alternative, perhaps better). It is 
difficult and error-prone to embed overrun-checking code in the 
task itself, and it will complicate the code -- poor "separation of 
concerns".

> But exactly this case is not guaranteed to work, or rather
> is guaranteed not to work...

Aborting blocking I/O is "guaranteed not to work"? Can you explain 
why? Is this something that has been discussed before on c.l.a.?

>> Isn't pragma Restrictions (No_Select_Statements) enough?
>> Or is it too strong, and a new restriction specifically
>> for ATC would be better?
> 
> I would prefer pragma Cancelable put on a task. If a task
> is not cancelable then abort would raise Tasking_Error,
> and an ATC in the task body would be a compile-time error.

I will leave it to the language experts to comment on that 
suggestion. I assume it would have to forbid ATCs in subprograms 
called from the task, too, which would require some form of 
subprogram-level contract that the subprogram body executes no ATCs.

What about ctrl-C, that is, process abort from the operating 
system? I don't think that users would be happy if Ada applications 
could not be aborted with ctrl-C. Do abort-deferred operations now 
defer ctrl-C, too?

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Storage management

[Dmitry A. Kazakov]

On Fri, 07 Nov 2008 14:12:30 +0200, Niklas Holsti wrote:

> Dmitry A. Kazakov wrote:
>> 
>> But exactly this case is not guaranteed to work, or rather
>> is guaranteed not to work...
> 
> Aborting blocking I/O is "guaranteed not to work"? Can you explain 
> why? Is this something that has been discussed before on c.l.a.?

I don't know. But I discussed that with AdaCore people. Since the following
does not work with GNAT Pro 6.2 (Windows wavefront):

with Ada.Text_IO;  use Ada.Text_IO;
procedure Test_ATC is
begin
   Put_Line ("Type");
   select
      delay 2.0;
      Put_Line ("Timed out");
   then abort
      Put_Line ("You typed " & Get_Line);
   end select;
end Test_ATC;

Actually I was almost certain that this were *not* required to work. I only
wished to know if they considered it as nice to have working or not. (:-))

There is no way Ada could abort I/O if the OS does not allow this. Second
to Get_Line, or likely the first wanted case is canceling blocking socket
read. I would give 98% that it never will work with ATC.

>>> Isn't pragma Restrictions (No_Select_Statements) enough?
>>> Or is it too strong, and a new restriction specifically
>>> for ATC would be better?
>> 
>> I would prefer pragma Cancelable put on a task. If a task
>> is not cancelable then abort would raise Tasking_Error,
>> and an ATC in the task body would be a compile-time error.
> 
> I will leave it to the language experts to comment on that 
> suggestion. I assume it would have to forbid ATCs in subprograms 
> called from the task, too, which would require some form of 
> subprogram-level contract that the subprogram body executes no ATCs.

Or to constrain its use like with the selective accept.

> What about ctrl-C, that is, process abort from the operating 
> system? I don't think that users would be happy if Ada applications 
> could not be aborted with ctrl-C. Do abort-deferred operations now 
> defer ctrl-C, too?

The meaning of ctrl-C depends on the OS. Ada standard cannot mandate that
pressing ctrl-C is equivalent to aborting the environment task in the sense
of "abort" statement. Then usually OS have efficient means to kill a
process preemptively bypassing any "abort deferred" stuff.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Storage management

[Georg Bauhaus]

Dmitry A. Kazakov schrieb:

> There is no way Ada could abort I/O if the OS does not allow this. Second
> to Get_Line, or likely the first wanted case is canceling blocking socket
> read. I would give 98% that it never will work with ATC.

OK, yet, does there have to be an operating system
that dictates how the Ada runtime does or does not
abort I/O? :-)

Re: Storage management

[Dmitry A. Kazakov]

On Fri, 07 Nov 2008 14:28:14 +0100, Georg Bauhaus wrote:

> Dmitry A. Kazakov schrieb:
> 
>> There is no way Ada could abort I/O if the OS does not allow this. Second
>> to Get_Line, or likely the first wanted case is canceling blocking socket
>> read. I would give 98% that it never will work with ATC.
> 
> OK, yet, does there have to be an operating system
> that dictates how the Ada runtime does or does not
> abort I/O? :-)

Yes, an OO OS.

If there were no I/O, but blocking entry calls, they would be trivially
cancelable in a timed entry call.

In the milliseconds area an I/O is not cancelable not because of physical
reasons, like when the disk controller is busy positioning the heads. These
take microseconds.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Storage management

[sjw]

On Nov 7, 8:30 am, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:
> I have a general question. Does anybody use abort and asynchronous transfer
> of control?
>
> After all, there is no chance to have them reasonably working anyway. The
> notorious example from ARM 9.7.1:
>
> select
>    delay 5.0;
> then abort
>    Get_Line (...);
> end select;
>
> has good chances not to work.

I've used this for test code where the idea was to demonstrate that
the abortable_part didn't get blocked like it used to.

Also, in deliverable code -- the abortable_part was waiting for a PO
to be triggered by an interrupt (or not).

Personally I've found no need to worry about problems with Get_Line in
the abortable_part.

Re: Storage management

[Dmitry A. Kazakov]

On Sat, 8 Nov 2008 03:04:24 -0800 (PST), sjw wrote:

> Also, in deliverable code -- the abortable_part was waiting for a PO
> to be triggered by an interrupt (or not).

Hmm, why ATC rather than a timed entry call?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Storage management

[sjw]

On 8 Nov, 12:33, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:
> On Sat, 8 Nov 2008 03:04:24 -0800 (PST), sjw wrote:
> > Also, in deliverable code -- the abortable_part was waiting for a PO
> > to be triggered by an interrupt (or not).
>
> Hmm, why ATC rather than a timed entry call?

I was remembering a previous version of this code -- we now do exactly
as you say.

Re: Storage management

[christoph.grein]

On 7 Nov., 14:22, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:

> I don't know. But I discussed that with AdaCore people. Since the following
> does not work with GNAT Pro 6.2 (Windows wavefront):
>
> with Ada.Text_IO;  use Ada.Text_IO;
> procedure Test_ATC is
> begin
>    Put_Line ("Type");
>    select
>       delay 2.0;
>       Put_Line ("Timed out");
>    then abort
>       Put_Line ("You typed " & Get_Line);
>    end select;
> end Test_ATC;

How come? What did they say? The following piece of code works fine
(GNAT Pro 6.0.1 on Linux SuSE 9.1):

  Start: constant Time := Clock;

begin

  select
    delay 5.0;
    Put_Line ("Time out");
  then abort
    Put_Line ("Read """ & Get_Line & '"');
  end select;

  Put_Line (Duration'Image (Clock - Start));

Re: Storage management

[Dmitry A. Kazakov]

On Mon, 10 Nov 2008 06:28:24 -0800 (PST), christoph.grein@eurocopter.com
wrote:

> How come? What did they say?

I think they will not object me quoting the conversation:

*Q.* Is it correct to conclude that Get_Line is not abortable this way?

*A.* Right, that's a correct understanding.
In general it is unsafe or not possible to interrupt system calls, so
if you need to interrupt I/O, you should probably use something like
Get_Immediate.

---------------------
I think they are absolutely right here. It may work (under SuSe), or not
(under Windows). To me this is a perfect reason to remove ATC stuff from
the language. It causes a sufficient distributed overhead, is unreliable
with OO programming and non-portable in virtually single case where it
could come handy.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de