Sapce overhead of controlled types 
Author Message
 Sapce overhead of controlled types

For gnat, the space overhead of controlled types seems to be 3 words
(1 as all other tagged types, and 2 to maintain a doubly linked list).
As in C++ there is no space overhead (the equivalent are not necessarily
"tagged" -- ie may have no virtual methods -- and implementations I've
used generate code so that the linked list is not needed).  I was
wondering if this implementation approach (putting objects on a doubly
linked list) was common in Ada compilers or even was made the only
practical by the standard.

-- Jean-Marc, for who this space overhead currently reduce the
usefullness of controlled types

Sent via Deja.com http://www.*-*-*.com/
Before you buy.



Fri, 13 Dec 2002 03:00:00 GMT  
 Sapce overhead of controlled types

Quote:

> For gnat, the space overhead of controlled types seems to be 3 words
> (1 as all other tagged types, and 2 to maintain a doubly linked list).
> As in C++ there is no space overhead (the equivalent are not necessarily
> "tagged" -- ie may have no virtual methods -- and implementations I've
> used generate code so that the linked list is not needed).  I was
> wondering if this implementation approach (putting objects on a doubly
> linked list) was common in Ada compilers or even was made the only
> practical by the standard.

Google gives a reference to the paper by Cyrille Comar & al on the
subject (ASCII/DOC/PS):

<http://adaic.org/docs/reports/comar/gnat/>

I believe that if you want to guarantee correct finalization in case
of object partial construction (ie: an exception occurs while an array
of controlled types is built), you need the linked list (doubly might
be for implementation convenience in the GNAT case) or at least
separate data to keep what needs to be cleaned up at a given point in
execution.

I don't know what C++ does guarantee here (or even if the problem
arises). Eg: you have a array of stuff with destructors, but while in
the middle of initializing your array, an exception occurs, what
happens? All elements including those uninitialized are destructed, or
only those initialized (and in reverse order of construction)? What
happens when you put a struct with destructors in a struct that
doesn't have them?

Of course, in all the cases wher such subtelties don't arise, an Ada
implementation can be efficient (but that probably means a lot of
headaches).

Quote:
> -- Jean-Marc, for who this space overhead currently reduce the
> usefullness of controlled types

Could you elaborate on your practical problems?

--



Fri, 13 Dec 2002 03:00:00 GMT  
 Sapce overhead of controlled types

Quote:

> For gnat, the space overhead of controlled types seems to be 3 words
> (1 as all other tagged types, and 2 to maintain a doubly linked list).
> As in C++ there is no space overhead (the equivalent are not necessarily
> "tagged" -- ie may have no virtual methods -- and implementations I've
> used generate code so that the linked list is not needed).  I was
> wondering if this implementation approach (putting objects on a doubly
> linked list) was common in Ada compilers or even was made the only
> practical by the standard.

I believe the Rational compiler avoids the linked-list overhead in the
usual cases.  All other compilers I know of use the linked-list
approach.  The language was designed to allow either approach.

- Bob



Fri, 13 Dec 2002 03:00:00 GMT  
 Sapce overhead of controlled types


Quote:

> > For gnat, the space overhead of controlled types seems to be 3 words
> > (1 as all other tagged types, and 2 to maintain a doubly linked
list).
> > As in C++ there is no space overhead (the equivalent are not
necessarily
> > "tagged" -- ie may have no virtual methods -- and implementations
I've
> > used generate code so that the linked list is not needed).  I was
> > wondering if this implementation approach (putting objects on a
doubly
> > linked list) was common in Ada compilers or even was made the only
> > practical by the standard.

> Google gives a reference to the paper by Cyrille Comar & al on the
> subject (ASCII/DOC/PS):

> <http://adaic.org/docs/reports/comar/gnat/>

Thanks, I'll have a look at it.  I wonder if it is not the same as
the one available from ACT.

Quote:
> I believe that if you want to guarantee correct finalization in case
> of object partial construction (ie: an exception occurs while an array
> of controlled types is built), you need the linked list (doubly might
> be for implementation convenience in the GNAT case) or at least
> separate data to keep what needs to be cleaned up at a given point in
> execution.

> I don't know what C++ does guarantee here (or even if the problem
> arises). Eg: you have a array of stuff with destructors, but while in
> the middle of initializing your array, an exception occurs, what
> happens? All elements including those uninitialized are destructed, or
> only those initialized (and in reverse order of construction)?

Second alternative: only objects whose constructor returned in the
normal way (IE not by an exception) are destroyed in the reverse
order of construction.

Quote:
> What
> happens when you put a struct with destructors in a struct that
> doesn't have them?

There is a default constructor created for it.  As a matter of fact,
every class (and struct is for this purpose a synonym of class) has
a constructor and a desctructor.

Quote:
> Of course, in all the cases wher such subtelties don't arise, an Ada
> implementation can be efficient (but that probably means a lot of
> headaches).

