(`⎕io←0`

and timings are done in Dyalog version 15.0.)

## Table Look-Up

Some functions can be computed faster by table look-up than a more traditional and more conventional calculation. For example:

```
b←?1e6⍴2
cmpx '*b' '(*0 1)[b]'
*b → 1.32E¯2 | 0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
(*0 1)[b] → 1.23E¯3 | -91% ⎕⎕⎕
```

Some observations about this benchmark:

**(a)** The advantage of table look-up depends on the time to calculate the function directly, *versus* the time to do indexing, `⍺[⍵]`

or `⍵⌷⍺`

, plus a small amount of time to calculate the function on a (much) smaller representative set.

Indexing is particularly efficient when the indices are boolean:

```
bb←b,1
bi←b,2
cmpx '2 3[bb]' '2 3 3[bi]'
2 3[bb] → 1.12E¯4 | 0% ⎕⎕⎕⎕⎕
2 3 3[bi] → 7.39E¯4 | +558% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
```

`bi`

is the same as `bb`

except that the last element of `2`

forces it to be 1-byte integers (for `bi`

) instead of 1-bit booleans (for `bb`

).

**(b)** Although the faster expression works best with 0-origin, the timing for 1-origin is similar.

```
cmpx '*b' '{⎕io←0 ⋄ (*0 1)[⍵]}b'
*b → 1.32E¯2 | 0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
{⎕io←0 ⋄ (*0 1)[⍵]}b → 1.22E¯3 | -91% ⎕⎕⎕
```

That is, if the current value of `⎕io`

is 1, the implementation can use a local `⎕io`

setting of 0.

**(c)** The fact that `*b`

is currently slower than `(*0 1)[b]`

represents a judgment by the implementers that `*b`

is not a sufficiently common computation to warrant writing faster code for it. Other similar functions already embody the table look-up technique:

```
cmpx '⍕b' '¯1↓,(2 2⍴''0 1 '')[b;]'
⍕b → 6.95E¯4 | 0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
¯1↓,(2 2⍴'0 1 ')[b;] → 6.92E¯4 | -1% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
```

## Small Domains

Table look-up works best for booleans, but it also works for other small domains such as 1-byte integers:

```
i1←?1e6⍴128 ⍝ 1-byte integers
cmpx '*i1' '(*⍳128)[i1]'
*i1 → 1.48E¯2 | 0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
(*⍳128)[i1] → 9.30E¯4 | -94% ⎕⎕
cmpx '○i1' '(○⍳128)[i1]'
○i1 → 2.78E¯3 | 0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
(○⍳128)[i1] → 9.25E¯4 | -67% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
```

In general, a table for 1-byte integers needs to have values for `¯128+⍳256`

. Here `⍳128`

is used to simulate that in C indexing can be done on 1-byte indices without extra computation on the indices. In APL, general 1-byte indices are used as `table[i1+128]`

; in C, the expression is `(table+offset)[i]`

.

Domains considered “small” get bigger all the time as machines come equipped with ever larger memories.

## Larger Domains

Table look-up is applicable when the argument is not a substantial subset of a large domain and there is a fast way to detect that it is not.

```
i4s←1e7+?1e6⍴1e5 ⍝ small-range 4-byte integers
G←{(⊂u⍳⍵)⌷⍺⍺ u←∪⍵}
cmpx '⍟i4s' '⍟G i4s'
⍟i4s → 1.44E¯2 | 0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
⍟G i4s → 9.59E¯3 | -34% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
```

The definition of `G`

implements that the argument is not used directly as indices (as in `(⊂⍵)⌷⍺⍺ u`

) but needed to be looked up, the `u⍳⍵`

in `(⊂u⍳⍵)⌷⍺⍺ u`

. Thus both index-of and indexing are key enablers for making table look-up competitive.

§4.3 of *Notation as a Tool of Thought* presents a different way to distribute the results of a calculation on the “nub” (unique items). But it takes more time and space and is limited to numeric scalar results.

```
H←{(⍺⍺ u)+.×(u←∪⍵)∘.=⍵}
i4a←1e7+?1e4⍴1e3 ⍝ small-range 4-byte integers
cmpx '⍟i4a' '⍟G i4a' '⍟H i4a'
⍟i4a → 1.56E¯4 | 0%
⍟G i4a → 6.25E¯5 | -60%
⍟H i4a → 1.78E¯1 | +113500% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
```

The benchmark is done on the smaller `i4a`

as a benchmark on `i4s`

founders on the `≢∪⍵`

by `≢⍵`

boolean matrix (for `i4s`

, 12.5 GB = `×/ 0.125 1e5 1e6`

) created by `H`

.

## Mathematical Background

“New Math” teaches that a function is a set of ordered pairs whose first items are unique:

`*⍵: {(⍵,*⍵)|⍵∊`

The set of all *C*} `(⍵,*⍵)`

where `⍵`

is a complex number

`⍟⍵: {(⍵,⍟⍵)|⍵∊`

The set of all *C*~{0}} `(⍵,⍟⍵)`

where `⍵`

is a non-zero complex number

`○⍵: {(⍵,○⍵)|⍵∊`

The set of all *C*} `(⍵,○⍵)`

where `⍵`

is a complex number

`⍕⍵: {(⍵,⍕⍵)|0=⍴⍴⍵} `

The set of all `(⍵,⍕⍵)`

where `⍵`

is a scalar

When `⍵`

is restricted (for example) to the boolean domain, the functions, the sets of ordered pairs, are more simply represented by enumerating all the possibilities:

`*⍵: {(0,1), (1,2.71828)}`

⍟⍵: {(0,Err), (1,0)}

○⍵: {(0,0), (1,3.14159)}

⍕⍵: {(0,'0'), (1,'1')}

## Realized and Potential Performance Improvements

**realized** (available no later than 15.0)

boolean 1-byte integer |
`⍕ ∘.f` `⍕ a∘⍕` |

**potential** (non-exhaustive list)

boolean 1-byte integer 2-byte integer small-range 4-byte integer |
`* ⍟ | - ○ ! ⍳ a∘f f.g` `* ⍟ | - ○ × ! ⍳ a∘f f.g ∘.f` `* ⍟ | - ○ × ⍳ a∘f` `* ⍟ | ×` |

`a`

is a scalar; `f`

and `g`

are primitive scalar dyadic functions.