Amount of copying on returned constant objects

Amount of copying on returned constant objects

[Alex R. Mosteo]

Hello,

before I go digging into assembler listings I'd like to ask here in case
someone has the answer ready.

I know that some "in" arguments may be passed as copies or as references, at
compiler discretion (this is one of these things that "programmers
shouldn't care about", many times quoted).

I wonder however about results of functions, that are not modified. Look for
example at the Element function of the new Ada.Containers. They return the
stored item, that may well be a quite large controlled tagged type, for
example.

Now, many times I want to query an element just for read-only purposes. I'm
faced with two options:

1) Just call Element on the container Key/Index, and be done with it.

2) Do a Find+Query_Element, which requires defining an extra procedure and
somewhat breaks the flow of control, but ensures no copying.

I tend to go with 1) because of laziness and the "no premature optimization"
rule. In C++ I could use constant references. Now, I wonder if 

a) is there something in the ARM that prevents an equivalent transparent
optimization in the Ada side (returning the reference when it is detected
that the returned object is not modified)?

b) If not, do you know of compilers that do this in practice? (Specially
interesting for me would be GNAT at -O2/-O3).

Failing these, I guess I could define constant accesses for use in my own
functions, but I find this not very Ada-like. Any other ideas?

Thanks in advance, have a nice week-end.

Re: Amount of copying on returned constant objects

[Ludovic Brenta]

"Alex R. Mosteo" <devnull@mailinator.com> writes:
> Hello,
>
> before I go digging into assembler listings I'd like to ask here in case
> someone has the answer ready.
>
> I know that some "in" arguments may be passed as copies or as references, at
> compiler discretion (this is one of these things that "programmers
> shouldn't care about", many times quoted).
>
> I wonder however about results of functions, that are not modified. Look for
> example at the Element function of the new Ada.Containers. They return the
> stored item, that may well be a quite large controlled tagged type, for
> example.

The "compiler discretion" does not apply to all cases. The compiler is
required to pass parameters of limited and tagged types by reference.
I'm not entirely sure that that also applies to the result of a
function call, but that would seem reasonable.  If the function
returns a class-wide or other unconstrained type, then the object will
have to be on the heap (in the region GNAT calls the "secondary
stack").

> Now, many times I want to query an element just for read-only purposes. I'm
> faced with two options:
>
> 1) Just call Element on the container Key/Index, and be done with it.

That would be my approach.

> 2) Do a Find+Query_Element, which requires defining an extra procedure and
> somewhat breaks the flow of control, but ensures no copying.
>
> I tend to go with 1) because of laziness and the "no premature optimization"
> rule. In C++ I could use constant references. Now, I wonder if 
>
> a) is there something in the ARM that prevents an equivalent transparent
> optimization in the Ada side (returning the reference when it is detected
> that the returned object is not modified)?
> 
> b) If not, do you know of compilers that do this in practice? (Specially
> interesting for me would be GNAT at -O2/-O3).

If you investigate GNAT, could you please post your findings here?

> Failing these, I guess I could define constant accesses for use in my own
> functions, but I find this not very Ada-like. Any other ideas?

-- 
Ludovic Brenta.

Re: Amount of copying on returned constant objects

[Alex R. Mosteo]

Ludovic Brenta wrote:

> If you investigate GNAT, could you please post your findings here?

I'll do, but I'm not sure if I will do this anytime soon :/

Re: Amount of copying on returned constant objects

[Alex R. Mosteo]

Alex R. Mosteo wrote:

> Ludovic Brenta wrote:
> 
>> If you investigate GNAT, could you please post your findings here?
> 
> I'll do, but I'm not sure if I will do this anytime soon :/

I tried a bit last night, with a quick and dirty test program. There's no
such optimization for GNAT GPL 2007 with -O2/-O3. I don't know about more
esoteric optimization switches.

I was going to paste this code but it has vanished from my /tmp folder
(silly me) after boot. Oh well, perhaps I'll rewrite it. 

Re: Amount of copying on returned constant objects

[Georg Bauhaus]