> > -- Jean-Marc, for who this space overhead currently reduce the
> > usefullness of controlled types

> Could you elaborate on your practical problems?

reference counted object pointers have an overhead of 12 bytes over a
bare access type.  As there are a lot of pointers to far fewer objects,
the overhead is significant.  I'll have to analyze to see if the
overhead remain acceptable or not but the analysis is needed.

-- Jean-Marc

Sent via Deja.com http://www.deja.com/
Before you buy.



Sat, 14 Dec 2002 03:00:00 GMT  
 Sapce overhead of controlled types

Quote:

> I believe that if you want to guarantee correct finalization in case
> of object partial construction (ie: an exception occurs while an array
> of controlled types is built), you need the linked list (doubly might
> be for implementation convenience in the GNAT case) or at least
> separate data to keep what needs to be cleaned up at a given point in
> execution.

You do not need extra per-object data for locals In the case of an
array, you need the index (or address) of the component currently being
initialized, so you can finalize just the ones that finished
initialization.  But this index is local to the code doing the
initialization, and it's needed anyway (how do you initialize an array
without looping through it?!).  For other types, you don't even need the
index.

On the other hand, always keeping a linked list makes the compiler
writer's life a lot simpler.

For heap data, you have to keep track of all the objects, which
more-or-less implies a doubly-linked list.

- Bob



Sat, 14 Dec 2002 03:00:00 GMT  
 Sapce overhead of controlled types

Quote:

> I don't know what C++ does guarantee here (or even if the problem
> arises). Eg: you have a array of stuff with destructors, but while in
> the middle of initializing your array, an exception occurs, what
> happens? All elements including those uninitialized are destructed, or
> only those initialized (and in reverse order of construction)? What
> happens when you put a struct with destructors in a struct that
> doesn't have them?

In C++, if an exception occurs partway through the construction of an
aggregate object, destructors are called in reverse order of
construction on all of the already constructed subobjects, and not on
any of the unconstructed ones. C++ has no concept of inheriting from a
special controlled type to get constructors and destructors.

I'm not aware of any C++ implementation that keeps track of what needs
to be destructed inside the objects themselves. A popular technique is
to maintain tables indexed by program counter location to keep track
of what needs to be destructed should an exception occur. Those tables
can be kept in separate memory segments and never even loaded unless
the exception actually happens, so that there is no runtime overhead
(except perhaps for missed opportunities for optimization) if an
exception does not occur.

As far as normal destruction goes, compilers just generate appropriate
code to accomplish this.



Sat, 14 Dec 2002 03:00:00 GMT  
 Sapce overhead of controlled types

Quote:
> For heap data, you have to keep track of all the objects, which
> more-or-less implies a doubly-linked list.

Why do the objects need to be tracked? Is there some point at which
Ada makes a heap-allocated controlled object go away by itself,
without the program explicitly requesting it?


Sat, 14 Dec 2002 03:00:00 GMT  
 Sapce overhead of controlled types

Quote:


> > For gnat, the space overhead of controlled types seems to be 3 words
> > (1 as all other tagged types, and 2 to maintain a doubly linked list).
> > As in C++ there is no space overhead (the equivalent are not necessarily
> > "tagged" -- ie may have no virtual methods -- and implementations I've
> > used generate code so that the linked list is not needed).  I was
> > wondering if this implementation approach (putting objects on a doubly
> > linked list) was common in Ada compilers or even was made the only
> > practical by the standard.

> I believe the Rational compiler avoids the linked-list overhead in the
> usual cases.  All other compilers I know of use the linked-list
> approach.  The language was designed to allow either approach.

The AverStar (AdaMagic) front end does not have a per-object space overhead,
but it does use a linked-list approach to keep track of what cleanup
actions need to be performed.  Generally there is one element on the
linked list per declaration, as opposed to one per controlled object.
This makes a difference when you declare an array of controlled components,
or a record with multiple controlled components.  If most of your declarations
involve individual controlled objects, then the space overhead is about
the same.  If most of your controlled objects are part of arrays or
records, then the space overhead would be less with the per-declaration
as opposed to per-object approach.

We handle partial construction by keeping track in the "cleanup record"
how far along the contruction has proceeded.

In the heap, because finalization must be performed when an access collection
is cleaned up, heap elements are on a doubly-linked list{*filter*} off
a cleanup record associated with the collection as a whole.  A single
heap element might contain multiple controlled objects, if it were
an array or record with muliple controlled components.

I think some C++ implementations use linked-lists in an analogous
way, at least for "static" contructors.

Quote:
> - Bob

--

