charles-cooper / itch-order-book

Fast implementation of an ITCH order book

This is a very fast implementation of the ITCH order book, clocking in at around 61ns / tick (or 16 million messages / second, tested on a 2012 i7-3820), offering fast updates and O(1) access to any price level (to get the price is a single dereference, the aggregate quantity is another dereference). It only calculates the aggregate quantities at each price and does not track the queue depth for each order.

Among other things, there is no hashtable or trees used, only <vector>s and C arrays, and no allocation beyond what <vector> does. For description and implementation see order_book.h.

Protocol specification: http://www.nasdaqtrader.com/content/technicalsupport/specifications/dataproducts/NQTVITCHSpecification.pdf (ITCH 5.0). Binary file spec: http://www.nasdaqtrader.com/content/technicalSupport/specifications/dataproducts/binaryfile.pdf.

In order to run it, ./build.sh && ./a.out < [file]. Note that the implementation is fast enough that you will likely to be I/O bound - in order to find out how fast it really is you should 'warm-up' by loading the file into the buffer cache using cat [file] > /dev/null. Sample files available at ftp://emi.nasdaq.com/ITCH/ (the file name has the format MMDDYYYY.NASDAQ_ITCH50.gz).

itch-order-book's Issues

Document ITCH version, add link to sample file

What version of ITCH does this work with?

"Uh oh bad code 74"

Hi Charles,

