10 ms·

Fairly trivial base introduction to the subject. In my experience teaching undergrads they mostly get this stuff already. Their CompArch class has taught them

Fairly trivial base introduction to the subject. In my experience teaching undergrads they mostly get this stuff already. Their CompArch class has taught them the basics of branch prediction, cache coherence, and instruction caches; the trivial elements of performance. I'm somewhat surprised the piece doesn't deal at all with a classic performance killer, false sharing, although it seems mostly concerned with single-threaded latency. The total lack of "free" optimization tricks like fat LTO, PGO, or even the standardized hinting attributes ([[likely]], [[unlikely]]) for optimizing icache layout was also surprising. Neither this piece, nor my undergraduates, deal with the more nitty-gritty elements of performance. These mostly get into the usage specifics of particular IO APIs, synchronization primitives, IPC mechanisms, and some of the more esoteric compiler builtins. Besides all that, what the nascent low-latency programmer almost always lacks, and the hardest thing to instill in them, is a certain paranoia. A genuine fear, hate, and anger, towards unnecessary allocations, copies, and other performance killers. A creeping feeling that causes them to compulsively run the benchmarks through callgrind looking for calls into the object cache that miss and go to an allocator in the middle of the hot loop. I think a formative moment for me was when I was writing a low-latency server and I realized that constructing a vector I/O operation ended up being overall slower than just copying the small objects I was dealing with into a contiguous buffer and performing a single write. There's no such thing as a free copy, and that includes fat pointers.

mbo 2y ago
Out of interest, do you have any literature that you'd recommend instead?
- nickelpro 2y ago
  On the software side I don't think HFT is as special a space as this paper makes it out to be.[1] Each year at cppcon there's another half-dozen talks going in depth on different elements of performance that cover more ground collectively than any single paper will. Similarly, there's an immense amount of formal literature and textbooks out of the game development space that can be very useful to newcomers looking for structural approaches to high performance compute and IO loops. Games care a lot about local and network latency, the problem spaces aren't that far apart (and writing games is a very fun way to learn). I don't have specific recommendations for holistic introductions to the field. I learn new techniques primarily through building things, watching conference talks, reading source code of other low latency projects, and discussion with coworkers. [1]: HFT is quite special on the hardware side, which is discussed in the paper. The NICs, network stacks, and extensive integration of FPGAs do heavily differentiate the industry and I don't want to insinuate otherwise. You will not find a lot of SystemVerilog programmers at a typical video game studio.
  - Maxatar 2y ago
    As someone who does quant trading professionally and game development as a hobby, they both are performance sensitive, but they emphasize different kinds of performance. Trading is about minimizing latency while video games are about maximizing bandwidth. Video games try to cram as much work as possible within about 16 milliseconds whereas for most trading algorithms 16 milliseconds is too slow to do anything, you want to process and produce a response to input within the span of microseconds, which is 3 orders of magnitude faster than a single frame in a video game. The problem spaces really are quite distinct in this respect and a lot of techniques from one space don't really carry over to the other.
    - nickelpro 2y ago
      Of course, time spans are different. But read the paper, it's dealing with incredibly basic techniques. When we're speaking on the level of "data should be in cache" and "cold code should be far away from the hot path" the fields are practically identical. You're entirely correct that quant work is dealing with pure latency in situations where game engines might amortize throughput over multiple frames. But a question about "how do I get started in performance/latency work?" isn't usefully answered by "get a Hudson River Trading internship".
      - Maxatar 2y ago
        On that point we certainly agree.
    - ssfrr 2y ago
      I'm curious how HFT relates to pro audio programming. The timescale is close to gaming (usually <10ms for desktop PC work), but you really care about the tail of the distribution. All the audio processing happens in a high-priority callback that's called for every audio frame and needs complete within the time budget, so you typically never allocate, do IO, or use any blocking synchronization primitives [1]. It's not hard real-time like you're going to crash your car, but if you miss your deadline it causes an unacceptable and audible glitch. I've always been a bit surprised that Jane Street uses OCaml. I know they've put a lot of attention into the GC, but it still seems fundamentally indeterminate in a way that would make most audio devs nervous. [1]: http://www.rossbencina.com/code/real-time-audio-programming-101-time-waits-for-nothing http://www.rossbencina.com/code/real-time-audio-programming-...