Alex R. Mosteo wrote:
> 
> 
> I wonder however about results of functions, that are not modified.
> 
> ... In C++ I could use constant references. Now, I wonder if 
> 
> a) is there something in the ARM that prevents an equivalent transparent
> optimization in the Ada side (returning the reference when it is detected
> that the returned object is not modified)?

OTOH, I might want a constant copy because the object in the
container is going to be modified... Can a compiler detect this?



-- Georg

Re: Amount of copying on returned constant objects

[Alex R. Mosteo]

Georg Bauhaus wrote:

> Alex R. Mosteo wrote:
>> 
>> 
>> I wonder however about results of functions, that are not modified.
>> 
>> ... In C++ I could use constant references. Now, I wonder if
>> 
>> a) is there something in the ARM that prevents an equivalent transparent
>> optimization in the Ada side (returning the reference when it is detected
>> that the returned object is not modified)?
> 
> OTOH, I might want a constant copy because the object in the
> container is going to be modified... Can a compiler detect this?

I don't think it can, at least easily. I guess that if you're keeping a
copy, constant or not, the optimization opportunity is lost. But what about
short-lived objects, like...

if Container.Element ("key").Is_Nice then -- Container for some tagged type
  ...
end if;

This is the kind of copies that I see interesting to optimize away. I don't
know enough about compilers to say if it is reasonable to expect one to
detect this situation or not.

If not, one possibility would be to have

function Element (Key : Key_Type) return Element_Type;

and

type Constant_Access is access constant Element_Type;
function Element (Key : Key_Type) return Constant_Access;

but I'm not sure about the amount of ambiguities one would get in that case.
In any case this does not exist in the standard 05 containers.

Re: Amount of copying on returned constant objects

[Pascal Obry]

Alex R. Mosteo a �crit :
> type Constant_Access is access constant Element_Type;
> function Element (Key : Key_Type) return Constant_Access;

Or in a more Ada 2005 way:

   function Element
     (Key : Key_Type) return access constant Element_Type;

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: Amount of copying on returned constant objects

[Alex R. Mosteo]

Pascal Obry wrote:

> Alex R. Mosteo a écrit :
>> type Constant_Access is access constant Element_Type;
>> function Element (Key : Key_Type) return Constant_Access;
> 
> Or in a more Ada 2005 way:
> 
>    function Element
>      (Key : Key_Type) return access constant Element_Type;
> 
> Pascal.

Certainly. I thought that constant wasn't appliable to anonymous accesses in
function results (for no special reason on my part).

Re: Amount of copying on returned constant objects

[Randy Brukardt]

"Pascal Obry" <pascal@obry.net> wrote in message
news:4676C27D.2050608@obry.net...
> Or in a more Ada 2005 way:
>
>    function Element
>      (Key : Key_Type) return access constant Element_Type;

The problem with this is that this access can be saved, and any operation on
the original container could make it become dangling (and thus any further
use be erroneous). That is *very* unsafe and virtually impossible to detect.

There were a substantial number of people (a group that includes me) that
want the containers to be safer than using raw access types (because they
can do checks that would be too tedious to do in hand-written code). That's
why the containers access-in-place routines use access-to-subprograms,
because they can have tampering checks that prevent the dangling access
problem (you get Program_Error if you try to do something that could make
the element inaccessible). That makes them much safer than returning a raw
pointer.

We actually spent quite a bit of effort on trying to find a way to secure
access values returned this way. But it isn't quite possible: even if you
make them uncopyable; they still can be held onto long enough to potentially
cause trouble with a renames.

What really would help would be a way for the container to know when the
access was destroyed, but there isn't any obvious way to do that in Ada.

Dmitry might (will?) tell us that a user-defined ".all" operation would do
the trick, but it's not obvious how to define that operation so that the
".all" definition itself would not expose the original problem.

                            Randy.

Re: Amount of copying on returned constant objects

[Dmitry A. Kazakov]

On Mon, 18 Jun 2007 15:25:33 -0500, Randy Brukardt wrote:

