Parsing Decimals four times faster | Hacker News Reader

Parsing Decimals four times faster

cantortrading.fi

140 pointscantortrading43 comments

I started reading this thinking it would be about FIX tag/value.

Now I’m more than a little shocked multiple someones are publishing real time data in JSON for algos?? I thought this was mostly a solved problem with OUCH, ITCH, FIX SBE and friends.

But great to see this writeup, getting these details right can make a big difference.

JSON is common in crypto what Cantor appears to be trading.

Does crypto allow colocation like stock trading? If it's gonna be some websocket endpoint, what's the point of optimizing microseconds?

This is a good point. You expect more jitter on a public network. My guess is they've come from traditional finance, where performance porn is just irresistible.

Some exchanges do offer colo.

It kind of does. Most exchanges are hosted in the cloud and I don't think AWS offers colocation similar to the traditional exchanges. I bet Cantor ensures that the machines they are using are close to those used by the exchanges.

HFT on a traditional exchange will be faster but that's not the competition. The competition in crypto faces the same problems so you just need to be faster than them.

Of course, if the whole process has too much uncontrollable noise (jitter) due to cloud specific reasons it probably doesn't matter. I hope they managed to control this before doing this optimization :)

one approach I've heard of some places using is to figure out where the exchange is hosted, spin up multiple instances to test the latency to the exchange, then choose the lowest latency instance. Not sure how often one would need to redo this process though.

one exchange that does allow colo is gemini. They're located in NY5 (https://docs.gemini.com/fix-api/#connecting) and allow cross connects. When colo-ed, you wouldn't be using websocket but their FIX API. Multiple other crypto providers are also colo-ed in the same location

Lots of prop-trading firms aren't comfortable trading over the Internet. Often the concern isn't "someone might see my trades", since reverse engineering alpha from that is hard, or even latency, since not all strategies are super latency sensitive, ... but plain old infosec.

These sorts of firms are super paranoid about the exfiltration of proprietary IP. When you add trading over the Internet in to the mix, you just have more ways to do that. You have highly dynamic cloud infrastructure to deal with (whereas traditionally everything is static), DNS security, tricky PKI/certificate management, the need for much tighter access controls, firewalling (both at the network and application protocol level) and the secure logging and monitoring of flow between networks. And everything needs to be tight enough so no single actor (external or internal) can compromise the system.

Where can I read more about those formats? I work in crypto, same as cantor trading that posted this, and always keen on re-using solved problems if they work :)

A great starting point is FIX. They are the open standards group in this area, at https://www.fixtrading.org/. ITCH and OUCH came from Island, now part of NASDAQ and the specs are on their website.

Thanks! I saw they have a working group on crypto so applied to join that, keen to see what they're up to. Standardizing data structures across chains makes a lot of sense but sadly there's a lot of competition rather than collaboration between them "Mine is better than yours hahahaha moon" etc... I'll have to give this some real thought! I think one issue may be that the specification is so complex implementing it within a new DEX without buy-in from others means it's a lot of work with little reward. Might be the case that if larger established front-offices/exchanges start expecting it that crypto could follow. Coinbase released an API standard that blockchains had to conform to for testing the chain prior to listing so it's not unprecedented for that to happen.

a couple of exchanges already have FIX APIs. I think Coinbase Pro and Gemini both do.

Bitstamp as well

Interesting! I’ve worked on the other side - blockchains themselves - and only recently started working for a DEX. Lots to learn!

> A great starting point is FIX.

I beg to differ. FIX could almost be a case study on how not to design a protocol.

Session management and recovery is outside the login protocol? Check! Can’t reliably recover from a failed login or wrong password attempt? Check! [0] Message boundaries are nontrivial to detect? Check! Field values are binary but cannot represent the byte 0x01? Check!