- _aavaa_ 2y ago
  I'd recommend: https://www.computerenhance.com https://www.computerenhance.com The author has a strong game development (engine and tooling) background and I have found it incredibly useful. It also satisfies the requirement for "A genuine fear, hate, and anger, towards unnecessary allocations, copies, and other performance killers."
  - hi_dang_ 2y ago
    Very anecdotal but of the people I know in game studios who are tasked with engine work, and people who make a killing doing FPGA work for HFT firms, both camps shook their head at Casey’s HMH thing. Uniformly I do not know of a single professional developer of this sort of caliber who looked at HMH and thought it looks great. Quite the opposite. I think they found his approach and justifications unsound as it would instil awful practices of premature unfounded optimization and a disdain for normal library code in favour of hand-rolling your own half-baked implementations based on outdated trivia. I agree with them on the basis that HMH exposed an unprepared and inexperienced audience to something that has to be regarded with utmost care. For this, I refer to Jonathan Blow’s presentation of “a list is probably good enough” as an antidote. I think JB’s recommendations are more in line with actual practices, whereas Casey just raised red flags uniformly from here-and-now engine devs shipping multi platform games.
    - nickelpro 2y ago
      Casey's a fundamentalist, in the religious extremist sense. Just as a theologian might have something to learn from the most extremely devout, so it is that there is valuable information in Casey's proselytizing. But you should no more follow Casey in form and function than you would any other fundamentalist.
      - _aavaa_ 2y ago
        While gesturing at religion and saying he's a fundamentalist is an easy rhetorical technique, it doesn't add much. Yes good resources do exist, but they are few and far between. The number of new undergraduates from cs or software engineering who learned to think in the ways needed to make low latency applications are a rounding error based on my experience with them. Most forgot it, weren't taught it well, or never saw it at all. They are more worried about learning the syntax of the current hot framework rather than on anything even resembling "Avoid copies, never allocate, keep the hot path local". The religious comparison is also a telling one given the state of the industry; for we aren't the theologian, we're the common folk looking for someone or something to follow in order to write better code. Who are Casey's alternatives? Gesturing the cppcon as a learning resource has "read research papers to learn about a field" vibes. They can be highly informative and worth the effort, but not for beginners. Who are Casey's contemporaries? If he's a fundamentalist then the atheists are nowhere to be seen by the beginners. Instead we have agile ceremony shamans, clean code bible missionaries, tdd doomsday cults, oop/rust/haskell/etc. zealots, a thriving megachurch industry of Lambda schools, and the mother of all cargo cults masquerading as web dev.
