Order Book Updating (Kraken)

order_engine.go

package orderengine

import (
	"sort"
)

// Book represents an order book
type Book []*Order

// Order is a single order to be placed
type Order struct {
	Price, Volume float64
}

// NewBook returns a new order book (Book)
func NewBook(maxDepth uint) Book {
	return make(Book, 0, maxDepth+1)
}

func (b *Book) removeOrder(order *Order, index int) {
	length := len(*b)
	if index < length-1 {
		copy((*b)[index:], (*b)[index+1:])
	}
	(*b)[length-1] = nil
	*b = (*b)[:length-1]
}

func (b *Book) insertOrder(order *Order, index int) {
	*b = append(*b, nil)
	copy((*b)[index+1:], (*b)[index:])
	(*b)[index] = order
	if length := len(*b); length == cap(*b) {
		*b = (*b)[:length-1]
	}
}

func (b *Book) replaceOrder(order *Order, index int) {
	(*b)[index] = order
}

// Update adds the orders supplied to the order book
func (b *Book) Update(orders ...*Order) {
	for _, order := range orders {
		length := len(*b)
		index := sort.Search(length, func(i int) bool {
			return order.Price <= (*b)[i].Price
		})
		if index >= length {
			continue
		} else if order.Volume == 0 {
			b.removeOrder(order, index)
		} else if order.Price == (*b)[index].Price {
			b.replaceOrder(order, index)
		} else {
			b.insertOrder(order, index)
		}
	}
}

order_engine_test.go

package orderengine

import (
	"testing"
)

func _newBook() *Book {
	book := append(NewBook(10),
		&Order{Price: 5706.30000, Volume: 1.00000000},
		&Order{Price: 5706.40000, Volume: 0.85600000},
		&Order{Price: 5706.90000, Volume: 1.17300000},
		&Order{Price: 5707.00000, Volume: 0.00200000},
		&Order{Price: 5707.40000, Volume: 4.33000000},
		&Order{Price: 5707.80000, Volume: 2.50000000},
		&Order{Price: 5708.20000, Volume: 5.00000000},
		&Order{Price: 5708.30000, Volume: 0.75483907},
		&Order{Price: 5709.20000, Volume: 3.30000000},
		&Order{Price: 5711.70000, Volume: 0.00749800})
	return &book
}

func TestInsertOrder(t *testing.T) {
	book := _newBook()
	index := 3
	startLen, startCap := len(*book), cap(*book)

	newOrder := &Order{Price: 5712.85, Volume: 1.0}
	book.insertOrder(newOrder, index)
	if (*book)[index] != newOrder {
		t.Fatal("incorrect index for inserted order")
	}
	if len(*book) != startLen {
		t.Fatalf("length of book changed (%d != %d)", len(*book), startLen)
	}
	if cap(*book) != startCap {
		t.Fatalf("capacity of book changed (%d != %d)", cap(*book), startCap)
	}
}

func TestRemoveOrder(t *testing.T) {
	book := _newBook()
	indexToRemove := 4
	newFirstOrder := (*book)[indexToRemove+1]
	startLen, startCap := len(*book), cap(*book)
	book.removeOrder((*book)[indexToRemove], indexToRemove)
	if len(*book) != startLen-1 {
		t.Fatalf("length of book didn't decrease by one (%d != %d)", len(*book), startLen-1)
	}
	if cap(*book) != startCap {
		t.Fatalf("capacity of book changed (%d != %d)", cap(*book), startCap)
	}
	if (*book)[indexToRemove] != newFirstOrder {
		t.Fatal("slice not restuctured")
	}
}

func TestReplaceOrder(t *testing.T) {
	book := _newBook()
	indexToChange, newVol := 0, 1.0
	newOrder := &Order{(*book)[indexToChange].Price, newVol}
	book.replaceOrder(newOrder, indexToChange)
	if (*book)[indexToChange] != newOrder {
		t.Fatal("order not changed")
	}
}

func TestNewBook(t *testing.T) {
	var length uint = 3
	book := NewBook(length)
	if cap(book) != int(length)+1 {
		t.Fatalf("capacities not equal (%d != %d)\n", len(book), length+1)
	}
}

