Performance - APL Wiki

Performance

From APL Wiki

Jump to navigation<br>Jump to search<br>Performance refers to the speed with which programs are executed in a particular language implementation. While a language such as APL cannot inherently be fast or slow, it is often described as being suitable to high-performance implementation, and there are many APL implementations focused partially or exclusively on performance. Currently-developed array-family implementations that advertise high performance include Dyalog APL, J, K (both Kx and Shakti), and Q, while research projects focused primarily on performance include APEX, Co-dfns, SaC, Futhark, and TAIL.

While dynamically-typed interpreted languages are typically considered to be slow (that is, by nature they lead implementations to run slowly), APL code which uses primarily flat arrays has been described as an excellent fit for modern hardware,[1] and Dyalog APL can in some cases perform better than straightforward C implementations.[2][3] Taking advantage of a high-performance implementation often requires writing in a flatter style, with few or no boxes or nested arrays, and compiled or GPU-based APLs may not fully support nested arrays.

Contents

1 Arrays and performance

2 Performant implementation

2.1 Internal datatypes

2.2 Fast array operations

2.2.1 Implementing APL with APL

2.3 Alternate array representations

2.4 Reference counting and data reuse

2.5 Operation merging and dynamic compilation

2.6 Ahead-of-time compilation

2.7 APL hardware

3 Performant usage

3.1 Changing representation

4 References

Arrays and performance

The central concept underlying the high-performance array languages currently in use is to take advantage of the regularity of arrays. Implementations implement primitives or short combinations of primitives with fast array algorithms, so that a program can make effective use of computer hardware if these primitives make up the bulk of its computation. Arrays allow for these fast algorithms when they are homogeneous in type: that is, they have a regular shape, which is part of the definition of a multidimensional array; and their elements can be stored with the same type. The type used should also be supported by the hardware (usually, the CPU's vector processor), which for example makes IEEE 754 floats the standard floating-point format in high-performance APLs.

When APL programs are evaluated as a sequence of array operations that don't interact with each other, the time taken for a program is simply the total of the time taken by each primitive. Two different types of costs contribute to a primitive's performance: "fixed" costs that don't scale with the size of the arguments (but could vary somewhat based on other properties), and "variable" costs that do. These variable costs are usually proportional to the argument or result size, but may be more complicated. The simplest model of array primitive performance that takes this divide into account is that a given primitive has a constant "overhead" time for each evaluation, and then processes its input at a fixed rate, called "throughput". The advantage of array programming is that this throughput can be made much lower than in other paradigms. However, when the arrays used are small, a program's performance will instead be dominated by overhead, which tends to be high even relative to other interpreted languages because most APL interpreters store all data in arrays. Overhead for a primitive might be tens or hundreds of nanoseconds while throughput can be many elements per nanosecond, so that throughput begins to be the dominant cost at arrays larger than about a thousand elements.

To make array operations fast, arrays are stored in a regular format in memory, so that all data about the format can be kept in the array's "header" and read only before, not during, data processing. This means that elements in the array must have the same storage type for efficient operation. Flat array model languages with or without boxes require that arrays have a homogeneous type (all numbers, all characters, or all boxes); nested APLs do not, but store homogeneous arrays differently and aren't as efficient when processing mixed-type arrays. Fast APLs tend to use several internal types to operate efficiently on subsets of the available numbers like integers or booleans, and may coerce numbers to a common type to ensure that an array is homogeneous in memory.

In the simplest case, homogeneous array storage allows an implementation to use specialized code to run a primitive on each type. Because this special code is written in a low-level language with complete knowledge of the types in use, it can attain a throughput similar to that of the implementation language (usually a low-level language such as C) for the primitive—although this will tend to leave overall algorithms running slower than that language because in APL they have been split into multiple passes. APL's array...