contingencies 2y ago
How I might approach it. Interested in feedback from people closer to the space. First, split the load in to simple asset-specific data streams with a front-end FPGA for raw speed. Resist the temptation to actually execute here as the friction is too high for iteration, people, supply chain, etc. Input may be a FIX stream or similar, output is a series of asset-specific binary event streams along low-latency buses, split in to asset-specific segments of a scalable cluster of low-end MCUs. Second, get rid of the general purpose operating system assumption on your asset-specific MCU-based execution platform to enable faster turnaround using low-level code you can actually find people to write on hardware you can actually purchase. Third, profit? In such a setup you'd need to monitor the overall state with a general purpose OS based governor which could pause or change strategies by reprogramming the individual elements as required. Just how low are the latencies involved? At a certain point you're better off paying to get the hardware closer to the core than bothering with engineering, right? I guess that heavily depends on the rules and available DCs / link infrastructure offered by the exchanges or pools in question. I would guess a number of profitable operations probably don't disclose which pools they connect to and make a business of front-running, regulations or terms of service be damned. In such cases, the relative network geographic latency between two points of execution is more powerful than the absolute latency to one.
- nickelpro 2y ago
  The work I do is all in the single-to-low-double-digit microsecond range to give you an idea of timing constraints. I'm peripheral to HFT as a field though. > First, split the load in to simple asset-specific data streams with a front-end FPGA for raw speed. Resist the temptation to actually execute here as the friction is too high for iteration, people, supply chain, etc. This is largely incorrect, or more generously out-of-date, and it influences everything downstream of your explanation. Think of FPGAs as far more flexible GPUs and you're in the right arena. Input parsing and filtering are the obvious applications, but this is by no means the end state. A wide variety of sanity checks and monitoring features are pushed to the FPGAs, fixed calculation tasks, and output generation. It is possible for the entire stack for some (or most, or all) transactions to be implemented at the FPGA layer. For such transactions the time magnitudes are mid-to-high triple digit nanoseconds. The stacks I've seen with my own two eyeballs talked to supervision algorithms over PCIe (which themselves must be not-slow, but not in the same realm as <10us work), but otherwise nothing crazy fancy. This is well covered in the older academic work on the subject [1], which is why I'm fairly certain its long out of date by now. HRT has some public information on the pipeline they use for testing and verifying trading components implemented in HDL.[2] With the modern tooling, namely Verilator, development isn't significantly different than modern software development. If anything, SystemVerilog components are much easier to unit test than typical C++ code. Beyond that it gets way too firm-specific to really comment on anything, and I'm certainly not the one to comment. There's maybe three dozen HFT firms in the entire United States? It's not a huge field with widely acknowledged industry norms. [1]: https://ieeexplore.ieee.org/document/6299067 https://ieeexplore.ieee.org/document/6299067 [2]: https://www.hudsonrivertrading.com/hrtbeat/verify-custom-hardware/ https://www.hudsonrivertrading.com/hrtbeat/verify-custom-har...
chipdart 2y ago
> Fairly trivial base introduction to the subject. Might be, but low-latency C++, in spite of being a field on its own, is a desert of information. The best resources available at the moment on low-latency C++ are a hand full of lectures from C++ conferences which left much to be desired. Putting aside the temptation to grandstand, this document is an outstanding contribution to the field and perhaps the first authoritative reference on the subject. Vague claims that you can piece together similar info from other courses does not count as a contribution, and helps no one.
- Aurornis 2y ago
  > this document is an outstanding contribution to the field and perhaps the first authoritative reference on the subject. I don't know how you arrive at this conclusion. The document really is an introduction to the same basic performance techniques that have been covered over and over. Loop unrolling, inlining, and the other techniques have appeared in countless textbooks and blog posts already. I was disappointed to read the paper because they spent so much time covering really basic micro techniques but then didn't cover any of the more complicated issues mentioned in the parent comment. I don't understand why you'd think this is an "outstanding contribution to the field" when it's basically a recap of simple techniques that have been covered countless times in textbooks and other works already. This paper may seem profound if someone has never, ever read anything about performance optimization before, but it's likely mundane to anyone who has worked on performance before or even wondered what inlining or -Funroll-loops does while reading some other code.
  - fsloth 2y ago
    ”covered countless times in textbooks” What’s your favourite textbook on the subject?
    - roblatham 2y ago
      it's an oldie but _Advanced Compiler Design and Implementation_ covers these concepts really well in a language-independent way.
radarsat1 2y ago
> A creeping feeling that causes them to compulsively run the benchmarks through callgrind I'm happy I don't deal with such things these days, but I feel where the real paranoia always lies is the Heisenberg feeling of not even being able to even trust these things, the sneaky suspicion that the program is doing something different when I'm not measuring it.
PoignardAzur 2y ago
> optimization tricks like fat LTO, PGO, or even the standardized hinting attributes ([[likely]], [[unlikely]]) for optimizing icache layout If you do PGO, aren't hinting attributes counter-productive? In fact, the common wisdom I mostly see compiler people express is that most of the time they're counter-productive even without PGO, and modern compilers trust their own analysis passes more than they trust these hints and will usually ignore them. FWIW, the only times I've seen these hints in the wild were in places where the compiler could easily insert them, eg the null check after a malloc call.
- nickelpro 2y ago
  I said "or even", if you're regularly using PGO they're irrelevant, but not everyone regularly uses PGO in a way that covers all their workloads. The hinting attributes are exceptional for lone conditionals (not if/else trees) without obvious context to the compiler if it will frequently follow or skip the branch. Compilers are frequently conservative with such things and keep the code in the hot path. The [[likely]] attribute then doesn't matter so much, but [[unlikely]] is absolutely respected and gets the code out of the hot path, especially with inlined into a large section. Godbolt is useful to verify this but obviously there's no substitute for benchmarking the performance impact.