> "Pascal Obry" <pascal@obry.net> wrote in message
> news:4676C27D.2050608@obry.net...

>> Or in a more Ada 2005 way:
>>
>>    function Element
>>      (Key : Key_Type) return access constant Element_Type;
> 
> That's
> why the containers access-in-place routines use access-to-subprograms,
> because they can have tampering checks that prevent the dangling access
> problem (you get Program_Error if you try to do something that could make
> the element inaccessible). That makes them much safer than returning a raw
> pointer.

In Ada, which has no procedural types closure itself is a problem because
an access type is still there (now to the procedure). Further, this
approach does not work if we needed to access several elements of the same
or different containers. How to do this:

   (Get (A, First (A)) + Get (A, Last (A))) / 2;

with closures in a more or less readable form?

> Dmitry might (will?) tell us that a user-defined ".all" operation would do
> the trick, but it's not obvious how to define that operation so that the
> ".all" definition itself would not expose the original problem.

Well, for all, there is a problem of complexity introduced by each new type
here. There is a type of the container, there are types of the element and
the index. That's already triply dispatching in the most general case.
[Actually, it is far more if ranges and other subsets of index are
introduced] I don't want yet another type of the access to element, or a
type of the procedure to access to the element etc. It is a mess when the
container gets derived from. We have no any language mechanism to bind all
these geometrically exploding combinations of types together.

BTW, which problem we are talking about. There are at least two:

1. An "easy" one is Alex's example:

   if Container.Element (Key).Is_Nice then

What he actually needs here is to force the compiler to infer from
Element's Is_Nice a new container operation:

   if Is_Nice (Container, Key) then

composed out of container's Element and element's Is_Nice.

2. A difficult one:

   declare
      X : Item renames Get (Container, Key_1);
      Y : Item renames Get (Container, Key_2);
   begin
      Remove (Container, From => Key_3, To => Key_4);
      X := Y;
   end; -- This must be safe and efficient

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

Re: Amount of copying on returned constant objects

[Alex R. Mosteo]

Randy Brukardt wrote:

> "Pascal Obry" <pascal@obry.net> wrote in message
> news:4676C27D.2050608@obry.net...
>> Or in a more Ada 2005 way:
>>
>>    function Element
>>      (Key : Key_Type) return access constant Element_Type;
> 
> The problem with this is that this access can be saved, and any operation
> on the original container could make it become dangling (and thus any
> further use be erroneous). That is *very* unsafe and virtually impossible
> to detect.

I see. I suspected that would be the reason for its absence. 

> There were a substantial number of people (a group that includes me) that
> want the containers to be safer than using raw access types (because they
> can do checks that would be too tedious to do in hand-written code).
> That's why the containers access-in-place routines use
> access-to-subprograms, because they can have tampering checks that prevent
> the dangling access problem (you get Program_Error if you try to do
> something that could make the element inaccessible). That makes them much
> safer than returning a raw pointer.

Actually I have benefitted from these sanity checks in real code. Too bad we
can have both things...

> We actually spent quite a bit of effort on trying to find a way to secure
> access values returned this way. But it isn't quite possible: even if you
> make them uncopyable; they still can be held onto long enough to
> potentially cause trouble with a renames.
> 
> What really would help would be a way for the container to know when the
> access was destroyed, but there isn't any obvious way to do that in Ada.

I guess then that some reference counting companion type (or maybe making
Cursors tagged and more heavyweight) was discarded because the distributed
overhead?

Re: Amount of copying on returned constant objects

[Randy Brukardt]

"Alex R. Mosteo" <devnull@mailinator.com> wrote in message
news:5dpp8pF35116bU1@mid.individual.net...
> Randy Brukardt wrote:
...
> > What really would help would be a way for the container to know when the
> > access was destroyed, but there isn't any obvious way to do that in Ada.
>
> I guess then that some reference counting companion type (or maybe making
> Cursors tagged and more heavyweight) was discarded because the distributed
> overhead?

