How fast is your limit order book implementation?

Quote from 2rosy:

is the map orderid->position in queue so you can handle order cancels in o(1)
More...

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

Yeah it's hard to compare then, as I need to make a few assumptions as to where and how cancels, mods affect the queue and how I represent the data. I suppose with ITCH you will know exactly as it provides the order IDs.
More...

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).
 
Quote from 2rosy:

is the map orderid->position in queue so you can handle order cancels in o(1)
More...

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.
 
Quote from hft_boy:

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).
More...

Thanks for the tip. I was not aware of this.
 
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;
    }
}
 
You must log in or register to reply here.
Back
Top