rust order matching

Cargo.toml

[package]
name = "order-matching"
version = "0.1.0"
authors = ["a.korchevsky <a.korchevsky@corp.mail.ru>"]

[dependencies]

[profile.dev]
opt-level = 0      # controls the `--opt-level` the compiler builds with.
                   # 0-1 is good for debugging. 2 is well-optimized. Max is 3.
                   # 's' attempts to reduce size, 'z' reduces size even more.
debug = true       # (u32 or bool) Include debug information (debug symbols).
                   # Equivalent to `-C debuginfo=2` compiler flag.
rpath = false      # controls whether compiler should set loader paths.
                   # If true, passes `-C rpath` flag to the compiler.
lto = false        # Link Time Optimization usually reduces size of binaries
                   # and static libraries. Increases compilation time.
                   # If true, passes `-C lto` flag to the compiler, and if a
                   # string is specified like 'thin' then `-C lto=thin` will
                   # be passed.
debug-assertions = true # controls whether debug assertions are enabled
                   # (e.g. debug_assert!() and arithmetic overflow checks)
codegen-units = 16 # if > 1 enables parallel code generation which improves
                   # compile times, but prevents some optimizations.
                   # Passes `-C codegen-units`.
panic = 'unwind'   # panic strategy (`-C panic=...`), can also be 'abort'
incremental = true # whether or not incremental compilation is enabled
overflow-checks = true # use overflow checks for integer arithmetic.
                   # Passes the `-C overflow-checks=...` flag to the compiler.

[profile.release]
opt-level = 3
debug = false
rpath = false
lto = false
debug-assertions = false
codegen-units = 16
panic = 'unwind'
incremental = false
overflow-checks = false

[profile.test]
opt-level = 0
debug = 2
rpath = false
lto = false
debug-assertions = true
codegen-units = 16
panic = 'unwind'
incremental = true
overflow-checks = true

[profile.bench]
opt-level = 3
debug = false
rpath = false
lto = false
debug-assertions = false
codegen-units = 16
panic = 'unwind'
incremental = false
overflow-checks = false

console

$ rustup run nightly cargo bench
warning: `panic` setting is ignored for `test` profile
warning: `panic` setting is ignored for `bench` profile
    Finished release [optimized] target(s) in 0.03s                                                                                                                     
     Running target/release/deps/order_matching-7e52160785d6d2fb

running 2 tests
test bench_book   ... bench:          47 ns/iter (+/- 6)
test bench_bucket ... bench:          11 ns/iter (+/- 1)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out

     Running target/release/deps/order_matching-212a89d839326b09

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

lib.rs

#![feature(test)]

extern crate test;

use test::Bencher;

pub mod orderbook;

use orderbook::Order;
use orderbook::OrderBucket;
use orderbook::OrderBook;
use orderbook::TradingPair;

#[bench]
fn bench_bucket(b: &mut Bencher) {
    let mut bucket = OrderBucket::new(1000);

    b.iter(|| {
        let order1 = Order::ask_limit(1, 1, 1, 1);
        let order2 = Order::ask_limit(2, 1, 1, 1);
        bucket.add(order1);
        bucket.add(order2);
        let collected = bucket.order_match(2);
        assert_eq!(collected, 2);
    });
}

#[bench]
fn bench_book(b: &mut Bencher) {
    let mut book = OrderBook::new(TradingPair::BTC_ETH);

    b.iter(|| {
        book.bid_limit(1, 1, 1);
        let order = book.ask_market(2, 1);
        assert_eq!(order.filled, 1);
    });
}

main.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::time::SystemTime;

pub mod orderbook;

use orderbook::Order;
use orderbook::OrderBucket;

fn main() {
    let mut bucket = OrderBucket::new(1000);

    let now = SystemTime::now();

    for _ in 0..10000000 {
        let order1 = Order::ask_limit(1, 1, 1, 1);
        let order2 = Order::bid_limit(1, 1, 1, 1);

        bucket.add(order1);
        bucket.add(order2);
        let collected = bucket.order_match(2);
        assert_eq!(collected, 2);
    }

    match now.elapsed() {
        Ok(elapsed) => {
            // it prints '2'
            println!("{}.{} sec", elapsed.as_secs(), elapsed.subsec_millis());
        }
        Err(e) => {
            // an error occurred!
            println!("Error: {:?}", e);
        }
    }
}

orderbook.rs

use std::collections::VecDeque;
use std::collections::BTreeMap;

pub enum Currency {
    BTC,
    ETH,
}

pub struct TradingPair {
    left: Currency,
    right: Currency,
}

impl TradingPair {
    pub const BTC_ETH: TradingPair = TradingPair {
        left: Currency::BTC,
        right: Currency::ETH,
    };
}

pub enum OrderType {
    LIMIT,
    MARKET,
}

pub enum OrderAction {
    BID,
    ASK,
}

pub struct Order {
    pub id: u64,
    pub user: u64,
    pub order_type: OrderType,
    pub order_action: OrderAction,
    pub amount: u64,
    pub price: u64,
    pub filled: u64,
}