Technical Director, Commercial Division, AverStar (formerly Intermetrics)
( http://www.*-*-*.com/ )  Burlington, MA  USA


Sat, 14 Dec 2002 03:00:00 GMT  
 Sapce overhead of controlled types

Quote:

> Why do the objects need to be tracked? Is there some point at which
> Ada makes a heap-allocated controlled object go away by itself,
> without the program explicitly requesting it?

Yes.  When the access type goes away, all remaining heap objects are
finalized.  That is, all objects created by allocators for that access
type, but not freed by Unchecked_Deallocation.  They get finalized (but
their storage is not (necessarily) reclaimed).

Since most access types are not nested within procedures, this usually
means that all remaining heap objects are finalized after the main
subprogram returns, but before the program terminates.

- Bob



Sun, 15 Dec 2002 03:00:00 GMT  
 Sapce overhead of controlled types

Quote:
> Yes.  When the access type goes away, all remaining heap objects are
> finalized.  That is, all objects created by allocators for that access
> type, but not freed by Unchecked_Deallocation.  They get finalized (but
> their storage is not (necessarily) reclaimed).

> Since most access types are not nested within procedures, this usually
> means that all remaining heap objects are finalized after the main
> subprogram returns, but before the program terminates.

Wasn't there a thread a while ago saying that controlled types could
be declared only at library level? If so, this would make your "most"
and "usually" be "all" and "always", yes?

Also, assuming controlled types can contain pointers to other
controlled objects, finalizers for such an object can continue to
explore the innards of an already finalized object. Is that right?
If so, then that means that their storage can not be reclaimed at
all, not just "not necessarily", as you stated, except perhaps
after all the finalizers have run.

Am I right about how all this works? It's different from C++, where
heap allocated objects have their detructors run only if they are
explicitly deleted. It also means that if you have a large linked
structure built of controlled types, you can't just throw it away
by exiting the program. Instead, each subobject must be finalized.



Sun, 15 Dec 2002 03:00:00 GMT  
 Sapce overhead of controlled types

Quote:

> Wasn't there a thread a while ago saying that controlled types could
> be declared only at library level? If so, this would make your "most"
> and "usually" be "all" and "always", yes?

No. The access type could be declared in an inner scope, despite the
controlled type having to be declared at the library level.

--
Jeff Carter
"I blow my nose on you."
Monty python & the Holy Grail



Sun, 15 Dec 2002 03:00:00 GMT  
 Sapce overhead of controlled types


Quote:
> Yes.  When the access type goes away, all remaining heap
objects are
> finalized.  That is, all objects created by allocators for
that access
> type, but not freed by Unchecked_Deallocation.  They get
finalized (but
> their storage is not (necessarily) reclaimed).

Note that a special case of this is that when the program ends,
all global controlled objects on the heap are finalized.

Since most finalization is only for the purposes of freeing
storage this is pretty silly, which is why GNAT introduced
the pragma Finalize_Storage_Only. In the case of JGNAT, this
pragma is useful for local types as well if the JVM takes
care of storage reclamation sufficiently completely.

Sent via Deja.com http://www.deja.com/
Before you buy.



Mon, 16 Dec 2002 03:00:00 GMT  
 Sapce overhead of controlled types

Quote:

> Wasn't there a thread a while ago saying that controlled types could
> be declared only at library level? If so, this would make your "most"
> and "usually" be "all" and "always", yes?

Jeff Carter answered that.

Quote:
> Also, assuming controlled types can contain pointers to other
> controlled objects, finalizers for such an object can continue to
> explore the innards of an already finalized object. Is that right?

Right.

Quote:
> If so, then that means that their storage can not be reclaimed at
> all, not just "not necessarily", as you stated, except perhaps
> after all the finalizers have run.

Right.  I think there are some compilers that will reclaim the storage
for a local collection.  You are correct that finalization of all
objects has to happen first.  Similarly, for stack objects, you have to
finalize all the objects in a procedure before deallocating the stack
frame.

Quote:
> Am I right about how all this works? It's different from C++, where
> heap allocated objects have their detructors run only if they are
> explicitly deleted. It also means that if you have a large linked
> structure built of controlled types, you can't just throw it away
> by exiting the program. Instead, each subobject must be finalized.

That's right.  Some compilers allow to get the C++ semantics by giving a
pragma.  That's what you want when finalization is just deallocating
storage -- you're about to exit the program anyway, so it's a waste of
time.

- Bob



Mon, 16 Dec 2002 03:00:00 GMT  
 
 [ 13 post ] 

 Relevant Pages 

1. Update of OPC-Controls produce heavy overhead

2. Explorer type control exists.

3. Changing control type

4. Windows XP and Clarion RTF control (type anything and program exits)

5. Control types for window/report

6. What type of control is it?

7. Reference behaviour of strictly typed controls

8. Number data-types: Control and meta combinations

9. Legality: formal packages with controlled types

10. Tasking and Controlled types in GNAT

11. controlled type in generic package?

12. What is wrong here? (Generic and controlled types)

 

 
Powered by phpBB® Forum Software