matheusmoreira 2y ago
> allocations, copies, and other performance killers Please elaborate on those other performance killers.

mbo 2y ago

Out of interest, do you have any literature that you'd recommend instead?

nickelpro 2y ago
On the software side I don't think HFT is as special a space as this paper makes it out to be.[1] Each year at cppcon there's another half-dozen talks going in depth on different elements of performance that cover more ground collectively than any single paper will. Similarly, there's an immense amount of formal literature and textbooks out of the game development space that can be very useful to newcomers looking for structural approaches to high performance compute and IO loops. Games care a lot about local and network latency, the problem spaces aren't that far apart (and writing games is a very fun way to learn). I don't have specific recommendations for holistic introductions to the field. I learn new techniques primarily through building things, watching conference talks, reading source code of other low latency projects, and discussion with coworkers. [1]: HFT is quite special on the hardware side, which is discussed in the paper. The NICs, network stacks, and extensive integration of FPGAs do heavily differentiate the industry and I don't want to insinuate otherwise. You will not find a lot of SystemVerilog programmers at a typical video game studio.
- Maxatar 2y ago
  As someone who does quant trading professionally and game development as a hobby, they both are performance sensitive, but they emphasize different kinds of performance. Trading is about minimizing latency while video games are about maximizing bandwidth. Video games try to cram as much work as possible within about 16 milliseconds whereas for most trading algorithms 16 milliseconds is too slow to do anything, you want to process and produce a response to input within the span of microseconds, which is 3 orders of magnitude faster than a single frame in a video game. The problem spaces really are quite distinct in this respect and a lot of techniques from one space don't really carry over to the other.
  - nickelpro 2y ago
    Of course, time spans are different. But read the paper, it's dealing with incredibly basic techniques. When we're speaking on the level of "data should be in cache" and "cold code should be far away from the hot path" the fields are practically identical. You're entirely correct that quant work is dealing with pure latency in situations where game engines might amortize throughput over multiple frames. But a question about "how do I get started in performance/latency work?" isn't usefully answered by "get a Hudson River Trading internship".
    - Maxatar 2y ago
      On that point we certainly agree.
  - ssfrr 2y ago
    I'm curious how HFT relates to pro audio programming. The timescale is close to gaming (usually <10ms for desktop PC work), but you really care about the tail of the distribution. All the audio processing happens in a high-priority callback that's called for every audio frame and needs complete within the time budget, so you typically never allocate, do IO, or use any blocking synchronization primitives [1]. It's not hard real-time like you're going to crash your car, but if you miss your deadline it causes an unacceptable and audible glitch. I've always been a bit surprised that Jane Street uses OCaml. I know they've put a lot of attention into the GC, but it still seems fundamentally indeterminate in a way that would make most audio devs nervous. [1]: http://www.rossbencina.com/code/real-time-audio-programming-101-time-waits-for-nothing http://www.rossbencina.com/code/real-time-audio-programming-...
