Each ALP primitive, every constructor, and every destructor come with performance semantics, in addition to functional semantics.

Performance semantics may differ for different backends– ALP stringently mandates that backends defines them, thus imposing a significant degree of predictability on implementations of ALP, but does not significantly limit possible implementation choices.

Warning: Performance semantics should not be mistaken for performance guarantees. The vast majority of computing platforms exhibit performance variabilities that preclude defining stringent such guarantees.

Performance semantics includes classical asymptotic work analysis in the style of Cormen et alii, as commonly taught as part of basic computer science courses. Aside from making the reasonable (although arguably too uncommon) demand that ALP libraries must clearly document the work complexity of the primitives it defines, ALP furthermore demands such analyses for the following quantities:

how many times operator(s) may be applied,
intra-process data movement from main memory to processing units,
new dynamic memory allocations and/or releases of previously allocated memory, and
whether system calls may occur during a call to the given primitive.

Note: Typically (but not always) the amount of work is proportional to the number of operator applications.; Typically (but not necessarily always) if primitives are allowed to allocate or free dynamic memory, then it may also thus make system calls.

For backends that allow for more than one user process, the following additional performance semantics must be defined:

inter-process data movement, and
how many synchronisation steps a primitive requires to complete.

Defining such performance semantics are crucial to

allow algorithm designers to design the best possible algorithms even if the target platforms and target use cases vary,
allow users to determine scalability under increasing problem sizes, and
allow system architects to determine the qualitative effect of scaling up system resources in an a-priori fashion.

These advantages furthermore do not require expensive experimentation on the part of algorithm designers, users, or system architects. However, it puts a significant demand on the implementers and maintainers of ALP.

See also: Backends

Author: A. N. Yzelman, Huawei Technologies Switzerland AG (2020-current)