Problem in "X (1).Re := X (1).Re + 1"

Problem in "X (1).Re := X (1).Re + 1"

[ytomino]

This is a thought experiment.

First, in RM 4.1.6:

* when the generalized_indexing is used within a primary where a name denoting a constant is permitted.

This means

declare
   package V is new Vectors (Complex);
   X : V.Vector;
begin
   X (1).Re := X (1).Re + 1;
end;

is interpreted as

declare
   package V is new Vectors (Complex);
   X : V.Vector;
begin
   Reference (X, 1).Element.all.Re := Constant_Reference (X, 1).Element.all.Re + 1;
end;

Is this OK?

If this is the truth, and if Vectors is implemented by reference-counting.
(I don't know copy-on-write is permitted in Ada.Containers.Vectors. Otherwise, please assume my original container like Vectors.)

Well then...
May a next eval-order problem be caused or not?

1. eval "Constant_Reference (X, 1)" => get an accessor pointing to shared data. (reference counter > 1)
2. eval "Reference (X, 1)" => do copy-on-write, and get an accessor pointing to new unshared data.
3. eval ".Element.all.Re" in right side => access *old* shared data. <- !!!!
4. eval ".Element.all.Re" in left side => access new data.
5. eval + 1 => calculate old data + 1.
6. eval assignment => store the result into new data.

(Real compiler usually does not generate the strange order such as this. But "arbitrary order" is spelled out in RM 5.2.)

Of course, the result is same if shared data is alive.
However, on the worst case, the other task can deallocate shared data during from 1 to 3. Or, if the element type is controlled type or havs access value.

What do you think?

Thanks.

Re: Problem in "X (1).Re := X (1).Re + 1"

[Adam Beneschan]

On Saturday, May 5, 2012 5:55:39 AM UTC-7, ytomino wrote:
> This is a thought experiment.
> 
> First, in RM 4.1.6:
> 
> * when the generalized_indexing is used within a primary where a name denoting a constant is permitted.
> 
> This means
> 
> declare
>    package V is new Vectors (Complex);
>    X : V.Vector;
> begin
>    X (1).Re := X (1).Re + 1;
> end;
> 
> is interpreted as
> 
> declare
>    package V is new Vectors (Complex);
>    X : V.Vector;
> begin
>    Reference (X, 1).Element.all.Re := Constant_Reference (X, 1).Element.all.Re + 1;
> end;
> 
> Is this OK?

No.  But if you change the 1 to 1.0 then I think it will be OK.

> 
> If this is the truth, and if Vectors is implemented by reference-counting.
> (I don't know copy-on-write is permitted in Ada.Containers.Vectors. Otherwise, please assume my original container like Vectors.)
> 
> Well then...
> May a next eval-order problem be caused or not?
> 
> 1. eval "Constant_Reference (X, 1)" => get an accessor pointing to shared data. (reference counter > 1)
> 2. eval "Reference (X, 1)" => do copy-on-write, and get an accessor pointing to new unshared data.
> 3. eval ".Element.all.Re" in right side => access *old* shared data. <- !!!!
> 4. eval ".Element.all.Re" in left side => access new data.
> 5. eval + 1 => calculate old data + 1.
> 6. eval assignment => store the result into new data.

I'm not yet really familiar with the ins and outs of user-defined references and user-defined indexing.  But my guess is that the phrase in A.18.2(147.17) that says "Reference returns an object whose discriminant is an access value that designates the element designated by Position" means that Reference can't return an object whose discriminant designates a *copy* of the element.  If I understand your question correctly, this means that the scenario you're concerned about can't happen.

But, as I said, I'm not completely familiar with all the issues involved.

                       -- Adam

Re: Problem in "X (1).Re := X (1).Re + 1"

[ytomino]

On Tuesday, May 8, 2012 12:37:44 AM UTC+9, Adam Beneschan wrote:
> 
> No.  But if you change the 1 to 1.0 then I think it will be OK.

Oops!
1.0 is correct.

> I'm not yet really familiar with the ins and outs of user-defined references
> and user-defined indexing.  But my guess is that the phrase in A.18.2(147.17)
> that says "Reference returns an object whose discriminant is an access value
> that designates the element designated by Position" means that Reference
> can't return an object whose discriminant designates a *copy* of the element.
> If I understand your question correctly, this means that the scenario you're
> concerned about can't happen.

Imagine an implementation of an reference-counted container.
Probably, it's like below:

function Reference (Container : Vector; Position : Cursor) return Ref_Type is
begin
   --  if data is shared, do copy-on-write to prepare for change
   --  (memory management and exclusive control is omitted in this pseudo-code)
   if Container.Data_Block.Ref_Count > 1 then
      Container.Data_Block.Ref_Count := Container.Data_Block.Ref_Count - 1;
      Container.Data_Block := new Data_Block_Type'(
         Length => Container.Data_Block.Length,
         Elements => (1 .. Length => Container.Data_Block.Elements (1 .. Length)),
         Ref_Count => 1);
   end if;
   -- return access value designated by Position
   return (Element => Container.Data_Block.Elements (To_Index (Cursor))'Access);
end Reference;

And, similar copy-on-write is inserted into Replace_Element and Update_Element.

In this container, Reference copies its elements as your saying. But the container comes to own copied elements, and Reference returns an access value that designates the element in same area. I hope that this is allowed for effective implementations.
Besides, if this is disallowed in Ada.Containers.Vectors, please assume my original container.
Surely you don't think that all reference-counted containers written by user are forbidden to implement user-defined indexing.

Re: Problem in "X (1).Re := X (1).Re + 1"

[Adam Beneschan]

On Monday, May 7, 2012 11:53:58 AM UTC-7, ytomino wrote:
> On Tuesday, May 8, 2012 12:37:44 AM UTC+9, Adam Beneschan wrote:
> > 
> > No.  But if you change the 1 to 1.0 then I think it will be OK.
> 
> Oops!
> 1.0 is correct.
> 
> > I'm not yet really familiar with the ins and outs of user-defined references
> > and user-defined indexing.  But my guess is that the phrase in A.18.2(147.17)
> > that says "Reference returns an object whose discriminant is an access value
> > that designates the element designated by Position" means that Reference
> > can't return an object whose discriminant designates a *copy* of the element.
> > If I understand your question correctly, this means that the scenario you're
> > concerned about can't happen.
> 
> Imagine an implementation of an reference-counted container.
> Probably, it's like below:
> 
> function Reference (Container : Vector; Position : Cursor) return Ref_Type is
> begin
>    --  if data is shared, do copy-on-write to prepare for change
>    --  (memory management and exclusive control is omitted in this pseudo-code)
>    if Container.Data_Block.Ref_Count > 1 then
>       Container.Data_Block.Ref_Count := Container.Data_Block.Ref_Count - 1;
>       Container.Data_Block := new Data_Block_Type'(
>          Length => Container.Data_Block.Length,
>          Elements => (1 .. Length => Container.Data_Block.Elements (1 .. Length)),
>          Ref_Count => 1);
>    end if;
>    -- return access value designated by Position
>    return (Element => Container.Data_Block.Elements (To_Index (Cursor))'Access);
> end Reference;
> 
> And, similar copy-on-write is inserted into Replace_Element and Update_Element.
> 
> In this container, Reference copies its elements as your saying. But the container comes to own copied elements, and Reference returns an access value that designates the element in same area. I hope that this is allowed for effective implementations.
> Besides, if this is disallowed in Ada.Containers.Vectors, please assume my original container.
> Surely you don't think that all reference-counted containers written by user are forbidden to implement user-defined indexing.

OK, I think I figured out what you were talking about.  Sorry, but your original post seemed to use a few words (like "implemented by reference-counting") and expect that readers would fill in the rest of the details.  Unfortunately, I'm not a mind-reader, so it took me a lot of effort to figure it out.  Maybe others here are better mind-readers than I am.  I don't know.

But I'm guessing that you're referring to an implementation where, when a copy of an element is made, the implementation doesn't make a copy immediately, but rather waits until somebody tries to modify either the original or the copy and *then* splits off a copy.  So in your example:

  X(1).Re := X(1).Re + 1.0;

you're assuming that X(1) was earlier created as a copy of something else--or that something else was created as a copy of X(1).  The main ways I can see that this could be done are by using the Copy or Assign operations of vectors, e.g.

  X := Copy(W);
  X(1).Re := X(1).Re + 1.0;

so that when X is created, it's done by creating references to all the elements in W rather than by copying the elements of W; and then making a new copy of an individual element when it needs to be modified.  Of course, it's silly to do this if the element type is Complex, since it's surely easier to copy two floats than to implement all the overhead needed to deal with references.  But I can imagine that it might make sense if the element type is ... um, more complex than Complex.  Or a whole lot bigger.

I'm still dubious that it can work, though.  Consider:

  X := V.Copy(W);                        -- (A)
  Ref1 := V.Constant_Reference (W, 1);   -- (B)
  Ref2 := V.Constant_Reference (X, 1);   -- (C)
  X(1).Re := X(1).Re + 1.0;              -- (D)

If the Copy function did not create any new copies of elements, then Ref1.Element and Ref2.Element will end up being accesses to the same element, after (C) is performed.  If the new copy of the element is not created until Reference is evaluated by the left side of statement (D), the result is that either Ref2.Element (or possibly Ref1.Element) will be pointing at the wrong thing.  

So it looks to me like the method you suggest shouldn't be allowed, even in your own container, since it would make it impossible to implement Constant_Reference  correctly.

My caveat still applies, though; this involves issues that I'm not yet completely familiar with, so it's possible that I made a serious error.  I'm hoping someone will come to my rescue if I did ... :)

                        -- Adam

Re: Problem in "X (1).Re := X (1).Re + 1"

[Randy Brukardt]

"Adam Beneschan" <adam@irvine.com> wrote in message 
news:10294366.7.1336426132700.JavaMail.geo-discussion-forums@yngg23...
On Monday, May 7, 2012 11:53:58 AM UTC-7, ytomino wrote:
> On Tuesday, May 8, 2012 12:37:44 AM UTC+9, Adam Beneschan wrote:
...
>So it looks to me like the method you suggest shouldn't be allowed, even in 
>your own container,
> since it would make it impossible to implement Constant_Reference 
> correctly.

It seems to me that his implementation is wrong, since Constant_Reference 
creates a reference, so it should be impossible for something else to 
"deallocate" the reference at the same time. (I'm talking about in a 
hand-created container,  I don't think this implementation would be 
legitimate for Vectors - although I'm not certain). That probably means that 
Constant_Reference would have to increase the reference count when it is 
created and decrease it when it is destroyed (specifically the reason why 
these return record types with discriminants rather than just a bare access 
value). If that's done, his original example is fine.

I'm pretty sure reference counting will work as an implementation using 
generalized indexing, but it is pretty complicated (as it always is). But I 
haven't actually tried this in practice, so I could be wrong...

                                   Randy.

Re: Problem in "X (1).Re := X (1).Re + 1"

[Adam Beneschan]

On Monday, May 7, 2012 6:14:42 PM UTC-7, Randy Brukardt wrote:
> "Adam Beneschan" wrote in message 
> news:10294366.7.1336426132700.JavaMail.geo-discussion-forums@yngg23...
> On Monday, May 7, 2012 11:53:58 AM UTC-7, ytomino wrote:
> > On Tuesday, May 8, 2012 12:37:44 AM UTC+9, Adam Beneschan wrote:
> ...
> >So it looks to me like the method you suggest shouldn't be allowed, even in 
> >your own container,
> > since it would make it impossible to implement Constant_Reference 
> > correctly.
> 
> It seems to me that his implementation is wrong, since Constant_Reference 
> creates a reference, so it should be impossible for something else to 
> "deallocate" the reference at the same time. (I'm talking about in a 
> hand-created container,  I don't think this implementation would be 
> legitimate for Vectors - although I'm not certain). That probably means that 
> Constant_Reference would have to increase the reference count when it is 
> created and decrease it when it is destroyed (specifically the reason why 
> these return record types with discriminants rather than just a bare access 
> value). If that's done, his original example is fine.

I'm not so sure.  If I understand the issue correctly, the problem isn't deallocation.  The problem occurs when two separate vector elements (whether they are elements of different vectors or of the same vector) share the same location temporarily; but later, the location of one of them moves, so that they no longer share the same location.  When that happens, any Constant_Reference that was previously applied to the element that has moved is no longer valid.  I don't see how having Constant_Reference increase a reference count solves the problem. (It would prevent a deallocation, but I think this is a problem that occurs before there is any deallocation.)  I may be misunderstanding what the OP is trying to accomplish; my understanding is based on the term "copy-on-write", but he didn't provide any details, and I had to look up what it meant since I wasn't familiar with the term.  Anyway, I think that a user-defined container would have the same problem as the language-defined container.  (It seems like, for a user-defined container, making Constant_Reference private would help.  Then it could still be used for user-defined indexing operations, while, I think, preventing callers from creating Constant_Reference_Type objects that could still exist when the elements that they refer to are relocated.)

In fact, looking into this further, I think there's a problem with the AARM in this regard.  A.18.2(254.a), which was from Ada 2005, says "an implementation that avoided copying until one of the containers is modified would be allowed".  It seems to me that this is no longer true.  I'm going to send something to Ada-Comment about this.

                           -- Adam

Re: Problem in "X (1).Re := X (1).Re + 1"

[Randy Brukardt]

"Adam Beneschan" <adam@irvine.com> wrote in message 
news:5209872.2691.1336497260879.JavaMail.geo-discussion-forums@ynlq12...
...
>In fact, looking into this further, I think there's a problem with the AARM 
>in this regard.
>A.18.2(254.a), which was from Ada 2005, says "an implementation that 
>avoided copying
>until one of the containers is modified would be allowed".  It seems to me 
>that this is no longer
>true.  I'm going to send something to Ada-Comment about this.

I think it is true, it's just that creating a reference (or for that matter, 
calling Query_Element) has to be dealt with specially; they're both somewhat 
like modifying an element. Query_Element is a bit less of a problem as most 
ways (but not all) to modify the container while the call is active are 
invalid. But it seems that the same problems can come up for it.

(Note that a copy-on-write implementation is not a good idea for the 
standard containers for other reasons as well, the main one being that the 
usual uses don't create many copies, so having overhead for that can't be 
justified. But it should be possible to create a container with that 
semantics.)

                      Randy.

Re: Problem in "X (1).Re := X (1).Re + 1"

[ytomino]

On Tuesday, May 8, 2012 6:28:52 AM UTC+9, Adam Beneschan wrote:
> 
> OK, I think I figured out what you were talking about.  Sorry, but your
> original post seemed to use a few words (like "implemented by
> reference-counting") and expect that readers would fill in the rest of the
> details.  Unfortunately, I'm not a mind-reader, so it took me a lot of effort
> to figure it out.  Maybe others here are better mind-readers than I am.
> I don't know.

Uh... I'm sorry your time.

> But I'm guessing that you're referring to an implementation where, when
> a copy of an element is made, the implementation doesn't make a copy
> immediately, but rather waits until somebody tries to modify either the 
> original or the copy and *then* splits off a copy.  So in your example:
> 
>   X(1).Re := X(1).Re + 1.0;
> 
> you're assuming that X(1) was earlier created as a copy of something else--or
> that something else was created as a copy of X(1).  The main ways I can see
> that this could be done are by using the Copy or Assign operations of
> vectors, e.g.
> 
>   X := Copy(W);
>   X(1).Re := X(1).Re + 1.0;

Yes. I had to write something that increases the reference counter of X happened before the subject line.
My omission about this issue was very bad.

> so that when X is created, it's done by creating references to all the
> elements in W rather than by copying the elements of W; and then making a new
> copy of an individual element when it needs to be modified.  Of course,
> it's silly to do this if the element type is Complex, since it's surely
> easier to copy two floats than to implement all the overhead needed to deal
> with references.  But I can imagine that it might make sense if the element
> type is ... um, more complex than Complex.  Or a whole lot bigger.

> I'm still dubious that it can work, though.  Consider:
> 
>   X := V.Copy(W);                        -- (A)
>   Ref1 := V.Constant_Reference (W, 1);   -- (B)
>   Ref2 := V.Constant_Reference (X, 1);   -- (C)
>   X(1).Re := X(1).Re + 1.0;              -- (D)
> 
> If the Copy function did not create any new copies of elements, then
> Ref1.Element and Ref2.Element will end up being accesses to the same element,
> after (C) is performed.  If the new copy of the element is not created until
> Reference is evaluated by the left side of statement (D), the result is that
> either Ref2.Element (or possibly Ref1.Element) will be pointing at the wrong
> thing.  

I was searching a way for controlling eval-order, when writing my first post.
I thought the function having "aliased in out" should be called earlier than the function having "aliased in".
But it was too simplistic.
Your example awoke me to that it can save the result of Constant_Reference.
Surely, it's the problem of *my* implementation.

> So it looks to me like the method you suggest shouldn't be allowed, even
> in your own container, since it would make it impossible to implement
> Constant_Reference  correctly.

I still don't think it's impossible.
How about inserting the copy-on-write code into Constant_Reference?

> My caveat still applies, though; this involves issues that I'm not yet
> completely familiar with, so it's possible that I made a serious error.
> I'm hoping someone will come to my rescue if I did ... :)

You at least seem more familiar with this than me. :)

Re: Problem in "X (1).Re := X (1).Re + 1"

[ytomino]

On Wednesday, May 9, 2012 7:29:14 AM UTC+9, Randy Brukardt wrote:
> 
> (Note that a copy-on-write implementation is not a good idea for the 
> standard containers for other reasons as well,

> the main one being that the usual uses don't create many copies,

Really?
Ada.Containers.Vectors have some "&" operators.
Many copies may be created when doing X & A & B & C...

Of course, it's ineffective only at reference-counting because appending is one of writing.
More trick is required to use remained area in the capacity.
However, this optimization is possible.
For example, plural containers that are different length are able to share same data area if the areas filled by each container are same.

> so having overhead for that can't be 
> justified. But it should be possible to create a container with that 
> semantics.)

Re: Problem in "X (1).Re := X (1).Re + 1"

[ytomino]

On Wednesday, May 9, 2012 2:14:20 AM UTC+9, Adam Beneschan wrote:
> On Monday, May 7, 2012 6:14:42 PM UTC-7, Randy Brukardt wrote:
> > "Adam Beneschan" wrote in message 
> > news:10294366.7.1336426132700.JavaMail.geo-discussion-forums@yngg23...
> > On Monday, May 7, 2012 11:53:58 AM UTC-7, ytomino wrote:
> > > On Tuesday, May 8, 2012 12:37:44 AM UTC+9, Adam Beneschan wrote:
> > ...
> > >So it looks to me like the method you suggest shouldn't be allowed, even in 
> > >your own container,
> > > since it would make it impossible to implement Constant_Reference 
> > > correctly.
> > 
> > It seems to me that his implementation is wrong, since Constant_Reference 
> > creates a reference, so it should be impossible for something else to 
> > "deallocate" the reference at the same time. (I'm talking about in a 
> > hand-created container,  I don't think this implementation would be 
> > legitimate for Vectors - although I'm not certain). That probably means that 
> > Constant_Reference would have to increase the reference count when it is 
> > created and decrease it when it is destroyed (specifically the reason why 
> > these return record types with discriminants rather than just a bare access 
> > value). If that's done, his original example is fine.
> 
> I'm not so sure.  If I understand the issue correctly, the problem isn't
> deallocation.  The problem occurs when two separate vector elements (whether
> they are elements of different vectors or of the same vector) share the same
> location temporarily; but later, the location of one of them moves, so that
> they no longer share the same location.  When that happens, any
> Constant_Reference that was previously applied to the element that has moved
> is no longer valid.  I don't see how having Constant_Reference increase
> a reference count solves the problem. (It would prevent a deallocation, but
> I think this is a problem that occurs before there is any deallocation.)

I had not made an issue of deallocation, too.
At first, I wanted to make calling Reference earlier than calling Constant_Reference in same statement.
But it's a kind of "dangling pointer".
Real problem is old access value designated to the shared area still alive after copy-on-write.
(I'm so thankful to Adam.)

> I may be misunderstanding what the OP is trying to accomplish;
> my understanding is based on the term "copy-on-write", but he didn't provide
> any details, and I had to look up what it meant since I wasn't familiar with
> the term.

...m(_ _)m

> Anyway, I think that a user-defined container would have the same problem as
> the language-defined container.
> (It seems like, for a user-defined container, making Constant_Reference
> private would help.  Then it could still be used for user-defined indexing
> operations, while, I think, preventing callers from creating
> Constant_Reference_Type objects that could still exist when the elements
> that they refer to are relocated.)

Or, making that Constant_Reference also do copy-on-write.
Then, an access value designated to shared area does not go out from the container.

> In fact, looking into this further, I think there's a problem with the AARM
> in this regard.  A.18.2(254.a), which was from Ada 2005, says
> "an implementation that avoided copying until one of the containers is
> modified would be allowed".  It seems to me that this is no longer true.

Ah, I could not remember it. I feel that perhaps I had read...

> I'm going to send something to Ada-Comment about this.

Re: Problem in "X (1).Re := X (1).Re + 1"

[ytomino]

On Wednesday, May 9, 2012 5:05:50 PM UTC+9, ytomino wrote:
> 
> I still don't think it's impossible.
> How about inserting the copy-on-write code into Constant_Reference?

I reconsidered.

X : Vector;
-- insert items into X
Ref1 := V.Constant_Reference (X, 1); -- reference counter = 1
Z := X; -- reference counter = 2
Ref2 := V.Constant_Reference (X, 2); -- (E) what should it do? 

If simple copy-on-write is executed at E, Ref1.Element will be an old value.
Probably, Reference/Constant_Reference should disable the container from increasing the reference counter.

X : Vector;
-- insert items into X
Ref1 := V.Constant_Reference (X, 1); -- reference counter = 1, and locking it
Z := X; -- deep copy, keeping reference counter = 1
Ref2 := V.Constant_Reference (X, 2); -- OK

Otherwise, more complicated mechanism like ownership control is required.

Re: Problem in "X (1).Re := X (1).Re + 1"

[Randy Brukardt]

"ytomino" <aghia05@gmail.com> wrote in message 
news:8861140.211.1336552896666.JavaMail.geo-discussion-forums@pbcrz9...
> On Wednesday, May 9, 2012 7:29:14 AM UTC+9, Randy Brukardt wrote:
>>
>> (Note that a copy-on-write implementation is not a good idea for the
>> standard containers for other reasons as well,
>
>> the main one being that the usual uses don't create many copies,
>
> Really?
> Ada.Containers.Vectors have some "&" operators.
> Many copies may be created when doing X & A & B & C...

Sure, the containers have some operations where this implementation would be 
a benefit. But I would guess that those operations would be used very rarely 
(if ever), so optimizing for them would be a mistake.

I think this is similar to the usage of the operations in 
Ada.Strings.Unbounded. There are many operations defined in that package, 
but most code I've seen only uses a handful of those operations. Optimizing 
for the other operations is wasted effort.

That's way I said it might make sense to use this implementation in your own 
container package, because your usage patterns might be far from typical. 
(There cannot be a one-size-really-fits-all implementation.)

                                  Randy. 

Re: Problem in "X (1).Re := X (1).Re + 1"

[Randy Brukardt]

"ytomino" <aghia05@gmail.com> wrote in message 
news:30097103.0.1336555778034.JavaMail.geo-discussion-forums@pbcow8...
...
> I had not made an issue of deallocation, too.
> At first, I wanted to make calling Reference earlier than calling 
> Constant_Reference in same statement.
> But it's a kind of "dangling pointer".
> Real problem is old access value designated to the shared area still alive 
> after copy-on-write.
> (I'm so thankful to Adam.)

This reminds me of something I forgot: The beauty of 
Constant_Reference/Reference in the standard containers is that there cannot 
be a dangling pointer (assuming no Unchecked programming is involved). These 
are tampering events so long as the pointer still exists, and thus is it 
impossible to modify the container (attempts to do so will raise 
Program_Error).

So the act of assigning a "Constant_Reference" as Adam did is to "lock" the 
container from [most] modification for a long time. That might be a problem 
for the program, but it can't cause the container to become corrupt.

(Iterators also use the tampering solution to prevent problems, but they use 
a weaker form.)

Of course, that might not be true for a user-defined container, but then you 
have to work out your own solution to the problem.

                              Randy.

Re: Problem in "X (1).Re := X (1).Re + 1"

[ytomino]

On Thursday, May 10, 2012 9:58:04 AM UTC+9, Randy Brukardt wrote:
> 
> This reminds me of something I forgot: The beauty of 
> Constant_Reference/Reference in the standard containers is that there cannot 
> be a dangling pointer (assuming no Unchecked programming is involved). These 
> are tampering events so long as the pointer still exists, and thus is it 
> impossible to modify the container (attempts to do so will raise 
> Program_Error).

I agree, generally.

Only in the cases of my and Adam's sample code, we have hoped that they work through with reference-counting or no reference-counting.
So any exceptions are unsuitable.

Re: Problem in "X (1).Re := X (1).Re + 1"

[ytomino]

On Thursday, May 10, 2012 9:52:12 AM UTC+9, Randy Brukardt wrote:
> 
> Sure, the containers have some operations where this implementation would be 
> a benefit. But I would guess that those operations would be used very rarely 
> (if ever), so optimizing for them would be a mistake.
> 
> I think this is similar to the usage of the operations in 
> Ada.Strings.Unbounded. There are many operations defined in that package, 
> but most code I've seen only uses a handful of those operations. Optimizing 
> for the other operations is wasted effort.

(This my opinion is unrelated to main subject.)

I could understand it. But I don't want to be satisfied.

Even if Ada.Strings.Unbounded.Replace_Slice *with resizing* is very slow, I will not worry.
However, if Replace_Slice *without resizing* is very slow, I will be angry.
Because, it's getting worse from raw array.
(Of course, exclude the time for memory management. It's main reason to use Unbounded_String.)
And, Vectors is also made to be similar to array. "&" is very popular primitive on array. It should not be worse though it's rarely.

Perhaps, reference counting is exaggerated, such as your saying.
In practice, something that is lighter than reference counting like move semantics (of C++) can satisfy it.

Recently, in GNAT, reference counting is implemented into Unbounded_String.
So, I also expect Vectors.

> That's way I said it might make sense to use this implementation in your own 
> container package, because your usage patterns might be far from typical. 
> (There cannot be a one-size-really-fits-all implementation.)

Re: Problem in "X (1).Re := X (1).Re + 1"

[Randy Brukardt]

"ytomino" <aghia05@gmail.com> wrote in message 
news:16249910.1154.1336624012153.JavaMail.geo-discussion-forums@pbyy9...
> On Thursday, May 10, 2012 9:58:04 AM UTC+9, Randy Brukardt wrote:
>>
>> This reminds me of something I forgot: The beauty of
>> Constant_Reference/Reference in the standard containers is that there 
>> cannot
>> be a dangling pointer (assuming no Unchecked programming is involved). 
>> These
>> are tampering events so long as the pointer still exists, and thus is it
>> impossible to modify the container (attempts to do so will raise
>> Program_Error).
>
> I agree, generally.
>
> Only in the cases of my and Adam's sample code, we have hoped that they 
> work through
>with reference-counting or no reference-counting. So any exceptions are 
>unsuitable.

"Unsuitable"? Doing dangerous things ought to be prevented; that's the point 
of the exceptions. And keeping uncontrolled pointers into a container that 
might be modified is one of those dangerous things. It took a *lot* of 
convincing that it could be possible to safely allow pointers at container 
elements.

Also note that not all container modifications are prevented, mostly ones 
that would cause trouble (although this is rather conservative).

Obviously, you can write your own container that allows any unsafe things 
you want, but that's not possible with the Standard containers.

                                   Randy.

Re: Problem in "X (1).Re := X (1).Re + 1"

[ytomino]

On Tuesday, May 15, 2012 3:09:18 PM UTC+9, Randy Brukardt wrote:
> "ytomino" wrote in message 
> news:16249910.1154.1336624012153.JavaMail.geo-discussion-forums@pbyy9...
> > On Thursday, May 10, 2012 9:58:04 AM UTC+9, Randy Brukardt wrote:
> >>
> >> This reminds me of something I forgot: The beauty of
> >> Constant_Reference/Reference in the standard containers is that there 
> >> cannot
> >> be a dangling pointer (assuming no Unchecked programming is involved). 
> >> These
> >> are tampering events so long as the pointer still exists, and thus is it
> >> impossible to modify the container (attempts to do so will raise
> >> Program_Error).
> >
> > I agree, generally.
> >
> > Only in the cases of my and Adam's sample code, we have hoped that they 
> > work through
> >with reference-counting or no reference-counting. So any exceptions are 
> >unsuitable.
> 
> "Unsuitable"? Doing dangerous things ought to be prevented; that's the point 
> of the exceptions. And keeping uncontrolled pointers into a container that 
> might be modified is one of those dangerous things. It took a *lot* of 
> convincing that it could be possible to safely allow pointers at container 
> elements.
> 
> Also note that not all container modifications are prevented, mostly ones 
> that would cause trouble (although this is rather conservative).
> 
> Obviously, you can write your own container that allows any unsafe things 
> you want, but that's not possible with the Standard containers.
> 
>                                    Randy.

Sorry, I can't understand what is your argument, and probably my words are lacking again. 
If a Standard container that's implemented A.18.2(254.a) is existing, should not it behave similarly to the normal version (no sharing version) Standard container? I think yes. 
Naturally error checkings have to be inserted. But, in the cases that the normal version container does not raise any exceptions,
the sharing version should try to make coherence by doing a trick at its hidden side, instead of raising a exception.
I feel that it has been an implicit promise.

Re: Problem in "X (1).Re := X (1).Re + 1"

[Simon Wright]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> "ytomino" <aghia05@gmail.com> wrote in message 
> news:30097103.0.1336555778034.JavaMail.geo-discussion-forums@pbcow8...
> ...
>> I had not made an issue of deallocation, too.
>> At first, I wanted to make calling Reference earlier than calling 
>> Constant_Reference in same statement.
>> But it's a kind of "dangling pointer".
>> Real problem is old access value designated to the shared area still alive 
>> after copy-on-write.
>> (I'm so thankful to Adam.)
>
> This reminds me of something I forgot: The beauty of
> Constant_Reference/Reference in the standard containers is that there
> cannot be a dangling pointer (assuming no Unchecked programming is
> involved). These are tampering events so long as the pointer still
> exists, and thus is it impossible to modify the container (attempts to
> do so will raise Program_Error).
>
> So the act of assigning a "Constant_Reference" as Adam did is to
> "lock" the container from [most] modification for a long time. That
> might be a problem for the program, but it can't cause the container
> to become corrupt.

Fair enough, but the copy-on-write scheme means that simply updating a
value in an element may be "tampering" - which I'm fairly sure it isn't
now (A.18.2(97)).

There seem to be new opportunities for error here.

I suppose that an implementation that used copy-on-write for the
standard containers would have to warn users that any use of Reference
or Constant_Reference would be liable to result in Program_Error in
unexpected places.

Note, I'm not saying this is a bad thing; I think it's exactly the right
thing (and probably a good reason not to implement the standard
containers like this).

Re: Problem in "X (1).Re := X (1).Re + 1"

[Randy Brukardt]

"ytomino" <aghia05@gmail.com> wrote in message 
news:29152338.116.1337113067360.JavaMail.geo-discussion-forums@pbcjt7...
...
> Sorry, I can't understand what is your argument, and probably my words are 
> lacking again.
> If a Standard container that's implemented A.18.2(254.a) is existing, 
> should not it behave similarly
> to the normal version (no sharing version) Standard container? I think 
> yes.

Yes, of course.

> Naturally error checkings have to be inserted. But, in the cases that the 
> normal version container
> does not raise any exceptions, the sharing version should try to make 
> coherence by doing a trick
> at its hidden side, instead of raising a exception. I feel that it has 
> been an implicit promise.

Quite right. But my point was that the examples you showed would almost 
certainly fail the tampering check in the Standard containers (*any* correct 
implementation) - so long as you have a valid pointer to an element, you 
cannot tamper with the container (tampering prevents certain types of 
modifications). So those examples would raise an exception, and the 
reference counting problems would never arise (because the modification is 
prevented).

The tampering check allows a wide variety of ways to manage the elements of 
a container, but probably not *every* possible way. And it should be obvious 
that any time you have a pointer into part of a container, you have to be 
very careful about what operations are allowed while that pointer exists. 
That might prevent some sorts of implementations, but it is the nature of 
pointers. (If that's really a problem for a custom container, don't use 
them!).

                                Randy.

Re: Problem in "X (1).Re := X (1).Re + 1"

[Dmitry A. Kazakov]

On Tue, 15 May 2012 23:12:56 +0100, Simon Wright wrote:

> I suppose that an implementation that used copy-on-write for the
> standard containers would have to warn users that any use of Reference
> or Constant_Reference would be liable to result in Program_Error in
> unexpected places.

Or support reference promotion (+ task identification), which is nice can
of worms...

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