impl Order {
    pub fn ask_market(id: u64, user: u64, amount: u64) -> Order {
        Order {
            id,
            user,
            order_type: OrderType::MARKET,
            order_action: OrderAction::ASK,
            amount,
            price: 0,
            filled: 0,
        }
    }
    pub fn bid_market(id: u64, user: u64, amount: u64) -> Order {
        Order {
            id,
            user,
            order_type: OrderType::MARKET,
            order_action: OrderAction::BID,
            amount,
            price: 0,
            filled: 0,
        }
    }
    pub fn ask_limit(id: u64, user: u64, amount: u64, price: u64) -> Order {
        Order {
            id,
            user,
            order_type: OrderType::LIMIT,
            order_action: OrderAction::ASK,
            amount,
            price,
            filled: 0,
        }
    }
    pub fn bid_limit(id: u64, user: u64, amount: u64, price: u64) -> Order {
        Order {
            id,
            user,
            order_type: OrderType::LIMIT,
            order_action: OrderAction::BID,
            amount,
            price,
            filled: 0,
        }
    }
}

pub struct OrderBucket {
    price: u64,
    total_volume: u64,
    queue: VecDeque<Order>,
}

impl OrderBucket {
    pub fn new(price: u64) -> OrderBucket {
        OrderBucket {
            price,
            total_volume: 0,
            queue: VecDeque::new(),
        }
    }

    pub fn add(&mut self, order: Order) {
        self.total_volume += order.amount - order.filled;
        self.queue.push_back(order);
    }

    pub fn order_match(&mut self, volume_collect: u64) -> u64 {
        let mut volume_to_collect: u64 = volume_collect;
        let mut total_matching_volume: u64 = 0;
        while !self.queue.is_empty() && volume_to_collect > 0 {
            let full: bool;
            {
                match self.queue.front_mut() {
                    Some(order) => {
                        let order_amount: u64 = order.amount - order.filled;
                        let amount: u64;
                        if order_amount < volume_to_collect {
                            amount = order_amount;
                        } else {
                            amount = volume_to_collect;
                        }
                        volume_to_collect -= amount;
                        order.filled += amount;
                        total_matching_volume += amount;
                        self.total_volume -= amount;
                        full = order.amount == order.filled;
                    }
                    None => {
                        full = false;
                    }
                }
            }
            if full {
                self.queue.pop_front();
            }
        }

        total_matching_volume
    }
}

pub struct OrderBook {
    pair: TradingPair,
    bid: BTreeMap<u64, OrderBucket>,
    ask: BTreeMap<u64, OrderBucket>,
    id: u64,
}

impl OrderBook {
    pub fn new(pair: TradingPair) -> OrderBook {
        OrderBook {
            pair,
            bid: BTreeMap::new(),
            ask: BTreeMap::new(),
            id: 0,
        }
    }

    pub fn bid_market(&mut self, user: u64, amount: u64) -> Order {
        self.id += 1;
        let mut order = Order::bid_market(self.id, user, amount);
        let volume_to_collect = order.amount - order.filled;
        let total: u64 = self.ask.values().fold(0, |acc, b| acc + b.total_volume);
        if total < volume_to_collect {
            order
        } else {
            let mut iter = self.ask.iter_mut().rev();
            while volume_to_collect > 0 {
                match iter.next() {
                    Some((_price, bucket)) => {
                        let matched = bucket.order_match(volume_to_collect);
                        order.filled += matched;
                    }
                    None => {
                        break;
                    }
                }
            }
            order
        }
    }

    pub fn ask_market(&mut self, user: u64, amount: u64) -> Order {
        self.id += 1;
        let mut order = Order::ask_market(self.id, user, amount);
        let volume_to_collect = order.amount - order.filled;
        let total: u64 = self.bid.values().fold(0, |acc, b| acc + b.total_volume);
        if total < volume_to_collect {
            order
        } else {
            let mut iter = self.bid.iter_mut();
            while volume_to_collect > 0 {
                match iter.next() {
                    Some((_price, bucket)) => {
                        let matched = bucket.order_match(volume_to_collect);
                        order.filled += matched;
                    }
                    None => {
                        break;
                    }
                }
            }
            order
        }
    }

    pub fn bid_limit(&mut self, user: u64, amount: u64, price: u64) {
        self.id += 1;
        let mut order = Order::bid_limit(self.id, user, amount, price);
        let volume_to_collect = order.amount - order.filled;
        let mut iter = self.ask.iter_mut();
        while volume_to_collect > 0 {
            match iter.next() {
                Some((_price, bucket)) => {
                    let matched = bucket.order_match(volume_to_collect);
                    order.filled += matched;
                }
                None => {
                    break;
                }
            }
        }
        if order.filled < order.amount {
            let bucket = self.bid.entry(price).or_insert_with(|| OrderBucket::new(price));
            bucket.add(order);
        }
    }
}