ALP User Documentation 0.7.0
Algebraic Programming User Documentation
Performance Semantics

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

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:

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:

Defining such performance semantics are crucial to

  1. allow algorithm designers to design the best possible algorithms even if the target platforms and target use cases vary,
  2. allow users to determine scalability under increasing problem sizes, and
  3. 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)