Publishing complete book events

Publish once

Publishing is writing the new Top where the strategy reads it: a variable the same thread reads next, or a slot another thread reads, at the price of a cache line moving between cores, 50–100 ns. Publish once is the data-structures chapter’s rule applied here: publish after complete venue events have been applied. One processing batch may contain several complete events, but a recv can stop in the middle of an event and cannot define its boundary. Publishing after each update would pay the transfer every time and, worse, show the strategy states that existed only inside the program: halfway through a message that moves both sides, the copy can briefly hold a bid at or above the ask, which the venue’s matching never leaves standing. The framer must retain incomplete events between reads. After applying each complete event and validating the resulting book, the handler can OR its change flags across a processing batch and publish the final top once. The simplified example below treats each decoded fixed-size update as a complete event; adapting a multi-level venue feed requires preserving its event boundaries:

use std::io;

pub struct FeedHandler<B: Book> {
    book: B,
    last_seq: u64,   // seq of the last update applied
    published: Top,  // the top the strategy was last given
}

impl<B: Book> FeedHandler<B> {
    pub fn run(&mut self, feed: &mut Feed, slot: &TopSlot) -> io::Result<()> {
        let mut batch: Vec<Update> = Vec::with_capacity(4096);
        loop {
            batch.clear();
            feed.recv_batch(&mut batch)?;  // one recv, every whole update decoded
            let mut changed = false;
            for (i, u) in batch.iter().enumerate() {
                match check_seq(self.last_seq, u.seq) {
                    Seq::Next => {
                        changed |= self.book.apply(u);
                        self.last_seq = u.seq;
                    }
                    Seq::Seen => {}                // already applied: drop it
                    Seq::Gap { expected, got } => {
                        // missing an update: recovery takes the rest
                        self.recover(feed, slot, expected, got, &batch[i..])?;
                        changed = false;          // recovery publishes for itself
                        break;
                    }
                }
            }
            if changed {
                let top = self.book.top();
                if top != self.published {        // two changes can cancel out
                    slot.publish(top);            // publish once per batch
                    self.published = top;
                }
            }
        }
    }
}

recv_batch makes one recv call and decodes every complete 48-byte update it returned, keeping any partial one for next time; publish must use the concurrency chapter’s message-passing or synchronised publication protocol; fitting a struct in a cache line does not make a plain struct store atomic. This is the handler in its simplest form: recover stands for everything that follows a gap, and a fuller handler that also records whether the book can be trusted replaces it when recovery is taken apart later in the chapter.

What it costs

Added up for the array: the sequence check about 1 ns; the index about 1 ns; the load and store 2–5 ns, the line almost always in L1; the cursor nothing on most updates and 5–20 ns, with the bitmap, on the few that move the best; the top compare 1–2 ns. In all, 5–30 ns an update, 20–120 cycles at 4 GHz, 0.5–3% of the budget. The tree’s map operation takes 100–500 ns, 400–2,000 cycles, a tenth to a half of a budget: three node visits with a pointer chase each, and on a new or emptied level an allocation or a free of 20–50 ns when a node splits or merges. Lacking a cursor, its top compare also needs the best before and after the change, two walks to the last leaf of 30–100 ns each, so the whole apply is 160–700 ns, unless it keeps its own copy of the best, which is a cursor by another name. The steps are the same; what each touches differs: the array, a line or two it touched a microsecond ago; the tree, three nodes anywhere in the heap.