Re: GNAT: Unbounded_Strings

Re: GNAT: Unbounded_Strings

[Florian Weimer]

"Maxim Reznik" <max1@mbank.com.ua> writes:

> I propose another implementation of Unbounded_Strings using
> reference counting.

Your implementation is not task safe, therefore it is not suitable for
inclusion in the GNAT runtime library because it has to deal correctly
with tasking issues.

> I'm posting it to this news group

Please do not post binaries to discussion groups.  Thanks.

Re: GNAT: Unbounded_Strings

[Florian Weimer]

"Maxim Reznik" <max1@mbank.com.ua> writes:

> I propose another implementation of Unbounded_Strings using
> reference counting.

Your implementation is not task safe, therefore it is not suitable for
inclusion in the GNAT runtime library, I think.

> I'm posting it to this news group

Please do not post binaries to discussion groups.  Thanks.

Re: GNAT: Unbounded_Strings

[Florian Weimer]

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

> "Maxim Reznik" <max1@mbank.com.ua> writes:
> 
>> I propose another implementation of Unbounded_Strings using
>> reference counting.
> 
> Your implementation is not task safe,

I was asked to explain this, so here we go.

Have a look at the following code:

        declare
           A, B : Unbounded_String;

        begin
           A := Fetch_Some_Data;
           B := A;
           Do_Something_With (A);
           Do_Something_Else_With (B);
        end;

Do_Something_With creates a task which continues to run after
Do_Something_With returns.  The task and Do_Something_Else_With both
modify A and B at some point.

According to the ARM (A) this is allowed:

  3. The implementation shall ensure that each language defined
     subprogram is reentrant in the sense that concurrent calls on the
     same subprogram perform as specified, so long as all parameters
     that could be passed by reference denote nonoverlapping objects.

A and B are clearly non-overlapping, so the situation describe above
is completely valid, in particular, it does not result in erroneous
execution.

However, your code does not synchronize the two task when the a local
copy of a shared string is made.  As a result, your subprograms are
not reentrant, and therefore not conforming to the implementation
requirement quoted above.

Re: GNAT: Unbounded_Strings

[Maxim Reznik]

"Florian Weimer" <fw@deneb.enyo.de> wrote in message news:873d8nfn0j.fsf@deneb.enyo.de...
> Florian Weimer <fw@deneb.enyo.de> writes:
>
> > "Maxim Reznik" <max1@mbank.com.ua> writes:
> >
> >> I propose another implementation of Unbounded_Strings using
> >> reference counting.
> >
> > Your implementation is not task safe,
>
> I was asked to explain this, so here we go.
[...]
> However, your code does not synchronize the two task when the a local
> copy of a shared string is made.  As a result, your subprograms are
> not reentrant, and therefore not conforming to the implementation
> requirement quoted above.

Thank you for your explanation.

Modifying of a shared string is synchronized by reference counter.
While this counter >1 any change of shared string can't be done.

One thing I could lose sight of is synchronization of counter itself.

Are following changes enough ?

++++
   protected type Counter is
       procedure Increment;
       procedure Decrement;
       function Value return Natural;
   private
       Count : Natural := 0;
   end Counter;

   type Shared_String (Length : Natural) is record
       Space : String (1 .. Length);
       Count : Counter;
   end record;

  -- replace all references to Share.Count with protected procedures.
++++

I think operators
++++
          if Source.Share.Count.Value = 1 then
               Change_Somehow( Source.Share.Space );
          else
               Make_A_Copy
               Decrement_Count (Source.Share);
          end if;
++++
are Ok, because of Count.Value=1 means that there isn't any other references to string and
nobody can change neither Share.Count nor Share.Space.

One bad consequence of this solution is 40 bytes overhead for each strings.

--
Maxim Reznik

Re: GNAT: Unbounded_Strings

[Florian Weimer]

"Maxim Reznik" <max1@mbank.com.ua> writes:

> Modifying of a shared string is synchronized by reference counter.
> While this counter >1 any change of shared string can't be done.

Yes, that's necessary for correct operation, and it might be
sufficient if the counter cannot raise after the comparison.

> One thing I could lose sight of is synchronization of counter itself.
> 
> Are following changes enough ?

I'm not sure, I think I would have to see the whole source code.

> I think operators
>++++
>           if Source.Share.Count.Value = 1 then
>                Change_Somehow( Source.Share.Space );
>           else
>                Make_A_Copy
>                Decrement_Count (Source.Share);
>           end if;
>++++

> are Ok, because of Count.Value=1 means that there isn't any other
> references to string and nobody can change neither Share.Count nor
> Share.Space.

I think this agrees with the letter of the ARM.  I'm still not sure if
it breaks any of my expectations regarding string types, but I

> One bad consequence of this solution is 40 bytes overhead for each strings.

You could use one global lock for all reference counter operations.
Contention on this lock isn't a problem when compared to the original
GNAT implementation because all operations which require copying a
string already involve the global allocator lock.