_aavaa_ 2y ago
I'd recommend: https://www.computerenhance.com https://www.computerenhance.com The author has a strong game development (engine and tooling) background and I have found it incredibly useful. It also satisfies the requirement for "A genuine fear, hate, and anger, towards unnecessary allocations, copies, and other performance killers."
- hi_dang_ 2y ago
  Very anecdotal but of the people I know in game studios who are tasked with engine work, and people who make a killing doing FPGA work for HFT firms, both camps shook their head at Casey’s HMH thing. Uniformly I do not know of a single professional developer of this sort of caliber who looked at HMH and thought it looks great. Quite the opposite. I think they found his approach and justifications unsound as it would instil awful practices of premature unfounded optimization and a disdain for normal library code in favour of hand-rolling your own half-baked implementations based on outdated trivia. I agree with them on the basis that HMH exposed an unprepared and inexperienced audience to something that has to be regarded with utmost care. For this, I refer to Jonathan Blow’s presentation of “a list is probably good enough” as an antidote. I think JB’s recommendations are more in line with actual practices, whereas Casey just raised red flags uniformly from here-and-now engine devs shipping multi platform games.
  - nickelpro 2y ago
    Casey's a fundamentalist, in the religious extremist sense. Just as a theologian might have something to learn from the most extremely devout, so it is that there is valuable information in Casey's proselytizing. But you should no more follow Casey in form and function than you would any other fundamentalist.
    - _aavaa_ 2y ago
      While gesturing at religion and saying he's a fundamentalist is an easy rhetorical technique, it doesn't add much. Yes good resources do exist, but they are few and far between. The number of new undergraduates from cs or software engineering who learned to think in the ways needed to make low latency applications are a rounding error based on my experience with them. Most forgot it, weren't taught it well, or never saw it at all. They are more worried about learning the syntax of the current hot framework rather than on anything even resembling "Avoid copies, never allocate, keep the hot path local". The religious comparison is also a telling one given the state of the industry; for we aren't the theologian, we're the common folk looking for someone or something to follow in order to write better code. Who are Casey's alternatives? Gesturing the cppcon as a learning resource has "read research papers to learn about a field" vibes. They can be highly informative and worth the effort, but not for beginners. Who are Casey's contemporaries? If he's a fundamentalist then the atheists are nowhere to be seen by the beginners. Instead we have agile ceremony shamans, clean code bible missionaries, tdd doomsday cults, oop/rust/haskell/etc. zealots, a thriving megachurch industry of Lambda schools, and the mother of all cargo cults masquerading as web dev.

contingencies 2y ago

How I might approach it. Interested in feedback from people closer to the space. First, split the load in to simple asset-specific data streams with a front-end FPGA for raw speed. Resist the temptation to actually execute here as the friction is too high for iteration, people, supply chain, etc. Input may be a FIX stream or similar, output is a series of asset-specific binary event streams along low-latency buses, split in to asset-specific segments of a scalable cluster of low-end MCUs. Second, get rid of the general purpose operating system assumption on your asset-specific MCU-based execution platform to enable faster turnaround using low-level code you can actually find people to write on hardware you can actually purchase. Third, profit? In such a setup you'd need to monitor the overall state with a general purpose OS based governor which could pause or change strategies by reprogramming the individual elements as required. Just how low are the latencies involved? At a certain point you're better off paying to get the hardware closer to the core than bothering with engineering, right? I guess that heavily depends on the rules and available DCs / link infrastructure offered by the exchanges or pools in question. I would guess a number of profitable operations probably don't disclose which pools they connect to and make a business of front-running, regulations or terms of service be damned. In such cases, the relative network geographic latency between two points of execution is more powerful than the absolute latency to one.

