itch_market.hpp

#pragma once
 
#include <array>
#include <cstddef>
#include <cstdint>
#include <expected>
#include <limits>
#include <memory>
#include <utility>
#include <vector>
 
#include <ankerl/unordered_dense.h>
 
#include <order_book/feed.hpp>
#include <order_book/itch.hpp>
#include <order_book/levels.hpp>
#include <order_book/order_book.hpp>
 
namespace order_book {

class ItchMarket {
public:
    [[nodiscard]] std::expected<bool, BookError> apply(const ItchMessage& message);
    [[nodiscard]] std::expected<bool, BookError> add(const ItchMessage& message);
    [[nodiscard]] std::expected<bool, BookError> execute(const ItchMessage& message);
    [[nodiscard]] std::expected<bool, BookError> remove(const ItchMessage& message);
    [[nodiscard]] std::expected<bool, BookError> replace(const ItchMessage& message);
    static constexpr std::size_t prefetch_distance = 16;
#if defined(__linux__) && defined(__x86_64__)
    static constexpr bool prefetch_levels_enabled = false;
#else
    static constexpr bool prefetch_levels_enabled = true;
#endif
    void prefetch(std::uint64_t order, std::uint16_t locate) const;
    void prefetch_levels(std::uint64_t order, std::uint16_t locate) const;
    [[nodiscard]] Bbo bbo(std::uint16_t locate) const;
    [[nodiscard]] std::size_t order_count() const { return m_order_count; }
    [[nodiscard]] std::size_t level_count() const { return m_levels.size(); }
 
private:
    // A resting order in 8 bytes, as ITCH gives shares in 32 bits; level 0 marks an entry of the
    // index that holds none
    struct Order {
        Shares remaining;
        std::uint32_t level;
    };
    // Reference numbers below this live in the index, and larger ones in m_overflow. Nasdaq starts
    // them low each day: the largest on 2019-12-30 is 308,631,072. The bound keeps m_chunks within
    // 2^16 entries, so a larger reference number's chunk is past its end and lookups need no check.
    static constexpr std::uint64_t paged_orders = std::uint64_t{1} << 32U;
    // Small pages, because each worker keeps only the locates assigned to it, so its orders are a
    // sparse subset of every range of reference numbers, and long-lived orders keep pages alive. On
    // the 2019-12-30 day, 128 reference numbers a page gave the lowest peak with ten workers:
    // smaller pages need more of the directory, which every worker keeps for every range it uses.
    static constexpr unsigned page_bits = 7;
    static constexpr std::size_t page_size = std::size_t{1} << page_bits;
    // The orders of page_size consecutive reference numbers, exactly 1 KiB: with its live count
    // beside the orders, the allocator would round a page up by a quarter
    using Page = std::array<Order, page_size>;
    // The pages of chunk_size consecutive page numbers, and how many live orders each holds. The
    // index makes a chunk only for a page it uses, so a high reference number costs one chunk
    // rather than a slot for every page below it.
    static constexpr unsigned chunk_bits = 9;
    static constexpr std::size_t chunk_size = std::size_t{1} << chunk_bits;
    struct Chunk {
        std::array<std::unique_ptr<Page>, chunk_size> pages;
        std::array<std::uint8_t, chunk_size> live{};
    };
    static_assert(page_size <= std::numeric_limits<std::uint8_t>::max());
 
    // Take `quantity` off `resting`, the order `order`, removing it and then its level once they
    // reach 0; returns whether its book's best bid or offer changed. Removing an order of
    // m_overflow invalidates `resting`.
    bool reduce(std::uint64_t order, Order& resting, Shares quantity);
    // The live order `order` of `locate`, or nullptr
    [[nodiscard]] Order* find(std::uint64_t order, std::uint16_t locate);
    // The index entry of `order`, live or not, or nullptr if its page does not exist
    [[nodiscard]] const Order* indexed(std::uint64_t order) const;
    // The chunk of `order`, which exists
    [[nodiscard]] Chunk& chunk(std::uint64_t order);
    // Where the page of `order` is in its chunk
    [[nodiscard]] static std::size_t page_slot(std::uint64_t order)
    {
        return (order >> page_bits) & (chunk_size - 1);
    }
    // The levels of `locate`'s book, made if it has none yet
    [[nodiscard]] BookLevels& book(std::uint16_t locate);
 
    std::vector<BookLevels> m_books;
    LevelPool m_levels;
    // Chunks by the reference numbers' bits above both a page's and a chunk's; never freed
    std::vector<std::unique_ptr<Chunk>> m_chunks;
    // Emptied pages, kept for reuse
    std::vector<std::unique_ptr<Page>> m_spare_pages;
    // Orders the index does not hold, by reference number and locate: those whose slot holds a live
    // order of another locate, and those from paged_orders up. Empty for a Nasdaq feed, whose
    // reference numbers are unique for the day and start low.
    ankerl::unordered_dense::map<std::pair<std::uint64_t, std::uint16_t>, Order> m_overflow;
    std::size_t m_order_count = 0;
};
 
} // namespace order_book