Order book/matching algorithms which are used by Equities exchanges

Mike Warn

unread,

Apr 25, 2015, 5:56:41 AM4/25/15

to mechanica...@googlegroups.com

Say I need to write world class exchange. How I will implement matching engine and order book. Can someone explain me algorithms which may be used for order book and matching: hash maps, lists, etc.

Perhaps someone worked for an exchange and may share some experience. Thanks.

any articles or books you may recommend to read?

Greg Young

unread,

Apr 25, 2015, 5:59:17 AM4/25/15

to mechanica...@googlegroups.com

Getting to millions of orders per second is fairly trivial. Io is normally a bigger problem.

--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Greg Young

unread,

Apr 25, 2015, 6:01:59 AM4/25/15

to mechanica...@googlegroups.com

Btw when working in it (algo trading not market but same data). I used an array list for order book (insertion sort) tried lots of other fancy stuff but couldnt beat it for actual data almost everything you care about and 90+% of orders happen in the top 5 or so positions.

Martin Thompson

unread,

Apr 25, 2015, 6:18:02 AM4/25/15

to mechanica...@googlegroups.com

The challenge is getting to millions per second and being very consistent across all order types and market conditions. The edge cases can get really ugly.

There is a lot of neat stuff you can do with math rather than branching. For example, don't have two sides to a market - have negative prices and quantities for the sell side. With this sort thinking you can play to the L1 prefetchers and keep the code cache really small. It is so easy to blow the 32K code cache on x86 processor.

When it comes to data structures you will find you need to roll your own to get very consistent performance. Exact features come down to what order types you support. Simple market and limit are easy. What about composite orders such as stops, conditionals, or even derivatives? Then you have the GT, FOK, IOC, and all that lot that putting matching constraints on the order execution.

I've found that IO, marshalling, and threading are the usual mistakes people make. Once that is sorted out then the order matching itself usually is the cause of the outliers due to unconsidered business complexity in core algorithms. You need to think O(1) or O(log log n) to be predictable which are both possible with the right upfront thinking and business understanding.

Darach Ennis

unread,

Apr 25, 2015, 7:00:20 AM4/25/15

to mechanica...@googlegroups.com

There used to be a pretty good spec and writeup of a reasonable problem + data structure here for a university competition called quantcup.

The site is gone but the way back machine remembers the spec:

http://web.archive.org/web/20110310171841/http://www.quantcup.org/home/spec

The winning entry is still available:

https://dl.dropboxusercontent.com/u/3001534/engine.c

The code is illustrative at best. Mr T points out some issues but the plethora of order cancellation, replace and rejection logic take a lot of care to get right.

A good resource for the states/transitions are contained in the FIX protocol documentation appendices but even they are incomplete and exchanges and brokers tend to deviate so YMMV.

Cheers,

Darach.

--

Vitaly Davidovich

unread,

Apr 25, 2015, 9:26:22 AM4/25/15

to mechanica...@googlegroups.com

Order books tend to be cache sensitive since the actual instructions involved are usually pretty cheap. So anything you can do to minimize how much data is touched and/or improve locality will help nicely. Some basic things for java would be use intrusive pointers rather than wrapper objects, avoid java generics (e.g. don't use jdk array list and the like), try to keep code devirtualized unless you verify that JIT does it for you in the way you want, minimize type hierarchy of objects involved, use object pools rather than letting GC manage order book objects, etc. This is one of those things where the individually little inefficiencies that java adds really add up, so keeping abstraction to a minimum helps (unfortunately java has some weak spots in terms of zero cost abstractions).

I agree with Greg that most activity in an order book is centralized around the top, and so you can use that knowledge to keep things simpler and faster for common case.

sent from my phone