nickelpro 2y ago
The work I do is all in the single-to-low-double-digit microsecond range to give you an idea of timing constraints. I'm peripheral to HFT as a field though. > First, split the load in to simple asset-specific data streams with a front-end FPGA for raw speed. Resist the temptation to actually execute here as the friction is too high for iteration, people, supply chain, etc. This is largely incorrect, or more generously out-of-date, and it influences everything downstream of your explanation. Think of FPGAs as far more flexible GPUs and you're in the right arena. Input parsing and filtering are the obvious applications, but this is by no means the end state. A wide variety of sanity checks and monitoring features are pushed to the FPGAs, fixed calculation tasks, and output generation. It is possible for the entire stack for some (or most, or all) transactions to be implemented at the FPGA layer. For such transactions the time magnitudes are mid-to-high triple digit nanoseconds. The stacks I've seen with my own two eyeballs talked to supervision algorithms over PCIe (which themselves must be not-slow, but not in the same realm as <10us work), but otherwise nothing crazy fancy. This is well covered in the older academic work on the subject [1], which is why I'm fairly certain its long out of date by now. HRT has some public information on the pipeline they use for testing and verifying trading components implemented in HDL.[2] With the modern tooling, namely Verilator, development isn't significantly different than modern software development. If anything, SystemVerilog components are much easier to unit test than typical C++ code. Beyond that it gets way too firm-specific to really comment on anything, and I'm certainly not the one to comment. There's maybe three dozen HFT firms in the entire United States? It's not a huge field with widely acknowledged industry norms. [1]: https://ieeexplore.ieee.org/document/6299067 https://ieeexplore.ieee.org/document/6299067 [2]: https://www.hudsonrivertrading.com/hrtbeat/verify-custom-hardware/ https://www.hudsonrivertrading.com/hrtbeat/verify-custom-har...

chipdart 2y ago

> Fairly trivial base introduction to the subject. Might be, but low-latency C++, in spite of being a field on its own, is a desert of information. The best resources available at the moment on low-latency C++ are a hand full of lectures from C++ conferences which left much to be desired. Putting aside the temptation to grandstand, this document is an outstanding contribution to the field and perhaps the first authoritative reference on the subject. Vague claims that you can piece together similar info from other courses does not count as a contribution, and helps no one.

Aurornis 2y ago
> this document is an outstanding contribution to the field and perhaps the first authoritative reference on the subject. I don't know how you arrive at this conclusion. The document really is an introduction to the same basic performance techniques that have been covered over and over. Loop unrolling, inlining, and the other techniques have appeared in countless textbooks and blog posts already. I was disappointed to read the paper because they spent so much time covering really basic micro techniques but then didn't cover any of the more complicated issues mentioned in the parent comment. I don't understand why you'd think this is an "outstanding contribution to the field" when it's basically a recap of simple techniques that have been covered countless times in textbooks and other works already. This paper may seem profound if someone has never, ever read anything about performance optimization before, but it's likely mundane to anyone who has worked on performance before or even wondered what inlining or -Funroll-loops does while reading some other code.
- fsloth 2y ago
  ”covered countless times in textbooks” What’s your favourite textbook on the subject?
  - roblatham 2y ago
    it's an oldie but _Advanced Compiler Design and Implementation_ covers these concepts really well in a language-independent way.

radarsat1 2y ago

> A creeping feeling that causes them to compulsively run the benchmarks through callgrind I'm happy I don't deal with such things these days, but I feel where the real paranoia always lies is the Heisenberg feeling of not even being able to even trust these things, the sneaky suspicion that the program is doing something different when I'm not measuring it.

PoignardAzur 2y ago

> optimization tricks like fat LTO, PGO, or even the standardized hinting attributes ([[likely]], [[unlikely]]) for optimizing icache layout If you do PGO, aren't hinting attributes counter-productive? In fact, the common wisdom I mostly see compiler people express is that most of the time they're counter-productive even without PGO, and modern compilers trust their own analysis passes more than they trust these hints and will usually ignore them. FWIW, the only times I've seen these hints in the wild were in places where the compiler could easily insert them, eg the null check after a malloc call.

nickelpro 2y ago
I said "or even", if you're regularly using PGO they're irrelevant, but not everyone regularly uses PGO in a way that covers all their workloads. The hinting attributes are exceptional for lone conditionals (not if/else trees) without obvious context to the compiler if it will frequently follow or skip the branch. Compilers are frequently conservative with such things and keep the code in the hot path. The [[likely]] attribute then doesn't matter so much, but [[unlikely]] is absolutely respected and gets the code out of the hot path, especially with inlined into a large section. Godbolt is useful to verify this but obviously there's no substitute for benchmarking the performance impact.

matheusmoreira 2y ago

> allocations, copies, and other performance killers Please elaborate on those other performance killers.