Cursors can be tagged if the implementation so choses, but that doesn't have
an effect on the element access problem. For that you need something that
allows direct dereferencing, and in Ada as it stands, that can only be an
access type.

Having a companion type would work if it was impossible to separate the
access from the reference counter. But there is no way in Ada to have a
visible access type that cannot be assigned out of its surrounding wrapper.
(Which is why I said that Dmitry would say that redefinition of ".all" for a
private type could solve the problem.)

                       Randy.

Re: Amount of copying on returned constant objects

[Markus E Leypold]

> "Alex R. Mosteo" <devnull@mailinator.com> wrote in message
> news:5dpp8pF35116bU1@mid.individual.net...
>> Randy Brukardt wrote:
> ...
>> > What really would help would be a way for the container to know when the
>> > access was destroyed, but there isn't any obvious way to do that in Ada.
>>
>> I guess then that some reference counting companion type (or maybe making
>> Cursors tagged and more heavyweight) was discarded because the distributed
>> overhead?
>
> Cursors can be tagged if the implementation so choses, but that doesn't have
> an effect on the element access problem. For that you need something that
> allows direct dereferencing, and in Ada as it stands, that can only be an
> access type.

I wonder wether you can't hide the dereferencing. I had a similar
Problem some time ago when implementing a cache of (rather large)
objects, but didn't want to make copies of every object when iterating
over them (i.e. for sorting or filtering purposes). My solution was to
have a generic function "Iterate" which is instantiated with the cache
and a function "operation" that will be doing the work on the
elemens. The elements are passed to operation (in this case) as 'in'
parameters, so 'operation' will not be able to change the elements,
only read them.

I wonder wether container implementations couldn't use a similar
trick: Instead of dereferencing a "do_with" generic would take an
operation as a parameter to which in turn the elements are passed
(control passes to do_with, do_with dereferences and passes elements
to operation).

This doesn't avoid the problem of cursors that become invalid. The
solution I see there would be to avoid cursors altogether and use
generic traversal and iteration functors like fold() for lists. This
way position is never made explicit and cannot be saved into a
variable.


>
> Having a companion type would work if it was impossible to separate
>the access from the reference counter. But there is no way in Ada to
>have a visible access type that cannot be assigned out of its
>surrounding wrapper.  (Which is why I said that Dmitry would say that
>redefinition of ".all" for a private type could solve the problem.)
>

What about a tagged type that is the abstraction of a storage cell
with method like Get(), Set() and Pass_Me_the_Data()? 

I've not thought much about the details, but that should cover the
most common use cases.

Regards -- Markus

Re: Amount of copying on returned constant objects

[Georg Bauhaus]

Markus E Leypold wrote:
>>
> I wonder wether container implementations couldn't use a similar
> trick: Instead of dereferencing a "do_with" generic would take an
> operation as a parameter to which in turn the elements are passed
> (control passes to do_with, do_with dereferences and passes elements
> to operation).

Query_element and Update_Element take a procedure parameter
for this very reason, IIUC.

Re: Amount of copying on returned constant objects

[Markus E Leypold]

> Markus E Leypold wrote:
>>>
>> I wonder wether container implementations couldn't use a similar
>> trick: Instead of dereferencing a "do_with" generic would take an
>> operation as a parameter to which in turn the elements are passed
>> (control passes to do_with, do_with dereferences and passes elements
>> to operation).
>
> Query_element and Update_Element take a procedure parameter
> for this very reason, IIUC.

Yes, thanks.

Regards -- Markus

Re: Amount of copying on returned constant objects

[Dmitry A. Kazakov]

On Tue, 19 Jun 2007 16:33:26 -0500, Randy Brukardt wrote:

