Tasks provide mid- to high-level functionality for programmers to describe asynchronous workflows. A task is an asynchronously or synchronously executing job; functions exist to create tasks that are executed concurrently, on demand, or in the current thread; to wait for their completion, check their status, and retrieve any results.
Here is a simple example of sorting a list in the background:
gap> task := RunTask(x -> SortedList(x), [3,2,1]);; gap> WaitTask(task); gap> TaskResult(task); [ 1, 2, 3 ]
RunTask dispatches a task to run in the background; a task is described by a function and zero or more arguments that are passed to RunTask. WaitTask waits for the task to complete; and TaskResult returns the result of the task.
TaskResult does an implicit WaitTask, so the second line above can actually be omitted:
gap> task := RunTask(x -> SortedList(x), [3,2,1]);; gap> TaskResult(task); [ 1, 2, 3 ]
It is simple to run two tasks in parallel. Let's compute the factorial of 10000 by splitting the work between two tasks:
gap> task1 := RunTask(Product, [1..5000]);; gap> task2 := RunTask(Product, [5001..10000]);; gap> TaskResult(task1) * TaskResult(task2) = Factorial(10000); true
You can use DelayTask to delay executing the task until its result is actually needed.
gap> task1 := DelayTask(Product, [1..5000]);; gap> task2 := DelayTask(Product, [5001..10000]);; gap> WaitTask(task1, task2); gap> TaskResult(task1) * TaskResult(task2) = Factorial(10000); true
Note that WaitTask is used here to start execution of both tasks; otherwise, task2 would not be started until TaskResult(task1) has been evaluated.
To start execution of a delayed task, you can also use ExecuteTask. This has no effect if a task has already been running.
For convenience, you can also use ImmediateTask to execute a task synchronously (i.e., the task is started immediately and the call does not return until the task has completed).
gap> task := ImmediateTask(x -> SortedList(x), [3,2,1]);; gap> TaskResult(task); [ 1, 2, 3 ]
This is indistinguishable from calling the function directly, but provides the same interface as normal tasks.
Sometimes it can be useful to ignore the result of a task. The RunAsyncTask provides the necessary functionality.
gap> RunAsyncTask(function() Print("Hello, world!\n"); end);;
Hello, world!
Such a task cannot be waited for and its result (if any) is ignored.
Task arguments are generally copied so that both the task that created them and the task that uses them can access the data concurrently without fear of race conditions. To avoid copying, arguments should be made shared or public (see the relevant parts of the section on regions); shared and public arguments will not be copied.
HPC-GAP currently has multiple implementations of the task API. To enable the reference implementation, set the environment variable GAP_STDTASKS to a non-empty value before starting GAP.
RunTask prepares a task for execution and starts it. The task will call the function func with arguments arg1 through argn (if provided). The return value of func is the result of the task.
The RunTask call itself returns a task object that can be used by functions that expect a task argument.
ScheduleTask prepares a task for execution, but, unlike RunTask does not start it until condition is met. See on how to construct conditions. Simple examples of conditions are individual tasks (execution occurs after the task completes) or lists of tasks (execution occurs after all tasks in the list complete).
gap> t1 := RunTask(x->x*x, 3);; gap> t2 := RunTask(x->x*x, 4);; gap> t := ScheduleTask([t1, t2], function() > return TaskResult(t1) + TaskResult(t2); > end); gap> TaskResult(t); 25
While the above example could also be achieved with RunTask in lieu of ScheduleTask, since TaskResult would wait for t1 and t2 to complete, the above implementation does not actually start the final task until the others are complete, making it more efficient, since no additional worker thread needs to be occupied.
DelayTask works as RunTask, but its start is delayed until it is being waited for (including implicitly by calling TaskResult).
RunAsyncTask creates an asynchronous task. It works like RunTask, except that its result will be ignored.
ScheduleAsyncTask creates an asynchronous task. It works like ScheduleTask, except that its result will be ignored.
MakeTaskAsync turns a synchronous task into an asynchronous task that cannot be waited for and whose result will be ignored.
ImmediateTask executes the task specified by its arguments synchronously, usually within the current thread.
ExecuteTask starts task if it is not already running. It has only an effect if its argument is a task returned by DelayTask; otherwise, it is a no-op.
WaitTask waits until task1 through taskn have completed; after that, it returns.
Alternatively, a condition can be passed to WaitTask in order to wait until a condition is met. See on how to construct conditions.
WaitTasks is an alias for WaitTask.
The WaitAnyTask function waits for any of its arguments to finish, then returns the number of that task.
gap> task1 := DelayTask(x->SortedList(x), [3,2,1]);; gap> task2 := DelayTask(x->SortedList(x), [6,5,4]);; gap> which := WaitAnyTask(task1, task2); 2 gap> if which = 1 then > Display(TaskResult(task1));Display(TaskResult(task2)); > else > Display(TaskResult(task2));Display(TaskResult(task1)); > fi; [ 4, 5, 6 ] [ 1, 2, 3 ]
One can pass a list of tasks to WaitAnyTask as an argument; WaitAnyTask([task1, ..., taskn]) behaves identically to WaitAnyTask(task1, ..., taskn).
The TaskResult function returns the result of a task. It implicitly does a WaitTask(task) if that is necessary. Multiple invocations of TaskResult with the same task argument will not do repeated waits and always return the same value.
The CurrentTask returns the currently running task.
This function returns the number of currently running tasks. Note that it is only an approximation and can change as new tasks are being started by other threads.
This function returns true if the task has started executing (i.e., for any non-delayed task), false otherwise.
This function returns true if the task has finished executing and its result is available, false otherwise.
This function returns true if the task is asynchronous, true otherwise.
This function terminates unused worker threads.
HPC-GAP uses a cooperative model for task cancellation. A programmer can request the cancellation of another task, but it is up to that other task to actually terminate itself. The tasks library has functions to request cancellation, to test for the cancellation state of a task, and to perform actions in response to cancellation requests.
CancelTask submits a request that task is to be cancelled.
TaskCancellationRequested returns true if CancelTask has been called for task, false otherwise.
OnTaskCancellation tests if cancellation for the current task has been requested. If so, then exit_func will be called (as a parameterless function) and the current task will be aborted. The result of the current task will be the value of exit_func().
Example:
gap> task := RunTask(function() > while true do > OnTaskCancellation(function() return 314; end); > od; > end); gap> CancelTask(task); gap> TaskResult(task); 314
OnTaskCancellationReturn is a convenience function that does the same as:
OnTaskCancellation(function() return value; end);
ScheduleTask and WaitTask can be made to wait on more complex conditions than just tasks. A condition is either a milestone, a task, or a list of milestones and tasks. ScheduleTask starts its task and WaitTask returns when the condition has been met. A condition represented by a task is met when the task has completed. A condition represented by a milestone is met when the milestone has been achieved (see below). A condition represented by a list is met when all conditions in the list have been met.
Milestones are a way to represent abstract conditions to which multiple tasks can contribute.
The NewMilestone function creates a new milestone. Its argument is a list of targets, which must be a list of integers and/or strings. If omitted, the list defaults to [0].
The ContributeToMilestone milestone function contributes the specified target to the milestone. Once all targets have been contributed to a milestone, it has been achieved.
The AchieveMilestone function allows a program to achieve a milestone in a single step without adding individual targets to it. This is most useful in conjunction with the default value for NewMilestone, e.g.
gap> m := NewMilestone();; gap> AchieveMilestone(m);
The IsMilestoneAchieved tests explicitly if a milestone has been achieved. It returns true on success, false otherwise.
gap> m := NewMilestone([1,2]);; gap> ContributeToMilestone(m, 1); gap> IsMilestoneAchieved(m); false gap> ContributeToMilestone(m, 2); gap> IsMilestoneAchieved(m); true
Variables with global scope have revised semantics in HPC-GAP in order to address concurrency issues. The normal semantics of global variables that are only accessed by a single thread remain unaltered.
Global variables in HPC-GAP an be accessed by all threads concurrently without explicit synchronization. Concurrent access is safe, but it is not deterministic. If multiple threads attempt to modify the same global variable simultaneously, the resulting value of the variable is random; it will be one of the values assigned by a thread, but it is impossible to predict with certainty which specific one will be assigned.
HPC-GAP supports the notion of thread-local variables. Thread-local variables are (after being declared as such) accessed and modified like global variables. However, unlike global variables, each thread can assign a distinct value to a thread-local variable.
gap> MakeThreadLocal("x");
gap> x := 1;;
gap> WaitTask(RunTask(function() x := 2; end));
gap> x;
1
As can be seen here, the assignment to x in a separate thread does not overwrite the value of x in the main thread.
MakeThreadLocal makes the variable described by the string name a thread-local variable. It normally does not give it an initial value; either explicit per-thread assignment or a call to BindThreadLocal or BindThreadLocalConstructor to provide a default value is necessary.
If a global variable with the same name exists and is bound at the time of the call, its value will be used as the default value as though BindThreadLocal had been called with that value as its second argument.
BindThreadLocal gives the thread-local variable described by the string name the default value obj. The first time the thread-local variable is accessed in a thread thereafter, it will yield obj as its value if it hasn't been assigned a specific value yet.
BindThreadLocal gives the thread-local variable described by the string name the constructor func. The first time the thread-local variable is accessed in a thread thereafter, it will yield func() as its value if it hasn't been assigned a specific value yet.
All thread-local variables are stored in the thread-local record ThreadVar. Thus, if x is a thread-local variable, using ThreadVar.x is the same as using x.
HPC-GAP allows multiple threads to access data shared between them; to avoid common concurrency errors, such as race conditions, it partitions GAP objects into regions. Access to regions is regulated so that no two threads can modify objects in the same region at the same time and so that objects that are being read by one thread cannot concurrently be modified by another.
Each thread has an associated thread-local region. When a thread implicitly or explicitly creates a new object, that object initially belongs to the thread's thread-local region.
Only the thread can read or modify objects in its thread-local region. For other threads to access an object, that object has to be migrated into a different region first.
Shared regions are explicitly created through the ShareObj and ShareSingleObj primitives (see below). Multiple threads can access them concurrently, but accessing them requires that a thread uses an atomic statement to acquire a read or write lock beforehand.
See the section on atomic statements (Section 3.9.43) for details.
Shared regions are by default ordered; each shared region has an associated numeric precedence level. Regions can generally only be locked in order of descending precedence. The purpose of this mechanism is to avoid accidental deadlocks.
The ordering requirement can be overridden in two ways: regions with a negative precedence are excluded from it. This exception should be used with care, as it can lead to deadlocks.
Alternatively, two or more regions can be locked simultaneously via the atomic statement. In this case, the ordering of these regions relative to each other can be arbitrary.
A special public region contains objects that only permit atomic operations. These include, in particular, all immutable objects (immutable in the sense that their in-memory representation cannot change).
All threads can access objects in the public region at all times without needing to acquire a read- or write-lock beforehand.
The read-only region is another special region that contains objects that are only meant to be read; attempting to modify an object in that region will result in a runtime error. To obtain a modifiable copy of such an object, the CopyRegion primitive can be used.
Objects can be migrated between regions using a number of functions. In order to migrate an object, the current thread must have exclusive access to that object; the object must be in its thread-local region or it must be in a shared region for which the current thread holds a write lock.
The ShareObj and ShareSingleObj functions create a new shared region and migrate their respective argument to that region; ShareObj will also migrate all subobjects that are within the same region, while ShareSingleObj will leave the subobjects unaffected.
The MigrateObj and MigrateSingleObj functions migrate objects to an existing region. The first argument of either function is the object to be migrated; the second is either a region (as returned by the RegionOf function) or an object whose containing region the first argument is to be migrated to.
The current thread needs exclusive access to the target region (denoted by the second argument) for the operation to succeed. If successful, the first argument will be in the same region as the second argument afterwards. In the case of MigrateObj, all subobjects within the same region as the first argument will also be migrated to the target region.
Finally, AdoptObj and AdoptSingleObj are special cases of MigrateObj and MigrateSingleObj, where the target region is the thread-local region of the current thread.
To migrate objects to the read-only region, one can use MakeReadOnly and MakeReadOnlyObj. The first migrates its argument and all its subjobjects that are within the same region to the read-only region; the second migrates only the argument itself, but not its subobjects.
It is generally not possible to migrate objects explicitly to the public region; only objects with purely atomic operations can be made public and that is done automatically when they are created.
The exception are immutable objects. When MakeImmutable is used, its argument is automatically moved to the public region.
gap> RegionOf(MakeImmutable([1,2,3])); <public region>
Regions can be given names, either explicitly via SetRegionName or when they are created via ShareObj and ShareSingleObj. Thread-local regions, the public, and the readonly region are given names by default.
Multiple regions can have the same name.
If either GAP code or a kernel primitive attempts to access an object that it is not allowed to access according to these semantics, either a "write guard error" (for a failed write access) or a "read guard error" (for a failed read access) will be raised. The global variable LastInaccessible will contain the object that caused such an error.
One exception is that threads can modify objects in regions that they have only read access (but not write access) to using write-once functions (Section 3.11).
To inspect objects whose contents lie in other regions (and therefore cannot be displayed by PrintObj or ViewObj, the functions ViewShared and UNSAFE_VIEW can be used.
The function NewRegion creates a new shared region. If the optional argument name is provided, then the name of the new region will be set to name.
gap> NewRegion("example region");
<region: example region>
NewRegion will create a region with a high precedence level. It is intended to be called by user code. The exact precedence level can be adjusted with prec, which must be an integer in the range [-1000..1000]; prec will be added to the normal precedence level.
NewLibraryRegion functions like NewRegion, except that the precedence of the region it creates is below that of NewRegion. It is intended to be used by user libraries and GAP packages.
NewSystemRegion functions like NewRegion, except that the precedence of the region it creates is below that of NewLibraryRegion. It is intended to be used by the standard GAP library.
NewKernelRegion functions like NewRegion, except that the precedence of the region it creates is below that of NewSystemRegion. It is intended to be used by the GAP kernel, and GAP library code that interacts closely with the kernel.
NewInternalRegion functions like NewRegion, except that the precedence of the region it creates is the lowest available. It is intended to be used for regions that are self-contained; i.e. no function that uses such a region may lock another region while accessing it. The precedence level of an internal region cannot be adjusted.
NewLibraryRegion functions like NewRegion, except that the precedence of the region it creates is negative. It is thus exempt from normal ordering and deadlock checks.
gap> RegionOf(1/2); <public region> gap> RegionOf([1,2,3]); <region: thread region #0> gap> RegionOf(ShareObj([1,2,3])); <region 0x45deaa0> gap> RegionOf(ShareObj([1,2,3])); <region 0x45deaa0> gap> RegionOf(ShareObj([1,2,3], "test region")); <region: test region>
Note that the unique number that each region is identified with is system-specific and can change each time the code is being run.
Region objects returned by RegionOf can be compared:
gap> RegionOf([1,2,3]) = RegionOf([4,5,6]); true
The result in this example is true because both lists are in the same thread-local region.
RegionPrecedence will return the precedence of the region of obj.
gap> RegionPrecedence(NewRegion("Test"));
30000
gap> RegionPrecedence(NewRegion("Test2", 1));
30001
gap> RegionPrecedence(NewLibraryRegion("LibTest", -1));
19999
The ShareObj function creates a new shared region and migrates the object and all its subobjects to that region. If the optional argument name is provided, then the name of the new region is set to name.
ShareObj will create a region with a high precedence level. It is intended to be called by user code. The actual precedence level can be adjusted by the optional prec argument in the same way as for NewRegion.
ShareLibraryObj functions like ShareObj, except that the precedence of the region it creates is below that of ShareObj. It is intended to be used by user libraries and GAP packages.
ShareSystemObj functions like ShareObj, except that the precedence of the region it creates is below that of ShareLibraryObj. It is intended to be used by the standard GAP library.
ShareKernelObj functions like ShareObj, except that the precedence of the region it creates is below that of ShareSystemObj. It is intended to be used by the GAP kernel, and GAP library code that interacts closely with the kernel.
ShareInternalObj functions like ShareObj, except that the precedence of the region it creates is the lowest available. It is intended to be used for regions that are self-contained; i.e. no function that uses such a region may lock another region while accessing it.
ShareLibraryObj functions like ShareObj, except that the precedence of the region it creates is negative. It is thus exempt from normal ordering and deadlock checks.
The ShareSingleObj function creates a new shared region and migrates the object, but not its subobjects, to that region. If the optional argument name is provided, then the name of the new region is set to name.
gap> m := [ [1, 2], [3, 4] ];; gap> ShareSingleObj(m);; gap> atomic readonly m do > Display([ IsShared(m), IsShared(m[1]), IsShared(m[2]) ]); > od; [ true, false, false ]
ShareSingleObj will create a region with a high precedence level. It is intended to be called by user code. The actual precedence level can be adjusted by the optional prec argument in the same way as for NewRegion.
ShareSingleLibraryObj functions like ShareSingleObj, except that the precedence of the region it creates is below that of ShareSingleObj. It is intended to be used by user libraries and GAP packages.
ShareSingleSystemObj functions like ShareSingleObj, except that the precedence of the region it creates is below that of ShareSingleLibraryObj. It is intended to be used by the standard GAP library.
ShareSingleKernelObj functions like ShareSingleObj, except that the precedence of the region it creates is below that of ShareSingleSystemObj. It is intended to be used by the GAP kernel, and GAP library code that interacts closely with the kernel.
ShareSingleInternalObj functions like ShareSingleObj, except that the precedence of the region it creates is the lowest available. It is intended to be used for regions that are self-contained; i.e. no function that uses such a region may lock another region while accessing it.
ShareSingleLibraryObj functions like ShareSingleObj, except that the precedence of the region it creates is negative. It is thus exempt from normal ordering and deadlock checks.
The MigrateObj function migrates obj (and all subobjects contained within the same region) to the region denoted by the target argument. Here, target can either be a region object returned by RegionOf or a normal gap object. If target is a normal gap object, obj will be migrated to the region containing target.
For the operation to succeed, the current thread must have exclusive access to the target region and the object being migrated.
The MigrateSingleObj function works like MigrateObj, except that it does not migrate the subobjects of obj.
The LockAndMigrateObj function works like MigrateObj, except that it will automatically try to acquire a lock for the region containing target if it does not have one already.
The IncorporateObj function allows convenient migration to a shared list or record. If target is a list, then IncorporateObj is equivalent to:
IncorporateObj := function(target, index, value)
atomic value do
target[index] := MigrateObj(value, target)
od;
end;
If target is a record, then it is equivalent to:
IncorporateObj := function(target, index, value)
atomic value do
target.(index) := MigrateObj(value, target)
od;
end;
The intended purpose is the population of a shared list or record with values after its creation.
Example:
gap> list := ShareObj([]); gap> atomic list do > IncorporateObj(list, 1, [1,2,3]); > IncorporateObj(list, 2, [4,5,6]); > IncorporateObj(list, 3, [7,8,9]); > od; gap> ViewShared(list); [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
Using plain assignment would leave the newly created lists in the thread-local region.
AtomicIncorporateObj extends IncorporateObj by also locking the target. I.e., for a list, it is equivalent to:
AtomicIncorporateObj := function(target, index, value)
atomic value do
target[index] := MigrateObj(value, target)
od;
end;
If target is a record, then it is equivalent to:
AtomicIncorporateObj := function(target, index, value)
atomic value do
target.(index) := MigrateObj(value, target)
od;
end;
The AdoptObj function migrates obj (and all its subobjects contained within the same region) to the thread's current region. It requires exclusive access to obj.
gap> l := ShareObj([1,2,3]);; gap> IsThreadLocal(l); false gap> atomic l do AdoptObj(l); od; gap> IsThreadLocal(l); true
The AdoptSingleObj function works like AdoptObj, except that it does not migrate the subobjects of obj.
The LockAndAdoptObj function works like AdoptObj, except that it will attempt acquire an exclusive lock for the region containing obj if it does not have one already.
The CopyRegion function performs a structural copy of obj. The resulting objects will be located in the current thread's thread-local region. The function returns the copy as its result.
gap> l := MakeReadOnly([1,2,3]); [ 1, 2, 3 ] gap> l2 := CopyRegion(l); [ 1, 2, 3 ] gap> RegionOf(l) = RegionOf(l2); false gap> IsIdenticalObj(l, l2); false gap> l = l2; true
The IsPublic function returns true if its argument is an object in the public region, false otherwise.
gap> IsPublic(1/2); true gap> IsPublic([1,2,3]); false gap> IsPublic(ShareObj([1,2,3])); false gap> IsPublic(MakeImmutable([1,2,3])); true
The IsThreadLocal function returns true if its argument is an object in the current thread's thread-local region, false otherwise.
gap> IsThreadLocal([1,2,3]); true gap> IsThreadLocal(ShareObj([1,2,3])); false gap> IsThreadLocal(1/2); false gap> RegionOf(1/2); <public region>
The IsShared function returns true if its argument is an object in a shared region. Note that if the current thread does not hold a lock on that shared region, another thread can migrate obj to a different region before the result is being evaluated; this can lead to race conditions. The function is intended primarily for debugging, not to build actual program logic around.
The HaveReadAccess function returns true if the current thread has read access to obj.
gap> HaveReadAccess([1,2,3]); true gap> l := ShareObj([1,2,3]);; gap> HaveReadAccess(l); false gap> atomic readonly l do t := HaveReadAccess(l); od;; t; true
The HaveWriteAccess function returns true if the current thread has write access to obj.
gap> HaveWriteAccess([1,2,3]); true gap> l := ShareObj([1,2,3]);; gap> HaveWriteAccess(l); false gap> atomic readwrite l do t := HaveWriteAccess(l); od;; t; true
The MakeReadOnly function migrates obj and all its subobjects that are within the same region as obj to the read-only region. It returns obj.
The MakeReadOnlyObj function migrates obj, but not any of its subobjects, to the read-only region. It returns obj.
The IsReadOnly function returns true if obj is in the read-only region, false otherwise.
gap> IsReadOnly([1,2,3]); false gap> IsReadOnly(MakeImmutable([1,2,3])); false gap> IsReadOnly(MakeReadOnly([1,2,3])); true
The SetRegionName function sets the name of the region of obj to name.
The ClearRegionName function clears the name of the region of obj to name.
The RegionName function returns the name of the region of obj. If that region does not have a name, fail will be returned.
The ViewShared function allows the inspection of objects in shared regions. It will try to lock the region and then call ViewObj(obj). If it cannot acquire a lock for the region, it will simply display the normal description of the object.
The UNSAFE_VIEW function allows the inspection of any object in the system, regardless of whether the current thread has access to the region containing it. It should be used with care: If the object inspected is being modified by another thread concurrently, the resulting behavior is undefined.
Moreover, the function works by temporarily disabling read and write guards for regions, so other threads may corrupt memory rather than producing errors.
It is generally safe to use if all threads but the current one are paused.
The atomic statement ensures exclusive or read-only access to one or more shared regions for statements within its scope. It has the following syntax:
atomic ([readwrite|readonly] expr (, expr)* )* do statements od;
Each expression is evaluated and the region containing the resulting object is locked with either a read-write or read-only lock, depending on the keyword preceding the expression. If neither the readwrite nor the readonly keyword was provided, read-write locks are used by default.
Examples:
gap> l := ShareObj([1,2,3]);; gap> atomic readwrite l do l[3] := 9; od; gap> atomic l do l[2] := 4; od; gap> atomic readonly l do Display(l); od; [ 1, 4, 9 ]
gap> l := ShareObj([1,2,3,4,5]);; gap> l2 := ShareObj([6,7,8]);; gap> atomic readwrite l, readonly l2 do > for i in [1..3] do l[i] := l2[i]; od; > l3 := AdoptObj(l); > od; gap> l3; [ 6, 7, 8, 4, 5 ]
Atomic statements must observe region ordering. That means that the highest precedence level of a region locked by an atomic statement must be less than the lowest precedene level of a region that is locked by the same thread at the time the atomic statement is executed.
Instead of atomic regions, entire functions can be declared to be atomic. This has the same effect as though the function's body were enclosed in an atomic statement. Function arguments can be declared either readwrite or readonly; they will be locked in the same way as for a lock statement. If a function argument is preceded by neither readwrite nor readonly, the corresponding object will not be locked.
Example:
gap> AddAtomic := atomic function(readwrite list, readonly item) > Add(list, item); > end;
There is an exception to the rule that objects can only be modified if a thread has write access to a region. A limited sets of objects can be modified using the "bind once" family of functions. These allow the modifications of objects to which a thread has read access in a limited fashion.
For reasons of implementation symmetry, these functions can also be used on the atomic versions of these objects.
Implementation note: The functionality is not currently available for component objects.
BindOnce modifies obj, which can be a positional object, atomic positional object, component object, or atomic component object. It inspects obj![index] for the positional versions or obj!.(index) for the component versions. If the respective element is not yet bound, value is assigned to that element. Otherwise, no modification happens. The test and modification occur as one atomic step. The function returns the value of the element; i.e. the old value if the element was bound and value if it was unbound.
The intent of this function is to allow concurrent initialization of objects, where multiple threads may attempt to set a value concurrently. Only one will succeed; all threads can then use the return value of BindOnce as the definitive value of the element. It also allows for the lazy initialization of objects in the read-only region.
The current thread needs to have at least read access to obj, but does not require write access.
TestBindOnce works like BindOnce, except that it returns true if the value could be bound and false otherwise.
BindOnceExpr works like BindOnce, except that it evaluates the parameterless function expr to determine the value. It will only evaluate expr if the element is not bound.
For positional objects, the implementation works as follows:
BindOnceExprPosObj := function(obj, index, expr)
if not IsBound(obj![index]) then
return BindOnce(obj, index, expr());
else
return obj![index]);
fi;
end;
The implementation for component objects works analogously.
The intent is to avoid unnecessary computations if the value is already bound. Note that this cannot be avoided entirely, because obj![index] or obj!.(index) can be bound while expr is evaluated, but it can minimize such occurrences.
TestBindOnceExpr works like BindOnceExpr, except that it returns true if the value could be bound and false otherwise.
StrictBindOnce works like BindOnce, except that it raises an error if the element is already bound. This is intended for cases where a read-only object is initialized, but where another thread trying to initialize it concurrently would be an error.
HPC-GAP has a multi-threaded user interface to assist with the development and debugging of concurrent programs. This user interface is enabled by default; to disable it, and use the single-threaded interface, GAP has to be started with the -S option.
The console user interface provides the user with the option to control threads by commands prefixed with an exclamation mark ("!"). Those commands are listed below.
For ease of use, users only need to type as many letters of each commands so that it can be unambiguously selected. Thus, the shell will recognize !l as an abbreviation for !list.
Starts a new shell thread and switches to it. Optionally, a name for the thread can be provided.
gap> !shell --- Switching to thread 4 [4] gap>
Starts a new background shell thread. Optionally, a name for the thread can be provided.
gap> !fork --- Created new thread 5
List all current threads that are interacting with the user. This does not list threads created with CreateThread() that have not entered a break loop.
gap> !list --- Thread 0 [0] --- Thread 4 [4] --- Thread 5 [5] (pending output)
Terminates the specified thread.
Makes the specified thread enter a break loop.
Give the thread with the numerical identifier or name <id> the name name.
gap> !name 5 test gap> !list --- Thread 0 [0] --- Thread 4 [4] --- Thread test [5] (pending output)
Provide information about the thread with the numerical identifier or name <id>. (/Not yet implemented./}
Hide output from the thread with the numerical identifier or name <id> when it is not the foreground thread. If no thread is specified, make this the default behavior for future threads.
Show output from the thread with the numerical identifier or name <id> even when it is not the foreground thread. If no thread is specified, make this the default behavior for future threads.
Keep <num> lines of output from each thread.
Set the prompt for the specified thread (or for all newly created threads if * was specified) to be <string>. If the string contains the pattern %id%, it is replaced with the numerical id of the thread; if it contains the pattern %name%, it is replaced with the name of the thread; if the thread has no name, the numerical id is displayed instead.
Prefix the output from the specified thread (or for all newly created threads if * was specified) wiht <string>. The same substitution rules as for the !prompt command apply.
Make the specified thread the foreground thread.
gap> !select 4 gap> !select 4 --- Switching to thread 4 [4] gap>
Make the next thread in numerical order the foreground thread.
Make the previous thread in numerical order the foreground thread.
Display the last <num> lines of output of the specified thread. If no thread was specified, display the last <num> lines of the current foreground thread.
!<id> is a shortcut for !select <id>.
Read commands from file <file>.
Create an alias. After defining the alias, !<shortcut> <rest of line> will be replaced with !<expansion> <rest of line>.
Removes the specified alias.
Evaluates <gap code> as a command.
Calls the function with name <function>, passing it the single argument <string> as a GAP string.
There are several functions to access the basic functionality of the shell user interface. Other than TextUIRegisterCommand, they can only be called from within a registered command.
Threads can be specified either by their numerical identifier or by their name (as a string). The empty string can be used to specify the current foreground thread.
Registers the command !name with the shell UI. It will call <func> with the rest of the command line passed as a string argument when typed.
Returns the numerical identifier of the current foreground thread.
Returns the name of the current foreground thread or fail if the current foreground thread has no name.
Makes id the current foreground thread. Returns true or false to indicate success.
Returns the last count lines of the thread specified by id (which can be a numerical identifier or a name). Returns fail if there is no such thread.
By default, retain length lines of output history from each thread.
Creates a new shell thread. Here, foreground is a boolean variable specifying whether it should be made the new foreground thread and name is the name of the thread. The empty string can be used to leave the thread without a name.
Run the command denoted by command as though a user had typed it. The command must not contain a newline character.
Display a prompt for the current thread.
HPC-GAP provides a number of atomic object types. These can be accessed by multiple threads concurrently without requiring explicit synchronization, but can have non-deterministic behavior for complex operations.
Atomic lists are fixed-size lists; they can be assigned to and read from like normal plain lists.
Atomic records are atomic versions of plain records. Unlike plain records, though, it is not possible to delete elements from an atomic record.
The primary use of atomic lists and records is to facilitate storing the result of idempotent operations and to support certain low-level operations.
Atomic lists and records can have three different replacement policies: write-once, strict write-once, and rewritable. The replacement policy determines whether an already assigned element can be changed. The write-once policy allows elements to be assigned only once, with subsequent assignments being ignored; the strict write-once policy allows elements also to be assigned only once, but subsequent assignments will raise an error; the rewritable policy allows elements to be assigned different values repeatedly. The default for new atomic objects is to be rewritable.
Thread-local records are variants of plain records that are replicated on a per-thread basis.
Atomic lists are created using the AtomicList or FixedAtomicList functions. After creation, they can be used exactly like any other list, except that atomic lists created with FixedAtomicList cannot be resized. Their contents can also be read as normal plain lists using FromAtomicList.
gap> a := AtomicList([1,2,4]); <atomic list of size 3> gap> WaitTask(RunTask(function() a[1] := a[1] + a[2]; end)); gap> a[1]; 3 gap> FromAtomicList(a); [ 3, 2, 4 ]
Because multiple threads can read and write the list concurrently without synchronization, the results of modifying the list may be non-deterministic.
It is faster to write to fixed atomic lists than to a resizable atomic list.
AtomicList is used to create a new atomic list. It takes either a plain list as an argument, in which case it will create a new atomic list of the same size, populated by the same elements; or it takes a count and an object argument. In that case, it creates an atomic list with count elements, each set to the value of obj.
gap> al := AtomicList([3, 1, 4]); <atomic list of size 3> gap> al[3]; 4 gap> al := AtomicList(10, `"alpha"); <atomic list of size 10> gap> al[3]; "alpha" gap> WaitTask(RunTask(function() al[3] := `"beta"; end)); gap> al[3]; "beta"
FixedAtomicList works like AtomicList except that the resulting list cannot be resized.
MakeFixedAtomicList turns a resizable atomic list into a fixed atomic list.
gap> a := AtomicList([99]); <atomic list of size 1> gap> a[2] := 100; 100 gap> MakeFixedAtomicList(a); <fixed atomic list of size 2> gap> a[3] := 101; Error, Atomic List Element: <pos>=3 is an invalid index for <list>
FromAtomicList returns a plain list containing the same elements as atomic_list at the time of the call. Because other threads can write concurrently to that list, the result is not guaranteed to be deterministic.
gap> al := AtomicList([10, 20, 30]);; gap> WaitTask(RunTask(function() al[2] := 40; end)); gap> FromAtomicList(al); [ 10, 40, 30 ]
ATOMIC_ADDITION is a low-level operation that atomically adds value to atomic_list[index]. It returns the value of atomic_list[index] after the addition has been performed.
gap> al := FixedAtomicList([4,5,6]);; gap> ATOMIC_ADDITION(al, 2, 7); 12 gap> FromAtomicList(al); [ 4, 12, 6 ]
COMPARE_AND_SWAP is an atomic operation. It atomically compares atomic_list[index] to old and, if they are identical, replaces the value (in the same atomic step) with new. It returns true if the replacement took place, false otherwise.
The primary use of COMPARE_AND_SWAP is to implement certain concurrency primitives; most programmers will not need to use it.
Atomic records are atomic counterparts to plain records. They support assignment to individual record fields, and conversion to and from plain records.
Assignment semantics can be specified on a per-record basis if the assigned record field is already populated, allowing either an overwrite, keeping the existing value, or raising an error.
It is not possible to unbind atomic record elements.
Like plain records, atomic records can be converted to component objects using Objectify.
AtomicRecord is used to create a new atomic record. Its single optional argument is either a positive integer, denoting the intended capacity (i.e., number of elements to be held) of the record, in which case a new empty atomic record with that initial capacity will be created. Alternatively, the caller can provide a plain record with which to initially populate the atomic record.
gap> r := AtomicRecord(rec( x := 2 )); <atomic record 1/2 full> gap> r.y := 3; 3 gap> TaskResult(RunTask(function() return r.x + r.y; end)); 5 gap> [ r.x, r.y ]; [ 2, 3 ]
Any atomic record can later grow beyond its initial capacity. There is no limit to the number of elements it can hold other than available memory.
FromAtomicRecord returns a plain record copy of the atomic record record. This copy is shallow; elements of record will not also be copied.
gap> r := AtomicRecord();; gap> r.x := 1;; r.y := 2;; r.z := 3;; gap> FromAtomicRecord(r); rec( x := 1, y := 2, z := 3 )
There are three functions that set the replacement policy of an atomic object. All three can also be used with plain lists and records, in which case an atomic version of the list or record is first created. This allows programmers to elide AtomicList and AtomicRecord calls when the next step is to change their policy.
MakeWriteOnceAtomic takes a list, record, atomic list, atomic record, atomic positional object, or atomic component object as its argument. If the argument is a non-atomic list or record, then the function first creates an atomic copy of the argument. The function then changes the replacement policy of the object to write-once: if an element of the object is already bound, then further attempts to assign to it will be ignored.
MakeStrictWriteOnceAtomic works like MakeWriteOnceAtomic, except that the replacement policy is being changed to being strict write-once: if an element is already bound, then further attempts to assign to it will raise an error.
MakeReadWriteAtomic is the inverse of MakeWriteOnceAtomic and MakeStrictWriteOnceAtomic in that the replacement policy is being changed to being rewritable: Elements can be replaced even if they are already bound.
Thread-local records allow an easy way to have a separate copy of a record for each indvidual thread that is accessed by the same name in each thread.
gap> r := ThreadLocalRecord();; # create new thread-local record gap> r.x := 99;; gap> WaitThread( CreateThread( function() > r.x := 100; > Display(r.x); > end ) ); 100 gap> r.x; 99
As can be seen above, even though r.x is overwritten in the second thread, it does not affect the value of r.x| in the first thread
ThreadLocalRecord creates a new thread-local record. It accepts up to two initial arguments. The defaults argument is a record of default values with which each thread-local copy is initially populated (this happens on demand, so values are not actually read until needed).
The second argument is a record of constructors; parameterless functions that return an initial value for the respective element. Constructors are evaluated only once per thread and only if the respective element is accessed without having previously been assigned a value.
gap> r := ThreadLocalRecord( rec(x := 99), > rec(y := function() return 101; end));; gap> r.x; 99 gap> r.y; 101 gap> TaskResult(RunTask(function() return r.x; end)); 99 gap> TaskResult(RunTask(function() return r.y; end)); 101
SetTLDefault can be used to set the default value of a record field after its creation. Here, record is an atomic record, name is the string of the field name, and value is the value.
gap> r := ThreadLocalRecord();; gap> SetTLDefault(r, "x", 314); gap> r.x; 314 gap> TaskResult(RunTask(function() return r.x; end)); 314
SetTLConstructor can be used to set the constructor of a thread-local record field after its creation, similar to SetTLDefault.
gap> r := ThreadLocalRecord();; gap> SetTLConstructor(r, "x", function() return 2718; end); gap> r.x; 2718 gap> TaskResult(RunTask(function() return r.x; end)); 2718
HPC-GAP has low-level functionality to support explicit creation of threads. In practice, programmers should use higher-level functionality, such as tasks, to describe concurrency. The thread functions described here exist to facilitate the construction of higher level libraries and are not meant to be used directly.
New threads are created with the function CreateThread. The thread takes at least one function as its argument that it will call in the newly created thread; it also accepts zero or more parameters that will be passed to that function.
The function returns a thread object describing the thread.
Only a finite number of threads can be active at a time (that limit is system-dependent). To reclaim the resources occupied by one thread, use the WaitThread function.
The WaitThread function waits for the thread identified by threadID to finish; it does not return any value. When it returns, it returns all resources occupied by the thread it waited for, such as thread-local memory and operating system structures, to the system.
The CurrentThread function returns the thread object for the current thread.
The ThreadID function returns a numeric thread id for the given thread. The thread id of the main thread is always 0.
gap> CurrentThread(); <thread #0: running> gap> ThreadID(CurrentThread()); 0
The KillThread function terminates the given thread. Any region locks that the thread currently holds will be unlocked. The thread can be specified as a thread object or via its numeric id.
The implementation for KillThread is dependent on the interpreter actually executing statements. Threads performing system calls, for example, will not be terminated until the system call returns. Similarly, long-running kernel functions will delay termination until the kernel function returns.
Use of CALL_WITH_CATCH will not prevent a thread from being terminated. If you wish to make sure that catch handlers will be visited, use InterruptThread instead. KillThread should be used for threads that cannot be controlled anymore in any other way but still eat system resources.
The PauseThread function suspends execution for the given thread. The thread can be specified as a thread object or via its numeric id.
The implementation for PauseThread() is dependent on the interpreter actually executing statements. Threads performing system calls, for example, will not pause until the system call returns. Similarly, long-running kernel functions will not pause until the kernel function returns.
While a thread is paused, the thread that initiated the pause can access the paused thread's thread-local region.
gap> loop := function() while true do Sleep(1); od; end;; gap> x := fail;; gap> th := CreateThread(function() x := [1, 2, 3]; loop(); end);; gap> PauseThread(th); gap> x; [ 1, 2, 3 ]
The ResumeThread function resumes execution for the given thread that was paused with PauseThread. The thread can be specified as a thread object or via its numeric id.
If the thread isn't paused, ResumeThread is a no-op.
The InterruptThread function calls an interrupt handler for the given thread. The thread can be specified as a thread object or via its numeric id. The interrupt is specified as an integer between 0 and MAX_INTERRUPT.
An interrupt number of zero (or an interrupt number for which no interrupt handler has been set up with SetInterruptHandler will cause the thread to enter a break loop. Otherwise, the respective interrupt handler that has been created with SetInterruptHandler will be called.
The implementation for InterruptThread is dependent on the interpreter actually executing statements. Threads performing system calls, for example, will not call interrupt handlers until the system call returns. Similarly, long-running kernel functions will delay invocation of the interrupt handler until the kernel function returns.
The SetInterruptHandler function allows the programmer to set up interrupt handlers for the current thread. The interrupt number must be in the range from 1 to MAX_INTERRUPT (inclusive); the handler must be a parameterless function (or fail to remove a handler).
The NewInterruptID function returns a previously unused number (starting at 1). These numbers can be used to globally coordinate interrupt numbers.
gap> StopTaskInterrupt := NewInterruptID(); 1 gap> SetInterruptHandler(StopTaskInterrupt, StopTaskHandler);
The global variable MAX_INTERRUPT is an integer containing the maximum value for the interrupt arguments to InterruptThread and SetInterruptHandler.
Channels are FIFO queues that threads can use to coordinate their activities.
CreateChannel() returns a FIFO communication channel that can be used to exchange information between threads. Its optional argument is a capacity (positive integer). If insufficient resources are available to create a channel, it returns -1. If the capacity is not a positive integer, an error will be raised.
If a capacity is not provided, by default the channel can hold an indefinite number of objects. Otherwise, attempts to store objects in the channel beyond its capacity will block.
gap> ch1:=CreateChannel(); <channel 0x460339c: 0 elements, 0 waiting> gap> ch2:=CreateChannel(5); <channel 0x460324c: 0/5 elements, 0 waiting>
SendChannel accepts two arguments, a channel object returned by CreateChannel, and an arbitrary GAP object. It stores obj in channel. If channel has a finite capacity and is currently full, then SendChannel will block until at least one element has been removed from the channel, e.g. using ReceiveChannel.
SendChannel performs automatic region migration for thread-local objects. If obj is thread-local for the current thread, it will be migrated (along with all subobjects contained in the same region) to the receiving thread's thread-local data space. In between sending and receiving, obj cannot be accessed by either thread.
This example demonstrates sending messages across a channel.
gap> ch1 := CreateChannel();; gap> SendChannel(ch1,1); gap> ch1; <channel 0x460339c: 1 elements, 0 waiting> gap> ReceiveChannel(ch1); 1 gap> ch1; <channel 0x460339c: 0 elements, 0 waiting>
Sleep in the following example is used to demonstrate blocking.
gap> ch2 := CreateChannel(5);;
gap> ch3 := CreateChannel();;
gap> for i in [1..5] do SendChannel(ch2,i); od;
gap> ch2;
<channel 0x460324c: 5/5 elements, 0 waiting>
gap> t:=CreateThread(
> function()
> local x;
> Sleep(10);
> x:=ReceiveChannel(ch2);
> Sleep(10);
> SendChannel(ch3,x);
> Print("Thread finished\n");
> end);;
> SendChannel(ch2,3); # this blocks until the thread reads from ch2
gap> ReceiveChannel(ch3); # the thread is blocked until we read from ch3
1
Thread finished
gap> WaitThread(t);
TransmitChannel is identical to SendChannel, except that it does not perform automatic region migration of thread-local objects.
gap> ch := CreateChannel(5);; gap> l := [ 1, 2, 3];; gap> original_region := RegionOf(l);; gap> SendChannel(ch, l); gap> WaitThread(CreateThread(function() > local ob; ob := ReceiveChannel(ch); > Display(RegionOf(ob) = original_region); > end)); false gap> l := [ 1, 2, 3];; gap> original_region := RegionOf(l);; gap> TransmitChannel(ch, l); gap> WaitThread(CreateThread(function() > local ob; ob := ReceiveChannel(ch); > Display(RegionOf(ob) = original_region); > end)); true
TrySendChannel is identical to SendChannel, except that it returns if the channel is full instead of blocking. It returns true if the send was successful and false otherwise.
gap> ch := CreateChannel(1);; gap> TrySendChannel(ch, 99); true gap> TrySendChannel(ch, 99); false
TryTransmitChannel is identical to TrySendChannel, except that it does not perform automatic region migration of thread-local objects.
ReceiveChannel is used to retrieve elements from a channel. If channel is empty, the call will block until an element has been added to the channel via SendChannel or a similar primitive.
See SendChannel for an example.
TryReceiveChannel, like ReceiveChannel, attempts to retrieve an object from channel. If it does not succeed, however, it will return default rather than blocking.
gap> ch := CreateChannel();; gap> SendChannel(ch, 99); gap> TryReceiveChannel(ch, fail); 99 gap> TryReceiveChannel(ch, fail); fail
MultiSendChannel allows the sending of all the objects contained in the list list to channel as a single operation. The list must be dense and is not modified by the call. The function will send elements starting at index 1 until all elements have been sent. If a channel with finite capacity is full, then the operation will block until all elements can be sent.
The operation is designed to be more efficient than sending all elements individually via SendChannel by minimizing potentially expensive concurrency operations.
See MultiReceiveChannel for an example.
TryMultiSendChannel operates like MultiSendChannel, except that it returns rather than blocking if it cannot send any more elements if the channel is full. It returns the number of elements it has sent. If channel does not have finite capacity, TryMultiSendChannel will always send all elements in the list.
MultiReceiveChannel is the receiving counterpart to MultiSendChannel. It will try to receive up to amount objects from channel. If the channel contains less than amount objects, it will return rather than blocking.
The function returns a list of all the objects received.
gap> ch:=CreateChannel();; gap> MultiSendChannel(ch, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); gap> MultiReceiveChannel(ch,7); [ 1, 2, 3, 4, 5, 6, 7 ] gap> MultiReceiveChannel(ch,7); [ 8, 9, 10 ] gap> MultiReceiveChannel(ch,7); [ ]
ReceiveAnyChannel is a multiplexing variant of ReceiveChannel. It blocks until at least one of the channels provided contains an object. It will then retrieve that object from the channel and return it.
gap> ch1 := CreateChannel();; gap> ch2 := CreateChannel();; gap> SendChannel(ch2, [1, 2, 3]);; gap> ReceiveAnyChannel(ch1, ch2); [ 1, 2, 3 ]
ReceiveAnyChannelWithIndex works like ReceiveAnyChannel, except that it returns a list with two elements, the first being the object being received, the second being the number of the channel from which the object has been retrieved.
gap> ch1 := CreateChannel();; gap> ch2 := CreateChannel();; gap> SendChannel(ch2, [1, 2, 3]);; gap> ReceiveAnyChannelWithIndex(ch1, ch2); [ [ 1, 2, 3 ], 2 ]
TallyChannel returns the number of objects that a channel contains. This number can increase or decrease, as data is sent to or received from this channel. Send operations will only ever increase and receive operations will only ever decrease this count. Thus, if there is only one thread receiving data from the channel, it can use the result as a lower bound for the number of elements that will be available in the channel.
gap> ch := CreateChannel();; gap> SendChannel(ch, 2); gap> SendChannel(ch, 3); gap> SendChannel(ch, 5); gap> TallyChannel(ch); 3
InspectChannel returns a list of the objects that a channel contains. Note that objects that are not in the shared, public, or read-only region will be temporarily stored in the so-called limbo region while in transit and will be inaccessible through normal means until they have been received.
gap> ch := CreateChannel();; gap> SendChannel(ch, 2); gap> SendChannel(ch, 3); gap> SendChannel(ch, 5); gap> InspectChannel(ch); [ 2, 3, 5 ]
This function is primarly intended for debugging purposes.
Semaphores are synchronized counters; they can also be used to simulate locks.
The function CreateSemaphore takes an optional argument, which defaults to zero. It is the counter with which the semaphore is initialized.
gap> sem := CreateSemaphore(1); <semaphore 0x1108e81c0: count = 1>
WaitSemaphore receives a previously created semaphore as its argument. If the semaphore's counter is greater than zero, it decrements the counter and returns; if the counter is zero, it waits until another thread increases it via SignalSemaphore, then decrements the counter and returns.
gap> sem := CreateSemaphore(1); <semaphore 0x1108e81c0: count = 1> gap> WaitSemaphore(sem); gap> sem; <semaphore 0x1108e81c0: count = 0>
SignalSemaphore receives a previously created semaphore as its argument. It increments the semaphore's counter and returns.
gap> sem := CreateSemaphore(1); <semaphore 0x1108e81c0: count = 1> gap> WaitSemaphore(sem); gap> sem; <semaphore 0x1108e81c0: count = 0> gap> SignalSemaphore(sem); gap> sem; <semaphore 0x1108e81c0: count = 1>
In order to use semaphores to simulate locks, create a semaphore with an initial value of 1. WaitSemaphore is then equivalent to a lock operation, SignalSemaphore is equivalent to an unlock operation.
Synchronization variables (also often called dataflow variables in the literature) are variables that can be written only once; attempts to read the variable block until it has been written to.
Synchronization variables are created with CreateSyncVar, written with SyncWrite and read with SyncRead.
gap> sv := CreateSyncVar();; gap> RunAsyncTask(function() > Sleep(10); > SyncWrite(sv, MakeImmutable([1, 2, 3])); > end);; gap> SyncRead(sv); [ 1, 2, 3 ]
The function CreateSyncVar takes no arguments. It returns a new synchronization variable. There is no need to deallocate it; the garbage collector will free the memory and all related resources when it is no longer accessible.
SyncWrite attempts to assign the value obj to syncvar. If syncvar has been previously assigned a value, the call will fail with a runtime error; otherwise, obj will be assigned to syncvar.
In order to make sure that the recipient can read the result, the obj argument should not be a thread-local object; it should be public, read-only, or shared.
SyncRead reads the value previously assigned to syncvar with SyncWrite. If no value has been assigned yet, it blocks. It returns the assigned value.
HPC-GAP has support to serialize most GAP data. While functions in particular cannot be serialized, it is possible to serialize all primitive types (booleans, integers, cyclotomics, permutations, floats, etc.) as well as all lists and records.
Custom serialization support can be written for data objects, positional objects, and component objects; serialization of compressed vectors is already supported by the standard library.
SerializeToNativeString takes the object passed as an argument and turns it into a string, from which a copy of the original can be extracted using DeserializeNativeString.
DeserializeNativeString reverts the serialization process.
Example:
gap> DeserializeNativeString(SerializeToNativeString([1,2,3])); [ 1, 2, 3 ]
InstallTypeSerializationTag allows the serialization of data objects, positional objects, and component objects. The value of tag must be unique for each type; it can be a string or integer. Non-negative integers are reserved for use by the standard library; users should use negative integers or strings instead.
Objects of such a type are serialized in a straightforward way: During serialization, data objects are converted into byte streams, positional objects into lists, and component objects into records. These objects are then serialized along with their tags; deserialization uses the type corresponding to the tag in conjunction with Objectify to reconstruct a copy of the original object.
Note that this functionality may be inadequate for objects that have complex data structures attached that are not meant to be replicated. The following alternative is meant for such objects.
The more general InstallSerializer allows for arbitarily complex serialization code. It installs method as the method to serialize objects matching filters; description has the same role as for InstallMethod.
The method must return a plain list matching a specific format. The first element must be a non-negative integer, the second must be a string descriptor that is unique to the serializer; these can then be followed by an arbitrary number of arguments.
As many of the arguments (starting with the third element of the list) as specified by the first element of the list will be converted from their object representation into a serializable representation. Data objects will be converted into untyped data objects, positional objects will be converted into plain lists, and component objects into records. Conversion will not modify the objects in place, but work on copies. The remaining arguments will remain untouched.
Upon deserialization, these arguments will be passed to a function specified by the second element of the list.
Example:
InstallSerializer("8-bit vectors", [ Is8BitVectorRep ], function(obj)
return [1, "Vec8Bit", obj, Q_VEC8BIT(obj), IS_MUTABLE_OBJ(obj)];
end);
Here, obj will be converted into its underlying representation, while the remaining arguments are left alone. "Vec8Bit" is the name that is used to look up the deserializer function.
The descriptor value must be the same as the second element of the list returned by the serializer; func must be a function that takes as many arguments as there were arguments after the second element of that list. For deserialization, this function is invoked and needs to return the deserialized object constructed from the arguments.
Example:
InstallDeserializer("Vec8Bit", function(obj, q, mut)
SET_TYPE_OBJ(obj, TYPE_VEC8BIT(q, mut));
return obj;
end);
Here, the untyped obj that was passed to the deserializer needs to be given the correct type, which is calculated from q and mut.
There are experimental bindings to the ZeroMQ library available (http://www.zeromq.net/). This section describes these bindings. You need to build HPC-GAP with "make ZMQ=yes" to activate them.
Messages in ZeroMQ are sent between endpoints called sockets. Each socket can be bound to an address specified by a URI and other sockets can connect to the same address to exchange messages with that socket.
Addresses are specified as URIs of one of four different types (TCP, IPC, in-process, PGM/EPGM), each for a different type of transport.
TCP URIs map to POSIX TCP stream sockets. The URI is of the form "tcp://<address>:<port>" or "tcp://*:<port>". Here, <address> is an internet address, either an IP address or a symbolic address (note that to resolve symbolic addresses, the library may have to consult DNS servers, which can take an indefinite amount of time or even fail). Port is a TCP port number. If a "*" is given instead of an address, this describes the so-called unspecified address; the URI can only be used for binding and will then accept incoming connections from all interfaces (as in binding to "0.0.0.0" in IPv4 or "::" in IPv6).
The URI for IPC communication is of the form "ipc://<path>", where <path> is an actual path on the file system. Binding to such a URI will create a file in that location.
gap> socket := ZmqDealerSocket();; gap> ZmqBind(socket, "ipc:///tmp/connector");
The in-process transport is used to communicate between threads in order to avoid the overhead of operating system calls. Messages are simply being copied from one thread's memory to the other's.
In-process URIs are of the form "inproc://<string>", where <string> is an arbitrary string.
Sockets are generally being created via calls to ZmqPushSocket, etc. Each such call takes two optional arguments, a URI and an identity.
If a URI is given, a call to ZmqAttach will be performed immediately with the socket and URI. In particular, if the URI is prefixed with a "+" character, then the socket will connect to the address specified by the part after the "+ character; otherwise, it will be bound to the URI.
gap> z := ZmqPushSocket("inproc://test"); # binds to inproc://test
gap> z := ZmqPushSocket("+inproc://test"); # connects to inproc://test
If an identity is also provided, the library will call ZmqSetIdentity to set the identity (name) for that socket.
For a precise description of the behavior of each socket type, please consult the original ZeroMQ documentation for zmq_socket().
A push socket is one end of a unidirectional pipe. Programs can send messages to it, which will be delivered to a matched pull socket at the other end.
A pull socket is the other end of a unidirectional pipe.
A reply socket provides the server side of a remote-procedure call interaction. It alternates between receiving a message and sending a message to the socket from which the previous one originated.
Deviating from that protocol (for example, by sending two messages in succession or receiving two without responding to the first) will result in an error.
A request socket provides the client side of a remote-procedure call interaction. It will alternate between sending a message to a connected reply socket and receiving the response.
A publisher socket is a unidirectional broadcast facility. It will send each outgoing message to all connected subscriber sockets.
A subscriber socket receives messages from a publisher socket. It can subscribe to only a specific subseet of messages (see the ZmqSubscribe function) or receive all of them.
A dealer socket is a bidirectional socket. One or more peers can connect to it. Outgoing messages will be sent to those peers in a round-robin fashion (i.e., the first message goes to the first peer, the second to the second peer, and so forth until all peers have received a message and the process begins anew with the first peer). Incoming messages will be received from all peers and processed fairly (i.e., no message will be held indefinitely).
Two dealer sockets can be used to create a bidirectional pipe.
Router sockets, like dealer sockets, can have multiple peers connected to them. Incoming messages are handled the same way as for dealer sockets. Outgoing messages should be multi-part messages, where the first part of the message is the identity of one of the peers. The message will then be sent only to the peer with that identity.
Peers can be dealer, request, or reply sockets.
ZmqSocket is a low-level function that is used by ZmqPushSocket etc. to create sockets. Its argument is a string, one of "PUSH", "PULL", "REP", "REQ", "PUB", "SUB", DEALER", "ROUTER", and it creates and returns a socket of that type.
ZmqClose closes socket. Afterwards, it cannot anymore be bound or connected to, nor receive or send messages. Messages already in transit will still be delivered.
ZmqIsOpen returns true if socket has not been closed yet, false otherwise.
ZmqSocketType returns the string with which the socket was created (see ZmqSocket).
ZmqBind will bind socket to uri. After being bound to the address specified by uri, the socket can be connected to at that address with ZmqConnect.
ZmqConnect is used to connect socket to another socket that has been bound to uri. Note that you can connect to an address that has not been bound yet; in that case, the connection will be delayed until the binding has occurred.
ZmqAttach is a unified interface for binding and connecting a socket. If uri begins with a "+" character, then the ZmqConnect is called with the socket and the rest of the uri string following the "+". Otherwise, ZmqBind is called with these arguments.
The intended use is to construct a network of connections from a list of strings.
ZmqSocketURI returns the most recent URI to which socket has been bound or connected. Sockets can be bound to or connected to multiple addresses, but only the most recent one is returned.
ZmqIsBound returns true if the socket has been bound to the address returned by ZmqSocketURI(), false otherwise.
ZmqIsBound returns true if the socket has been connected to the address returned by ZmqSocketURI(), false otherwise.
ZeroMQ allows the sending and receiving of both string messages and multi-part messages. String messages are sequences of bytes (which can include zero), provided as a GAP string, while multi-part messages are lists of strings, provided as a GAP list. Multi-part messages are largely a convenience feature (e.g., to allow a message to have header parts without the inconvenience of having to encode those in a single string). When sent, multi-part messages will be delivered in their entirety; they can be retrieved one part at a time, but if the first part is available, the last part is available also.
ZmqSend will send data to socket, according to the routing behavior of the underlying socket mechanism.
ZmqReceive will either retrieve a string message or a single part of a multi-part message from socket and return the result as a GAP string.
gap> z := ZmqSocket("inproc://test");;
gap> z2 := ZmqSocket("+inproc://test");;
gap> ZmqSend(z, "notice");
gap> ZmqReceive(z2);
"notice"
gap> ZmqSend(z, ["alpha", "beta"]);
gap> ZmqReceive(z2);
"alpha"
gap> ZmqReceive(z2);
"beta"
ZmqReceiveList will retrieve a message in its entirety from socket and return the result as a list of strings.
gap> z := ZmqPushSocket("inproc://test");;
gap> z2 := ZmqPullSocket("+inproc://test");;
gap> ZmqSend(z, "notice");
gap> ZmqReceiveList(z2);
[ "notice" ]
gap> ZmqSend(z, ["alpha", "beta"]);
gap> ZmqReceiveList(z2);
[ "alpha", "beta" ]
ZmqReceiveListAsString works like ZmqReceiveList, but will return the result a single string, with multiple parts separated by separator.
gap> z := ZmqPushSocket("inproc://test");;
gap> z2 := ZmqPullSocket("+inproc://test");;
gap> ZmqSend(z, "notice");
gap> ZmqReceiveListAsString(z2, "::");
"notice"
gap> ZmqSend(z, ["alpha", "beta"]);
gap> ZmqReceiveListAsString(z2, "::");
"alpha::beta"
ZmqHasMore will return true if a socket has one or more remaining parts of a multi-part message outstanding, false otherwise.
gap> z := ZmqPushSocket("inproc://test");;
gap> z2 := ZmqPullSocket("+inproc://test");;
gap> ZmqSend(z, "notice");
gap> ZmqReceive(z2);
"notice"
gap> ZmqHasMore(z2);
false
gap> ZmqSend(z, ["alpha", "beta"]);
gap> ZmqReceive(z2);
"alpha"
gap> ZmqHasMore(z2);
true
gap> ZmqReceive(z2);
"beta"
gap> ZmqHasMore(z2);
false
ZmqPoll is a facility to determine if messages can be received from one of the sockets listed in inputs or sent to one of the sockets listed in outputs. It returns a list of indices describing the sockets that at least one message can be received from or sent to. The timeout is an integer. If positive, it describes a duration (in milliseconds) after which it will return. If zero, the function will return immediately. If it is -1, then the function will block indefinitely until at least one message can be retrieved from one of the sockets in inputs or at least one message can be sent to one of the sockets in outputs. If the timeout is non-negative, the result can be the empty list. It is guaranteed to have at least one element otherwise.
The indices in the result are in the range [1..Length(inputs)+Length(outputs). An index i less than or equal to Length(inputs) refers to the socket inputs[i]. An index j in the range [Length(inputs)+1..Length(inputs)+Length(outputs) refers to the socket outputs[j-Length(inputs)]. Multiple indices are listed in ascending order (i.e., they form a GAP set).
gap> send1 := ZmqPushSocket("inproc://#1");;
gap> recv1 := ZmqPullSocket("+inproc://#1");;
gap> send2 := ZmqPushSocket();;
gap> recv2 := ZmqPullSocket();;
gap> ZmqSetSendCapacity(send2, 1);
gap> ZmqSetReceiveCapacity(recv2, 1);
gap> ZmqBind(send2, "inproc://#2");
gap> ZmqConnect(recv2, "inproc://#2");
gap> ZmqSend(send2, "alpha");
gap> ZmqSend(send2, "beta");
gap> ZmqPoll([recv1, recv2], [send1, send2], 0);
[ 2, 3 ]
In the example above, the code constructs sockets send2 and recv2 with a capacity to store at most one outgoing and incoming message, respectively. Then the code sends two messages to send2, one of which will be in the incoming buffer of recv2, and the other will remain in the outgoing buffer of send2. At this point, no more messages can be sent to send2, because its outgoing buffer is at capacity, and recv2 has a message that can be received. Conversely, send1 can still accept outgoing messages, and recv1 has no messages.
Thus, the result is the list [2, 3]. The 2 refers to recv2 (as the second socket in the list of inputs), while 3 refers to send1 (as the first socket in the list of outputs).
Sockets have properties that can be set and queried. Most such properties only affect binds and connects that occur after they have been set. Binding or connecting a socket first and then setting a property will not change the behavior of the socket.
ZmqSetIdentity can be used to give the socket an identity. An identity is a string of up to 255 characters that should not start with a null character (the null character is reserved for internal use).
This identity should be globally unique. Uniqueness is not enforced, however, and undefined behavior may result from different sockets with the same identity interacting.
ZmqGetIdentity returns the current identity of the socket.
ZmqSetSendCapacity sets the maximum number of messages that a socket can store in its outgoing buffer.
ZmqSetReceiveCapacity sets the maximum number of messages that a socket can store in its outgoing buffer.
ZmqGetSendCapacity returns the maximum number of messages that a socket can store in its outgoing buffer.
ZmqGetReceiveCapacity returns the maximum number of messages that a socket can store in its incoming buffer.
ZmqSetSendBufferSize sets the size of the transmission buffer used by the underlying operating system structure for sending data.
ZmqGetSendBufferSize returns the size of the transmission buffer used by the underlying operating system structure for sending data.
ZmqSetReceiveBufferSize sets the size of the transmission buffer used by the underlying operating system structure for receiving data.
ZmqGetReceiveBufferSize returns the size of the transmission buffer used by the underlying operating system structure for receiving data.
The ZmqSubscribe function can only be used for Subscriber sockets. After calling it, only messages that begin with the given prefix string will be received by the subscriber. All others will be silently discarded. The function can be used multiple times, and then all messages that match any of the prefixes will be received.
The ZmqUnsubscribe function removes the given prefix string from the socket's subscription list.
The zgap script provides facilities to start a number of child processes controlled by a single master process and to allow for easy coordination between them.
From the shell, run zgap via:
bin/zgap -N <nodes> <gap_options> <gap_files>
Here, <nodes> should be a positive integer that describes the number of workers one wishes to start. The rest of the command line, consisting of gap options and gap files, will be passed to the master and the worker processes verbatim. This allows, for example, the initialization of functions that need to be known by all workers.
The first line of output will be prefixed with [zgap] and will list the directory where zgap will store the files and sockets it uses to communicate. In particular, the logXX.txt files within that directory will contain the output generated by the workers; this is useful for debugging, as the workers do not have a working break loop.
Example:
bin/zgap -N 4 -P 8 -m 1G common.g
On NUMA architectures that support the numactl command, it is possible to further specify which node each worker should be running on. This can take one of two forms:
bin/zgap -N <count>:<start>-<end> bin/zgap -N <count>:+<start>-<end>
Each will distribute <count> worker processes on the physical nodes ranging from <start> to <end> in a round-robin fashion, reusing nodes if there are more workers than nodes. The first mode (without a + sign) will use absolute node numbers, the second will be relative to the master process. See the numactl manual page for further details.
Example:
bin/zgap -N 4:+0-3 -P 8 -m 1G common.g
Note: Currently, zgap can only be run from the GAP root directory. This is an implementation restriction that is to be removed at a later date.
Most of the following API functions take a dest argument, which is used to specify the destination of the operation. To specify a worker thread, dest would have to be an integer in the range from 1 to the number of worker processes; 0 specifies the master process. Multiple processes can be specified by a range or list of integers. The variable ZAll contains a range encompassing the worker processes; ZSelf contains the index of the current worker or 0 for the master.
This function sends cmd to the given destination and executes it there. The command must be a valid GAP statement ending in a semicolon. If dest specifies multiple processes, the command will be executed on all of them.
This function binds the global variable described by the string var to the value expr in all processes listed in dest. Note that expr must evaluate to a serializable value.
gap> ZBind(ZAll, "counter", 0);
This function is the counterpart to ZBind. It will unbind var in all specified processes.
gap> ZUnbind(ZAll, "status");
This function will execute the function specified by the string func in the specified processes. The string func must be the name of a global variable referring to the function to be executed. This function should be created at startup by adding a file to the commandline that defines it in all workers or by ZExec.
gap> ZBind(ZAll, "counter", 0); gap> ZExec(Zall, "add := function(n) counter := counter + n; end;"); gap> ZCall(1, "add", [1]);
This function works like ZCall, except that any return value will be passed to the callback function.
gap> res := false; false gap> ZQuery(1, "ReturnTrue", [], function(x) res := x; end); gap> res; true
ZResponse is a convenience function to construct blocking callbacks for ZCall and ZTask. It returns a record containing a put, a get, and a test function. Here, put is passed as the callback; get can be used to read the returned value; and test can be used to test for the presence of a value.
gap> resp := ZResponse();; gap> ZQuery(1, "Z", [4], resp.put); gap> resp.get(); Z(2^2) gap> resp.test(); true
This function works like ZQuery, except that the function will be executed via a task and callback will be called after the task finishes and returns a result.
This function works like ZCall, except that the function will be executed via a task.
This function does a Read(file) for all specified processes.
This function does a ReadGapRoot(file) for all specified processes.
The functionality described in this section should only be used by experts, and even by those only with caution (especially the parts that relate to the memory model).
Not only is it possible to crash or hang the GAP kernel, it can happen in ways that are very difficult to reproduce, leading to software defects that are discovered only long after deployment of a package and then become difficult to correct.
The performance benefit of using these primitives is generally minimal; while concurrency can induce some overhead, the benefit from micromanaging concurrency in an interpreted language such as GAP is likely to be small.
These low-level primitives exist primarily for the benefit of kernel programmers; it allows them to prototype new kernel functionality in GAP before implementing it in C.
The LOCK operation combined with UNLOCK is a low-level interface for the functionality of the atomic statement.
LOCK takes zero or more pairs of parameters, where each is either an object or a boolean value. If an argument is an object, the region containing it will be locked. If an argument is the boolean value false, all subsequent locks will be read locks; if it is the boolean value true, all subsequent locks will be write locks. If the first argument is not a boolean value, all locks until the first boolean value will be write locks.
Locks are managed internally as a stack of locked regions; LOCK returns an integer indicating a pointer to the top of the stack; this integer is used later by the UNLOCK operation to unlock locks on the stack up to that position. If LOCK should fail for some reason, it will return fail.
Calling LOCK() with no parameters returns the current lock stack pointer.
TRYLOCK works similarly to LOCK. If it cannot acquire all region locks, it returns fail and does not lock any regions. Otherwise, its semantics are identical to LOCK.
UNLOCK unlocks all regions on the stack at stackpos or higher and sets the stack pointer to stackpos.
gap> l1 := ShareObj([1,2,3]);; gap> l2 := ShareObj([4,5,6]);; gap> p := LOCK(l1); 0 gap> LOCK(l2); 1 gap> UNLOCK(p); # unlock both RegionOf(l1) and RegionOf(l2) gap> LOCK(); # current stack pointer 0
HPC-GAP supports hash locks; internally, the kernel maintains a fixed size array of locks; objects are mapped to a lock via hash function. The hash function is based on the object reference, not its contents (except for short integers and finite field elements).
gap> l := [ 1, 2, 3];; gap> f := l -> Sum(l);; gap> HASH_LOCK(l); # lock 'l' gap> f(l); # do something with 'l' 6 gap> HASH_UNLOCK(l); # unlock 'l'
Hash locks should only be used for very short operations, since there is a chance that two concurrently locked objects map to the same hash value, leading to unnecessary contention.
Hash locks are unrelated to the locks used by the atomic statements and the LOCK and UNLOCK primitives.
HASH_LOCK obtains the read-write lock for the hash value associated with obj.
HASH_UNLOCK releases the read-write lock for the hash value associated with obj.
HASH_LOCK_SHARED obtains the read-only lock for the hash value associated with obj.
HASH_UNLOCK_SHARED releases the read-only lock for the hash value associated with obj.
HPC-GAP allows migration of arbitrary objects to the public region. This functionality is potentially dangerous; for example, if two threads try resize a plain list simultaneously, this can result in memory corruption.
Accordingly, such data should never be accessed except through operations that protect accesses through locks, memory barriers, or other mechanisms.
MAKE_PUBLIC makes obj and all its subobjects members of the public region.
MAKE_PUBLIC_NORECURSE makes obj, but not any of its subobjects members of the public region.
The memory models of some processors do no guarantee that read and writes reflect accesses to main memory in the same order in which the processor performed them; for example, code may write variable v1 first, and v2 second; but the cache line containing v2 is flushed to main memory first so that other processors see the change to v2 before the change to v1.
Memory barriers can be used to prevent such counter-intuitive reordering of memory accesses.
The ORDERED_WRITE function guarantees that all writes that occur prior to its execution or during the evaluation of expr become visible to other processors before any of the code executed after.
Example:
gap> y:=0;; f := function() y := 1; return 2; end;; gap> x := ORDERED_WRITE(f()); 2
Here, the write barrier ensure that the assignment to y that occurs during the call of f() becomes visible to other processors before or at the same time as the assignment to x.
This can also be done differently, with the same semantics:
gap> t := f();; # temporary variable gap> ORDERED_WRITE(0);; # dummy argument gap> x := t; 2
Conversely, the ORDERED_READ function ensures that reads that occur before its call or during the evaluation of expr are not reordered with respects to memory reads occurring after it.
There are two new functions to exchange a pair of objects.
SWITCH_OBJ exchanges its two arguments. All variables currently referencing obj1 will reference obj2 instead after the operation completes, and vice versa. Both objects stay within their previous regions.
gap> a := [ 1, 2, 3];; gap> b := [ 4, 5, 6];; gap> SWITCH_OBJ(a, b); gap> a; [ 4, 5, 6 ] gap> b; [ 1, 2, 3 ]
The function requires exclusive access to both objects, which may necessitate using an atomic statement, e.g.:
gap> a := ShareObj([ 1, 2, 3]);; gap> b := ShareObj([ 4, 5, 6]);; gap> atomic a, b do SWITCH_OBJ(a, b); od; gap> atomic readonly a do Display(a); od; [ 4, 5, 6 ] gap> atomic readonly b do Display(b); od; [ 1, 2, 3 ]
FORCE_SWITCH_OBJ works like SWITCH_OBJ, except that it can also exchange objects in the public region:
gap> a := ShareObj([ 1, 2, 3]);; gap> b := MakeImmutable([ 4, 5, 6]);; gap> atomic a do FORCE_SWITCH_OBJ(a, b); od; gap> a; [ 4, 5, 6 ]
This function should be used with extreme caution and only with public objects for which only the current thread has a reference. Otherwise, undefined behavior and crashes can result from other threads accessing the public object concurrently.