2
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ By the way, are you targetting C++17 or C++20? It only makes sense to have one of those tags. \$\endgroup\$
    – G. Sliepen
    Jun 25, 2023 at 15:52
  • \$\begingroup\$ I'm targeting C++20, but for features available in GCC 12 \$\endgroup\$
    – jpf
    Jun 25, 2023 at 15:59

2 Answers 2

2
\$\begingroup\$

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);
\$\endgroup\$
6
  • \$\begingroup\$ Price has to be a short, sadly nothing I can do about that. I also didn't include much error checking because it's assumed that the input is valid. For the last point, is there a way to use a enum class like how I use it with just enum? I haven't been able to find a way. \$\endgroup\$
    – jpf
    Jun 25, 2023 at 21:58
  • 1
    \$\begingroup\$ Maybe the price has to be between SHRT_MIN and SHRT_MAX, but does it matter if you store the value in an int? If you assume the input is valid, why still have checks for side and peakSize? As for enum class, you can still use it, but you need to explicitly cast it to an integer: Book &bookSide{books[static_cast<int>(side)]}; This might be a bit annoying, but you can of course create a helper function for it. Alternatively, put enum Side in a namespace Side. \$\endgroup\$
    – G. Sliepen
    Jun 25, 2023 at 22:05
  • \$\begingroup\$ Yeah I wanted to store them as ints, but the spec specifically calls out for a short. if I were to put it in a namespace, wouldn't it also just be better to have have them as bools? \$\endgroup\$
    – jpf
    Jun 25, 2023 at 22:13
  • \$\begingroup\$ A bool would work, but then you could write orderbook.ProcessOrder<true>(order), which would compile without errors, but what does that mean? It's much better to prevent that and force a symbolic name to be used. \$\endgroup\$
    – G. Sliepen
    Jun 25, 2023 at 22:37
  • 1
    \$\begingroup\$ @jpf Never assume user input will be valid. I learned that a long time ago when I was writing compilers. \$\endgroup\$
    – pacmaninbw
    Jun 25, 2023 at 23:06
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Could you please elaborate on why templating like doesn't make a lot of sense? Is it a matter of style, or is there some reason why this is bad. \$\endgroup\$
    – jpf
    Jun 25, 2023 at 22:14
  • \$\begingroup\$ @jpf Not a matter of style. Templates are for generic algorithms, where the code does not depend on a specific type. They are not for replacing arguments/parameters. \$\endgroup\$
    – pacmaninbw
    Jun 25, 2023 at 23:11
  • \$\begingroup\$ The reason I'm doing it this way is so that I get something similar to template specialisation, is there a better way of doing this without if constexpr? \$\endgroup\$
    – jpf
    Jun 26, 2023 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.