> "Alex R. Mosteo" <devnull@mailinator.com> wrote in message
> news:5dpp8pF35116bU1@mid.individual.net...
>> Randy Brukardt wrote:
> ...
>>> What really would help would be a way for the container to know when the
>>> access was destroyed, but there isn't any obvious way to do that in Ada.
>>
>> I guess then that some reference counting companion type (or maybe making
>> Cursors tagged and more heavyweight) was discarded because the distributed
>> overhead?
> 
> Cursors can be tagged if the implementation so choses, but that doesn't have
> an effect on the element access problem. For that you need something that
> allows direct dereferencing, and in Ada as it stands, that can only be an
> access type.
> 
> Having a companion type would work if it was impossible to separate the
> access from the reference counter. But there is no way in Ada to have a
> visible access type that cannot be assigned out of its surrounding wrapper.
> (Which is why I said that Dmitry would say that redefinition of ".all" for a
> private type could solve the problem.)

Actually it would be only a half of the solution. The access type for which
.all gets overridden is an implementation of the cursor. The public view
of, should be a derived type of Element:

                      --- This is far not Ada!
   type Cursor is new Element with private;
      -- I can do with a Cursor anything I could do with an Element

   function Get (Collection : Container, What : Key) return Cursor;
      -- Factory

private
   type Cursor is access Element with interface Element;
      -- Privately Cursor is an access type that implements the interface
      -- of Element. It could be also a fat record rather than access, with
      -- a reference to the container and an index within. Whatever, it
      -- cannot be seen from outside.

   function Is_Nice (Item : Cursor) return Boolean;
      -- Implementation of Element's interface by Cursor

   --  + Getter/Setter, of course

Here the referential nature of Cursor is hidden and Cursor is a full
substitute of Element

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

Re: Amount of copying on returned constant objects

[Georg Bauhaus]

On Mon, 2007-06-18 at 20:23 +0300, Alex R. Mosteo wrote:


> type Constant_Access is access constant Element_Type;
> function Element (Key : Key_Type) return Constant_Access;

IIRC, a similar idea was in one of Matt's proposals.

Re: Amount of copying on returned constant objects

[Dmitry A. Kazakov]

On Fri, 15 Jun 2007 19:19:00 +0300, Alex R. Mosteo wrote:

> I know that some "in" arguments may be passed as copies or as references, at
> compiler discretion (this is one of these things that "programmers
> shouldn't care about", many times quoted).
> 
> I wonder however about results of functions, that are not modified. Look for
> example at the Element function of the new Ada.Containers. They return the
> stored item, that may well be a quite large controlled tagged type, for
> example.
> 
> Now, many times I want to query an element just for read-only purposes. I'm
> faced with two options:
> 
> 1) Just call Element on the container Key/Index, and be done with it.
> 
> 2) Do a Find+Query_Element, which requires defining an extra procedure and
> somewhat breaks the flow of control, but ensures no copying.
> 
> I tend to go with 1) because of laziness and the "no premature optimization"
> rule. In C++ I could use constant references. Now, I wonder if 
> 
> a) is there something in the ARM that prevents an equivalent transparent
> optimization in the Ada side (returning the reference when it is detected
> that the returned object is not modified)?

No [*], but a way to help the compiler to know what you wanted is:

   declare
      Item : Element renames Get (Collection, Key);
                 -- Please, don't make new objects, if you can
   begin
      ... -- Use Item

> Thanks in advance, have a nice week-end.

Same to you.

---------------
* In Ada 95 there were limited types returned strictly by reference, but
this semantics was crapped in Ada 2005.

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

Re: Amount of copying on returned constant objects

[Alex R. Mosteo]

Dmitry A. Kazakov wrote:

> On Fri, 15 Jun 2007 19:19:00 +0300, Alex R. Mosteo wrote:

>> a) is there something in the ARM that prevents an equivalent transparent
>> optimization in the Ada side (returning the reference when it is detected
>> that the returned object is not modified)?
> 
> No [*], but a way to help the compiler to know what you wanted is:
> 
>    declare
>       Item : Element renames Get (Collection, Key);
>                  -- Please, don't make new objects, if you can
>    begin
>       ... -- Use Item

And this gives me another question: is there any guarantee that renaming
will avoid multiple calls, or implementation advice in this direction? I've
tried to quickly find the answer in 8.5.4 but I guess I'm not specially
suited for ARM reading today, since I don't see it clearly.