How fast is your limit order book implementation?

Discussion in 'Programming' started by hft_boy, Dec 20, 2012.

  1. hft_boy

    hft_boy

    I think the idea is to use orderid -> order object which maintains node pointers to maintain the linked list with.
     
    #11     Dec 23, 2012
  2. hft_boy

    hft_boy

    Python eh?
     
    #12     Dec 23, 2012
  3. hft_boy

    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).
     
    #13     Dec 23, 2012
  4. 2rosy

    2rosy

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

    Actually, I think a lot of this game is about knowing what you can throw away.
     
    #15     Dec 23, 2012
  6. hoppla

    hoppla

    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.
     
    #16     Dec 23, 2012
  7. Thanks for the tip. I was not aware of this.
     
    #17     Dec 24, 2012
  8. hft_boy

    hft_boy

    #18     Dec 24, 2012
  9. Moves the bottleneck, & costs money.
     
    #19     Dec 24, 2012
  10. 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;
        }
    }
    
     
    #20     Dec 24, 2012