But FIX has a brilliant extensible hierarchical message structure that is more type safe than JSON, you say! Sure, kind of, but the encoding of lists of nested objects is utter nonsense. Not only is it somewhat redundant (the number of repeats is sent first, but the number of repeats is also determinable after parsing the whole thing, resulting in some awkward questions about what to do if the numbers disagree), but it has worse problems. Specifically, if the sender and receiver don’t agree on the precise set of fields and their order in each nested object, then the list cannot be parsed. This makes the whole concept of extensibility someone dubious. (This is because there is no delimiter between repeated objects; instead you notice that the field you’re parsing can’t legally belong to the object you’re parsing, meaning it’s time to use a crystal ball to determine whether a new repeat has started, the whole list is done, or an error has occurred.)

On top of all this, the standard implementation, QuickFIX, is a work of art, and not in a good way.

FIX SBE is IMO not at all better except that it can be serialized and deserialized faster.

[0]. No, really. If you try to log in to someone else’s session and the server rejects the password, you have just fried their session. The protocol cannot recover. Sometimes I wonder if this was deliberate, because screwing this up at the protocol level takes some creativity. Imagine if trying to log in to someone else’s email account caused their next login attempt to fail! Oh wait, some password attempt policies do this, but FIX does it by corrupting the whole protocol state machine rather than merely having a misguided policy.

That login stuff sounds… painful. So you’re saying as UserA if I try to login as UserB, UserBs login is corrupted and they have to relogin?

Worse. For a “session” (connection from a client to a server with corresponding IDs — the IDs serve a purpose somewhere between a username and a TCP port), there is some state that is used to recover potentially lost messages if the session drops and reconnects. If a session is down, someone tries to connect and restore that session, and the login fails, then the replay state will get out of sync on both ends and a subsequent valid reconnection will either fail or lose messages.

FIX is less ergonomic than JSON, that is not in question. FIX is much faster to generate and parse than JSON, and much easier to deal with than bespoke binary feeds.

I think FIX makes the right tradeoffs.

I don't understand what you mean regarding killing someone else's session. You can reset sequence numbers in the login message.

There is absolutely no reason that FIX should be faster to generate than JSON. I agree that one could plausibly parse it faster. JSON wasn’t meant as a real comparison though — FIX is structurally much more like protocol buffers, but protocol buffers are much better.

As for sequence numbers: suppose your session drops. You’ve received the message with sequence number 5, but you’ve missed 6 and 7. You’ve sent 10 and 11 but the other end only got 10. Now someone (your own misconfigured software or someone else) connects and sends Logon to the server with your comp id, with sequence number 11 but the wrong authentication data. What is even supposed to happen? The session now contains two different message 11s to the server. It’s broken. You can (sometimes) recover by resetting sequence numbers, but that defeats the entire purpose of having sequence numbers in the first place: the server was supposed to recover the original message 11 on a reconnection attempt and correctly handle it as a possible duplicate. (As a practical matter merely experiencing network trouble during a reconnection also seems to break everything, mostly because common FIX implementations are terrible.)

I suppose it must be possible to be so deeply entrenched in the FIX ecosystem that this makes any sense at all, but the whole protocol is backwards. You should connect, authenticate that connection, and then run the session protocol inside the authenticated connection. The Logon should not be sequenced — that gets the layering backwards.

And replying further: this isn’t about whether FIX makes the right trade offs. This is about the fact that, even in the position in design space that FIX occupies, FIX is terrible. One could have easily designed a protocol with the same level of security as FIX and precisely the same (application) message semantics and schema that actually worked well. It wouldn’t even be very different from FIX. All you would need is proper layering, group delimiters, delimiters for entire messages, and either proper escaping or length-prefixing of fields. (And length-prefixing would make parsing quite a bit faster without needing to resort to vectorized searches for where fields and groups end.)

Eurex's 'Enhanced Order Book Interface' is another one, with documentation that i think is pretty good - there's a PDF manual here:

https://www.eurex.com/ex-en/support/initiatives/t7-release-1...

Thanks Twic!

T7 is a mess

LSE's platform is much more modern: GTP being pretty much the perfect example of how to build a modern super-fast protocol

