[HN Gopher] Parsing Decimals four times faster
___________________________________________________________________
Parsing Decimals four times faster
Author : cantortrading
Score : 113 points
Date : 2022-01-27 14:46 UTC (8 hours ago)
(HTM) web link (cantortrading.fi)
(TXT) w3m dump (cantortrading.fi)
| loeg wrote:
| Lovely concrete and succinct example of a variety of strategies
| to attack performance problems. Very cool.
| dhosek wrote:
| 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.
| pvg wrote:
| 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...
| solmag wrote:
| It's a nice article, but don't they run against Amdahl's law? I
| mean they're parsing JSON from some web api?
| marginalia_nu wrote:
| Ahmdals law deals with throughput or start-to-stop time for
| processing a given work, not necessarily latency.
| funcDropShadow wrote:
| 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.
| dahfizz wrote:
| 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.
| Bootvis wrote:
| Isn't Amdahl's law only applicable to systems that some
| parallelism?
| edflsafoiewq wrote:
| 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.
| CUViper wrote:
| 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.
| Bootvis wrote:
| 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.
| SloopJon wrote:
| 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?
| pclmulqdq wrote:
| 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...
| [deleted]
| lordnacho wrote:
| 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.
| andylynch wrote:
| 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.
| Bootvis wrote:
| JSON is common in crypto what Cantor appears to be trading.
| gfd wrote:
| Does crypto allow colocation like stock trading? If it's
| gonna be some websocket endpoint, what's the point of
| optimizing microseconds?
| nly wrote:
| 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.
| Bootvis wrote:
| 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 :)
| ajoseps wrote:
| 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
| lordnacho wrote:
| 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.
| ajoseps wrote:
| 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.
| exdsq wrote:
| 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 :)
| twic wrote:
| 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...
| exdsq wrote:
| Thanks Twic!
| andylynch wrote:
| 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.
| exdsq wrote:
| 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.
| ajoseps wrote:
| a couple of exchanges already have FIX APIs. I think
| Coinbase Pro and Gemini both do.
| exdsq wrote:
| Interesting! I've worked on the other side - blockchains
| themselves - and only recently started working for a DEX.
| Lots to learn!
| Bootvis wrote:
| Bitstamp as well
| amluto wrote:
| > 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.
| dahfizz wrote:
| 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.
| exdsq wrote:
| 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?
| amluto wrote:
| 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.
___________________________________________________________________
(page generated 2022-01-27 23:01 UTC)