Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Quant Cup 1's winning order book implementation
/*****************************************************************************
* QuantCup 1: Price-Time Matching Engine
*
* Submitted by: voyager
*
* Design Overview:
* In this implementation, the limit order book is represented using
* a flat linear array (pricePoints), indexed by the numeric price value.
* Each entry in this array corresponds to a specific price point and holds
* an instance of struct pricePoint. This data structure maintains a list
* of outstanding buy/sell orders at the respective price. Each outstanding
* limit order is represented by an instance of struct orderBookEntry.
*
* askMin and bidMax are global variables that maintain starting points,
* at which the matching algorithm initiates its search.
* askMin holds the lowest price that contains at least one outstanding
* sell order. Analogously, bidMax represents the maximum price point that
* contains at least one outstanding buy order.
*
* When a Buy order arrives, we search the book for outstanding Sell orders
* that cross with the incoming order. We start the search at askMin and
* proceed upwards, incrementing askMin until:
* a) The incoming Buy order is filled.
* b) We reach a price point that no longer crosses with the incoming
* limit price (askMin > BuyOrder.price)
* In case b), we create a new orderBookEntry to record the
* remainder of the incoming Buy order and add it to the global order
* book by appending it to the list at pricePoints[BuyOrder.price].
*
* Incoming Sell orders are handled analogously, except that we start at
* bidMax and proceed downwards.
*
* Although this matching algorithm runs in linear time and may, in
* degenerate cases, require scanning a large number of array slots,
* it appears to work reasonably well in practice, at least on the
* simulated data feed (score_feed.h). The vast majority of incoming
* limit orders can be handled by examining no more than two distinct
* price points and no order requires examining more than five price points.
*
* To avoid incurring the costs of dynamic heap-based memory allocation,
* this implementation maintains the full set of orderBookEntry instances
* in a statically-allocated contiguous memory arena (arenaBookEntries).
* Allocating a new entry is simply a matter of bumping up the orderID
* counter (curOrderID) and returning a pointer to arenaBookEntries[curOrderID].
*
* To cancel an order, we simply set its size to zero. Notably, we avoid
* unhooking its orderBookEntry from the list of active orders in order to
* avoid incurring the costs of pointer manipulation and conditional branches.
* This allows us to handle order cancellation requests very efficiently; the
* current implementation requires only one memory store instruction on
* x86_64. During order matching, when we walk the list of outstanding orders,
* we simply skip these zero-sized entries.
*
* The current implementation uses a custom version of strcpy() to copy the string
* fields ("symbol" and "trader") between data structures. This custom version
* has been optimized for the case STRINGLEN=5 and implements loop unrolling
* to eliminate the use of induction variables and conditional branching.
*
* The memory layout of struct orderBookEntry has been optimized for
* efficient cache access.
*****************************************************************************/
#include < stdio.h > #include < strings.h > #include < stdlib.h > #include "engine.h"
/* Enable/disable optimizations */
#
define UNROLL_STRCPY
# define MAX_NUM_ORDERS 1010000
// #define DEBUG (enable/disable debugging)
# ifdef DEBUG# define ASSERT(c) do {\
if (!(c)) {
fprintf(stderr, "ASSERT failure at line %d\n", __LINE__);\
exit(1);
}
} while (0)#
else# define ASSERT(c)# endif
# ifdef UNROLL_STRCPY# define COPY_STRING(dst, src) do {\
dst[0] = src[0];
dst[1] = src[1];
dst[2] = src[2];\
dst[3] = src[3]; /* dst[4] = src[4]; */ \
} while (0)#
else# include < string.h > #define COPY_STRING(dst, src) strcpy(dst, src)# endif
/* struct orderBookEntry: describes a single outstanding limit order
(Buy or Sell). */
typedef struct orderBookEntry {
t_size size; /* Order size */
struct orderBookEntry * next; /* Next entry in the pricePoint list */
char trader[4];
}
orderBookEntry_t;
/* struct pricePoint: describes a single price point in the limit order book. */
typedef struct pricePoint {
orderBookEntry_t * listHead;
orderBookEntry_t * listTail;
}
pricePoint_t;
/** Global state ***/
/* An array of pricePoint structures representing the entire limit order book */
static pricePoint_t pricePoints[MAX_PRICE + 1];
static t_orderid curOrderID; /* Monotonically-increasing orderID */
static unsigned int askMin; /* Minimum Ask price */
static unsigned int bidMax; /* Maximum Bid price */
/* Statically-allocated memory arena for order book entries. This data
structure allows us to avoid the overhead of heap-based memory allocation. */
static orderBookEntry_t arenaBookEntries[MAX_NUM_ORDERS];
static orderBookEntry_t * arenaPtr;
#
define ALLOC_BOOK_ENTRY(id)
void init() {
/* Initialize the price point array */
bzero(pricePoints, (MAX_PRICE + 1) * sizeof(pricePoint_t));
/* Initialize the memory arena */
bzero(arenaBookEntries, MAX_NUM_ORDERS * sizeof(orderBookEntry_t));
arenaPtr = arenaBookEntries; // Bring the arena pointer into the cache
curOrderID = 0;
askMin = MAX_PRICE + 1;
bidMax = MIN_PRICE - 1;
}
void destroy() {}
/* Insert a new order book entry at the tail of the price point list */
void ppInsertOrder(pricePoint_t * ppEntry, orderBookEntry_t * entry) {
if (ppEntry - > listHead != NULL)
ppEntry - > listTail - > next = entry;
else
ppEntry - > listHead = entry;
ppEntry - > listTail = entry;
}
/* Report trade execution */
void EXECUTE_TRADE(const char * symbol,
const char * buyTrader,
const char * sellTrader, t_price tradePrice,
t_size tradeSize) {
t_execution exec;
if (tradeSize == 0) /* Skip orders that have been cancelled */
return;
COPY_STRING(exec.symbol, symbol);
exec.price = tradePrice;
exec.size = tradeSize;
exec.side = 0;
COPY_STRING(exec.trader, buyTrader);
exec.trader[4] = '\0';
execution(exec); /* Report the buy-side trade */
exec.side = 1;
COPY_STRING(exec.trader, sellTrader);
exec.trader[4] = '\0';
execution(exec); /* Report the sell-side trade */
}
/* Process an incoming limit order */
t_orderid limit(t_order order) {
orderBookEntry_t * bookEntry;
orderBookEntry_t * entry;
pricePoint_t * ppEntry;
t_price price = order.price;
t_size orderSize = order.size;
if (order.side == 0) { /* Buy order */
/* Look for outstanding sell orders that cross with the incoming order */
if (price >= askMin) {
ppEntry = pricePoints + askMin;
do {
bookEntry = ppEntry - > listHead;
while (bookEntry != NULL) {
if (bookEntry - > size < orderSize) {
EXECUTE_TRADE(order.symbol, order.trader,
bookEntry - > trader, price, bookEntry - > size);
orderSize -= bookEntry - > size;
bookEntry = bookEntry - > next;
} else {
EXECUTE_TRADE(order.symbol, order.trader,
bookEntry - > trader, price, orderSize);
if (bookEntry - > size > orderSize)
bookEntry - > size -= orderSize;
else
bookEntry = bookEntry - > next;
ppEntry - > listHead = bookEntry;
return ++curOrderID;
}
}
/* We have exhausted all orders at the askMin price point. Move on to
the next price level. */
ppEntry - > listHead = NULL;
ppEntry++;
askMin++;
} while (price >= askMin);
}
entry = arenaBookEntries + (++curOrderID);
entry - > size = orderSize;
COPY_STRING(entry - > trader, order.trader);
ppInsertOrder( & pricePoints[price], entry);
if (bidMax < price)
bidMax = price;
return curOrderID;
} else { /* Sell order */
/* Look for outstanding Buy orders that cross with the incoming order */
if (price <= bidMax) {
ppEntry = pricePoints + bidMax;
do {
bookEntry = ppEntry - > listHead;
while (bookEntry != NULL) {
if (bookEntry - > size < orderSize) {
EXECUTE_TRADE(order.symbol, bookEntry - > trader,
order.trader, price, bookEntry - > size);
orderSize -= bookEntry - > size;
bookEntry = bookEntry - > next;
} else {
EXECUTE_TRADE(order.symbol, bookEntry - > trader,
order.trader, price, orderSize);
if (bookEntry - > size > orderSize)
bookEntry - > size -= orderSize;
else
bookEntry = bookEntry - > next;
ppEntry - > listHead = bookEntry;
return ++curOrderID;
}
}
/* We have exhausted all orders at the bidMax price point. Move on to
the next price level. */
ppEntry - > listHead = NULL;
ppEntry--;
bidMax--;
} while (price <= bidMax);
}
entry = arenaBookEntries + (++curOrderID);
entry - > size = orderSize;
COPY_STRING(entry - > trader, order.trader);
ppInsertOrder( & pricePoints[price], entry);
if (askMin > price)
askMin = price;
return curOrderID;
}
}
/* Cancel an outstanding order */
void cancel(t_orderid orderid) {
arenaBookEntries[orderid].size = 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.