* Re: GNAT: Unbounded_Strings [not found] <9h9a9n$6bm$1@news.kiev.sovam.com> @ 2001-06-26 9:45 ` Florian Weimer 2001-06-26 9:46 ` Florian Weimer 1 sibling, 0 replies; 5+ messages in thread From: Florian Weimer @ 2001-06-26 9:45 UTC (permalink / raw) "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. ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: GNAT: Unbounded_Strings [not found] <9h9a9n$6bm$1@news.kiev.sovam.com> 2001-06-26 9:45 ` GNAT: Unbounded_Strings Florian Weimer @ 2001-06-26 9:46 ` Florian Weimer 2001-06-26 12:23 ` Florian Weimer 1 sibling, 1 reply; 5+ messages in thread From: Florian Weimer @ 2001-06-26 9:46 UTC (permalink / raw) "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. ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: GNAT: Unbounded_Strings 2001-06-26 9:46 ` Florian Weimer @ 2001-06-26 12:23 ` Florian Weimer 2001-06-26 13:58 ` Maxim Reznik 0 siblings, 1 reply; 5+ messages in thread From: Florian Weimer @ 2001-06-26 12:23 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: GNAT: Unbounded_Strings 2001-06-26 12:23 ` Florian Weimer @ 2001-06-26 13:58 ` Maxim Reznik 2001-06-26 15:28 ` Florian Weimer 0 siblings, 1 reply; 5+ messages in thread From: Maxim Reznik @ 2001-06-26 13:58 UTC (permalink / raw) "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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: GNAT: Unbounded_Strings 2001-06-26 13:58 ` Maxim Reznik @ 2001-06-26 15:28 ` Florian Weimer 0 siblings, 0 replies; 5+ messages in thread From: Florian Weimer @ 2001-06-26 15:28 UTC (permalink / raw) "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. ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2001-06-26 15:28 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <9h9a9n$6bm$1@news.kiev.sovam.com> 2001-06-26 9:45 ` GNAT: Unbounded_Strings Florian Weimer 2001-06-26 9:46 ` Florian Weimer 2001-06-26 12:23 ` Florian Weimer 2001-06-26 13:58 ` Maxim Reznik 2001-06-26 15:28 ` Florian Weimer
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox