This is a follow up to my previous implementation:
The input is of the format
ACTION [OID [SYMBOL SIDE QTY PX]]
ACTION: single character value with the following definitions
O - place order, requires OID, SYMBOL, SIDE, QTY, PX
X - cancel order, requires OID
P - print sorted book (see example below)
where
OID: positive 32-bit integer value which must be unique for all orders
SYMBOL: alpha-numeric string value. Maximum length of 8.
SIDE: single character value buy or sell
QTY: positive 16-bit integer value
PX: positive double precision value (7.5 format)
and the output is as given in the sample output.
I would like further suggestions on this code, specifically if there can be made further optimizations on the broad design, as well as any speed ups. Also, given that the maximum length of the symbol is 8 (hard limit), can further optimizations be made on the nature of the struct ?
As an aside, is this how actual OrderBook implementations in HFT exchanges would occur ?
'orderbook.h':
#include <fstream>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>
typedef std::vector<std::string> vector_str;
using orderid_t = uint32_t;
using qty_t = uint16_t;
using price_t = unsigned long long;
using symbol_t = std::string;
constexpr char string_delim = ' ';
constexpr int money_decimal_digits = 6;
constexpr long long money_scale = 100000;
namespace
{
std::vector<std::string> split(std::string_view strv)
{
std::vector<std::string> result;
size_t start = 0;
while (start < strv.size())
{
size_t end = strv.find(string_delim, start);
if (end == std::string_view::npos)
{
end = strv.size();
}
result.emplace_back(strv.substr(start, end - start));
start = end + 1;
}
return result;
}
}
enum class side_t : bool
{
BUY,
SELL
};
std::string format_7_5(price_t number)
{
std::ostringstream out;
out << number / money_scale
<< '.'
<< std::setw(money_decimal_digits) << std::setfill('0')
<< number % money_scale;
return out.str();
}
struct Node
{
orderid_t oid;
qty_t qty;
price_t price;
symbol_t symbol;
side_t side;
std::list<Node>::iterator list_itr = {};
};
class OrderBook
{
// mapping from order id to order
std::map<orderid_t, Node *> &orders_map_;
public:
std::map<price_t, std::list<Node>> Booklevel_sell_ = {};
std::map<price_t, std::list<Node>> Booklevel_buy_ = {};
OrderBook(std::map<orderid_t, Node *> &orders_map) : orders_map_(orders_map)
{
}
private:
// Utility function to process book levels
void processBookLevel(bool is_buy, const std::map<price_t, std::list<Node>> &bookLevel, vector_str &results)
{
// Iterating over bookLevel in reverse order
for (auto level_itr = bookLevel.rbegin(); level_itr != bookLevel.rend(); ++level_itr)
{
const auto &curr_list = level_itr->second;
if (is_buy)
{
// Process curr_list in normal order for buy orders
for (const auto &item : curr_list)
{
results.emplace_back("P " + std::to_string(item.oid) + " " +
format_7_5(item.price) + " " +
std::to_string(item.qty));
}
}
else
{
// Process curr_list in reverse order for sell orders
for (auto item_ritr = curr_list.rbegin(); item_ritr != curr_list.rend(); ++item_ritr)
{
const auto &item = *item_ritr;
results.emplace_back("P " + std::to_string(item.oid) + " " +
format_7_5(item.price) + " " +
std::to_string(item.qty));
}
}
}
}
public:
void print(vector_str &results)
{
processBookLevel(false, Booklevel_sell_, results);
processBookLevel(true, Booklevel_buy_, results);
}
vector_str insert_order(orderid_t oid, const symbol_t &symbol, side_t side, qty_t qty, price_t price)
{
// Check for duplicate orders by order ID.
// If an order with the same ID already exists in our orders_map, return an error message.
if (auto itr = orders_map_.find(oid); itr != orders_map_.end())
{
return vector_str{"E " + std::to_string(oid) + " Duplicate order id"};
}
vector_str final_lst{};
// Lambda to push completed trade info (Fills) into a list for reporting.
auto pushToFinalList = [&final_lst](orderid_t oid, const symbol_t &symbol, qty_t qty, price_t price)
{
final_lst.push_back("F " + std::to_string(oid) + " " + symbol + " " + std::to_string(qty) + " " + format_7_5(price));
};
auto qty_to_fill = qty; // Quantity of the order to be filled.
// Lambda for handling the trade process.
// It iterates through the order book, executes trades based on price conditions,
// and modifies the order quantities or removes filled orders.
auto handleTrade = [&](auto begin, auto end, auto priceCondition, auto eraser)
{
for (auto itr = begin; itr != end && priceCondition(itr->first) && qty_to_fill > 0;)
{
auto &curr_list = itr->second;
// Iterate through each order in the current price level list.
for (auto list_itr = curr_list.begin(); list_itr != curr_list.end() && qty_to_fill > 0;)
{
// Calculate the quantity to trade, which is the minimum of qty_to_fill and the current order's quantity.
auto qty_to_trade = std::min(qty_to_fill, list_itr->qty);
// Record the trade details for both participating orders.
pushToFinalList(oid, symbol, qty_to_trade, price); // The newly inserted order.
pushToFinalList(list_itr->oid, list_itr->symbol, qty_to_trade, list_itr->price); // The matched order.
qty_to_fill -= qty_to_trade; // Decrease the remaining quantity to fill.
// If the current order is fully filled, remove it and update iterator; otherwise, decrease its quantity.
if (list_itr->qty <= qty_to_trade)
{
orders_map_.erase(list_itr->oid); // Remove the order from the global map.
list_itr = curr_list.erase(list_itr); // Remove the order from the current price level.
}
else
{
list_itr->qty -= qty_to_trade; // Deduct the traded quantity.
++list_itr; // Move to the next order in the list.
}
}
// If the current list (price level) is empty after trades, remove it from the book.
if (curr_list.empty())
{
itr = eraser(itr);
}
else
{
// Implies that the current price level is not empty after qty_to_fill is exhausted.
break;
}
}
};
// Process trades for BUY orders against SELL book and vice versa.
// Utilizes the handleTrade lambda with specific iterators and conditions based on the order side.
if (side == side_t::BUY)
{
handleTrade(
Booklevel_sell_.begin(), Booklevel_sell_.end(),
[price](auto p)
{ return p <= price; }, // Matching condition for BUY: sell price should be <= buy order price.
[&](auto itr)
{ return Booklevel_sell_.erase(itr); }); // Eraser for direct iterator (forward list).
}
else
{
handleTrade(
Booklevel_buy_.rbegin(), Booklevel_buy_.rend(),
[price](auto p)
{ return p >= price; }, // Matching condition for SELL: buy price should be >= sell order price.
[&](auto itr) -> decltype(Booklevel_buy_.rbegin())
{
// Eraser for reverse iterator, requires conversion for erase and then to reverse iterator again.
return std::make_reverse_iterator(Booklevel_buy_.erase(std::next(itr).base()));
});
}
// If there's any quantity left unfilled after attempting to match, add the remaining part of the order to the book.
if (qty_to_fill > 0)
{
// Select the appropriate book (buy or sell) based on the order side.
std::map<price_t, std::list<Node>> &bookLevel = (side == side_t::BUY) ? Booklevel_buy_ : Booklevel_sell_;
// Add the unfilled order to the book.
bookLevel[price].push_back(Node{oid, qty_to_fill, price, symbol, side});
// Keep a direct reference to the order in the global orders map for quick access.
orders_map_[oid] = &*(bookLevel[price].rbegin());
orders_map_[oid]->list_itr = --(bookLevel[price].end());
}
return final_lst; // Return the list of filled trades.
}
};
class UnifiedOrderBook
{
std::unordered_map<std::string, OrderBook> ob_;
std::map<orderid_t, Node *> orders_map_;
public:
vector_str print()
{
auto ans = vector_str();
for (auto it = ob_.begin(); it != ob_.end(); ++it)
{
it->second.print(ans);
}
return ans;
}
bool cancel_order(orderid_t oid)
{
auto itr = orders_map_.find(oid);
if (itr == orders_map_.end())
{
return false;
}
auto &curr_node = itr->second;
auto &ob = ob_.find(curr_node->symbol)->second;
auto &bookLevel = curr_node->side == side_t::BUY ? ob.Booklevel_buy_ : ob.Booklevel_sell_;
// Directly accessing the price level.
auto &priceLevel = bookLevel[curr_node->price];
// Erase the order from the list.
priceLevel.erase(curr_node->list_itr);
// If the price level becomes empty after erasure, remove it from the bookLevel.
if (priceLevel.empty())
{
bookLevel.erase(curr_node->price);
}
orders_map_.erase(itr);
return true;
}
vector_str insert_order(orderid_t oid, const symbol_t &symbol, side_t side, qty_t qty, price_t price)
{
auto book_itr = ob_.find(symbol);
if (book_itr == ob_.end())
{
auto insert_result = ob_.emplace(std::make_pair(symbol, OrderBook(orders_map_)));
book_itr = insert_result.first;
}
return book_itr->second.insert_order(oid, symbol, side, qty, price);
}
};
class SimpleCross
{
public:
vector_str process(const std::string &line)
{
auto tokens_vec = split(line);
switch (tokens_vec[0][0])
{
case 'P':
{
return uob_.print();
}
case 'X':
{
return uob_.cancel_order(static_cast<orderid_t>(std::stoul(tokens_vec[1]))) ? vector_str{line} : vector_str{"E OrderID not found"};
}
case 'O':
{
double price;
orderid_t order_id;
qty_t qty;
side_t side;
try
{
order_id = static_cast<orderid_t>(std::stoul(tokens_vec[1]));
}
catch (...)
{
return vector_str{"E Invalid order id"};
}
try
{
qty = static_cast<qty_t>(std::stoul(tokens_vec[4]));
}
catch (...)
{
return vector_str{"E Invalid quantity"};
}
try
{
price = std::stod(tokens_vec[5]);
}
catch (...)
{
return vector_str{"E Invalid price"};
}
if (tokens_vec[3] == "B")
{
side = side_t::BUY;
}
else if (tokens_vec[3] == "S")
{
side = side_t::SELL;
}
else
{
return vector_str{"E Invalid side provided"};
}
return uob_.insert_order(order_id, tokens_vec[2], side, qty, static_cast<price_t>(price * 1e5));
}
default:
return vector_str{"E invalid arguments provided"};
}
return vector_str{"E invalid arguments provided"};
}
vector_str action(const std::string &line)
{
return process(line);
}
private:
UnifiedOrderBook uob_;
};
void driver(const std::string &inputFilename, const std::string &outputFilename = "")
{
SimpleCross scross;
std::string line;
std::ifstream actions(inputFilename, std::ios::in);
std::ofstream outFile;
bool useFileOutput = !outputFilename.empty();
if (useFileOutput)
{
outFile.open(outputFilename, std::ios::out);
}
while (std::getline(actions, line))
{
vector_str results = scross.action(line);
for (vector_str::const_iterator it = results.begin(); it != results.end(); ++it)
{
if (useFileOutput)
{
outFile << *it << std::endl;
}
else
{
std::cout << *it << std::endl;
}
}
}
}
Main CPP program
#include "orderbook.h"
int main(int argc, char **argv)
{
std::string filename = "actions.txt";
if (argc > 1)
{
filename = argv[1];
}
driver(filename);
return 0;
}
Sample Input
O 10000 AAPL B 10 100.0
O 10001 AAPL B 10 99.0
O 10002 AAPL S 5 101.0
O 10003 AAPL S 5 100.0
O 10004 AAPL S 6 100.0
X 10002
O 10005 AAPL B 10 99.0
O 10006 AAPL B 10 100.0
O 10007 AAPL S 10 101.0
O 10008 AAPL S 10 102.0
O 10008 AAPL S 10 102.0
O 10009 AAPL S 10 102.0
P
O 10010 AAPL B 13 102.0
Sample Output
F 10003 AAPL 5 100.000000
F 10000 AAPL 5 100.000000
F 10004 AAPL 5 100.000000
F 10000 AAPL 5 100.000000
X 10002
F 10006 AAPL 1 100.000000
F 10004 AAPL 1 100.000000
E 10008 Duplicate order id
P 10009 102.000000 10
P 10008 102.000000 10
P 10007 101.000000 10
P 10006 100.000000 9
P 10001 99.000000 10
P 10005 99.000000 10
F 10010 AAPL 10 102.000000
F 10007 AAPL 10 101.000000
F 10010 AAPL 3 102.000000
F 10008 AAPL 3 102.000000