Just downloaded the code as well as a couple of files from the Nasdaq server to try it out and keep hitting this error code after a while.
(I added the Trace flag and I see that the program is working but then it just exists with error code 74.

Uh oh bad code 74
a.out: main.cpp:148: int main(): Assertion `false' failed.
Aborted (core dumped)

Has it happened to you? Any idea on how to solve it?

Thank you.

PS: I am using the last version of clang on Linux.

Replace hard tabs with soft tabs

Kind of self explanatory. Hard tabs are ugly, not consistent across editors/viewers, etc.

evaluation order of function arguments is not defined

At this point (and possibly other places) there appears to be a data dependency between the evaluation of function arguments.

In order to make sure the read calls happen in the order you intend, they would have to be made in separate statements.

Recommended Speed Improvements

Yours:

# cpuset -c -l4 /usr/bin/time -h ./a.out < NASDAQ.ITCH50
31.84s real 7.66s user 23.68s sys

Mine:

# cpuset -c -l4 /usr/bin/time -h ./maker < NASDAQ.ITCH50
19.68s real 6.59s user 13.08s sys

Neither program was set to build an actual orderbook so this is just testing the ability to read the packets from the accompanying file and provide them to a given function to process the packets. My version of this particular part of the program is 38.19% faster than yours.

The difference in speed comes down to you copying the packet contents into `buf', while my program simply returns a pointer to what resides in the network buffer ensuring at all times the complete packet contents exists.

To put it another way, in my version there is no copying from userland buffer to userland buffer. The copy happens just once when read from the socket.

My version is also written in C but that is mostly irrelevant. Here is the actual function which handles returning the pointer:

void *circular_getp(circular *c, size_t n, int *match)
{
  uint32_t avail;

  if(n > PAGESIZE){
    *match = -1;
    errno = EINVAL;
    return 0;
  }

  while((avail = c->tail - c->head) < n){
    ssize_t r = oneread(c->op,c->fd,c->x + c->tail, PAGESIZE - avail);
    if(r <= 0) { *match = r; return 0; }
    c->tail += r;
  }

  *match = 1;
  return c->x + c->head;
}

Avoid copying when you don't have to!

Cheers!

Edit: I couldn't get the code to align properly. Github hates me. Sorry. ;(

Ask levels in reverse order?

This is more a question than an issue: why don't you keep the ask levels in reverse sorted order?

Since most updates appear near best bid/ask, keeping ask levels in reverse sorted order would mean to have best ask at the end of the vector instead of at the beginning, thus being more efficient, if I'm not mistaken.

Missing file ?

I cannot run build since the itch.h includes the endian.h which does not exist:

$ sh build.sh 
In file included from main.cpp:6:
./itch.h:2:10: fatal error: 'endian.h' file not found
#include <endian.h>
         ^~~~~~~~~~
1 error generated.
In file included from main.cpp:6:
./itch.h:2:10: fatal error: 'endian.h' file not found
#include <endian.h>
         ^~~~~~~~~~
1 error generated.

I'm on MacOs Mojave 10.14.4.

$ clang --version
Apple LLVM version 10.0.1 (clang-1001.0.46.4)
Target: x86_64-apple-darwin18.5.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

I have googled the issue but this does not help.

Thanks.

During replace ask is converted to bid bug?

Hi @charles-cooper,

Thank you for really interesting approach of building order book. Recently I have been investigating various implementations available as an open-source and your implementation I find at this moment is one of most comprehensive ones, though code base isn't that big! :)
Anyways, I've got a query. During replace, specifically for this part of code:

itch-order-book/order_book.h

Line 328 in 095ac97

if (!bid) {

Why ask price (negative) is converted for bid price (positive) during replace?

As an example (using BOOST unit testing):

BOOST_AUTO_TEST_CASE(TestForCharlesCooper)
{
    // add ask orders
    order_book::add_order(order_id_t(1), book_id_t(1), sprice_t(-2500), qty_t(25));
    order_book::add_order(order_id_t(2), book_id_t(1) ,sprice_t(-2350), qty_t(5));

    // Expect 2 ask orders & 0 bids
    BOOST_CHECK(order_book::s_books[1].m_offers.size() == 2);
    BOOST_CHECK(order_book::s_books[1].m_bids.size() == 0);

    // Now replace best ask to lower it
    order_book::replace_order(order_id_t(2), order_id_t(3), qty_t(5), sprice_t(-2400));

    // Expect 2 ask orders
    BOOST_CHECK(order_book::s_books[1].m_offers.size() == 2);
    BOOST_CHECK(order_book::s_books[1].m_bids.size() == 0);
}

using gdb I see following:

(gdb) p order_book::s_books[1].m_bids
$10 = std::vector of length 1, capacity 1 = {{
    m_price = (unknown: 0x960),
    m_ptr = (unknown: 0x1)
  }}
(gdb) p order_book::s_books[1].m_offers
$11 = std::vector of length 1, capacity 2 = {{
    m_price = (unknown: 0xfffff63c),
    m_ptr = 0
  }}
(gdb) p (int)order_book::s_books[1].m_bids.begin()->m_price
$12 = 2400
(gdb) p (int)order_book::s_books[1].m_offers.begin()->m_price
$13 = -2500
(gdb)

I think following code is redundant:

  static void replace_order(order_id_t const old_oid, order_id_t const new_oid,
                            qty_t const new_qty, sprice_t new_price)
  {
#if TRACE
    printf("REPLACE %lu %lu %d %u\n", old_oid, new_oid, new_price, new_qty);
#endif  // TRACE
    order_t *order = oid_map.get(old_oid);
    order_book *book = &s_books[MKPRIMITIVE(order->book_idx)];
    bool const bid = is_bid(book->s_levels[order->level_idx].m_price);
    book->DELETE_ORDER(order);
    //TODO Bug?
    /*if (!bid) {
      new_price = sprice_t(-1 * MKPRIMITIVE(new_price));
    }*/
    book->add_order(new_oid, order->book_idx, new_price, new_qty);
  }
};

[Question] Clarification on the Role of execute_order in Relation to add_order

I apologize if this question seems basic, but I'm trying to understand the architectural decision behind the execute_order method in your order book implementation. From my understanding, typically in an order-driven market, trades occur automatically when a new order crosses the bid-ask spread. Given this, I'm curious why execute_order is implemented as a separate method that requires external invocation. Shouldn't the add_order function be designed to automatically trigger a trade execution if the new order's price crosses the spread? Could you please explain the rationale behind requiring execute_order to be called separately instead of handling this within the add_order logic?

Thank you for your time and help!

sorting order of m_bids and m_asks

sorry, if I misread the code, but

shouldn't be the m_bids sorted ascending and the m_offers sorted decreasing based on the price? Because currently it seems both are sorted ascending. So when you add a new offer, you try to search for the place in the m_offers array from the wrong side. (by wrong, I mean it is more likely that the new order will be added around the current market price)

cannot build

What is the suggested compiler for this? I tried:

$ clang++ --version
clang version 3.3 (branches/release_33 183898)
$ g++ --version
g++ (SUSE Linux) 4.8.1 20130909 [gcc-4_8-branch revision 202388]
$ icpc --version
icpc (ICC) 17.0.4 20170411

and none of them works.

g++ -O3 -march=native -std=c++1y main.cpp bufferedreader.cpp
In file included from main.cpp:6:0:
itch.h:28:46: error: template declaration of 'constexpr const unsigned char netlen'
 template<MSG __type> unsigned char constexpr netlen = -1;