!standard A(3/4) 17-06-08 AI12-0139-1/04 !standard A.18(5) !class Amendment 14-10-13 !status work item 14-10-13 !status received 14-10-03 !priority Low !difficulty Hard !subject Thread-safe Ada libraries !summary Add variants of the standard libraries that are thread-safe. !problem With the advent of multi-core computers, concurrency in the software becomes the normal case, not the specialized application. Yet, presently, the Ada standard libraries are not required to be thread-safe. They should be. In particular, the Container libraries are thread-unsafe, yet often used for communicating among concurrent threads. The same is true for "simpler" data structures provided by standard libraries such as vectors or the variants of strings. It is rather dangerous to leave the user in the dark about whether a particular library package is thread-safe or not. !proposal We propose to add a variant of the Ada Standard library that is required to be thread-safe. We define the package Ada.Task_Safe as a new root for a duplicate of the entire Ada library and postulate thread-safeness for the entire content of the package, including its child units. !wording Add as A (2.1) : In addition, the package Ada.Task_Safe is predefined. It contains duplicates of all child units of the package Ada listed above. Syntax and semantics of all declarations and specifications are identical, except for the different root of the unit hierarchy and the behaviour in the presence of concurrency as specified in this clause or as specified for specific packages in this International Standard. In addition to the semantics of package Ada and its child units, the effects of concurrent invocations of all subprograms, protected operations, and primitive operations defined within the child units of Ada.Task_Safe shall be the same as the effects of some [arbitrary] sequence of the same invocations. Causing a call to any operation of the library from within the library, e.g., by callback mechanisms, is a bounded error. The call may perform as specified or it may deadlock[, in which case implementations are allowed to raise Program_Error]. Add as A (3.2.1 and 3.2.2) : -- Note to ARG: this is within Implementation Requirements Within Ada.Task_Safe and its child units, implementations shall ensure the implied atomicity of operations on global resources and the visibility of changes across the boundaries of concurrent units as implied by atomic changes to shared resources. The implementation should provide for mutual exclusion at a fine degree of granularity, at a minimum of at least one lock per object of each type with task-safe operations. For containers, the Stable nested package will acquire exclusive access to the underlying upon creation, with no further synchronization associated with individual operations. <<< I have no idea what the last sentence tries to say, but I copied it faithfully from the minutes. What Stable nested package and what underlying ... ? If I guess at what it is traing to say, it would completely void the purpose of this AI, since the creator task would own the container exclusively forever and this would explicitly prevent shared use of the container by multiple tasks altogether. >>> <<< Note to ARG: the following is a prototyping of a more specific semantics for a given package. I randomly chose Hashed_Maps.>> <<< Note to ARG: Semi-unrelated RM observation: Several of the present container packages contain dynamic semantics under the heading of static semantics. E.g. A.18.24 (7/3). Which I why I did not bother distinguishing either, but I did leave out the heading of "static semantics" present in other packages.>>> Add a package A.18.X The Generic Package Ada.Task_Safe.Containers.Hashed_Maps The language-defined generic package Ada.Task_Safe.Containers.Hashed_Maps provides a map with the same operations as the package Containers.Hashed_Maps (see A.18.5), with the added semantics that concurrent operations are synchronized so that modifying accesses preclude any concurrent accesses. Concurrent reads are non-blocking. The declaration of the generic library package Task_Safe.Containers.Hashed_Maps has the same contents and semantics as Containers.Hashed_Maps except: No tampering checks are performed. <<< Note to ARG. The following paragraph is written so that tampering code blocks temporarily rather than fail permanently. If I did not catch all cases, let me know and please provide words to include the missed ones.>>> Any operation that modifies a map, cursor or iterator instance blocks while any other operation on the same map instance or any cursor or iterator instance obtained for the same map instance is executed or while iterator instances other than the one operated upon or obtained for other map instances exist. All operations on the same map instance or any cursor or iterator instance block while an operation executes that modifies the same map instance or any cursor or iterator instance obtained for the same map instance. !discussion To mandate that the existing library shall be thread-safe is considered to be too much of a performance burden, particularly for applications that include no concurrency. Hence a thread-safe duplicate of the library is proposed. Examining each unit of the standard library to determine whether a thread-safe version is needed or wanted is a possible alternative with major disadvantages: 1. The user would carry the burden of having to check for each subunit whether it is thread-safe or not, and if not, whether an alternative exists and, if so, under which name. Thus, cognitive burden to the user is high. 2. Chances to make existing units thread-safe are very low, since the consensus seems to be that the added execution cost should not be part of the default behavior. 3. The implementation burden of making individual units thread-safe may be considerably higher than an overall scheme (which, with very coarse lock granularity, allows automated generation of the implementation). 4. Ultimately only the implementer knows whether deep down in the implementation thread-unsafe mechanisms, e.g., a fault handling strategy with shared state, are used. A prescription of lock granularity, as is implied by postulating a unit-by-unit thread-safeness, may be very costly to implementers, since dependencies might need to be undone. 5. Short of explicit statements to the effect, it is not possible to judge whether a subunit is already thread-safe for the reasons above. The global approach has the following advantages: 1. Switching between thread-safe and thread-unsafe versions is done by altering the package prefixes. With good "use"-clauses, the change can be confined to the "with/use"-clauses. 2. The protected notion extends across child units and it does so intentionally, since there are child units in the Ada library whose semantics interact via shared resources. The thread-safeness therefore needs to extend across child units. 3. Implementations can start with coarse-grained locks and trivial implementations and gradually refine the locks in those areas where they believe that a higher degree of concurrency is needed by customers. 4. Nothing stands in the way of users, who want to use the thread-unsafe versions and "roll their own" protection against destructive data races. It is intentional that the types defined in the child units of package Ada are incompatible with types defined in child units of package Ada.Task_Safe. We want to avoid any mixing with all the ensuing semantic complications. In particular access types shall not be able to designate objects from both kinds of packages (for obvious reasons). The semantic specification is intentionally focused only on the needed effect, leaving the actual realization to the implementations. Given this freedom, all callbacks of library operations from within the library are at risk to cause deadlocks. It is questionable whether lock granularity can be specified tightly enough for deterministic behavior at reasonable implementation effort. This approach allows later refinements when the community feels that the freedom of implementation was too wide and some granularity of locking is to be required. ----- Note to ARG: The proposal extends to the entire library; a more modest alternative is to apply the change only to package Containers to cover all containers. I advise against it, since it would be hard to extend compatibly later on. Also I do not see why the rest of the library should not also work correctly for concurrent calls. End of Note. ------ At the Oct'15 meeting, the ARG wanted to see what a specific prototype of a package could be with a more refined synchronization requirement. This version (3 of June'16) contains such a package. The rules are intended to allow concurrent reads, but prevent writes concurrent to reads on the same data structures. In the process, tampering situations were (hopefully) eliminated. We can have tampering back if the rule about iterator instances is rewritten to the simpler "do not access shared data concurrently"-model (as opposed ot the transaction model now put into the semantics to also deal with tampering). !examples Any existing code calling library operations from within concurrent tasks. !ASIS No impact. !ACATS test !appendix From: Tucker Taft Sent: Friday, October 3, 2014 9:23 PM It is a real drag that iterating over a container seems to require setting one or more flags to prevent tampering, which seems to require some sort of trick to update a possibly read-only container, as well as introducing race conditions when concurrent tasks are iterating over the same container, etc. Suppose we allowed implementations to go a different route, where they could maintain a per-task table of containers-being-iterated. This table would never get very big, and the tampering checks would be allowed to be implemented by checking if the container about to be updated is in the table. Clearly it is generally erroneous to update a container from another task while it is being iterated, and we weren't trying to protect against that in any case. We could more generally say that even if appropriate task signaling is done, etc. to avoid a true data race, it is still erroneous for a separate task to tamper with a container while it is being iterated. Once we make that statement, we can use per-task tables for all of the within-task tampering checks, and avoid the problems mentioned above with having to set flags in read-only containers, and create race conditions when two tasks want to iterate the same container. This depends on efficient per-task storage of some sort, which many operating systems are beginning to provide. You probably would *not* want to use a conventional task attribute, as those generally require a heavier-weight O/S call. This might argue for some kind of more efficient task attribute, which is only visible to the current task, and could be mapped to typical O/S per-task storage. Or perhaps it could be controlled by a defaulted generic parameter of Task_Attributes, which would indicate whether the attribute should be visible from other tasks. *************************************************************** From: Tullio Vardanega Sent: Monday, October 6, 2014 11:04 AM I like this idea. *************************************************************** From: Bob Duff Sent: Monday, October 6, 2014 11:41 AM > I like this idea. I'm very much in favor of somehow solving the race condition issue. I think the appropriate way to proceed is for some Ada implementer to implement Tucker's idea, and see if it's efficient enough. I don't think ARG should be discussing this without that information. Note that the tampering checks are not the only thing that makes the containers inefficient. > On 04/10/2014 04:23, Tucker Taft wrote: > > This depends on efficient per-task storage of some sort, which many > > operating systems are beginning to provide. On any machine with a decent number of registers (not x86 :-( ), I'd like to store a pointer to the current thread-control-block in a register. I don't know why more operating systems don't do that. *************************************************************** From: Tucker Taft Sent: Monday, October 6, 2014 11:52 AM > I think the appropriate way to proceed is for some Ada implementer to > implement Tucker's idea, and see if it's efficient enough. > I don't think ARG should be discussing this without that information. What I think is worth discussing is whether we could live with the limitation that even if two tasks coordinate properly, you don't need to detect tampering performed by one such task while the other is iterating. That is, it is fine if the tampering checks only detect tampering performed by the same task as the one doing the iterating. It certainly seems acceptable to me... I also think your comment has the danger of getting us back into the chicken-and-egg, where a vendor won't devote resources to implement something if it isn't being considered for standardization, and we aren't allowed to consider something for standardization until some vendor implements it. > Note that the tampering checks are not the only thing that makes the > containers inefficient. It might be nice to have a concise list of these problems. Could you provide a start for that? >>> This depends on efficient per-task storage of some sort, which many >>> operating systems are beginning to provide. > > On any machine with a decent number of registers (not x86 :-( ), I'd > like to store a pointer to the current thread-control-block in a > register. I don't know why more operating systems don't do that. I think efficient thread-local storage is becoming nearly ubiquitous. *************************************************************** From: Edmond Schonberg Sent: Monday, October 6, 2014 12:02 PM >> Note that the tampering checks are not the only thing that makes the >> containers inefficient. But right now this is the biggest hit when using containers in non-concurrent situations: having to finalize a cursor on every iteration to clear the tampering bits is a horrible hit. The performance comparison with containers in other languages makes them unacceptable at once. *************************************************************** From: Bob Duff Sent: Monday, October 6, 2014 1:12 PM > What I think is worth discussing is whether we could live with the > limitation that even if two tasks coordinate properly, you don't need > to detect tampering performed by one such task while the other is iterating. I can. But then, I can live without tampering checks entirely. >...That is, it is fine if the tampering checks only detect tampering >performed by the same task as the one doing the iterating. It >certainly seems acceptable to me... > > I also think your comment has the danger of getting us back into the > chicken-and-egg, where a vendor won't devote resources to implement > something if it isn't being considered for standardization, and we > aren't allowed to consider something for standardization until some vendor > implements it. Well, AdaCore is already planning to expend some resources on fast containers, although I don't know exactly how much and when. You can agitate within AdaCore to make that happen. I also don't know whether we will manage to make fast containers with the same interface as the standard ones. I kind of doubt it. > > Note that the tampering checks are not the only thing that makes the > > containers inefficient. > > It might be nice to have a concise list of these problems. Could you > provide a start for that? I don't think I have time to do a thorough study right now. In my work on the pretty printer, I took a different approach. Vectors were WAY too slow. Instead of figuring out in detail why, I wrote my own Fast_Vectors, which supports only the operations I needed. E.g. it has Append, but not Insert. Fast_Vectors is not safe. E.g. it exports a function that returns a pointer to the underlying array. Sounds like a recipe for dangling pointers, but in practice it's not. You just have to get into the habit of doing: X : Elems_Array renames Elems (V) (1 .. Last_Index (V)); ... -- operate on X, but don't do Append (etc) while X still exists I find that usage very natural -- typical code IME goes in phases: build the vector, operate read-only, append some more, operate read-only, ... In a multi-tasking program, it would be: build the vector, then spawn a bunch of tasks to operate read-only. No tampering checks, either, and I don't recall any bugs related to that. > I think efficient thread-local storage is becoming nearly ubiquitous. It's about time. We've all known how to do that for decades. *************************************************************** From: Bob Duff Sent: Monday, October 6, 2014 1:18 PM > >> Note that the tampering checks are not the only thing that makes > >> the containers inefficient. > > But right now this is the biggest hit when using containers in > non-concurrent situations: having to finalize a cursor on every > iteration to clear the tampering bits is a horrible hit. The > performance comparison with containers in other languages makes them > unacceptable at once. True, but they might still be unacceptable after the suggested change. If I were going to work on this, I'd first determine the speedup we can get by entirely removing the checks, because that's easy to implement compared to Tucker's suggestion. *************************************************************** From: Arnaud Charlet Sent: Monday, October 6, 2014 2:01 PM > I can. But then, I can live without tampering checks entirely. Agreed, tampering checks seem just too misguided IMO, and introducing complex task specific data won't solve that in GNAT, so I do not see that as a viable way to improve efficiency of containers in GNAT. > Well, AdaCore is already planning to expend some resources on fast > containers, although I don't know exactly how much and when. > You can agitate within AdaCore to make that happen. Right. We should feel free to start with another API here and simplify things, instead of trying to "fix things" on the current API. > I also don't know whether we will manage to make fast containers with > the same interface as the standard ones. > I kind of doubt it. Agreed, this shouldn't be a prerequisite for this investigation. At this point, even though it's sad to say, I think we've gone too far in terms of overengineering the containers API, and made it very inefficient, for only a relative added safety (and this safety actually is hurting users who are getting tampering check error instead of getting the proper behavior when e.g. manipulating temp object), so it's probably time to restart from scratch (which is a big surprise to me given how many containers have already been written in the world in the past decades). *************************************************************** From: Tucker Taft Sent: Monday, October 6, 2014 2:14 PM >> I can. But then, I can live without tampering checks entirely. > > Agreed, tampering checks seem just too misguided IMO, and introducing > complex task specific data won't solve that in GNAT,... Actually, it is pretty simple, compared to the current tampering bits. It is just a stack of iterators in progress. Typically the stack will be empty when it is checked, namely when you try to update a container. > ... so I do not see that > as a viable way to improve efficiency of containers in GNAT. I think that may be a premature assessment. > ... so it's probably time to restart from scratch (which is a big > surprise to me given how many containers have already been written in > the world in the past decades). That might be fine for AdaCore's own library, but is not really practical for the Ada standard. The ARG needs to address the efficiency of the current containers. *************************************************************** From: Arnaud Charlet Sent: Monday, October 6, 2014 2:23 PM > Actually, it is pretty simple, compared to the current tampering bits. > It is just a stack of iterators in progress. Typically the stack will > be empty when it is checked, namely when you try to update a > container. Anything involving task-specific data isn't just "pretty simple" in GNAT unfortunately. > >... so I do not see that > >as a viable way to improve efficiency of containers in GNAT. > > I think that may be a premature assessment. > > >... so it's probably time to restart from scratch (which is a big > >surprise to me given how many containers have already been written in > >the world in the past decades). > > That might be fine for AdaCore's own library, but is not really > practical for the Ada standard. The ARG needs to address the > efficiency of the current containers. My point is that we probably need a pause here on containers and let the dust settle on one hand (and gather more feedback from users), and let AdaCore on the other hand experiment on their own, without giving too much direction/guidance. To give a more positive feedback, the 'for X of ...' loop syntax is really very convenient and a real improvement in Ada 2012 (and not just for containers, for arrays as well). We just need to make the underlying implementation of such simple to express loops more efficient now. *************************************************************** From: Randy Brukardt Sent: Monday, October 6, 2014 9:24 PM > It is a real drag that iterating over a container seems to require > setting one or more flags to prevent tampering, which seems to require > some sort of trick to update a possibly read-only container, as well > as introducing race conditions when concurrent tasks are iterating > over the same container, etc. I think we need a better problem statement than "it is a real drag". :-) In particular, there's no need to worry about race conditions with concurrent tasks, since any uncontrolled access is erroneous anyway, and if the access is properly controlled, the operations will happen sequentially anyway. > Suppose we allowed implementations to go a different route, where they > could maintain a per-task table of containers-being-iterated. This > table would never get very big, and the tampering checks would be > allowed to be implemented by checking if the container about to be > updated is in the table. Clearly it is generally erroneous to update > a container from another task while it is being iterated, and we > weren't trying to protect against that in > any case. We could more generally say that even if > appropriate task signaling is done, > etc. to avoid a true data race, it is still erroneous for a separate > task to tamper with a container while it is being iterated. Once we > make that statement, we can use per-task tables for all of the > within-task tampering checks, and avoid the problems mentioned above > with having to set flags in read-only containers, and create race > conditions when two tasks want to iterate the same container. I don't like introducing additional erroneous cases even when you do everything right (in this case, use appropriate task signaling). Moreover, it seems that the idea of allowing suppression of tampering checks also covers this area (because with the checks suppressed, any violation of tampering is erroneous). So I don't see this is adding anything, but perhaps that's because I don't understand the problem you're trying to solve. Moreover, this certainly isn't going to address any performance problems (this will make the checks more expensive in the general case, although one could imagine structuring them so they remain cheap if no objects are in the tampering state). After all, the main performance problem is using finalization to clear the tampering state, and this proposal does nothing for that. Finally, it seems to me that one could build a lock-free (somewhat of a misnomer) version of this based on a per-instance table for all tasks. If you're willing to take the performance hit of the more complex check, you could avoid having tampering values in the objects way and still not require any additional special rules. [The basic idea is that one has an atomic length for the table which takes on a special value that is used while the table is being modified, then the check is something like: if Tamper_Len = 0 then return; -- OK. else while Tamper_Len = Modification_in_Progress loop Yield; -- Or whatever to allow another task to run if one is ready for this processor. end loop; for I in 1 .. Tamper_Len loop if Container'Access = Tamper_Tab(I) then raise Program_Error; end if; end loop; end if; There might be a problem with this if there is no lock for protected actions (as in single-processor ceiling locking), as there is a possibility that the Yield might happen inside of a protected action. But the modification we're waiting for is not in a protected action, so we're OK so long as no additional protected action could be started. I think that has to be true on a multiprocessor. One could also use a scheme like this in a regular protected object, but I'd expect that to be much more expensive in general. Note that in the above, the while loop could only run if multiple tasks are operating on objects associated with the instance, that's probably not going to be very common. Adding a object to the table would something like (this isn't quite right, there's a race at the start if multiple tasks tried to enter a tampering object): while Tamper_Len = Modification_in_Progress loop Yield; -- Or whatever to allow another task to run if one is ready for this processor. end loop; Temp_Len := Tamper_Len; Tamper_Len := Modification_in_Progress; Tamper_Tab(Temp_Len+1) := Container'Access; Tamper_Len := Temp_Len+1; ] > This depends on efficient per-task storage of some sort, which many > operating systems are beginning to provide. You probably would *not* > want to use a conventional task attribute, as those generally require > a heavier-weight O/S call. My suggestion above doesn't require that nor does it require any erroneousness. Neither scheme improves performance, although neither would add much expense in the normal case that no objects are in tampering regions. *************************************************************** From: Randy Brukardt Sent: Monday, October 6, 2014 9:26 PM > >> Note that the tampering checks are not the only thing that makes > >> the containers inefficient. > > > > But right now this is the biggest hit when using containers in > non-concurrent situations: having to finalize a cursor on every > iteration to clear the tampering bits is a horrible hit. The > performance comparison with containers in other languages makes them > unacceptable at once. AI12-0111-1 discusses this. In Paris, we discussed the idea of an aspect to suppress the tampering checks (it would have to be on the instance to work). We assigned this AI (and idea) to one Ed Schonberg -- is there any feedback on it?? *************************************************************** From: Edmond Schonberg Sent: Monday, October 6, 2014 9:37 PM Sorry, swamped by other tasks (so to speak). Using an aspect on the instance might work, but off-hand we would really need two versions of the container packages: I don’t see an extra actual parameter determining whether to use controlled types or not in the implementation of references; there is too much machinery in each container package that depends on this. *************************************************************** From: Randy Brukardt Sent: Monday, October 6, 2014 10:05 PM Right, that's what we expected when we talked about it. The idea was that the aspect would chose which actual package to instantiate. J-P even suggested that we just have Unsafe_Vectors and the like in the language, but I remember that Tucker was very opposed to that. (I personally wouldn't care, it would only be a few paragraphs in the Standard and we have plenty of other Unchecked_ packages in the language already.) That would be a bit less mechanism, but I do agree that it is appealing if it works at least somewhat like other forms of Suppress. *************************************************************** From: Randy Brukardt Sent: Monday, October 6, 2014 9:36 PM ... > I don't think I have time to do a thorough study right now. > In my work on the pretty printer, I took a different approach. > Vectors were WAY too slow. Instead of figuring out in detail why, I > wrote my own Fast_Vectors, which supports only the operations I > needed. E.g. it has Append, but not Insert. Of course. That was always the intent: if the standard containers are too slow for your purposes, write your own that's better. There can't be a one-size-fits-all container. > Fast_Vectors is not safe. E.g. it exports a function that returns a > pointer to the underlying array. Sounds like a recipe for dangling > pointers, but in practice it's not. You just have to get into the > habit of doing: > > X : Elems_Array renames Elems (V) (1 .. Last_Index (V)); > ... -- operate on X, but don't do Append (etc) while X still > exists Of course, if "trusting the programmer" was a good enough way to do development, we wouldn't need Ada and all of the static and dynamic checks that it provides. After all, if you are "in the habit" of doing things right, any old programming language will do. I hope that Ada can do better (at least by default -- after all, in practice, most performance problems are not where the programmer expects them to be). *************************************************************** From: Randy Brukardt Sent: Monday, October 6, 2014 9:40 PM > > >> Note that the tampering checks are not the only thing that makes > > >> the containers inefficient. > > > > But right now this is the biggest hit when using containers in > > non-concurrent situations: having to finalize a cursor on every > > iteration to clear the tampering bits is a horrible hit. The > > performance comparison with containers in other languages makes them > > unacceptable at once. > > True, but they might still be unacceptable after the suggested change. They'd have to be, since the problem is the finalization overhead, not the tampering value itself (that's just an increment or decrement, which is dirt cheap). Tucker's scheme is more expensive than that (not a lot, but it surely could not be cheaper). I think Tucker's scheme is aimed at multitasking, not efficiency per-se (although I can't tell from his original message). Besides, people keep talking about iterators, but the problem is not with them but with Reference/Constant_Reference (which are part of some iterators, but have their own tampering checks). *************************************************************** From: Randy Brukardt Sent: Monday, October 6, 2014 10:00 PM ... > At this point, even though it's sad to say, I think we've gone too far > in terms of overengineering the containers API, and made it very > inefficient, for only a relative added safety (and this safety > actually is hurting users who are getting tampering check error > instead of getting the proper behavior when e.g. manipulating temp > object), so it's probably time to restart from scratch (which is a big > surprise to me given how many containers have already been written in > the world in the past decades). The primary purpose of the tampering checks were to make the containers have the same level of safety as an array object. Without them, it would be just too dangerous to use the containers on indefinite types (which was one of the major purposes behind them). One could get rid of them if one had sufficient proof capabilities to detect problems statically (which probably would require a different containers definition, since the current definition doesn't tell you what container is being read). One certainly can get rid of a lot of the checks associated with Reference/Constant_Reference simply based on how they're used (but of course that requires front-end support). I don't buy that the safety is really hurting users because every case where a tampering check is made is potentially dangerous. I'd like to see an example of these supposely extra errors "when manipulating temp object". Note that one reason that the tampering checks are as conservative as they are is to limit dependency on the underlying implementation. For instance, an implementation of a list that uses separate nodes probably wouldn't have problems with a modification so long as it isn't of the node itself or an adjacent node. But we wanted to allow other implementations as well, so we don't make the checks that specific. If we got rid of the tampering checks altogether, users (and implementers!) would be effectively tied to a particular implementation strategy -- since what would work in one implementation might cause a crash in another -- testing would be insufficient to guarentee portability (you can't really test for the absence of erroneousness). I'm in favor of the idea of allowing suppression of the tampering checks (we allow suppression of a lot of other things and the sky doesn't fall), but I want the default to remain safe. It certainly will in our compiler. *************************************************************** From: Bob Duff Sent: Tuesday, October 7, 2014 10:04 AM > > X : Elems_Array renames Elems (V) (1 .. Last_Index (V)); > > ... -- operate on X, but don't do Append (etc) while X still > > exists > > If course, if "trusting the programmer" was a good enough way to do > development, we wouldn't need Ada and all of the static and dynamic > checks that it provides. After all, if you are "in the habit" of doing > things right, any old programming language will do. I think your analogy is inapt. For array indexing (say), you can't prevent out-of-bounds indexing via any "habits" -- every indexing operation is an opportunity for making a mistake, and run-time checks help. In contrast, the above renaming habit is easy to follow, and (IME) effective in preventing bugs. No guarantees, of course. *************************************************************** From: Randy Brukardt Sent: Wednesday, October 8, 2014 11:57 PM > I think your analogy is inapt. For array indexing (say), you can't > prevent out-of-bounds indexing via any "habits" -- every indexing > operation is an opportunity for making a mistake, and run-time checks > help. I disagree that there is a huge difference. Even for array indexing, there are "habits" that you can use to reduce error, at least in Ada: "always use the 'Range attribute when iterating", "always use a membership after calculating an array index". > In contrast, the above renaming habit is easy to follow, and > (IME) effective in preventing bugs. No guarantees, of course. It's only effective if every subprogram you call in the scope of the renames knows about the "habit". Which is hard in a project of any size, where someone (including you) might add something down the road that breaks the "habit" without even realizing that it is called from such a region. I tend to think that any requirement on a programmer that isn't checked either at compile-time or runtime is a bug waiting to happen. I know I've regretted many, many shortcuts that we've taken over the years (and the above is a shortcut at best). But I know you don't think that way (you don't buy the seatbelt analogy, while I wouldn't consider suppressing checks and assertions in production code unless performance needs required that, and even then I often try to eliminate or hoist the checks by adjusting the code rather than suppressing them). *************************************************************** From: Bob Duff Sent: Tuesday, October 7, 2014 10:09 AM >... The ARG needs to address the efficiency of the current containers. That's as may be, but you're not going to get efficiency by chatting in ARG meetings, nor emailing arg@. Experimentation is the only way. On the other hand, the issue of two tasks having read-only access to a container is probably appropriate for ARG discussion. Even there, I'd like to see efficiency experiments before final decisions are made. *************************************************************** From: Tucker Taft Sent: Tuesday, October 7, 2014 11:23 AM >> It is a real drag that iterating over a container seems to require >> setting one or more flags to prevent tampering, which seems to >> require some sort of trick to update a possibly read-only container, >> as well as introducing race conditions when concurrent tasks are >> iterating over the same container, etc. > > I think we need a better problem statement than "it is a real drag". > :-) In particular, there's no need to worry about race conditions with > concurrent tasks, since any uncontrolled access is erroneous anyway, > and if the access is properly controlled, the operations will happen > sequentially anyway. The idea was that if we don't require implementations to detect tampering by other tasks, then you can create a tampering check that is local to a given task, and does not introduce a race condition by directly modifying the container being iterated. > I don't like introducing additional erroneous cases even when you do > everything right (in this case, use appropriate task signaling). > Moreover, it seems that the idea of allowing suppression of tampering > checks also covers this area (because with the checks suppressed, any > violation of tampering is erroneous). So I don't see this is adding > anything, but perhaps that's because I don't understand the problem you're trying to solve. I am trying to make the 99% case more efficient, where the (presumably unintended) tampering is done by the task doing the iterating. If you have to protect against a different task coming in and doing the tampering, then you have to create some kind of global synchronized flag indicating that an iteration is occurring. Similarly, you will need a complex synchronized flag if you don't want a race condition when two separate threads iterate over the same container. If we can allow these checks to be local to a task, then there is no need for a synchronized flag. > Moreover, this certainly isn't going to address any performance > problems (this will make the checks more expensive in the general > case, although one could imagine structuring them so they remain cheap > if no objects are in the tampering state). After all, the main > performance problem is using finalization to clear the tampering > state, and this proposal does nothing for that. .. I think it is a serious performance and/or safety problem if you can't allow two tasks to iterate concurrently over the same container. *************************************************************** From: Jeff Cousins Sent: Wednesday, October 8, 2014 7:45 AM > I don't think I have time to do a thorough study right now. In my work on > the pretty printer, I took a different approach. Vectors were WAY too slow. > Instead of figuring out in detail why, I wrote my own Fast_Vectors, which > supports only the operations I needed. E.g. it has Append, but not Insert. In our, admittedly limited, use of Containers, for vectors we use Append but not Insert. *************************************************************** From: Randy Brukardt Sent: Wednesday, October 8, 2014 11:47 PM ... > I am trying to make the 99% case more efficient, where the (presumably unintended) > tampering is done by the task doing the iterating. If you have to protect against > a different task coming in and doing the tampering, then you have to create some > kind of global synchronized flag indicating that an iteration is occurring. (1) Tampering is used for more than just iteration, and most of the problems are in fact not related to iteration. Focusing too closely on iteration will obscure the needed fixes. (2) As I noted with my sample code, that global flag is pretty cheap - it's a single atomic object. > Similarly, you will need a complex synchronized flag if you don't want a race > condition when two separate threads iterate over the same container. No, you just need a test-and-set on the flag. I showed that in my example code (I forgot the test-and-set, but that's mainly because you can't write that in straight Ada). Adding or removing containers from the list just lock it (that is a pretty cheap operation, so there's no point in doing anything fancy). [If you have an optimized protected object as GNAT supposedly does, a protected object used only for exclusion would do the trick too.] > If we can allow these checks to be local to a task, then there is no need > for a synchronized flag. True, but if the cost is to expand erroneous execution even when locks are used to serialize access, that's just nasty. ... > > Moreover, this certainly isn't going to address any performance > > problems (this will make the checks more expensive in the general > > case, although one could imagine structuring them so they remain > > cheap if no objects are in the tampering state). After all, the main > > performance problem is using finalization to clear the tampering > > state, and this proposal does nothing for that. .. > > I think it is a serious performance and/or safety problem if you can't > allow two tasks to iterate concurrently over the same container. Given that allowing multiple tasks to even access the same container is not guarenteed by the language, it's hard to call whatever it takes to do that a "performance" problem. For the perspective of portable code, you simply can't have multiple tasks iterating over the same container. In the absence of a change in what the language requires, performance of things that you can't do is irrelevant. Going forward, there is certainly going to be interest in providing parallel operations on containers. The problem is that the specifications of the containers as currently defined aren't going to work well in conjunction with the features proposed to support parallelism. In particular, (as I discovered when I worked on one of the early global in/out proposals) the fact that the container isn't a parameter to most read operations means that it's not possible to bound what's read in a meaningful manner. And there's not going to be much safe parallelism if global in has to be set to "all". (I would expect that is also a problem with proof, but I'm not an expert on that.) As such, I suspect that we'll need special parallel containers (even for read-only uses) with a somewhat different interface. The existing containers aren't going anywhere (they date back to Ada 2005), but I think it's likely that they'll have to remain mainly for use in single tasking cases. (And a side note: With the tampering checks suppressed, there would be no efficiency problem from those checks, so I don't see a major issue from that. For tasking, you have to use an expensive implementation when the checks are on, but when suppressed you surely wouldn't use that implementation. It's much less intrusive than to introduce additional erroneousness for people that don't need additional performance.) *************************************************************** From: Randy Brukardt Sent: Thursday, October 9, 2014 12:17 AM > >... The ARG needs to address the efficiency of the current containers. > > That's as may be, but you're not going to get efficiency by chatting > in ARG meetings, nor emailing arg@. Experimentation is the only way. Huh? We know (from Ed's reports) that the problem is caused by the finalization required to clear the tampering state after a call to Reference. (Since that integral to the user-defined indexing for the containers, it gets used a lot.) The question is how to get rid of that overhead. That's a language decision, not really an implementation one. There's the possibility of the front-end eliminating that overhead (without any language change) in the case where the creation and finalization of the result of Reference occur with no calls in between. That should be common, as most direct uses of components would qualify: A := List(Cur).Component; However, there certainly would be programs that can't be optimized that way. In particular, any time the result is passed as a parameter, we'd have to assume that the called subprogram could tamper. (That in fact is precisely the case that the checks are intended to catch, because such tampering could destroy the passed object while it is still being used.) It's probably the case that there will exist programs that are still too inefficient even with the possible optimizations. The only way to eliminate the overhead from all programs is to (at the language level) turn off the tampering check. That has to be done on an instantiation-wide basis (because the bulk of the overhead is from the result of the Reference function, and its overhead can only be removed if it knows that there is no place where a tampering check can be expected to fail - that is, there can't be anywhere for the current container where the checks aren't suppressed). There are only two sensible ways to proceed at this point (at least, no one has come up with any other ideas): (1) Define a set of Unchecked_xxx containers, identical except that they have no tampering checks (erroneousness instead for what would have been a failed check). (2) Define an aspect of the instantiation of a container which allows suppressing the tampering checks. An undetected failed check makes the program erroneous, in the normal way for suppressed checks. In both cases, the expected use would be much like pragma Suppress (test with checks on, turn them off for production). When we discussed this in Paris, we were leaning toward #2, but we wanted to get feedback from Ed and others as to whether such an aspect would be too hard to implement (as it would have to essentially chose an alternate body for the generic container). I think we have to get rid of this problem before we can even find out if there are any other performance issues (in the single tasking case), because this one has such an impact. In any case, only the ARG can settle on a final solution to the problem, as a language change of some sort is needed. And the parameters of the problem are well-understood -- I worried about it when it was defined, but became convinced that it wasn't that much more expensive than the other parts of the accessor. Apparently, I was wrong about that -- that's when we needed experimentation, not now. *************************************************************** From: Tucker Taft Sent: Thursday, October 9, 2014 7:40 AM > (1) Tampering is used for more than just iteration, and most of the > problems are in fact not related to iteration. Focusing too closely on > iteration will obscure the needed fixes. > (2) As I noted with my sample code, that global flag is pretty cheap - > it's a single atomic object. ... On a multi-core machine or more generally a multi-processor, updating an atomic object is unfortunately not cheap. *************************************************************** From: Bob Duff Sent: Thursday, October 9, 2014 11:05 AM > Huh? We know (from Ed's reports) that the problem is caused by the > finalization required to clear the tampering state after a call to > Reference. No, we don't know that's THE problem. We know it's A problem, and we can guess that it might well be the biggest problem. But we also know that there are other efficiency problems. >... (Since that integral to the user-defined indexing for the >containers, it gets used a lot.) The question is how to get rid of that >overhead. That's a language decision, not really an implementation one. Sure, we will need some language design work, but we need to start with experimentation. I have some ideas about efficiency, but I'm not going to discuss them here (yet). I assure you I will vote against any change whose purpose is efficiency, unless we have good experimental results. > When we discussed this in Paris, we were leaning toward #2, but we > wanted to get feedback from Ed and others as to whether such an aspect > would be too hard to implement (as it would have to essentially chose > an alternate body for the generic container). Then let's quit chatting about it until Ed and others produce such feedback. > I think we have to get rid of this problem before we can even find out > if there are any other performance issues (in the single tasking > case), because this one is has such an impact. We have to get rid of it as an experiment -- we don't have to worry about RM wording at this point. > In any case, only the ARG can settle on a final solution to the > problem, as ^^^^^ > a language change of some sort is needed. Yes, "final". >...that's when we needed > experimentation, not now. Yes. Let's not repeat the mistake of designing for efficiency without knowing the facts. *************************************************************** From: Randy Brukardt Sent: Thursday, October 9, 2014 3:01 PM > > Huh? We know (from Ed's reports) that the problem is caused by the > > finalization required to clear the tampering state after a call to > > Reference. > > No, we don't know that's THE problem. We know it's A problem, and we > can guess that it might well be the biggest problem. > But we also know that there are other efficiency problems. We do? I've not heard of anything other than the tampering issue for single-tasking use (the 99% case as Tucker put it). I don't consider multitasking use a "performance issue", since the containers were not designed for such use, they're not required to work for such use, and reading without write protection is seriously unsafe IMHO. Ergo, I believe we need special containers for such uses, changing the existing ones makes no sense. As far as single-tasking goes, the containers are just wrappers around what you'd write yourself. It's hard for me to imagine any performance problem with that beyond those caused by implementation choices. (By that I mean things that aren't required by the specification; for instance, my containers implementation contains 99% dangling pointer detection, but that's not required by the standard. I could imagine that in some uses the cost of those checks would be a problem (especially the extra memory used which might be significant for small elements). The checks required are cheap (null cursor and wrong container detection are just single compares, for instance). Those things could only matter on the bleeding edge, and the Ada containers (any containers, for that matter) can never work on the bleeding edge. You have to go to custom code at that point. > >... (Since that integral to the user-defined indexing for the > >containers, it gets used a lot.) The question is how to get rid of > >that overhead. That's a language decision, not really an implementation one. > > Sure, we will need some language design work, but we need to start > with experimentation. I have some ideas about efficiency, but I'm not > going to discuss them here (yet). Quite honestly, I don't think that there is any point to making containers be bleeding edge efficient. There is no possibility that any language-defined package will be able to meet critical needs. The big value of the containers is to off-load the memory management complications; the performance just needs to be good enough so that they can be used in the 95% of non-critical applications. You can *always* do better with a hand-written and tuned algorithm, after all. The issue here is that the tampering on Reference is making it impractical to use in a lot more than 5% of the critical uses. > I assure you I will vote against any change whose purpose is > efficiency, unless we have good experimental results. You are against check suppression? Amazing. That seems like a good idea regardless of whether it solves everyone's performance issues. > > When we discussed this in Paris, we were leaning toward #2, but we > > wanted to get feedback from Ed and others as to whether such an > > aspect would be too hard to implement (as it would have to > > essentially chose an alternate body for the generic container). > > Then let's quit chatting about it until Ed and others produce such > feedback. Knowing Ed, that will never happen, so the above is the same as doing nothing at all. And the griping will continue. I'm sick and tired of people complaining that the containers (and other parts of Ada, too) are not what they never were intended to be. They were intended to be safe and correct for single-tasking use. That's it; it's easier to write them yourself if all you care about it performance. (I can write a simple linked list in 10 minutes, and it will be faster than any container could possibly be.) The advantage of the containers is that they contain checking that you would never bother with in a hand-written data structure and that they handle all of the memory management for you. Performance only matters to the extent that it is significantly worse than one would expect, as with Reference. We were not interested in getting the last ounce of performance out of these - that could only be done by abandoning all of the goals and writing them precisely as most would be hand -- no checking at all, no consistency at all, etc. I'm not remotely interested in seeing such stuff (fast but unsafe containers) in the Standard. I don't even want to waste time talking about them. Moreover, we're surely not going to abandon the current containers (as they were introduced in Ada 2005). So anything new has to be an addition, not a change. (There's no chance of improving the performance without changing the specifications to remove sloth-inducing operations, as anything on that line can be done without involving the ARG in the first place.) So I find performance discussion pointless, with the exception of clearly defined problem areas (in this case, Reference needing to use finalization). For everything else, implementers should simply do it and not complain here. ... > >...that's when we needed > > experimentation, not now. > > Yes. Let's not repeat the mistake of designing for efficiency without > knowing the facts. You said too much: > Let's not repeat the mistake of designing for efficiency. There is a very specific overly expensive check in the current design, we need to address that, and we need to do it immediately so that the containers can be used as intended. Beyond that, I'm strongly opposed to making any changes to the current containers in the name of efficiency. Efficiency was never a goal for these containers, beyond "good enough". And they're "good enough" with the possible exception of the tampering check for Reference. This is just about a "dead body" issue for me - "container churn" is the one thing that we were trying to prevent with Ada.Containers. If we can't even resist tinkering ourselves (and thus breaking people's programs), we're lost. If you or anyone else wants to experiment with their own container design, go to it. There are at least as many container designs as there are people. But that has nothing to do with the Standard. *************************************************************** From: Edmond Schonberg Sent: Thursday, October 9, 2014 4:24 PM >>> When we discussed this in Paris, we were leaning toward #2, but we >>> wanted to get feedback from Ed and others as to whether such an >>> aspect would be too hard to implement (as it would have to >>> essentially chose an alternate body for the generic container). >> >> Then let's quit chatting about it until Ed and others produce such >> feedback. > > Knowing Ed, that will never happen, so the above is the same as doing > nothing at all. And the griping will continue. Thanks for the vote of confidence! In fact, swamped by other tasks (including assorted nits like aspect Default_Storage_Pool, apparently dropped on the floor, and a bevy of impatient customers) I don’t expect to have much time to go back to playing with alternate implementations of containers. A few users that have large computer-intensive programs declared them unusable for their application, and rolled their own. Jeff wrote interesting ACATS tests that made sure that the same heavy-duty finalization machinery is present in all containers. I suspect that over time other libraries will appear, with different interfaces, and be eventually incorporated into RM 2020. These will not have tampering checks. If customer demand increases we might explore optimizing some typical loops, but right now this has priority epsilon. *************************************************************** From: Randy Brukardt Sent: Thursday, October 9, 2014 4:50 PM > > Knowing Ed, that will never happen, so the above is the same as > > doing nothing at all. And the griping will continue. > > Thanks for the vote of confidence! Sorry about that. I should know better than to take my annoyance with one person out on some bystander. But... > In fact, swamped by other > tasks (including assorted nits like aspect Default_Storage_Pool, > apparently dropped on the floor, and a bevy of impatient customers) I > don't expect to have much time to go back to playing with alternate > implementations of containers. A few users that have large > computer-intensive programs declared them unusable for their > application, and rolled their own. Jeff wrote interesting ACATS > tests that made sure that the same heavy-duty finalization machinery > is present in all containers. I suspect that over time other > libraries will appear, with different interfaces, and be eventually > incorporated into RM 2020. These will not have tampering checks. If > customer demand increases we might explore optimizing some typical > loops, but right now this has priority epsilon. ...you then essentially agree with my point. :-) You're too busy to do the sorts of experiments that Bob seems to be asking for. Which leaves us in a quandary: do we provide a method of suppressing tampering checks in the hopes that it is sufficient to solve the most pressing problems? Or do we wait for Godot to attempt to solve this? I know where I stand: suppressing checks has a long history in Ada specifically for performance improvement. Redesigning the existing containers isn't an option for them (ever), and leaving them with performance that is not "good enough" for the Reference case makes no sense. I.e., the proposed suppression aspect is a simple fix to the existing problem without destroying safety for all or requiring a wholesale redesign. BTW, a proper multitasking container doesn't need tampering checks, as an attempt to write a container being read would simply be blocking. The tampering situation for a different task would just wait, and the same task would then cause deadlock. (The downside being that the locking would need similar management to the tampering checks, so I don't know if it's really possible to increase the performance.) A container without either checks or locks does not belong in the standard, IMHO. (There are lots of private containers out there, and these might be best as one of those.) *************************************************************** From: Randy Brukardt Sent: Monday, October 12, 2015 6:06 PM > My homework AI on thread-safe libraries..... Interesting. It doesn't seem to go far enough, IMHO, as there doesn't seem to be any indication of what ought to work and what can deadlock. For instance, consider the call-back version of the iterators in the various Ada.Containers. Is it required that one can make a call back into the container from the call-back? If not, these protected libraries aren't going to be very useful (most useful code will deadlock), and if so, the wording better make it clear what's expected. Especially as clearly one can construct programs that will deadlock in the face of an locking scheme that one could imagine using for the containers (especially easy if we allow the tampering check to be suppressed for performance reasons). Similarly, can one modify individual components of a container in parallel, or not? Explain your answer. ;-) "Within Ada.Protected and its child units, implementations shall ensure the implied atomicity of operations on global ressources and the visibility of changes across the boundaries of concurrent units as implied by atomic changes to shared ressources." What's "implied atomicity" mean?? I don't think there is anything "implied" here. I think it would be much better if this was written as a real requirement in Ada terms (I realize that's much harder, but that's the point). Basically, I think this would be a full employment act for the ARG, because it would take years to "interpret" the meaning of this on each and every language-defined library (at least the non-pure ones). I doubt that there are many where it would be obvious. *************************************************************** From: Tucker Taft Sent: Monday, October 12, 2015 8:40 PM > My homework AI on thread-safe libraries..... Alas, "protected" is a reserved word... ;-) Language-defined packages are already required to be thread safe to some degree. I would suggest we focus our energies on the particular packages that pose a real problem for the user. The whole notion of "Current_Output" and friends is bizarre in a multi-threaded program, so that one really can't be fixed, unless we make it per-task, I suppose, which is certainly not providing "equivalent" thread-safe functionality. In fact, it seems that in several cases these will not be equivalent in functionality. Perhaps the fundamental question is: What is the real problem this AI is trying to solve? It might really help if the "!problem" presented some examples of real problems that typical programmers face, and discussed some of the alternative solutions already available, and the cases where the existing solutions are particularly painful. *************************************************************** From: Erhard Ploedereder Sent: Wednesday, October 14, 2015 11:14 AM > The whole notion of "Current_Output" and friends is bizarre in a > multi-threaded program, so that one really can't be fixed, unless we > make it per-task, I suppose, which is certainly not providing > "equivalent" thread-safe functionality. Well, with two threads writing a string to Current_Output, I would rather have a guarantee not to get (-- forgive the non-Ada strings) "this thiis res isalw loyr basde " and instead get "this is really bad this is worse" or "this is worse this is really bad" That's the point of making calls sequentially consistent, which I think my proposal does. I don't find it bizarre at all to get a race for which string gets outputted first, if I coded my tasks to not coordinate/synchronize. I do find it bizarre, however, to get gibberish seemingly unrelated to my calls. As to the rest, I tried to pick that up in the revised AI. *************************************************************** From: Erhard Ploedereder Sent: Wednesday, October 14, 2015 10:56 AM Delivered: Wednesday, October 28, 2015 9:16 PM -- it was caught in the spam filter Here is revision [this is version /02 of the AI - Editor] responding to comments about - deadlock by callback - reserved name of package - more rationale needed - the alternative of making selected units thread-safe *************************************************************** From: Erhard Ploedereder Sent: Wednesday, June 8, 2016 8:53 PM Delivered: Thursday, June 16, 2016 8:37 PM -- it was caught in the spam filter [It helps to send updates *before* the meeting agenda deadline, when the editor is in the office to ensure that they get posted and distributed - Editor.] This is V3 of AI-12-0139, Thread-safe libraries or, at least, containers [this is version /03 of the AI - Editor]. It includes V2, the version not seen in Burlington, plus the wording of a prototype of a package with more explicit and more refined synchronization properties, since that was my homework assignment. I chose Hashed_Maps and created Safe.Containers.Hashed_Maps with a Read-Write-Lock scheme. You find the package wording at the end of the !wording section. I have one question: I suspect that the set of "tampering" operations is the set of all "modifying" accesses to maps, cursors and iterators. True or false? i.e., are there modifying ops that are not tampering? *************************************************************** From: Randy Brukardt Sent: Monday, July 11, 2016 8:30 PM Not sure if Erhard ever got proper answers to his questions in this draft, so here they are... Erhard Ploedereder wrote: > I have one question: I suspect that the set of "tampering" > operations is the set of all "modifying" accesses to maps, cursors and > iterators. > True or false? i.e., are there modifying ops that are not tampering? Tampering covers modification of the container (that is, insert, delete, etc.) but not modification of the data of an element IN the container. Specifically, tampering allows writing the contents of an element (otherwise, one couldn't write a loop that changes all elements of a container, a capability that seems important). I suspect that means that tampering isn't enough for concurrency purposes, but I do think it is a proper subset (so the rules given in your proposal are fine). Aside: I think we would need a better definition of "modifying access" for the purposes of these rules; remember that the language has to be written without regard to the possible implementation of the bodies of these packages. I would probably define "modifying access" as tamper-with-elements plus writing an element via Reference, Replace, or Update_Element. (Of course, Tucker wants to get rid of tamper-with-elements in general, so it gets more complex if one has to effectively put that back for this case.) In the AI, you have: <<< Note to ARG: Semi-unrelated RM observation: Several of the present container packages contain dynamic semantics under the heading of static semantics. E.g. A.18.24 (7/3). Which I why I did not bother distinguishing either, but I did leave out the heading of "static semantics" present in other packages. This is a well-known bug in the RM -- ALL language-defined packages have their semantics defined in a Static Semantics section (even though 95% of that is really Dynamic Semantics). We've discussed this several times, and each time decided to continue to follow the (argubly wrong) precedent rather than spending months trying to fix it by separating Static and Dynamic semantics for packages. (Such a fix would be a lot of work, and it would provide exactly no benefit to Ada users or implementers. Only true pedants would care.) So the text in this case should all be under Static Semantics, even though that is of course nonsense. *************************************************************** From: Erhard Ploederder Sent: Wednesday, June 7, 2017 9:08 PM Here is AI12-0139-1, updated to /04. (My homework). I edited as requested in the minutes, my related questions are marked in the text of the AI. I added a few clarifications. The minutes propose that the types of the old and new packages should be compatible. I did not make that change, because this then would allow mixing operations from Task_Safe and original packages to work on the same objects. Clearly, this cannot possibly work, if the former protect by lock but the other do not. On the contrary, these types need to be kept apart "at all cost". Raphael did not propose a specific set of packages, so a narrowing to a subset of packages has not happened yet. Presumably, at least all container packages should be included. However, there are obvious candidates, for which the dual version is unnecessary. Pure packages with subprograms that have only scalar parameters are one example. What is better, though? Uniformity, by having the copy regardless with an implementation that merely replicates the existing package or parsimoniousness, avoiding the copying by an implementer and making the user search in both branches for a package of the functionality (s)he likes? Note that renaming of packages cannot be made an implementation choice; it would have to be prescribed semantics, because of the type issues. *************************************************************** From: Randy Brukardt Sent: Wednesday, June 7, 2017 10:30 PM ... > The minutes propose that the types of the old and new packages should > be compatible. I did not make that change, because this then would > allow mixing operations from Task_Safe and original packages to work > on the same objects. > Clearly, this cannot possibly work, if the former protect by lock but > the other do not. On the contrary, these types need to be kept apart > "at all cost". I think you missed the point of this part of the minutes. The vast majority of language-defined types are either elementary or "open" composite (that is, not any sort of abstraction, like type String). For those types, there could be no difference between a "locking" version and a "normal" version, because there is not going to be any locking in any case. What would a "locking" type Boolean do that is different from the regular version? Hopefully nothing. In that case, having a proliferation of types that are identical in ALL semantics seems like a bad thing. I don't want two versions of Integer, or Boolean, or Interfaces.C.Int, or Ada.Strings.Alignment, with all of the problems of deciding what to use and the issues of interoperability. You're right of course that the types that actually have some locking semantics should be different. But there should not be that many such types. (That of course depends on which packages end up with Task_Safe versions.) Ideally, one could use, say, the Task_Safe Text_IO with the normal vector container, as the performance characteristics of these packages are going to be very different. I doubt that anyone would want to use a fully locked container implementation in any code that proves to matter to performance. (Of course, there is a lot of non-performance critical code out there, so that doesn't have anything to do with whether or not these packages are a good idea in the first place.) *************************************************************** From: Randy Brukardt Sent: Thursday, June 8, 2017 11:27 PM > I edited as requested in the minutes, my related questions are marked > in the text of the AI. I added a few clarifications. From the AI: ... For containers, the Stable nested package will acquire exclusive access to the underlying upon creation, with no further synchronization associated with individual operations. <<< I have no idea what the last sentence tries to say, but I copied it faithfully from the minutes. What Stable nested package and what underlying ... ? If I guess at what it is traing to say, it would completely void the purpose of this AI, since the creator task would own the container exclusively forever and this would explicitly prevent shared use of the container by multiple tasks altogether. >>> The Stable subpackages are the ones proposed in AI12-0111-1 to eliminate tampering and other overhead. The idea of the note was to ensure that the Stable views, at least, are efficiently implemented (that is, get the lock when the Stable view is created). Note that a Stable view is essentially the same as getting setting the tampering flag: no changes to the container are allowed while it exists. (Of course, one still can change components of an element; tampering/Stable only prevents adding/removing/changing the bounds/discriminants of elements.) The creator package is one that would never own a stable view of a container; that's only usable for *reading* a container. Writing operations are only possible when no other task owns a Stable view (or it doing any thing that requires a tampering check; they're rather equivalent) - presumably they'd be locked out. In any case, this is in addition to the fine-grained locking of individual operations; it's not exclusive! (If no one uses Stable views, or we don't end up adding them, the sentence has no effect at all.) ---- From the AI: <<< Note to ARG: Semi-unrelated RM observation: Several of the present container packages contain dynamic semantics under the heading of static semantics. E.g. A.18.24 (7/3). Which I why I did not bother distinguishing either, but I did leave out the heading of "static semantics" present in other packages.>>> I think I've previously answered this, but the RM never uses Dynamic Semantics to describe language-defined packages. This seems like a mistake - virtually everything about such packages are Dynamic Semantics - but it would be a terrible idea to have a few packages with Dynamic Semantics heading and most without. (And changing all of them is impractical because the old Scribe describes these as sections, with @begin and @end parts: they're not headers that can be moved easily -- the only way to change the classification of an existing paragraph is to delete it and reinsert it somewhere else -- which necessarily changes the paragraph numbers.) ---- From the AI: No tampering checks are performed. <<< Note to ARG. The following paragraph is written so that tampering code blocks temporarily rather than fail permanently. If I did not catch all cases, let me know and please provide words to include the missed ones.>>> You do know that means that a task that does something that would fail a tampering check (it's own) would deadlock instead in the Task_Safe version? That's about the nastiest way for a task to fail; we had massive problems with this in Claw (the programs in question were actually wrong, but figuring that out from a deadlock was near impossible). We ended up putting some of lock waits on timers so that they would raise an exception rather than deadlock. That was OK for Claw (where a delay of more than a couple seconds processing the GUI is essentially the same as a failure as the GUI would be non-responsive), but it probably wouldn't be OK for the containers (whether a 10 second delay is acceptable or not is not something the implementer can know). Based on that experience, I personally think anything that is designed to fail by deadlock is unusable. YMMV. *************************************************************** From: Raphael Amiard Sent: Monday, June 12, 2017 3:57 AM > Raphael Amiard: > http://www.ada-auth.org/ai-files/minutes/min-1610.html#Amiard > AI12-0139-1 (determine which language-defined units would > benefit from having task-safe versions) Here is my homework for this AI. YES -> would benefit from task safe version DEFAULT -> Should be task safe by default NO -> No need Ada.Assertions (Ada 2005) YES Ada.Asynchronous_Task_Control NO (already safe) Ada.Calendar NO (no need) Ada.Calendar.Arithmetic (Ada 2005) NO Ada.Calendar.Formatting (Ada 2005) NO Ada.Calendar.Time_Zones (Ada 2005) NO Ada.Characters NO (Pure functions) Ada.Characters.Conversions (Ada 2005) NO (Pure functions) Ada.Characters.Handling NO Ada.Characters.Latin_1 NO (constants) Ada.Command_Line DEFAULT Ada.Complex_Text_IO (Ada 2005) YES All containers should have a task safe version Ada.Containers (Ada 2005) YES Ada.Containers.Doubly_Linked_Lists (Ada 2005) YES Ada.Containers.Generic_Array_Sort (Ada 2005 generic procedure) YES Ada.Containers.Generic_Constrained_Array_Sort (Ada 2005 generic procedure) YES Ada.Containers.Hashed_Maps (Ada 2005) YES Ada.Containers.Hashed_Sets (Ada 2005) YES Ada.Containers.Indefinite_Doubly_Linked_Lists (Ada 2005) YES Ada.Containers.Indefinite_Hashed_Maps (Ada 2005) YES Ada.Containers.Indefinite_Hashed_Sets (Ada 2005) YES Ada.Containers.Indefinite_Ordered_Maps (Ada 2005) YES Ada.Containers.Indefinite_Ordered_Sets (Ada 2005) YES Ada.Containers.Indefinite_Vectors (Ada 2005) YES Ada.Containers.Ordered_Maps (Ada 2005) YES Ada.Containers.Ordered_Sets (Ada 2005) YES Ada.Containers.Vectors (Ada 2005) YES Ada.Decimal NO (Pure functions) Ada.Direct_IO YES Ada.Directories (Ada 2005) YES (Directory search) Ada.Dispatching (Ada 2005) NO (already safe) Ada.Dispatching.EDF (Ada 2005) NO (already safe) Ada.Dispatching.Round_Robin (Ada 2005) NO (already safe) Ada.Dynamic_Priorities NO (already safe) Ada.Environment_Variables (Ada 2005) YES Ada.Exceptions NO Ada.Execution_Time (Ada 2005) NO (pure functions) Ada.Execution_Time.Timers (Ada 2005) YES Ada.Execution_Time.Group_Budgets (Ada 2005) NO Ada.Finalization NO Ada.Float_Text_IO YES Ada.Float_Wide_Text_IO YES Ada.Float_Wide_Wide_Text_IO (Ada 2005) YES Ada.Integer_Text_IO YES Ada.Integer_Wide_Text_IO YES Ada.Integer_Wide_Wide_Text_IO (Ada 2005) YES Ada.Interrupts YES Ada.Interrupts.Names NO (no need) Ada.IO_Exceptions NO Ada.Numerics NO Ada.Numerics.Complex_Arrays (Ada 2005) YES ? Ada.Numerics.Complex_Elementary_Functions NO (Pure functions) Ada.Numerics.Complex_Types YES ? Ada.Numerics.Discrete_Random YES Ada.Numerics.Elementary_Functions No (Pure functions) Ada.Numerics.Float_Random YES Ada.Numerics.Generic_Complex_Arrays (Ada 2005) YES ? Transitively Ada.Numerics.Generic_Complex_Elementary_Functions YES ? Transitively Ada.Numerics.Generic_Complex_Types YES ? Transitively Ada.Numerics.Generic_Elementary_Functions YES ? Transitively Ada.Numerics.Generic_Real_Arrays (Ada 2005) YES ? Transitively Ada.Numerics.Real_Arrays (Ada 2005) YES ? Transitively Ada.Real_Time NO (no need) Ada.Real_Time.Timing_Events (Ada 2005) YES or already safe ? Ada.Sequential_IO YES Ada.Storage_IO YES Ada.Streams YES Ada.Streams.Stream_IO YES Ada.Strings Ada.Strings.Bounded YES Ada.Strings.Bounded.Hash (Ada 2005 generic function) NO (no need) Ada.Strings.Fixed NO (no need) Ada.Strings.Fixed.Hash (Ada 2005 generic function) NO Ada.Strings.Hash (Ada 2005 generic function) NO Ada.Strings.Maps NO (Pure functions) Ada.Strings.Maps.Constants NO Ada.Strings.Unbounded YES Ada.Strings.Unbounded.Hash (Ada 2005 generic function) NO Ada.Strings.Wide_Bounded YES Ada.Strings.Wide_Bounded.Wide_Hash (Ada 2005 generic function) NO Ada.Strings.Wide_Fixed NO (no need) Ada.Strings.Wide_Fixed.Wide_Hash (Ada 2005 generic function) NO Ada.Strings.Wide_Hash (Ada 2005 generic function) NO Ada.Strings.Wide_Maps NO Ada.Strings.Wide_Maps.Wide_Constants NO Ada.Strings.Wide_Unbounded YES Ada.Strings.Wide_Unbounded.Wide_Hash (Ada 2005 generic function) NO Ada.Strings.Wide_Wide_Bounded (Ada 2005) YES Ada.Strings.Wide_Wide_Bounded.Wide_Wide_Hash (Ada 2005 generic function) NO Ada.Strings.Wide_Wide_Fixed (Ada 2005) NO Ada.Strings.Wide_Wide_Fixed.Wide_Wide_Hash (Ada 2005 generic function) NO Ada.Strings.Wide_Wide_Hash (Ada 2005 generic function) NO Ada.Strings.Wide_Wide_Maps (Ada 2005) NO Ada.Strings.Wide_Wide_Maps.Wide_Wide_Constants (Ada 2005) NO Ada.Strings.Wide_Wide_Unbounded (Ada 2005) YES Ada.Strings.Wide_Wide_Unbounded.Wide_Wide_Hash (Ada 2005 generic function) NO Ada.Synchronous_Task_Control NO (already safe) Ada.Tags NO (pure functions) Ada.Tags.Generic_Dispatching_Constructor (generic function) NO Ada.Task_Attributes NO (already safe) Ada.Task_Identification NO (already safe) Ada.Task_Termination (Ada 2005) NO (already safe) Ada.Text_IO YES Ada.Text_IO.Bounded_IO (Ada 2005) YES Ada.Text_IO.Complex_IO YES Ada.Text_IO.Decimal_IO (Nested package of Ada.Text_IO) YES Ada.Text_IO.Editing YES Ada.Text_IO.Enumeration_IO (Nested package of Ada.Text_IO) YES Ada.Text_IO.Fixed_IO (Nested package of Ada.Text_IO) YES Ada.Text_IO.Float_IO (Nested package of Ada.Text_IO) YES Ada.Text_IO.Integer_IO (Nested package of Ada.Text_IO) YES Ada.Text_IO.Modular_IO (Nested package of Ada.Text_IO) YES Ada.Text_IO.Text_Streams YES Ada.Text_IO.Unbounded_IO (Ada 2005) YES Ada.Unchecked_Conversion (generic function) NO Ada.Unchecked_Deallocation (generic procedure) YES or DEFAULT Unchecked_Deallocation might already be task safe on most native implementations, because the C malloc/free are task safe. To be verified. Could not find anything in the RM about existing task safety. Ada.Wide_Characters (Ada 2005) NO Ada.Wide_Text_IO YES Ada.Wide_Text_IO.Bounded_IO (Ada 2005) YES Ada.Wide_Text_IO.Complex_IO YES Ada.Wide_Text_IO.Decimal_IO (Nested package of Ada.Wide_Text_IO) YES Ada.Wide_Text_IO.Editing YES Ada.Wide_Text_IO.Enumeration_IO (Nested package of Ada.Wide_Text_IO) YES Ada.Wide_Text_IO.Fixed_IO (Nested package of Ada.Wide_Text_IO) YES Ada.Wide_Text_IO.Float_IO (Nested package of Ada.Wide_Text_IO) YES Ada.Wide_Text_IO.Integer_IO (Nested package of Ada.Wide_Text_IO) YES Ada.Wide_Text_IO.Modular_IO (Nested package of Ada.Wide_Text_IO) YES Ada.Wide_Text_IO.Text_Streams YES Ada.Wide_Text_IO.Unbounded_IO (Ada 2005) YES Ada.Wide_Wide_Characters (Ada 2005) NO Ada.Wide_Wide_Text_IO (Ada 2005) YES Ada.Wide_Wide_Text_IO.Bounded_IO (Ada 2005) YES Ada.Wide_Wide_Text_IO.Complex_IO (Ada 2005) YES Ada.Wide_Wide_Text_IO.Decimal_IO (Nested package of Ada.Wide_Wide_Text_IO) YES Ada.Wide_Wide_Text_IO.Editing (Ada 2005) YES Ada.Wide_Wide_Text_IO.Enumeration_IO (Nested package of Ada.Wide_Wide_Text_IO) YES Ada.Wide_Wide_Text_IO.Fixed_IO (Nested package of Ada.Wide_Wide_Text_IO) YES Ada.Wide_Wide_Text_IO.Float_IO (Nested package of Ada.Wide_Wide_Text_IO) YES Ada.Wide_Wide_Text_IO.Integer_IO (Nested package of Ada.Wide_Wide_Text_IO) YES Ada.Wide_Wide_Text_IO.Modular_IO (Nested package of Ada.Wide_Wide_Text_IO) YES Ada.Wide_Wide_Text_IO.Text_Streams (Ada 2005) YES Ada.Wide_Wide_Text_IO.Unbounded_IO (Ada 2005) YES *************************************************************** From: Erhard Ploedereder Sent: Monday, June 12, 2017 5:49 PM > What would a "locking" type Boolean do that is different from the > regular version? Hopefully nothing. Under lock: surely a value manifested in memory. not under lock: quite likely cached in a register. *************************************************************** From: Randy Brukardt Sent: Monday, June 12, 2017 6:06 PM We have aspect Atomic for that, and given that aspect is very expensive (due to the need to use fences), you surely would not want to apply it to every object in a program. (Volatile is not enough for any useful guarentees.) Ergo, you need the unlocked version for most uses. Similarly, there is no sane way to make a task-safe String, given that one can access individual components, slices, and the whole thing, presumably at one time. To do so, you'd have to make it private, but of course that's impossible for the existing data types. *************************************************************** From: Erhard Ploedereder Sent: Monday, June 12, 2017 6:04 PM > The Stable subpackages are the ones proposed in AI12-0111-1 to eliminate > tampering and other overhead. The idea of the note was to ensure that the Stable > views, at least, are efficiently implemented (that is, get the lock when the > Stable view is created). Note that a Stable view is essentially the same as > getting setting the tampering flag: no changes to the container are allowed > while it exists. (Of course, one still can change components of an element; > tampering/Stable only prevents adding/removing/changing the bounds/discriminants > of elements.) I got it. Will fix (eventually) once I have really understood which ops are not tampering and yet making changes to the container that need to be synchronized. I was hoping for "none", but the last meeting said otherwise, so Stable containers seems to be more that just read-only (regrettably). *************************************************************** From: Randy Brukardt Sent: Monday, June 12, 2017 6:25 PM There are two sides to tampering: Only writes of various kinds can tamper (and not all writes are considered tampering, for instance writing through the result of Reference is not tampering - only writes that add, delete, or change the shape of an element are tampering). Any operation that needs to hold onto an element or position for a long time (via call-back or returning a reference) - regardless of whether it is a read or a write - "prohibits tampering" in order that changes to the container avoid causing erroneous execution. You only get an exception (or locking from tampering) when tampering is prohibited AND an operation that tampers is executed. Hope this helps. *************************************************************** From: Erhard Ploedereder Sent: Thursday, June 15, 2017 12:02 PM > In that case, having a proliferation of types that are identical in > ALL semantics seems like a bad thing. I don't want two versions of > Integer Now that you mention it ... I did not think about task-safeness applying to package Standard. But that is actually a neat idea! C++ pre-defines a rather full complement of atomic scalar(?) types, e.g., std::atomic_int, and even std::atomic_bool for the reasons explained in an earlier message, i.e., to guarantee race-free modification of their values (which is explitly not guaranteed for other "normal" types). They are the result of applying a template, which can also be applied to user-defined types, e.g. pointer types. ***************************************************************