Fast OrderBook Implementation - Follow Up

Question

Following up from: Fast OrderBook Implementation

Here is the updated version (I've also implemented some extra functionality)

==> Order.hpp <==

struct Order {
    int id;
    int quantity; // hiddenQuantity needs to be >= peakSize
    int peakSize;
    int hiddenQuantity;
    short price; // we don't really need this, cause price is the index

    Order(int id = 0, int quantity = 0, int peakSize = 0, int hiddenQuantity = 0, short price = 0) :
        id(id),
        quantity(quantity),
        peakSize(peakSize),
        hiddenQuantity(hiddenQuantity),
        price(price) { }
};

==> OrderBook.cpp <==

#include "OrderBook.hpp"

template<Side side>
inline bool OrderBook::compare(const int &top, const int &bottom) {
    if constexpr (side == Side::Bid)
        return top >= bottom;
    else
        return top <= bottom;
}

template<Side side>
inline void OrderBook::findNextPrice() {
    Book &bookSide{books[side]};

    while (compare<side>(bookSide.top, bookSide.bottom) and bookSide.orders[bookSide.top].empty())
        if constexpr (side == Side::Bid)
            --bookSide.top;
        else
            ++bookSide.top;

    if (not compare<side>(bookSide.top, bookSide.bottom))
        bookSide.makeDefault();
}

inline void OrderBook::replenishIcebergOrder(Order &order) {
    if (order.quantity == 0 and order.hiddenQuantity > 0) {
        order.quantity = std::min(order.peakSize, order.hiddenQuantity);
        order.hiddenQuantity -= order.quantity;
    }
}


template<Side side>
void OrderBook::processOrder(Order &order) {
    constexpr Side otherSide = (side == Side::Bid) ? Side::Ask : Side::Bid;
    matchOrders<side, otherSide>(order);
    displayOrderBook();
}

template<Side side, Side otherSide>
void OrderBook::matchOrders(Order &order) {

    auto &otherBook{books[otherSide]};

    while (compare<otherSide>(otherBook.top, order.price) and order.quantity > 0) {
        auto &other = otherBook.orders[otherBook.top].front();

        if constexpr (side == Side::Bid)
            std::cout << order.id << ',' << other.id;
        else
            std::cout << other.id << ',' << order.id;

        std::cout << ',' << otherBook.top << ',' << std::min(other.quantity, order.quantity) << '\n';

        int change = other.quantity - order.quantity;
        other.quantity = std::max(0, change);
        order.quantity = std::max(0, -change);

        replenishIcebergOrder(other);
        replenishIcebergOrder(order);

        if (other.quantity == 0) {
            otherBook.orders[otherBook.top].pop_front();
            if (otherBook.orders[otherBook.top].empty())
                findNextPrice<otherSide>();
        }
    }

    if (order.quantity > 0)
        addOrder<side>(order);
}

template<Side side>
void OrderBook::addOrder(Order &order) {
    Book &bookSide{books[side]};

    if constexpr (side == Side::Bid) {
        bookSide.top = std::max(bookSide.top, static_cast<int>(order.price));
        bookSide.bottom = std::min(bookSide.bottom, static_cast<int>(order.price));
    } else {
        bookSide.top = std::min(bookSide.top, static_cast<int>(order.price));
        bookSide.bottom = std::max(bookSide.bottom, static_cast<int>(order.price));
    }

    bookSide.orders[order.price].push_back(std::move(order));
}

// TODO: is there a better way to do this?
void OrderBook::displayOrderBook() {
    std::cout << "+-----------------------------------------------------------------+\n";
    std::cout << "| BUY                            | SELL                           |\n";
    std::cout << "| Id       | Volume      | Price | Price | Volume      | Id       |\n";
    std::cout << "+----------+-------------+-------+-------+-------------+----------+\n";

    std::vector<std::pair<Order, Order>> orders;
    unsigned long int bidIndex{0}, askIndex{0};

    for (int i = books[Side::Bid].top; i >= books[Side::Bid].bottom; --i) {
        for (auto &order: books[Side::Bid].orders[i]) {
            if (bidIndex >= orders.size()) {
                orders.push_back({order, Order{}});
                ++bidIndex;
            } else {
                orders[bidIndex++].first = order;
            }
        }
    }

    for (int i = books[Side::Ask].top; i <= books[Side::Ask].bottom; ++i) {
        for (auto &order: books[Side::Ask].orders[i]) {
            if (askIndex >= orders.size()) {
                orders.push_back({Order{}, order});
                ++askIndex;
            } else {
                orders[askIndex++].second = order;
            }
        }
    }

    auto displayField = [](const int &value) {
        return value == 0 ?  "" : std::to_string(value);
    };

    for (const auto &[bidOrder, askOrder]: orders) {
        std::cout << '|' << std::setw(10) << displayField(bidOrder.id) << '|'
            << std::setw(13) << formatWithCommas(bidOrder.quantity) << '|'
            << std::setw(7) << formatWithCommas(bidOrder.price) << '|'
            << std::setw(7) << formatWithCommas(askOrder.price) << '|'
            << std::setw(13) << formatWithCommas(askOrder.quantity) << '|'
            << std::setw(10) << displayField(askOrder.id) << "|\n";
    }

    std::cout << "+-----------------------------------------------------------------+\n";
}

std::string OrderBook::formatWithCommas(const int &value) {
    if (value == 0)
        return "";

    std::string numberString = std::to_string(value);
    for (int i = numberString.size() - 3; i > 0; i -= 3)
        numberString.insert(i, ",");

    return numberString;
}

==> OrderBook.hpp <==

#include <array>
#include <vector>
#include <deque>
#include <iostream>
#include <iomanip>

#include "Order.hpp"

#define BOOK_TOP 32768 // one level above SHRT_MAX
#define BOOK_BOTTOM -1 // one level blow bottom of book
#define BOOK_SIZE 32767 // SHRT_MAX

enum Side { Bid = 0, Ask = 1 };

struct Book {
    /*
    could use a ring buffer/circular queue instead of a deque
    if you know the max possible level depth/width of the orderbook,
    to avoid expensive allocations and deallocations,
    but I decided to keep things simple.
    I chose deque over a doubly linked since it's semi contiguous
    */

    std::vector<std::deque<Order>> orders;

    int top;
    int bottom;
    int defaultTop;
    int defaultBottom;

    Book (long unsigned int size, int top, int bottom) : 
        orders{size},
        top{top},
        bottom{bottom},
        defaultTop(top),
        defaultBottom(bottom) { }

    void makeDefault() {
        top = defaultTop;
        bottom = defaultBottom;
    }
};


class OrderBook {
    
public:

    OrderBook() : 
        books{{Book{BOOK_SIZE, BOOK_BOTTOM, BOOK_TOP}, 
                Book{BOOK_SIZE, BOOK_TOP, BOOK_BOTTOM}}} { }

    ~OrderBook() = default;

    template<Side side>
    inline bool compare(const int &top, const int &bottom);

    template<Side side>
    inline void findNextPrice();

    inline void replenishIcebergOrder(Order &order);

    template<Side side>
    void processOrder(Order &order);

    template<Side side, Side otherSide>
    void matchOrders(Order &order);

    template<Side side>
    void addOrder(Order &order);

    void displayOrderBook();

    std::string formatWithCommas(const int &value);

private:
    std::array<Book, 2> books; // bids, asks
};

==> main.cpp <==

#include "OrderBook.cpp"

int main() {
    OrderBook orderbook;

    std::string line;
    while (std::getline(std::cin, line)) {
        if (line.empty() or line[0] == '#' or line[0] == ' ')
            continue;

        std::istringstream iss{line};
        std::string item;
        std::vector<std::string> items;

        while (getline(iss, item, ','))
            items.push_back(item);

        char side{items[0][0]};
        int id{stoi(items[1])};
        short price{static_cast<short>(std::stoi(items[2]))};
        int quantity{std::stoi(items[3])};
        int peakSize{0};
        int hiddenQuantity{0};

        // error checking
        if ((side != 'B' and side != 'S') or id <= 0 or price <= 0 or quantity <= 0) {
            std::cerr << "Invalid input: " << line << '\n';
            continue;
        }

        // IceBerg order
        if (items.size() == 5) {
            peakSize = stoi(items[4]);
            if (peakSize <= 0 or peakSize > quantity) {
                std::cerr << "Invalid input: " << line << '\n';
                continue;
            }
            hiddenQuantity = quantity - peakSize;
            quantity = peakSize;
        }
        
        Order order{id, quantity, peakSize, hiddenQuantity, price};

        if (side == 'B')
            orderbook.processOrder<Side::Bid>(order);
        else
            orderbook.processOrder<Side::Ask>(order);
    }

    return 0;
}

Here is an example test

B,100321,5103,7500
B,100322,5101,7500
B,100323,5103,7500
S,100324,5103,7500
S,100345,5103,100000,10000
  

   # this is a test
# this is another test

# this is going to be invalid
S,1,5103,100,10000

B,2,5103,100
B,3,5103,1000,90
S,4,5103,100,100
S,5,5104,100,100
S,6,5103,100,100


B,7,5105,300,300
S,8,5105,300,100

B,1234567890,32503,1234567890
S,1234567890,32505,1234567890

which ofc can be tested by doing something like cat test | ./order_book

Answer 1

There's still a hole in struct Order

You moved short price to the end of the struct, but since you also have int member variables, the size of the struct will very likely be rounded to a multiple of sizeof(int). You will probably have a short-sized hole at the end, which isn't as efficient as making price an int.

Missing error checking

In main() you are reading input from std::cin, but while there is some attempt at validating the input, errors are mostly just ignored. Let's go over the possible errors:

• There might be an error reading a line from std::cin. Your while-loop will end if that happens, but it treats it the same as if it successfully reached the end of the file. You should check the return value of std::cin.eof() after the while-loop; if it's not true, then something bad happened before reaching the end of the file.
• There might be a problem parsing each line. Splitting the line on commas seems fine. However, std::stoi() can sometimes return values even though the string you give it is not purely a number. For example: "1two3" will be parsed as 1. To be more correct, you can use the second parameter of std::stoi() to check where it stopped parsing the number; if it's not a NUL-byte, there was some stuff after the number it could not parse.
• Similarly, items[0] might be longer than one character, and maybe items.size() > 5?
• Even printing to std::cout can fail, consider for example someone closing the terminal your program is running in, or if you redirect the output to a file, and the disk is full.

Ideally, you check for all these errors, and if you encounter an error that you cannot deal with properly, then you should print an error message to std::cerr and terminate the program with the EXIT_FAILURE exit code.

Just ignoring a line of input you cannot parse is not properly dealing with the issue. It might have been a valid order that was corrupted somehow, or the input might not be a list of orders at all. Ignoring it will result in incorrect or unexpected output.

Move enum Side into a struct, class or namespace

Because enum Side is no longer an enum class, and you declared it in the global namespace, the names Bid and Ask are also in the global namespace without needing the Side:: prefix. It's always better to limit the scope of things. You can move enum Side into struct OrderBook. Then in main() you need to write:

if (side == 'B')
    orderbook.processOrder<OrderBook::Bid>(order);
else
    orderbook.processOrder<OrderBook::Ask>(order);

Answer 2

General Observations

The code is still missing the #include <sstream> directive in main.cpp and does not compile for me without it. The file OrderBook.cpp is missing the #include <string> directive and does not compile without it.

To be honest, I don't see a lot of improvement from the original question.

I still think that the enum Side should be a parameter to functions where it is necessary and the templates don't make a lot of sense to me.

I still think that Side is not an appropriate name for the enum.

Include Guards

The header files Order.hpp and OrderBook.hpp do no contain any form of include guards, this leads to multiply defined objects in the code and causes linking errors. By adding include guards to the 2 header files I was able to compile and link without problems.

There are 2 forms of include guards you can use in C++, the older style

#ifndef ORDER_HPP_
#define ORDER_HPP_

struct Order {
    int id;
    int quantity; // hiddenQuantity needs to be >= peakSize
    int peakSize;
    int hiddenQuantity;
    short price; // we don't really need this, cause price is the index

    Order(int id = 0, int quantity = 0, int peakSize = 0, int hiddenQuantity = 0, short price = 0) :
        id(id),
        quantity(quantity),
        peakSize(peakSize),
        hiddenQuantity(hiddenQuantity),
        price(price) { }
};

#endif // !ORDER_HPP_

Or the newer #pragma once which is not portable to all compilers.

C++ Header Files

There are libraries that provide header.hpp files, but the convention is to use header.h rather than header.hpp.

Constants in C++

There are 3 symbolic constants defined in OrderBook.hpp. These 3 symbolic constants are using the older C programming language method of using macros to define constants. In C++ we prefer to use constexpr or const assignments because they are type safe where the macros are not type safe.

The existing code is

#define BOOK_TOP 32768 // one level above SHRT_MAX
#define BOOK_BOTTOM -1 // one level blow bottom of book
#define BOOK_SIZE 32767 // SHRT_MAX

The suggested code is

constexpr int BOOK_TOP = 32768;     // one level above SHRT_MAX
constexpr int BOOK_BOTTOM = -1;     // one level blow bottom of book
constexpr int BOOK_SIZE =  32767;   // SHRT_MAX

This code should be moved into OrderBook.cpp. The constructor for OrderBook should also be moved into OrderBook.cpp.

Use of the inline Keyword in Declarations

I mentioned this in the review for the previous version of this question, the keyword inline is only a suggestion to the compiler there is no guarantee that the compiler will inline these functions. For better optimization use the compiler optimization switches.