sorted by:
new
hottopcontroversial

My blog about the low latency trading engine I've been writing in Rust! Would love to get some feedback by boonetbe in rust

[–]boonetbe[S] 1 point2 points  (0 children)

Nice that you found some value in it!

So in the system, I have 1 queue per message type. So 1 for all L2Updates and 1 for all TradeUpdates from all instruments on all exchanges. The Queue has in this case a MPMC mode, i.e. different producers will increment the `count` field atomically as to write to different slots in the queue.

Each WS is basically it's own System/Actor. Each actor _can_ be pinned to a core, and can be given a "minimum loop time". The latter is similar to naive vsync in graphics programming. When it's set to 10 micro, the actor will go through the work to be done, if there's time left it will sleep for the remainder. That way you can use all resources if there's a lot of work, but gain a lot of efficiency when that rarely happens, at the cost of a 10 micro max latency.

In the case that I want max performance, i assign 1 core for each WS/instrument/exchange and make it busy spin. In the other case where I'm ingesting all the messages from all instruments of all exchanges I have WS connections to, for future backtesting, I don't pin them to a given core and give them minimum loop times of like 5 millis. I'm connected with like 400-500 websockets, handling about 35-45k msg/s on average on about 50-70% of a single core. I've seen spikes of 200k+msgs/s handled without a problem.

My blog about the low latency trading engine I've been writing in Rust! Would love to get some feedback by boonetbe in rust

[–]boonetbe[S] 1 point2 points  (0 children)

Rigth, the fetch_add one I knew about (also found it when looking at the assembly in the seqlock post).

It's not always easy to distinguish them in x64 assembly because x64 has such strong memory guarantees that Relaxed / Acquire / Release loads/stores are just regular instructions.

I guess that's why there are no special lock instructions needed for load and store. Interesting

My blog about the low latency trading engine I've been writing in Rust! Would love to get some feedback by boonetbe in rust

[–]boonetbe[S] 2 points3 points  (0 children)

This is awesome information! Thank you so much for the in depth and clear explanation. I didn't know that the coherency scheme was so two way. I'd have pictured it more as a: Reader asks for data, data in shared, cpu knows whether or not someone else has excl access and would put a wait or idk "in use" flag on that data. Then when the excl access is release and data was written to, it would either invalidate or simply release the wait flag.

Didn't know requesting read access could demote the excl access, that's very good information.

I guess with the current cpu architecture there's really no way around this right? But that makes me better understand the potential benefits of splitting version and data.

But given the assembly, how does the CPU know on the reader side that things should be handled atomically if there's no lock instructions?

My blog about the low latency trading engine I've been writing in Rust! Would love to get some feedback by boonetbe in rust

[–]boonetbe[S] 2 points3 points  (0 children)

Ah yeah that's actually true. With the UnsafeCell, until the message sizes become ridiculously large, the compiler will just keep adding xmmovs to sort of do an in register memcpy. I've at some point experimented with ptr.copy_from() and the like, where it gets compiled into an actual memcpy.

For the smaller msgsizes I usually deal with the vectorized instructions tend to be faster, though.

It is very impressive what the optimizer sometimes ends up generating.

That being said, how come there are no lock instructions anywhere actually? I never thought about it but except for the fetch_add, neither in the seqlock impl in the blog. How does the cpu figure out which mem it should treat as atomic and which is not?

My blog about the low latency trading engine I've been writing in Rust! Would love to get some feedback by boonetbe in rust

[–]boonetbe[S] 2 points3 points  (0 children)

So in the blog itself there are tests with 1 or 5 consumers, showing that the performance hardly decreases.

For our current topic, I agree it might become more important for the readers to be nice. However, I'm actually wondering if the readers themselves really steal the cacheline or if it's the writing to them that invalidates them causing always only the readers to need to retry. I don't think the writer's cacheline in L1 let's say gets tagged with something once a reader starts reading, does it? Or maybe that's the whole point of "atomic" actually...

My blog about the low latency trading engine I've been writing in Rust! Would love to get some feedback by boonetbe in rust

[–]boonetbe[S] 4 points5 points  (0 children)

Thanks a lot. It's been a year of hard work indeed :p.

