How fast is your limit order book implementation?

I think the idea is to use orderid -> order object which maintains node pointers to maintain the linked list with.

 

Python eh?

 

I see. Btw if you're using gcc, you might want to be careful with unordered_map. The gcc 4.7 implementation is broken (slow).

 

fpga based

http://www.novasparks.com/news-and-...book-capability-for-global-cash-equities.html

 

C#, with a lot of System.Collections.Concurrent;

Actually, I think a lot of this game is about knowing what you can throw away.

 

time priority is maintained in the list, but because I need to make assumptions as to where cancels, mods affect the queue I found that a map allows for o(1) lookups of specific order qtys that need to be removed as per my queueing model. As a result the cancels/mods aren't always o(1) - only in the best case scenario. I've benchmarked this against a list-only implementation and found that including the map speeds things up considerably (cant recall the exact figures any more - it's been a while). hft_boy is on the money with his assumption.

 

Thanks for the tip. I was not aware of this.

 

I don't get it. What does it actually do?

 

Moves the bottleneck, & costs money.

 

Here is my implementation. I never benchmarked it, but it has to be in the order of nanoseconds for each operation.

Code:

package com.jbooktrader.platform.marketdepth;

import com.jbooktrader.platform.marketbook.*;
import com.jbooktrader.platform.util.*;

import java.text.*;
import java.util.*;

public class MarketDepth {
    private final LinkedList<MarketDepthItem> bids, asks;
    private final LinkedList<Double> balances;
    private double averageBalance;
    private double midPointPrice;
    private final DecimalFormat df2;
    private int volume, previousVolume;
    private int cumulativeBid, cumulativeAsk;


    public MarketDepth() {
        bids = new LinkedList<MarketDepthItem>();
        asks = new LinkedList<MarketDepthItem>();
        balances = new LinkedList<Double>();
        df2 = NumberFormatterFactory.getNumberFormatter(2);
    }

    public synchronized String getSizes() {
        return cumulativeBid + "-" + cumulativeAsk;
    }

    public synchronized String getTop() {
        return bids.getFirst().getPrice() + "-" + asks.getFirst().getPrice();
    }

    public void reset() {
        bids.clear();
        asks.clear();
        balances.clear();
    }

    private int getCumulativeSize(LinkedList<MarketDepthItem> items) {
        int cumulativeSize = 0;
        for (MarketDepthItem item : items) {
            cumulativeSize += item.getSize();
        }

        return cumulativeSize;
    }

    public synchronized void update(int position, MarketDepthOperation operation, MarketDepthSide side, double price, int size) {
        if (price < 0) {
            // IB API sometimes sends "-1" as the price when market depth is resetting.
            return;
        }

        List<MarketDepthItem> items = (side == MarketDepthSide.Bid) ? bids : asks;
        int levels = items.size();

        switch (operation) {
            case Insert:
                if (position <= levels) {
                    items.add(position, new MarketDepthItem(size, price));
                }
                break;
            case Update:
                if (position < levels) {
                    MarketDepthItem item = items.get(position);
                    item.setSize(size);
                    item.setPrice(price);
                }
                break;
            case Delete:
                if (position < levels) {
                    items.remove(position);
                }
                break;
        }


        if (operation == MarketDepthOperation.Update) {
            if (!bids.isEmpty() && !asks.isEmpty()) {
                cumulativeBid = getCumulativeSize(bids);
                cumulativeAsk = getCumulativeSize(asks);

                double totalDepth = cumulativeBid + cumulativeAsk;
                if (totalDepth != 0) {
                    double balance = 100.0d * (cumulativeBid - cumulativeAsk) / totalDepth;
                    balances.add(balance);
                    midPointPrice = (bids.getFirst().getPrice() + asks.getFirst().getPrice()) / 2;
                }
            }
        }
    }

    public synchronized void update(int volume) {
        this.volume = volume;
    }

    public synchronized MarketSnapshot takeMarketSnapshot(long time) {
        if (balances.isEmpty()) {
            return null;
        }

        int oneSecondVolume = (previousVolume == 0) ? 0 : Math.max(0, volume - previousVolume);
        previousVolume = volume;

        double multiplier = 2.0 / (balances.size() + 1.0);
        for (double balance : balances) {
            averageBalance += (balance - averageBalance) * multiplier;
        }

        double oneSecondBalance = Double.valueOf(df2.format(averageBalance));
        MarketSnapshot marketSnapshot = new MarketSnapshot(time, oneSecondBalance, midPointPrice, oneSecondVolume);
        // retain the last balance, clear the rest
        while (balances.size() > 1) {
            balances.removeFirst();
        }

        return marketSnapshot;
    }
}