Hi,
I am working on implementing a Lindaspace, for fun.
The data that have to be thread-safe, are the tuple themselves, which are stored.
I thought to represent tuples as an unconstrained array type of access to a Storable class-wide type. Storable is an interface extended with whatever data type, to make a really heterogenous data structure. As for the pattern matching feature of linda’s primitives (“Copies a tuple that matches a given pattern from the tuplespace”), I’ll build an array of Tag values that matches the argument, and compares it with the content of the store. For the store, I thought of a indefinite vector, but I could go with a vector of stacks representing present Tag patterns too.
The tuple are the resources to be synchronized. So they should be housed in their own protected object, initialized with an access value of the storage container, ok.
If I can implement a synchronized interface with a concurrent type but its primitives with normal subprograms, I cannot do the opposite. I cannot implement the interface with a normal tagged type, and implement primitives with calls from entries or protected operations.
I would be useful because I rather see synchronization as a property of the primitives, not the type itself. But at the same time the controlling parameter has to be the store, because it is what does the research and storing.
What scheme do you advise ?
with Store;
private with Ada.Containers.Vectors;
generic
with package actualStore is new Store (<>);
package tupleSpacePackage is
use actualStore;
type tuple is array (Positive range 1..<>) of access Storable'Class;
type tupleSpace is synchronized interface;
procedure Out_Operation (L: in out tupleSpace; T: tuple) is abstract;
-- with Nonblocking;
procedure In_Operation (L: in out tupleSpace; T: Tuple) is abstract
with Synchronization => By_Entry;
-- with Nonblocking => False,
procedure RD_Operation (L: tupleSpace; T: out tuple) is abstract
with Synchronization => By_Entry;
-- with Nonblocking => False,
procedure Inp_Operation (L: in out tupleSpace; T: Tuple) is abstract;
-- with Nonblocking;
procedure RDP_Operation (L: tupleSpace; T: out Tuple) is abstract;
-- with Nonblocking;
end tupleSpacePackage;
Since we know what operation is blocking or not, I thought Nonblocking would come handy but I get “Nonblocking” is not a valid aspect identifier" so I commented it out.
My book only touches on Ada 2005 yet, but I’ll finish it before attacking other works on concurrency etc. More modern features. But still I’d rather do this right.
I would not expose pointers and forget about synchronized as you should not do anything complex in a protected action.
If a tuple cannot be an array, then make it private. Moreover if you do that you could deploy schemas to avoid copying on assignment and have eager pool allocation, e.g. by using handles to the tuple vector. Same applies to the tuple elements.
As for task safety, just use a mutex. At the beginning of an operation seize the mutex using a holder object. That is all.
Mutex (seize/release) is two protected actions instead of one, so there is no performance hit. And before entering fruitless discussion about deadlocks observe that protected actions are far ore restricted in terms what you can call from, so you will get an erroneous execution before you blink.
Note that mutex need to be reentrant to allow nested operations. Internal private operations can be made unsafe assuming them running under the mutex. Mutex implementation is almost trivial, I leave it to you.
You could use a protected object, you could also use Task — it’s not really propounded on in tutorials, but you can use a Task to implement (and enforce) a protocol… mutual exclusion is one such protocol:
Task Mutual_Exclusion is
Entry Seize;
Entry Release;
Entry Done;
End Mutual_Exclusion;
Task Body Mutual_Exclusion is
Finished : Boolean:= False;
Begin
Loop
Exit when Finished;
select
accept Seize;
-- INSERT MUTEX CODE HERE.
accept Release;
or
accept Done;
Finished:= True;
end select;
End loop;
End Mutual_Exclusion;
Monitors are extremely slow. Ada 95 did really good job introducing protected objects.
Here is some rant.
I really wonder what the incoming parallel loops and blocks would be.
The background is my present project to implement arbitrary precision arithmetic for Simple Components. I added parallel algorithms for multiplication and modular exponentiation, the latter is a major performance eater, backed by a pool of tasks. All algorithms: direct classroom, Karatsuba, Montgomery domain CIOS and Dussé-Kaliski become dramatically slower when executed on 16 cores in parallel. The tasking overhead is just too big.
I guess that the problem is in the OS scheduling intervals. When you queue a rendezvous you get blocked until the next rescheduling event which under Windows 10ms by default (can be reduced to 1ms). To compare modular squaring, the main part of exponentiation is about 4.6 microseconds on relatively large numbers. Again, this is only a guess. I stay corrected.
If new parallel constructs would be backed by OS threads, they will be utterly useless. I hope the compiler would rather compile into some scalar instructions or GPU co-processor, but that is out my league.
They don’t have to be, IIRC.
There was some research which (again IIRC/IIUC) would allow Ada’s Task to be “promoted”/“converted” to something very like protected objects: passive tasks.
This is perhaps one of the big failings of Ada development as a language, in practice: the refusal to buy-in on something that is correct Ada, able to be processed on all Ada compilers with the “special form” being usable/more-efficient on that particular implementation. (semi-e.g. Imagine if NVidia had produced the initial CUDA with an Ada compiler where the “put it on the GPU” was simply Pragma CUDA( The_Task );.) — This is, I think, partly on the way of being addressed with/by SPARK…at least potentially. (There is a strong possibility that SPARK will stop essentially as-is and be used merely as a check for “Ok, we can turn off these checks”, rather than being fully integrated into the compiler and optimizer.)
Sure, protected objects are useful.
I don’t know.
I don’t think that it would be nearly as big a pain-point in a new Ada implementation, with an eye toward designing it in such a way. — Honestly, parallel is a good reason there should be something like DIANA (a standardized internal-representation) along with an executor (i.e. VM/interpreter), for to facilitate bootstrapping as well as porting: make it easy to write your Ada compiler in Ada.
I think I understand where you’re coming from, but I fundamentally disagree: much of the militation on having better OSes is because of the catering to “how we do things in C/C++” — while it’s not an OS, a good example can be made from WASM: instead of defining the system with parallel-amiable containers [instead of arrays], and some sort of Ada task-like construct, and something like Ada’s generic parameterization (although more robust, like [IIUC] O’Caml’s), they instead went with “Let’s make our minimum viable product ‘it can run this C++ compiler’s output’.”
Hmm, Ada always allowed tasks implemented independent on OS threads. The problem with that was I/O. Any blocking would block all tasks.
Any implementation deviating from OS must have limitations akin protected objects have. Lack of limitations is paid by performance. So, monitors are slow, but you can do anything from there. Protected actions are fast, but you can do almost nothing.
I think you misunderstood: I wasn’t talking about shoehorning in CUDA support to GNAT, but if NVidia’s initial CUDA implementation had been an Ada compiler, not a C compiler with special pragma/directives.
Since “POSIX threads” are nothing but a layer over native Windows threads it is to expect that an implementation using Win32 API would be insignificantly faster. The layer would do some useless POSIX stuff additionally to raw CreateThread. I also remember than some POSIX/UNIX-esque Windows calls leak. I forgot which.
In any case this has no effect of thread scheduling.
I think I’ll do without the whole debate this time… Too early and I have already enough difficulty with grasping concurrency and the associated constructs. I’ll leave the can of worm for later.
So I’ll just stick to my practical issues at hand: how do we use Nonblocking, to tell that not all primitives of a synchronized interface will be blocking ?
Keep in mind that the aspect is brand new, so it may not be implemented in GNAT yet. I noticed a lot of their files have it in there, but commented out, so I am assuming they are still working on it.
I don’t know if this is useful, but the Ada 22 overview has a page of discussion on it:
REF: Defining Nonblocking
If you check the index of that document there are 4 or 5 other sections that also briefly touch on it and some have code examples.
I noticed a lot of their files have it in there, but commented out
Right, I should have thought of that ! Now I’ll remember to look whenever something should by all means work. Next: it might be buried in the RM but how do containers deal with tasks ? Precisely, what happens if two tasks insert an element in a vector at the same time ? Do I need to protect the container ?
And I have the “rd” operation, which copies a tuple from the tuplespace. The documentation says it should be blocking until there is a matching pattern. But it does not modify the protected object, its a read-only operation. How can I make a read-only operation blocking, since entries require a out or in out parameter ? I want the API to function like an entry (be abortable or select-ed) whose guard is the presence or absence of another tuple of the same pattern. But second problem… guards can’t use parameters.
I know I’m overthinking btw. Please indulge me, I want to make a good tuplespace.
The majority of containers are not task safe. Notable exceptions are the synchornized queues. But in general, if you are using something like an Ordered_Map, Vector, etc. then those are not task safe. You’ll need to wrap its use into a protected object or a task. I don’t think the intent is to bury the info though. They have a lot of language keywords for tasking/context switching now (protected, synchronized, task) so my intuition is they would put those front and center either in the package name or in the public type definition. They would want people to know they are task safe. Older stuff though, I am less sure about.
package Ada.Containers.Ordered_Maps
with Preelaborate, Remote_Types, Nonblocking, Global => in out synchronized
I tried to read about those keywords, I frankly don’t understand much yet… What would the above mean for instance ? I reckon Remote_types means the package body has to be copied between partitions, nonblocking means no subprogram or primitive of a type or component of a type declared in it is blocking, but I don’t grasp “synchronized” yet.
Does it explicit that the user is in charge of synchronization, or the opposite ?
The Global aspect deals with any relation to global objects. I’m not a language lawyer, but my instinct this is saying that any global variables/objects associated with this package are update-able (in out) and task safe (synchronized). I would imagine this is to cover dynamic allocation since it is an OS resource, globally available, and can be called by various contexts simultaneously (also note that the bounded versions have global as null, so this reinforces my thought about dynamic allocation). I’d have to dig through the A.I.s probably to see if that is the intent. I don’t think it means the container type itself is synchronized though.
Maybe someone with a better understanding of the RM can comment. Someone like @sttaft maybe would have a better / more accurate explanation.
These aspects are defined in the Ada RM. Take a look in the index. Of course, they might still seem a bit mysterious even after reading their definitions!
Below is the definition of Remote_Types – this merely says that objects of the types declared in the package can be sent across a “wire” to another node on a network, because it has a streamable representation.
E.2.2 Remote Types Library Units
A remote types library unit supports the definition of types intended for use in communication between active partitions.
Legality Rules
When the library unit aspect (see 13.1.1) Remote_Types of a library unit is True, the library unit is a remote types library unit. The following restrictions apply to such a library unit:
it shall be preelaborable;
it shall depend semantically only on declared pure library_items, shared passive library units, other remote types library units, or preelaborated normal library units that are mentioned only in private with clauses;
it shall not contain the declaration of any variable within the visible part of the library unit;
the full view of each type declared in the visible part of the library unit that has any available stream attributes shall support external streaming (see 13.13.2).
Nonblocking means that you can call the operations of instances of this generic from inside a protected operation or a parallel construct, and you won’t hit any potentially blocking operation.
Global => in out synchronized means that by default, the operations declared in the package do not use global variables, or if they do, they properly synchronize their access to them, so that multiple tasks can simultaneously create and manipulate distinct instances of the types declared in an instance of this generic.
Thank you for translating the Legaleese in normal English All clear now.
What is the practice to emulate an entry who guard condition would require reading the parameter ? The purpose here would be to copy a tuple from the tuplespace using its tag pattern, but blocks if none with such pattern exists, until it does. Lke a entry family except of dynamic size, based on a container. Something like (illegal)
entry RD_Operation (T: out Tuple) when V.Contains (To_Tag_Array (T)) is
```.