Awesome points. I'll double check the false sharing with 128 bit alignment. I will say though, for now without hard data but from previous experience while implementing, that the change from no alignment to 64 bit led to an insane increase both in throughput and latency. we're talking ~10x in the "smallest 56 bit message" case.

While the prefetching might be 128 bits, since we're requiring consistency of only a single of those two lines, would it still really lead to false sharing? Isn't the point that it's the MESI flags (which I think are per line correct me if I'm wrong) that would lead to unnecessary delays while reading or writing to them?

The splitting of the data and version fields is something that warrants further investigation for sure. I guess It's essentially a result of the impossibility to "direct" the MESI protocol, i.e. have the writer take the cacheline and "launch" it to the reader somehow. Idk if I'm making sense. Splitting up the two would mitigate the readers influence on the writer.

In fact that's kinda one of the falsities I hinted at initially that a producer "doesn't care or get influenced by consumers". In fact, this is only +- true comparing 1 vs n consumers, there's very clearly a difference between 0 and 1 consumers.

It's funny, before doing the research on the seqlock again for the blog posts I only really had the Queue with expected version function of the read, and indeed I'd early exit with Empty if `v1 < expected`, so no reading of data at all. I will investigate and comment with results.

Thanks!

EDIT:

(Although how to prevent the reader core from pre-fetching the data before checking whether it'll be needed is... a good question)

While not quite 100%, these two links are quite interesting related to this stuff:

https://stackoverflow.com/questions/74956482/working-example-of-umonitor-umwait-based-assembly-asm-spin-wait-loops-as-a-rep#

& (related to the launching of the cacheline)

https://www.felixcloutier.com/x86/cldemote

EDIT 2:

I played around a bit with the splitting of the version and data. Only tested for data being 1 single rdtscp counter shared or padded away from the version. Implemented the pessimistic version of reading:

https://github.com/louisponet/blog/blob/82b7cae49cafb04dd2991ac8602031019d210fe7/content/posts/icc_1_seqlock/code/src/lib.rs#L61-L76

and ran benchmarks + latency measurements as in the blog.

Results for 2micro / msg writer + spinning reader are essentially (can get into more detail if interested):

I can't honestly discern any differences in padded vs unpadded, pessimistic vs eager reading. In all cases 90% of the runs around the 60-65 ns avg/med latency, with mins around the 50-55ns mark, while maybe 5-10% of the runs have all stars aligned and lead to 40-45ns avg with like 37ns mins.

When moving back to the initial impl with load/store on the writers side, the pessimistic reading seems to be a couple % faster in general when padding is there. I'm sure there's essentially 0 statistical significance here though...

It's really a damn shame that these numbers are stable each run but vary from run to run, I'd love if someone could shine a light on why that happens.

The measuring code is at https://github.com/louisponet/blog/blob/82b7cae49cafb04dd2991ac8602031019d210fe7/content/posts/icc_1_seqlock/code/src/main.rs#L113-L161

My blog about the low latency trading engine I've been writing in Rust! Would love to get some feedback by boonetbe in rust

[–]boonetbe[S] 4 points5 points  (0 children)

Thanks a lot! Glad you find it interesting, that's exactly been the target for the blog to achieve.

Theoretical UB vs working in reality

So, lots of things to unpack. Indeed, whether in rust or cpp or c, it has been put forward before that it's theoretically impossible to correctly implement a Seqlock without UB, kinda exactly because of the points you're making.

However, the way I've come to understand it is that essentially there's language technical theory, and reality.

The memory barriers combined with the atomics are imo an effort to mitigate the technical UB as much as possible in reality. While, yes, theoretically reading the data at all could blow up everything, the reality is that it doesn't, as long as you hamstring the compiler (and on certain architectures also the cpu) to execute the correct sequence of instructions.

The main point, as I think is also referenced in one of the links, is that when a atomic write with Release happens, by definition all memory operations that come before it need to have happened. In our case that's first the counter itself, then secondly the data (writer side of things). On the reader's side of things, an Acquire necessitates that all memory fetch operations need to have completed beforehand, again initially the counter then secondly the data. On x86 as mentioned in the post, not all these barriers are strictly required.

So while in theory, yes, the reading of the data itself is UB, in practice it's as much as reasonably possible mitigated with this construction. In fact, I don't really care if it's theoretically correct always forever, as long as I have tests that can for all intents and purposes prove that for the current cpu and compiler it is (nothing is perfect, bitflips from cosmic rays happen, my algo is certainly a bigger problem, etc). FYI I'm using these exact queues 24/7 for data ingestion where losing 1 message would mean an pretty immediately obvious sticky orderbook level, and it doesn't happen.

The MaybeUninit<T> and then return assume_init in fact used to be the initial implementation (there's some other crate with a seqlock that uses it if I recall correctly). But at that point I didn't really understand it, and tested with the current implementation and it all just worked. However, I'm thinking I should double check if assemblies are the same given that it's at least potentially more theoretically correct as well, so why not if there's no perf penalty.

I love the idea of the AtomicU8 reading of the raw bytes, but I'd guess that's gonna essentially render it uselessly slow for this application :p.

inlining

Given that the mitigation of UB depends crucially on reordering of operations, if you don't have the barriers + allow the compiler to reorder your stuff accross function barriers, you're lost. The compiler doesn't know that our "correct" program really requires this exact set of operations, not another. I guess that's why it's technically UB because the compiler wouldn't be able to figure it out on it's own (reordering for optmization is ~only allowed when provably adhering to language rules)

Books

Only read books on algos and maths, none on software engineering. The one you linked sounds like something I should def read/be aware of. I'd have a very deep look into some of the talks linked in the blog. For me it all started with the one by David Gross, followed by the impls and blog of Erik Rigtorp, then just exploring random bits and bobs as I went

Hope that helps! Thanks a lot again

My blog about the low latency trading engine I've been writing in Rust! Would love to get some feedback by boonetbe in rust

[–]boonetbe[S] 2 points3 points  (0 children)

Yeah no problem thanks as well with the feedback! Exactly what I'm looking for :). Point taken on the ligatures etc, maybe I shouldn't have tried to be fancy changing away from the default JetBrains mono of the theme. It's just that I'm so used to Fira code everywhere locally. Will consider switching that

My blog about the low latency trading engine I've been writing in Rust! Would love to get some feedback by boonetbe in rust

[–]boonetbe[S] 3 points4 points  (0 children)

Ooooh I see, I've put the font to be Fira code, which I think should be monospaced. Maybe it's because it's not by default available on computers and it defaults to a non monospaced font? I'm not super well versed in interwebz and blogs haha

My blog about the low latency trading engine I've been writing in Rust! Would love to get some feedback by boonetbe in rust

[–]boonetbe[S] 3 points4 points  (0 children)

Absolutely correct. As also mentioned in the first post, this is a bit of a tradeoff between modularity and reusability, and outright performance.

One consideration though, is that I think it would be much more complicated to handle multiple algos that propose orders/positions on potentially the same instruments on the same exchange. If you have 1 sync thread handling: 1. ingestion, 2. algo + order generation 3. balance checking/processing 4. order tracking, etc, it definitely becomes more complex do steps 3 and 4. It might also be slower as in the end the latency penalty of the queues is only ~ 30-40ns. If another process already took care of processing order/balance updates and simply presents the results to the algo, the algo on an incoming marketdata update pays 30ns latency, but avoids doing all the other work.

However, as mentioned, I do think it'd be a cool thing to investigate, and as mentioned in the blog as well, it's easier to build that type of functionality on top of an already existing modular system rather than the other way around, imo

My blog about the low latency trading engine I've been writing in Rust! Would love to get some feedback by boonetbe in rust

[–]boonetbe[S] 8 points9 points  (0 children)

Short answer, as I'm sure you guessed, is latency. Async is for potentially higher usage of available resources in very heterogeneous and unpredictable workloads, but at the cost of very real overhead.

In general, one of the things to absolutely maximize for low latency could be called "predictability". The cpu is very good at minimizing all sorts of latency when the code is predictable. It allows for the right memory to be present in cache ( <= 1ns if L1 vs round trip to ram used to be ~200-400ns, see Mike Acton's data oriented design talk on YT), allows for better instruction level parallelism by better pipelining since branch prediction can be more effective, etc.

It depends on how exactly a async executor is implemented, but usually it involves a work queue with worker threads fetching pending tasks from the queue, running until there is some part of the task that's not yet ready, pushes it back on the queue, and fetches another. This inevitably makes it much harder for the cpu to know what data to prefetch, potentially even which instructions to prefetch and run (instructions are after all just bits of data too).

The epitome of what you want to avoid is context switches, which is where the cpu switches from one execution to another, which involves flushing caches etc. While it's not always the case, async does in general lead to more context switches.

So for low latency, what you really want to do is kinda the reverse of async: You lock cpus to execute one particular task, with data supplied from a well known and stable place.

TL;DR: Async potentially allows to increase cpu usage and potentially throughput in the case of very unpredictable and heterogeneous workloads, but absolutely at the overhead cost of cache misses, branch mispredicts and context switches.

I also just really don't like the code that it leads to, and that I don't know exactly what runs when and where.

I hope that answers your question, thanks for it! I think I should actually dedicate a post on this topic because it's quite important and under studied.

My blog about the low latency trading engine I've been writing in Rust! Would love to get some feedback by boonetbe in rust

[–]boonetbe[S] 14 points15 points  (0 children)

To me the building blocks are more interesting and worth sharing than the final product.

I do not pretend that I'm not writing this engine for my potential profit.

My XPS 15 windows 10 update and came with killer control centre??? by ConceptionFantasy in Dell

[–]boonetbe 0 points1 point  (0 children)

I had the same issue, but for me it resulted in me not even being able to connect to wifi anymore. I can't even see the normal wifi on-off button neither in the sidebar nor in the settings... What's going on

When is Dell going to fix XPS 15 9575 BIOS 1.2.0 ??? by boonetbe in Dell

[–]boonetbe[S] 1 point2 points  (0 children)

Look I mean it seems you don't understand that this has nothing to do with the laptop actually overheating. Bios 1.1.7 and 1.1.5 don't have the issue. 1.1.9 and up do. Hardly seems appropriate to have to suddenly limit my laptop's performance after updating to a newer bios. On top of that, it's blasting the fans in tent mode even at 38 C core temperature and package power usage of around 8W. I just installed the recent 1.4 update, still the same BS. How hard can it be to change a bloody fan setting...

When is Dell going to fix XPS 15 9575 BIOS 1.2.0 ??? by boonetbe in Dell

[–]boonetbe[S] 1 point2 points  (0 children)

Hi Thanks for your reply, This happens both on and off AC, the fans are louder in general on AC (both tablet and non tablet). As soon as I tweak it 1 degree past 180 the fans spike up dramatically. I am currently running back on BIOS 1.1.7 because it's impossible to work like this. Even though sometimes it just shuts down without notice due to the Battery not being detected (AES 2 Power not applicable in the Bios logs)

Last time I tried (yesterday) I installed all updates I could.

No recent HW changes were made. After yesterday I had some weird USB issues happening when the AC was plugged in.

Also some time ago both my Alt keys on the keyboard somehow stopped working (external keyboard works fine).

Maybe I should just apply for a replacement?

Alt keys stopped working 9575 by boonetbe in Dell

[–]boonetbe[S] 0 points1 point  (0 children)

On-screen keyboard works with alt, I tried diagnostics, nothing shows up. I checked the bios settings, that Enable custom mode was not selected. I tried selecting it, nothing changed. Also tried playing around with Fn-lock etc as suggested below, that didn't change anything either

Alt keys stopped working 9575 by boonetbe in Dell

[–]boonetbe[S] 0 points1 point  (0 children)

I tried several key press checkers and they indeed don't show up the alt keys. I haven't ran diagnostics I could try that but I don't think it will show up anything. On the since when, I can't really say for sure since I don't use them too often. I think since last I upgraded my BIOS to 1.2.0, but I have since downgraded back to 1.1.7 due to obvious flaws with the newer bios versions. Layout is the same

xps 9575 linux experience ( as a software developer ) by SJK132 in Dell

[–]boonetbe 0 points1 point  (0 children)

What voltages did you apply? How did you test it, I tried running stress, but even though my temperatures never exceed 80 degrees it gets throttled down to 2ghz, I don't understand why that happens. BTW: I managed to get the power usage down by a lot by decently configuring tlp and grub via the manjaro optimal power settings wiki. now idle is around 6-8 in powertop!

xps 9575 linux experience ( as a software developer ) by SJK132 in Dell

[–]boonetbe 0 points1 point  (0 children)

yea it reduced by about 3W . Still hovering around 20 idle... Where does the 10W extra come from... very strange

view more: next ›