Sortedness flags in primitive implementation

CBQN has flags for arrays to indicate that the cells are ordered (as if sorted): one for ascending ordering and one for descending. Both flags together mean all cells are the same. These flags can be set in many cases, and allow for faster operation in many primitives, including asymptotic improvements. They're particularly important for Bins (โ‹โ’) to avoid checking that a large ๐•จ is sorted in order to search a much smaller ๐•ฉ.

Setting flags

Trivial cases of arithmetic imply flags: for the identity, flags of a are maintained, and constant results can have both flags set.

Many primitives are monotonic in each argument. For example, if aโ‰คb, then (a<k)โ‰ฅ(b<k), that is, < is monotonically descending in ๐•จ. In the table below, + indicates an ascending argument, which corresponds to maintained order, while - indicates a descending argument and swapped order. The result inherits any flags shared by ๐•จ and ๐•ฉ (so, a bitwise and) after swapping flags for any descending arguments. Since it's reused, a scalar argument is effectively constant and should count as having both flags set. Table โŒœ counts as having a constant right argument.

Prim Bool ๐•จ ๐•ฉ
+โŒŠโŒˆ โˆจโˆงร— + +
>โ‰ฅ-ยฌ + -
<โ‰ค - +

Multiplication by a constant factor with ร—โˆงรท, such as kร—v or vรทk, maintains the ordering of v if k is positive, reverses it if negative, and gives a constant result if zero and v is finite.

The following scans F` have ordered results. Since F`โŒพโŒฝ applies โŒฝ to the result of F`, it gives the opposite ordering.

Prim Bool Order
โŒŠ ร—โˆง Ascending
โŒˆ +โˆจ Descending

Other primitives have the effects listed below.

Prim Monadic Dyadic
โ†• Sorted up Same as ๐•ฉ
/ Sorted up Same as ๐•ฉ
โ†‘ Sorted up Same as ๐•ฉ if no fills
โ†“ Same as ๐•ฉ Same as ๐•ฉ
โŒฝ Swaps flags
โฅŠ sโฅŠatom is constant
โŠ Same as ๐•จ if ๐•ฉ up, swapped if ๐•ฉ down
โŠ Up if ๐•ฉ sorted
โท Same as ๐•ฉ
โŠ” Elements sorted up Elements same as ๐•ฉ
โˆพยซยป Checkable if ๐•จ and ๐•ฉ both ordered

As โˆพยซยป are fast operations and require a check that can be relatively expensive on short arguments, it's not clear whether they should try to maintain sortedness flags.

Using flags

Ordering functions โˆงโˆจโ‹โ’ can use flags in obvious ways: pre-sorted arguments make Sort and Grade trivial, and Bins should check for a sortedness flag before attempting to verify that ๐•จ is sorted.

Both Bins โ‹โ’ and Searches โŠโŠ’โˆŠโท can apply adaptive galloping methods if both arguments are sorted. There's extensive research on these techniques but I don't have much experience with them.

The minimum and maximum of an ordered list are its first and last cells (reversed if sorted down). This is useful for primitives that perform range checking, as well as folds and scans with โŒŠ or โŒˆ. In particular, the scan either returns ๐•ฉ or acts as โŠฃ`.

Sorted arguments can be split into runs with binary searches. If the range is much smaller than the length then the runs must be long on average. Then operations such as /โผ or +ยด where a run can be processed in constant time can process runs quickly. For example, +ยด on a sorted-descending boolean list is simply the index of the first 0 as found by a binary search. Other cases include ๐•ฉ for monadic /, ๐•จ for / and โŠ”, scans with + or boolean โ‰ =, and Match (โ‰กโ‰ข) if both arguments are sorted in the same direction.

Small-range selection can be performed with in-register shuffles. For โŠ with sorted ๐•จ, an adaptive technique is to operate on ๐•จ one vector register at a time, checking the range with the first and last element. Then either a shuffle or gather can be used as appropriate, or even a broadcast if the first and last index are equal.