Fill: price-time priority¶
What an open order fills this step under price-time priority, min(open, max(0, meeting - ahead)): the other side's open quantity at prices the order meets, less the quantity ahead of it on its own side (a better price, or the same price arrived earlier), never below nothing and never above what it has open.
All three are counts of shares; meeting and ahead are folds over the game's book, which it computes and passes in. Source: Harris, Trading and Exchanges, ch. 6 (order precedence rules). Checked against a reference in numpy, which has its own tests.
- Source
- Harris, Trading and Exchanges, ch. 6 (order precedence rules).
- Proof
- reference, invariant, limit.
fill.trait
namespace lusine.finance;
integer fill(integer open, integer meeting, integer ahead)
{
let room = meeting - ahead;
return room <= 0 ? 0 : (room < open ? room : open);
}
What an open order fills this step, min(open, max(0, meeting − ahead)): what meets it at its price, less what is ahead of it on its own side, never below nothing and never above what it has open. All three are counts of shares; meeting and ahead are folds over the game's book, which the game passes in.
import os, sys
root = os.getcwd()
while not os.path.isfile(os.path.join(root, 'docsite.json')):
root = os.path.dirname(root)
sys.path.insert(0, os.path.join(root, 'tools'))
import numpy as np
import matplotlib.pyplot as plt
from lusine import trait_run
EPS = float(np.finfo(np.float32).eps) # Trait's float is binary32
The kernel¶
The law as the library states it.
print(trait_run.source('finance/fill.trait'))
// lusine.finance.fill: what an open order fills this step under price-time priority, min(open, max(0, meeting -
// ahead)): the other side's open quantity at prices the order meets, less the quantity ahead of it on its own side (a
// better price, or the same price arrived earlier), never below nothing and never above what it has open. All three
// are counts of shares; meeting and ahead are folds over the game's book, which it computes and passes in.
// Source: Harris, Trading and Exchanges, ch. 6 (order precedence rules).
// Checked against a reference in numpy, which has its own tests.
namespace lusine.finance;
integer fill(integer open, integer meeting, integer ahead)
{
let room = meeting - ahead;
return room <= 0 ? 0 : (room < open ? room : open);
}
The program¶
Each section runs the kernel over a lattice of items, one an order: the host sets every parameter, and main() binds the kernel over the items.
print(trait_run.law_program('finance/fill.trait', 'fill'))
def fill(**kw):
return trait_run.law('finance/fill.trait', 'fill', **kw)
namespace probe;
lusine.version version = { { number = 1 } };
struct item {
host integer open;
host integer meeting;
host integer ahead;
integer result_0;
};
lattice<item, 1> items(spacing = 1 m, boundary = wall);
void main() { items.result_0 = lusine.finance.fill(items.open, items.meeting, items.ahead); }
Reference: Harris's order precedence¶
Asks of 5 at 100 and 5 at 101 meet a bid of 8 at 101: both asks meet it, nothing is ahead, and it fills 8. A second bid of 4 at 101, arriving after it, has the first's 8 ahead of it and fills the 2 left (Harris, Trading and Exchanges, ch. 6).
got = fill(open=[8, 4], meeting=[10, 10], ahead=[0, 8])
assert list(got) == [8, 2], got
print('the first bid fills', got[0], 'and the second', got[1])
the first bid fills 8 and the second 2
Invariant: the continuous match, order by order¶
Two hundred random books, each a queue of orders on one side already in priority order and a quantity meeting them, all in one run: each order's fill is what the textbook's continuous match gives it, the orders taking in turn what the ones before left, and the queue fills min(its total, what meets it) in all.
rng = np.random.default_rng(301)
books = []
for _ in range(200):
q = rng.integers(1, 50, rng.integers(1, 12))
books.append((q, int(rng.integers(0, 400))))
opens = np.concatenate([q for q, _ in books])
meets = np.concatenate([np.full(len(q), m) for q, m in books])
aheads = np.concatenate([np.concatenate([[0], np.cumsum(q)[:-1]]) for q, _ in books])
got = fill(open=opens, meeting=meets, ahead=aheads)
at = 0
for q, m in books:
left, want = m, []
for x in q:
want.append(min(int(x), left))
left -= want[-1]
mine = got[at:at + len(q)]
assert list(mine) == want and mine.sum() == min(q.sum(), m)
at += len(q)
assert np.all((got >= 0) & (got <= opens))
print(len(books), 'books,', len(opens), 'orders: each the continuous match')
200 books, 1200 orders: each the continuous match
Limit: behind the book, and a deep book¶
An order with more ahead of it than meets it fills nothing, never a negative quantity; nothing meeting fills nothing; a book deeper than all ahead and the order fills it whole.
got = fill(open=[5, 5, 5, 5], meeting=[3, 0, 100, 7], ahead=[7, 0, 20, 7])
assert list(got) == [0, 0, 5, 0], got
print(got)
[0 0 5 0]