func TestUpdateBook(t *testing.T) {
	book := _newBook()

	book.Update(&Order{Price: 5709.20000, Volume: 3.00000000},
		&Order{Price: 5708.20000, Volume: 0.00000000},
		&Order{Price: 5705.90000, Volume: 7.62400000})
	book.Update(&Order{Price: 5709.20000, Volume: 8.00000000},
		&Order{Price: 5709.40000, Volume: 0.30000000})
	book.Update(&Order{Price: 5708.30000, Volume: 0.00000000},
		&Order{Price: 5705.90000, Volume: 7.62400000})

	prices := []float64{5705.9, 5706.3, 5706.4, 5706.9, 5707.0, 5707.4, 5707.8, 5709.2, 5709.4, 5711.7}
	vols := []float64{7.624, 1.0, 0.856, 1.173, 0.002, 4.33, 2.5, 8.0, 0.3, 0.007498}
	for i, order := range *book {
		if prices[i] != order.Price {
			t.Fatalf("wrong price in orderbook (%f != %f)", prices[i], order.Price)
		}
		if vols[i] != order.Volume {
			t.Fatalf("wrong volume in orderbook (%f != %f)", vols[i], order.Volume)
		}
	}

}

func TestRepeatedInsert(t *testing.T) {
	book := _newBook()
	startLen, startCap := len(*book), cap(*book)

	newOrders := []*Order{&Order{Price: 5707.85, Volume: 1.0},
		&Order{Price: 5707.86, Volume: 1.0},
		&Order{Price: 5707.87, Volume: 1.0}}
	book.Update(newOrders...)
	if len(*book) != startLen {
		t.Fatalf("length of book changed (%d != %d)", len(*book), startLen)
	}
	if cap(*book) != startCap {
		t.Fatalf("capacity of book changed (%d != %d)", cap(*book), startCap)
	}
}

func TestOutOfRangeUpdate(t *testing.T) {
	book := _newBook()
	newOrder := &Order{Price: 5712.85, Volume: 1.0}
	book.Update(newOrder)
	for _, order := range *book {
		if order == newOrder {
			t.Fatal("out of range order in order book")
		}
	}
}

func Benchmark_newBook(b *testing.B) {
	for n := 0; n < b.N; n++ {
		_ = _newBook()
	}
}

func BenchmarkUpdateBook(b *testing.B) {
	first := []*Order{&Order{Price: 5709.20000, Volume: 3.00000000},
		&Order{Price: 5708.20000, Volume: 0.00000000},
		&Order{Price: 5705.90000, Volume: 7.62400000}}
	second := []*Order{&Order{Price: 5709.20000, Volume: 8.00000000},
		&Order{Price: 5709.40000, Volume: 0.30000000}}
	third := []*Order{&Order{Price: 5708.30000, Volume: 0.00000000},
		&Order{Price: 5705.90000, Volume: 7.62400000}}
	b.ResetTimer()

	for n := 0; n < b.N; n++ {
		book := _newBook()
		book.Update(first...)
		book.Update(second...)
		book.Update(third...)
	}
}

func BenchmarkSingleInsert(b *testing.B) {
	order := &Order{Price: 5705.90000, Volume: 7.62400000}
	b.ResetTimer()

	for n := 0; n < b.N; n++ {
		book := _newBook()
		book.insertOrder(order, 0)
	}
}

func BenchmarkSingleRemove(b *testing.B) {
	order := &Order{Price: 5706.30000, Volume: 0.0}
	b.ResetTimer()

	for n := 0; n < b.N; n++ {
		book := _newBook()
		book.removeOrder(order, 0)
	}
}

func BenchmarkSingleReplace(b *testing.B) {
	order := &Order{Price: 5706.30000, Volume: 1.0}
	b.ResetTimer()

	for n := 0; n < b.N; n++ {
		book := _newBook()
		book.replaceOrder(order, 0)
	}
}

func BenchmarkNewBook(b *testing.B) {
	var maxDepth uint = 10

	for n := 0; n < b.N; n++ {
		_ = NewBook(maxDepth)
	}
}