1.
작년 Tower Research Capital이 10만불을 걸고 프로그램경진대회를 하였습니다. Quantcup이라는 이름으로 진행한 첫 대회의 주제는 Price-Time Matching Engine이었습니다.
QuantCup: a quant trading themed programming contest
우선 주최측이 기본소스를 제공하였습니다. 참가자는 주최즉이 제공한 소스중 engine.c를 수정하여 score_feed.h의 데이타를 가장 빨리 처리하는 개발자가 우승하는 방식입니다. 제공한 소스의 기본값은 14,500입니다. 대회 결과 437.9를 보인 voyager가 우승하였다고 합니다. 차이가 엄청나죠.(^^) 왜 이런 결과가 나왔는지 직접 확인해보시길 바랍니다. 그러면 주최측 소스와 우승자의 소스를 보시죠. 먼저 주최측 소스입니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 |
/* Most basic implementation of the matching engine O(n) add O(n) cancel */ //#include <stdio.h> #include "engine.h" // INTERNAL TYPES /* Limit Order Internal */ typedef struct { t_order order; t_orderid id; } t_order_in; // DOUBLY LINKED LIST #define MYDATA t_order_in #define MYDATAINIT {{'', '', 0, 0, 0}, 0} #include "double_link_list.c" // GLOBALS /* Stores all live bids and asks*/ list * bids; list * asks; /* The next ID which will be assigned an order */ t_orderid nextid; // IMPLEMENTATION HELPERS /* Returns the node with the given id in list l, or NULL if no node has that id */ node * find_node(t_orderid id, list * l) { node * node_iter = l->head->next; while (node_iter->data.id != id && node_iter != l->tail) { node_iter = node_iter->next; } if (node_iter == l->tail) { return NULL; } else { return node_iter; } } /* Call the execution report callback to notify both parties to the trade o1 and o2 are assumed to be the same price on opposite sides */ void send_exec(t_order * o1, t_order * o2) { t_execution exec = (t_execution)(*o1); exec.size = o1->size > o2->size ? o2->size : o1->size; execution(exec); // rename trader field on exec to old's name int i; for(i = 0; i < STRINGLEN; i++) { exec.trader[i] = o2->trader[i]; } exec.side = !exec.side; execution(exec); } /* IN: order_new: new order being added to the book node_old: old order sitting on the book l: side of the book old sits on OUT: */ void trade(t_order * order_new, node * node_old, list * l) { // shorthand t_order * order_old = &node_old->data.order; // execution report send_exec(order_new, order_old); // new completely fills old if (order_new->size >= order_old->size) { order_new->size -= order_old->size; remove_node(l, node_old); } // new partially fills old else { order_old->size -= order_new->size; order_new->size = 0; } } /* helpers for cross function */ int hit_ask(t_price bid, t_price ask) { return bid >= ask; } int hit_bid(t_price ask, t_price bid) { return ask <= bid; } // cross as many shares as possible int cross(t_order * order) { // which side int isask = is_ask(order->side); list * book = isask ? bids : asks; int (*cross_test)(t_price, t_price) = isask ? hit_bid : hit_ask; // trade through existing orders one-by-one node * book_iter = book->head->next; while(book_iter != book->tail && cross_test(order->price, book_iter->data.order.price)) { trade(order, book_iter, book); if (order->size == 0) { return 1; } book_iter = book_iter->next; } return 0; } /* helpers for queue function */ int priority_ask(t_price ask_new, t_price ask_old) { return ask_new < ask_old; } int priority_bid(t_price bid_new, t_price bid_old) { return bid_new > bid_old; } void queue(t_order * order) { int isask = is_ask(order->side); list * book = isask ? asks : bids; int (*priority_test)(t_price, t_price) = isask ? priority_ask : priority_bid; node * book_iter = book->head->next; while(book_iter != book->tail && !priority_test(order->price, book_iter->data.order.price)) { book_iter = book_iter->next; } t_order_in o; o.order = *order; o.id = nextid; insert_before(book, book_iter, o); } // IMPLEMENTATION void init() { nextid = 1; bids = new_list(); asks = new_list(); } void destroy() { delete_list(bids); delete_list(asks); } t_orderid limit(t_order order) { if (!cross(&order)) queue(&order); return nextid++; } void cancel(t_orderid orderid) { // look for orderid in bids node * node = find_node(orderid, bids); if (node) { remove_node(bids, node); } else { // look for orderid in asks node = find_node(orderid, asks); if (node) { remove_node(asks, node); } } } |
다음은 우승자의 소스입니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 |
/***************************************************************************** * QuantCup 1: Price-Time Matching Engine * * Submitted by: voyager * * Design Overview: * In this implementation, the limit order book is represented using * a flat linear array (pricePoints), indexed by the numeric price value. * Each entry in this array corresponds to a specific price point and holds * an instance of struct pricePoint. This data structure maintains a list * of outstanding buy/sell orders at the respective price. Each outstanding * limit order is represented by an instance of struct orderBookEntry. * * askMin and bidMax are global variables that maintain starting points, * at which the matching algorithm initiates its search. * askMin holds the lowest price that contains at least one outstanding * sell order. Analogously, bidMax represents the maximum price point that * contains at least one outstanding buy order. * * When a Buy order arrives, we search the book for outstanding Sell orders * that cross with the incoming order. We start the search at askMin and * proceed upwards, incrementing askMin until: * a) The incoming Buy order is filled. * b) We reach a price point that no longer crosses with the incoming * limit price (askMin > BuyOrder.price) * In case b), we create a new orderBookEntry to record the * remainder of the incoming Buy order and add it to the global order * book by appending it to the list at pricePoints[BuyOrder.price]. * * Incoming Sell orders are handled analogously, except that we start at * bidMax and proceed downwards. * * Although this matching algorithm runs in linear time and may, in * degenerate cases, require scanning a large number of array slots, * it appears to work reasonably well in practice, at least on the * simulated data feed (score_feed.h). The vast majority of incoming * limit orders can be handled by examining no more than two distinct * price points and no order requires examining more than five price points. * * To avoid incurring the costs of dynamic heap-based memory allocation, * this implementation maintains the full set of orderBookEntry instances * in a statically-allocated contiguous memory arena (arenaBookEntries). * Allocating a new entry is simply a matter of bumping up the orderID * counter (curOrderID) and returning a pointer to arenaBookEntries[curOrderID]. * * To cancel an order, we simply set its size to zero. Notably, we avoid * unhooking its orderBookEntry from the list of active orders in order to * avoid incurring the costs of pointer manipulation and conditional branches. * This allows us to handle order cancellation requests very efficiently; the * current implementation requires only one memory store instruction on * x86_64. During order matching, when we walk the list of outstanding orders, * we simply skip these zero-sized entries. * * The current implementation uses a custom version of strcpy() to copy the string * fields ("symbol" and "trader") between data structures. This custom version * has been optimized for the case STRINGLEN=5 and implements loop unrolling * to eliminate the use of induction variables and conditional branching. * * The memory layout of struct orderBookEntry has been optimized for * efficient cache access. *****************************************************************************/ #include <stdio.h> #include <strings.h> #include <stdlib.h> #include "engine.h" /* Enable/disable optimizations */ #define UNROLL_STRCPY #define MAX_NUM_ORDERS 1010000 // #define DEBUG (enable/disable debugging) #ifdef DEBUG #define ASSERT(c) do { \ if (!(c)) { fprintf(stderr, "ASSERT failure at line %d\n", __LINE__); \ exit(1); }} while(0) #else #define ASSERT(c) #endif #ifdef UNROLL_STRCPY #define COPY_STRING(dst, src) do { \ dst[0] = src[0]; dst[1] = src[1]; dst[2] = src[2]; \ dst[3] = src[3]; /* dst[4] = src[4]; */ \ } while(0) #else #include <string.h> #define COPY_STRING(dst, src) strcpy(dst, src) #endif /* struct orderBookEntry: describes a single outstanding limit order (Buy or Sell). */ typedef struct orderBookEntry { t_size size; /* Order size */ struct orderBookEntry *next; /* Next entry in the pricePoint list */ char trader[4]; } orderBookEntry_t; /* struct pricePoint: describes a single price point in the limit order book. */ typedef struct pricePoint { orderBookEntry_t *listHead; orderBookEntry_t *listTail; } pricePoint_t; /** Global state ***/ /* An array of pricePoint structures representing the entire limit order book */ static pricePoint_t pricePoints[MAX_PRICE + 1]; static t_orderid curOrderID; /* Monotonically-increasing orderID */ static unsigned int askMin; /* Minimum Ask price */ static unsigned int bidMax; /* Maximum Bid price */ /* Statically-allocated memory arena for order book entries. This data structure allows us to avoid the overhead of heap-based memory allocation. */ static orderBookEntry_t arenaBookEntries[MAX_NUM_ORDERS]; static orderBookEntry_t *arenaPtr; #define ALLOC_BOOK_ENTRY(id) void init() { /* Initialize the price point array */ bzero(pricePoints, (MAX_PRICE + 1) * sizeof(pricePoint_t)); /* Initialize the memory arena */ bzero(arenaBookEntries, MAX_NUM_ORDERS * sizeof(orderBookEntry_t)); arenaPtr = arenaBookEntries; // Bring the arena pointer into the cache curOrderID = 0; askMin = MAX_PRICE + 1; bidMax = MIN_PRICE - 1; } void destroy() { } /* Insert a new order book entry at the tail of the price point list */ void ppInsertOrder(pricePoint_t *ppEntry, orderBookEntry_t *entry) { if (ppEntry->listHead != NULL) ppEntry->listTail->next = entry; else ppEntry->listHead = entry; ppEntry->listTail = entry; } /* Report trade execution */ void EXECUTE_TRADE(const char *symbol, const char *buyTrader, const char *sellTrader, t_price tradePrice, t_size tradeSize) { t_execution exec; if (tradeSize == 0) /* Skip orders that have been cancelled */ return; COPY_STRING(exec.symbol, symbol); exec.price = tradePrice; exec.size = tradeSize; exec.side = 0; COPY_STRING(exec.trader, buyTrader); exec.trader[4] = '\0'; execution(exec); /* Report the buy-side trade */ exec.side = 1; COPY_STRING(exec.trader, sellTrader); exec.trader[4] = '\0'; execution(exec); /* Report the sell-side trade */ } /* Process an incoming limit order */ t_orderid limit(t_order order) { orderBookEntry_t *bookEntry; orderBookEntry_t *entry; pricePoint_t *ppEntry; t_price price = order.price; t_size orderSize = order.size; if (order.side == 0) { /* Buy order */ /* Look for outstanding sell orders that cross with the incoming order */ if (price >= askMin) { ppEntry = pricePoints + askMin; do { bookEntry = ppEntry->listHead; while(bookEntry != NULL) { if (bookEntry->size < orderSize) { EXECUTE_TRADE(order.symbol, order.trader, bookEntry->trader, price, bookEntry->size); orderSize -= bookEntry->size; bookEntry = bookEntry->next; } else { EXECUTE_TRADE(order.symbol, order.trader, bookEntry->trader, price, orderSize); if (bookEntry->size > orderSize) bookEntry->size -= orderSize; else bookEntry = bookEntry->next; ppEntry->listHead = bookEntry; return ++curOrderID; } } /* We have exhausted all orders at the askMin price point. Move on to the next price level. */ ppEntry->listHead = NULL; ppEntry++; askMin++; } while(price >= askMin); } entry = arenaBookEntries + (++curOrderID); entry->size = orderSize; COPY_STRING(entry->trader, order.trader); ppInsertOrder(&pricePoints[price], entry); if (bidMax < price) bidMax = price; return curOrderID; } else { /* Sell order */ /* Look for outstanding Buy orders that cross with the incoming order */ if (price <= bidMax) { ppEntry = pricePoints + bidMax; do { bookEntry = ppEntry->listHead; while(bookEntry != NULL) { if (bookEntry->size < orderSize) { EXECUTE_TRADE(order.symbol, bookEntry->trader, order.trader, price, bookEntry->size); orderSize -= bookEntry->size; bookEntry = bookEntry->next; } else { EXECUTE_TRADE(order.symbol, bookEntry->trader, order.trader,price, orderSize); if (bookEntry->size > orderSize) bookEntry->size -= orderSize; else bookEntry = bookEntry->next; ppEntry->listHead = bookEntry; return ++curOrderID; } } /* We have exhausted all orders at the bidMax price point. Move on to the next price level. */ ppEntry->listHead = NULL; ppEntry--; bidMax--; } while (price <= bidMax); } entry = arenaBookEntries + (++curOrderID); entry->size = orderSize; COPY_STRING(entry->trader, order.trader); ppInsertOrder(&pricePoints[price], entry); if (askMin > price) askMin = price; return curOrderID; } } /* Cancel an outstanding order */ void cancel(t_orderid orderid) { arenaBookEntries[orderid].size = 0; } |
2.
우승자는 아닙니다만 또다른 분이 소스를 올려놓았습니다. 아래를 가시면 주최측이 제공한 전체소스도 같이 확인할 수 있습니다. engine.c를 제외하면 주최측이 제공한 소스입니다.
Edmund Horner’s various projects and free stuff
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 |
/** Edmund's price-time matching engine. * * See http://www.quantcup.org/ for background. * * Operations to optimise: * - Finding matching orders (and removing them). * - Adding an unmatched order. * - Cancelling an order. * * First trick is to preallocate all data structures. The maximum number of live orders is 65536. * Second trick is use an array of NODEs, one per price. Price is limited to integers between 1 and 65536. * Third trick is to use a unified set of nodes for asks and bids. At a given price, either bids or asks exist, but never both. * Fourth trick is to use a skip list for nodes. * Fifth trick is to use a hash table for orders in the queue, so we can find and cancel them. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include "engine.h" #define LIST_HEIGHT 4 #define MAP_SIZE MAX_LIVE_ORDERS #ifdef NDEBUG #define fprintf(...) #endif typedef struct ORDER { t_orderid id; t_order data; struct ORDER *next, *prev; struct ORDER *next_in_bin; } ORDER; typedef struct BIN { ORDER *first, *last; } BIN; typedef struct NODE { t_side side; t_price price; ORDER *first_order, *last_order; struct NODE *nexts[LIST_HEIGHT], *prevs[LIST_HEIGHT]; } NODE; static NODE *nodes; static NODE *bottom_node; static NODE *top_node; static NODE *best_bid; static NODE *best_ask; static ORDER *orders; static BIN free_orders; static BIN *id_map; static t_orderid next_id = 0; static char *order_string(t_order *data) { static char buffer[100]; snprintf(buffer, sizeof(buffer), "{ \"%s\", \"%s\", %d, %d, %ld }", data->symbol, data->trader, data->side, data->price, data->size); return buffer; } void init() { int i; fprintf(stderr, "Initialising\n"); nodes = malloc(sizeof(NODE) * (MAX_PRICE+2)); for (i = MIN_PRICE; i <= MAX_PRICE; i++) { nodes[i].price = 0; } bottom_node = &nodes[0]; top_node = &nodes[MAX_PRICE+1]; bottom_node->price = 0; top_node->price = 0; for (i = 0; i < LIST_HEIGHT; i++) { bottom_node->nexts[i] = top_node; bottom_node->prevs[i] = NULL; top_node->nexts[i] = bottom_node; top_node->prevs[i] = NULL; } best_ask = top_node; best_bid = bottom_node; orders = malloc(sizeof(ORDER) * MAX_LIVE_ORDERS); for (i = 0; i < MAX_LIVE_ORDERS; i++) { orders[i].id = 0; orders[i].next_in_bin = &orders[i+1]; } orders[MAX_LIVE_ORDERS-1].next_in_bin = NULL; free_orders.first = &orders[0]; free_orders.last = &orders[MAX_LIVE_ORDERS-1]; id_map = malloc(sizeof(BIN) * MAP_SIZE); memset(id_map, 0, sizeof(BIN) * MAP_SIZE); next_id = 1; } void destroy() { fprintf(stderr, "Destroying\n"); free(nodes); free(orders); free(id_map); } static void find_place(t_price price, NODE **vector) { NODE *n = bottom_node; int i; int steps = 0; /*if (price >= best_ask->price) n = best_ask;*/ for (i = LIST_HEIGHT - 1; i >= 0; i--) { while (n->nexts[i]->price <= price && n->nexts[i] != top_node) { n = n->nexts[i]; steps++; } vector[i] = n; } if (steps >= 20) { printf("EEK, steps = %d\n", steps); } } static void add_to_list(NODE *node) { int i; NODE *prevs[LIST_HEIGHT]; find_place(node->price, prevs); for (i = 0; i < LIST_HEIGHT; i++) { node->prevs[i] = prevs[i]; node->nexts[i] = prevs[i]->nexts[i]; prevs[i]->nexts[i]->prevs[i] = node; prevs[i]->nexts[i] = node; if ((rand() % 4) != 0) break; } for (i = i+1; i < LIST_HEIGHT; i++) { node->nexts[i] = NULL; node->prevs[i] = NULL; } if (is_ask(node->side) && (node->price < best_ask->price || best_ask == top_node)) { int i; /*for (i = LIST_HEIGHT-1; i >= 1; i++) { if (node->nexts[i] == NULL && best_ask != top_node) { node->nexts[i] = best_ask; best_ask->prevs[i]->nexts[i] = node; } if (node->prevs[i] == NULL) { node->prevs[i] = best_ask->prevs[i]; best_ask->prevs[i] = node; } }*/ best_ask = node; } else if (!is_ask(node->side) && (node->price > best_bid->price || best_bid == bottom_node)) best_bid = node; } /** * Remove a node from the skip list. * N.B. The node's nexts[0] and prevs[0] pointers remain intact after this! */ static void remove_from_list(NODE *node) { int i; assert(node->nexts[0] != NULL); assert(node->prevs[0] != NULL); node->price = 0; for (i = 0; i < LIST_HEIGHT; i++) { if (node->nexts[i]) node->nexts[i]->prevs[i] = node->prevs[i]; if (node->prevs[i]) node->prevs[i]->nexts[i] = node->nexts[i]; } if (node == best_bid) { best_bid = best_bid->prevs[0]; assert(best_bid != NULL); assert((best_bid != bottom_node) != (best_bid->price == 0)); } if (node == best_ask) { best_ask = best_ask->nexts[0]; assert(best_ask != NULL); assert((best_ask != top_node) != (best_ask->price == 0)); } } static ORDER *allocate_order(t_orderid id) { ORDER *order; int h; assert(free_orders.first); order = free_orders.first; free_orders.first = order->next_in_bin; if (free_orders.first == NULL) free_orders.last = NULL; order->id = next_id; h = order->id % MAP_SIZE; order->next_in_bin = NULL; if (id_map[h].first == NULL) { id_map[h].first = order; } else { id_map[h].last->next_in_bin = order; } id_map[h].last = order; return order; } static ORDER *free_order(t_orderid id) { int h = id % MAP_SIZE; ORDER *order = id_map[h].first; ORDER *prev = NULL; int i = 0; while (order != NULL) { if (order->id == id) break; prev = order; order = order->next_in_bin; i++; } if (i > 10) printf("i = %d!\n", i); if (order == NULL) return NULL; if (prev == NULL) { id_map[h].first = order->next_in_bin; if (id_map[h].first == NULL) id_map[h].last = NULL; } else { prev->next_in_bin = order->next_in_bin; } order->next_in_bin = NULL; free_orders.last->next_in_bin = order; free_orders.last = order; return order; } /** * 1. Clear order id. * 2. Remove the order from the list for that price. * 3. If list is now empty, remove that price. * 4. Add order to free orders stack. */ static void remove_order(ORDER *order) { NODE *node; order->id = 0; node = &nodes[order->data.price]; assert(node->price == order->data.price); if (order->next != NULL) order->next->prev = order->prev; else node->last_order = order->prev; if (order->prev != NULL) order->prev->next = order->next; else node->first_order = order->next; if (node->first_order == NULL) { fprintf(stderr, "Last order removed, removing node from list\n"); remove_from_list(node); } } /* Call the execution report callback to notify both parties to the trade o1 and o2 are assumed to be the same price on opposite sides */ void send_exec(t_order * o1, t_order * o2) { t_execution exec = *(t_execution *)o1; int i; fprintf(stderr, "Executing order %s\n", order_string(o1)); fprintf(stderr, " against %s\n", order_string(o2)); exec.size = o1->size > o2->size ? o2->size : o1->size; execution(exec); // rename trader field on exec to old's name for(i = 0; i < STRINGLEN; i++) { exec.trader[i] = o2->trader[i]; } exec.side = !exec.side; execution(exec); } /** * Attempt to consume a node. * If the node is completely consumed, remove it from the list. * If completely consumed, and data still has size, return 1. */ static int consume_node(NODE *node, t_order *data) { ORDER *order; while (data->size > 0 && node->first_order) { order = node->first_order; send_exec(data, &order->data); if (data->size < order->data.size) { order->data.size -= data->size; data->size = 0; fprintf(stderr, "New order is exhausted\n"); break; } data->size -= order->data.size; fprintf(stderr, "Old order consumed\n"); free_order(order->id); remove_order(order); } return data->size > 0; } static int cross(t_order *data) { if (is_ask(data->side)) { while (best_bid != bottom_node && best_bid->price >= data->price) { if (!consume_node(best_bid, data)) break; } } else { while (best_ask != top_node && best_ask->price <= data->price) { if (!consume_node(best_ask, data)) break; } } return data->size == 0; } static void queue(t_order *data) { ORDER *order; NODE *node = &nodes[data->price]; fprintf(stderr, "Queueing %s\n", order_string(data)); if (node->price == 0) { node->price = data->price; node->side = data->side; node->first_order = NULL; node->last_order = NULL; add_to_list(node); } else { assert(node->side == data->side); assert(node->price == data->price); } order = allocate_order(next_id); order->data = *data; order->prev = node->last_order; order->next = NULL; if (node->last_order) node->last_order->next = order; node->last_order = order; if (node->first_order == NULL) node->first_order = order; } t_orderid limit(t_order data) { fprintf(stderr, "Placing order: %s\n", order_string(&data)); if (!cross(&data)) queue(&data); fprintf(stderr, "Order id is %ld\n", next_id); return next_id++; } void cancel(t_orderid id) { ORDER *order; fprintf(stderr, "Cancelling order: %ld\n", id); order = free_order(id); if (order) { fprintf(stderr, "Cancelling %s\n", order_string(&order->data)); remove_order(order); } } #ifdef NDEBUG #undef fprintf #endif |
3.
왜 이런 경진대회를 했을까요? 아마도 주문시스템을 구축할 때 가장 기본이 되는 것이 Limit Order Book관리이기때문입니다. 해외의 호가시세를 받아서 호가잔량정보를 만드려면 LOB기술이 필수적입니다. 따라서 LOB의 성능이 주문시스템의 성능에 큰 영향을 줍니다.
위의 소스들은 Limit Orde Book을 관리하기 위하여 double link list를 사용하였습니다. 이와 관련하여 재미있는 설문조사가 있습니다. LinkedIn의 어떤 분이 하는 조사입니다.
What is your favorite data structure when writing high-performance trading software?
HFT시스템을 구축할 때 어떤 방식으로 자료관리를 하는지에 대한 질문입니다. Hash Table or Hash Map이 14 (51%), Red?black Tree 2 (7%), Ring Buffer 9 (33%), Bloom filter 1 (3%), Soft Heap (0%)입니다.
아마 국내의 경우 Hash Table을 많이 사용할 듯 합니다. 물론 다른 경우도 있겠죠.
