Quant Cup 1's winning order book implementation

engine.c

/*****************************************************************************
 *                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;
}