Raul, briefly inline, I will not extend this thread, I am not looking for a solution to our engine, it is already architected extremely efficiently.
> On 22 Nov 2019, at 4:53 am, Raul Miller <rauldmil...@gmail.com> wrote: >> > > This is the kind of information I was looking for. > > That said, I am having trouble reconciling the concept of "single > digit microsecond latency round-trip from the client" with traversing > linked list structures of that size at that rate and not being able to > do the same thing with arrays. (I can see achieving that some of the > time -- relatively unloaded systems, and tree structures for quick > traversal, but I'm pretty sure you're going to have stalls of some > sort sooner or later. This might be manageable, though, if the > requirements of the quirks of the algorithm are baked into the > agreements about use of the system.) > > Then again, further down in this message, it seems like you're > suggesting that you're not actually traversing the lists. No, several lists are maintained. For the primary order matching the main 2 lists start at BestBid and BestOffer. Matching is the process of traversing the list so a 100% hit rate) until no balance remains, or matching ceases (strike a “worse price”). This is a key to getting the matching algorithm optimised. The lists are stored in the appopriate sorted order (Price/Time). > >> C kills C++ for this stuff (simply closer to the metal) and likewise both >> kill array languages. >> I have seen efforts by people to write matching engines in array languages >> (eg BITMEX is written in kdb+) and they all fail at performance, barely able >> to consume over 1,000 orders per second. >> The key reason is the overhead of the array language to process incoming >> orders arriving each in a single message upwards of 100,000 orders per >> second. >> >> You can append to arrays in array languages at this rate but you can’t >> maintain indices for optimal search matching (head of list) and it is >> likewise impractical to run shadows of the data. > > "Head of list" does not sound like "order matching". Maybe a part of a > larger system that does order matching, but it seems to me that "head > of list" means matching already happened. So, presumably, I'm missing > out on some key details. As per above, Head of List is the Best Bid (for Buys) or Best Ask (for Sells) and “possible matches” start at that point. So an incoming Bid will try to start matching at Best Offer etc as above. > >> Cache misses do not impact this matching, it is physical memory and all >> orders are stored as contiguous rows in the Orders table as are other >> tables. The linked lists provide the only proven way to scale the matching >> speeds required. > > Yeah, ok, but it sounds like you are feeding me contradictory views of > the system. So -- again -- presumably I'm missing out on some key > details. (And, this means that if I were to attempt to optimize for > these cases, I would almost certainly do it wrong.) No, I explained the tables we maintain in memory are contiguous (dense) so we don’t strike cache hits. The linked lists themselves are likewise dense, as the list next/prev pointers are column on the order table… so all dense. > >> So I stand by my comments, which were a constructive suggestion that an >> “ordering attribute” in an array could be a mechanism to help an array >> language become useful in this space, a I used sorted linked lists in C. >> However relying solely on arrays for this kind of performance when receiving >> and processing over 100,000 “events” (orders) per second will not do it. > > Color me... uncertain about what you have been claiming… I wasn’t claiming anything ? I suggested an ordering attribute may allow a matching engine model to be efficiently built in J (and I suspect once understood/tuned could be applied to other use cases just as efficiently. Anyway enough discussion on this thread, if I ever get time (though I rarely do) I will model this to demonstrate what I think could is possible and offer more a more concrete suggestion & use case. Thanks, Rob > > Thanks, > > > -- > Raul > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