https://www.lseg.com/sites/default/files/content/documents/G...

Awesome write-up. I love that they're so open about sharing the speed improvement with the open source community. I've worked in several trading firms where it's just not thinkable to do something like that.

Lovely concrete and succinct example of a variety of strategies to attack performance problems. Very cool.

Great article but I've got one question. If they have to read the assembly created by the compiler to understand how to write Rust code that the compiler could optimize, why didn't they directly write assembly code?

Portability?

It's much easier to read assembly code than to write it. You're only looking for the necessary performance in a few hot-spots. Everywhere else the convenience of a high-level language is welcome. With the tail-call optimization, it's really only a fact of how programming languages are implemented that you need to look at the assembly. In a language that guarantees tail calls, or has a special tail-call keyword, you could forget about what's going on at the instruction level.

Portability: one you hand-code assembler for an architecture you lose compatibility for others. Unless you provide multiple code paths to account for this, but that increases testing and maintenance requirements.

Future optimisations using better on-chip features, or other new techniques: new instructions that reduce the task might get used by the compiler but it won't update your section in hand-coded assembler.

Maintainability: you don't want to force larger parts of your workforce/community to be familiar with assembly if it is not useful day-to-day, or lock your assembly capable people to maintaining those hand-written-assembly portions.

Understood. About maintainability I guess that that code must be marked as do not modify, or the compiler will walk out of the optimization path. Future developers on that project must know very well why that code is written like that. Furthermore any new compiler or CPU could break the optimizations.

I find it fascinating that something like parsing decimals is not a long-solved problem (and kind of connected was the recent post on emulating the IBM system 360 where decimal parsing was baked into the hardware.

I think it is, for the most part, a long-solved problem and both your example and the article outline it, in a somewhat circuitous and circumscribed way - it's a combination of 'make computers so much faster, it doesn't matter' and 'don't use decimals'. This writeup is about a very specialized case in which they're both using decimals (down to the internal representation) and it's not quite fast enough for their purposes.

Every x86 computer, incidentally, still carries vestigial hardware support for BCD.

https://stackoverflow.com/questions/33182491/why-bcd-instruc...

The rust_decimal crate seems to use C#-style decimals, which always struck me as wasteful. Is there any particular advantage to that format over IEEE decimal floating point?

Without hardware support, IEEE 754 decimal floating point can have some very sharp edges. I'm sure that the C# decimal format avoids these by spending more space.

I'm personally surprised that this firm isn't using "integer # of exchange ticks" as their storage format for prices...

Integer # of exchange ticks would be nice, but that covers a very wide integer range across a lot of products and changes without warning (not to mention, can be inconsistently applied...).

Using base-10 decimals is a good compromise between the perfect solution and something that 'just works'. It also means we don't have to go rewrite everything and instead can just do some optimization work when needed.

It's a nice article, but don't they run against Amdahl's law? I mean they're parsing JSON from some web api?

Isn't Amdahl's law only applicable to systems that some parallelism?

Amdahl's law basically says when you speed up part of a task, the overall speedup is limited by the part you didn't speed up. The speedup doesn't have to come from parallelism.

It can be applied more generally. If you're focusing on improving the performance of something that only takes 10% of your time, then the other 90% will still dominate.

Aha, I see. If you’re in a race where every microsecond counts you would still care about there 10% after you’ve made sure that the 90% can’t be further optimized.

Ahmdals law deals with throughput or start-to-stop time for processing a given work, not necessarily latency.

Possibly, but if you are processing live market data, you are in the arena of almost hard real-time systems. I.e. you effectively have a time budget to process every single tick/message. Then, even low-level optimization can make a large difference. E.g. if you can make some helper method use less memory, i.e. it uses less of your caches, that can make a big difference on your business logic. Amdahl's law is not at all suited to understand such non-linear non-local inter-dependencies.

The key, I think, is that everyone else is parsing the same JSON from the same web api. If you can do it faster than them, its still an advantage.

Reply on news.ycombinator.com